Initial checkin of tree pattern parser and type inference engine (which still needs work).

llvm-svn: 7668

2 files changed, 224 insertions, 3 deletions

diff --git a/llvm/support/tools/TableGen/InstrSelectorEmitter.cpp b/llvm/support/tools/TableGen/InstrSelectorEmitter.cpp
index e5bab478e90..a2bd08c7948 100644
--- a/llvm/support/tools/TableGen/InstrSelectorEmitter.cpp
+++ b/llvm/support/tools/TableGen/InstrSelectorEmitter.cpp
@@ -6,7 +6,9 @@
 //===----------------------------------------------------------------------===//
 
 #include "InstrSelectorEmitter.h"
+#include "CodeGenWrappers.h"
 #include "Record.h"
+#include "Support/Debug.h"
 
 NodeType::ArgResultTypes NodeType::Translate(Record *R) {
   const std::string &Name = R->getName();
@@ -17,6 +19,22 @@ NodeType::ArgResultTypes NodeType::Translate(Record *R) {
   throw "Unknown DagNodeValType '" + Name + "'!";
 }
 
+std::ostream &operator<<(std::ostream &OS, const TreePatternNode &N) {
+  if (N.isLeaf())
+    return OS << N.getType() << ":" << *N.getValue();
+  OS << "(" << N.getType() << ":";
+  OS << N.getOperator()->getName();
+  
+  const std::vector<TreePatternNode*> &Children = N.getChildren();
+  if (!Children.empty()) {
+    OS << " " << *Children[0];
+    for (unsigned i = 1, e = Children.size(); i != e; ++i)
+      OS << ", " << *Children[i];
+  }  
+  return OS << ")";
+}
+void TreePatternNode::dump() const { std::cerr << *this; }
+
 
 /// ProcessNodeTypes - Process all of the node types in the current
 /// RecordKeeper, turning them into the more accessible NodeTypes data
@@ -52,9 +70,148 @@ void InstrSelectorEmitter::ProcessNodeTypes() {
 
     // Add the node type mapping now...
     NodeTypes[Node] = NodeType(RetTy, ArgTypes);
-  }  
+    DEBUG(std::cerr << "Got node type '" << Node->getName() << "'\n");
+  }
+}
+
+static MVT::ValueType getIntrinsicType(Record *R) {
+  // Check to see if this is a register or a register class...
+  const std::vector<Record*> &SuperClasses = R->getSuperClasses();
+  for (unsigned i = 0, e = SuperClasses.size(); i != e; ++i)
+    if (SuperClasses[i]->getName() == "RegisterClass") {
+      return getValueType(R->getValueAsDef("RegType"));
+    } else if (SuperClasses[i]->getName() == "Register") {
+      std::cerr << "WARNING: Explicit registers not handled yet!\n";
+    } else if (SuperClasses[i]->getName() == "Nonterminal") {
+    }
+  //throw "Error: Unknown value used: " + R->getName();
+
+  return MVT::Other;
+}
+
+// Parse the specified DagInit into a TreePattern which we can use.
+//
+TreePatternNode *InstrSelectorEmitter::ParseTreePattern(DagInit *DI,
+                                                   const std::string &RecName) {
+  Record *Operator = DI->getNodeType();
+
+  if (!NodeTypes.count(Operator))
+    throw "Illegal node for instruction pattern: '" + Operator->getName() +"'!";
+
+  const std::vector<Init*> &Args = DI->getArgs();
+  std::vector<TreePatternNode*> Children;
+  
+  for (unsigned i = 0, e = Args.size(); i != e; ++i) {
+    Init *Arg = Args[i];
+    if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) {
+      Children.push_back(ParseTreePattern(DI, RecName));
+    } else if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) {
+      Children.push_back(new TreePatternNode(DI));
+      // If it's a regclass or something else known, set the type.
+      Children.back()->setType(getIntrinsicType(DI->getDef()));
+    } else {
+      Arg->dump();
+      throw "Unknown value for tree pattern in '" + RecName + "'!";
+    }
+  }
+
+  return new TreePatternNode(Operator, Children);
+}
+
+// UpdateNodeType - Set the node type of N to VT if VT contains information.  If
+// N already contains a conflicting type, then throw an exception
+//
+static bool UpdateNodeType(TreePatternNode *N, MVT::ValueType VT,
+                           const std::string &RecName) {
+  if (VT == MVT::Other || N->getType() == VT) return false;
+
+  if (N->getType() == MVT::Other) {
+    N->setType(VT);
+    return true;
+  }
+
+  throw "Type inferfence contradiction found for pattern " + RecName;
 }
 
+// InferTypes - Perform type inference on the tree, returning true if there
+// are any remaining untyped nodes and setting MadeChange if any changes were
+// made.
+bool InstrSelectorEmitter::InferTypes(TreePatternNode *N,
+                                      const std::string &RecName,
+                                      bool &MadeChange) {
+  if (N->isLeaf()) return N->getType() == MVT::Other;
+
+  bool AnyUnset = false;
+  Record *Operator = N->getOperator();
+  assert(NodeTypes.count(Operator) && "No node info for node!");
+  const NodeType &NT = NodeTypes[Operator];
+
+  // Check to see if we can infer anything about the argument types from the
+  // return types...
+  const std::vector<TreePatternNode*> &Children = N->getChildren();
+  if (Children.size() != NT.ArgTypes.size())
+    throw "In record " + RecName + " incorrect number of children for " +
+          Operator->getName() + " node!";
+
+  for (unsigned i = 0, e = Children.size(); i != e; ++i) {
+    AnyUnset |= InferTypes(Children[i], RecName, MadeChange);
+
+
+    switch (NT.ArgTypes[i]) {
+    case NodeType::Arg0:
+      MadeChange |=UpdateNodeType(Children[i], Children[0]->getType(), RecName);
+      break;
+    case NodeType::Val:
+      if (Children[i]->getType() == MVT::isVoid)
+        throw "In pattern for " + RecName + " should not get a void node!";
+      break;
+    case NodeType::Ptr: // FIXME
+    default: assert(0 && "Invalid argument ArgType!");
+    }
+  }
+
+  // See if we can infer anything about the return type now...
+  switch (NT.ResultType) {
+  case NodeType::Void:
+    MadeChange |= UpdateNodeType(N, MVT::isVoid, RecName);
+    break;
+  case NodeType::Arg0:
+    MadeChange |= UpdateNodeType(N, Children[0]->getType(), RecName);
+    break;
+
+  case NodeType::Ptr:   // FIXME: get from target
+  case NodeType::Val:
+    assert(0 && "Unhandled type constraint!");
+    break;
+  }
+
+  return AnyUnset | N->getType() == MVT::Other;
+}
+
+
+// ReadAndCheckPattern - Parse the specified DagInit into a pattern and then
+// perform full type inference.
+//
+TreePatternNode *InstrSelectorEmitter::ReadAndCheckPattern(DagInit *DI,
+                                                  const std::string &RecName) {
+  // First, parse the pattern...
+  TreePatternNode *Pattern = ParseTreePattern(DI, RecName);
+  
+  bool MadeChange, AnyUnset;
+  do {
+    MadeChange = false;
+    AnyUnset = InferTypes(Pattern, RecName, MadeChange);
+    if (AnyUnset && !MadeChange) {
+      std::cerr << "In pattern: " << *Pattern << "\n";
+      throw "Cannot infer types for " + RecName;
+    }
+  } while (AnyUnset || MadeChange);
+
+  return Pattern;
+}
+
+
+
 /// ProcessInstructionPatterns - Read in all subclasses of Instruction, and
 /// process those with a useful Pattern field.
 ///
@@ -62,9 +219,12 @@ void InstrSelectorEmitter::ProcessInstructionPatterns() {
   std::vector<Record*> Insts = Records.getAllDerivedDefinitions("Instruction");
   for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
     Record *Inst = Insts[i];
-    if (DagInit *PatternInit =
-          dynamic_cast<DagInit*>(Inst->getValueInit("Pattern"))) {
+    if (DagInit *DI = dynamic_cast<DagInit*>(Inst->getValueInit("Pattern"))) {
+      TreePatternNode *Pattern = ReadAndCheckPattern(DI, Inst->getName());
+
 
+      DEBUG(std::cerr << "Parsed inst pattern " << Inst->getName() << "\t= "
+                      << *Pattern << "\n");
     }
   }
 }
@@ -74,6 +234,8 @@ void InstrSelectorEmitter::run(std::ostream &OS) {
   // Type-check all of the node types to ensure we "understand" them.
   ProcessNodeTypes();
   
+  // Read in all of the nonterminals...
+
   // Read all of the instruction patterns in...
   ProcessInstructionPatterns();
 
diff --git a/llvm/support/tools/TableGen/InstrSelectorEmitter.h b/llvm/support/tools/TableGen/InstrSelectorEmitter.h
index 941763eb03c..dc16fb20f47 100644
--- a/llvm/support/tools/TableGen/InstrSelectorEmitter.h
+++ b/llvm/support/tools/TableGen/InstrSelectorEmitter.h
@@ -9,8 +9,11 @@
 #define INSTRSELECTOR_EMITTER_H
 
 #include "TableGenBackend.h"
+#include "llvm/CodeGen/ValueTypes.h"
 #include <vector>
 #include <map>
+class DagInit;
+class Init;
 
 struct NodeType {
   enum ArgResultTypes {
@@ -36,6 +39,47 @@ struct NodeType {
   static ArgResultTypes Translate(Record *R);
 };
 
+class TreePatternNode {
+  /// Operator - The operation that this node represents... this is null if this
+  /// is a leaf.
+  Record *Operator;
+
+  /// Type - The inferred value type...
+  MVT::ValueType                Type;
+
+  /// Children - If this is not a leaf (Operator != 0), this is the subtrees
+  /// that we contain.
+  std::vector<TreePatternNode*> Children;
+
+  /// Value - If this node is a leaf, this indicates what the thing is.
+  Init *Value;
+public:
+  TreePatternNode(Record *o, const std::vector<TreePatternNode*> &c)
+    : Operator(o), Type(MVT::Other), Children(c), Value(0) {}
+  TreePatternNode(Init *V) : Operator(0), Type(MVT::Other), Value(V) {}
+
+  Record *getOperator() const { return Operator; }
+  MVT::ValueType getType() const { return Type; }
+  void setType(MVT::ValueType T) { Type = T; }
+
+  bool isLeaf() const { return Operator == 0; }
+
+  const std::vector<TreePatternNode*> &getChildren() const {
+    assert(Operator != 0 && "This is a leaf node!");
+    return Children;
+  }
+  Init *getValue() const {
+    assert(Operator == 0 && "This is not a leaf node!");
+    return Value;
+  }
+
+  void dump() const;
+};
+
+std::ostream &operator<<(std::ostream &OS, const TreePatternNode &N);
+
+
+
 class InstrSelectorEmitter : public TableGenBackend {
   RecordKeeper &Records;
 
@@ -55,6 +99,21 @@ private:
   // ProcessInstructionPatterns - Read in all subclasses of Instruction, and
   // process those with a useful Pattern field.
   void ProcessInstructionPatterns();
+
+  // ParseTreePattern - Parse the specified DagInit into a TreePattern which we
+  // can use.
+  //
+  TreePatternNode *ParseTreePattern(DagInit *DI, const std::string &RecName);
+
+  // InferTypes - Perform type inference on the tree, returning true if there
+  // are any remaining untyped nodes and setting MadeChange if any changes were
+  // made.
+  bool InferTypes(TreePatternNode *N, const std::string &RecName,
+                  bool &MadeChange);
+
+  // ReadAndCheckPattern - Parse the specified DagInit into a pattern and then
+  // perform full type inference.
+  TreePatternNode *ReadAndCheckPattern(DagInit *DI, const std::string &RecName);
 };
 
 #endif