1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/share/vm/adlc/dfa.cpp Sat Dec 01 00:00:00 2007 +0000 1.3 @@ -0,0 +1,1021 @@ 1.4 +/* 1.5 + * Copyright 1997-2004 Sun Microsystems, Inc. All Rights Reserved. 1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1.7 + * 1.8 + * This code is free software; you can redistribute it and/or modify it 1.9 + * under the terms of the GNU General Public License version 2 only, as 1.10 + * published by the Free Software Foundation. 1.11 + * 1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT 1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1.15 + * version 2 for more details (a copy is included in the LICENSE file that 1.16 + * accompanied this code). 1.17 + * 1.18 + * You should have received a copy of the GNU General Public License version 1.19 + * 2 along with this work; if not, write to the Free Software Foundation, 1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1.21 + * 1.22 + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or 1.24 + * have any questions. 1.25 + * 1.26 + */ 1.27 + 1.28 +// DFA.CPP - Method definitions for outputting the matcher DFA from ADLC 1.29 +#include "adlc.hpp" 1.30 + 1.31 +//---------------------------Switches for debugging output--------------------- 1.32 +static bool debug_output = false; 1.33 +static bool debug_output1 = false; // top level chain rules 1.34 + 1.35 +//---------------------------Access to internals of class State---------------- 1.36 +static const char *sLeft = "_kids[0]"; 1.37 +static const char *sRight = "_kids[1]"; 1.38 + 1.39 +//---------------------------DFA productions----------------------------------- 1.40 +static const char *dfa_production = "DFA_PRODUCTION"; 1.41 +static const char *dfa_production_set_valid = "DFA_PRODUCTION__SET_VALID"; 1.42 + 1.43 +//---------------------------Production State---------------------------------- 1.44 +static const char *knownInvalid = "knownInvalid"; // The result does NOT have a rule defined 1.45 +static const char *knownValid = "knownValid"; // The result must be produced by a rule 1.46 +static const char *unknownValid = "unknownValid"; // Unknown (probably due to a child or predicate constraint) 1.47 + 1.48 +static const char *noConstraint = "noConstraint"; // No constraints seen so far 1.49 +static const char *hasConstraint = "hasConstraint"; // Within the first constraint 1.50 + 1.51 + 1.52 +//------------------------------Production------------------------------------ 1.53 +// Track the status of productions for a particular result 1.54 +class Production { 1.55 +public: 1.56 + const char *_result; 1.57 + const char *_constraint; 1.58 + const char *_valid; 1.59 + Expr *_cost_lb; // Cost lower bound for this production 1.60 + Expr *_cost_ub; // Cost upper bound for this production 1.61 + 1.62 +public: 1.63 + Production(const char *result, const char *constraint, const char *valid); 1.64 + ~Production() {}; 1.65 + 1.66 + void initialize(); // reset to be an empty container 1.67 + 1.68 + const char *valid() const { return _valid; } 1.69 + Expr *cost_lb() const { return (Expr *)_cost_lb; } 1.70 + Expr *cost_ub() const { return (Expr *)_cost_ub; } 1.71 + 1.72 + void print(); 1.73 +}; 1.74 + 1.75 + 1.76 +//------------------------------ProductionState-------------------------------- 1.77 +// Track the status of all production rule results 1.78 +// Reset for each root opcode (e.g., Op_RegI, Op_AddI, ...) 1.79 +class ProductionState { 1.80 +private: 1.81 + Dict _production; // map result of production, char*, to information or NULL 1.82 + const char *_constraint; 1.83 + 1.84 +public: 1.85 + // cmpstr does string comparisions. hashstr computes a key. 1.86 + ProductionState(Arena *arena) : _production(cmpstr, hashstr, arena) { initialize(); }; 1.87 + ~ProductionState() { }; 1.88 + 1.89 + void initialize(); // reset local and dictionary state 1.90 + 1.91 + const char *constraint(); 1.92 + void set_constraint(const char *constraint); // currently working inside of constraints 1.93 + 1.94 + const char *valid(const char *result); // unknownValid, or status for this production 1.95 + void set_valid(const char *result); // if not constrained, set status to knownValid 1.96 + 1.97 + Expr *cost_lb(const char *result); 1.98 + Expr *cost_ub(const char *result); 1.99 + void set_cost_bounds(const char *result, const Expr *cost, bool has_state_check, bool has_cost_check); 1.100 + 1.101 + // Return the Production associated with the result, 1.102 + // or create a new Production and insert it into the dictionary. 1.103 + Production *getProduction(const char *result); 1.104 + 1.105 + void print(); 1.106 + 1.107 +private: 1.108 + // Disable public use of constructor, copy-ctor, ... 1.109 + ProductionState( ) : _production(cmpstr, hashstr, Form::arena) { assert( false, "NotImplemented"); }; 1.110 + ProductionState( const ProductionState & ) : _production(cmpstr, hashstr, Form::arena) { assert( false, "NotImplemented"); }; // Deep-copy 1.111 +}; 1.112 + 1.113 + 1.114 +//---------------------------Helper Functions---------------------------------- 1.115 +// cost_check template: 1.116 +// 1) if (STATE__NOT_YET_VALID(EBXREGI) || _cost[EBXREGI] > c) { 1.117 +// 2) DFA_PRODUCTION__SET_VALID(EBXREGI, cmovI_memu_rule, c) 1.118 +// 3) } 1.119 +// 1.120 +static void cost_check(FILE *fp, const char *spaces, 1.121 + const char *arrayIdx, const Expr *cost, const char *rule, ProductionState &status) { 1.122 + bool state_check = false; // true if this production needs to check validity 1.123 + bool cost_check = false; // true if this production needs to check cost 1.124 + bool cost_is_above_upper_bound = false; // true if this production is unnecessary due to high cost 1.125 + bool cost_is_below_lower_bound = false; // true if this production replaces a higher cost production 1.126 + 1.127 + // Get information about this production 1.128 + const Expr *previous_ub = status.cost_ub(arrayIdx); 1.129 + if( !previous_ub->is_unknown() ) { 1.130 + if( previous_ub->less_than_or_equal(cost) ) { 1.131 + cost_is_above_upper_bound = true; 1.132 + if( debug_output ) { fprintf(fp, "// Previous rule with lower cost than: %s === %s_rule costs %s\n", arrayIdx, rule, cost->as_string()); } 1.133 + } 1.134 + } 1.135 + 1.136 + const Expr *previous_lb = status.cost_lb(arrayIdx); 1.137 + if( !previous_lb->is_unknown() ) { 1.138 + if( cost->less_than_or_equal(previous_lb) ) { 1.139 + cost_is_below_lower_bound = true; 1.140 + if( debug_output ) { fprintf(fp, "// Previous rule with higher cost\n"); } 1.141 + } 1.142 + } 1.143 + 1.144 + // line 1) 1.145 + // Check for validity and compare to other match costs 1.146 + const char *validity_check = status.valid(arrayIdx); 1.147 + if( validity_check == unknownValid ) { 1.148 + fprintf(fp, "%sif (STATE__NOT_YET_VALID(%s) || _cost[%s] > %s) {\n", spaces, arrayIdx, arrayIdx, cost->as_string()); 1.149 + state_check = true; 1.150 + cost_check = true; 1.151 + } 1.152 + else if( validity_check == knownInvalid ) { 1.153 + if( debug_output ) { fprintf(fp, "%s// %s KNOWN_INVALID \n", spaces, arrayIdx); } 1.154 + } 1.155 + else if( validity_check == knownValid ) { 1.156 + if( cost_is_above_upper_bound ) { 1.157 + // production cost is known to be too high. 1.158 + return; 1.159 + } else if( cost_is_below_lower_bound ) { 1.160 + // production will unconditionally overwrite a previous production that had higher cost 1.161 + } else { 1.162 + fprintf(fp, "%sif ( /* %s KNOWN_VALID || */ _cost[%s] > %s) {\n", spaces, arrayIdx, arrayIdx, cost->as_string()); 1.163 + cost_check = true; 1.164 + } 1.165 + } 1.166 + 1.167 + // line 2) 1.168 + // no need to set State vector if our state is knownValid 1.169 + const char *production = (validity_check == knownValid) ? dfa_production : dfa_production_set_valid; 1.170 + fprintf(fp, "%s %s(%s, %s_rule, %s)", spaces, production, arrayIdx, rule, cost->as_string() ); 1.171 + if( validity_check == knownValid ) { 1.172 + if( cost_is_below_lower_bound ) { fprintf(fp, "\t // overwrites higher cost rule"); } 1.173 + } 1.174 + fprintf(fp, "\n"); 1.175 + 1.176 + // line 3) 1.177 + if( cost_check || state_check ) { 1.178 + fprintf(fp, "%s}\n", spaces); 1.179 + } 1.180 + 1.181 + status.set_cost_bounds(arrayIdx, cost, state_check, cost_check); 1.182 + 1.183 + // Update ProductionState 1.184 + if( validity_check != knownValid ) { 1.185 + // set State vector if not previously known 1.186 + status.set_valid(arrayIdx); 1.187 + } 1.188 +} 1.189 + 1.190 + 1.191 +//---------------------------child_test---------------------------------------- 1.192 +// Example: 1.193 +// STATE__VALID_CHILD(_kids[0], FOO) && STATE__VALID_CHILD(_kids[1], BAR) 1.194 +// Macro equivalent to: _kids[0]->valid(FOO) && _kids[1]->valid(BAR) 1.195 +// 1.196 +static void child_test(FILE *fp, MatchList &mList) { 1.197 + if( mList._lchild ) // If left child, check it 1.198 + fprintf(fp, "STATE__VALID_CHILD(_kids[0], %s)", ArchDesc::getMachOperEnum(mList._lchild)); 1.199 + if( mList._lchild && mList._rchild ) // If both, add the "&&" 1.200 + fprintf(fp, " && " ); 1.201 + if( mList._rchild ) // If right child, check it 1.202 + fprintf(fp, "STATE__VALID_CHILD(_kids[1], %s)", ArchDesc::getMachOperEnum(mList._rchild)); 1.203 +} 1.204 + 1.205 +//---------------------------calc_cost----------------------------------------- 1.206 +// Example: 1.207 +// unsigned int c = _kids[0]->_cost[FOO] + _kids[1]->_cost[BAR] + 5; 1.208 +// 1.209 +Expr *ArchDesc::calc_cost(FILE *fp, const char *spaces, MatchList &mList, ProductionState &status) { 1.210 + fprintf(fp, "%sunsigned int c = ", spaces); 1.211 + Expr *c = new Expr("0"); 1.212 + if (mList._lchild ) { // If left child, add it in 1.213 + sprintf(Expr::buffer(), "_kids[0]->_cost[%s]", ArchDesc::getMachOperEnum(mList._lchild)); 1.214 + c->add(Expr::buffer()); 1.215 +} 1.216 + if (mList._rchild) { // If right child, add it in 1.217 + sprintf(Expr::buffer(), "_kids[1]->_cost[%s]", ArchDesc::getMachOperEnum(mList._rchild)); 1.218 + c->add(Expr::buffer()); 1.219 + } 1.220 + // Add in cost of this rule 1.221 + const char *mList_cost = mList.get_cost(); 1.222 + c->add(mList_cost, *this); 1.223 + 1.224 + fprintf(fp, "%s;\n", c->as_string()); 1.225 + c->set_external_name("c"); 1.226 + return c; 1.227 +} 1.228 + 1.229 + 1.230 +//---------------------------gen_match----------------------------------------- 1.231 +void ArchDesc::gen_match(FILE *fp, MatchList &mList, ProductionState &status, Dict &operands_chained_from) { 1.232 + const char *spaces4 = " "; 1.233 + const char *spaces6 = " "; 1.234 + 1.235 + fprintf(fp, "%s", spaces4); 1.236 + // Only generate child tests if this is not a leaf node 1.237 + bool has_child_constraints = mList._lchild || mList._rchild; 1.238 + const char *predicate_test = mList.get_pred(); 1.239 + if( has_child_constraints || predicate_test ) { 1.240 + // Open the child-and-predicate-test braces 1.241 + fprintf(fp, "if( "); 1.242 + status.set_constraint(hasConstraint); 1.243 + child_test(fp, mList); 1.244 + // Only generate predicate test if one exists for this match 1.245 + if( predicate_test ) { 1.246 + if( has_child_constraints ) { fprintf(fp," &&\n"); } 1.247 + fprintf(fp, "%s %s", spaces6, predicate_test); 1.248 + } 1.249 + // End of outer tests 1.250 + fprintf(fp," ) "); 1.251 + } else { 1.252 + // No child or predicate test needed 1.253 + status.set_constraint(noConstraint); 1.254 + } 1.255 + 1.256 + // End of outer tests 1.257 + fprintf(fp,"{\n"); 1.258 + 1.259 + // Calculate cost of this match 1.260 + const Expr *cost = calc_cost(fp, spaces6, mList, status); 1.261 + // Check against other match costs, and update cost & rule vectors 1.262 + cost_check(fp, spaces6, ArchDesc::getMachOperEnum(mList._resultStr), cost, mList._opcode, status); 1.263 + 1.264 + // If this is a member of an operand class, update the class cost & rule 1.265 + expand_opclass( fp, spaces6, cost, mList._resultStr, status); 1.266 + 1.267 + // Check if this rule should be used to generate the chains as well. 1.268 + const char *rule = /* set rule to "Invalid" for internal operands */ 1.269 + strcmp(mList._opcode,mList._resultStr) ? mList._opcode : "Invalid"; 1.270 + 1.271 + // If this rule produces an operand which has associated chain rules, 1.272 + // update the operands with the chain rule + this rule cost & this rule. 1.273 + chain_rule(fp, spaces6, mList._resultStr, cost, rule, operands_chained_from, status); 1.274 + 1.275 + // Close the child-and-predicate-test braces 1.276 + fprintf(fp, " }\n"); 1.277 + 1.278 +} 1.279 + 1.280 + 1.281 +//---------------------------expand_opclass------------------------------------ 1.282 +// Chain from one result_type to all other members of its operand class 1.283 +void ArchDesc::expand_opclass(FILE *fp, const char *indent, const Expr *cost, 1.284 + const char *result_type, ProductionState &status) { 1.285 + const Form *form = _globalNames[result_type]; 1.286 + OperandForm *op = form ? form->is_operand() : NULL; 1.287 + if( op && op->_classes.count() > 0 ) { 1.288 + if( debug_output ) { fprintf(fp, "// expand operand classes for operand: %s \n", (char *)op->_ident ); } // %%%%% Explanation 1.289 + // Iterate through all operand classes which include this operand 1.290 + op->_classes.reset(); 1.291 + const char *oclass; 1.292 + // Expr *cCost = new Expr(cost); 1.293 + while( (oclass = op->_classes.iter()) != NULL ) 1.294 + // Check against other match costs, and update cost & rule vectors 1.295 + cost_check(fp, indent, ArchDesc::getMachOperEnum(oclass), cost, result_type, status); 1.296 + } 1.297 +} 1.298 + 1.299 +//---------------------------chain_rule---------------------------------------- 1.300 +// Starting at 'operand', check if we know how to automatically generate other results 1.301 +void ArchDesc::chain_rule(FILE *fp, const char *indent, const char *operand, 1.302 + const Expr *icost, const char *irule, Dict &operands_chained_from, ProductionState &status) { 1.303 + 1.304 + // Check if we have already generated chains from this starting point 1.305 + if( operands_chained_from[operand] != NULL ) { 1.306 + return; 1.307 + } else { 1.308 + operands_chained_from.Insert( operand, operand); 1.309 + } 1.310 + if( debug_output ) { fprintf(fp, "// chain rules starting from: %s and %s \n", (char *)operand, (char *)irule); } // %%%%% Explanation 1.311 + 1.312 + ChainList *lst = (ChainList *)_chainRules[operand]; 1.313 + if (lst) { 1.314 + // printf("\nChain from <%s> at cost #%s\n",operand, icost ? icost : "_"); 1.315 + const char *result, *cost, *rule; 1.316 + for(lst->reset(); (lst->iter(result,cost,rule)) == true; ) { 1.317 + // Do not generate operands that are already available 1.318 + if( operands_chained_from[result] != NULL ) { 1.319 + continue; 1.320 + } else { 1.321 + // Compute the cost for previous match + chain_rule_cost 1.322 + // total_cost = icost + cost; 1.323 + Expr *total_cost = icost->clone(); // icost + cost 1.324 + total_cost->add(cost, *this); 1.325 + 1.326 + // Check for transitive chain rules 1.327 + Form *form = (Form *)_globalNames[rule]; 1.328 + if ( ! form->is_instruction()) { 1.329 + // printf(" result=%s cost=%s rule=%s\n", result, total_cost, rule); 1.330 + // Check against other match costs, and update cost & rule vectors 1.331 + const char *reduce_rule = strcmp(irule,"Invalid") ? irule : rule; 1.332 + cost_check(fp, indent, ArchDesc::getMachOperEnum(result), total_cost, reduce_rule, status); 1.333 + chain_rule(fp, indent, result, total_cost, irule, operands_chained_from, status); 1.334 + } else { 1.335 + // printf(" result=%s cost=%s rule=%s\n", result, total_cost, rule); 1.336 + // Check against other match costs, and update cost & rule vectors 1.337 + cost_check(fp, indent, ArchDesc::getMachOperEnum(result), total_cost, rule, status); 1.338 + chain_rule(fp, indent, result, total_cost, rule, operands_chained_from, status); 1.339 + } 1.340 + 1.341 + // If this is a member of an operand class, update class cost & rule 1.342 + expand_opclass( fp, indent, total_cost, result, status ); 1.343 + } 1.344 + } 1.345 + } 1.346 +} 1.347 + 1.348 +//---------------------------prune_matchlist----------------------------------- 1.349 +// Check for duplicate entries in a matchlist, and prune out the higher cost 1.350 +// entry. 1.351 +void ArchDesc::prune_matchlist(Dict &minimize, MatchList &mlist) { 1.352 + 1.353 +} 1.354 + 1.355 +//---------------------------buildDFA------------------------------------------ 1.356 +// DFA is a large switch with case statements for each ideal opcode encountered 1.357 +// in any match rule in the ad file. Each case has a series of if's to handle 1.358 +// the match or fail decisions. The matches test the cost function of that 1.359 +// rule, and prune any cases which are higher cost for the same reduction. 1.360 +// In order to generate the DFA we walk the table of ideal opcode/MatchList 1.361 +// pairs generated by the ADLC front end to build the contents of the case 1.362 +// statements (a series of if statements). 1.363 +void ArchDesc::buildDFA(FILE* fp) { 1.364 + int i; 1.365 + // Remember operands that are the starting points for chain rules. 1.366 + // Prevent cycles by checking if we have already generated chain. 1.367 + Dict operands_chained_from(cmpstr, hashstr, Form::arena); 1.368 + 1.369 + // Hash inputs to match rules so that final DFA contains only one entry for 1.370 + // each match pattern which is the low cost entry. 1.371 + Dict minimize(cmpstr, hashstr, Form::arena); 1.372 + 1.373 + // Track status of dfa for each resulting production 1.374 + // reset for each ideal root. 1.375 + ProductionState status(Form::arena); 1.376 + 1.377 + // Output the start of the DFA method into the output file 1.378 + 1.379 + fprintf(fp, "\n"); 1.380 + fprintf(fp, "//------------------------- Source -----------------------------------------\n"); 1.381 + // Do not put random source code into the DFA. 1.382 + // If there are constants which need sharing, put them in "source_hpp" forms. 1.383 + // _source.output(fp); 1.384 + fprintf(fp, "\n"); 1.385 + fprintf(fp, "//------------------------- Attributes -------------------------------------\n"); 1.386 + _attributes.output(fp); 1.387 + fprintf(fp, "\n"); 1.388 + fprintf(fp, "//------------------------- Macros -----------------------------------------\n"); 1.389 + // #define DFA_PRODUCTION(result, rule, cost)\ 1.390 + // _cost[ (result) ] = cost; _rule[ (result) ] = rule; 1.391 + fprintf(fp, "#define %s(result, rule, cost)\\\n", dfa_production); 1.392 + fprintf(fp, " _cost[ (result) ] = cost; _rule[ (result) ] = rule;\n"); 1.393 + fprintf(fp, "\n"); 1.394 + 1.395 + // #define DFA_PRODUCTION__SET_VALID(result, rule, cost)\ 1.396 + // DFA_PRODUCTION( (result), (rule), (cost) ); STATE__SET_VALID( (result) ); 1.397 + fprintf(fp, "#define %s(result, rule, cost)\\\n", dfa_production_set_valid); 1.398 + fprintf(fp, " %s( (result), (rule), (cost) ); STATE__SET_VALID( (result) );\n", dfa_production); 1.399 + fprintf(fp, "\n"); 1.400 + 1.401 + fprintf(fp, "//------------------------- DFA --------------------------------------------\n"); 1.402 + 1.403 + fprintf(fp, 1.404 +"// DFA is a large switch with case statements for each ideal opcode encountered\n" 1.405 +"// in any match rule in the ad file. Each case has a series of if's to handle\n" 1.406 +"// the match or fail decisions. The matches test the cost function of that\n" 1.407 +"// rule, and prune any cases which are higher cost for the same reduction.\n" 1.408 +"// In order to generate the DFA we walk the table of ideal opcode/MatchList\n" 1.409 +"// pairs generated by the ADLC front end to build the contents of the case\n" 1.410 +"// statements (a series of if statements).\n" 1.411 +); 1.412 + fprintf(fp, "\n"); 1.413 + fprintf(fp, "\n"); 1.414 + if (_dfa_small) { 1.415 + // Now build the individual routines just like the switch entries in large version 1.416 + // Iterate over the table of MatchLists, start at first valid opcode of 1 1.417 + for (i = 1; i < _last_opcode; i++) { 1.418 + if (_mlistab[i] == NULL) continue; 1.419 + // Generate the routine header statement for this opcode 1.420 + fprintf(fp, "void State::_sub_Op_%s(const Node *n){\n", NodeClassNames[i]); 1.421 + // Generate body. Shared for both inline and out-of-line version 1.422 + gen_dfa_state_body(fp, minimize, status, operands_chained_from, i); 1.423 + // End of routine 1.424 + fprintf(fp, "}\n"); 1.425 + } 1.426 + } 1.427 + fprintf(fp, "bool State::DFA"); 1.428 + fprintf(fp, "(int opcode, const Node *n) {\n"); 1.429 + fprintf(fp, " switch(opcode) {\n"); 1.430 + 1.431 + // Iterate over the table of MatchLists, start at first valid opcode of 1 1.432 + for (i = 1; i < _last_opcode; i++) { 1.433 + if (_mlistab[i] == NULL) continue; 1.434 + // Generate the case statement for this opcode 1.435 + if (_dfa_small) { 1.436 + fprintf(fp, " case Op_%s: { _sub_Op_%s(n);\n", NodeClassNames[i], NodeClassNames[i]); 1.437 + } else { 1.438 + fprintf(fp, " case Op_%s: {\n", NodeClassNames[i]); 1.439 + // Walk the list, compacting it 1.440 + gen_dfa_state_body(fp, minimize, status, operands_chained_from, i); 1.441 + } 1.442 + // Print the "break" 1.443 + fprintf(fp, " break;\n"); 1.444 + fprintf(fp, " }\n"); 1.445 + } 1.446 + 1.447 + // Generate the default case for switch(opcode) 1.448 + fprintf(fp, " \n"); 1.449 + fprintf(fp, " default:\n"); 1.450 + fprintf(fp, " tty->print(\"Default case invoked for: \\n\");\n"); 1.451 + fprintf(fp, " tty->print(\" opcode = %cd, \\\"%cs\\\"\\n\", opcode, NodeClassNames[opcode]);\n", '%', '%'); 1.452 + fprintf(fp, " return false;\n"); 1.453 + fprintf(fp, " }\n"); 1.454 + 1.455 + // Return status, indicating a successful match. 1.456 + fprintf(fp, " return true;\n"); 1.457 + // Generate the closing brace for method Matcher::DFA 1.458 + fprintf(fp, "}\n"); 1.459 + Expr::check_buffers(); 1.460 +} 1.461 + 1.462 + 1.463 +class dfa_shared_preds { 1.464 + enum { count = 2 }; 1.465 + 1.466 + static bool _found[count]; 1.467 + static const char* _type [count]; 1.468 + static const char* _var [count]; 1.469 + static const char* _pred [count]; 1.470 + 1.471 + static void check_index(int index) { assert( 0 <= index && index < count, "Invalid index"); } 1.472 + 1.473 + // Confirm that this is a separate sub-expression. 1.474 + // Only need to catch common cases like " ... && shared ..." 1.475 + // and avoid hazardous ones like "...->shared" 1.476 + static bool valid_loc(char *pred, char *shared) { 1.477 + // start of predicate is valid 1.478 + if( shared == pred ) return true; 1.479 + 1.480 + // Check previous character and recurse if needed 1.481 + char *prev = shared - 1; 1.482 + char c = *prev; 1.483 + switch( c ) { 1.484 + case ' ': 1.485 + return dfa_shared_preds::valid_loc(pred, prev); 1.486 + case '!': 1.487 + case '(': 1.488 + case '<': 1.489 + case '=': 1.490 + return true; 1.491 + case '|': 1.492 + if( prev != pred && *(prev-1) == '|' ) return true; 1.493 + case '&': 1.494 + if( prev != pred && *(prev-1) == '&' ) return true; 1.495 + default: 1.496 + return false; 1.497 + } 1.498 + 1.499 + return false; 1.500 + } 1.501 + 1.502 +public: 1.503 + 1.504 + static bool found(int index){ check_index(index); return _found[index]; } 1.505 + static void set_found(int index, bool val) { check_index(index); _found[index] = val; } 1.506 + static void reset_found() { 1.507 + for( int i = 0; i < count; ++i ) { _found[i] = false; } 1.508 + }; 1.509 + 1.510 + static const char* type(int index) { check_index(index); return _type[index]; } 1.511 + static const char* var (int index) { check_index(index); return _var [index]; } 1.512 + static const char* pred(int index) { check_index(index); return _pred[index]; } 1.513 + 1.514 + // Check each predicate in the MatchList for common sub-expressions 1.515 + static void cse_matchlist(MatchList *matchList) { 1.516 + for( MatchList *mList = matchList; mList != NULL; mList = mList->get_next() ) { 1.517 + Predicate* predicate = mList->get_pred_obj(); 1.518 + char* pred = mList->get_pred(); 1.519 + if( pred != NULL ) { 1.520 + for(int index = 0; index < count; ++index ) { 1.521 + const char *shared_pred = dfa_shared_preds::pred(index); 1.522 + const char *shared_pred_var = dfa_shared_preds::var(index); 1.523 + bool result = dfa_shared_preds::cse_predicate(predicate, shared_pred, shared_pred_var); 1.524 + if( result ) dfa_shared_preds::set_found(index, true); 1.525 + } 1.526 + } 1.527 + } 1.528 + } 1.529 + 1.530 + // If the Predicate contains a common sub-expression, replace the Predicate's 1.531 + // string with one that uses the variable name. 1.532 + static bool cse_predicate(Predicate* predicate, const char *shared_pred, const char *shared_pred_var) { 1.533 + bool result = false; 1.534 + char *pred = predicate->_pred; 1.535 + if( pred != NULL ) { 1.536 + char *new_pred = pred; 1.537 + for( char *shared_pred_loc = strstr(new_pred, shared_pred); 1.538 + shared_pred_loc != NULL && dfa_shared_preds::valid_loc(new_pred,shared_pred_loc); 1.539 + shared_pred_loc = strstr(new_pred, shared_pred) ) { 1.540 + // Do not modify the original predicate string, it is shared 1.541 + if( new_pred == pred ) { 1.542 + new_pred = strdup(pred); 1.543 + shared_pred_loc = strstr(new_pred, shared_pred); 1.544 + } 1.545 + // Replace shared_pred with variable name 1.546 + strncpy(shared_pred_loc, shared_pred_var, strlen(shared_pred_var)); 1.547 + } 1.548 + // Install new predicate 1.549 + if( new_pred != pred ) { 1.550 + predicate->_pred = new_pred; 1.551 + result = true; 1.552 + } 1.553 + } 1.554 + return result; 1.555 + } 1.556 + 1.557 + // Output the hoisted common sub-expression if we found it in predicates 1.558 + static void generate_cse(FILE *fp) { 1.559 + for(int j = 0; j < count; ++j ) { 1.560 + if( dfa_shared_preds::found(j) ) { 1.561 + const char *shared_pred_type = dfa_shared_preds::type(j); 1.562 + const char *shared_pred_var = dfa_shared_preds::var(j); 1.563 + const char *shared_pred = dfa_shared_preds::pred(j); 1.564 + fprintf(fp, " %s %s = %s;\n", shared_pred_type, shared_pred_var, shared_pred); 1.565 + } 1.566 + } 1.567 + } 1.568 +}; 1.569 +// shared predicates, _var and _pred entry should be the same length 1.570 +bool dfa_shared_preds::_found[dfa_shared_preds::count] = { false, false }; 1.571 +const char* dfa_shared_preds::_type[dfa_shared_preds::count] = { "int", "bool" }; 1.572 +const char* dfa_shared_preds::_var [dfa_shared_preds::count] = { "_n_get_int__", "Compile__current____select_24_bit_instr__" }; 1.573 +const char* dfa_shared_preds::_pred[dfa_shared_preds::count] = { "n->get_int()", "Compile::current()->select_24_bit_instr()" }; 1.574 + 1.575 + 1.576 +void ArchDesc::gen_dfa_state_body(FILE* fp, Dict &minimize, ProductionState &status, Dict &operands_chained_from, int i) { 1.577 + // Start the body of each Op_XXX sub-dfa with a clean state. 1.578 + status.initialize(); 1.579 + 1.580 + // Walk the list, compacting it 1.581 + MatchList* mList = _mlistab[i]; 1.582 + do { 1.583 + // Hash each entry using inputs as key and pointer as data. 1.584 + // If there is already an entry, keep the one with lower cost, and 1.585 + // remove the other one from the list. 1.586 + prune_matchlist(minimize, *mList); 1.587 + // Iterate 1.588 + mList = mList->get_next(); 1.589 + } while(mList != NULL); 1.590 + 1.591 + // Hoist previously specified common sub-expressions out of predicates 1.592 + dfa_shared_preds::reset_found(); 1.593 + dfa_shared_preds::cse_matchlist(_mlistab[i]); 1.594 + dfa_shared_preds::generate_cse(fp); 1.595 + 1.596 + mList = _mlistab[i]; 1.597 + 1.598 + // Walk the list again, generating code 1.599 + do { 1.600 + // Each match can generate its own chains 1.601 + operands_chained_from.Clear(); 1.602 + gen_match(fp, *mList, status, operands_chained_from); 1.603 + mList = mList->get_next(); 1.604 + } while(mList != NULL); 1.605 + // Fill in any chain rules which add instructions 1.606 + // These can generate their own chains as well. 1.607 + operands_chained_from.Clear(); // 1.608 + if( debug_output1 ) { fprintf(fp, "// top level chain rules for: %s \n", (char *)NodeClassNames[i]); } // %%%%% Explanation 1.609 + const Expr *zeroCost = new Expr("0"); 1.610 + chain_rule(fp, " ", (char *)NodeClassNames[i], zeroCost, "Invalid", 1.611 + operands_chained_from, status); 1.612 +} 1.613 + 1.614 + 1.615 + 1.616 +//------------------------------Expr------------------------------------------ 1.617 +Expr *Expr::_unknown_expr = NULL; 1.618 +char Expr::string_buffer[STRING_BUFFER_LENGTH]; 1.619 +char Expr::external_buffer[STRING_BUFFER_LENGTH]; 1.620 +bool Expr::_init_buffers = Expr::init_buffers(); 1.621 + 1.622 +Expr::Expr() { 1.623 + _external_name = NULL; 1.624 + _expr = "Invalid_Expr"; 1.625 + _min_value = Expr::Max; 1.626 + _max_value = Expr::Zero; 1.627 +} 1.628 +Expr::Expr(const char *cost) { 1.629 + _external_name = NULL; 1.630 + 1.631 + int intval = 0; 1.632 + if( cost == NULL ) { 1.633 + _expr = "0"; 1.634 + _min_value = Expr::Zero; 1.635 + _max_value = Expr::Zero; 1.636 + } 1.637 + else if( ADLParser::is_int_token(cost, intval) ) { 1.638 + _expr = cost; 1.639 + _min_value = intval; 1.640 + _max_value = intval; 1.641 + } 1.642 + else { 1.643 + assert( strcmp(cost,"0") != 0, "Recognize string zero as an int"); 1.644 + _expr = cost; 1.645 + _min_value = Expr::Zero; 1.646 + _max_value = Expr::Max; 1.647 + } 1.648 +} 1.649 + 1.650 +Expr::Expr(const char *name, const char *expression, int min_value, int max_value) { 1.651 + _external_name = name; 1.652 + _expr = expression ? expression : name; 1.653 + _min_value = min_value; 1.654 + _max_value = max_value; 1.655 + assert(_min_value >= 0 && _min_value <= Expr::Max, "value out of range"); 1.656 + assert(_max_value >= 0 && _max_value <= Expr::Max, "value out of range"); 1.657 +} 1.658 + 1.659 +Expr *Expr::clone() const { 1.660 + Expr *cost = new Expr(); 1.661 + cost->_external_name = _external_name; 1.662 + cost->_expr = _expr; 1.663 + cost->_min_value = _min_value; 1.664 + cost->_max_value = _max_value; 1.665 + 1.666 + return cost; 1.667 +} 1.668 + 1.669 +void Expr::add(const Expr *c) { 1.670 + // Do not update fields until all computation is complete 1.671 + const char *external = compute_external(this, c); 1.672 + const char *expr = compute_expr(this, c); 1.673 + int min_value = compute_min (this, c); 1.674 + int max_value = compute_max (this, c); 1.675 + 1.676 + _external_name = external; 1.677 + _expr = expr; 1.678 + _min_value = min_value; 1.679 + _max_value = max_value; 1.680 +} 1.681 + 1.682 +void Expr::add(const char *c) { 1.683 + Expr *cost = new Expr(c); 1.684 + add(cost); 1.685 +} 1.686 + 1.687 +void Expr::add(const char *c, ArchDesc &AD) { 1.688 + const Expr *e = AD.globalDefs()[c]; 1.689 + if( e != NULL ) { 1.690 + // use the value of 'c' defined in <arch>.ad 1.691 + add(e); 1.692 + } else { 1.693 + Expr *cost = new Expr(c); 1.694 + add(cost); 1.695 + } 1.696 +} 1.697 + 1.698 +const char *Expr::compute_external(const Expr *c1, const Expr *c2) { 1.699 + const char * result = NULL; 1.700 + 1.701 + // Preserve use of external name which has a zero value 1.702 + if( c1->_external_name != NULL ) { 1.703 + sprintf( string_buffer, "%s", c1->as_string()); 1.704 + if( !c2->is_zero() ) { 1.705 + strcat( string_buffer, "+"); 1.706 + strcat( string_buffer, c2->as_string()); 1.707 + } 1.708 + result = strdup(string_buffer); 1.709 + } 1.710 + else if( c2->_external_name != NULL ) { 1.711 + if( !c1->is_zero() ) { 1.712 + sprintf( string_buffer, "%s", c1->as_string()); 1.713 + strcat( string_buffer, " + "); 1.714 + } else { 1.715 + string_buffer[0] = '\0'; 1.716 + } 1.717 + strcat( string_buffer, c2->_external_name ); 1.718 + result = strdup(string_buffer); 1.719 + } 1.720 + return result; 1.721 +} 1.722 + 1.723 +const char *Expr::compute_expr(const Expr *c1, const Expr *c2) { 1.724 + if( !c1->is_zero() ) { 1.725 + sprintf( string_buffer, "%s", c1->_expr); 1.726 + if( !c2->is_zero() ) { 1.727 + strcat( string_buffer, "+"); 1.728 + strcat( string_buffer, c2->_expr); 1.729 + } 1.730 + } 1.731 + else if( !c2->is_zero() ) { 1.732 + sprintf( string_buffer, "%s", c2->_expr); 1.733 + } 1.734 + else { 1.735 + sprintf( string_buffer, "0"); 1.736 + } 1.737 + char *cost = strdup(string_buffer); 1.738 + 1.739 + return cost; 1.740 +} 1.741 + 1.742 +int Expr::compute_min(const Expr *c1, const Expr *c2) { 1.743 + int result = c1->_min_value + c2->_min_value; 1.744 + assert( result >= 0, "Invalid cost computation"); 1.745 + 1.746 + return result; 1.747 +} 1.748 + 1.749 +int Expr::compute_max(const Expr *c1, const Expr *c2) { 1.750 + int result = c1->_max_value + c2->_max_value; 1.751 + if( result < 0 ) { // check for overflow 1.752 + result = Expr::Max; 1.753 + } 1.754 + 1.755 + return result; 1.756 +} 1.757 + 1.758 +void Expr::print() const { 1.759 + if( _external_name != NULL ) { 1.760 + printf(" %s == (%s) === [%d, %d]\n", _external_name, _expr, _min_value, _max_value); 1.761 + } else { 1.762 + printf(" %s === [%d, %d]\n", _expr, _min_value, _max_value); 1.763 + } 1.764 +} 1.765 + 1.766 +void Expr::print_define(FILE *fp) const { 1.767 + assert( _external_name != NULL, "definition does not have a name"); 1.768 + assert( _min_value == _max_value, "Expect user definitions to have constant value"); 1.769 + fprintf(fp, "#define %s (%s) \n", _external_name, _expr); 1.770 + fprintf(fp, "// value == %d \n", _min_value); 1.771 +} 1.772 + 1.773 +void Expr::print_assert(FILE *fp) const { 1.774 + assert( _external_name != NULL, "definition does not have a name"); 1.775 + assert( _min_value == _max_value, "Expect user definitions to have constant value"); 1.776 + fprintf(fp, " assert( %s == %d, \"Expect (%s) to equal %d\");\n", _external_name, _min_value, _expr, _min_value); 1.777 +} 1.778 + 1.779 +Expr *Expr::get_unknown() { 1.780 + if( Expr::_unknown_expr == NULL ) { 1.781 + Expr::_unknown_expr = new Expr(); 1.782 + } 1.783 + 1.784 + return Expr::_unknown_expr; 1.785 +} 1.786 + 1.787 +bool Expr::init_buffers() { 1.788 + // Fill buffers with 0 1.789 + for( int i = 0; i < STRING_BUFFER_LENGTH; ++i ) { 1.790 + external_buffer[i] = '\0'; 1.791 + string_buffer[i] = '\0'; 1.792 + } 1.793 + 1.794 + return true; 1.795 +} 1.796 + 1.797 +bool Expr::check_buffers() { 1.798 + // returns 'true' if buffer use may have overflowed 1.799 + bool ok = true; 1.800 + for( int i = STRING_BUFFER_LENGTH - 100; i < STRING_BUFFER_LENGTH; ++i) { 1.801 + if( external_buffer[i] != '\0' || string_buffer[i] != '\0' ) { 1.802 + ok = false; 1.803 + assert( false, "Expr:: Buffer overflow"); 1.804 + } 1.805 + } 1.806 + 1.807 + return ok; 1.808 +} 1.809 + 1.810 + 1.811 +//------------------------------ExprDict--------------------------------------- 1.812 +// Constructor 1.813 +ExprDict::ExprDict( CmpKey cmp, Hash hash, Arena *arena ) 1.814 + : _expr(cmp, hash, arena), _defines() { 1.815 +} 1.816 +ExprDict::~ExprDict() { 1.817 +} 1.818 + 1.819 +// Return # of name-Expr pairs in dict 1.820 +int ExprDict::Size(void) const { 1.821 + return _expr.Size(); 1.822 +} 1.823 + 1.824 +// define inserts the given key-value pair into the dictionary, 1.825 +// and records the name in order for later output, ... 1.826 +const Expr *ExprDict::define(const char *name, Expr *expr) { 1.827 + const Expr *old_expr = (*this)[name]; 1.828 + assert(old_expr == NULL, "Implementation does not support redefinition"); 1.829 + 1.830 + _expr.Insert(name, expr); 1.831 + _defines.addName(name); 1.832 + 1.833 + return old_expr; 1.834 +} 1.835 + 1.836 +// Insert inserts the given key-value pair into the dictionary. The prior 1.837 +// value of the key is returned; NULL if the key was not previously defined. 1.838 +const Expr *ExprDict::Insert(const char *name, Expr *expr) { 1.839 + return (Expr*)_expr.Insert((void*)name, (void*)expr); 1.840 +} 1.841 + 1.842 +// Finds the value of a given key; or NULL if not found. 1.843 +// The dictionary is NOT changed. 1.844 +const Expr *ExprDict::operator [](const char *name) const { 1.845 + return (Expr*)_expr[name]; 1.846 +} 1.847 + 1.848 +void ExprDict::print_defines(FILE *fp) { 1.849 + fprintf(fp, "\n"); 1.850 + const char *name = NULL; 1.851 + for( _defines.reset(); (name = _defines.iter()) != NULL; ) { 1.852 + const Expr *expr = (const Expr*)_expr[name]; 1.853 + assert( expr != NULL, "name in ExprDict without matching Expr in dictionary"); 1.854 + expr->print_define(fp); 1.855 + } 1.856 +} 1.857 +void ExprDict::print_asserts(FILE *fp) { 1.858 + fprintf(fp, "\n"); 1.859 + fprintf(fp, " // Following assertions generated from definition section\n"); 1.860 + const char *name = NULL; 1.861 + for( _defines.reset(); (name = _defines.iter()) != NULL; ) { 1.862 + const Expr *expr = (const Expr*)_expr[name]; 1.863 + assert( expr != NULL, "name in ExprDict without matching Expr in dictionary"); 1.864 + expr->print_assert(fp); 1.865 + } 1.866 +} 1.867 + 1.868 +// Print out the dictionary contents as key-value pairs 1.869 +static void dumpekey(const void* key) { fprintf(stdout, "%s", key); } 1.870 +static void dumpexpr(const void* expr) { fflush(stdout); ((Expr*)expr)->print(); } 1.871 + 1.872 +void ExprDict::dump() { 1.873 + _expr.print(dumpekey, dumpexpr); 1.874 +} 1.875 + 1.876 + 1.877 +//------------------------------ExprDict::private------------------------------ 1.878 +// Disable public use of constructor, copy-ctor, operator =, operator == 1.879 +ExprDict::ExprDict( ) : _expr(cmpkey,hashkey), _defines() { 1.880 + assert( false, "NotImplemented"); 1.881 +} 1.882 +ExprDict::ExprDict( const ExprDict & ) : _expr(cmpkey,hashkey), _defines() { 1.883 + assert( false, "NotImplemented"); 1.884 +} 1.885 +ExprDict &ExprDict::operator =( const ExprDict &rhs) { 1.886 + assert( false, "NotImplemented"); 1.887 + _expr = rhs._expr; 1.888 + return *this; 1.889 +} 1.890 +// == compares two dictionaries; they must have the same keys (their keys 1.891 +// must match using CmpKey) and they must have the same values (pointer 1.892 +// comparison). If so 1 is returned, if not 0 is returned. 1.893 +bool ExprDict::operator ==(const ExprDict &d) const { 1.894 + assert( false, "NotImplemented"); 1.895 + return false; 1.896 +} 1.897 + 1.898 + 1.899 +//------------------------------Production------------------------------------- 1.900 +Production::Production(const char *result, const char *constraint, const char *valid) { 1.901 + initialize(); 1.902 + _result = result; 1.903 + _constraint = constraint; 1.904 + _valid = valid; 1.905 +} 1.906 + 1.907 +void Production::initialize() { 1.908 + _result = NULL; 1.909 + _constraint = NULL; 1.910 + _valid = knownInvalid; 1.911 + _cost_lb = Expr::get_unknown(); 1.912 + _cost_ub = Expr::get_unknown(); 1.913 +} 1.914 + 1.915 +void Production::print() { 1.916 + printf("%s", (_result == NULL ? "NULL" : _result ) ); 1.917 + printf("%s", (_constraint == NULL ? "NULL" : _constraint ) ); 1.918 + printf("%s", (_valid == NULL ? "NULL" : _valid ) ); 1.919 + _cost_lb->print(); 1.920 + _cost_ub->print(); 1.921 +} 1.922 + 1.923 + 1.924 +//------------------------------ProductionState-------------------------------- 1.925 +void ProductionState::initialize() { 1.926 + _constraint = noConstraint; 1.927 + 1.928 + // reset each Production currently in the dictionary 1.929 + DictI iter( &_production ); 1.930 + const void *x, *y = NULL; 1.931 + for( ; iter.test(); ++iter) { 1.932 + x = iter._key; 1.933 + y = iter._value; 1.934 + Production *p = (Production*)y; 1.935 + if( p != NULL ) { 1.936 + p->initialize(); 1.937 + } 1.938 + } 1.939 +} 1.940 + 1.941 +Production *ProductionState::getProduction(const char *result) { 1.942 + Production *p = (Production *)_production[result]; 1.943 + if( p == NULL ) { 1.944 + p = new Production(result, _constraint, knownInvalid); 1.945 + _production.Insert(result, p); 1.946 + } 1.947 + 1.948 + return p; 1.949 +} 1.950 + 1.951 +void ProductionState::set_constraint(const char *constraint) { 1.952 + _constraint = constraint; 1.953 +} 1.954 + 1.955 +const char *ProductionState::valid(const char *result) { 1.956 + return getProduction(result)->valid(); 1.957 +} 1.958 + 1.959 +void ProductionState::set_valid(const char *result) { 1.960 + Production *p = getProduction(result); 1.961 + 1.962 + // Update valid as allowed by current constraints 1.963 + if( _constraint == noConstraint ) { 1.964 + p->_valid = knownValid; 1.965 + } else { 1.966 + if( p->_valid != knownValid ) { 1.967 + p->_valid = unknownValid; 1.968 + } 1.969 + } 1.970 +} 1.971 + 1.972 +Expr *ProductionState::cost_lb(const char *result) { 1.973 + return getProduction(result)->cost_lb(); 1.974 +} 1.975 + 1.976 +Expr *ProductionState::cost_ub(const char *result) { 1.977 + return getProduction(result)->cost_ub(); 1.978 +} 1.979 + 1.980 +void ProductionState::set_cost_bounds(const char *result, const Expr *cost, bool has_state_check, bool has_cost_check) { 1.981 + Production *p = getProduction(result); 1.982 + 1.983 + if( p->_valid == knownInvalid ) { 1.984 + // Our cost bounds are not unknown, just not defined. 1.985 + p->_cost_lb = cost->clone(); 1.986 + p->_cost_ub = cost->clone(); 1.987 + } else if (has_state_check || _constraint != noConstraint) { 1.988 + // The production is protected by a condition, so 1.989 + // the cost bounds may expand. 1.990 + // _cost_lb = min(cost, _cost_lb) 1.991 + if( cost->less_than_or_equal(p->_cost_lb) ) { 1.992 + p->_cost_lb = cost->clone(); 1.993 + } 1.994 + // _cost_ub = max(cost, _cost_ub) 1.995 + if( p->_cost_ub->less_than_or_equal(cost) ) { 1.996 + p->_cost_ub = cost->clone(); 1.997 + } 1.998 + } else if (has_cost_check) { 1.999 + // The production has no condition check, but does 1.1000 + // have a cost check that could reduce the upper 1.1001 + // and/or lower bound. 1.1002 + // _cost_lb = min(cost, _cost_lb) 1.1003 + if( cost->less_than_or_equal(p->_cost_lb) ) { 1.1004 + p->_cost_lb = cost->clone(); 1.1005 + } 1.1006 + // _cost_ub = min(cost, _cost_ub) 1.1007 + if( cost->less_than_or_equal(p->_cost_ub) ) { 1.1008 + p->_cost_ub = cost->clone(); 1.1009 + } 1.1010 + } else { 1.1011 + // The costs are unconditionally set. 1.1012 + p->_cost_lb = cost->clone(); 1.1013 + p->_cost_ub = cost->clone(); 1.1014 + } 1.1015 + 1.1016 +} 1.1017 + 1.1018 +// Print out the dictionary contents as key-value pairs 1.1019 +static void print_key (const void* key) { fprintf(stdout, "%s", key); } 1.1020 +static void print_production(const void* production) { fflush(stdout); ((Production*)production)->print(); } 1.1021 + 1.1022 +void ProductionState::print() { 1.1023 + _production.print(print_key, print_production); 1.1024 +}