change getQualifiedName to be a global function.

Split the pattern parsing code out from the dag isel emitter into it's own file.

No functionality change.


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

1 files changed, 2092 insertions, 0 deletions

diff --git a/utils/TableGen/CodeGenDAGPatterns.cpp b/utils/TableGen/CodeGenDAGPatterns.cpp
new file mode 100644
index 0000000000..4d36764859
--- /dev/null
+++ b/utils/TableGen/CodeGenDAGPatterns.cpp
@@ -0,0 +1,2092 @@
+//===- CodegenDAGPatterns.cpp - Read DAG patterns from .td file -----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the CodegenDAGPatterns class, which is used to read and
+// represent the patterns present in a .td file for instructions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "CodegenDAGPatterns.h"
+#include "Record.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/Support/Debug.h"
+//#include "llvm/Support/MathExtras.h"
+#include "llvm/Support/Streams.h"
+//#include <algorithm>
+#include <set>
+using namespace llvm;
+
+//===----------------------------------------------------------------------===//
+// Helpers for working with extended types.
+
+/// FilterVTs - Filter a list of VT's according to a predicate.
+///
+template<typename T>
+static std::vector<MVT::ValueType> 
+FilterVTs(const std::vector<MVT::ValueType> &InVTs, T Filter) {
+  std::vector<MVT::ValueType> Result;
+  for (unsigned i = 0, e = InVTs.size(); i != e; ++i)
+    if (Filter(InVTs[i]))
+      Result.push_back(InVTs[i]);
+  return Result;
+}
+
+template<typename T>
+static std::vector<unsigned char> 
+FilterEVTs(const std::vector<unsigned char> &InVTs, T Filter) {
+  std::vector<unsigned char> Result;
+  for (unsigned i = 0, e = InVTs.size(); i != e; ++i)
+    if (Filter((MVT::ValueType)InVTs[i]))
+      Result.push_back(InVTs[i]);
+  return Result;
+}
+
+static std::vector<unsigned char>
+ConvertVTs(const std::vector<MVT::ValueType> &InVTs) {
+  std::vector<unsigned char> Result;
+  for (unsigned i = 0, e = InVTs.size(); i != e; ++i)
+    Result.push_back(InVTs[i]);
+  return Result;
+}
+
+static bool LHSIsSubsetOfRHS(const std::vector<unsigned char> &LHS,
+                             const std::vector<unsigned char> &RHS) {
+  if (LHS.size() > RHS.size()) return false;
+  for (unsigned i = 0, e = LHS.size(); i != e; ++i)
+    if (std::find(RHS.begin(), RHS.end(), LHS[i]) == RHS.end())
+      return false;
+  return true;
+}
+
+/// isExtIntegerVT - Return true if the specified extended value type vector
+/// contains isInt or an integer value type.
+namespace llvm {
+namespace MVT {
+bool isExtIntegerInVTs(const std::vector<unsigned char> &EVTs) {
+  assert(!EVTs.empty() && "Cannot check for integer in empty ExtVT list!");
+  return EVTs[0] == isInt || !(FilterEVTs(EVTs, isInteger).empty());
+}
+
+/// isExtFloatingPointVT - Return true if the specified extended value type 
+/// vector contains isFP or a FP value type.
+bool isExtFloatingPointInVTs(const std::vector<unsigned char> &EVTs) {
+  assert(!EVTs.empty() && "Cannot check for integer in empty ExtVT list!");
+  return EVTs[0] == isFP || !(FilterEVTs(EVTs, isFloatingPoint).empty());
+}
+} // end namespace MVT.
+} // end namespace llvm.
+
+//===----------------------------------------------------------------------===//
+// SDTypeConstraint implementation
+//
+
+SDTypeConstraint::SDTypeConstraint(Record *R) {
+  OperandNo = R->getValueAsInt("OperandNum");
+  
+  if (R->isSubClassOf("SDTCisVT")) {
+    ConstraintType = SDTCisVT;
+    x.SDTCisVT_Info.VT = getValueType(R->getValueAsDef("VT"));
+  } else if (R->isSubClassOf("SDTCisPtrTy")) {
+    ConstraintType = SDTCisPtrTy;
+  } else if (R->isSubClassOf("SDTCisInt")) {
+    ConstraintType = SDTCisInt;
+  } else if (R->isSubClassOf("SDTCisFP")) {
+    ConstraintType = SDTCisFP;
+  } else if (R->isSubClassOf("SDTCisSameAs")) {
+    ConstraintType = SDTCisSameAs;
+    x.SDTCisSameAs_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum");
+  } else if (R->isSubClassOf("SDTCisVTSmallerThanOp")) {
+    ConstraintType = SDTCisVTSmallerThanOp;
+    x.SDTCisVTSmallerThanOp_Info.OtherOperandNum = 
+      R->getValueAsInt("OtherOperandNum");
+  } else if (R->isSubClassOf("SDTCisOpSmallerThanOp")) {
+    ConstraintType = SDTCisOpSmallerThanOp;
+    x.SDTCisOpSmallerThanOp_Info.BigOperandNum = 
+      R->getValueAsInt("BigOperandNum");
+  } else if (R->isSubClassOf("SDTCisIntVectorOfSameSize")) {
+    ConstraintType = SDTCisIntVectorOfSameSize;
+    x.SDTCisIntVectorOfSameSize_Info.OtherOperandNum =
+      R->getValueAsInt("OtherOpNum");
+  } else {
+    cerr << "Unrecognized SDTypeConstraint '" << R->getName() << "'!\n";
+    exit(1);
+  }
+}
+
+/// getOperandNum - Return the node corresponding to operand #OpNo in tree
+/// N, which has NumResults results.
+TreePatternNode *SDTypeConstraint::getOperandNum(unsigned OpNo,
+                                                 TreePatternNode *N,
+                                                 unsigned NumResults) const {
+  assert(NumResults <= 1 &&
+         "We only work with nodes with zero or one result so far!");
+  
+  if (OpNo >= (NumResults + N->getNumChildren())) {
+    cerr << "Invalid operand number " << OpNo << " ";
+    N->dump();
+    cerr << '\n';
+    exit(1);
+  }
+
+  if (OpNo < NumResults)
+    return N;  // FIXME: need value #
+  else
+    return N->getChild(OpNo-NumResults);
+}
+
+/// ApplyTypeConstraint - Given a node in a pattern, apply this type
+/// constraint to the nodes operands.  This returns true if it makes a
+/// change, false otherwise.  If a type contradiction is found, throw an
+/// exception.
+bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N,
+                                           const SDNodeInfo &NodeInfo,
+                                           TreePattern &TP) const {
+  unsigned NumResults = NodeInfo.getNumResults();
+  assert(NumResults <= 1 &&
+         "We only work with nodes with zero or one result so far!");
+  
+  // Check that the number of operands is sane.  Negative operands -> varargs.
+  if (NodeInfo.getNumOperands() >= 0) {
+    if (N->getNumChildren() != (unsigned)NodeInfo.getNumOperands())
+      TP.error(N->getOperator()->getName() + " node requires exactly " +
+               itostr(NodeInfo.getNumOperands()) + " operands!");
+  }
+
+  const CodeGenTarget &CGT = TP.getDAGPatterns().getTargetInfo();
+  
+  TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NumResults);
+  
+  switch (ConstraintType) {
+  default: assert(0 && "Unknown constraint type!");
+  case SDTCisVT:
+    // Operand must be a particular type.
+    return NodeToApply->UpdateNodeType(x.SDTCisVT_Info.VT, TP);
+  case SDTCisPtrTy: {
+    // Operand must be same as target pointer type.
+    return NodeToApply->UpdateNodeType(MVT::iPTR, TP);
+  }
+  case SDTCisInt: {
+    // If there is only one integer type supported, this must be it.
+    std::vector<MVT::ValueType> IntVTs =
+      FilterVTs(CGT.getLegalValueTypes(), MVT::isInteger);
+
+    // If we found exactly one supported integer type, apply it.
+    if (IntVTs.size() == 1)
+      return NodeToApply->UpdateNodeType(IntVTs[0], TP);
+    return NodeToApply->UpdateNodeType(MVT::isInt, TP);
+  }
+  case SDTCisFP: {
+    // If there is only one FP type supported, this must be it.
+    std::vector<MVT::ValueType> FPVTs =
+      FilterVTs(CGT.getLegalValueTypes(), MVT::isFloatingPoint);
+        
+    // If we found exactly one supported FP type, apply it.
+    if (FPVTs.size() == 1)
+      return NodeToApply->UpdateNodeType(FPVTs[0], TP);
+    return NodeToApply->UpdateNodeType(MVT::isFP, TP);
+  }
+  case SDTCisSameAs: {
+    TreePatternNode *OtherNode =
+      getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NumResults);
+    return NodeToApply->UpdateNodeType(OtherNode->getExtTypes(), TP) |
+           OtherNode->UpdateNodeType(NodeToApply->getExtTypes(), TP);
+  }
+  case SDTCisVTSmallerThanOp: {
+    // The NodeToApply must be a leaf node that is a VT.  OtherOperandNum must
+    // have an integer type that is smaller than the VT.
+    if (!NodeToApply->isLeaf() ||
+        !dynamic_cast<DefInit*>(NodeToApply->getLeafValue()) ||
+        !static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef()
+               ->isSubClassOf("ValueType"))
+      TP.error(N->getOperator()->getName() + " expects a VT operand!");
+    MVT::ValueType VT =
+     getValueType(static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef());
+    if (!MVT::isInteger(VT))
+      TP.error(N->getOperator()->getName() + " VT operand must be integer!");
+    
+    TreePatternNode *OtherNode =
+      getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N,NumResults);
+    
+    // It must be integer.
+    bool MadeChange = false;
+    MadeChange |= OtherNode->UpdateNodeType(MVT::isInt, TP);
+    
+    // This code only handles nodes that have one type set.  Assert here so
+    // that we can change this if we ever need to deal with multiple value
+    // types at this point.
+    assert(OtherNode->getExtTypes().size() == 1 && "Node has too many types!");
+    if (OtherNode->hasTypeSet() && OtherNode->getTypeNum(0) <= VT)
+      OtherNode->UpdateNodeType(MVT::Other, TP);  // Throw an error.
+    return false;
+  }
+  case SDTCisOpSmallerThanOp: {
+    TreePatternNode *BigOperand =
+      getOperandNum(x.SDTCisOpSmallerThanOp_Info.BigOperandNum, N, NumResults);
+
+    // Both operands must be integer or FP, but we don't care which.
+    bool MadeChange = false;
+    
+    // This code does not currently handle nodes which have multiple types,
+    // where some types are integer, and some are fp.  Assert that this is not
+    // the case.
+    assert(!(MVT::isExtIntegerInVTs(NodeToApply->getExtTypes()) &&
+             MVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes())) &&
+           !(MVT::isExtIntegerInVTs(BigOperand->getExtTypes()) &&
+             MVT::isExtFloatingPointInVTs(BigOperand->getExtTypes())) &&
+           "SDTCisOpSmallerThanOp does not handle mixed int/fp types!");
+    if (MVT::isExtIntegerInVTs(NodeToApply->getExtTypes()))
+      MadeChange |= BigOperand->UpdateNodeType(MVT::isInt, TP);
+    else if (MVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes()))
+      MadeChange |= BigOperand->UpdateNodeType(MVT::isFP, TP);
+    if (MVT::isExtIntegerInVTs(BigOperand->getExtTypes()))
+      MadeChange |= NodeToApply->UpdateNodeType(MVT::isInt, TP);
+    else if (MVT::isExtFloatingPointInVTs(BigOperand->getExtTypes()))
+      MadeChange |= NodeToApply->UpdateNodeType(MVT::isFP, TP);
+
+    std::vector<MVT::ValueType> VTs = CGT.getLegalValueTypes();
+    
+    if (MVT::isExtIntegerInVTs(NodeToApply->getExtTypes())) {
+      VTs = FilterVTs(VTs, MVT::isInteger);
+    } else if (MVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes())) {
+      VTs = FilterVTs(VTs, MVT::isFloatingPoint);
+    } else {
+      VTs.clear();
+    }
+
+    switch (VTs.size()) {
+    default:         // Too many VT's to pick from.
+    case 0: break;   // No info yet.
+    case 1: 
+      // Only one VT of this flavor.  Cannot ever satisify the constraints.
+      return NodeToApply->UpdateNodeType(MVT::Other, TP);  // throw
+    case 2:
+      // If we have exactly two possible types, the little operand must be the
+      // small one, the big operand should be the big one.  Common with 
+      // float/double for example.
+      assert(VTs[0] < VTs[1] && "Should be sorted!");
+      MadeChange |= NodeToApply->UpdateNodeType(VTs[0], TP);
+      MadeChange |= BigOperand->UpdateNodeType(VTs[1], TP);
+      break;
+    }    
+    return MadeChange;
+  }
+  case SDTCisIntVectorOfSameSize: {
+    TreePatternNode *OtherOperand =
+      getOperandNum(x.SDTCisIntVectorOfSameSize_Info.OtherOperandNum,
+                    N, NumResults);
+    if (OtherOperand->hasTypeSet()) {
+      if (!MVT::isVector(OtherOperand->getTypeNum(0)))
+        TP.error(N->getOperator()->getName() + " VT operand must be a vector!");
+      MVT::ValueType IVT = OtherOperand->getTypeNum(0);
+      IVT = MVT::getIntVectorWithNumElements(MVT::getVectorNumElements(IVT));
+      return NodeToApply->UpdateNodeType(IVT, TP);
+    }
+    return false;
+  }
+  }  
+  return false;
+}
+
+//===----------------------------------------------------------------------===//
+// SDNodeInfo implementation
+//
+SDNodeInfo::SDNodeInfo(Record *R) : Def(R) {
+  EnumName    = R->getValueAsString("Opcode");
+  SDClassName = R->getValueAsString("SDClass");
+  Record *TypeProfile = R->getValueAsDef("TypeProfile");
+  NumResults = TypeProfile->getValueAsInt("NumResults");
+  NumOperands = TypeProfile->getValueAsInt("NumOperands");
+  
+  // Parse the properties.
+  Properties = 0;
+  std::vector<Record*> PropList = R->getValueAsListOfDefs("Properties");
+  for (unsigned i = 0, e = PropList.size(); i != e; ++i) {
+    if (PropList[i]->getName() == "SDNPCommutative") {
+      Properties |= 1 << SDNPCommutative;
+    } else if (PropList[i]->getName() == "SDNPAssociative") {
+      Properties |= 1 << SDNPAssociative;
+    } else if (PropList[i]->getName() == "SDNPHasChain") {
+      Properties |= 1 << SDNPHasChain;
+    } else if (PropList[i]->getName() == "SDNPOutFlag") {
+      Properties |= 1 << SDNPOutFlag;
+    } else if (PropList[i]->getName() == "SDNPInFlag") {
+      Properties |= 1 << SDNPInFlag;
+    } else if (PropList[i]->getName() == "SDNPOptInFlag") {
+      Properties |= 1 << SDNPOptInFlag;
+    } else {
+      cerr << "Unknown SD Node property '" << PropList[i]->getName()
+           << "' on node '" << R->getName() << "'!\n";
+      exit(1);
+    }
+  }
+  
+  
+  // Parse the type constraints.
+  std::vector<Record*> ConstraintList =
+    TypeProfile->getValueAsListOfDefs("Constraints");
+  TypeConstraints.assign(ConstraintList.begin(), ConstraintList.end());
+}
+
+//===----------------------------------------------------------------------===//
+// TreePatternNode implementation
+//
+
+TreePatternNode::~TreePatternNode() {
+#if 0 // FIXME: implement refcounted tree nodes!
+  for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
+    delete getChild(i);
+#endif
+}
+
+/// 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 returns true if any information was updated.
+///
+bool TreePatternNode::UpdateNodeType(const std::vector<unsigned char> &ExtVTs,
+                                     TreePattern &TP) {
+  assert(!ExtVTs.empty() && "Cannot update node type with empty type vector!");
+  
+  if (ExtVTs[0] == MVT::isUnknown || LHSIsSubsetOfRHS(getExtTypes(), ExtVTs)) 
+    return false;
+  if (isTypeCompletelyUnknown() || LHSIsSubsetOfRHS(ExtVTs, getExtTypes())) {
+    setTypes(ExtVTs);
+    return true;
+  }
+
+  if (getExtTypeNum(0) == MVT::iPTR) {
+    if (ExtVTs[0] == MVT::iPTR || ExtVTs[0] == MVT::isInt)
+      return false;
+    if (MVT::isExtIntegerInVTs(ExtVTs)) {
+      std::vector<unsigned char> FVTs = FilterEVTs(ExtVTs, MVT::isInteger);
+      if (FVTs.size()) {
+        setTypes(ExtVTs);
+        return true;
+      }
+    }
+  }
+  
+  if (ExtVTs[0] == MVT::isInt && MVT::isExtIntegerInVTs(getExtTypes())) {
+    assert(hasTypeSet() && "should be handled above!");
+    std::vector<unsigned char> FVTs = FilterEVTs(getExtTypes(), MVT::isInteger);
+    if (getExtTypes() == FVTs)
+      return false;
+    setTypes(FVTs);
+    return true;
+  }
+  if (ExtVTs[0] == MVT::iPTR && MVT::isExtIntegerInVTs(getExtTypes())) {
+    //assert(hasTypeSet() && "should be handled above!");
+    std::vector<unsigned char> FVTs = FilterEVTs(getExtTypes(), MVT::isInteger);
+    if (getExtTypes() == FVTs)
+      return false;
+    if (FVTs.size()) {
+      setTypes(FVTs);
+      return true;
+    }
+  }      
+  if (ExtVTs[0] == MVT::isFP  && MVT::isExtFloatingPointInVTs(getExtTypes())) {
+    assert(hasTypeSet() && "should be handled above!");
+    std::vector<unsigned char> FVTs =
+      FilterEVTs(getExtTypes(), MVT::isFloatingPoint);
+    if (getExtTypes() == FVTs)
+      return false;
+    setTypes(FVTs);
+    return true;
+  }
+      
+  // If we know this is an int or fp type, and we are told it is a specific one,
+  // take the advice.
+  //
+  // Similarly, we should probably set the type here to the intersection of
+  // {isInt|isFP} and ExtVTs
+  if ((getExtTypeNum(0) == MVT::isInt && MVT::isExtIntegerInVTs(ExtVTs)) ||
+      (getExtTypeNum(0) == MVT::isFP  && MVT::isExtFloatingPointInVTs(ExtVTs))){
+    setTypes(ExtVTs);
+    return true;
+  }
+  if (getExtTypeNum(0) == MVT::isInt && ExtVTs[0] == MVT::iPTR) {
+    setTypes(ExtVTs);
+    return true;
+  }
+
+  if (isLeaf()) {
+    dump();
+    cerr << " ";
+    TP.error("Type inference contradiction found in node!");
+  } else {
+    TP.error("Type inference contradiction found in node " + 
+             getOperator()->getName() + "!");
+  }
+  return true; // unreachable
+}
+
+
+void TreePatternNode::print(std::ostream &OS) const {
+  if (isLeaf()) {
+    OS << *getLeafValue();
+  } else {
+    OS << "(" << getOperator()->getName();
+  }
+  
+  // FIXME: At some point we should handle printing all the value types for 
+  // nodes that are multiply typed.
+  switch (getExtTypeNum(0)) {
+  case MVT::Other: OS << ":Other"; break;
+  case MVT::isInt: OS << ":isInt"; break;
+  case MVT::isFP : OS << ":isFP"; break;
+  case MVT::isUnknown: ; /*OS << ":?";*/ break;
+  case MVT::iPTR:  OS << ":iPTR"; break;
+  default: {
+    std::string VTName = llvm::getName(getTypeNum(0));
+    // Strip off MVT:: prefix if present.
+    if (VTName.substr(0,5) == "MVT::")
+      VTName = VTName.substr(5);
+    OS << ":" << VTName;
+    break;
+  }
+  }
+
+  if (!isLeaf()) {
+    if (getNumChildren() != 0) {
+      OS << " ";
+      getChild(0)->print(OS);
+      for (unsigned i = 1, e = getNumChildren(); i != e; ++i) {
+        OS << ", ";
+        getChild(i)->print(OS);
+      }
+    }
+    OS << ")";
+  }
+  
+  if (!PredicateFn.empty())
+    OS << "<<P:" << PredicateFn << ">>";
+  if (TransformFn)
+    OS << "<<X:" << TransformFn->getName() << ">>";
+  if (!getName().empty())
+    OS << ":$" << getName();
+
+}
+void TreePatternNode::dump() const {
+  print(*cerr.stream());
+}
+
+/// isIsomorphicTo - Return true if this node is recursively isomorphic to
+/// the specified node.  For this comparison, all of the state of the node
+/// is considered, except for the assigned name.  Nodes with differing names
+/// that are otherwise identical are considered isomorphic.
+bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N) const {
+  if (N == this) return true;
+  if (N->isLeaf() != isLeaf() || getExtTypes() != N->getExtTypes() ||
+      getPredicateFn() != N->getPredicateFn() ||
+      getTransformFn() != N->getTransformFn())
+    return false;
+
+  if (isLeaf()) {
+    if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue()))
+      if (DefInit *NDI = dynamic_cast<DefInit*>(N->getLeafValue()))
+        return DI->getDef() == NDI->getDef();
+    return getLeafValue() == N->getLeafValue();
+  }
+  
+  if (N->getOperator() != getOperator() ||
+      N->getNumChildren() != getNumChildren()) return false;
+  for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
+    if (!getChild(i)->isIsomorphicTo(N->getChild(i)))
+      return false;
+  return true;
+}
+
+/// clone - Make a copy of this tree and all of its children.
+///
+TreePatternNode *TreePatternNode::clone() const {
+  TreePatternNode *New;
+  if (isLeaf()) {
+    New = new TreePatternNode(getLeafValue());
+  } else {
+    std::vector<TreePatternNode*> CChildren;
+    CChildren.reserve(Children.size());
+    for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
+      CChildren.push_back(getChild(i)->clone());
+    New = new TreePatternNode(getOperator(), CChildren);
+  }
+  New->setName(getName());
+  New->setTypes(getExtTypes());
+  New->setPredicateFn(getPredicateFn());
+  New->setTransformFn(getTransformFn());
+  return New;
+}
+
+/// SubstituteFormalArguments - Replace the formal arguments in this tree
+/// with actual values specified by ArgMap.
+void TreePatternNode::
+SubstituteFormalArguments(std::map<std::string, TreePatternNode*> &ArgMap) {
+  if (isLeaf()) return;
+  
+  for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
+    TreePatternNode *Child = getChild(i);
+    if (Child->isLeaf()) {
+      Init *Val = Child->getLeafValue();
+      if (dynamic_cast<DefInit*>(Val) &&
+          static_cast<DefInit*>(Val)->getDef()->getName() == "node") {
+        // We found a use of a formal argument, replace it with its value.
+        Child = ArgMap[Child->getName()];
+        assert(Child && "Couldn't find formal argument!");
+        setChild(i, Child);
+      }
+    } else {
+      getChild(i)->SubstituteFormalArguments(ArgMap);
+    }
+  }
+}
+
+
+/// InlinePatternFragments - If this pattern refers to any pattern
+/// fragments, inline them into place, giving us a pattern without any
+/// PatFrag references.
+TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) {
+  if (isLeaf()) return this;  // nothing to do.
+  Record *Op = getOperator();
+  
+  if (!Op->isSubClassOf("PatFrag")) {
+    // Just recursively inline children nodes.
+    for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
+      setChild(i, getChild(i)->InlinePatternFragments(TP));
+    return this;
+  }
+
+  // Otherwise, we found a reference to a fragment.  First, look up its
+  // TreePattern record.
+  TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op);
+  
+  // Verify that we are passing the right number of operands.
+  if (Frag->getNumArgs() != Children.size())
+    TP.error("'" + Op->getName() + "' fragment requires " +
+             utostr(Frag->getNumArgs()) + " operands!");
+
+  TreePatternNode *FragTree = Frag->getOnlyTree()->clone();
+
+  // Resolve formal arguments to their actual value.
+  if (Frag->getNumArgs()) {
+    // Compute the map of formal to actual arguments.
+    std::map<std::string, TreePatternNode*> ArgMap;
+    for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i)
+      ArgMap[Frag->getArgName(i)] = getChild(i)->InlinePatternFragments(TP);
+  
+    FragTree->SubstituteFormalArguments(ArgMap);
+  }
+  
+  FragTree->setName(getName());
+  FragTree->UpdateNodeType(getExtTypes(), TP);
+  
+  // Get a new copy of this fragment to stitch into here.
+  //delete this;    // FIXME: implement refcounting!
+  return FragTree;
+}
+
+/// getImplicitType - Check to see if the specified record has an implicit
+/// type which should be applied to it.  This infer the type of register
+/// references from the register file information, for example.
+///
+static std::vector<unsigned char> getImplicitType(Record *R, bool NotRegisters,
+                                      TreePattern &TP) {
+  // Some common return values
+  std::vector<unsigned char> Unknown(1, MVT::isUnknown);
+  std::vector<unsigned char> Other(1, MVT::Other);
+
+  // Check to see if this is a register or a register class...
+  if (R->isSubClassOf("RegisterClass")) {
+    if (NotRegisters) 
+      return Unknown;
+    const CodeGenRegisterClass &RC = 
+      TP.getDAGPatterns().getTargetInfo().getRegisterClass(R);
+    return ConvertVTs(RC.getValueTypes());
+  } else if (R->isSubClassOf("PatFrag")) {
+    // Pattern fragment types will be resolved when they are inlined.
+    return Unknown;
+  } else if (R->isSubClassOf("Register")) {
+    if (NotRegisters) 
+      return Unknown;
+    const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();
+    return T.getRegisterVTs(R);
+  } else if (R->isSubClassOf("ValueType") || R->isSubClassOf("CondCode")) {
+    // Using a VTSDNode or CondCodeSDNode.
+    return Other;
+  } else if (R->isSubClassOf("ComplexPattern")) {
+    if (NotRegisters) 
+      return Unknown;
+    std::vector<unsigned char>
+    ComplexPat(1, TP.getDAGPatterns().getComplexPattern(R).getValueType());
+    return ComplexPat;
+  } else if (R->getName() == "ptr_rc") {
+    Other[0] = MVT::iPTR;
+    return Other;
+  } else if (R->getName() == "node" || R->getName() == "srcvalue" ||
+             R->getName() == "zero_reg") {
+    // Placeholder.
+    return Unknown;
+  }
+  
+  TP.error("Unknown node flavor used in pattern: " + R->getName());
+  return Other;
+}
+
+/// ApplyTypeConstraints - Apply all of the type constraints relevent to
+/// this node and its children in the tree.  This returns true if it makes a
+/// change, false otherwise.  If a type contradiction is found, throw an
+/// exception.
+bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) {
+  CodegenDAGPatterns &CDP = TP.getDAGPatterns();
+  if (isLeaf()) {
+    if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue())) {
+      // If it's a regclass or something else known, include the type.
+      return UpdateNodeType(getImplicitType(DI->getDef(), NotRegisters, TP),TP);
+    } else if (IntInit *II = dynamic_cast<IntInit*>(getLeafValue())) {
+      // Int inits are always integers. :)
+      bool MadeChange = UpdateNodeType(MVT::isInt, TP);
+      
+      if (hasTypeSet()) {
+        // At some point, it may make sense for this tree pattern to have
+        // multiple types.  Assert here that it does not, so we revisit this
+        // code when appropriate.
+        assert(getExtTypes().size() >= 1 && "TreePattern doesn't have a type!");
+        MVT::ValueType VT = getTypeNum(0);
+        for (unsigned i = 1, e = getExtTypes().size(); i != e; ++i)
+          assert(getTypeNum(i) == VT && "TreePattern has too many types!");
+        
+        VT = getTypeNum(0);
+        if (VT != MVT::iPTR) {
+          unsigned Size = MVT::getSizeInBits(VT);
+          // Make sure that the value is representable for this type.
+          if (Size < 32) {
+            int Val = (II->getValue() << (32-Size)) >> (32-Size);
+            if (Val != II->getValue())
+              TP.error("Sign-extended integer value '" + itostr(II->getValue())+
+                       "' is out of range for type '" + 
+                       getEnumName(getTypeNum(0)) + "'!");
+          }
+        }
+      }
+      
+      return MadeChange;
+    }
+    return false;
+  }
+  
+  // special handling for set, which isn't really an SDNode.
+  if (getOperator()->getName() == "set") {
+    assert (getNumChildren() >= 2 && "Missing RHS of a set?");
+    unsigned NC = getNumChildren();
+    bool MadeChange = false;
+    for (unsigned i = 0; i < NC-1; ++i) {
+      MadeChange = getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
+      MadeChange |= getChild(NC-1)->ApplyTypeConstraints(TP, NotRegisters);
+    
+      // Types of operands must match.
+      MadeChange |= getChild(i)->UpdateNodeType(getChild(NC-1)->getExtTypes(),
+                                                TP);
+      MadeChange |= getChild(NC-1)->UpdateNodeType(getChild(i)->getExtTypes(),
+                                                   TP);
+      MadeChange |= UpdateNodeType(MVT::isVoid, TP);
+    }
+    return MadeChange;
+  } else if (getOperator()->getName() == "implicit" ||
+             getOperator()->getName() == "parallel") {
+    bool MadeChange = false;
+    for (unsigned i = 0; i < getNumChildren(); ++i)
+      MadeChange = getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
+    MadeChange |= UpdateNodeType(MVT::isVoid, TP);
+    return MadeChange;
+  } else if (getOperator() == CDP.get_intrinsic_void_sdnode() ||
+             getOperator() == CDP.get_intrinsic_w_chain_sdnode() ||
+             getOperator() == CDP.get_intrinsic_wo_chain_sdnode()) {
+    unsigned IID = 
+    dynamic_cast<IntInit*>(getChild(0)->getLeafValue())->getValue();
+    const CodeGenIntrinsic &Int = CDP.getIntrinsicInfo(IID);
+    bool MadeChange = false;
+    
+    // Apply the result type to the node.
+    MadeChange = UpdateNodeType(Int.ArgVTs[0], TP);
+    
+    if (getNumChildren() != Int.ArgVTs.size())
+      TP.error("Intrinsic '" + Int.Name + "' expects " +
+               utostr(Int.ArgVTs.size()-1) + " operands, not " +
+               utostr(getNumChildren()-1) + " operands!");
+
+    // Apply type info to the intrinsic ID.
+    MadeChange |= getChild(0)->UpdateNodeType(MVT::iPTR, TP);
+    
+    for (unsigned i = 1, e = getNumChildren(); i != e; ++i) {
+      MVT::ValueType OpVT = Int.ArgVTs[i];
+      MadeChange |= getChild(i)->UpdateNodeType(OpVT, TP);
+      MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
+    }
+    return MadeChange;
+  } else if (getOperator()->isSubClassOf("SDNode")) {
+    const SDNodeInfo &NI = CDP.getSDNodeInfo(getOperator());
+    
+    bool MadeChange = NI.ApplyTypeConstraints(this, TP);
+    for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
+      MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
+    // Branch, etc. do not produce results and top-level forms in instr pattern
+    // must have void types.
+    if (NI.getNumResults() == 0)
+      MadeChange |= UpdateNodeType(MVT::isVoid, TP);
+    
+    // If this is a vector_shuffle operation, apply types to the build_vector
+    // operation.  The types of the integers don't matter, but this ensures they
+    // won't get checked.
+    if (getOperator()->getName() == "vector_shuffle" &&
+        getChild(2)->getOperator()->getName() == "build_vector") {
+      TreePatternNode *BV = getChild(2);
+      const std::vector<MVT::ValueType> &LegalVTs
+        = CDP.getTargetInfo().getLegalValueTypes();
+      MVT::ValueType LegalIntVT = MVT::Other;
+      for (unsigned i = 0, e = LegalVTs.size(); i != e; ++i)
+        if (MVT::isInteger(LegalVTs[i]) && !MVT::isVector(LegalVTs[i])) {
+          LegalIntVT = LegalVTs[i];
+          break;
+        }
+      assert(LegalIntVT != MVT::Other && "No legal integer VT?");
+            
+      for (unsigned i = 0, e = BV->getNumChildren(); i != e; ++i)
+        MadeChange |= BV->getChild(i)->UpdateNodeType(LegalIntVT, TP);
+    }
+    return MadeChange;  
+  } else if (getOperator()->isSubClassOf("Instruction")) {
+    const DAGInstruction &Inst = CDP.getInstruction(getOperator());
+    bool MadeChange = false;
+    unsigned NumResults = Inst.getNumResults();
+    
+    assert(NumResults <= 1 &&
+           "Only supports zero or one result instrs!");
+
+    CodeGenInstruction &InstInfo =
+      CDP.getTargetInfo().getInstruction(getOperator()->getName());
+    // Apply the result type to the node
+    if (NumResults == 0 || InstInfo.NumDefs == 0) {
+      MadeChange = UpdateNodeType(MVT::isVoid, TP);
+    } else {
+      Record *ResultNode = Inst.getResult(0);
+      
+      if (ResultNode->getName() == "ptr_rc") {
+        std::vector<unsigned char> VT;
+        VT.push_back(MVT::iPTR);
+        MadeChange = UpdateNodeType(VT, TP);
+      } else {
+        assert(ResultNode->isSubClassOf("RegisterClass") &&
+               "Operands should be register classes!");
+
+        const CodeGenRegisterClass &RC = 
+          CDP.getTargetInfo().getRegisterClass(ResultNode);
+        MadeChange = UpdateNodeType(ConvertVTs(RC.getValueTypes()), TP);
+      }
+    }
+
+    unsigned ChildNo = 0;
+    for (unsigned i = 0, e = Inst.getNumOperands(); i != e; ++i) {
+      Record *OperandNode = Inst.getOperand(i);
+      
+      // If the instruction expects a predicate or optional def operand, we
+      // codegen this by setting the operand to it's default value if it has a
+      // non-empty DefaultOps field.
+      if ((OperandNode->isSubClassOf("PredicateOperand") ||
+           OperandNode->isSubClassOf("OptionalDefOperand")) &&
+          !CDP.getDefaultOperand(OperandNode).DefaultOps.empty())
+        continue;
+       
+      // Verify that we didn't run out of provided operands.
+      if (ChildNo >= getNumChildren())
+        TP.error("Instruction '" + getOperator()->getName() +
+                 "' expects more operands than were provided.");
+      
+      MVT::ValueType VT;
+      TreePatternNode *Child = getChild(ChildNo++);
+      if (OperandNode->isSubClassOf("RegisterClass")) {
+        const CodeGenRegisterClass &RC = 
+          CDP.getTargetInfo().getRegisterClass(OperandNode);
+        MadeChange |= Child->UpdateNodeType(ConvertVTs(RC.getValueTypes()), TP);
+      } else if (OperandNode->isSubClassOf("Operand")) {
+        VT = getValueType(OperandNode->getValueAsDef("Type"));
+        MadeChange |= Child->UpdateNodeType(VT, TP);
+      } else if (OperandNode->getName() == "ptr_rc") {
+        MadeChange |= Child->UpdateNodeType(MVT::iPTR, TP);
+      } else {
+        assert(0 && "Unknown operand type!");
+        abort();
+      }
+      MadeChange |= Child->ApplyTypeConstraints(TP, NotRegisters);
+    }
+    
+    if (ChildNo != getNumChildren())
+      TP.error("Instruction '" + getOperator()->getName() +
+               "' was provided too many operands!");
+    
+    return MadeChange;
+  } else {
+    assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!");
+    
+    // Node transforms always take one operand.
+    if (getNumChildren() != 1)
+      TP.error("Node transform '" + getOperator()->getName() +
+               "' requires one operand!");
+
+    // If either the output or input of the xform does not have exact
+    // type info. We assume they must be the same. Otherwise, it is perfectly
+    // legal to transform from one type to a completely different type.
+    if (!hasTypeSet() || !getChild(0)->hasTypeSet()) {
+      bool MadeChange = UpdateNodeType(getChild(0)->getExtTypes(), TP);
+      MadeChange |= getChild(0)->UpdateNodeType(getExtTypes(), TP);
+      return MadeChange;
+    }
+    return false;
+  }
+}
+
+/// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the
+/// RHS of a commutative operation, not the on LHS.
+static bool OnlyOnRHSOfCommutative(TreePatternNode *N) {
+  if (!N->isLeaf() && N->getOperator()->getName() == "imm")
+    return true;
+  if (N->isLeaf() && dynamic_cast<IntInit*>(N->getLeafValue()))
+    return true;
+  return false;
+}
+
+
+/// canPatternMatch - If it is impossible for this pattern to match on this
+/// target, fill in Reason and return false.  Otherwise, return true.  This is
+/// used as a santity check for .td files (to prevent people from writing stuff
+/// that can never possibly work), and to prevent the pattern permuter from
+/// generating stuff that is useless.
+bool TreePatternNode::canPatternMatch(std::string &Reason, 
+                                      CodegenDAGPatterns &CDP){
+  if (isLeaf()) return true;
+
+  for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
+    if (!getChild(i)->canPatternMatch(Reason, CDP))
+      return false;
+
+  // If this is an intrinsic, handle cases that would make it not match.  For
+  // example, if an operand is required to be an immediate.
+  if (getOperator()->isSubClassOf("Intrinsic")) {
+    // TODO:
+    return true;
+  }
+  
+  // If this node is a commutative operator, check that the LHS isn't an
+  // immediate.
+  const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(getOperator());
+  if (NodeInfo.hasProperty(SDNPCommutative)) {
+    // Scan all of the operands of the node and make sure that only the last one
+    // is a constant node, unless the RHS also is.
+    if (!OnlyOnRHSOfCommutative(getChild(getNumChildren()-1))) {
+      for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i)
+        if (OnlyOnRHSOfCommutative(getChild(i))) {
+          Reason="Immediate value must be on the RHS of commutative operators!";
+          return false;
+        }
+    }
+  }
+  
+  return true;
+}