TableGen: permit non-leaf ComplexPattern uses

This allows the results of a ComplexPattern check to be distributed to separate
named Operands, instead of the current system where all results must apply (and
match perfectly) with a single Operand.

For example, if "some_addrmode" is a ComplexPattern producing two results, you
can write:

   def : Pat<(load (some_addrmode GPR64:$base, imm:$offset)),
             (INST GPR64:$base, imm:$offset)>;

This should allow neater instruction definitions in TableGen that don't put all
possible aspects of addressing into a single operand, but are still usable with
relatively simple C++ CodeGen idioms.

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

3 files changed, 165 insertions, 56 deletions

diff --git a/utils/TableGen/CodeGenDAGPatterns.cpp b/utils/TableGen/CodeGenDAGPatterns.cpp
index e003dc8322..1636fb4233 100644
--- a/utils/TableGen/CodeGenDAGPatterns.cpp
+++ b/utils/TableGen/CodeGenDAGPatterns.cpp
@@ -738,9 +738,13 @@ static unsigned getPatternSize(const TreePatternNode *P,
   // specified. To get best possible pattern match we'll need to dynamically
   // calculate the complexity of all patterns a dag can potentially map to.
   const ComplexPattern *AM = P->getComplexPatternInfo(CGP);
-  if (AM)
+  if (AM) {
     Size += AM->getNumOperands() * 3;
 
+    // We don't want to count any children twice, so return early.
+    return Size;
+  }
+
   // If this node has some predicate function that must match, it adds to the
   // complexity of this node.
   if (!P->getPredicateFns().empty())
@@ -1122,6 +1126,9 @@ static unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) {
   if (Operator->isSubClassOf("ValueType"))
     return 1;  // A type-cast of one result.
 
+  if (Operator->isSubClassOf("ComplexPattern"))
+    return 1;
+
   Operator->dump();
   errs() << "Unhandled node in GetNumNodeResults\n";
   exit(1);
@@ -1425,6 +1432,9 @@ static EEVT::TypeSet getImplicitType(Record *R, unsigned ResNo,
     return EEVT::TypeSet(); // Unknown.
   }
 
+  if (R->isSubClassOf("Operand"))
+    return EEVT::TypeSet(getValueType(R->getValueAsDef("Type")));
+
   TP.error("Unknown node flavor used in pattern: " + R->getName());
   return EEVT::TypeSet(MVT::Other, TP);
 }
@@ -1447,12 +1457,37 @@ getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const {
 /// return the ComplexPattern information, otherwise return null.
 const ComplexPattern *
 TreePatternNode::getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const {
-  if (!isLeaf()) return nullptr;
+  Record *Rec;
+  if (isLeaf()) {
+    DefInit *DI = dyn_cast<DefInit>(getLeafValue());
+    if (!DI)
+      return nullptr;
+    Rec = DI->getDef();
+  } else
+    Rec = getOperator();
+
+  if (!Rec->isSubClassOf("ComplexPattern"))
+    return nullptr;
+  return &CGP.getComplexPattern(Rec);
+}
+
+unsigned TreePatternNode::getNumMIResults(const CodeGenDAGPatterns &CGP) const {
+  // A ComplexPattern specifically declares how many results it fills in.
+  if (const ComplexPattern *CP = getComplexPatternInfo(CGP))
+    return CP->getNumOperands();
+
+  // If MIOperandInfo is specified, that gives the count.
+  if (isLeaf()) {
+    DefInit *DI = dyn_cast<DefInit>(getLeafValue());
+    if (DI && DI->getDef()->isSubClassOf("Operand")) {
+      DagInit *MIOps = DI->getDef()->getValueAsDag("MIOperandInfo");
+      if (MIOps->getNumArgs())
+        return MIOps->getNumArgs();
+    }
+  }
 
-  DefInit *DI = dyn_cast<DefInit>(getLeafValue());
-  if (DI && DI->getDef()->isSubClassOf("ComplexPattern"))
-    return &CGP.getComplexPattern(DI->getDef());
-  return nullptr;
+  // Otherwise there is just one result.
+  return 1;
 }
 
 /// NodeHasProperty - Return true if this node has the specified property.
@@ -1725,6 +1760,15 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) {
     return MadeChange;
   }
 
+  if (getOperator()->isSubClassOf("ComplexPattern")) {
+    bool MadeChange = false;
+
+    for (unsigned i = 0; i < getNumChildren(); ++i)
+      MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
+
+    return MadeChange;
+  }
+
   assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!");
 
   // Node transforms always take one operand.
@@ -1781,6 +1825,9 @@ bool TreePatternNode::canPatternMatch(std::string &Reason,
     return true;
   }
 
+  if (getOperator()->isSubClassOf("ComplexPattern"))
+    return true;
+
   // If this node is a commutative operator, check that the LHS isn't an
   // immediate.
   const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(getOperator());
@@ -1927,6 +1974,7 @@ TreePatternNode *TreePattern::ParseTreePattern(Init *TheInit, StringRef OpName){
       !Operator->isSubClassOf("Instruction") &&
       !Operator->isSubClassOf("SDNodeXForm") &&
       !Operator->isSubClassOf("Intrinsic") &&
+      !Operator->isSubClassOf("ComplexPattern") &&
       Operator->getName() != "set" &&
       Operator->getName() != "implicit")
     error("Unrecognized node '" + Operator->getName() + "'!");
@@ -1982,6 +2030,27 @@ TreePatternNode *TreePattern::ParseTreePattern(Init *TheInit, StringRef OpName){
     Children.insert(Children.begin(), IIDNode);
   }
 
+  if (Operator->isSubClassOf("ComplexPattern")) {
+    for (unsigned i = 0; i < Children.size(); ++i) {
+      TreePatternNode *Child = Children[i];
+
+      if (Child->getName().empty())
+        error("All arguments to a ComplexPattern must be named");
+
+      // Check that the ComplexPattern uses are consistent: "(MY_PAT $a, $b)"
+      // and "(MY_PAT $b, $a)" should not be allowed in the same pattern;
+      // neither should "(MY_PAT_1 $a, $b)" and "(MY_PAT_2 $a, $b)".
+      auto OperandId = std::make_pair(Operator, i);
+      auto PrevOp = ComplexPatternOperands.find(Child->getName());
+      if (PrevOp != ComplexPatternOperands.end()) {
+        if (PrevOp->getValue() != OperandId)
+          error("All ComplexPattern operands must appear consistently: "
+                "in the same order in just one ComplexPattern instance.");
+      } else
+        ComplexPatternOperands[Child->getName()] = OperandId;
+    }
+  }
+
   unsigned NumResults = GetNumNodeResults(Operator, CDP);
   TreePatternNode *Result = new TreePatternNode(Operator, Children, NumResults);
   Result->setName(OpName);
@@ -2553,14 +2622,11 @@ public:
       return;
     }
 
-    // Get information about the SDNode for the operator.
-    const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N->getOperator());
-
     // Notice properties of the node.
-    if (OpInfo.hasProperty(SDNPMayStore)) mayStore = true;
-    if (OpInfo.hasProperty(SDNPMayLoad)) mayLoad = true;
-    if (OpInfo.hasProperty(SDNPSideEffect)) hasSideEffects = true;
-    if (OpInfo.hasProperty(SDNPVariadic)) isVariadic = true;
+    if (N->NodeHasProperty(SDNPMayStore, CDP)) mayStore = true;
+    if (N->NodeHasProperty(SDNPMayLoad, CDP)) mayLoad = true;
+    if (N->NodeHasProperty(SDNPSideEffect, CDP)) hasSideEffects = true;
+    if (N->NodeHasProperty(SDNPVariadic, CDP)) isVariadic = true;
 
     if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) {
       // If this is an intrinsic, analyze it.
@@ -3434,8 +3500,8 @@ static void GenerateVariantsOf(TreePatternNode *N,
                                std::vector<TreePatternNode*> &OutVariants,
                                CodeGenDAGPatterns &CDP,
                                const MultipleUseVarSet &DepVars) {
-  // We cannot permute leaves.
-  if (N->isLeaf()) {
+  // We cannot permute leaves or ComplexPattern uses.
+  if (N->isLeaf() || N->getOperator()->isSubClassOf("ComplexPattern")) {
     OutVariants.push_back(N);
     return;
   }
diff --git a/utils/TableGen/CodeGenDAGPatterns.h b/utils/TableGen/CodeGenDAGPatterns.h
index 59b3dbec04..fb30cdd948 100644
--- a/utils/TableGen/CodeGenDAGPatterns.h
+++ b/utils/TableGen/CodeGenDAGPatterns.h
@@ -409,6 +409,12 @@ public:
   const ComplexPattern *
   getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const;
 
+  /// Returns the number of MachineInstr operands that would be produced by this
+  /// node if it mapped directly to an output Instruction's
+  /// operand. ComplexPattern specifies this explicitly; MIOperandInfo gives it
+  /// for Operands; otherwise 1.
+  unsigned getNumMIResults(const CodeGenDAGPatterns &CGP) const;
+
   /// NodeHasProperty - Return true if this node has the specified property.
   bool NodeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const;
 
@@ -527,6 +533,13 @@ class TreePattern {
   /// hasError - True if the currently processed nodes have unresolvable types
   /// or other non-fatal errors
   bool HasError;
+
+  /// It's important that the usage of operands in ComplexPatterns is
+  /// consistent: each named operand can be defined by at most one
+  /// ComplexPattern. This records the ComplexPattern instance and the operand
+  /// number for each operand encountered in a ComplexPattern to aid in that
+  /// check.
+  StringMap<std::pair<Record *, unsigned>> ComplexPatternOperands;
 public:
 
   /// TreePattern constructor - Parse the specified DagInits into the
diff --git a/utils/TableGen/DAGISelMatcherGen.cpp b/utils/TableGen/DAGISelMatcherGen.cpp
index b45e3eadea..97e37ba689 100644
--- a/utils/TableGen/DAGISelMatcherGen.cpp
+++ b/utils/TableGen/DAGISelMatcherGen.cpp
@@ -62,6 +62,13 @@ namespace {
     /// insertion easier.
     StringMap<unsigned> VariableMap;
 
+    /// This maintains the recorded operand number that OPC_CheckComplexPattern
+    /// drops each sub-operand into. We don't want to insert these into
+    /// VariableMap because that leads to identity checking if they are
+    /// encountered multiple times. Biased by 1 like VariableMap for
+    /// consistency.
+    StringMap<unsigned> NamedComplexPatternOperands;
+
     /// NextRecordedOperandNo - As we emit opcodes to record matched values in
     /// the RecordedNodes array, this keeps track of which slot will be next to
     /// record into.
@@ -76,10 +83,8 @@ namespace {
     SmallVector<unsigned, 2> MatchedGlueResultNodes;
 
     /// MatchedComplexPatterns - This maintains a list of all of the
-    /// ComplexPatterns that we need to check.  The patterns are known to have
-    /// names which were recorded.  The second element of each pair is the first
-    /// slot number that the OPC_CheckComplexPat opcode drops the matched
-    /// results into.
+    /// ComplexPatterns that we need to check. The second element of each pair
+    /// is the recorded operand number of the input node.
     SmallVector<std::pair<const TreePatternNode*,
                           unsigned>, 2> MatchedComplexPatterns;
 
@@ -115,6 +120,11 @@ namespace {
     void EmitOperatorMatchCode(const TreePatternNode *N,
                                TreePatternNode *NodeNoTypes);
 
+    /// If this is the first time a node with unique identifier Name has been
+    /// seen, record it. Otherwise, emit a check to make sure this is the same
+    /// node. Returns true if this is the first encounter.
+    bool recordUniqueNode(std::string Name);
+
     // Result Code Generation.
     unsigned getNamedArgumentSlot(StringRef Name) {
       unsigned VarMapEntry = VariableMap[Name];
@@ -266,7 +276,8 @@ void MatcherGen::EmitLeafMatchCode(const TreePatternNode *N) {
 
     // Remember this ComplexPattern so that we can emit it after all the other
     // structural matches are done.
-    MatchedComplexPatterns.push_back(std::make_pair(N, 0));
+    unsigned InputOperand = VariableMap[N->getName()] - 1;
+    MatchedComplexPatterns.push_back(std::make_pair(N, InputOperand));
     return;
   }
 
@@ -277,6 +288,25 @@ void MatcherGen::EmitLeafMatchCode(const TreePatternNode *N) {
 void MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N,
                                        TreePatternNode *NodeNoTypes) {
   assert(!N->isLeaf() && "Not an operator?");
+
+  if (N->getOperator()->isSubClassOf("ComplexPattern")) {
+    // The "name" of a non-leaf complex pattern (MY_PAT $op1, $op2) is
+    // "MY_PAT:op1:op2". We should already have validated that the uses are
+    // consistent.
+    std::string PatternName = N->getOperator()->getName();
+    for (unsigned i = 0; i < N->getNumChildren(); ++i) {
+      PatternName += ":";
+      PatternName += N->getChild(i)->getName();
+    }
+
+    if (recordUniqueNode(PatternName)) {
+      auto NodeAndOpNum = std::make_pair(N, NextRecordedOperandNo - 1);
+      MatchedComplexPatterns.push_back(NodeAndOpNum);
+    }
+
+    return;
+  }
+
   const SDNodeInfo &CInfo = CGP.getSDNodeInfo(N->getOperator());
 
   // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is
@@ -415,6 +445,22 @@ void MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N,
   }
 }
 
+bool MatcherGen::recordUniqueNode(std::string Name) {
+  unsigned &VarMapEntry = VariableMap[Name];
+  if (VarMapEntry == 0) {
+    // If it is a named node, we must emit a 'Record' opcode.
+    AddMatcher(new RecordMatcher("$" + Name, NextRecordedOperandNo));
+    VarMapEntry = ++NextRecordedOperandNo;
+    return true;
+  }
+
+  // If we get here, this is a second reference to a specific name.  Since
+  // we already have checked that the first reference is valid, we don't
+  // have to recursively match it, just check that it's the same as the
+  // previously named thing.
+  AddMatcher(new CheckSameMatcher(VarMapEntry-1));
+  return false;
+}
 
 void MatcherGen::EmitMatchCode(const TreePatternNode *N,
                                TreePatternNode *NodeNoTypes) {
@@ -432,21 +478,9 @@ void MatcherGen::EmitMatchCode(const TreePatternNode *N,
 
   // If this node has a name associated with it, capture it in VariableMap. If
   // we already saw this in the pattern, emit code to verify dagness.
-  if (!N->getName().empty()) {
-    unsigned &VarMapEntry = VariableMap[N->getName()];
-    if (VarMapEntry == 0) {
-      // If it is a named node, we must emit a 'Record' opcode.
-      AddMatcher(new RecordMatcher("$" + N->getName(), NextRecordedOperandNo));
-      VarMapEntry = ++NextRecordedOperandNo;
-    } else {
-      // If we get here, this is a second reference to a specific name.  Since
-      // we already have checked that the first reference is valid, we don't
-      // have to recursively match it, just check that it's the same as the
-      // previously named thing.
-      AddMatcher(new CheckSameMatcher(VarMapEntry-1));
+  if (!N->getName().empty())
+    if (!recordUniqueNode(N->getName()))
       return;
-    }
-  }
 
   if (N->isLeaf())
     EmitLeafMatchCode(N);
@@ -497,16 +531,20 @@ bool MatcherGen::EmitMatcherCode(unsigned Variant) {
     const TreePatternNode *N = MatchedComplexPatterns[i].first;
 
     // Remember where the results of this match get stuck.
-    MatchedComplexPatterns[i].second = NextRecordedOperandNo;
+    if (N->isLeaf()) {
+      NamedComplexPatternOperands[N->getName()] = NextRecordedOperandNo + 1;
+    } else {
+      unsigned CurOp = NextRecordedOperandNo;
+      for (unsigned i = 0; i < N->getNumChildren(); ++i) {
+        NamedComplexPatternOperands[N->getChild(i)->getName()] = CurOp + 1;
+        CurOp += N->getChild(i)->getNumMIResults(CGP);
+      }
+    }
 
     // Get the slot we recorded the value in from the name on the node.
-    unsigned RecNodeEntry = VariableMap[N->getName()];
-    assert(!N->getName().empty() && RecNodeEntry &&
-           "Complex pattern should have a name and slot");
-    --RecNodeEntry;  // Entries in VariableMap are biased.
+    unsigned RecNodeEntry = MatchedComplexPatterns[i].second;
 
-    const ComplexPattern &CP =
-      CGP.getComplexPattern(((DefInit*)N->getLeafValue())->getDef());
+    const ComplexPattern &CP = *N->getComplexPatternInfo(CGP);
 
     // Emit a CheckComplexPat operation, which does the match (aborting if it
     // fails) and pushes the matched operands onto the recorded nodes list.
@@ -543,21 +581,12 @@ void MatcherGen::EmitResultOfNamedOperand(const TreePatternNode *N,
                                           SmallVectorImpl<unsigned> &ResultOps){
   assert(!N->getName().empty() && "Operand not named!");
 
-  // A reference to a complex pattern gets all of the results of the complex
-  // pattern's match.
-  if (const ComplexPattern *CP = N->getComplexPatternInfo(CGP)) {
-    unsigned SlotNo = 0;
-    for (unsigned i = 0, e = MatchedComplexPatterns.size(); i != e; ++i)
-      if (MatchedComplexPatterns[i].first->getName() == N->getName()) {
-        SlotNo = MatchedComplexPatterns[i].second;
-        break;
-      }
-    assert(SlotNo != 0 && "Didn't get a slot number assigned?");
+  if (unsigned SlotNo = NamedComplexPatternOperands[N->getName()]) {
+    // Complex operands have already been completely selected, just find the
+    // right slot ant add the arguments directly.
+    for (unsigned i = 0; i < N->getNumMIResults(CGP); ++i)
+      ResultOps.push_back(SlotNo - 1 + i);
 
-    // The first slot entry is the node itself, the subsequent entries are the
-    // matched values.
-    for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i)
-      ResultOps.push_back(SlotNo+i);
     return;
   }
 
@@ -575,7 +604,8 @@ void MatcherGen::EmitResultOfNamedOperand(const TreePatternNode *N,
     }
   }
 
-  ResultOps.push_back(SlotNo);
+  for (unsigned i = 0; i < N->getNumMIResults(CGP); ++i)
+    ResultOps.push_back(SlotNo + i);
 }
 
 void MatcherGen::EmitResultLeafAsOperand(const TreePatternNode *N,