Mercurial > hg > truffle
annotate src/share/vm/adlc/dfa.cpp @ 17467:55fb97c4c58d hs25-b65
8029233: Update copyright year to match last edit in jdk8 hotspot repository for 2013
Summary: Copyright year updated for files modified during 2013
Reviewed-by: twisti, iveresov
| author | mikael |
|---|---|
| date | Tue, 24 Dec 2013 11:48:39 -0800 |
| parents | 573cf206e381 |
| children | 4ca6dc0799b6 |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
17467
55fb97c4c58d
8029233: Update copyright year to match last edit in jdk8 hotspot repository for 2013
mikael
parents:
8878
diff
changeset
|
2 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. |
| 0 | 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 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
628
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
628
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
628
diff
changeset
|
21 * questions. |
| 0 | 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) { | |
|
8878
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
194 if (mList._lchild) { // If left child, check it |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
195 const char* lchild_to_upper = ArchDesc::getMachOperEnum(mList._lchild); |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
196 fprintf(fp, "STATE__VALID_CHILD(_kids[0], %s)", lchild_to_upper); |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
197 delete[] lchild_to_upper; |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
198 } |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
199 if (mList._lchild && mList._rchild) { // If both, add the "&&" |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
200 fprintf(fp, " && "); |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
201 } |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
202 if (mList._rchild) { // If right child, check it |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
203 const char* rchild_to_upper = ArchDesc::getMachOperEnum(mList._rchild); |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
204 fprintf(fp, "STATE__VALID_CHILD(_kids[1], %s)", rchild_to_upper); |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
205 delete[] rchild_to_upper; |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
206 } |
| 0 | 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"); | |
|
8878
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
216 if (mList._lchild) { // If left child, add it in |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
217 const char* lchild_to_upper = ArchDesc::getMachOperEnum(mList._lchild); |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
218 sprintf(Expr::buffer(), "_kids[0]->_cost[%s]", lchild_to_upper); |
| 0 | 219 c->add(Expr::buffer()); |
|
8878
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
220 delete[] lchild_to_upper; |
| 0 | 221 } |
|
8878
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
222 if (mList._rchild) { // If right child, add it in |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
223 const char* rchild_to_upper = ArchDesc::getMachOperEnum(mList._rchild); |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
224 sprintf(Expr::buffer(), "_kids[1]->_cost[%s]", rchild_to_upper); |
| 0 | 225 c->add(Expr::buffer()); |
|
8878
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
226 delete[] rchild_to_upper; |
| 0 | 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; | |
|
8878
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
246 const char *predicate_test = mList.get_pred(); |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
247 if (has_child_constraints || predicate_test) { |
| 0 | 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 | |
|
8878
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
253 if (predicate_test) { |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
254 if (has_child_constraints) { |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
255 fprintf(fp," &&\n"); |
|
573cf206e381
8006014: Memory leak in hotspot/src/share/vm/adlc/dfa.cpp
neliasso
parents:
1972
diff
changeset
|
256 } |
| 0 | 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 { | |
|
475
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
474 enum { count = 4 }; |
| 0 | 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 ' ': | |
|
475
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
495 case '\n': |
| 0 | 496 return dfa_shared_preds::valid_loc(pred, prev); |
| 497 case '!': | |
| 498 case '(': | |
| 499 case '<': | |
| 500 case '=': | |
| 501 return true; | |
|
475
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
502 case '"': // such as: #line 10 "myfile.ad"\n mypredicate |
|
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
503 return true; |
| 0 | 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 | |
|
475
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
583 bool dfa_shared_preds::_found[dfa_shared_preds::count] |
|
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
584 = { false, false, false, false }; |
|
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
585 const char* dfa_shared_preds::_type[dfa_shared_preds::count] |
|
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
586 = { "int", "jlong", "intptr_t", "bool" }; |
|
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
587 const char* dfa_shared_preds::_var [dfa_shared_preds::count] |
|
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
588 = { "_n_get_int__", "_n_get_long__", "_n_get_intptr_t__", "Compile__current____select_24_bit_instr__" }; |
|
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
589 const char* dfa_shared_preds::_pred[dfa_shared_preds::count] |
|
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
590 = { "n->get_int()", "n->get_long()", "n->get_intptr_t()", "Compile::current()->select_24_bit_instr()" }; |
| 0 | 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 | |
|
603
dbbe28fc66b5
6778669: Patch from Red Hat -- fixes compilation errors
twisti
parents:
475
diff
changeset
|
886 static void dumpekey(const void* key) { fprintf(stdout, "%s", (char*) key); } |
| 0 | 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 | |
|
603
dbbe28fc66b5
6778669: Patch from Red Hat -- fixes compilation errors
twisti
parents:
475
diff
changeset
|
1036 static void print_key (const void* key) { fprintf(stdout, "%s", (char*) key); } |
| 0 | 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 } |