1 /* 2 * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25 // DFA.CPP - Method definitions for outputting the matcher DFA from ADLC 26 #include "adlc.hpp" 27 28 //---------------------------Switches for debugging output--------------------- 29 static bool debug_output = false; 30 static bool debug_output1 = false; // top level chain rules 31 32 //---------------------------Access to internals of class State---------------- 33 static const char *sLeft = "_kids[0]"; 34 static const char *sRight = "_kids[1]"; 35 36 //---------------------------DFA productions----------------------------------- 37 static const char *dfa_production = "DFA_PRODUCTION"; 38 static const char *dfa_production_set_valid = "DFA_PRODUCTION__SET_VALID"; 39 40 //---------------------------Production State---------------------------------- 41 static const char *knownInvalid = "knownInvalid"; // The result does NOT have a rule defined 42 static const char *knownValid = "knownValid"; // The result must be produced by a rule 43 static const char *unknownValid = "unknownValid"; // Unknown (probably due to a child or predicate constraint) 44 45 static const char *noConstraint = "noConstraint"; // No constraints seen so far 46 static const char *hasConstraint = "hasConstraint"; // Within the first constraint 47 48 49 //------------------------------Production------------------------------------ 50 // Track the status of productions for a particular result 51 class Production { 52 public: 53 const char *_result; 54 const char *_constraint; 55 const char *_valid; 56 Expr *_cost_lb; // Cost lower bound for this production 57 Expr *_cost_ub; // Cost upper bound for this production 58 59 public: 60 Production(const char *result, const char *constraint, const char *valid); 61 ~Production() {}; 62 63 void initialize(); // reset to be an empty container 64 65 const char *valid() const { return _valid; } 66 Expr *cost_lb() const { return (Expr *)_cost_lb; } 67 Expr *cost_ub() const { return (Expr *)_cost_ub; } 68 69 void print(); 70 }; 71 72 73 //------------------------------ProductionState-------------------------------- 74 // Track the status of all production rule results 75 // Reset for each root opcode (e.g., Op_RegI, Op_AddI, ...) 76 class ProductionState { 77 private: 78 Dict _production; // map result of production, char*, to information or NULL 79 const char *_constraint; 80 81 public: 82 // cmpstr does string comparisions. hashstr computes a key. 83 ProductionState(Arena *arena) : _production(cmpstr, hashstr, arena) { initialize(); }; 84 ~ProductionState() { }; 85 86 void initialize(); // reset local and dictionary state 87 88 const char *constraint(); 89 void set_constraint(const char *constraint); // currently working inside of constraints 90 91 const char *valid(const char *result); // unknownValid, or status for this production 92 void set_valid(const char *result); // if not constrained, set status to knownValid 93 94 Expr *cost_lb(const char *result); 95 Expr *cost_ub(const char *result); 96 void set_cost_bounds(const char *result, const Expr *cost, bool has_state_check, bool has_cost_check); 97 98 // Return the Production associated with the result, 99 // or create a new Production and insert it into the dictionary. 100 Production *getProduction(const char *result); 101 102 void print(); 103 104 private: 105 // Disable public use of constructor, copy-ctor, ... 106 ProductionState( ) : _production(cmpstr, hashstr, Form::arena) { assert( false, "NotImplemented"); }; 107 ProductionState( const ProductionState & ) : _production(cmpstr, hashstr, Form::arena) { assert( false, "NotImplemented"); }; // Deep-copy 108 }; 109 110 111 //---------------------------Helper Functions---------------------------------- 112 // cost_check template: 113 // 1) if (STATE__NOT_YET_VALID(EBXREGI) || _cost[EBXREGI] > c) { 114 // 2) DFA_PRODUCTION__SET_VALID(EBXREGI, cmovI_memu_rule, c) 115 // 3) } 116 // 117 static void cost_check(FILE *fp, const char *spaces, 118 const char *arrayIdx, const Expr *cost, const char *rule, ProductionState &status) { 119 bool state_check = false; // true if this production needs to check validity 120 bool cost_check = false; // true if this production needs to check cost 121 bool cost_is_above_upper_bound = false; // true if this production is unnecessary due to high cost 122 bool cost_is_below_lower_bound = false; // true if this production replaces a higher cost production 123 124 // Get information about this production 125 const Expr *previous_ub = status.cost_ub(arrayIdx); 126 if( !previous_ub->is_unknown() ) { 127 if( previous_ub->less_than_or_equal(cost) ) { 128 cost_is_above_upper_bound = true; 129 if( debug_output ) { fprintf(fp, "// Previous rule with lower cost than: %s === %s_rule costs %s\n", arrayIdx, rule, cost->as_string()); } 130 } 131 } 132 133 const Expr *previous_lb = status.cost_lb(arrayIdx); 134 if( !previous_lb->is_unknown() ) { 135 if( cost->less_than_or_equal(previous_lb) ) { 136 cost_is_below_lower_bound = true; 137 if( debug_output ) { fprintf(fp, "// Previous rule with higher cost\n"); } 138 } 139 } 140 141 // line 1) 142 // Check for validity and compare to other match costs 143 const char *validity_check = status.valid(arrayIdx); 144 if( validity_check == unknownValid ) { 145 fprintf(fp, "%sif (STATE__NOT_YET_VALID(%s) || _cost[%s] > %s) {\n", spaces, arrayIdx, arrayIdx, cost->as_string()); 146 state_check = true; 147 cost_check = true; 148 } 149 else if( validity_check == knownInvalid ) { 150 if( debug_output ) { fprintf(fp, "%s// %s KNOWN_INVALID \n", spaces, arrayIdx); } 151 } 152 else if( validity_check == knownValid ) { 153 if( cost_is_above_upper_bound ) { 154 // production cost is known to be too high. 155 return; 156 } else if( cost_is_below_lower_bound ) { 157 // production will unconditionally overwrite a previous production that had higher cost 158 } else { 159 fprintf(fp, "%sif ( /* %s KNOWN_VALID || */ _cost[%s] > %s) {\n", spaces, arrayIdx, arrayIdx, cost->as_string()); 160 cost_check = true; 161 } 162 } 163 164 // line 2) 165 // no need to set State vector if our state is knownValid 166 const char *production = (validity_check == knownValid) ? dfa_production : dfa_production_set_valid; 167 fprintf(fp, "%s %s(%s, %s_rule, %s)", spaces, production, arrayIdx, rule, cost->as_string() ); 168 if( validity_check == knownValid ) { 169 if( cost_is_below_lower_bound ) { fprintf(fp, "\t // overwrites higher cost rule"); } 170 } 171 fprintf(fp, "\n"); 172 173 // line 3) 174 if( cost_check || state_check ) { 175 fprintf(fp, "%s}\n", spaces); 176 } 177 178 status.set_cost_bounds(arrayIdx, cost, state_check, cost_check); 179 180 // Update ProductionState 181 if( validity_check != knownValid ) { 182 // set State vector if not previously known 183 status.set_valid(arrayIdx); 184 } 185 } 186 187 188 //---------------------------child_test---------------------------------------- 189 // Example: 190 // STATE__VALID_CHILD(_kids[0], FOO) && STATE__VALID_CHILD(_kids[1], BAR) 191 // Macro equivalent to: _kids[0]->valid(FOO) && _kids[1]->valid(BAR) 192 // 193 static void child_test(FILE *fp, MatchList &mList) { 194 if (mList._lchild) { // If left child, check it 195 const char* lchild_to_upper = ArchDesc::getMachOperEnum(mList._lchild); 196 fprintf(fp, "STATE__VALID_CHILD(_kids[0], %s)", lchild_to_upper); 197 delete[] lchild_to_upper; 198 } 199 if (mList._lchild && mList._rchild) { // If both, add the "&&" 200 fprintf(fp, " && "); 201 } 202 if (mList._rchild) { // If right child, check it 203 const char* rchild_to_upper = ArchDesc::getMachOperEnum(mList._rchild); 204 fprintf(fp, "STATE__VALID_CHILD(_kids[1], %s)", rchild_to_upper); 205 delete[] rchild_to_upper; 206 } 207 } 208 209 //---------------------------calc_cost----------------------------------------- 210 // Example: 211 // unsigned int c = _kids[0]->_cost[FOO] + _kids[1]->_cost[BAR] + 5; 212 // 213 Expr *ArchDesc::calc_cost(FILE *fp, const char *spaces, MatchList &mList, ProductionState &status) { 214 fprintf(fp, "%sunsigned int c = ", spaces); 215 Expr *c = new Expr("0"); 216 if (mList._lchild) { // If left child, add it in 217 const char* lchild_to_upper = ArchDesc::getMachOperEnum(mList._lchild); 218 sprintf(Expr::buffer(), "_kids[0]->_cost[%s]", lchild_to_upper); 219 c->add(Expr::buffer()); 220 delete[] lchild_to_upper; 221 } 222 if (mList._rchild) { // If right child, add it in 223 const char* rchild_to_upper = ArchDesc::getMachOperEnum(mList._rchild); 224 sprintf(Expr::buffer(), "_kids[1]->_cost[%s]", rchild_to_upper); 225 c->add(Expr::buffer()); 226 delete[] rchild_to_upper; 227 } 228 // Add in cost of this rule 229 const char *mList_cost = mList.get_cost(); 230 c->add(mList_cost, *this); 231 232 fprintf(fp, "%s;\n", c->as_string()); 233 c->set_external_name("c"); 234 return c; 235 } 236 237 238 //---------------------------gen_match----------------------------------------- 239 void ArchDesc::gen_match(FILE *fp, MatchList &mList, ProductionState &status, Dict &operands_chained_from) { 240 const char *spaces4 = " "; 241 const char *spaces6 = " "; 242 243 fprintf(fp, "%s", spaces4); 244 // Only generate child tests if this is not a leaf node 245 bool has_child_constraints = mList._lchild || mList._rchild; 246 const char *predicate_test = mList.get_pred(); 247 if (has_child_constraints || predicate_test) { 248 // Open the child-and-predicate-test braces 249 fprintf(fp, "if( "); 250 status.set_constraint(hasConstraint); 251 child_test(fp, mList); 252 // Only generate predicate test if one exists for this match 253 if (predicate_test) { 254 if (has_child_constraints) { 255 fprintf(fp," &&\n"); 256 } 257 fprintf(fp, "%s %s", spaces6, predicate_test); 258 } 259 // End of outer tests 260 fprintf(fp," ) "); 261 } else { 262 // No child or predicate test needed 263 status.set_constraint(noConstraint); 264 } 265 266 // End of outer tests 267 fprintf(fp,"{\n"); 268 269 // Calculate cost of this match 270 const Expr *cost = calc_cost(fp, spaces6, mList, status); 271 // Check against other match costs, and update cost & rule vectors 272 cost_check(fp, spaces6, ArchDesc::getMachOperEnum(mList._resultStr), cost, mList._opcode, status); 273 274 // If this is a member of an operand class, update the class cost & rule 275 expand_opclass( fp, spaces6, cost, mList._resultStr, status); 276 277 // Check if this rule should be used to generate the chains as well. 278 const char *rule = /* set rule to "Invalid" for internal operands */ 279 strcmp(mList._opcode,mList._resultStr) ? mList._opcode : "Invalid"; 280 281 // If this rule produces an operand which has associated chain rules, 282 // update the operands with the chain rule + this rule cost & this rule. 283 chain_rule(fp, spaces6, mList._resultStr, cost, rule, operands_chained_from, status); 284 285 // Close the child-and-predicate-test braces 286 fprintf(fp, " }\n"); 287 288 } 289 290 291 //---------------------------expand_opclass------------------------------------ 292 // Chain from one result_type to all other members of its operand class 293 void ArchDesc::expand_opclass(FILE *fp, const char *indent, const Expr *cost, 294 const char *result_type, ProductionState &status) { 295 const Form *form = _globalNames[result_type]; 296 OperandForm *op = form ? form->is_operand() : NULL; 297 if( op && op->_classes.count() > 0 ) { 298 if( debug_output ) { fprintf(fp, "// expand operand classes for operand: %s \n", (char *)op->_ident ); } // %%%%% Explanation 299 // Iterate through all operand classes which include this operand 300 op->_classes.reset(); 301 const char *oclass; 302 // Expr *cCost = new Expr(cost); 303 while( (oclass = op->_classes.iter()) != NULL ) 304 // Check against other match costs, and update cost & rule vectors 305 cost_check(fp, indent, ArchDesc::getMachOperEnum(oclass), cost, result_type, status); 306 } 307 } 308 309 //---------------------------chain_rule---------------------------------------- 310 // Starting at 'operand', check if we know how to automatically generate other results 311 void ArchDesc::chain_rule(FILE *fp, const char *indent, const char *operand, 312 const Expr *icost, const char *irule, Dict &operands_chained_from, ProductionState &status) { 313 314 // Check if we have already generated chains from this starting point 315 if( operands_chained_from[operand] != NULL ) { 316 return; 317 } else { 318 operands_chained_from.Insert( operand, operand); 319 } 320 if( debug_output ) { fprintf(fp, "// chain rules starting from: %s and %s \n", (char *)operand, (char *)irule); } // %%%%% Explanation 321 322 ChainList *lst = (ChainList *)_chainRules[operand]; 323 if (lst) { 324 // printf("\nChain from <%s> at cost #%s\n",operand, icost ? icost : "_"); 325 const char *result, *cost, *rule; 326 for(lst->reset(); (lst->iter(result,cost,rule)) == true; ) { 327 // Do not generate operands that are already available 328 if( operands_chained_from[result] != NULL ) { 329 continue; 330 } else { 331 // Compute the cost for previous match + chain_rule_cost 332 // total_cost = icost + cost; 333 Expr *total_cost = icost->clone(); // icost + cost 334 total_cost->add(cost, *this); 335 336 // Check for transitive chain rules 337 Form *form = (Form *)_globalNames[rule]; 338 if ( ! form->is_instruction()) { 339 // printf(" result=%s cost=%s rule=%s\n", result, total_cost, rule); 340 // Check against other match costs, and update cost & rule vectors 341 const char *reduce_rule = strcmp(irule,"Invalid") ? irule : rule; 342 cost_check(fp, indent, ArchDesc::getMachOperEnum(result), total_cost, reduce_rule, status); 343 chain_rule(fp, indent, result, total_cost, irule, operands_chained_from, status); 344 } else { 345 // printf(" result=%s cost=%s rule=%s\n", result, total_cost, rule); 346 // Check against other match costs, and update cost & rule vectors 347 cost_check(fp, indent, ArchDesc::getMachOperEnum(result), total_cost, rule, status); 348 chain_rule(fp, indent, result, total_cost, rule, operands_chained_from, status); 349 } 350 351 // If this is a member of an operand class, update class cost & rule 352 expand_opclass( fp, indent, total_cost, result, status ); 353 } 354 } 355 } 356 } 357 358 //---------------------------prune_matchlist----------------------------------- 359 // Check for duplicate entries in a matchlist, and prune out the higher cost 360 // entry. 361 void ArchDesc::prune_matchlist(Dict &minimize, MatchList &mlist) { 362 363 } 364 365 //---------------------------buildDFA------------------------------------------ 366 // DFA is a large switch with case statements for each ideal opcode encountered 367 // in any match rule in the ad file. Each case has a series of if's to handle 368 // the match or fail decisions. The matches test the cost function of that 369 // rule, and prune any cases which are higher cost for the same reduction. 370 // In order to generate the DFA we walk the table of ideal opcode/MatchList 371 // pairs generated by the ADLC front end to build the contents of the case 372 // statements (a series of if statements). 373 void ArchDesc::buildDFA(FILE* fp) { 374 int i; 375 // Remember operands that are the starting points for chain rules. 376 // Prevent cycles by checking if we have already generated chain. 377 Dict operands_chained_from(cmpstr, hashstr, Form::arena); 378 379 // Hash inputs to match rules so that final DFA contains only one entry for 380 // each match pattern which is the low cost entry. 381 Dict minimize(cmpstr, hashstr, Form::arena); 382 383 // Track status of dfa for each resulting production 384 // reset for each ideal root. 385 ProductionState status(Form::arena); 386 387 // Output the start of the DFA method into the output file 388 389 fprintf(fp, "\n"); 390 fprintf(fp, "//------------------------- Source -----------------------------------------\n"); 391 // Do not put random source code into the DFA. 392 // If there are constants which need sharing, put them in "source_hpp" forms. 393 // _source.output(fp); 394 fprintf(fp, "\n"); 395 fprintf(fp, "//------------------------- Attributes -------------------------------------\n"); 396 _attributes.output(fp); 397 fprintf(fp, "\n"); 398 fprintf(fp, "//------------------------- Macros -----------------------------------------\n"); 399 // #define DFA_PRODUCTION(result, rule, cost)\ 400 // _cost[ (result) ] = cost; _rule[ (result) ] = rule; 401 fprintf(fp, "#define %s(result, rule, cost)\\\n", dfa_production); 402 fprintf(fp, " _cost[ (result) ] = cost; _rule[ (result) ] = rule;\n"); 403 fprintf(fp, "\n"); 404 405 // #define DFA_PRODUCTION__SET_VALID(result, rule, cost)\ 406 // DFA_PRODUCTION( (result), (rule), (cost) ); STATE__SET_VALID( (result) ); 407 fprintf(fp, "#define %s(result, rule, cost)\\\n", dfa_production_set_valid); 408 fprintf(fp, " %s( (result), (rule), (cost) ); STATE__SET_VALID( (result) );\n", dfa_production); 409 fprintf(fp, "\n"); 410 411 fprintf(fp, "//------------------------- DFA --------------------------------------------\n"); 412 413 fprintf(fp, 414 "// DFA is a large switch with case statements for each ideal opcode encountered\n" 415 "// in any match rule in the ad file. Each case has a series of if's to handle\n" 416 "// the match or fail decisions. The matches test the cost function of that\n" 417 "// rule, and prune any cases which are higher cost for the same reduction.\n" 418 "// In order to generate the DFA we walk the table of ideal opcode/MatchList\n" 419 "// pairs generated by the ADLC front end to build the contents of the case\n" 420 "// statements (a series of if statements).\n" 421 ); 422 fprintf(fp, "\n"); 423 fprintf(fp, "\n"); 424 if (_dfa_small) { 425 // Now build the individual routines just like the switch entries in large version 426 // Iterate over the table of MatchLists, start at first valid opcode of 1 427 for (i = 1; i < _last_opcode; i++) { 428 if (_mlistab[i] == NULL) continue; 429 // Generate the routine header statement for this opcode 430 fprintf(fp, "void State::_sub_Op_%s(const Node *n){\n", NodeClassNames[i]); 431 // Generate body. Shared for both inline and out-of-line version 432 gen_dfa_state_body(fp, minimize, status, operands_chained_from, i); 433 // End of routine 434 fprintf(fp, "}\n"); 435 } 436 } 437 fprintf(fp, "bool State::DFA"); 438 fprintf(fp, "(int opcode, const Node *n) {\n"); 439 fprintf(fp, " switch(opcode) {\n"); 440 441 // Iterate over the table of MatchLists, start at first valid opcode of 1 442 for (i = 1; i < _last_opcode; i++) { 443 if (_mlistab[i] == NULL) continue; 444 // Generate the case statement for this opcode 445 if (_dfa_small) { 446 fprintf(fp, " case Op_%s: { _sub_Op_%s(n);\n", NodeClassNames[i], NodeClassNames[i]); 447 } else { 448 fprintf(fp, " case Op_%s: {\n", NodeClassNames[i]); 449 // Walk the list, compacting it 450 gen_dfa_state_body(fp, minimize, status, operands_chained_from, i); 451 } 452 // Print the "break" 453 fprintf(fp, " break;\n"); 454 fprintf(fp, " }\n"); 455 } 456 457 // Generate the default case for switch(opcode) 458 fprintf(fp, " \n"); 459 fprintf(fp, " default:\n"); 460 fprintf(fp, " tty->print(\"Default case invoked for: \\n\");\n"); 461 fprintf(fp, " tty->print(\" opcode = %cd, \\\"%cs\\\"\\n\", opcode, NodeClassNames[opcode]);\n", '%', '%'); 462 fprintf(fp, " return false;\n"); 463 fprintf(fp, " }\n"); 464 465 // Return status, indicating a successful match. 466 fprintf(fp, " return true;\n"); 467 // Generate the closing brace for method Matcher::DFA 468 fprintf(fp, "}\n"); 469 Expr::check_buffers(); 470 } 471 472 473 class dfa_shared_preds { 474 enum { count = 4 }; 475 476 static bool _found[count]; 477 static const char* _type [count]; 478 static const char* _var [count]; 479 static const char* _pred [count]; 480 481 static void check_index(int index) { assert( 0 <= index && index < count, "Invalid index"); } 482 483 // Confirm that this is a separate sub-expression. 484 // Only need to catch common cases like " ... && shared ..." 485 // and avoid hazardous ones like "...->shared" 486 static bool valid_loc(char *pred, char *shared) { 487 // start of predicate is valid 488 if( shared == pred ) return true; 489 490 // Check previous character and recurse if needed 491 char *prev = shared - 1; 492 char c = *prev; 493 switch( c ) { 494 case ' ': 495 case '\n': 496 return dfa_shared_preds::valid_loc(pred, prev); 497 case '!': 498 case '(': 499 case '<': 500 case '=': 501 return true; 502 case '"': // such as: #line 10 "myfile.ad"\n mypredicate 503 return true; 504 case '|': 505 if (prev != pred && *(prev-1) == '|') return true; 506 break; 507 case '&': 508 if (prev != pred && *(prev-1) == '&') return true; 509 break; 510 default: 511 return false; 512 } 513 514 return false; 515 } 516 517 public: 518 519 static bool found(int index){ check_index(index); return _found[index]; } 520 static void set_found(int index, bool val) { check_index(index); _found[index] = val; } 521 static void reset_found() { 522 for( int i = 0; i < count; ++i ) { _found[i] = false; } 523 }; 524 525 static const char* type(int index) { check_index(index); return _type[index]; } 526 static const char* var (int index) { check_index(index); return _var [index]; } 527 static const char* pred(int index) { check_index(index); return _pred[index]; } 528 529 // Check each predicate in the MatchList for common sub-expressions 530 static void cse_matchlist(MatchList *matchList) { 531 for( MatchList *mList = matchList; mList != NULL; mList = mList->get_next() ) { 532 Predicate* predicate = mList->get_pred_obj(); 533 char* pred = mList->get_pred(); 534 if( pred != NULL ) { 535 for(int index = 0; index < count; ++index ) { 536 const char *shared_pred = dfa_shared_preds::pred(index); 537 const char *shared_pred_var = dfa_shared_preds::var(index); 538 bool result = dfa_shared_preds::cse_predicate(predicate, shared_pred, shared_pred_var); 539 if( result ) dfa_shared_preds::set_found(index, true); 540 } 541 } 542 } 543 } 544 545 // If the Predicate contains a common sub-expression, replace the Predicate's 546 // string with one that uses the variable name. 547 static bool cse_predicate(Predicate* predicate, const char *shared_pred, const char *shared_pred_var) { 548 bool result = false; 549 char *pred = predicate->_pred; 550 if( pred != NULL ) { 551 char *new_pred = pred; 552 for( char *shared_pred_loc = strstr(new_pred, shared_pred); 553 shared_pred_loc != NULL && dfa_shared_preds::valid_loc(new_pred,shared_pred_loc); 554 shared_pred_loc = strstr(new_pred, shared_pred) ) { 555 // Do not modify the original predicate string, it is shared 556 if( new_pred == pred ) { 557 new_pred = strdup(pred); 558 shared_pred_loc = strstr(new_pred, shared_pred); 559 } 560 // Replace shared_pred with variable name 561 strncpy(shared_pred_loc, shared_pred_var, strlen(shared_pred_var)); 562 } 563 // Install new predicate 564 if( new_pred != pred ) { 565 predicate->_pred = new_pred; 566 result = true; 567 } 568 } 569 return result; 570 } 571 572 // Output the hoisted common sub-expression if we found it in predicates 573 static void generate_cse(FILE *fp) { 574 for(int j = 0; j < count; ++j ) { 575 if( dfa_shared_preds::found(j) ) { 576 const char *shared_pred_type = dfa_shared_preds::type(j); 577 const char *shared_pred_var = dfa_shared_preds::var(j); 578 const char *shared_pred = dfa_shared_preds::pred(j); 579 fprintf(fp, " %s %s = %s;\n", shared_pred_type, shared_pred_var, shared_pred); 580 } 581 } 582 } 583 }; 584 // shared predicates, _var and _pred entry should be the same length 585 bool dfa_shared_preds::_found[dfa_shared_preds::count] 586 = { false, false, false, false }; 587 const char* dfa_shared_preds::_type[dfa_shared_preds::count] 588 = { "int", "jlong", "intptr_t", "bool" }; 589 const char* dfa_shared_preds::_var [dfa_shared_preds::count] 590 = { "_n_get_int__", "_n_get_long__", "_n_get_intptr_t__", "Compile__current____select_24_bit_instr__" }; 591 const char* dfa_shared_preds::_pred[dfa_shared_preds::count] 592 = { "n->get_int()", "n->get_long()", "n->get_intptr_t()", "Compile::current()->select_24_bit_instr()" }; 593 594 595 void ArchDesc::gen_dfa_state_body(FILE* fp, Dict &minimize, ProductionState &status, Dict &operands_chained_from, int i) { 596 // Start the body of each Op_XXX sub-dfa with a clean state. 597 status.initialize(); 598 599 // Walk the list, compacting it 600 MatchList* mList = _mlistab[i]; 601 do { 602 // Hash each entry using inputs as key and pointer as data. 603 // If there is already an entry, keep the one with lower cost, and 604 // remove the other one from the list. 605 prune_matchlist(minimize, *mList); 606 // Iterate 607 mList = mList->get_next(); 608 } while(mList != NULL); 609 610 // Hoist previously specified common sub-expressions out of predicates 611 dfa_shared_preds::reset_found(); 612 dfa_shared_preds::cse_matchlist(_mlistab[i]); 613 dfa_shared_preds::generate_cse(fp); 614 615 mList = _mlistab[i]; 616 617 // Walk the list again, generating code 618 do { 619 // Each match can generate its own chains 620 operands_chained_from.Clear(); 621 gen_match(fp, *mList, status, operands_chained_from); 622 mList = mList->get_next(); 623 } while(mList != NULL); 624 // Fill in any chain rules which add instructions 625 // These can generate their own chains as well. 626 operands_chained_from.Clear(); // 627 if( debug_output1 ) { fprintf(fp, "// top level chain rules for: %s \n", (char *)NodeClassNames[i]); } // %%%%% Explanation 628 const Expr *zeroCost = new Expr("0"); 629 chain_rule(fp, " ", (char *)NodeClassNames[i], zeroCost, "Invalid", 630 operands_chained_from, status); 631 } 632 633 634 635 //------------------------------Expr------------------------------------------ 636 Expr *Expr::_unknown_expr = NULL; 637 char Expr::string_buffer[STRING_BUFFER_LENGTH]; 638 char Expr::external_buffer[STRING_BUFFER_LENGTH]; 639 bool Expr::_init_buffers = Expr::init_buffers(); 640 641 Expr::Expr() { 642 _external_name = NULL; 643 _expr = "Invalid_Expr"; 644 _min_value = Expr::Max; 645 _max_value = Expr::Zero; 646 } 647 Expr::Expr(const char *cost) { 648 _external_name = NULL; 649 650 int intval = 0; 651 if( cost == NULL ) { 652 _expr = "0"; 653 _min_value = Expr::Zero; 654 _max_value = Expr::Zero; 655 } 656 else if( ADLParser::is_int_token(cost, intval) ) { 657 _expr = cost; 658 _min_value = intval; 659 _max_value = intval; 660 } 661 else { 662 assert( strcmp(cost,"0") != 0, "Recognize string zero as an int"); 663 _expr = cost; 664 _min_value = Expr::Zero; 665 _max_value = Expr::Max; 666 } 667 } 668 669 Expr::Expr(const char *name, const char *expression, int min_value, int max_value) { 670 _external_name = name; 671 _expr = expression ? expression : name; 672 _min_value = min_value; 673 _max_value = max_value; 674 assert(_min_value >= 0 && _min_value <= Expr::Max, "value out of range"); 675 assert(_max_value >= 0 && _max_value <= Expr::Max, "value out of range"); 676 } 677 678 Expr *Expr::clone() const { 679 Expr *cost = new Expr(); 680 cost->_external_name = _external_name; 681 cost->_expr = _expr; 682 cost->_min_value = _min_value; 683 cost->_max_value = _max_value; 684 685 return cost; 686 } 687 688 void Expr::add(const Expr *c) { 689 // Do not update fields until all computation is complete 690 const char *external = compute_external(this, c); 691 const char *expr = compute_expr(this, c); 692 int min_value = compute_min (this, c); 693 int max_value = compute_max (this, c); 694 695 _external_name = external; 696 _expr = expr; 697 _min_value = min_value; 698 _max_value = max_value; 699 } 700 701 void Expr::add(const char *c) { 702 Expr *cost = new Expr(c); 703 add(cost); 704 } 705 706 void Expr::add(const char *c, ArchDesc &AD) { 707 const Expr *e = AD.globalDefs()[c]; 708 if( e != NULL ) { 709 // use the value of 'c' defined in <arch>.ad 710 add(e); 711 } else { 712 Expr *cost = new Expr(c); 713 add(cost); 714 } 715 } 716 717 const char *Expr::compute_external(const Expr *c1, const Expr *c2) { 718 const char * result = NULL; 719 720 // Preserve use of external name which has a zero value 721 if( c1->_external_name != NULL ) { 722 sprintf(string_buffer, "%s", c1->as_string()); 723 if( !c2->is_zero() ) { 724 strncat(string_buffer, "+", STRING_BUFFER_LENGTH); 725 strncat(string_buffer, c2->as_string(), STRING_BUFFER_LENGTH); 726 } 727 result = strdup(string_buffer); 728 } 729 else if( c2->_external_name != NULL ) { 730 if( !c1->is_zero() ) { 731 sprintf(string_buffer, "%s", c1->as_string()); 732 strncat(string_buffer, " + ", STRING_BUFFER_LENGTH); 733 } else { 734 string_buffer[0] = '\0'; 735 } 736 strncat(string_buffer, c2->_external_name, STRING_BUFFER_LENGTH); 737 result = strdup(string_buffer); 738 } 739 return result; 740 } 741 742 const char *Expr::compute_expr(const Expr *c1, const Expr *c2) { 743 if( !c1->is_zero() ) { 744 sprintf( string_buffer, "%s", c1->_expr); 745 if( !c2->is_zero() ) { 746 strncat(string_buffer, "+", STRING_BUFFER_LENGTH); 747 strncat(string_buffer, c2->_expr, STRING_BUFFER_LENGTH); 748 } 749 } 750 else if( !c2->is_zero() ) { 751 sprintf( string_buffer, "%s", c2->_expr); 752 } 753 else { 754 sprintf( string_buffer, "0"); 755 } 756 char *cost = strdup(string_buffer); 757 758 return cost; 759 } 760 761 int Expr::compute_min(const Expr *c1, const Expr *c2) { 762 int result = c1->_min_value + c2->_min_value; 763 assert( result >= 0, "Invalid cost computation"); 764 765 return result; 766 } 767 768 int Expr::compute_max(const Expr *c1, const Expr *c2) { 769 STATIC_ASSERT(4 == sizeof(Expr::_max_value)); 770 STATIC_ASSERT(4 == sizeof(Expr::Max)); 771 long long result = static_cast<long long>(c1->_max_value) + static_cast<long long>(c2->_max_value); 772 if( result > Expr::Max ) { // check for overflow 773 result = Expr::Max; 774 } 775 776 return static_cast<int>(result); 777 } 778 779 void Expr::print() const { 780 if( _external_name != NULL ) { 781 printf(" %s == (%s) === [%d, %d]\n", _external_name, _expr, _min_value, _max_value); 782 } else { 783 printf(" %s === [%d, %d]\n", _expr, _min_value, _max_value); 784 } 785 } 786 787 void Expr::print_define(FILE *fp) const { 788 assert( _external_name != NULL, "definition does not have a name"); 789 assert( _min_value == _max_value, "Expect user definitions to have constant value"); 790 fprintf(fp, "#define %s (%s) \n", _external_name, _expr); 791 fprintf(fp, "// value == %d \n", _min_value); 792 } 793 794 void Expr::print_assert(FILE *fp) const { 795 assert( _external_name != NULL, "definition does not have a name"); 796 assert( _min_value == _max_value, "Expect user definitions to have constant value"); 797 fprintf(fp, " assert( %s == %d, \"Expect (%s) to equal %d\");\n", _external_name, _min_value, _expr, _min_value); 798 } 799 800 Expr *Expr::get_unknown() { 801 if( Expr::_unknown_expr == NULL ) { 802 Expr::_unknown_expr = new Expr(); 803 } 804 805 return Expr::_unknown_expr; 806 } 807 808 bool Expr::init_buffers() { 809 // Fill buffers with 0 810 for( int i = 0; i < STRING_BUFFER_LENGTH; ++i ) { 811 external_buffer[i] = '\0'; 812 string_buffer[i] = '\0'; 813 } 814 815 return true; 816 } 817 818 bool Expr::check_buffers() { 819 // returns 'true' if buffer use may have overflowed 820 bool ok = true; 821 for( int i = STRING_BUFFER_LENGTH - 100; i < STRING_BUFFER_LENGTH; ++i) { 822 if( external_buffer[i] != '\0' || string_buffer[i] != '\0' ) { 823 ok = false; 824 assert( false, "Expr:: Buffer overflow"); 825 } 826 } 827 828 return ok; 829 } 830 831 832 //------------------------------ExprDict--------------------------------------- 833 // Constructor 834 ExprDict::ExprDict( CmpKey cmp, Hash hash, Arena *arena ) 835 : _expr(cmp, hash, arena), _defines() { 836 } 837 ExprDict::~ExprDict() { 838 } 839 840 // Return # of name-Expr pairs in dict 841 int ExprDict::Size(void) const { 842 return _expr.Size(); 843 } 844 845 // define inserts the given key-value pair into the dictionary, 846 // and records the name in order for later output, ... 847 const Expr *ExprDict::define(const char *name, Expr *expr) { 848 const Expr *old_expr = (*this)[name]; 849 assert(old_expr == NULL, "Implementation does not support redefinition"); 850 851 _expr.Insert(name, expr); 852 _defines.addName(name); 853 854 return old_expr; 855 } 856 857 // Insert inserts the given key-value pair into the dictionary. The prior 858 // value of the key is returned; NULL if the key was not previously defined. 859 const Expr *ExprDict::Insert(const char *name, Expr *expr) { 860 return (Expr*)_expr.Insert((void*)name, (void*)expr); 861 } 862 863 // Finds the value of a given key; or NULL if not found. 864 // The dictionary is NOT changed. 865 const Expr *ExprDict::operator [](const char *name) const { 866 return (Expr*)_expr[name]; 867 } 868 869 void ExprDict::print_defines(FILE *fp) { 870 fprintf(fp, "\n"); 871 const char *name = NULL; 872 for( _defines.reset(); (name = _defines.iter()) != NULL; ) { 873 const Expr *expr = (const Expr*)_expr[name]; 874 assert( expr != NULL, "name in ExprDict without matching Expr in dictionary"); 875 expr->print_define(fp); 876 } 877 } 878 void ExprDict::print_asserts(FILE *fp) { 879 fprintf(fp, "\n"); 880 fprintf(fp, " // Following assertions generated from definition section\n"); 881 const char *name = NULL; 882 for( _defines.reset(); (name = _defines.iter()) != NULL; ) { 883 const Expr *expr = (const Expr*)_expr[name]; 884 assert( expr != NULL, "name in ExprDict without matching Expr in dictionary"); 885 expr->print_assert(fp); 886 } 887 } 888 889 // Print out the dictionary contents as key-value pairs 890 static void dumpekey(const void* key) { fprintf(stdout, "%s", (char*) key); } 891 static void dumpexpr(const void* expr) { fflush(stdout); ((Expr*)expr)->print(); } 892 893 void ExprDict::dump() { 894 _expr.print(dumpekey, dumpexpr); 895 } 896 897 898 //------------------------------ExprDict::private------------------------------ 899 // Disable public use of constructor, copy-ctor, operator =, operator == 900 ExprDict::ExprDict( ) : _expr(cmpkey,hashkey), _defines() { 901 assert( false, "NotImplemented"); 902 } 903 ExprDict::ExprDict( const ExprDict & ) : _expr(cmpkey,hashkey), _defines() { 904 assert( false, "NotImplemented"); 905 } 906 ExprDict &ExprDict::operator =( const ExprDict &rhs) { 907 assert( false, "NotImplemented"); 908 _expr = rhs._expr; 909 return *this; 910 } 911 // == compares two dictionaries; they must have the same keys (their keys 912 // must match using CmpKey) and they must have the same values (pointer 913 // comparison). If so 1 is returned, if not 0 is returned. 914 bool ExprDict::operator ==(const ExprDict &d) const { 915 assert( false, "NotImplemented"); 916 return false; 917 } 918 919 920 //------------------------------Production------------------------------------- 921 Production::Production(const char *result, const char *constraint, const char *valid) { 922 initialize(); 923 _result = result; 924 _constraint = constraint; 925 _valid = valid; 926 } 927 928 void Production::initialize() { 929 _result = NULL; 930 _constraint = NULL; 931 _valid = knownInvalid; 932 _cost_lb = Expr::get_unknown(); 933 _cost_ub = Expr::get_unknown(); 934 } 935 936 void Production::print() { 937 printf("%s", (_result == NULL ? "NULL" : _result ) ); 938 printf("%s", (_constraint == NULL ? "NULL" : _constraint ) ); 939 printf("%s", (_valid == NULL ? "NULL" : _valid ) ); 940 _cost_lb->print(); 941 _cost_ub->print(); 942 } 943 944 945 //------------------------------ProductionState-------------------------------- 946 void ProductionState::initialize() { 947 _constraint = noConstraint; 948 949 // reset each Production currently in the dictionary 950 DictI iter( &_production ); 951 const void *x, *y = NULL; 952 for( ; iter.test(); ++iter) { 953 x = iter._key; 954 y = iter._value; 955 Production *p = (Production*)y; 956 if( p != NULL ) { 957 p->initialize(); 958 } 959 } 960 } 961 962 Production *ProductionState::getProduction(const char *result) { 963 Production *p = (Production *)_production[result]; 964 if( p == NULL ) { 965 p = new Production(result, _constraint, knownInvalid); 966 _production.Insert(result, p); 967 } 968 969 return p; 970 } 971 972 void ProductionState::set_constraint(const char *constraint) { 973 _constraint = constraint; 974 } 975 976 const char *ProductionState::valid(const char *result) { 977 return getProduction(result)->valid(); 978 } 979 980 void ProductionState::set_valid(const char *result) { 981 Production *p = getProduction(result); 982 983 // Update valid as allowed by current constraints 984 if( _constraint == noConstraint ) { 985 p->_valid = knownValid; 986 } else { 987 if( p->_valid != knownValid ) { 988 p->_valid = unknownValid; 989 } 990 } 991 } 992 993 Expr *ProductionState::cost_lb(const char *result) { 994 return getProduction(result)->cost_lb(); 995 } 996 997 Expr *ProductionState::cost_ub(const char *result) { 998 return getProduction(result)->cost_ub(); 999 } 1000 1001 void ProductionState::set_cost_bounds(const char *result, const Expr *cost, bool has_state_check, bool has_cost_check) { 1002 Production *p = getProduction(result); 1003 1004 if( p->_valid == knownInvalid ) { 1005 // Our cost bounds are not unknown, just not defined. 1006 p->_cost_lb = cost->clone(); 1007 p->_cost_ub = cost->clone(); 1008 } else if (has_state_check || _constraint != noConstraint) { 1009 // The production is protected by a condition, so 1010 // the cost bounds may expand. 1011 // _cost_lb = min(cost, _cost_lb) 1012 if( cost->less_than_or_equal(p->_cost_lb) ) { 1013 p->_cost_lb = cost->clone(); 1014 } 1015 // _cost_ub = max(cost, _cost_ub) 1016 if( p->_cost_ub->less_than_or_equal(cost) ) { 1017 p->_cost_ub = cost->clone(); 1018 } 1019 } else if (has_cost_check) { 1020 // The production has no condition check, but does 1021 // have a cost check that could reduce the upper 1022 // and/or lower bound. 1023 // _cost_lb = min(cost, _cost_lb) 1024 if( cost->less_than_or_equal(p->_cost_lb) ) { 1025 p->_cost_lb = cost->clone(); 1026 } 1027 // _cost_ub = min(cost, _cost_ub) 1028 if( cost->less_than_or_equal(p->_cost_ub) ) { 1029 p->_cost_ub = cost->clone(); 1030 } 1031 } else { 1032 // The costs are unconditionally set. 1033 p->_cost_lb = cost->clone(); 1034 p->_cost_ub = cost->clone(); 1035 } 1036 1037 } 1038 1039 // Print out the dictionary contents as key-value pairs 1040 static void print_key (const void* key) { fprintf(stdout, "%s", (char*) key); } 1041 static void print_production(const void* production) { fflush(stdout); ((Production*)production)->print(); } 1042 1043 void ProductionState::print() { 1044 _production.print(print_key, print_production); 1045 }