dfa.cpp revision 603
/*
* Copyright 1997-2009 Sun Microsystems, Inc. All Rights Reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
* CA 95054 USA or visit www.sun.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 *unknownValid = "unknownValid"; // Unknown (probably due to a child or predicate constraint)
//------------------------------Production------------------------------------
// Track the status of productions for a particular result
class Production {
public:
const char *_result;
const char *_constraint;
const char *_valid;
public:
~Production() {};
void initialize(); // reset to be an empty container
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:
const char *_constraint;
public:
// cmpstr does string comparisions. hashstr computes a key.
~ProductionState() { };
void initialize(); // reset local and dictionary state
const char *constraint();
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.
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) }
//
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
if( !previous_ub->is_unknown() ) {
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()); }
}
}
if( !previous_lb->is_unknown() ) {
cost_is_below_lower_bound = true;
}
}
// line 1)
// Check for validity and compare to other match costs
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 ) {
}
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;
if( validity_check == knownValid ) {
}
// line 3)
if( cost_check || state_check ) {
}
// Update ProductionState
if( validity_check != knownValid ) {
// set State vector if not previously known
}
}
//---------------------------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)
//
}
//---------------------------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) {
}
}
// Add in cost of this rule
c->add(mList_cost, *this);
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 = " ";
// Only generate child tests if this is not a leaf node
if( has_child_constraints || predicate_test ) {
// Open the child-and-predicate-test braces
// Only generate predicate test if one exists for this match
if( predicate_test ) {
}
// End of outer tests
} else {
// No child or predicate test needed
}
// End of outer tests
// Calculate cost of this match
// Check against other match costs, and update cost & rule vectors
// If this is a member of an operand class, update the class cost & rule
// Check if this rule should be used to generate the chains as well.
const char *rule = /* set rule to "Invalid" for internal operands */
// If this rule produces an operand which has associated chain rules,
// update the operands with the chain rule + this rule cost & this rule.
// Close the child-and-predicate-test braces
}
//---------------------------expand_opclass------------------------------------
// Chain from one result_type to all other members of its operand class
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
const char *oclass;
// Expr *cCost = new Expr(cost);
// Check against other match costs, and update cost & rule vectors
}
}
//---------------------------chain_rule----------------------------------------
// Starting at 'operand', check if we know how to automatically generate other results
// Check if we have already generated chains from this starting point
return;
} else {
}
if( debug_output ) { fprintf(fp, "// chain rules starting from: %s and %s \n", (char *)operand, (char *)irule); } // %%%%% Explanation
if (lst) {
// printf("\nChain from <%s> at cost #%s\n",operand, icost ? icost : "_");
// Do not generate operands that are already available
continue;
} else {
// Compute the cost for previous match + chain_rule_cost
// total_cost = icost + cost;
// Check for transitive chain rules
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
} else {
// printf(" result=%s cost=%s rule=%s\n", result, total_cost, rule);
// Check against other match costs, and update cost & rule vectors
}
// If this is a member of an operand class, update class cost & rule
}
}
}
}
//---------------------------prune_matchlist-----------------------------------
// Check for duplicate entries in a matchlist, and prune out the higher cost
// entry.
}
//---------------------------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.
// pairs generated by the ADLC front end to build the contents of the case
// statements (a series of if statements).
int i;
// Remember operands that are the starting points for chain rules.
// Prevent cycles by checking if we have already generated chain.
// Hash inputs to match rules so that final DFA contains only one entry for
// each match pattern which is the low cost entry.
// Track status of dfa for each resulting production
// reset for each ideal root.
// Output the start of the DFA method into the output file
// 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);
// #define DFA_PRODUCTION(result, rule, cost)\
// _cost[ (result) ] = cost; _rule[ (result) ] = rule;
// #define DFA_PRODUCTION__SET_VALID(result, rule, cost)\
// DFA_PRODUCTION( (result), (rule), (cost) ); STATE__SET_VALID( (result) );
"// 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"
"// pairs generated by the ADLC front end to build the contents of the case\n"
"// statements (a series of if statements).\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++) {
// Generate the routine header statement for this opcode
// Generate body. Shared for both inline and out-of-line version
// End of routine
}
}
// Iterate over the table of MatchLists, start at first valid opcode of 1
for (i = 1; i < _last_opcode; i++) {
// Generate the case statement for this opcode
if (_dfa_small) {
} else {
// Walk the list, compacting it
}
// Print the "break"
}
// Generate the default case for switch(opcode)
fprintf(fp, " tty->print(\" opcode = %cd, \\\"%cs\\\"\\n\", opcode, NodeClassNames[opcode]);\n", '%', '%');
// Return status, indicating a successful match.
// Generate the closing brace for method Matcher::DFA
Expr::check_buffers();
}
class dfa_shared_preds {
enum { count = 4 };
// Confirm that this is a separate sub-expression.
// Only need to catch common cases like " ... && shared ..."
// and avoid hazardous ones like "...->shared"
// start of predicate is valid
// Check previous character and recurse if needed
char c = *prev;
switch( c ) {
case ' ':
case '\n':
case '!':
case '(':
case '<':
case '=':
return true;
case '"': // such as: #line 10 "myfile.ad"\n mypredicate
return true;
case '|':
case '&':
default:
return false;
}
return false;
}
public:
static void reset_found() {
};
// Check each predicate in the MatchList for common sub-expressions
}
}
}
}
// 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;
// Do not modify the original predicate string, it is shared
}
// Replace shared_pred with variable name
}
// Install new predicate
result = true;
}
}
return result;
}
// Output the hoisted common sub-expression if we found it in predicates
for(int j = 0; j < count; ++j ) {
if( dfa_shared_preds::found(j) ) {
}
}
}
};
// shared predicates, _var and _pred entry should be the same length
= { false, false, false, false };
= { "int", "jlong", "intptr_t", "bool" };
= { "_n_get_int__", "_n_get_long__", "_n_get_intptr_t__", "Compile__current____select_24_bit_instr__" };
= { "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
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.
// Iterate
// Hoist previously specified common sub-expressions out of predicates
// Walk the list again, generating code
do {
// Each match can generate its own chains
// Fill in any chain rules which add instructions
// These can generate their own chains as well.
if( debug_output1 ) { fprintf(fp, "// top level chain rules for: %s \n", (char *)NodeClassNames[i]); } // %%%%% Explanation
}
//------------------------------Expr------------------------------------------
_expr = "Invalid_Expr";
}
int intval = 0;
_expr = "0";
}
_min_value = intval;
_max_value = intval;
}
else {
}
}
}
return cost;
}
// 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);
}
}
if( e != NULL ) {
// use the value of 'c' defined in <arch>.ad
add(e);
} else {
}
}
// Preserve use of external name which has a zero value
}
}
} else {
string_buffer[0] = '\0';
}
}
return result;
}
}
}
}
else {
}
return cost;
}
return result;
}
if( result < 0 ) { // check for overflow
}
return result;
}
if( _external_name != NULL ) {
} else {
}
}
}
fprintf(fp, " assert( %s == %d, \"Expect (%s) to equal %d\");\n", _external_name, _min_value, _expr, _min_value);
}
}
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;
ok = false;
assert( false, "Expr:: Buffer overflow");
}
}
return ok;
}
//------------------------------ExprDict---------------------------------------
// Constructor
}
}
// Return # of name-Expr pairs in dict
}
// define inserts the given key-value pair into the dictionary,
// and records the name in order for later output, ...
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.
}
// Finds the value of a given key; or NULL if not found.
// The dictionary is NOT changed.
}
}
}
}
}
// Print out the dictionary contents as key-value pairs
}
//------------------------------ExprDict::private------------------------------
// Disable public use of constructor, copy-ctor, operator =, operator ==
assert( false, "NotImplemented");
}
assert( false, "NotImplemented");
}
assert( false, "NotImplemented");
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.
assert( false, "NotImplemented");
return false;
}
//------------------------------Production-------------------------------------
initialize();
}
void Production::initialize() {
_constraint = NULL;
}
void Production::print() {
}
//------------------------------ProductionState--------------------------------
void ProductionState::initialize() {
// reset each Production currently in the dictionary
const void *x, *y = NULL;
Production *p = (Production*)y;
if( p != NULL ) {
p->initialize();
}
}
}
if( p == NULL ) {
}
return p;
}
}
}
// Update valid as allowed by current constraints
if( _constraint == noConstraint ) {
p->_valid = knownValid;
} else {
if( p->_valid != knownValid ) {
p->_valid = unknownValid;
}
}
}
}
}
void ProductionState::set_cost_bounds(const char *result, const Expr *cost, bool has_state_check, bool has_cost_check) {
if( p->_valid == knownInvalid ) {
// Our cost bounds are not unknown, just not defined.
// The production is protected by a condition, so
// the cost bounds may expand.
// _cost_lb = min(cost, _cost_lb)
}
// _cost_ub = max(cost, _cost_ub)
}
} else if (has_cost_check) {
// The production has no condition check, but does
// have a cost check that could reduce the upper
// _cost_lb = min(cost, _cost_lb)
}
// _cost_ub = min(cost, _cost_ub)
}
} else {
// The costs are unconditionally set.
}
}
// Print out the dictionary contents as key-value pairs
static void print_production(const void* production) { fflush(stdout); ((Production*)production)->print(); }
void ProductionState::print() {
}