Mercurial > hg > graal-compiler
view src/share/vm/adlc/dfa.cpp @ 2149:7e37af9d69ef
7011379: G1: overly long concurrent marking cycles
Summary: This changeset introduces filtering of SATB buffers at the point when they are about to be enqueued. If this filtering clears enough entries on each buffer, the buffer can then be re-used and not enqueued. This cuts down the number of SATB buffers that need to be processed by the concurrent marking threads.
Reviewed-by: johnc, ysr
author | tonyp |
---|---|
date | Wed, 19 Jan 2011 09:35:17 -0500 |
parents | f95d63e2154a |
children | 573cf206e381 |
line wrap: on
line source
/* * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. * */ // DFA.CPP - Method definitions for outputting the matcher DFA from ADLC #include "adlc.hpp" //---------------------------Switches for debugging output--------------------- static bool debug_output = false; static bool debug_output1 = false; // top level chain rules //---------------------------Access to internals of class State---------------- static const char *sLeft = "_kids[0]"; static const char *sRight = "_kids[1]"; //---------------------------DFA productions----------------------------------- static const char *dfa_production = "DFA_PRODUCTION"; static const char *dfa_production_set_valid = "DFA_PRODUCTION__SET_VALID"; //---------------------------Production State---------------------------------- static const char *knownInvalid = "knownInvalid"; // The result does NOT have a rule defined static const char *knownValid = "knownValid"; // The result must be produced by a rule static const char *unknownValid = "unknownValid"; // Unknown (probably due to a child or predicate constraint) static const char *noConstraint = "noConstraint"; // No constraints seen so far static const char *hasConstraint = "hasConstraint"; // Within the first constraint //------------------------------Production------------------------------------ // Track the status of productions for a particular result class Production { public: const char *_result; const char *_constraint; const char *_valid; Expr *_cost_lb; // Cost lower bound for this production Expr *_cost_ub; // Cost upper bound for this production public: Production(const char *result, const char *constraint, const char *valid); ~Production() {}; void initialize(); // reset to be an empty container const char *valid() const { return _valid; } Expr *cost_lb() const { return (Expr *)_cost_lb; } Expr *cost_ub() const { return (Expr *)_cost_ub; } void print(); }; //------------------------------ProductionState-------------------------------- // Track the status of all production rule results // Reset for each root opcode (e.g., Op_RegI, Op_AddI, ...) class ProductionState { private: Dict _production; // map result of production, char*, to information or NULL const char *_constraint; public: // cmpstr does string comparisions. hashstr computes a key. ProductionState(Arena *arena) : _production(cmpstr, hashstr, arena) { initialize(); }; ~ProductionState() { }; void initialize(); // reset local and dictionary state const char *constraint(); void set_constraint(const char *constraint); // currently working inside of constraints const char *valid(const char *result); // unknownValid, or status for this production void set_valid(const char *result); // if not constrained, set status to knownValid Expr *cost_lb(const char *result); Expr *cost_ub(const char *result); void set_cost_bounds(const char *result, const Expr *cost, bool has_state_check, bool has_cost_check); // Return the Production associated with the result, // or create a new Production and insert it into the dictionary. Production *getProduction(const char *result); void print(); private: // Disable public use of constructor, copy-ctor, ... ProductionState( ) : _production(cmpstr, hashstr, Form::arena) { assert( false, "NotImplemented"); }; ProductionState( const ProductionState & ) : _production(cmpstr, hashstr, Form::arena) { assert( false, "NotImplemented"); }; // Deep-copy }; //---------------------------Helper Functions---------------------------------- // cost_check template: // 1) if (STATE__NOT_YET_VALID(EBXREGI) || _cost[EBXREGI] > c) { // 2) DFA_PRODUCTION__SET_VALID(EBXREGI, cmovI_memu_rule, c) // 3) } // static void cost_check(FILE *fp, const char *spaces, const char *arrayIdx, const Expr *cost, const char *rule, ProductionState &status) { bool state_check = false; // true if this production needs to check validity bool cost_check = false; // true if this production needs to check cost bool cost_is_above_upper_bound = false; // true if this production is unnecessary due to high cost bool cost_is_below_lower_bound = false; // true if this production replaces a higher cost production // Get information about this production const Expr *previous_ub = status.cost_ub(arrayIdx); if( !previous_ub->is_unknown() ) { if( previous_ub->less_than_or_equal(cost) ) { cost_is_above_upper_bound = true; if( debug_output ) { fprintf(fp, "// Previous rule with lower cost than: %s === %s_rule costs %s\n", arrayIdx, rule, cost->as_string()); } } } const Expr *previous_lb = status.cost_lb(arrayIdx); if( !previous_lb->is_unknown() ) { if( cost->less_than_or_equal(previous_lb) ) { cost_is_below_lower_bound = true; if( debug_output ) { fprintf(fp, "// Previous rule with higher cost\n"); } } } // line 1) // Check for validity and compare to other match costs const char *validity_check = status.valid(arrayIdx); if( validity_check == unknownValid ) { fprintf(fp, "%sif (STATE__NOT_YET_VALID(%s) || _cost[%s] > %s) {\n", spaces, arrayIdx, arrayIdx, cost->as_string()); state_check = true; cost_check = true; } else if( validity_check == knownInvalid ) { if( debug_output ) { fprintf(fp, "%s// %s KNOWN_INVALID \n", spaces, arrayIdx); } } else if( validity_check == knownValid ) { if( cost_is_above_upper_bound ) { // production cost is known to be too high. return; } else if( cost_is_below_lower_bound ) { // production will unconditionally overwrite a previous production that had higher cost } else { fprintf(fp, "%sif ( /* %s KNOWN_VALID || */ _cost[%s] > %s) {\n", spaces, arrayIdx, arrayIdx, cost->as_string()); cost_check = true; } } // line 2) // no need to set State vector if our state is knownValid const char *production = (validity_check == knownValid) ? dfa_production : dfa_production_set_valid; fprintf(fp, "%s %s(%s, %s_rule, %s)", spaces, production, arrayIdx, rule, cost->as_string() ); if( validity_check == knownValid ) { if( cost_is_below_lower_bound ) { fprintf(fp, "\t // overwrites higher cost rule"); } } fprintf(fp, "\n"); // line 3) if( cost_check || state_check ) { fprintf(fp, "%s}\n", spaces); } status.set_cost_bounds(arrayIdx, cost, state_check, cost_check); // Update ProductionState if( validity_check != knownValid ) { // set State vector if not previously known status.set_valid(arrayIdx); } } //---------------------------child_test---------------------------------------- // Example: // STATE__VALID_CHILD(_kids[0], FOO) && STATE__VALID_CHILD(_kids[1], BAR) // Macro equivalent to: _kids[0]->valid(FOO) && _kids[1]->valid(BAR) // static void child_test(FILE *fp, MatchList &mList) { if( mList._lchild ) // If left child, check it fprintf(fp, "STATE__VALID_CHILD(_kids[0], %s)", ArchDesc::getMachOperEnum(mList._lchild)); if( mList._lchild && mList._rchild ) // If both, add the "&&" fprintf(fp, " && " ); if( mList._rchild ) // If right child, check it fprintf(fp, "STATE__VALID_CHILD(_kids[1], %s)", ArchDesc::getMachOperEnum(mList._rchild)); } //---------------------------calc_cost----------------------------------------- // Example: // unsigned int c = _kids[0]->_cost[FOO] + _kids[1]->_cost[BAR] + 5; // Expr *ArchDesc::calc_cost(FILE *fp, const char *spaces, MatchList &mList, ProductionState &status) { fprintf(fp, "%sunsigned int c = ", spaces); Expr *c = new Expr("0"); if (mList._lchild ) { // If left child, add it in sprintf(Expr::buffer(), "_kids[0]->_cost[%s]", ArchDesc::getMachOperEnum(mList._lchild)); c->add(Expr::buffer()); } if (mList._rchild) { // If right child, add it in sprintf(Expr::buffer(), "_kids[1]->_cost[%s]", ArchDesc::getMachOperEnum(mList._rchild)); c->add(Expr::buffer()); } // Add in cost of this rule const char *mList_cost = mList.get_cost(); c->add(mList_cost, *this); fprintf(fp, "%s;\n", c->as_string()); c->set_external_name("c"); return c; } //---------------------------gen_match----------------------------------------- void ArchDesc::gen_match(FILE *fp, MatchList &mList, ProductionState &status, Dict &operands_chained_from) { const char *spaces4 = " "; const char *spaces6 = " "; fprintf(fp, "%s", spaces4); // Only generate child tests if this is not a leaf node bool has_child_constraints = mList._lchild || mList._rchild; const char *predicate_test = mList.get_pred(); if( has_child_constraints || predicate_test ) { // Open the child-and-predicate-test braces fprintf(fp, "if( "); status.set_constraint(hasConstraint); child_test(fp, mList); // Only generate predicate test if one exists for this match if( predicate_test ) { if( has_child_constraints ) { fprintf(fp," &&\n"); } fprintf(fp, "%s %s", spaces6, predicate_test); } // End of outer tests fprintf(fp," ) "); } else { // No child or predicate test needed status.set_constraint(noConstraint); } // End of outer tests fprintf(fp,"{\n"); // Calculate cost of this match const Expr *cost = calc_cost(fp, spaces6, mList, status); // Check against other match costs, and update cost & rule vectors cost_check(fp, spaces6, ArchDesc::getMachOperEnum(mList._resultStr), cost, mList._opcode, status); // If this is a member of an operand class, update the class cost & rule expand_opclass( fp, spaces6, cost, mList._resultStr, status); // Check if this rule should be used to generate the chains as well. const char *rule = /* set rule to "Invalid" for internal operands */ strcmp(mList._opcode,mList._resultStr) ? mList._opcode : "Invalid"; // If this rule produces an operand which has associated chain rules, // update the operands with the chain rule + this rule cost & this rule. chain_rule(fp, spaces6, mList._resultStr, cost, rule, operands_chained_from, status); // Close the child-and-predicate-test braces fprintf(fp, " }\n"); } //---------------------------expand_opclass------------------------------------ // Chain from one result_type to all other members of its operand class void ArchDesc::expand_opclass(FILE *fp, const char *indent, const Expr *cost, const char *result_type, ProductionState &status) { const Form *form = _globalNames[result_type]; OperandForm *op = form ? form->is_operand() : NULL; if( op && op->_classes.count() > 0 ) { if( debug_output ) { fprintf(fp, "// expand operand classes for operand: %s \n", (char *)op->_ident ); } // %%%%% Explanation // Iterate through all operand classes which include this operand op->_classes.reset(); const char *oclass; // Expr *cCost = new Expr(cost); while( (oclass = op->_classes.iter()) != NULL ) // Check against other match costs, and update cost & rule vectors cost_check(fp, indent, ArchDesc::getMachOperEnum(oclass), cost, result_type, status); } } //---------------------------chain_rule---------------------------------------- // Starting at 'operand', check if we know how to automatically generate other results void ArchDesc::chain_rule(FILE *fp, const char *indent, const char *operand, const Expr *icost, const char *irule, Dict &operands_chained_from, ProductionState &status) { // Check if we have already generated chains from this starting point if( operands_chained_from[operand] != NULL ) { return; } else { operands_chained_from.Insert( operand, operand); } if( debug_output ) { fprintf(fp, "// chain rules starting from: %s and %s \n", (char *)operand, (char *)irule); } // %%%%% Explanation ChainList *lst = (ChainList *)_chainRules[operand]; if (lst) { // printf("\nChain from <%s> at cost #%s\n",operand, icost ? icost : "_"); const char *result, *cost, *rule; for(lst->reset(); (lst->iter(result,cost,rule)) == true; ) { // Do not generate operands that are already available if( operands_chained_from[result] != NULL ) { continue; } else { // Compute the cost for previous match + chain_rule_cost // total_cost = icost + cost; Expr *total_cost = icost->clone(); // icost + cost total_cost->add(cost, *this); // Check for transitive chain rules Form *form = (Form *)_globalNames[rule]; if ( ! form->is_instruction()) { // printf(" result=%s cost=%s rule=%s\n", result, total_cost, rule); // Check against other match costs, and update cost & rule vectors const char *reduce_rule = strcmp(irule,"Invalid") ? irule : rule; cost_check(fp, indent, ArchDesc::getMachOperEnum(result), total_cost, reduce_rule, status); chain_rule(fp, indent, result, total_cost, irule, operands_chained_from, status); } else { // printf(" result=%s cost=%s rule=%s\n", result, total_cost, rule); // Check against other match costs, and update cost & rule vectors cost_check(fp, indent, ArchDesc::getMachOperEnum(result), total_cost, rule, status); chain_rule(fp, indent, result, total_cost, rule, operands_chained_from, status); } // If this is a member of an operand class, update class cost & rule expand_opclass( fp, indent, total_cost, result, status ); } } } } //---------------------------prune_matchlist----------------------------------- // Check for duplicate entries in a matchlist, and prune out the higher cost // entry. void ArchDesc::prune_matchlist(Dict &minimize, MatchList &mlist) { } //---------------------------buildDFA------------------------------------------ // DFA is a large switch with case statements for each ideal opcode encountered // in any match rule in the ad file. Each case has a series of if's to handle // the match or fail decisions. The matches test the cost function of that // rule, and prune any cases which are higher cost for the same reduction. // In order to generate the DFA we walk the table of ideal opcode/MatchList // pairs generated by the ADLC front end to build the contents of the case // statements (a series of if statements). void ArchDesc::buildDFA(FILE* fp) { int i; // Remember operands that are the starting points for chain rules. // Prevent cycles by checking if we have already generated chain. Dict operands_chained_from(cmpstr, hashstr, Form::arena); // Hash inputs to match rules so that final DFA contains only one entry for // each match pattern which is the low cost entry. Dict minimize(cmpstr, hashstr, Form::arena); // Track status of dfa for each resulting production // reset for each ideal root. ProductionState status(Form::arena); // Output the start of the DFA method into the output file fprintf(fp, "\n"); fprintf(fp, "//------------------------- Source -----------------------------------------\n"); // Do not put random source code into the DFA. // If there are constants which need sharing, put them in "source_hpp" forms. // _source.output(fp); fprintf(fp, "\n"); fprintf(fp, "//------------------------- Attributes -------------------------------------\n"); _attributes.output(fp); fprintf(fp, "\n"); fprintf(fp, "//------------------------- Macros -----------------------------------------\n"); // #define DFA_PRODUCTION(result, rule, cost)\ // _cost[ (result) ] = cost; _rule[ (result) ] = rule; fprintf(fp, "#define %s(result, rule, cost)\\\n", dfa_production); fprintf(fp, " _cost[ (result) ] = cost; _rule[ (result) ] = rule;\n"); fprintf(fp, "\n"); // #define DFA_PRODUCTION__SET_VALID(result, rule, cost)\ // DFA_PRODUCTION( (result), (rule), (cost) ); STATE__SET_VALID( (result) ); fprintf(fp, "#define %s(result, rule, cost)\\\n", dfa_production_set_valid); fprintf(fp, " %s( (result), (rule), (cost) ); STATE__SET_VALID( (result) );\n", dfa_production); fprintf(fp, "\n"); fprintf(fp, "//------------------------- DFA --------------------------------------------\n"); fprintf(fp, "// DFA is a large switch with case statements for each ideal opcode encountered\n" "// in any match rule in the ad file. Each case has a series of if's to handle\n" "// the match or fail decisions. The matches test the cost function of that\n" "// rule, and prune any cases which are higher cost for the same reduction.\n" "// In order to generate the DFA we walk the table of ideal opcode/MatchList\n" "// pairs generated by the ADLC front end to build the contents of the case\n" "// statements (a series of if statements).\n" ); fprintf(fp, "\n"); fprintf(fp, "\n"); if (_dfa_small) { // Now build the individual routines just like the switch entries in large version // Iterate over the table of MatchLists, start at first valid opcode of 1 for (i = 1; i < _last_opcode; i++) { if (_mlistab[i] == NULL) continue; // Generate the routine header statement for this opcode fprintf(fp, "void State::_sub_Op_%s(const Node *n){\n", NodeClassNames[i]); // Generate body. Shared for both inline and out-of-line version gen_dfa_state_body(fp, minimize, status, operands_chained_from, i); // End of routine fprintf(fp, "}\n"); } } fprintf(fp, "bool State::DFA"); fprintf(fp, "(int opcode, const Node *n) {\n"); fprintf(fp, " switch(opcode) {\n"); // Iterate over the table of MatchLists, start at first valid opcode of 1 for (i = 1; i < _last_opcode; i++) { if (_mlistab[i] == NULL) continue; // Generate the case statement for this opcode if (_dfa_small) { fprintf(fp, " case Op_%s: { _sub_Op_%s(n);\n", NodeClassNames[i], NodeClassNames[i]); } else { fprintf(fp, " case Op_%s: {\n", NodeClassNames[i]); // Walk the list, compacting it gen_dfa_state_body(fp, minimize, status, operands_chained_from, i); } // Print the "break" fprintf(fp, " break;\n"); fprintf(fp, " }\n"); } // Generate the default case for switch(opcode) fprintf(fp, " \n"); fprintf(fp, " default:\n"); fprintf(fp, " tty->print(\"Default case invoked for: \\n\");\n"); fprintf(fp, " tty->print(\" opcode = %cd, \\\"%cs\\\"\\n\", opcode, NodeClassNames[opcode]);\n", '%', '%'); fprintf(fp, " return false;\n"); fprintf(fp, " }\n"); // Return status, indicating a successful match. fprintf(fp, " return true;\n"); // Generate the closing brace for method Matcher::DFA fprintf(fp, "}\n"); Expr::check_buffers(); } class dfa_shared_preds { enum { count = 4 }; static bool _found[count]; static const char* _type [count]; static const char* _var [count]; static const char* _pred [count]; static void check_index(int index) { assert( 0 <= index && index < count, "Invalid index"); } // Confirm that this is a separate sub-expression. // Only need to catch common cases like " ... && shared ..." // and avoid hazardous ones like "...->shared" static bool valid_loc(char *pred, char *shared) { // start of predicate is valid if( shared == pred ) return true; // Check previous character and recurse if needed char *prev = shared - 1; char c = *prev; switch( c ) { case ' ': case '\n': return dfa_shared_preds::valid_loc(pred, prev); case '!': case '(': case '<': case '=': return true; case '"': // such as: #line 10 "myfile.ad"\n mypredicate return true; case '|': if( prev != pred && *(prev-1) == '|' ) return true; case '&': if( prev != pred && *(prev-1) == '&' ) return true; default: return false; } return false; } public: static bool found(int index){ check_index(index); return _found[index]; } static void set_found(int index, bool val) { check_index(index); _found[index] = val; } static void reset_found() { for( int i = 0; i < count; ++i ) { _found[i] = false; } }; static const char* type(int index) { check_index(index); return _type[index]; } static const char* var (int index) { check_index(index); return _var [index]; } static const char* pred(int index) { check_index(index); return _pred[index]; } // Check each predicate in the MatchList for common sub-expressions static void cse_matchlist(MatchList *matchList) { for( MatchList *mList = matchList; mList != NULL; mList = mList->get_next() ) { Predicate* predicate = mList->get_pred_obj(); char* pred = mList->get_pred(); if( pred != NULL ) { for(int index = 0; index < count; ++index ) { const char *shared_pred = dfa_shared_preds::pred(index); const char *shared_pred_var = dfa_shared_preds::var(index); bool result = dfa_shared_preds::cse_predicate(predicate, shared_pred, shared_pred_var); if( result ) dfa_shared_preds::set_found(index, true); } } } } // If the Predicate contains a common sub-expression, replace the Predicate's // string with one that uses the variable name. static bool cse_predicate(Predicate* predicate, const char *shared_pred, const char *shared_pred_var) { bool result = false; char *pred = predicate->_pred; if( pred != NULL ) { char *new_pred = pred; for( char *shared_pred_loc = strstr(new_pred, shared_pred); shared_pred_loc != NULL && dfa_shared_preds::valid_loc(new_pred,shared_pred_loc); shared_pred_loc = strstr(new_pred, shared_pred) ) { // Do not modify the original predicate string, it is shared if( new_pred == pred ) { new_pred = strdup(pred); shared_pred_loc = strstr(new_pred, shared_pred); } // Replace shared_pred with variable name strncpy(shared_pred_loc, shared_pred_var, strlen(shared_pred_var)); } // Install new predicate if( new_pred != pred ) { predicate->_pred = new_pred; result = true; } } return result; } // Output the hoisted common sub-expression if we found it in predicates static void generate_cse(FILE *fp) { for(int j = 0; j < count; ++j ) { if( dfa_shared_preds::found(j) ) { const char *shared_pred_type = dfa_shared_preds::type(j); const char *shared_pred_var = dfa_shared_preds::var(j); const char *shared_pred = dfa_shared_preds::pred(j); fprintf(fp, " %s %s = %s;\n", shared_pred_type, shared_pred_var, shared_pred); } } } }; // shared predicates, _var and _pred entry should be the same length bool dfa_shared_preds::_found[dfa_shared_preds::count] = { false, false, false, false }; const char* dfa_shared_preds::_type[dfa_shared_preds::count] = { "int", "jlong", "intptr_t", "bool" }; const char* dfa_shared_preds::_var [dfa_shared_preds::count] = { "_n_get_int__", "_n_get_long__", "_n_get_intptr_t__", "Compile__current____select_24_bit_instr__" }; const char* dfa_shared_preds::_pred[dfa_shared_preds::count] = { "n->get_int()", "n->get_long()", "n->get_intptr_t()", "Compile::current()->select_24_bit_instr()" }; void ArchDesc::gen_dfa_state_body(FILE* fp, Dict &minimize, ProductionState &status, Dict &operands_chained_from, int i) { // Start the body of each Op_XXX sub-dfa with a clean state. status.initialize(); // Walk the list, compacting it MatchList* mList = _mlistab[i]; do { // Hash each entry using inputs as key and pointer as data. // If there is already an entry, keep the one with lower cost, and // remove the other one from the list. prune_matchlist(minimize, *mList); // Iterate mList = mList->get_next(); } while(mList != NULL); // Hoist previously specified common sub-expressions out of predicates dfa_shared_preds::reset_found(); dfa_shared_preds::cse_matchlist(_mlistab[i]); dfa_shared_preds::generate_cse(fp); mList = _mlistab[i]; // Walk the list again, generating code do { // Each match can generate its own chains operands_chained_from.Clear(); gen_match(fp, *mList, status, operands_chained_from); mList = mList->get_next(); } while(mList != NULL); // Fill in any chain rules which add instructions // These can generate their own chains as well. operands_chained_from.Clear(); // if( debug_output1 ) { fprintf(fp, "// top level chain rules for: %s \n", (char *)NodeClassNames[i]); } // %%%%% Explanation const Expr *zeroCost = new Expr("0"); chain_rule(fp, " ", (char *)NodeClassNames[i], zeroCost, "Invalid", operands_chained_from, status); } //------------------------------Expr------------------------------------------ Expr *Expr::_unknown_expr = NULL; char Expr::string_buffer[STRING_BUFFER_LENGTH]; char Expr::external_buffer[STRING_BUFFER_LENGTH]; bool Expr::_init_buffers = Expr::init_buffers(); Expr::Expr() { _external_name = NULL; _expr = "Invalid_Expr"; _min_value = Expr::Max; _max_value = Expr::Zero; } Expr::Expr(const char *cost) { _external_name = NULL; int intval = 0; if( cost == NULL ) { _expr = "0"; _min_value = Expr::Zero; _max_value = Expr::Zero; } else if( ADLParser::is_int_token(cost, intval) ) { _expr = cost; _min_value = intval; _max_value = intval; } else { assert( strcmp(cost,"0") != 0, "Recognize string zero as an int"); _expr = cost; _min_value = Expr::Zero; _max_value = Expr::Max; } } Expr::Expr(const char *name, const char *expression, int min_value, int max_value) { _external_name = name; _expr = expression ? expression : name; _min_value = min_value; _max_value = max_value; assert(_min_value >= 0 && _min_value <= Expr::Max, "value out of range"); assert(_max_value >= 0 && _max_value <= Expr::Max, "value out of range"); } Expr *Expr::clone() const { Expr *cost = new Expr(); cost->_external_name = _external_name; cost->_expr = _expr; cost->_min_value = _min_value; cost->_max_value = _max_value; return cost; } void Expr::add(const Expr *c) { // Do not update fields until all computation is complete const char *external = compute_external(this, c); const char *expr = compute_expr(this, c); int min_value = compute_min (this, c); int max_value = compute_max (this, c); _external_name = external; _expr = expr; _min_value = min_value; _max_value = max_value; } void Expr::add(const char *c) { Expr *cost = new Expr(c); add(cost); } void Expr::add(const char *c, ArchDesc &AD) { const Expr *e = AD.globalDefs()[c]; if( e != NULL ) { // use the value of 'c' defined in <arch>.ad add(e); } else { Expr *cost = new Expr(c); add(cost); } } const char *Expr::compute_external(const Expr *c1, const Expr *c2) { const char * result = NULL; // Preserve use of external name which has a zero value if( c1->_external_name != NULL ) { sprintf( string_buffer, "%s", c1->as_string()); if( !c2->is_zero() ) { strcat( string_buffer, "+"); strcat( string_buffer, c2->as_string()); } result = strdup(string_buffer); } else if( c2->_external_name != NULL ) { if( !c1->is_zero() ) { sprintf( string_buffer, "%s", c1->as_string()); strcat( string_buffer, " + "); } else { string_buffer[0] = '\0'; } strcat( string_buffer, c2->_external_name ); result = strdup(string_buffer); } return result; } const char *Expr::compute_expr(const Expr *c1, const Expr *c2) { if( !c1->is_zero() ) { sprintf( string_buffer, "%s", c1->_expr); if( !c2->is_zero() ) { strcat( string_buffer, "+"); strcat( string_buffer, c2->_expr); } } else if( !c2->is_zero() ) { sprintf( string_buffer, "%s", c2->_expr); } else { sprintf( string_buffer, "0"); } char *cost = strdup(string_buffer); return cost; } int Expr::compute_min(const Expr *c1, const Expr *c2) { int result = c1->_min_value + c2->_min_value; assert( result >= 0, "Invalid cost computation"); return result; } int Expr::compute_max(const Expr *c1, const Expr *c2) { int result = c1->_max_value + c2->_max_value; if( result < 0 ) { // check for overflow result = Expr::Max; } return result; } void Expr::print() const { if( _external_name != NULL ) { printf(" %s == (%s) === [%d, %d]\n", _external_name, _expr, _min_value, _max_value); } else { printf(" %s === [%d, %d]\n", _expr, _min_value, _max_value); } } void Expr::print_define(FILE *fp) const { assert( _external_name != NULL, "definition does not have a name"); assert( _min_value == _max_value, "Expect user definitions to have constant value"); fprintf(fp, "#define %s (%s) \n", _external_name, _expr); fprintf(fp, "// value == %d \n", _min_value); } void Expr::print_assert(FILE *fp) const { assert( _external_name != NULL, "definition does not have a name"); assert( _min_value == _max_value, "Expect user definitions to have constant value"); fprintf(fp, " assert( %s == %d, \"Expect (%s) to equal %d\");\n", _external_name, _min_value, _expr, _min_value); } Expr *Expr::get_unknown() { if( Expr::_unknown_expr == NULL ) { Expr::_unknown_expr = new Expr(); } return Expr::_unknown_expr; } bool Expr::init_buffers() { // Fill buffers with 0 for( int i = 0; i < STRING_BUFFER_LENGTH; ++i ) { external_buffer[i] = '\0'; string_buffer[i] = '\0'; } return true; } bool Expr::check_buffers() { // returns 'true' if buffer use may have overflowed bool ok = true; for( int i = STRING_BUFFER_LENGTH - 100; i < STRING_BUFFER_LENGTH; ++i) { if( external_buffer[i] != '\0' || string_buffer[i] != '\0' ) { ok = false; assert( false, "Expr:: Buffer overflow"); } } return ok; } //------------------------------ExprDict--------------------------------------- // Constructor ExprDict::ExprDict( CmpKey cmp, Hash hash, Arena *arena ) : _expr(cmp, hash, arena), _defines() { } ExprDict::~ExprDict() { } // Return # of name-Expr pairs in dict int ExprDict::Size(void) const { return _expr.Size(); } // define inserts the given key-value pair into the dictionary, // and records the name in order for later output, ... const Expr *ExprDict::define(const char *name, Expr *expr) { const Expr *old_expr = (*this)[name]; assert(old_expr == NULL, "Implementation does not support redefinition"); _expr.Insert(name, expr); _defines.addName(name); return old_expr; } // Insert inserts the given key-value pair into the dictionary. The prior // value of the key is returned; NULL if the key was not previously defined. const Expr *ExprDict::Insert(const char *name, Expr *expr) { return (Expr*)_expr.Insert((void*)name, (void*)expr); } // Finds the value of a given key; or NULL if not found. // The dictionary is NOT changed. const Expr *ExprDict::operator [](const char *name) const { return (Expr*)_expr[name]; } void ExprDict::print_defines(FILE *fp) { fprintf(fp, "\n"); const char *name = NULL; for( _defines.reset(); (name = _defines.iter()) != NULL; ) { const Expr *expr = (const Expr*)_expr[name]; assert( expr != NULL, "name in ExprDict without matching Expr in dictionary"); expr->print_define(fp); } } void ExprDict::print_asserts(FILE *fp) { fprintf(fp, "\n"); fprintf(fp, " // Following assertions generated from definition section\n"); const char *name = NULL; for( _defines.reset(); (name = _defines.iter()) != NULL; ) { const Expr *expr = (const Expr*)_expr[name]; assert( expr != NULL, "name in ExprDict without matching Expr in dictionary"); expr->print_assert(fp); } } // Print out the dictionary contents as key-value pairs static void dumpekey(const void* key) { fprintf(stdout, "%s", (char*) key); } static void dumpexpr(const void* expr) { fflush(stdout); ((Expr*)expr)->print(); } void ExprDict::dump() { _expr.print(dumpekey, dumpexpr); } //------------------------------ExprDict::private------------------------------ // Disable public use of constructor, copy-ctor, operator =, operator == ExprDict::ExprDict( ) : _expr(cmpkey,hashkey), _defines() { assert( false, "NotImplemented"); } ExprDict::ExprDict( const ExprDict & ) : _expr(cmpkey,hashkey), _defines() { assert( false, "NotImplemented"); } ExprDict &ExprDict::operator =( const ExprDict &rhs) { assert( false, "NotImplemented"); _expr = rhs._expr; return *this; } // == compares two dictionaries; they must have the same keys (their keys // must match using CmpKey) and they must have the same values (pointer // comparison). If so 1 is returned, if not 0 is returned. bool ExprDict::operator ==(const ExprDict &d) const { assert( false, "NotImplemented"); return false; } //------------------------------Production------------------------------------- Production::Production(const char *result, const char *constraint, const char *valid) { initialize(); _result = result; _constraint = constraint; _valid = valid; } void Production::initialize() { _result = NULL; _constraint = NULL; _valid = knownInvalid; _cost_lb = Expr::get_unknown(); _cost_ub = Expr::get_unknown(); } void Production::print() { printf("%s", (_result == NULL ? "NULL" : _result ) ); printf("%s", (_constraint == NULL ? "NULL" : _constraint ) ); printf("%s", (_valid == NULL ? "NULL" : _valid ) ); _cost_lb->print(); _cost_ub->print(); } //------------------------------ProductionState-------------------------------- void ProductionState::initialize() { _constraint = noConstraint; // reset each Production currently in the dictionary DictI iter( &_production ); const void *x, *y = NULL; for( ; iter.test(); ++iter) { x = iter._key; y = iter._value; Production *p = (Production*)y; if( p != NULL ) { p->initialize(); } } } Production *ProductionState::getProduction(const char *result) { Production *p = (Production *)_production[result]; if( p == NULL ) { p = new Production(result, _constraint, knownInvalid); _production.Insert(result, p); } return p; } void ProductionState::set_constraint(const char *constraint) { _constraint = constraint; } const char *ProductionState::valid(const char *result) { return getProduction(result)->valid(); } void ProductionState::set_valid(const char *result) { Production *p = getProduction(result); // Update valid as allowed by current constraints if( _constraint == noConstraint ) { p->_valid = knownValid; } else { if( p->_valid != knownValid ) { p->_valid = unknownValid; } } } Expr *ProductionState::cost_lb(const char *result) { return getProduction(result)->cost_lb(); } Expr *ProductionState::cost_ub(const char *result) { return getProduction(result)->cost_ub(); } void ProductionState::set_cost_bounds(const char *result, const Expr *cost, bool has_state_check, bool has_cost_check) { Production *p = getProduction(result); if( p->_valid == knownInvalid ) { // Our cost bounds are not unknown, just not defined. p->_cost_lb = cost->clone(); p->_cost_ub = cost->clone(); } else if (has_state_check || _constraint != noConstraint) { // The production is protected by a condition, so // the cost bounds may expand. // _cost_lb = min(cost, _cost_lb) if( cost->less_than_or_equal(p->_cost_lb) ) { p->_cost_lb = cost->clone(); } // _cost_ub = max(cost, _cost_ub) if( p->_cost_ub->less_than_or_equal(cost) ) { p->_cost_ub = cost->clone(); } } else if (has_cost_check) { // The production has no condition check, but does // have a cost check that could reduce the upper // and/or lower bound. // _cost_lb = min(cost, _cost_lb) if( cost->less_than_or_equal(p->_cost_lb) ) { p->_cost_lb = cost->clone(); } // _cost_ub = min(cost, _cost_ub) if( cost->less_than_or_equal(p->_cost_ub) ) { p->_cost_ub = cost->clone(); } } else { // The costs are unconditionally set. p->_cost_lb = cost->clone(); p->_cost_ub = cost->clone(); } } // Print out the dictionary contents as key-value pairs static void print_key (const void* key) { fprintf(stdout, "%s", (char*) key); } static void print_production(const void* production) { fflush(stdout); ((Production*)production)->print(); } void ProductionState::print() { _production.print(print_key, print_production); }