//

// 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.

//

//

//

// archDesc.cpp - Internal format for architecture definition

#include "adlc.hpp"

static FILE *errfile = stderr;

//--------------------------- utility functions -----------------------------

inline char  toUpper(char lower) {

  return (('a' <= lower && lower <= 'z') ? (lower + ('A'-'a')) : lower);

}

char *toUpper(const char *str) {

  char *upper  = new char[strlen(str)+1];

  char *result = upper;

  const char *end    = str + strlen(str);

  for (; str < end; ++str, ++upper) {

    *upper = toUpper(*str);

  }

  *upper = '\0';

  return result;

}

// Utilities to characterize effect statements

static bool is_def(int usedef) {

  switch(usedef) {

  case Component::DEF:

  case Component::USE_DEF: return true; break;

  }

  return false;

}

static bool is_use(int usedef) {

  switch(usedef) {

  case Component::USE:

  case Component::USE_DEF:

  case Component::USE_KILL: return true; break;

  }

  return false;

}

static bool is_kill(int usedef) {

  switch(usedef) {

  case Component::KILL:

  case Component::USE_KILL: return true; break;

  }

  return false;

}

//---------------------------ChainList Methods-------------------------------

ChainList::ChainList() {

}

void ChainList::insert(const char *name, const char *cost, const char *rule) {

  _name.addName(name);

  _cost.addName(cost);

  _rule.addName(rule);

}

bool ChainList::search(const char *name) {

  return _name.search(name);

}

void ChainList::reset() {

  _name.reset();

  _cost.reset();

  _rule.reset();

}

bool ChainList::iter(const char * &name, const char * &cost, const char * &rule) {

  bool        notDone = false;

  const char *n       = _name.iter();

  const char *c       = _cost.iter();

  const char *r       = _rule.iter();

  if (n && c && r) {

    notDone = true;

    name = n;

    cost = c;

    rule = r;

  }

  return notDone;

}

void ChainList::dump() {

  output(stderr);

}

void ChainList::output(FILE *fp) {

  fprintf(fp, "\nChain Rules: output resets iterator\n");

  const char   *cost  = NULL;

  const char   *name  = NULL;

  const char   *rule  = NULL;

  bool   chains_exist = false;

  for(reset(); (iter(name,cost,rule)) == true; ) {

    fprintf(fp, "Chain to <%s> at cost #%s using %s_rule\n",name, cost ? cost : "0", rule);

    //  // Check for transitive chain rules

    //  Form *form = (Form *)_globalNames[rule];

    //  if (form->is_instruction()) {

    //    // chain_rule(fp, indent, name, cost, rule);

    //    chain_rule(fp, indent, name, cost, rule);

    //  }

  }

  reset();

  if( ! chains_exist ) {

    fprintf(fp, "No entries in this ChainList\n");

  }

}

//---------------------------MatchList Methods-------------------------------

bool MatchList::search(const char *opc, const char *res, const char *lch,

                       const char *rch, Predicate *pr) {

  bool tmp = false;

  if ((res == _resultStr) || (res && _resultStr && !strcmp(res, _resultStr))) {

    if ((lch == _lchild) || (lch && _lchild && !strcmp(lch, _lchild))) {

      if ((rch == _rchild) || (rch && _rchild && !strcmp(rch, _rchild))) {

        char * predStr = get_pred();

        char * prStr = pr?pr->_pred:NULL;

        if (ADLParser::equivalent_expressions(prStr, predStr)) {

          return true;

        }

      }

    }

  }

  if (_next) {

    tmp = _next->search(opc, res, lch, rch, pr);

  }

  return tmp;

}

void MatchList::dump() {

  output(stderr);

}

void MatchList::output(FILE *fp) {

  fprintf(fp, "\nMatchList output is Unimplemented();\n");

}

//---------------------------ArchDesc Constructor and Destructor-------------

ArchDesc::ArchDesc()

  : _globalNames(cmpstr,hashstr, Form::arena),

    _globalDefs(cmpstr,hashstr, Form::arena),

    _preproc_table(cmpstr,hashstr, Form::arena),

    _idealIndex(cmpstr,hashstr, Form::arena),

    _internalOps(cmpstr,hashstr, Form::arena),

    _internalMatch(cmpstr,hashstr, Form::arena),

    _chainRules(cmpstr,hashstr, Form::arena),

    _cisc_spill_operand(NULL) {

      // Initialize the opcode to MatchList table with NULLs

      for( int i=0; i<_last_opcode; ++i ) {

        _mlistab[i] = NULL;

      }

      // Set-up the global tables

      initKeywords(_globalNames);    // Initialize the Name Table with keywords

      // Prime user-defined types with predefined types: Set, RegI, RegF, ...

      initBaseOpTypes();

      // Initialize flags & counters

      _TotalLines        = 0;

      _no_output         = 0;

      _quiet_mode        = 0;

      _disable_warnings  = 0;

      _dfa_debug         = 0;

      _dfa_small         = 0;

      _adl_debug         = 0;

      _adlocation_debug  = 0;

      _internalOpCounter = 0;

      _cisc_spill_debug  = false;

      _short_branch_debug = false;

      // Initialize match rule flags

      for (int i = 0; i < _last_opcode; i++) {

        _has_match_rule[i] = false;

      }

      // Error/Warning Counts

      _syntax_errs       = 0;

      _semantic_errs     = 0;

      _warnings          = 0;

      _internal_errs     = 0;

      // Initialize I/O Files

      _ADL_file._name = NULL; _ADL_file._fp = NULL;

      // Machine dependent output files

      _DFA_file._name    = NULL;  _DFA_file._fp = NULL;

      _HPP_file._name    = NULL;  _HPP_file._fp = NULL;

      _CPP_file._name    = NULL;  _CPP_file._fp = NULL;

      _bug_file._name    = "bugs.out";      _bug_file._fp = NULL;

      // Initialize Register & Pipeline Form Pointers

      _register = NULL;

      _encode = NULL;

      _pipeline = NULL;

}

ArchDesc::~ArchDesc() {

  // Clean-up and quit

}

//---------------------------ArchDesc methods: Public ----------------------

// Store forms according to type

void ArchDesc::addForm(PreHeaderForm *ptr) { _pre_header.addForm(ptr); };

void ArchDesc::addForm(HeaderForm    *ptr) { _header.addForm(ptr); };

void ArchDesc::addForm(SourceForm    *ptr) { _source.addForm(ptr); };

void ArchDesc::addForm(EncodeForm    *ptr) { _encode = ptr; };

void ArchDesc::addForm(InstructForm  *ptr) { _instructions.addForm(ptr); };

void ArchDesc::addForm(MachNodeForm  *ptr) { _machnodes.addForm(ptr); };

void ArchDesc::addForm(OperandForm   *ptr) { _operands.addForm(ptr); };

void ArchDesc::addForm(OpClassForm   *ptr) { _opclass.addForm(ptr); };

void ArchDesc::addForm(AttributeForm *ptr) { _attributes.addForm(ptr); };

void ArchDesc::addForm(RegisterForm  *ptr) { _register = ptr; };

void ArchDesc::addForm(FrameForm     *ptr) { _frame = ptr; };

void ArchDesc::addForm(PipelineForm  *ptr) { _pipeline = ptr; };

// Build MatchList array and construct MatchLists

void ArchDesc::generateMatchLists() {

  // Call inspection routines to populate array

  inspectOperands();

  inspectInstructions();

}

// Build MatchList structures for operands

void ArchDesc::inspectOperands() {

  // Iterate through all operands

  _operands.reset();

  OperandForm *op;

  for( ; (op = (OperandForm*)_operands.iter()) != NULL;) {

    // Construct list of top-level operands (components)

    op->build_components();

    // Ensure that match field is defined.

    if ( op->_matrule == NULL )  continue;

    // Type check match rules

    check_optype(op->_matrule);

    // Construct chain rules

    build_chain_rule(op);

    MatchRule &mrule = *op->_matrule;

    Predicate *pred  =  op->_predicate;

    // Grab the machine type of the operand

    const char  *rootOp    = op->_ident;

    mrule._machType  = rootOp;

    // Check for special cases

    if (strcmp(rootOp,"Universe")==0) continue;

    if (strcmp(rootOp,"label")==0) continue;

    // !!!!! !!!!!

    assert( strcmp(rootOp,"sReg") != 0, "Disable untyped 'sReg'");

    if (strcmp(rootOp,"sRegI")==0) continue;

    if (strcmp(rootOp,"sRegP")==0) continue;

    if (strcmp(rootOp,"sRegF")==0) continue;

    if (strcmp(rootOp,"sRegD")==0) continue;

    if (strcmp(rootOp,"sRegL")==0) continue;

    // Cost for this match

    const char *costStr     = op->cost();

    const char *defaultCost =

      ((AttributeForm*)_globalNames[AttributeForm::_op_cost])->_attrdef;

    const char *cost        =  costStr? costStr : defaultCost;

    // Find result type for match.

    const char *result      = op->reduce_result();

    bool        has_root    = false;

    // Construct a MatchList for this entry

    buildMatchList(op->_matrule, result, rootOp, pred, cost);

  }

}

// Build MatchList structures for instructions

void ArchDesc::inspectInstructions() {

  // Iterate through all instructions

  _instructions.reset();

  InstructForm *instr;

  for( ; (instr = (InstructForm*)_instructions.iter()) != NULL; ) {

    // Construct list of top-level operands (components)

    instr->build_components();

    // Ensure that match field is defined.

    if ( instr->_matrule == NULL )  continue;

    MatchRule &mrule = *instr->_matrule;

    Predicate *pred  =  instr->build_predicate();

    // Grab the machine type of the operand

    const char  *rootOp    = instr->_ident;

    mrule._machType  = rootOp;

    // Cost for this match

    const char *costStr = instr->cost();

    const char *defaultCost =

      ((AttributeForm*)_globalNames[AttributeForm::_ins_cost])->_attrdef;

    const char *cost    =  costStr? costStr : defaultCost;

    // Find result type for match

    const char *result  = instr->reduce_result();

    Attribute *attr = instr->_attribs;

    while (attr != NULL) {

      if (strcmp(attr->_ident,"ins_short_branch") == 0 &&

          attr->int_val(*this) != 0) {

        instr->set_short_branch(true);

      } else if (strcmp(attr->_ident,"ins_alignment") == 0 &&

          attr->int_val(*this) != 0) {

        instr->set_alignment(attr->int_val(*this));

      }

      attr = (Attribute *)attr->_next;

    }

    if (!instr->is_short_branch()) {

      buildMatchList(instr->_matrule, result, mrule._machType, pred, cost);

    }

  }

}

static int setsResult(MatchRule &mrule) {

  if (strcmp(mrule._name,"Set") == 0) return 1;

  return 0;

}

const char *ArchDesc::getMatchListIndex(MatchRule &mrule) {

  if (setsResult(mrule)) {

    // right child

    return mrule._rChild->_opType;

  } else {

    // first entry

    return mrule._opType;

  }

}

//------------------------------result of reduction----------------------------

//------------------------------left reduction---------------------------------

// Return the left reduction associated with an internal name

const char *ArchDesc::reduceLeft(char         *internalName) {

  const char *left  = NULL;

  MatchNode *mnode = (MatchNode*)_internalMatch[internalName];

  if (mnode->_lChild) {

    mnode = mnode->_lChild;

    left = mnode->_internalop ? mnode->_internalop : mnode->_opType;

  }

  return left;

}

//------------------------------right reduction--------------------------------

const char *ArchDesc::reduceRight(char  *internalName) {

  const char *right  = NULL;

  MatchNode *mnode = (MatchNode*)_internalMatch[internalName];

  if (mnode->_rChild) {

    mnode = mnode->_rChild;

    right = mnode->_internalop ? mnode->_internalop : mnode->_opType;

  }

  return right;

}

//------------------------------check_optype-----------------------------------

void ArchDesc::check_optype(MatchRule *mrule) {

  MatchRule *rule = mrule;

  //   !!!!!

  //   // Cycle through the list of match rules

  //   while(mrule) {

  //     // Check for a filled in type field

  //     if (mrule->_opType == NULL) {

  //     const Form  *form    = operands[_result];

  //     OpClassForm *opcForm = form ? form->is_opclass() : NULL;

  //     assert(opcForm != NULL, "Match Rule contains invalid operand name.");

  //     }

  //     char *opType = opcForm->_ident;

  //   }

}

//------------------------------add_chain_rule_entry--------------------------

void ArchDesc::add_chain_rule_entry(const char *src, const char *cost,

                                    const char *result) {

  // Look-up the operation in chain rule table

  ChainList *lst = (ChainList *)_chainRules[src];

  if (lst == NULL) {

    lst = new ChainList();

    _chainRules.Insert(src, lst);

  }

  if (!lst->search(result)) {

    if (cost == NULL) {

      cost = ((AttributeForm*)_globalNames[AttributeForm::_op_cost])->_attrdef;

    }

    lst->insert(result, cost, result);

  }

}

//------------------------------build_chain_rule-------------------------------

void ArchDesc::build_chain_rule(OperandForm *oper) {

  MatchRule     *rule;

  // Check for chain rules here

  // If this is only a chain rule

  if ((oper->_matrule) && (oper->_matrule->_lChild == NULL) &&

      (oper->_matrule->_rChild == NULL)) {

    {

      const Form *form = _globalNames[oper->_matrule->_opType];

      if ((form) && form->is_operand() &&

          (form->ideal_only() == false)) {

        add_chain_rule_entry(oper->_matrule->_opType, oper->cost(), oper->_ident);

      }

    }

    // Check for additional chain rules

    if (oper->_matrule->_next) {

      rule = oper->_matrule;

      do {

        rule = rule->_next;

        // Any extra match rules after the first must be chain rules

        const Form *form = _globalNames[rule->_opType];

        if ((form) && form->is_operand() &&

            (form->ideal_only() == false)) {

          add_chain_rule_entry(rule->_opType, oper->cost(), oper->_ident);

        }

      } while(rule->_next != NULL);

    }

  }

  else if ((oper->_matrule) && (oper->_matrule->_next)) {

    // Regardles of whether the first matchrule is a chain rule, check the list

    rule = oper->_matrule;

    do {

      rule = rule->_next;

      // Any extra match rules after the first must be chain rules

      const Form *form = _globalNames[rule->_opType];

      if ((form) && form->is_operand() &&

          (form->ideal_only() == false)) {

        assert( oper->cost(), "This case expects NULL cost, not default cost");

        add_chain_rule_entry(rule->_opType, oper->cost(), oper->_ident);

      }

    } while(rule->_next != NULL);

  }

}

//------------------------------buildMatchList---------------------------------

// operands and instructions provide the result

void ArchDesc::buildMatchList(MatchRule *mrule, const char *resultStr,

                              const char *rootOp, Predicate *pred,

                              const char *cost) {

  const char *leftstr, *rightstr;

  MatchNode  *mnode;

  leftstr = rightstr = NULL;

  // Check for chain rule, and do not generate a match list for it

  if ( mrule->is_chain_rule(_globalNames) ) {

    return;

  }

  // Identify index position among ideal operands

  intptr_t    index     = _last_opcode;

  const char  *indexStr  = getMatchListIndex(*mrule);

  index  = (intptr_t)_idealIndex[indexStr];

  if (index == 0) {

    fprintf(stderr, "Ideal node missing: %s\n", indexStr);

    assert(index != 0, "Failed lookup of ideal node\n");

  }

  // Check that this will be placed appropriately in the DFA

  if (index >= _last_opcode) {

    fprintf(stderr, "Invalid match rule %s <-- ( %s )\n",

            resultStr ? resultStr : " ",

            rootOp    ? rootOp    : " ");

    assert(index < _last_opcode, "Matching item not in ideal graph\n");

    return;

  }

  // Walk the MatchRule, generating MatchList entries for each level

  // of the rule (each nesting of parentheses)

  // Check for "Set"

  if (!strcmp(mrule->_opType, "Set")) {

    mnode = mrule->_rChild;

    buildMList(mnode, rootOp, resultStr, pred, cost);

    return;

  }

  // Build MatchLists for children

  // Check each child for an internal operand name, and use that name

  // for the parent's matchlist entry if it exists

  mnode = mrule->_lChild;

  if (mnode) {

    buildMList(mnode, NULL, NULL, NULL, NULL);

    leftstr = mnode->_internalop ? mnode->_internalop : mnode->_opType;

  }

  mnode = mrule->_rChild;

  if (mnode) {