1879N/A * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 0N/A * published by the Free Software Foundation. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1472N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 0N/A// DFA.CPP - Method definitions for outputting the matcher DFA from ADLC 0N/A//---------------------------Switches for debugging output--------------------- 0N/A//---------------------------Access to internals of class State---------------- 0N/A//---------------------------DFA productions----------------------------------- 0N/A//---------------------------Production State---------------------------------- 0N/Astatic const char *
knownInvalid =
"knownInvalid";
// The result does NOT have a rule defined 0N/Astatic const char *
knownValid =
"knownValid";
// The result must be produced by a rule 0N/Astatic const char *
unknownValid =
"unknownValid";
// Unknown (probably due to a child or predicate constraint) 0N/Astatic const char *
noConstraint =
"noConstraint";
// No constraints seen so far 0N/Astatic const char *
hasConstraint =
"hasConstraint";
// Within the first constraint 0N/A//------------------------------Production------------------------------------ 0N/A// Track the status of productions for a particular result 0N/A//------------------------------ProductionState-------------------------------- 0N/A// Track the status of all production rule results 0N/A// Reset for each root opcode (e.g., Op_RegI, Op_AddI, ...) 0N/A // cmpstr does string comparisions. hashstr computes a key. 0N/A const char *
valid(
const char *
result);
// unknownValid, or status for this production 0N/A // Return the Production associated with the result, 0N/A // or create a new Production and insert it into the dictionary. 0N/A // Disable public use of constructor, copy-ctor, ... 0N/A//---------------------------Helper Functions---------------------------------- 0N/A// cost_check template: 0N/A// 1) if (STATE__NOT_YET_VALID(EBXREGI) || _cost[EBXREGI] > c) { 0N/A// 2) DFA_PRODUCTION__SET_VALID(EBXREGI, cmovI_memu_rule, c) 0N/A bool state_check =
false;
// true if this production needs to check validity 0N/A bool cost_check =
false;
// true if this production needs to check cost 0N/A // Get information about this production 0N/A // Check for validity and compare to other match costs 0N/A // production cost is known to be too high. 0N/A // production will unconditionally overwrite a previous production that had higher cost 0N/A // no need to set State vector if our state is knownValid 0N/A // Update ProductionState 0N/A // set State vector if not previously known 0N/A//---------------------------child_test---------------------------------------- 0N/A// STATE__VALID_CHILD(_kids[0], FOO) && STATE__VALID_CHILD(_kids[1], BAR) 0N/A// Macro equivalent to: _kids[0]->valid(FOO) && _kids[1]->valid(BAR) 0N/A//---------------------------calc_cost----------------------------------------- 0N/A// unsigned int c = _kids[0]->_cost[FOO] + _kids[1]->_cost[BAR] + 5; 0N/A // Add in cost of this rule 0N/A//---------------------------gen_match----------------------------------------- 0N/A // Only generate child tests if this is not a leaf node 0N/A // Open the child-and-predicate-test braces 0N/A // Only generate predicate test if one exists for this match 0N/A // End of outer tests 0N/A // No child or predicate test needed 0N/A // End of outer tests 0N/A // Calculate cost of this match 0N/A // Check against other match costs, and update cost & rule vectors 0N/A // If this is a member of an operand class, update the class cost & rule 0N/A // Check if this rule should be used to generate the chains as well. 0N/A const char *
rule =
/* set rule to "Invalid" for internal operands */ 0N/A // If this rule produces an operand which has associated chain rules, 0N/A // update the operands with the chain rule + this rule cost & this rule. 0N/A // Close the child-and-predicate-test braces 0N/A//---------------------------expand_opclass------------------------------------ 0N/A// Chain from one result_type to all other members of its operand class 0N/A // Iterate through all operand classes which include this operand 0N/A // Expr *cCost = new Expr(cost); 0N/A // Check against other match costs, and update cost & rule vectors 0N/A//---------------------------chain_rule---------------------------------------- 0N/A// Starting at 'operand', check if we know how to automatically generate other results 0N/A // Check if we have already generated chains from this starting point 0N/A // printf("\nChain from <%s> at cost #%s\n",operand, icost ? icost : "_"); 0N/A // Do not generate operands that are already available 0N/A // Compute the cost for previous match + chain_rule_cost 0N/A // total_cost = icost + cost; 0N/A // Check for transitive chain rules 0N/A // printf(" result=%s cost=%s rule=%s\n", result, total_cost, rule); 0N/A // Check against other match costs, and update cost & rule vectors 0N/A // printf(" result=%s cost=%s rule=%s\n", result, total_cost, rule); 0N/A // Check against other match costs, and update cost & rule vectors 0N/A // If this is a member of an operand class, update class cost & rule 0N/A//---------------------------prune_matchlist----------------------------------- 0N/A// Check for duplicate entries in a matchlist, and prune out the higher cost 0N/A//---------------------------buildDFA------------------------------------------ 0N/A// DFA is a large switch with case statements for each ideal opcode encountered 0N/A// in any match rule in the ad file. Each case has a series of if's to handle 0N/A// the match or fail decisions. The matches test the cost function of that 0N/A// rule, and prune any cases which are higher cost for the same reduction. 0N/A// pairs generated by the ADLC front end to build the contents of the case 0N/A// statements (a series of if statements). 0N/A // Remember operands that are the starting points for chain rules. 0N/A // Prevent cycles by checking if we have already generated chain. 0N/A // Hash inputs to match rules so that final DFA contains only one entry for 0N/A // each match pattern which is the low cost entry. 0N/A // Track status of dfa for each resulting production 0N/A // reset for each ideal root. 0N/A // Output the start of the DFA method into the output file 0N/A fprintf(
fp,
"//------------------------- Source -----------------------------------------\n");
0N/A // Do not put random source code into the DFA. 0N/A // If there are constants which need sharing, put them in "source_hpp" forms. 0N/A // _source.output(fp); 0N/A fprintf(
fp,
"//------------------------- Attributes -------------------------------------\n");
0N/A fprintf(
fp,
"//------------------------- Macros -----------------------------------------\n");
0N/A // #define DFA_PRODUCTION(result, rule, cost)\ 0N/A // _cost[ (result) ] = cost; _rule[ (result) ] = rule; 0N/A fprintf(
fp,
" _cost[ (result) ] = cost; _rule[ (result) ] = rule;\n");
0N/A // #define DFA_PRODUCTION__SET_VALID(result, rule, cost)\ 0N/A // DFA_PRODUCTION( (result), (rule), (cost) ); STATE__SET_VALID( (result) ); 0N/A fprintf(
fp,
"//------------------------- DFA --------------------------------------------\n");
0N/A"// DFA is a large switch with case statements for each ideal opcode encountered\n" 0N/A"// in any match rule in the ad file. Each case has a series of if's to handle\n" 0N/A"// the match or fail decisions. The matches test the cost function of that\n" 0N/A"// rule, and prune any cases which are higher cost for the same reduction.\n" 0N/A"// pairs generated by the ADLC front end to build the contents of the case\n" 0N/A"// statements (a series of if statements).\n" 0N/A // Now build the individual routines just like the switch entries in large version 0N/A // Iterate over the table of MatchLists, start at first valid opcode of 1 0N/A // Generate the routine header statement for this opcode 0N/A // Generate body. Shared for both inline and out-of-line version 0N/A // Iterate over the table of MatchLists, start at first valid opcode of 1 0N/A // Generate the case statement for this opcode 0N/A // Walk the list, compacting it 0N/A // Print the "break" 0N/A // Generate the default case for switch(opcode) 0N/A fprintf(
fp,
" tty->print(\"Default case invoked for: \\n\");\n");
0N/A fprintf(
fp,
" tty->print(\" opcode = %cd, \\\"%cs\\\"\\n\", opcode, NodeClassNames[opcode]);\n",
'%',
'%');
0N/A // Return status, indicating a successful match. 0N/A // Generate the closing brace for method Matcher::DFA 0N/A // Confirm that this is a separate sub-expression. 0N/A // Only need to catch common cases like " ... && shared ..." 0N/A // and avoid hazardous ones like "...->shared" 0N/A // start of predicate is valid 0N/A // Check previous character and recurse if needed 475N/A case '"':
// such as: #line 10 "myfile.ad"\n mypredicate 0N/A // Check each predicate in the MatchList for common sub-expressions 0N/A // If the Predicate contains a common sub-expression, replace the Predicate's 0N/A // string with one that uses the variable name. 0N/A // Do not modify the original predicate string, it is shared 0N/A // Replace shared_pred with variable name 0N/A // Install new predicate 0N/A // Output the hoisted common sub-expression if we found it in predicates 0N/A// shared predicates, _var and _pred entry should be the same length 475N/A = {
false,
false,
false,
false };
475N/A = {
"int",
"jlong",
"intptr_t",
"bool" };
475N/A = {
"_n_get_int__",
"_n_get_long__",
"_n_get_intptr_t__",
"Compile__current____select_24_bit_instr__" };
475N/A = {
"n->get_int()",
"n->get_long()",
"n->get_intptr_t()",
"Compile::current()->select_24_bit_instr()" };
0N/A // Start the body of each Op_XXX sub-dfa with a clean state. 0N/A // Walk the list, compacting it 0N/A // Hash each entry using inputs as key and pointer as data. 0N/A // If there is already an entry, keep the one with lower cost, and 0N/A // remove the other one from the list. 0N/A // Hoist previously specified common sub-expressions out of predicates 0N/A // Walk the list again, generating code 0N/A // Each match can generate its own chains 0N/A // Fill in any chain rules which add instructions 0N/A // These can generate their own chains as well. 0N/A//------------------------------Expr------------------------------------------ 0N/A // Do not update fields until all computation is complete 0N/A // use the value of 'c' defined in <arch>.ad 0N/A // Preserve use of external name which has a zero value 0N/A // Fill buffers with 0 0N/A // returns 'true' if buffer use may have overflowed 0N/A//------------------------------ExprDict--------------------------------------- 0N/A// Return # of name-Expr pairs in dict 0N/A// define inserts the given key-value pair into the dictionary, 0N/A// and records the name in order for later output, ... 0N/A// Insert inserts the given key-value pair into the dictionary. The prior 0N/A// value of the key is returned; NULL if the key was not previously defined. 0N/A// Finds the value of a given key; or NULL if not found. 0N/A// The dictionary is NOT changed. 0N/A fprintf(
fp,
" // Following assertions generated from definition section\n");
0N/A// Print out the dictionary contents as key-value pairs 0N/A//------------------------------ExprDict::private------------------------------ 0N/A// Disable public use of constructor, copy-ctor, operator =, operator == 0N/A// == compares two dictionaries; they must have the same keys (their keys 0N/A// must match using CmpKey) and they must have the same values (pointer 0N/A// comparison). If so 1 is returned, if not 0 is returned. 0N/A//------------------------------Production------------------------------------- 0N/A//------------------------------ProductionState-------------------------------- 0N/A // reset each Production currently in the dictionary 0N/A // Update valid as allowed by current constraints 0N/A // Our cost bounds are not unknown, just not defined. 0N/A // The production is protected by a condition, so 0N/A // the cost bounds may expand. 0N/A // _cost_lb = min(cost, _cost_lb) 0N/A // _cost_ub = max(cost, _cost_ub) 0N/A // The production has no condition check, but does 0N/A // have a cost check that could reduce the upper 0N/A // _cost_lb = min(cost, _cost_lb) 0N/A // _cost_ub = min(cost, _cost_ub) 0N/A // The costs are unconditionally set. 0N/A// Print out the dictionary contents as key-value pairs