/*

 * Copyright 1997-2004 Sun Microsystems, Inc.  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 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 *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 = 2 };

  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 ' ':

      return dfa_shared_preds::valid_loc(pred, prev);

    case '!':

    case '(':

    case '<':

    case '=':

      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.