Finish implementation of nonterminal instantiation.

Tree patterns are now, finally, ready to use!


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7699 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 158 insertions, 21 deletions

diff --git a/utils/TableGen/InstrSelectorEmitter.cpp b/utils/TableGen/InstrSelectorEmitter.cpp
index 250c8975c1..3e30a52b6c 100644
--- a/utils/TableGen/InstrSelectorEmitter.cpp
+++ b/utils/TableGen/InstrSelectorEmitter.cpp
@@ -38,6 +38,49 @@ bool TreePatternNode::updateNodeType(MVT::ValueType VT,
   throw "Type inferfence contradiction found for pattern " + RecName;
 }
 
+/// InstantiateNonterminals - If this pattern refers to any nonterminals which
+/// are not themselves completely resolved, clone the nonterminal and resolve it
+/// with the using context we provide.
+///
+void TreePatternNode::InstantiateNonterminals(InstrSelectorEmitter &ISE) {
+  if (!isLeaf()) {
+    for (unsigned i = 0, e = Children.size(); i != e; ++i)
+      Children[i]->InstantiateNonterminals(ISE);
+    return;
+  }
+  
+  // If this is a leaf, it might be a reference to a nonterminal!  Check now.
+  if (DefInit *DI = dynamic_cast<DefInit*>(getValue()))
+    if (DI->getDef()->isSubClassOf("Nonterminal")) {
+      Pattern *NT = ISE.getPattern(DI->getDef());
+      if (!NT->isResolved()) {
+        // We found an unresolved nonterminal reference.  Ask the ISE to clone
+        // it for us, then update our reference to the fresh, new, resolved,
+        // nonterminal.
+        
+        Value = new DefInit(ISE.InstantiateNonterminal(NT, getType()));
+      }
+    }
+}
+
+
+/// clone - Make a copy of this tree and all of its children.
+///
+TreePatternNode *TreePatternNode::clone() const {
+  TreePatternNode *New;
+  if (isLeaf()) {
+    New = new TreePatternNode(Value);
+  } else {
+    std::vector<TreePatternNode*> CChildren(Children.size());
+    for (unsigned i = 0, e = Children.size(); i != e; ++i)
+      CChildren[i] = Children[i]->clone();
+    New = new TreePatternNode(Operator, CChildren);
+  }
+  New->setType(Type);
+  return New;
+}
+
+
 std::ostream &operator<<(std::ostream &OS, const TreePatternNode &N) {
   if (N.isLeaf())
     return OS << N.getType() << ":" << *N.getValue();
@@ -67,16 +110,13 @@ Pattern::Pattern(PatternType pty, DagInit *RawPat, Record *TheRec,
 
   // First, parse the pattern...
   Tree = ParseTreePattern(RawPat);
-  
-  bool MadeChange, AnyUnset;
-  do {
-    MadeChange = false;
-    AnyUnset = InferTypes(Tree, MadeChange);
-  } while ((AnyUnset || MadeChange) && !(AnyUnset && !MadeChange));
+
+  // Run the type-inference engine...
+  InferAllTypes();
 
   if (PTy == Instruction || PTy == Expander) {
     // Check to make sure there is not any unset types in the tree pattern...
-    if (AnyUnset) {
+    if (!isResolved()) {
       std::cerr << "In pattern: " << *Tree << "\n";
       error("Could not infer all types!");
     }
@@ -92,13 +132,12 @@ Pattern::Pattern(PatternType pty, DagInit *RawPat, Record *TheRec,
 
       Result = RegInit->getDef();
       Tree = Tree->getChild(1);
-
     }
   }
-
-  Resolved = !AnyUnset;
 }
 
+
+
 void Pattern::error(const std::string &Msg) const {
   std::string M = "In ";
   switch (PTy) {
@@ -175,6 +214,15 @@ TreePatternNode *Pattern::ParseTreePattern(DagInit *DI) {
   return new TreePatternNode(Operator, Children);
 }
 
+void Pattern::InferAllTypes() {
+  bool MadeChange, AnyUnset;
+  do {
+    MadeChange = false;
+    AnyUnset = InferTypes(Tree, MadeChange);
+  } while ((AnyUnset || MadeChange) && !(AnyUnset && !MadeChange));
+  Resolved = !AnyUnset;
+}
+
 
 // InferTypes - Perform type inference on the tree, returning true if there
 // are any remaining untyped nodes and setting MadeChange if any changes were
@@ -240,15 +288,16 @@ bool Pattern::InferTypes(TreePatternNode *N, bool &MadeChange) {
   return AnyUnset | N->getType() == MVT::Other;
 }
 
-/// InstantiateNonterminalsReferenced - If this pattern refers to any
-/// nonterminals which are not themselves completely resolved, clone the
-/// nonterminal and resolve it with the using context we provide.
+/// clone - This method is used to make an exact copy of the current pattern,
+/// then change the "TheRecord" instance variable to the specified record.
 ///
-void Pattern::InstantiateNonterminalsReferenced() {
-
+Pattern *Pattern::clone(Record *R) const {
+  assert(PTy == Nonterminal && "Can only clone nonterminals");
+  return new Pattern(Tree->clone(), R, Resolved, ISE);
 }
 
 
+
 std::ostream &operator<<(std::ostream &OS, const Pattern &P) {
   switch (P.getPatternType()) {
   case Pattern::Nonterminal: OS << "Nonterminal pattern "; break;
@@ -362,10 +411,50 @@ void InstrSelectorEmitter::ReadExpanderPatterns() {
 // information from the context that they are used in.
 //
 void InstrSelectorEmitter::InstantiateNonterminals() {
+  DEBUG(std::cerr << "Instantiating nonterminals:\n");
   for (std::map<Record*, Pattern*>::iterator I = Patterns.begin(),
          E = Patterns.end(); I != E; ++I)
     if (I->second->isResolved())
-      I->second->InstantiateNonterminalsReferenced();
+      I->second->InstantiateNonterminals();
+}
+
+/// InstantiateNonterminal - This method takes the nonterminal specified by
+/// NT, which should not be completely resolved, clones it, applies ResultTy
+/// to its root, then runs the type inference stuff on it.  This should
+/// produce a newly resolved nonterminal, which we make a record for and
+/// return.  To be extra fancy and efficient, this only makes one clone for
+/// each type it is instantiated with.
+Record *InstrSelectorEmitter::InstantiateNonterminal(Pattern *NT,
+                                                     MVT::ValueType ResultTy) {
+  assert(!NT->isResolved() && "Nonterminal is already resolved!");
+
+  // Check to see if we have already instantiated this pair...
+  Record* &Slot = InstantiatedNTs[std::make_pair(NT, ResultTy)];
+  if (Slot) return Slot;
+  
+  DEBUG(std::cerr << "  Nonterminal '" << NT->getRecord()->getName()
+                  << "' for type '" << getName(ResultTy) << "'\n");
+
+  Record *New = new Record(NT->getRecord()->getName()+"_"+getName(ResultTy));
+
+  // Copy the pattern...
+  Pattern *NewPat = NT->clone(New);
+
+  // Apply the type to the root...
+  NewPat->getTree()->updateNodeType(ResultTy, New->getName());
+
+  // Infer types...
+  NewPat->InferAllTypes();
+
+  // Make sure everything is good to go now...
+  if (!NewPat->isResolved())
+    NewPat->error("Instantiating nonterminal did not resolve all types!");
+
+  // Add the pattern to the patterns map, add the record to the RecordKeeper,
+  // return the new record.
+  Patterns[New] = NewPat;
+  Records.addDef(New);
+  return Slot = New;
 }
 
 
@@ -381,4 +470,11 @@ void InstrSelectorEmitter::run(std::ostream &OS) {
   // Instantiate any unresolved nonterminals with information from the context
   // that they are used in.
   InstantiateNonterminals();
+
+
+  std::cerr << "Patterns aquired:\n";
+  for (std::map<Record*, Pattern*>::iterator I = Patterns.begin(),
+         E = Patterns.end(); I != E; ++I)
+    if (I->second->isResolved())
+      std::cerr << "  " << *I->second << "\n";
 }
diff --git a/utils/TableGen/InstrSelectorEmitter.h b/utils/TableGen/InstrSelectorEmitter.h
index e8c8fad33f..0a8ca982fe 100644
--- a/utils/TableGen/InstrSelectorEmitter.h
+++ b/utils/TableGen/InstrSelectorEmitter.h
@@ -87,8 +87,16 @@ public:
     return Value;
   }
 
+  /// clone - Make a copy of this tree and all of its children.
+  ///
+  TreePatternNode *clone() const;
+
   void dump() const;
 
+  /// InstantiateNonterminals - If this pattern refers to any nonterminals which
+  /// are not themselves completely resolved, clone the nonterminal and resolve
+  /// it with the using context we provide.
+  void InstantiateNonterminals(InstrSelectorEmitter &ISE);
 
   // UpdateNodeType - Set the node type of N to VT if VT contains information.
   // If N already contains a conflicting type, then throw an exception.  This
@@ -145,6 +153,11 @@ public:
   Pattern(PatternType pty, DagInit *RawPat, Record *TheRec,
           InstrSelectorEmitter &ise);
 
+  /// Pattern - Constructor used for cloning nonterminal patterns
+  Pattern(TreePatternNode *tree, Record *rec, bool res,
+          InstrSelectorEmitter &ise) : PTy(Nonterminal), Tree(tree), Result(0),
+                                       TheRecord(rec), Resolved(res), ISE(ise){}
+
   /// getPatternType - Return what flavor of Record this pattern originated from
   ///
   PatternType getPatternType() const { return PTy; }
@@ -162,15 +175,30 @@ public:
 
   bool isResolved() const { return Resolved; }
 
-  /// InstantiateNonterminalsReferenced - If this pattern refers to any
-  /// nonterminals which are not themselves completely resolved, clone the
-  /// nonterminal and resolve it with the using context we provide.
-  void InstantiateNonterminalsReferenced();
+  /// InferAllTypes - Runs the type inference engine on the current pattern,
+  /// stopping when nothing can be inferred, then updating the Resolved field.
+  void InferAllTypes();
+
+  /// InstantiateNonterminals - If this pattern refers to any nonterminals which
+  /// are not themselves completely resolved, clone the nonterminal and resolve
+  /// it with the using context we provide.
+  void InstantiateNonterminals() {
+    Tree->InstantiateNonterminals(ISE);
+  }
+
+  /// clone - This method is used to make an exact copy of the current pattern,
+  /// then change the "TheRecord" instance variable to the specified record.
+  ///
+  Pattern *clone(Record *R) const;
+
+  /// error - Throw an exception, prefixing it with information about this
+  /// pattern.
+  void error(const std::string &Msg) const;
+
 private:
   MVT::ValueType getIntrinsicType(Record *R) const;
   TreePatternNode *ParseTreePattern(DagInit *DI);
   bool InferTypes(TreePatternNode *N, bool &MadeChange);
-  void error(const std::string &Msg) const;
 };
 
 std::ostream &operator<<(std::ostream &OS, const Pattern &P);
@@ -189,6 +217,11 @@ class InstrSelectorEmitter : public TableGenBackend {
   /// Patterns - a list of all of the patterns defined by the target description
   ///
   std::map<Record*, Pattern*> Patterns;
+
+  /// InstantiatedNTs - A data structure to keep track of which nonterminals
+  /// have been instantiated already...
+  ///
+  std::map<std::pair<Pattern*,MVT::ValueType>, Record*> InstantiatedNTs;
 public:
   InstrSelectorEmitter(RecordKeeper &R) : Records(R) {}
   
@@ -209,6 +242,14 @@ public:
   /// nonterminal, but only if it hasn't been read in already.
   Pattern *ReadNonterminal(Record *R);
 
+  /// InstantiateNonterminal - This method takes the nonterminal specified by
+  /// NT, which should not be completely resolved, clones it, applies ResultTy
+  /// to its root, then runs the type inference stuff on it.  This should
+  /// produce a newly resolved nonterminal, which we make a record for and
+  /// return.  To be extra fancy and efficient, this only makes one clone for
+  /// each type it is instantiated with.
+  Record *InstantiateNonterminal(Pattern *NT, MVT::ValueType ResultTy);
+
 private:
   // ReadNodeTypes - Read in all of the node types in the current RecordKeeper,
   // turning them into the more accessible NodeTypes data structure.