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