1 /*
   2  * Copyright (c) 1997, 2013, 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     case '&':
 507       if( prev != pred && *(prev-1) == '&' ) return true;
 508     default:
 509       return false;
 510     }
 511 
 512     return false;
 513   }
 514 
 515 public:
 516 
 517   static bool        found(int index){ check_index(index); return _found[index]; }
 518   static void    set_found(int index, bool val) { check_index(index); _found[index] = val; }
 519   static void  reset_found() {
 520     for( int i = 0; i < count; ++i ) { _found[i] = false; }
 521   };
 522 
 523   static const char* type(int index) { check_index(index); return _type[index]; }
 524   static const char* var (int index) { check_index(index); return _var [index];  }
 525   static const char* pred(int index) { check_index(index); return _pred[index]; }
 526 
 527   // Check each predicate in the MatchList for common sub-expressions
 528   static void cse_matchlist(MatchList *matchList) {
 529     for( MatchList *mList = matchList; mList != NULL; mList = mList->get_next() ) {
 530       Predicate* predicate = mList->get_pred_obj();
 531       char*      pred      = mList->get_pred();
 532       if( pred != NULL ) {
 533         for(int index = 0; index < count; ++index ) {
 534           const char *shared_pred      = dfa_shared_preds::pred(index);
 535           const char *shared_pred_var  = dfa_shared_preds::var(index);
 536           bool result = dfa_shared_preds::cse_predicate(predicate, shared_pred, shared_pred_var);
 537           if( result ) dfa_shared_preds::set_found(index, true);
 538         }
 539       }
 540     }
 541   }
 542 
 543   // If the Predicate contains a common sub-expression, replace the Predicate's
 544   // string with one that uses the variable name.
 545   static bool cse_predicate(Predicate* predicate, const char *shared_pred, const char *shared_pred_var) {
 546     bool result = false;
 547     char *pred = predicate->_pred;
 548     if( pred != NULL ) {
 549       char *new_pred = pred;
 550       for( char *shared_pred_loc = strstr(new_pred, shared_pred);
 551       shared_pred_loc != NULL && dfa_shared_preds::valid_loc(new_pred,shared_pred_loc);
 552       shared_pred_loc = strstr(new_pred, shared_pred) ) {
 553         // Do not modify the original predicate string, it is shared
 554         if( new_pred == pred ) {
 555           new_pred = strdup(pred);
 556           shared_pred_loc = strstr(new_pred, shared_pred);
 557         }
 558         // Replace shared_pred with variable name
 559         strncpy(shared_pred_loc, shared_pred_var, strlen(shared_pred_var));
 560       }
 561       // Install new predicate
 562       if( new_pred != pred ) {
 563         predicate->_pred = new_pred;
 564         result = true;
 565       }
 566     }
 567     return result;
 568   }
 569 
 570   // Output the hoisted common sub-expression if we found it in predicates
 571   static void generate_cse(FILE *fp) {
 572     for(int j = 0; j < count; ++j ) {
 573       if( dfa_shared_preds::found(j) ) {
 574         const char *shared_pred_type = dfa_shared_preds::type(j);
 575         const char *shared_pred_var  = dfa_shared_preds::var(j);
 576         const char *shared_pred      = dfa_shared_preds::pred(j);
 577         fprintf(fp, "    %s %s = %s;\n", shared_pred_type, shared_pred_var, shared_pred);
 578       }
 579     }
 580   }
 581 };
 582 // shared predicates, _var and _pred entry should be the same length
 583 bool         dfa_shared_preds::_found[dfa_shared_preds::count]
 584   = { false, false, false, false };
 585 const char*  dfa_shared_preds::_type[dfa_shared_preds::count]
 586   = { "int", "jlong", "intptr_t", "bool" };
 587 const char*  dfa_shared_preds::_var [dfa_shared_preds::count]
 588   = { "_n_get_int__", "_n_get_long__", "_n_get_intptr_t__", "Compile__current____select_24_bit_instr__" };
 589 const char*  dfa_shared_preds::_pred[dfa_shared_preds::count]
 590   = { "n->get_int()", "n->get_long()", "n->get_intptr_t()", "Compile::current()->select_24_bit_instr()" };
 591 
 592 
 593 void ArchDesc::gen_dfa_state_body(FILE* fp, Dict &minimize, ProductionState &status, Dict &operands_chained_from, int i) {
 594   // Start the body of each Op_XXX sub-dfa with a clean state.
 595   status.initialize();
 596 
 597   // Walk the list, compacting it
 598   MatchList* mList = _mlistab[i];
 599   do {
 600     // Hash each entry using inputs as key and pointer as data.
 601     // If there is already an entry, keep the one with lower cost, and
 602     // remove the other one from the list.
 603     prune_matchlist(minimize, *mList);
 604     // Iterate
 605     mList = mList->get_next();
 606   } while(mList != NULL);
 607 
 608   // Hoist previously specified common sub-expressions out of predicates
 609   dfa_shared_preds::reset_found();
 610   dfa_shared_preds::cse_matchlist(_mlistab[i]);
 611   dfa_shared_preds::generate_cse(fp);
 612 
 613   mList = _mlistab[i];
 614 
 615   // Walk the list again, generating code
 616   do {
 617     // Each match can generate its own chains
 618     operands_chained_from.Clear();
 619     gen_match(fp, *mList, status, operands_chained_from);
 620     mList = mList->get_next();
 621   } while(mList != NULL);
 622   // Fill in any chain rules which add instructions
 623   // These can generate their own chains as well.
 624   operands_chained_from.Clear();  //
 625   if( debug_output1 ) { fprintf(fp, "// top level chain rules for: %s \n", (char *)NodeClassNames[i]); } // %%%%% Explanation
 626   const Expr *zeroCost = new Expr("0");
 627   chain_rule(fp, "   ", (char *)NodeClassNames[i], zeroCost, "Invalid",
 628              operands_chained_from, status);
 629 }
 630 
 631 
 632 
 633 //------------------------------Expr------------------------------------------
 634 Expr *Expr::_unknown_expr = NULL;
 635 char  Expr::string_buffer[STRING_BUFFER_LENGTH];
 636 char  Expr::external_buffer[STRING_BUFFER_LENGTH];
 637 bool  Expr::_init_buffers = Expr::init_buffers();
 638 
 639 Expr::Expr() {
 640   _external_name = NULL;
 641   _expr          = "Invalid_Expr";
 642   _min_value     = Expr::Max;
 643   _max_value     = Expr::Zero;
 644 }
 645 Expr::Expr(const char *cost) {
 646   _external_name = NULL;
 647 
 648   int intval = 0;
 649   if( cost == NULL ) {
 650     _expr = "0";
 651     _min_value = Expr::Zero;
 652     _max_value = Expr::Zero;
 653   }
 654   else if( ADLParser::is_int_token(cost, intval) ) {
 655     _expr = cost;
 656     _min_value = intval;
 657     _max_value = intval;
 658   }
 659   else {
 660     assert( strcmp(cost,"0") != 0, "Recognize string zero as an int");
 661     _expr = cost;
 662     _min_value = Expr::Zero;
 663     _max_value = Expr::Max;
 664   }
 665 }
 666 
 667 Expr::Expr(const char *name, const char *expression, int min_value, int max_value) {
 668   _external_name = name;
 669   _expr          = expression ? expression : name;
 670   _min_value     = min_value;
 671   _max_value     = max_value;
 672   assert(_min_value >= 0 && _min_value <= Expr::Max, "value out of range");
 673   assert(_max_value >= 0 && _max_value <= Expr::Max, "value out of range");
 674 }
 675 
 676 Expr *Expr::clone() const {
 677   Expr *cost = new Expr();
 678   cost->_external_name = _external_name;
 679   cost->_expr          = _expr;
 680   cost->_min_value     = _min_value;
 681   cost->_max_value     = _max_value;
 682 
 683   return cost;
 684 }
 685 
 686 void Expr::add(const Expr *c) {
 687   // Do not update fields until all computation is complete
 688   const char *external  = compute_external(this, c);
 689   const char *expr      = compute_expr(this, c);
 690   int         min_value = compute_min (this, c);
 691   int         max_value = compute_max (this, c);
 692 
 693   _external_name = external;
 694   _expr      = expr;
 695   _min_value = min_value;
 696   _max_value = max_value;
 697 }
 698 
 699 void Expr::add(const char *c) {
 700   Expr *cost = new Expr(c);
 701   add(cost);
 702 }
 703 
 704 void Expr::add(const char *c, ArchDesc &AD) {
 705   const Expr *e = AD.globalDefs()[c];
 706   if( e != NULL ) {
 707     // use the value of 'c' defined in <arch>.ad
 708     add(e);
 709   } else {
 710     Expr *cost = new Expr(c);
 711     add(cost);
 712   }
 713 }
 714 
 715 const char *Expr::compute_external(const Expr *c1, const Expr *c2) {
 716   const char * result = NULL;
 717 
 718   // Preserve use of external name which has a zero value
 719   if( c1->_external_name != NULL ) {
 720     sprintf( string_buffer, "%s", c1->as_string());
 721     if( !c2->is_zero() ) {
 722       strcat( string_buffer, "+");
 723       strcat( string_buffer, c2->as_string());
 724     }
 725     result = strdup(string_buffer);
 726   }
 727   else if( c2->_external_name != NULL ) {
 728     if( !c1->is_zero() ) {
 729       sprintf( string_buffer, "%s", c1->as_string());
 730       strcat( string_buffer, " + ");
 731     } else {
 732       string_buffer[0] = '\0';
 733     }
 734     strcat( string_buffer, c2->_external_name );
 735     result = strdup(string_buffer);
 736   }
 737   return result;
 738 }
 739 
 740 const char *Expr::compute_expr(const Expr *c1, const Expr *c2) {
 741   if( !c1->is_zero() ) {
 742     sprintf( string_buffer, "%s", c1->_expr);
 743     if( !c2->is_zero() ) {
 744       strcat( string_buffer, "+");
 745       strcat( string_buffer, c2->_expr);
 746     }
 747   }
 748   else if( !c2->is_zero() ) {
 749     sprintf( string_buffer, "%s", c2->_expr);
 750   }
 751   else {
 752     sprintf( string_buffer, "0");
 753   }
 754   char *cost = strdup(string_buffer);
 755 
 756   return cost;
 757 }
 758 
 759 int Expr::compute_min(const Expr *c1, const Expr *c2) {
 760   int result = c1->_min_value + c2->_min_value;
 761   assert( result >= 0, "Invalid cost computation");
 762 
 763   return result;
 764 }
 765 
 766 int Expr::compute_max(const Expr *c1, const Expr *c2) {
 767   int result = c1->_max_value + c2->_max_value;
 768   if( result < 0 ) {  // check for overflow
 769     result = Expr::Max;
 770   }
 771 
 772   return result;
 773 }
 774 
 775 void Expr::print() const {
 776   if( _external_name != NULL ) {
 777     printf("  %s == (%s) === [%d, %d]\n", _external_name, _expr, _min_value, _max_value);
 778   } else {
 779     printf("  %s === [%d, %d]\n", _expr, _min_value, _max_value);
 780   }
 781 }
 782 
 783 void Expr::print_define(FILE *fp) const {
 784   assert( _external_name != NULL, "definition does not have a name");
 785   assert( _min_value == _max_value, "Expect user definitions to have constant value");
 786   fprintf(fp, "#define  %s  (%s)  \n", _external_name, _expr);
 787   fprintf(fp, "// value == %d \n", _min_value);
 788 }
 789 
 790 void Expr::print_assert(FILE *fp) const {
 791   assert( _external_name != NULL, "definition does not have a name");
 792   assert( _min_value == _max_value, "Expect user definitions to have constant value");
 793   fprintf(fp, "  assert( %s == %d, \"Expect (%s) to equal %d\");\n", _external_name, _min_value, _expr, _min_value);
 794 }
 795 
 796 Expr *Expr::get_unknown() {
 797   if( Expr::_unknown_expr == NULL ) {
 798     Expr::_unknown_expr = new Expr();
 799   }
 800 
 801   return Expr::_unknown_expr;
 802 }
 803 
 804 bool Expr::init_buffers() {
 805   // Fill buffers with 0
 806   for( int i = 0; i < STRING_BUFFER_LENGTH; ++i ) {
 807     external_buffer[i] = '\0';
 808     string_buffer[i]   = '\0';
 809   }
 810 
 811   return true;
 812 }
 813 
 814 bool Expr::check_buffers() {
 815   // returns 'true' if buffer use may have overflowed
 816   bool ok = true;
 817   for( int i = STRING_BUFFER_LENGTH - 100; i < STRING_BUFFER_LENGTH; ++i) {
 818     if( external_buffer[i] != '\0' || string_buffer[i]   != '\0' ) {
 819       ok = false;
 820       assert( false, "Expr:: Buffer overflow");
 821     }
 822   }
 823 
 824   return ok;
 825 }
 826 
 827 
 828 //------------------------------ExprDict---------------------------------------
 829 // Constructor
 830 ExprDict::ExprDict( CmpKey cmp, Hash hash, Arena *arena )
 831   : _expr(cmp, hash, arena), _defines()  {
 832 }
 833 ExprDict::~ExprDict() {
 834 }
 835 
 836 // Return # of name-Expr pairs in dict
 837 int ExprDict::Size(void) const {
 838   return _expr.Size();
 839 }
 840 
 841 // define inserts the given key-value pair into the dictionary,
 842 // and records the name in order for later output, ...
 843 const Expr  *ExprDict::define(const char *name, Expr *expr) {
 844   const Expr *old_expr = (*this)[name];
 845   assert(old_expr == NULL, "Implementation does not support redefinition");
 846 
 847   _expr.Insert(name, expr);
 848   _defines.addName(name);
 849 
 850   return old_expr;
 851 }
 852 
 853 // Insert inserts the given key-value pair into the dictionary.  The prior
 854 // value of the key is returned; NULL if the key was not previously defined.
 855 const Expr  *ExprDict::Insert(const char *name, Expr *expr) {
 856   return (Expr*)_expr.Insert((void*)name, (void*)expr);
 857 }
 858 
 859 // Finds the value of a given key; or NULL if not found.
 860 // The dictionary is NOT changed.
 861 const Expr  *ExprDict::operator [](const char *name) const {
 862   return (Expr*)_expr[name];
 863 }
 864 
 865 void ExprDict::print_defines(FILE *fp) {
 866   fprintf(fp, "\n");
 867   const char *name = NULL;
 868   for( _defines.reset(); (name = _defines.iter()) != NULL; ) {
 869     const Expr *expr = (const Expr*)_expr[name];
 870     assert( expr != NULL, "name in ExprDict without matching Expr in dictionary");
 871     expr->print_define(fp);
 872   }
 873 }
 874 void ExprDict::print_asserts(FILE *fp) {
 875   fprintf(fp, "\n");
 876   fprintf(fp, "  // Following assertions generated from definition section\n");
 877   const char *name = NULL;
 878   for( _defines.reset(); (name = _defines.iter()) != NULL; ) {
 879     const Expr *expr = (const Expr*)_expr[name];
 880     assert( expr != NULL, "name in ExprDict without matching Expr in dictionary");
 881     expr->print_assert(fp);
 882   }
 883 }
 884 
 885 // Print out the dictionary contents as key-value pairs
 886 static void dumpekey(const void* key)  { fprintf(stdout, "%s", (char*) key); }
 887 static void dumpexpr(const void* expr) { fflush(stdout); ((Expr*)expr)->print(); }
 888 
 889 void ExprDict::dump() {
 890   _expr.print(dumpekey, dumpexpr);
 891 }
 892 
 893 
 894 //------------------------------ExprDict::private------------------------------
 895 // Disable public use of constructor, copy-ctor, operator =, operator ==
 896 ExprDict::ExprDict( ) : _expr(cmpkey,hashkey), _defines()  {
 897   assert( false, "NotImplemented");
 898 }
 899 ExprDict::ExprDict( const ExprDict & ) : _expr(cmpkey,hashkey), _defines() {
 900   assert( false, "NotImplemented");
 901 }
 902 ExprDict &ExprDict::operator =( const ExprDict &rhs) {
 903   assert( false, "NotImplemented");
 904   _expr = rhs._expr;
 905   return *this;
 906 }
 907 // == compares two dictionaries; they must have the same keys (their keys
 908 // must match using CmpKey) and they must have the same values (pointer
 909 // comparison).  If so 1 is returned, if not 0 is returned.
 910 bool ExprDict::operator ==(const ExprDict &d) const {
 911   assert( false, "NotImplemented");
 912   return false;
 913 }
 914 
 915 
 916 //------------------------------Production-------------------------------------
 917 Production::Production(const char *result, const char *constraint, const char *valid) {
 918   initialize();
 919   _result     = result;
 920   _constraint = constraint;
 921   _valid      = valid;
 922 }
 923 
 924 void Production::initialize() {
 925   _result     = NULL;
 926   _constraint = NULL;
 927   _valid      = knownInvalid;
 928   _cost_lb    = Expr::get_unknown();
 929   _cost_ub    = Expr::get_unknown();
 930 }
 931 
 932 void Production::print() {
 933   printf("%s", (_result     == NULL ? "NULL" : _result ) );
 934   printf("%s", (_constraint == NULL ? "NULL" : _constraint ) );
 935   printf("%s", (_valid      == NULL ? "NULL" : _valid ) );
 936   _cost_lb->print();
 937   _cost_ub->print();
 938 }
 939 
 940 
 941 //------------------------------ProductionState--------------------------------
 942 void ProductionState::initialize() {
 943   _constraint = noConstraint;
 944 
 945   // reset each Production currently in the dictionary
 946   DictI iter( &_production );
 947   const void *x, *y = NULL;
 948   for( ; iter.test(); ++iter) {
 949     x = iter._key;
 950     y = iter._value;
 951     Production *p = (Production*)y;
 952     if( p != NULL ) {
 953       p->initialize();
 954     }
 955   }
 956 }
 957 
 958 Production *ProductionState::getProduction(const char *result) {
 959   Production *p = (Production *)_production[result];
 960   if( p == NULL ) {
 961     p = new Production(result, _constraint, knownInvalid);
 962     _production.Insert(result, p);
 963   }
 964 
 965   return p;
 966 }
 967 
 968 void ProductionState::set_constraint(const char *constraint) {
 969   _constraint = constraint;
 970 }
 971 
 972 const char *ProductionState::valid(const char *result) {
 973   return getProduction(result)->valid();
 974 }
 975 
 976 void ProductionState::set_valid(const char *result) {
 977   Production *p = getProduction(result);
 978 
 979   // Update valid as allowed by current constraints
 980   if( _constraint == noConstraint ) {
 981     p->_valid = knownValid;
 982   } else {
 983     if( p->_valid != knownValid ) {
 984       p->_valid = unknownValid;
 985     }
 986   }
 987 }
 988 
 989 Expr *ProductionState::cost_lb(const char *result) {
 990   return getProduction(result)->cost_lb();
 991 }
 992 
 993 Expr *ProductionState::cost_ub(const char *result) {
 994   return getProduction(result)->cost_ub();
 995 }
 996 
 997 void ProductionState::set_cost_bounds(const char *result, const Expr *cost, bool has_state_check, bool has_cost_check) {
 998   Production *p = getProduction(result);
 999 
1000   if( p->_valid == knownInvalid ) {
1001     // Our cost bounds are not unknown, just not defined.
1002     p->_cost_lb = cost->clone();
1003     p->_cost_ub = cost->clone();
1004   } else if (has_state_check || _constraint != noConstraint) {
1005     // The production is protected by a condition, so
1006     // the cost bounds may expand.
1007     // _cost_lb = min(cost, _cost_lb)
1008     if( cost->less_than_or_equal(p->_cost_lb) ) {
1009       p->_cost_lb = cost->clone();
1010     }
1011     // _cost_ub = max(cost, _cost_ub)
1012     if( p->_cost_ub->less_than_or_equal(cost) ) {
1013       p->_cost_ub = cost->clone();
1014     }
1015   } else if (has_cost_check) {
1016     // The production has no condition check, but does
1017     // have a cost check that could reduce the upper
1018     // and/or lower bound.
1019     // _cost_lb = min(cost, _cost_lb)
1020     if( cost->less_than_or_equal(p->_cost_lb) ) {
1021       p->_cost_lb = cost->clone();
1022     }
1023     // _cost_ub = min(cost, _cost_ub)
1024     if( cost->less_than_or_equal(p->_cost_ub) ) {
1025       p->_cost_ub = cost->clone();
1026     }
1027   } else {
1028     // The costs are unconditionally set.
1029     p->_cost_lb = cost->clone();
1030     p->_cost_ub = cost->clone();
1031   }
1032 
1033 }
1034 
1035 // Print out the dictionary contents as key-value pairs
1036 static void print_key (const void* key)              { fprintf(stdout, "%s", (char*) key); }
1037 static void print_production(const void* production) { fflush(stdout); ((Production*)production)->print(); }
1038 
1039 void ProductionState::print() {
1040   _production.print(print_key, print_production);
1041 }