automaton.h

Go to the documentation of this file.

//
// File: automaton.h
//
// Purpose: Implements the many-to-one rule automaton class used to match insn patterns
//          in the LEGO DDG.
//
// Author: Mark C. Toburen
//
// History:
//    Created - 7/30/01
//

#ifndef _AUTOMATON_H_
#define _AUTOMATON_H_

#include "typedefs.h"
#include "succ_node.h"
#include "belong.h"
#include "tree_node.h"

class Automaton {
private:
   map<string, TreeNode> ParseTree;

public:

   // default constructor
   Automaton () {}

   // constructor
   Automaton (map<string, vector<insn> > rules) {
      TreeIter find, end;
      RuleIter rule;
      InsnVecIter vec;
      TreeNode *tnode;

      // Build the parse tree.
      for (rule = rules.begin(); rule != rules.end(); rule++) {

         // skip the blank rule that results from the last '/' in the rules file
         if (rule->first == "") continue;
         //cout << rule->first << endl;

         // For each op in the rule:
         //   1. If the op hasn't been inserted into the ParseTree map
         //      a. create a new TreeNode for this op
         //      b. insert the TreeNode into the ParseTree map with the op name as its key
         //   2. If the op exists in the ParseTree
         //      a. insert a new "belong_to" entry for this op & rule
         for (vec = (rule->second).begin() + 1; vec != (rule->second).end(); vec++) {

            // See if the current op in the rule is in the ParseTree
            find = ParseTree.find(vec->GetName());
            end = ParseTree.end();
            if (find == end) {
               //cerr << ">> Automaton: inserting op: " << vec->GetName() << endl;
               // Create a new TreeNode and insert it into the ParseTree.
               tnode = new TreeNode(rule, vec);
               ParseTree.insert(pair<string, TreeNode>(vec->GetName(), *tnode));
            } else {
               // insert a new "belong_to" entry for this op & rule
               (find->second).InsertBelong(rule, vec);
            }
         }
      }
      SetSuccessorParents();
   }

   // set the parent parse tree node of all the successors in the tree
   void SetSuccessorParents () {
      TreeIter titer, find, end = ParseTree.end();
      BelongIter biter;
      SuccNode *succ;

      for (titer = ParseTree.begin(); titer != ParseTree.end(); titer++) {
         for (biter = (titer->second).GetBelongTo().begin(); biter != (titer->second).GetBelongTo().end(); biter++) {
            if (!(succ = (biter->second).GetSuccessor()))
               continue;   // this op has no successor for this rule
            find = ParseTree.find(succ->GetOp().GetName());
            if (find == end)
               cerr << ">> SetSuccessorParents: cannot find successor op in ParseTree." << endl;
            else {
               succ->SetParentNode(&(find->second));
            }
         }
      }
   }

   // search the parse tree for a start node with name OPNAME
   TreeNode *FindStartOp (string opname) {
      TreeIter find;
      BelongIter biter;

      find = ParseTree.find(opname);
      if (find != ParseTree.end()) {
         for (biter = (find->second).GetBelongTo().begin(); biter != (find->second).GetBelongTo().end(); biter++) {
            if ((biter->second).IsStartOp())
               return &(find->second);
            continue;
         }
      } else
         return NULL;
   }

   void PrintAutomaton () {
      TreeIter titer;
      BelongIter biter;
      SuccNode *succ;

      cout << "Printing automaton ... " << endl;
      for (titer = ParseTree.begin(); titer != ParseTree.end(); titer++) {
         for (biter = (titer->second).GetBelongTo().begin(); biter != (titer->second).GetBelongTo().end(); biter++) {
            cout << biter->first << "\t" << (titer->second).GetOp().GetName() << "\t" << (biter->second).IsStartOp();
            if ((biter->second).IsStartOp() == true)
               cout << "\t" << (biter->second).GetMacroInsn().GetName();
            succ = (biter->second).GetSuccessor();
            if (succ != NULL)
               cout << "\t" << succ->GetOp().GetName() << "(" << succ->GetParentNode()->GetOp().GetName() << ")\t" << succ->IsLeafNode();
            cout << endl;
         }
      }
      cout << "done." << endl;
   }
};

#endif // _AUTOMATON_H_

---