dfa.cpp revision 5776:de6a9e811145
11541Srgrimes/* 21541Srgrimes * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. 31541Srgrimes * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 41541Srgrimes * 51541Srgrimes * This code is free software; you can redistribute it and/or modify it 61541Srgrimes * under the terms of the GNU General Public License version 2 only, as 71541Srgrimes * published by the Free Software Foundation. 81541Srgrimes * 91541Srgrimes * This code is distributed in the hope that it will be useful, but WITHOUT 101541Srgrimes * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 111541Srgrimes * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 121541Srgrimes * version 2 for more details (a copy is included in the LICENSE file that 131541Srgrimes * accompanied this code). 1458705Scharnier * 151541Srgrimes * You should have received a copy of the GNU General Public License version 161541Srgrimes * 2 along with this work; if not, write to the Free Software Foundation, 171541Srgrimes * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 181541Srgrimes * 191541Srgrimes * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 201541Srgrimes * or visit www.oracle.com if you need additional information or have any 211541Srgrimes * questions. 221541Srgrimes * 231541Srgrimes */ 241541Srgrimes 251541Srgrimes// DFA.CPP - Method definitions for outputting the matcher DFA from ADLC 261541Srgrimes#include "adlc.hpp" 271541Srgrimes 281541Srgrimes//---------------------------Switches for debugging output--------------------- 291541Srgrimesstatic bool debug_output = false; 301541Srgrimesstatic bool debug_output1 = false; // top level chain rules 311541Srgrimes 321541Srgrimes//---------------------------Access to internals of class State---------------- 331541Srgrimesstatic const char *sLeft = "_kids[0]"; 3450477Speterstatic const char *sRight = "_kids[1]"; 351541Srgrimes 361541Srgrimes//---------------------------DFA productions----------------------------------- 371541Srgrimesstatic const char *dfa_production = "DFA_PRODUCTION"; 381541Srgrimesstatic const char *dfa_production_set_valid = "DFA_PRODUCTION__SET_VALID"; 391541Srgrimes 401541Srgrimes//---------------------------Production State---------------------------------- 4134924Sbdestatic const char *knownInvalid = "knownInvalid"; // The result does NOT have a rule defined 4212662Sdgstatic const char *knownValid = "knownValid"; // The result must be produced by a rule 4312662Sdgstatic const char *unknownValid = "unknownValid"; // Unknown (probably due to a child or predicate constraint) 441541Srgrimes 4540794Speterstatic const char *noConstraint = "noConstraint"; // No constraints seen so far 4612726Sbdestatic const char *hasConstraint = "hasConstraint"; // Within the first constraint 4712662Sdg 4822521Sdyson 4912662Sdg//------------------------------Production------------------------------------ 5012662Sdg// Track the status of productions for a particular result 5112662Sdgclass Production { 521541Srgrimespublic: 531541Srgrimes const char *_result; 5412623Sphk const char *_constraint; 5512623Sphk const char *_valid; 5612623Sphk Expr *_cost_lb; // Cost lower bound for this production 579759Sbde Expr *_cost_ub; // Cost upper bound for this production 581541Srgrimes 5912820Sphkpublic: 601541Srgrimes Production(const char *result, const char *constraint, const char *valid); 611541Srgrimes ~Production() {}; 621541Srgrimes 631541Srgrimes void initialize(); // reset to be an empty container 641541Srgrimes 6512820Sphk const char *valid() const { return _valid; } 661541Srgrimes Expr *cost_lb() const { return (Expr *)_cost_lb; } 671541Srgrimes Expr *cost_ub() const { return (Expr *)_cost_ub; } 681541Srgrimes 691541Srgrimes void print(); 701541Srgrimes}; 711541Srgrimes 721541Srgrimes 731541Srgrimes//------------------------------ProductionState-------------------------------- 741541Srgrimes// Track the status of all production rule results 759507Sdg// Reset for each root opcode (e.g., Op_RegI, Op_AddI, ...) 7612286Sphkclass ProductionState { 771541Srgrimesprivate: 781541Srgrimes Dict _production; // map result of production, char*, to information or NULL 791541Srgrimes const char *_constraint; 801541Srgrimes 8169947Sjakepublic: 8214531Shsu // cmpstr does string comparisions. hashstr computes a key. 831541Srgrimes ProductionState(Arena *arena) : _production(cmpstr, hashstr, arena) { initialize(); }; 841541Srgrimes ~ProductionState() { }; 851541Srgrimes 861541Srgrimes void initialize(); // reset local and dictionary state 8758634Scharnier 881541Srgrimes const char *constraint(); 8965904Sjhb void set_constraint(const char *constraint); // currently working inside of constraints 9065904Sjhb 9165904Sjhb const char *valid(const char *result); // unknownValid, or status for this production 921541Srgrimes void set_valid(const char *result); // if not constrained, set status to knownValid 931541Srgrimes 941541Srgrimes Expr *cost_lb(const char *result); 951541Srgrimes Expr *cost_ub(const char *result); 9669947Sjake void set_cost_bounds(const char *result, const Expr *cost, bool has_state_check, bool has_cost_check); 971541Srgrimes 981541Srgrimes // Return the Production associated with the result, 995455Sdg // or create a new Production and insert it into the dictionary. 1001541Srgrimes Production *getProduction(const char *result); 1011541Srgrimes 1029507Sdg void print(); 1039507Sdg 1049507Sdgprivate: 1059507Sdg // Disable public use of constructor, copy-ctor, ... 10634961Sphk ProductionState( ) : _production(cmpstr, hashstr, Form::arena) { assert( false, "NotImplemented"); }; 1079507Sdg ProductionState( const ProductionState & ) : _production(cmpstr, hashstr, Form::arena) { assert( false, "NotImplemented"); }; // Deep-copy 1089507Sdg}; 1099507Sdg 1109507Sdg 1119507Sdg//---------------------------Helper Functions---------------------------------- 11262622Sjhb// cost_check template: 11312286Sphk// 1) if (STATE__NOT_YET_VALID(EBXREGI) || _cost[EBXREGI] > c) { 11462622Sjhb// 2) DFA_PRODUCTION__SET_VALID(EBXREGI, cmovI_memu_rule, c) 11512286Sphk// 3) } 11662622Sjhb// 11712286Sphkstatic void cost_check(FILE *fp, const char *spaces, 11862622Sjhb const char *arrayIdx, const Expr *cost, const char *rule, ProductionState &status) { 11912286Sphk bool state_check = false; // true if this production needs to check validity 12062622Sjhb bool cost_check = false; // true if this production needs to check cost 12112286Sphk bool cost_is_above_upper_bound = false; // true if this production is unnecessary due to high cost 12262622Sjhb bool cost_is_below_lower_bound = false; // true if this production replaces a higher cost production 12312286Sphk 12462622Sjhb // Get information about this production 12512286Sphk const Expr *previous_ub = status.cost_ub(arrayIdx); 12662622Sjhb if( !previous_ub->is_unknown() ) { 12751337Sdillon if( previous_ub->less_than_or_equal(cost) ) { 12812286Sphk cost_is_above_upper_bound = true; 12946381Sbillf if( debug_output ) { fprintf(fp, "// Previous rule with lower cost than: %s === %s_rule costs %s\n", arrayIdx, rule, cost->as_string()); } 13046381Sbillf } 1311541Srgrimes } 13212286Sphk 13362573Sphk const Expr *previous_lb = status.cost_lb(arrayIdx); 1341541Srgrimes if( !previous_lb->is_unknown() ) { 13512286Sphk if( cost->less_than_or_equal(previous_lb) ) { 13612286Sphk cost_is_below_lower_bound = true; 13712286Sphk if( debug_output ) { fprintf(fp, "// Previous rule with higher cost\n"); } 13812286Sphk } 13912286Sphk } 1401541Srgrimes 1411541Srgrimes // line 1) 14212286Sphk // Check for validity and compare to other match costs 1431541Srgrimes const char *validity_check = status.valid(arrayIdx); 1441541Srgrimes if( validity_check == unknownValid ) { 1451541Srgrimes fprintf(fp, "%sif (STATE__NOT_YET_VALID(%s) || _cost[%s] > %s) {\n", spaces, arrayIdx, arrayIdx, cost->as_string()); 1461541Srgrimes state_check = true; 14715809Sdyson cost_check = true; 1485455Sdg } 14915809Sdyson else if( validity_check == knownInvalid ) { 15038517Sdfr if( debug_output ) { fprintf(fp, "%s// %s KNOWN_INVALID \n", spaces, arrayIdx); } 1511541Srgrimes } 1521541Srgrimes else if( validity_check == knownValid ) { 1531541Srgrimes if( cost_is_above_upper_bound ) { 15469947Sjake // production cost is known to be too high. 15514531Shsu return; 1561541Srgrimes } else if( cost_is_below_lower_bound ) { 1571541Srgrimes // production will unconditionally overwrite a previous production that had higher cost 1581541Srgrimes } else { 1591541Srgrimes fprintf(fp, "%sif ( /* %s KNOWN_VALID || */ _cost[%s] > %s) {\n", spaces, arrayIdx, arrayIdx, cost->as_string()); 1601541Srgrimes cost_check = true; 1611541Srgrimes } 16265557Sjasone } 1631541Srgrimes 1641541Srgrimes // line 2) 1651541Srgrimes // no need to set State vector if our state is knownValid 1661541Srgrimes const char *production = (validity_check == knownValid) ? dfa_production : dfa_production_set_valid; 1671541Srgrimes fprintf(fp, "%s %s(%s, %s_rule, %s)", spaces, production, arrayIdx, rule, cost->as_string() ); 1681541Srgrimes if( validity_check == knownValid ) { 1691541Srgrimes if( cost_is_below_lower_bound ) { fprintf(fp, "\t // overwrites higher cost rule"); } 1701541Srgrimes } 1711541Srgrimes fprintf(fp, "\n"); 1721541Srgrimes 1731541Srgrimes // line 3) 1741541Srgrimes if( cost_check || state_check ) { 1751541Srgrimes fprintf(fp, "%s}\n", spaces); 17665557Sjasone } 17765557Sjasone 17865557Sjasone status.set_cost_bounds(arrayIdx, cost, state_check, cost_check); 17965557Sjasone 1801541Srgrimes // Update ProductionState 1811541Srgrimes if( validity_check != knownValid ) { 1821541Srgrimes // set State vector if not previously known 1831541Srgrimes status.set_valid(arrayIdx); 1841541Srgrimes } 1851541Srgrimes} 1861541Srgrimes 1871541Srgrimes 1881541Srgrimes//---------------------------child_test---------------------------------------- 1891541Srgrimes// Example: 1901541Srgrimes// STATE__VALID_CHILD(_kids[0], FOO) && STATE__VALID_CHILD(_kids[1], BAR) 1911541Srgrimes// Macro equivalent to: _kids[0]->valid(FOO) && _kids[1]->valid(BAR) 1921541Srgrimes// 1931541Srgrimesstatic void child_test(FILE *fp, MatchList &mList) { 1941541Srgrimes if (mList._lchild) { // If left child, check it 1955455Sdg const char* lchild_to_upper = ArchDesc::getMachOperEnum(mList._lchild); 19643748Sdillon fprintf(fp, "STATE__VALID_CHILD(_kids[0], %s)", lchild_to_upper); 1971541Srgrimes delete[] lchild_to_upper; 1981541Srgrimes } 19938517Sdfr if (mList._lchild && mList._rchild) { // If both, add the "&&" 2001541Srgrimes fprintf(fp, " && "); 2011541Srgrimes } 2021541Srgrimes if (mList._rchild) { // If right child, check it 2031541Srgrimes const char* rchild_to_upper = ArchDesc::getMachOperEnum(mList._rchild); 2041541Srgrimes fprintf(fp, "STATE__VALID_CHILD(_kids[1], %s)", rchild_to_upper); 20569947Sjake delete[] rchild_to_upper; 2061541Srgrimes } 2071541Srgrimes} 2081541Srgrimes 20915809Sdyson//---------------------------calc_cost----------------------------------------- 2105455Sdg// Example: 21115809Sdyson// unsigned int c = _kids[0]->_cost[FOO] + _kids[1]->_cost[BAR] + 5; 21242957Sdillon// 21342957SdillonExpr *ArchDesc::calc_cost(FILE *fp, const char *spaces, MatchList &mList, ProductionState &status) { 21442957Sdillon fprintf(fp, "%sunsigned int c = ", spaces); 21542957Sdillon Expr *c = new Expr("0"); 21642957Sdillon if (mList._lchild) { // If left child, add it in 21718169Sdyson const char* lchild_to_upper = ArchDesc::getMachOperEnum(mList._lchild); 2181541Srgrimes sprintf(Expr::buffer(), "_kids[0]->_cost[%s]", lchild_to_upper); 2191541Srgrimes c->add(Expr::buffer()); 22018169Sdyson delete[] lchild_to_upper; 2211541Srgrimes} 2221541Srgrimes if (mList._rchild) { // If right child, add it in 22318169Sdyson const char* rchild_to_upper = ArchDesc::getMachOperEnum(mList._rchild); 2241541Srgrimes sprintf(Expr::buffer(), "_kids[1]->_cost[%s]", rchild_to_upper); 22518169Sdyson c->add(Expr::buffer()); 2261541Srgrimes delete[] rchild_to_upper; 2271541Srgrimes } 22818169Sdyson // Add in cost of this rule 2291541Srgrimes const char *mList_cost = mList.get_cost(); 2301541Srgrimes c->add(mList_cost, *this); 2311541Srgrimes 2321541Srgrimes fprintf(fp, "%s;\n", c->as_string()); 2335455Sdg c->set_external_name("c"); 23412286Sphk return c; 2351541Srgrimes} 23612286Sphk 23712286Sphk 23846381Sbillf//---------------------------gen_match----------------------------------------- 23946381Sbillfvoid ArchDesc::gen_match(FILE *fp, MatchList &mList, ProductionState &status, Dict &operands_chained_from) { 24040794Speter const char *spaces4 = " "; 24140794Speter const char *spaces6 = " "; 24240794Speter 24340794Speter fprintf(fp, "%s", spaces4); 24462622Sjhb // Only generate child tests if this is not a leaf node 24540794Speter bool has_child_constraints = mList._lchild || mList._rchild; 24662622Sjhb const char *predicate_test = mList.get_pred(); 24740794Speter if (has_child_constraints || predicate_test) { 24862622Sjhb // Open the child-and-predicate-test braces 24940794Speter fprintf(fp, "if( "); 25062622Sjhb status.set_constraint(hasConstraint); 25146381Sbillf child_test(fp, mList); 25262622Sjhb // Only generate predicate test if one exists for this match 25346381Sbillf if (predicate_test) { 25462622Sjhb if (has_child_constraints) { 25540794Speter fprintf(fp," &&\n"); 25662622Sjhb } 25740794Speter fprintf(fp, "%s %s", spaces6, predicate_test); 25862622Sjhb } 25940794Speter // End of outer tests 26062622Sjhb fprintf(fp," ) "); 26140794Speter } else { 26262622Sjhb // No child or predicate test needed 26340794Speter status.set_constraint(noConstraint); 26462622Sjhb } 26540794Speter 26662622Sjhb // End of outer tests 26740794Speter fprintf(fp,"{\n"); 26862622Sjhb 26940794Speter // Calculate cost of this match 27062622Sjhb const Expr *cost = calc_cost(fp, spaces6, mList, status); 27140794Speter // Check against other match costs, and update cost & rule vectors 27262622Sjhb cost_check(fp, spaces6, ArchDesc::getMachOperEnum(mList._resultStr), cost, mList._opcode, status); 27340794Speter 27462622Sjhb // If this is a member of an operand class, update the class cost & rule 27540794Speter expand_opclass( fp, spaces6, cost, mList._resultStr, status); 27662622Sjhb 27740794Speter // Check if this rule should be used to generate the chains as well. 27862622Sjhb const char *rule = /* set rule to "Invalid" for internal operands */ 27940794Speter strcmp(mList._opcode,mList._resultStr) ? mList._opcode : "Invalid"; 28062622Sjhb 28140794Speter // If this rule produces an operand which has associated chain rules, 28262622Sjhb // update the operands with the chain rule + this rule cost & this rule. 28340794Speter chain_rule(fp, spaces6, mList._resultStr, cost, rule, operands_chained_from, status); 28462622Sjhb 28540794Speter // Close the child-and-predicate-test braces 28662622Sjhb fprintf(fp, " }\n"); 28740794Speter 28862622Sjhb} 28940794Speter 29062622Sjhb 29140794Speter//---------------------------expand_opclass------------------------------------ 29262622Sjhb// Chain from one result_type to all other members of its operand class 29340794Spetervoid ArchDesc::expand_opclass(FILE *fp, const char *indent, const Expr *cost, 29462622Sjhb const char *result_type, ProductionState &status) { 29540794Speter const Form *form = _globalNames[result_type]; 29662622Sjhb OperandForm *op = form ? form->is_operand() : NULL; 29740794Speter if( op && op->_classes.count() > 0 ) { 29862622Sjhb if( debug_output ) { fprintf(fp, "// expand operand classes for operand: %s \n", (char *)op->_ident ); } // %%%%% Explanation 29940794Speter // Iterate through all operand classes which include this operand 30062622Sjhb op->_classes.reset(); 30140794Speter const char *oclass; 30262622Sjhb // Expr *cCost = new Expr(cost); 30340794Speter while( (oclass = op->_classes.iter()) != NULL ) 30462622Sjhb // Check against other match costs, and update cost & rule vectors 30540794Speter cost_check(fp, indent, ArchDesc::getMachOperEnum(oclass), cost, result_type, status); 30662622Sjhb } 30740794Speter} 30862622Sjhb 30940794Speter//---------------------------chain_rule---------------------------------------- 31062622Sjhb// Starting at 'operand', check if we know how to automatically generate other results 31140794Spetervoid ArchDesc::chain_rule(FILE *fp, const char *indent, const char *operand, 31262622Sjhb const Expr *icost, const char *irule, Dict &operands_chained_from, ProductionState &status) { 31340794Speter 31462622Sjhb // Check if we have already generated chains from this starting point 31540794Speter if( operands_chained_from[operand] != NULL ) { 31662622Sjhb return; 31740794Speter } else { 31862622Sjhb operands_chained_from.Insert( operand, operand); 31940794Speter } 32062622Sjhb if( debug_output ) { fprintf(fp, "// chain rules starting from: %s and %s \n", (char *)operand, (char *)irule); } // %%%%% Explanation 32140794Speter 32262622Sjhb ChainList *lst = (ChainList *)_chainRules[operand]; 32340794Speter if (lst) { 32440794Speter // printf("\nChain from <%s> at cost #%s\n",operand, icost ? icost : "_"); 32540794Speter const char *result, *cost, *rule; 32671429Sume for(lst->reset(); (lst->iter(result,cost,rule)) == true; ) { 32771429Sume // Do not generate operands that are already available 32871429Sume if( operands_chained_from[result] != NULL ) { 32971429Sume continue; 33071429Sume } else { 33171429Sume // Compute the cost for previous match + chain_rule_cost 33271429Sume // total_cost = icost + cost; 33371429Sume Expr *total_cost = icost->clone(); // icost + cost 33471429Sume total_cost->add(cost, *this); 33571429Sume 33671429Sume // Check for transitive chain rules 33771429Sume Form *form = (Form *)_globalNames[rule]; 33871429Sume if ( ! form->is_instruction()) { 33971429Sume // printf(" result=%s cost=%s rule=%s\n", result, total_cost, rule); 34071429Sume // Check against other match costs, and update cost & rule vectors 34171429Sume const char *reduce_rule = strcmp(irule,"Invalid") ? irule : rule; 34240794Speter cost_check(fp, indent, ArchDesc::getMachOperEnum(result), total_cost, reduce_rule, status); 34340794Speter chain_rule(fp, indent, result, total_cost, irule, operands_chained_from, status); 34440794Speter } else { 34540794Speter // printf(" result=%s cost=%s rule=%s\n", result, total_cost, rule); 34640794Speter // Check against other match costs, and update cost & rule vectors 34740794Speter cost_check(fp, indent, ArchDesc::getMachOperEnum(result), total_cost, rule, status); 34840794Speter chain_rule(fp, indent, result, total_cost, rule, operands_chained_from, status); 34940794Speter } 35040794Speter 35140794Speter // If this is a member of an operand class, update class cost & rule 35240794Speter expand_opclass( fp, indent, total_cost, result, status ); 35340794Speter } 35440794Speter } 35540794Speter } 356} 357 358//---------------------------prune_matchlist----------------------------------- 359// Check for duplicate entries in a matchlist, and prune out the higher cost 360// entry. 361void ArchDesc::prune_matchlist(Dict &minimize, MatchList &mlist) { 362 363} 364 365//---------------------------buildDFA------------------------------------------ 366// DFA is a large switch with case statements for each ideal opcode encountered 367// in any match rule in the ad file. Each case has a series of if's to handle 368// the match or fail decisions. The matches test the cost function of that 369// rule, and prune any cases which are higher cost for the same reduction. 370// In order to generate the DFA we walk the table of ideal opcode/MatchList 371// pairs generated by the ADLC front end to build the contents of the case 372// statements (a series of if statements). 373void ArchDesc::buildDFA(FILE* fp) { 374 int i; 375 // Remember operands that are the starting points for chain rules. 376 // Prevent cycles by checking if we have already generated chain. 377 Dict operands_chained_from(cmpstr, hashstr, Form::arena); 378 379 // Hash inputs to match rules so that final DFA contains only one entry for 380 // each match pattern which is the low cost entry. 381 Dict minimize(cmpstr, hashstr, Form::arena); 382 383 // Track status of dfa for each resulting production 384 // reset for each ideal root. 385 ProductionState status(Form::arena); 386 387 // Output the start of the DFA method into the output file 388 389 fprintf(fp, "\n"); 390 fprintf(fp, "//------------------------- Source -----------------------------------------\n"); 391 // Do not put random source code into the DFA. 392 // If there are constants which need sharing, put them in "source_hpp" forms. 393 // _source.output(fp); 394 fprintf(fp, "\n"); 395 fprintf(fp, "//------------------------- Attributes -------------------------------------\n"); 396 _attributes.output(fp); 397 fprintf(fp, "\n"); 398 fprintf(fp, "//------------------------- Macros -----------------------------------------\n"); 399 // #define DFA_PRODUCTION(result, rule, cost)\ 400 // _cost[ (result) ] = cost; _rule[ (result) ] = rule; 401 fprintf(fp, "#define %s(result, rule, cost)\\\n", dfa_production); 402 fprintf(fp, " _cost[ (result) ] = cost; _rule[ (result) ] = rule;\n"); 403 fprintf(fp, "\n"); 404 405 // #define DFA_PRODUCTION__SET_VALID(result, rule, cost)\ 406 // DFA_PRODUCTION( (result), (rule), (cost) ); STATE__SET_VALID( (result) ); 407 fprintf(fp, "#define %s(result, rule, cost)\\\n", dfa_production_set_valid); 408 fprintf(fp, " %s( (result), (rule), (cost) ); STATE__SET_VALID( (result) );\n", dfa_production); 409 fprintf(fp, "\n"); 410 411 fprintf(fp, "//------------------------- DFA --------------------------------------------\n"); 412 413 fprintf(fp, 414"// DFA is a large switch with case statements for each ideal opcode encountered\n" 415"// in any match rule in the ad file. Each case has a series of if's to handle\n" 416"// the match or fail decisions. The matches test the cost function of that\n" 417"// rule, and prune any cases which are higher cost for the same reduction.\n" 418"// In order to generate the DFA we walk the table of ideal opcode/MatchList\n" 419"// pairs generated by the ADLC front end to build the contents of the case\n" 420"// statements (a series of if statements).\n" 421); 422 fprintf(fp, "\n"); 423 fprintf(fp, "\n"); 424 if (_dfa_small) { 425 // Now build the individual routines just like the switch entries in large version 426 // Iterate over the table of MatchLists, start at first valid opcode of 1 427 for (i = 1; i < _last_opcode; i++) { 428 if (_mlistab[i] == NULL) continue; 429 // Generate the routine header statement for this opcode 430 fprintf(fp, "void State::_sub_Op_%s(const Node *n){\n", NodeClassNames[i]); 431 // Generate body. Shared for both inline and out-of-line version 432 gen_dfa_state_body(fp, minimize, status, operands_chained_from, i); 433 // End of routine 434 fprintf(fp, "}\n"); 435 } 436 } 437 fprintf(fp, "bool State::DFA"); 438 fprintf(fp, "(int opcode, const Node *n) {\n"); 439 fprintf(fp, " switch(opcode) {\n"); 440 441 // Iterate over the table of MatchLists, start at first valid opcode of 1 442 for (i = 1; i < _last_opcode; i++) { 443 if (_mlistab[i] == NULL) continue; 444 // Generate the case statement for this opcode 445 if (_dfa_small) { 446 fprintf(fp, " case Op_%s: { _sub_Op_%s(n);\n", NodeClassNames[i], NodeClassNames[i]); 447 } else { 448 fprintf(fp, " case Op_%s: {\n", NodeClassNames[i]); 449 // Walk the list, compacting it 450 gen_dfa_state_body(fp, minimize, status, operands_chained_from, i); 451 } 452 // Print the "break" 453 fprintf(fp, " break;\n"); 454 fprintf(fp, " }\n"); 455 } 456 457 // Generate the default case for switch(opcode) 458 fprintf(fp, " \n"); 459 fprintf(fp, " default:\n"); 460 fprintf(fp, " tty->print(\"Default case invoked for: \\n\");\n"); 461 fprintf(fp, " tty->print(\" opcode = %cd, \\\"%cs\\\"\\n\", opcode, NodeClassNames[opcode]);\n", '%', '%'); 462 fprintf(fp, " return false;\n"); 463 fprintf(fp, " }\n"); 464 465 // Return status, indicating a successful match. 466 fprintf(fp, " return true;\n"); 467 // Generate the closing brace for method Matcher::DFA 468 fprintf(fp, "}\n"); 469 Expr::check_buffers(); 470} 471 472 473class dfa_shared_preds { 474 enum { count = 4 }; 475 476 static bool _found[count]; 477 static const char* _type [count]; 478 static const char* _var [count]; 479 static const char* _pred [count]; 480 481 static void check_index(int index) { assert( 0 <= index && index < count, "Invalid index"); } 482 483 // Confirm that this is a separate sub-expression. 484 // Only need to catch common cases like " ... && shared ..." 485 // and avoid hazardous ones like "...->shared" 486 static bool valid_loc(char *pred, char *shared) { 487 // start of predicate is valid 488 if( shared == pred ) return true; 489 490 // Check previous character and recurse if needed 491 char *prev = shared - 1; 492 char c = *prev; 493 switch( c ) { 494 case ' ': 495 case '\n': 496 return dfa_shared_preds::valid_loc(pred, prev); 497 case '!': 498 case '(': 499 case '<': 500 case '=': 501 return true; 502 case '"': // such as: #line 10 "myfile.ad"\n mypredicate 503 return true; 504 case '|': 505 if( prev != pred && *(prev-1) == '|' ) return true; 506 case '&': 507 if( prev != pred && *(prev-1) == '&' ) return true; 508 default: 509 return false; 510 } 511 512 return false; 513 } 514 515public: 516 517 static bool found(int index){ check_index(index); return _found[index]; } 518 static void set_found(int index, bool val) { check_index(index); _found[index] = val; } 519 static void reset_found() { 520 for( int i = 0; i < count; ++i ) { _found[i] = false; } 521 }; 522 523 static const char* type(int index) { check_index(index); return _type[index]; } 524 static const char* var (int index) { check_index(index); return _var [index]; } 525 static const char* pred(int index) { check_index(index); return _pred[index]; } 526 527 // Check each predicate in the MatchList for common sub-expressions 528 static void cse_matchlist(MatchList *matchList) { 529 for( MatchList *mList = matchList; mList != NULL; mList = mList->get_next() ) { 530 Predicate* predicate = mList->get_pred_obj(); 531 char* pred = mList->get_pred(); 532 if( pred != NULL ) { 533 for(int index = 0; index < count; ++index ) { 534 const char *shared_pred = dfa_shared_preds::pred(index); 535 const char *shared_pred_var = dfa_shared_preds::var(index); 536 bool result = dfa_shared_preds::cse_predicate(predicate, shared_pred, shared_pred_var); 537 if( result ) dfa_shared_preds::set_found(index, true); 538 } 539 } 540 } 541 } 542 543 // If the Predicate contains a common sub-expression, replace the Predicate's 544 // string with one that uses the variable name. 545 static bool cse_predicate(Predicate* predicate, const char *shared_pred, const char *shared_pred_var) { 546 bool result = false; 547 char *pred = predicate->_pred; 548 if( pred != NULL ) { 549 char *new_pred = pred; 550 for( char *shared_pred_loc = strstr(new_pred, shared_pred); 551 shared_pred_loc != NULL && dfa_shared_preds::valid_loc(new_pred,shared_pred_loc); 552 shared_pred_loc = strstr(new_pred, shared_pred) ) { 553 // Do not modify the original predicate string, it is shared 554 if( new_pred == pred ) { 555 new_pred = strdup(pred); 556 shared_pred_loc = strstr(new_pred, shared_pred); 557 } 558 // Replace shared_pred with variable name 559 strncpy(shared_pred_loc, shared_pred_var, strlen(shared_pred_var)); 560 } 561 // Install new predicate 562 if( new_pred != pred ) { 563 predicate->_pred = new_pred; 564 result = true; 565 } 566 } 567 return result; 568 } 569 570 // Output the hoisted common sub-expression if we found it in predicates 571 static void generate_cse(FILE *fp) { 572 for(int j = 0; j < count; ++j ) { 573 if( dfa_shared_preds::found(j) ) { 574 const char *shared_pred_type = dfa_shared_preds::type(j); 575 const char *shared_pred_var = dfa_shared_preds::var(j); 576 const char *shared_pred = dfa_shared_preds::pred(j); 577 fprintf(fp, " %s %s = %s;\n", shared_pred_type, shared_pred_var, shared_pred); 578 } 579 } 580 } 581}; 582// shared predicates, _var and _pred entry should be the same length 583bool dfa_shared_preds::_found[dfa_shared_preds::count] 584 = { false, false, false, false }; 585const char* dfa_shared_preds::_type[dfa_shared_preds::count] 586 = { "int", "jlong", "intptr_t", "bool" }; 587const char* dfa_shared_preds::_var [dfa_shared_preds::count] 588 = { "_n_get_int__", "_n_get_long__", "_n_get_intptr_t__", "Compile__current____select_24_bit_instr__" }; 589const char* dfa_shared_preds::_pred[dfa_shared_preds::count] 590 = { "n->get_int()", "n->get_long()", "n->get_intptr_t()", "Compile::current()->select_24_bit_instr()" }; 591 592 593void ArchDesc::gen_dfa_state_body(FILE* fp, Dict &minimize, ProductionState &status, Dict &operands_chained_from, int i) { 594 // Start the body of each Op_XXX sub-dfa with a clean state. 595 status.initialize(); 596 597 // Walk the list, compacting it 598 MatchList* mList = _mlistab[i]; 599 do { 600 // Hash each entry using inputs as key and pointer as data. 601 // If there is already an entry, keep the one with lower cost, and 602 // remove the other one from the list. 603 prune_matchlist(minimize, *mList); 604 // Iterate 605 mList = mList->get_next(); 606 } while(mList != NULL); 607 608 // Hoist previously specified common sub-expressions out of predicates 609 dfa_shared_preds::reset_found(); 610 dfa_shared_preds::cse_matchlist(_mlistab[i]); 611 dfa_shared_preds::generate_cse(fp); 612 613 mList = _mlistab[i]; 614 615 // Walk the list again, generating code 616 do { 617 // Each match can generate its own chains 618 operands_chained_from.Clear(); 619 gen_match(fp, *mList, status, operands_chained_from); 620 mList = mList->get_next(); 621 } while(mList != NULL); 622 // Fill in any chain rules which add instructions 623 // These can generate their own chains as well. 624 operands_chained_from.Clear(); // 625 if( debug_output1 ) { fprintf(fp, "// top level chain rules for: %s \n", (char *)NodeClassNames[i]); } // %%%%% Explanation 626 const Expr *zeroCost = new Expr("0"); 627 chain_rule(fp, " ", (char *)NodeClassNames[i], zeroCost, "Invalid", 628 operands_chained_from, status); 629} 630 631 632 633//------------------------------Expr------------------------------------------ 634Expr *Expr::_unknown_expr = NULL; 635char Expr::string_buffer[STRING_BUFFER_LENGTH]; 636char Expr::external_buffer[STRING_BUFFER_LENGTH]; 637bool Expr::_init_buffers = Expr::init_buffers(); 638 639Expr::Expr() { 640 _external_name = NULL; 641 _expr = "Invalid_Expr"; 642 _min_value = Expr::Max; 643 _max_value = Expr::Zero; 644} 645Expr::Expr(const char *cost) { 646 _external_name = NULL; 647 648 int intval = 0; 649 if( cost == NULL ) { 650 _expr = "0"; 651 _min_value = Expr::Zero; 652 _max_value = Expr::Zero; 653 } 654 else if( ADLParser::is_int_token(cost, intval) ) { 655 _expr = cost; 656 _min_value = intval; 657 _max_value = intval; 658 } 659 else { 660 assert( strcmp(cost,"0") != 0, "Recognize string zero as an int"); 661 _expr = cost; 662 _min_value = Expr::Zero; 663 _max_value = Expr::Max; 664 } 665} 666 667Expr::Expr(const char *name, const char *expression, int min_value, int max_value) { 668 _external_name = name; 669 _expr = expression ? expression : name; 670 _min_value = min_value; 671 _max_value = max_value; 672 assert(_min_value >= 0 && _min_value <= Expr::Max, "value out of range"); 673 assert(_max_value >= 0 && _max_value <= Expr::Max, "value out of range"); 674} 675 676Expr *Expr::clone() const { 677 Expr *cost = new Expr(); 678 cost->_external_name = _external_name; 679 cost->_expr = _expr; 680 cost->_min_value = _min_value; 681 cost->_max_value = _max_value; 682 683 return cost; 684} 685 686void Expr::add(const Expr *c) { 687 // Do not update fields until all computation is complete 688 const char *external = compute_external(this, c); 689 const char *expr = compute_expr(this, c); 690 int min_value = compute_min (this, c); 691 int max_value = compute_max (this, c); 692 693 _external_name = external; 694 _expr = expr; 695 _min_value = min_value; 696 _max_value = max_value; 697} 698 699void Expr::add(const char *c) { 700 Expr *cost = new Expr(c); 701 add(cost); 702} 703 704void Expr::add(const char *c, ArchDesc &AD) { 705 const Expr *e = AD.globalDefs()[c]; 706 if( e != NULL ) { 707 // use the value of 'c' defined in <arch>.ad 708 add(e); 709 } else { 710 Expr *cost = new Expr(c); 711 add(cost); 712 } 713} 714 715const char *Expr::compute_external(const Expr *c1, const Expr *c2) { 716 const char * result = NULL; 717 718 // Preserve use of external name which has a zero value 719 if( c1->_external_name != NULL ) { 720 sprintf( string_buffer, "%s", c1->as_string()); 721 if( !c2->is_zero() ) { 722 strcat( string_buffer, "+"); 723 strcat( string_buffer, c2->as_string()); 724 } 725 result = strdup(string_buffer); 726 } 727 else if( c2->_external_name != NULL ) { 728 if( !c1->is_zero() ) { 729 sprintf( string_buffer, "%s", c1->as_string()); 730 strcat( string_buffer, " + "); 731 } else { 732 string_buffer[0] = '\0'; 733 } 734 strcat( string_buffer, c2->_external_name ); 735 result = strdup(string_buffer); 736 } 737 return result; 738} 739 740const char *Expr::compute_expr(const Expr *c1, const Expr *c2) { 741 if( !c1->is_zero() ) { 742 sprintf( string_buffer, "%s", c1->_expr); 743 if( !c2->is_zero() ) { 744 strcat( string_buffer, "+"); 745 strcat( string_buffer, c2->_expr); 746 } 747 } 748 else if( !c2->is_zero() ) { 749 sprintf( string_buffer, "%s", c2->_expr); 750 } 751 else { 752 sprintf( string_buffer, "0"); 753 } 754 char *cost = strdup(string_buffer); 755 756 return cost; 757} 758 759int Expr::compute_min(const Expr *c1, const Expr *c2) { 760 int result = c1->_min_value + c2->_min_value; 761 assert( result >= 0, "Invalid cost computation"); 762 763 return result; 764} 765 766int Expr::compute_max(const Expr *c1, const Expr *c2) { 767 int result = c1->_max_value + c2->_max_value; 768 if( result < 0 ) { // check for overflow 769 result = Expr::Max; 770 } 771 772 return result; 773} 774 775void Expr::print() const { 776 if( _external_name != NULL ) { 777 printf(" %s == (%s) === [%d, %d]\n", _external_name, _expr, _min_value, _max_value); 778 } else { 779 printf(" %s === [%d, %d]\n", _expr, _min_value, _max_value); 780 } 781} 782 783void Expr::print_define(FILE *fp) const { 784 assert( _external_name != NULL, "definition does not have a name"); 785 assert( _min_value == _max_value, "Expect user definitions to have constant value"); 786 fprintf(fp, "#define %s (%s) \n", _external_name, _expr); 787 fprintf(fp, "// value == %d \n", _min_value); 788} 789 790void Expr::print_assert(FILE *fp) const { 791 assert( _external_name != NULL, "definition does not have a name"); 792 assert( _min_value == _max_value, "Expect user definitions to have constant value"); 793 fprintf(fp, " assert( %s == %d, \"Expect (%s) to equal %d\");\n", _external_name, _min_value, _expr, _min_value); 794} 795 796Expr *Expr::get_unknown() { 797 if( Expr::_unknown_expr == NULL ) { 798 Expr::_unknown_expr = new Expr(); 799 } 800 801 return Expr::_unknown_expr; 802} 803 804bool Expr::init_buffers() { 805 // Fill buffers with 0 806 for( int i = 0; i < STRING_BUFFER_LENGTH; ++i ) { 807 external_buffer[i] = '\0'; 808 string_buffer[i] = '\0'; 809 } 810 811 return true; 812} 813 814bool Expr::check_buffers() { 815 // returns 'true' if buffer use may have overflowed 816 bool ok = true; 817 for( int i = STRING_BUFFER_LENGTH - 100; i < STRING_BUFFER_LENGTH; ++i) { 818 if( external_buffer[i] != '\0' || string_buffer[i] != '\0' ) { 819 ok = false; 820 assert( false, "Expr:: Buffer overflow"); 821 } 822 } 823 824 return ok; 825} 826 827 828//------------------------------ExprDict--------------------------------------- 829// Constructor 830ExprDict::ExprDict( CmpKey cmp, Hash hash, Arena *arena ) 831 : _expr(cmp, hash, arena), _defines() { 832} 833ExprDict::~ExprDict() { 834} 835 836// Return # of name-Expr pairs in dict 837int ExprDict::Size(void) const { 838 return _expr.Size(); 839} 840 841// define inserts the given key-value pair into the dictionary, 842// and records the name in order for later output, ... 843const Expr *ExprDict::define(const char *name, Expr *expr) { 844 const Expr *old_expr = (*this)[name]; 845 assert(old_expr == NULL, "Implementation does not support redefinition"); 846 847 _expr.Insert(name, expr); 848 _defines.addName(name); 849 850 return old_expr; 851} 852 853// Insert inserts the given key-value pair into the dictionary. The prior 854// value of the key is returned; NULL if the key was not previously defined. 855const Expr *ExprDict::Insert(const char *name, Expr *expr) { 856 return (Expr*)_expr.Insert((void*)name, (void*)expr); 857} 858 859// Finds the value of a given key; or NULL if not found. 860// The dictionary is NOT changed. 861const Expr *ExprDict::operator [](const char *name) const { 862 return (Expr*)_expr[name]; 863} 864 865void ExprDict::print_defines(FILE *fp) { 866 fprintf(fp, "\n"); 867 const char *name = NULL; 868 for( _defines.reset(); (name = _defines.iter()) != NULL; ) { 869 const Expr *expr = (const Expr*)_expr[name]; 870 assert( expr != NULL, "name in ExprDict without matching Expr in dictionary"); 871 expr->print_define(fp); 872 } 873} 874void ExprDict::print_asserts(FILE *fp) { 875 fprintf(fp, "\n"); 876 fprintf(fp, " // Following assertions generated from definition section\n"); 877 const char *name = NULL; 878 for( _defines.reset(); (name = _defines.iter()) != NULL; ) { 879 const Expr *expr = (const Expr*)_expr[name]; 880 assert( expr != NULL, "name in ExprDict without matching Expr in dictionary"); 881 expr->print_assert(fp); 882 } 883} 884 885// Print out the dictionary contents as key-value pairs 886static void dumpekey(const void* key) { fprintf(stdout, "%s", (char*) key); } 887static void dumpexpr(const void* expr) { fflush(stdout); ((Expr*)expr)->print(); } 888 889void ExprDict::dump() { 890 _expr.print(dumpekey, dumpexpr); 891} 892 893 894//------------------------------ExprDict::private------------------------------ 895// Disable public use of constructor, copy-ctor, operator =, operator == 896ExprDict::ExprDict( ) : _expr(cmpkey,hashkey), _defines() { 897 assert( false, "NotImplemented"); 898} 899ExprDict::ExprDict( const ExprDict & ) : _expr(cmpkey,hashkey), _defines() { 900 assert( false, "NotImplemented"); 901} 902ExprDict &ExprDict::operator =( const ExprDict &rhs) { 903 assert( false, "NotImplemented"); 904 _expr = rhs._expr; 905 return *this; 906} 907// == compares two dictionaries; they must have the same keys (their keys 908// must match using CmpKey) and they must have the same values (pointer 909// comparison). If so 1 is returned, if not 0 is returned. 910bool ExprDict::operator ==(const ExprDict &d) const { 911 assert( false, "NotImplemented"); 912 return false; 913} 914 915 916//------------------------------Production------------------------------------- 917Production::Production(const char *result, const char *constraint, const char *valid) { 918 initialize(); 919 _result = result; 920 _constraint = constraint; 921 _valid = valid; 922} 923 924void Production::initialize() { 925 _result = NULL; 926 _constraint = NULL; 927 _valid = knownInvalid; 928 _cost_lb = Expr::get_unknown(); 929 _cost_ub = Expr::get_unknown(); 930} 931 932void Production::print() { 933 printf("%s", (_result == NULL ? "NULL" : _result ) ); 934 printf("%s", (_constraint == NULL ? "NULL" : _constraint ) ); 935 printf("%s", (_valid == NULL ? "NULL" : _valid ) ); 936 _cost_lb->print(); 937 _cost_ub->print(); 938} 939 940 941//------------------------------ProductionState-------------------------------- 942void ProductionState::initialize() { 943 _constraint = noConstraint; 944 945 // reset each Production currently in the dictionary 946 DictI iter( &_production ); 947 const void *x, *y = NULL; 948 for( ; iter.test(); ++iter) { 949 x = iter._key; 950 y = iter._value; 951 Production *p = (Production*)y; 952 if( p != NULL ) { 953 p->initialize(); 954 } 955 } 956} 957 958Production *ProductionState::getProduction(const char *result) { 959 Production *p = (Production *)_production[result]; 960 if( p == NULL ) { 961 p = new Production(result, _constraint, knownInvalid); 962 _production.Insert(result, p); 963 } 964 965 return p; 966} 967 968void ProductionState::set_constraint(const char *constraint) { 969 _constraint = constraint; 970} 971 972const char *ProductionState::valid(const char *result) { 973 return getProduction(result)->valid(); 974} 975 976void ProductionState::set_valid(const char *result) { 977 Production *p = getProduction(result); 978 979 // Update valid as allowed by current constraints 980 if( _constraint == noConstraint ) { 981 p->_valid = knownValid; 982 } else { 983 if( p->_valid != knownValid ) { 984 p->_valid = unknownValid; 985 } 986 } 987} 988 989Expr *ProductionState::cost_lb(const char *result) { 990 return getProduction(result)->cost_lb(); 991} 992 993Expr *ProductionState::cost_ub(const char *result) { 994 return getProduction(result)->cost_ub(); 995} 996 997void ProductionState::set_cost_bounds(const char *result, const Expr *cost, bool has_state_check, bool has_cost_check) { 998 Production *p = getProduction(result); 999 1000 if( p->_valid == knownInvalid ) { 1001 // Our cost bounds are not unknown, just not defined. 1002 p->_cost_lb = cost->clone(); 1003 p->_cost_ub = cost->clone(); 1004 } else if (has_state_check || _constraint != noConstraint) { 1005 // The production is protected by a condition, so 1006 // the cost bounds may expand. 1007 // _cost_lb = min(cost, _cost_lb) 1008 if( cost->less_than_or_equal(p->_cost_lb) ) { 1009 p->_cost_lb = cost->clone(); 1010 } 1011 // _cost_ub = max(cost, _cost_ub) 1012 if( p->_cost_ub->less_than_or_equal(cost) ) { 1013 p->_cost_ub = cost->clone(); 1014 } 1015 } else if (has_cost_check) { 1016 // The production has no condition check, but does 1017 // have a cost check that could reduce the upper 1018 // and/or lower bound. 1019 // _cost_lb = min(cost, _cost_lb) 1020 if( cost->less_than_or_equal(p->_cost_lb) ) { 1021 p->_cost_lb = cost->clone(); 1022 } 1023 // _cost_ub = min(cost, _cost_ub) 1024 if( cost->less_than_or_equal(p->_cost_ub) ) { 1025 p->_cost_ub = cost->clone(); 1026 } 1027 } else { 1028 // The costs are unconditionally set. 1029 p->_cost_lb = cost->clone(); 1030 p->_cost_ub = cost->clone(); 1031 } 1032 1033} 1034 1035// Print out the dictionary contents as key-value pairs 1036static void print_key (const void* key) { fprintf(stdout, "%s", (char*) key); } 1037static void print_production(const void* production) { fflush(stdout); ((Production*)production)->print(); } 1038 1039void ProductionState::print() { 1040 _production.print(print_key, print_production); 1041} 1042