TableGen: allow non-leaf ComplexPatterns

[t.p.northover]

Summary

Hi,

The attached patch is a first step to (hopefully) using less monolithic "ADDRESS!!!" operands for load/store operations on ARM64 while still allowing C++ selection (to avoid AArch64's TableGen pattern nightmare).

The idea is that instead of just being able to use ComplexPatterns as leaf nodes (e.g. "my_pat:$address") you can specify how the results map to named operands on a finer level: "(my_pat GPR64:$base, imm:$offset)".

I believe the only XYZGenDAGISel.inc changed by this patch is the Hexagon one, and looking at the file its changes appear sensible.

The Hexagon change is actually a bugfix that this code revealed, but serves as a reasonable example for the code: what *was* happening was that the Hexagon result instructions were getting the ComplexPattern *input* and a newly-materialized "0" as an operand: the ComplexPattern results were being ignored completely. Since the ComplexPatterns were so trivial this didn't actually affect any output, but it was fairly clearly not intended.

So how does it look?

Cheers.

Tim.

[adasgupt]

Thanks for identifying the bug and providing a fix, Tim. We'll take a look at the Hexagon bugfix.

[jverma]

def : Pat <(stOp (OpNode (ldOp (addrPred IntRegs:$addr, extPred:$offset)),
                         immPred:$bitend),
                 (addrPred (i32 IntRegs:$addr), extPred:$offset)),
           (MI IntRegs:$addr, extPred:$offset, (xformFunc immPred:$bitend))>;

}

Hi Tim,

Your patch seems to be doing the right thing. However, I still don't understand the implication of your change on the complex patterns, SelectADDRriU6_[0-2], defined in HexagonISelDAGToDAG.cpp. Can you please explain it a little?

Thanks,
Jyotsna

[t.p.northover]

Hi Jyotsna,

Your patch seems to be doing the right thing. However, I still don't understand the
implication of your change on the complex patterns, SelectADDRriU6_[0-2],
defined in HexagonISelDAGToDAG.cpp. Can you please explain it a little?

Sure, suppose someone changed (say) SelectADDRriU2_0(SDValue Addr,
SDValue &Base, SDValue &Offset) so that it examined Addr, looking for
something like (add IntRegs:$base, imm:$offset) and set the Base &
Offset references appropriately.

At the moment what would happen is that a (MemOPw_ADDr_V4 Addr, 0,
whatever) node would be produced. Addr would then go through a second
round of selection (even though SelectADDRriU2_0 had already dealt
with it), leading to multiple instructions and assembly looking like:

r0 = Base + Offset
mem(r0+#0) += whatever

(this won't actually be seen now, because you have a *real* pattern
that looks for "(add IntRegs:$base, extPred:$offset)" and has a higher
complexity so it gets tried first, but imagine some other cunning ruse
by SelectADDRriU2_0 to simplify things).

What I think you'd want to happen instead is that (MemOpw_ADDr_V4
Base, Offset, whatever) is produced and then selection carried on from
Base & Offset if needed. This would give code like:

mem(Base+Offset) += whatever

Interpreting your question completely differently (which may be
helpful for any out-of-tree targets you're considering): if XYZ is a
ComplexPattern and you only use it where both the input and the output
match up to that monolithic entity completely then you should see no
difference. That is, both of these should be unchanged by my work:

def : Pat<(whatever XYZ:$a, ...), (INST XYZ:$a)>;
def : Instruction<(ins XYZ:$a, ...), [(set ..., (whatever XYZ:$a))]>;

XYZ is used in both the input and the output, so everything matches up
just as it did before.

I hope this helps, but please do ask for any clarification if I've not
been clear enough.

Cheers.

Tim.

[jverma]

Thanks for the explanation Tim. It makes perfect sense.

[adasgupt]

LGTM. Jyotsna looked at the patch and she is okay with the Hexagon changes as well.

[t.p.northover]

Thanks! I've committed it as r209206.

Tim.

lib/Target/Hexagon/HexagonInstrInfoV4.td

multiclass MemOpi_bitPats <PatFrag ldOp, PatFrag stOp, PatLeaf immPred,
   let AddedComplexity = 250 in
   def : Pat<(stOp (OpNode (ldOp (add IntRegs:$base, extPred:$offset)),
                           immPred:$bitend),
                   (add IntRegs:$base, extPred:$offset)),
             (MI IntRegs:$base, extPred:$offset, (xformFunc immPred:$bitend))>;
 
   // mem[bhw](Rs+#0) = [clrbit|setbit](#U5)
   let AddedComplexity = 225 in
-  def : Pat <(stOp (OpNode (ldOp addrPred:$addr), immPred:$bitend),
-                   addrPred:$addr),
-             (MI IntRegs:$addr, #0, (xformFunc immPred:$bitend))>;
+  def : Pat <(stOp (OpNode (ldOp (addrPred IntRegs:$addr, extPred:$offset)),
+                           immPred:$bitend),
+                   (addrPred (i32 IntRegs:$addr), extPred:$offset)),
+             (MI IntRegs:$addr, extPred:$offset, (xformFunc immPred:$bitend))>;
 }
 
 multiclass MemOpi_bitExtType<PatFrag ldOpByte, PatFrag ldOpHalf > {
   // Byte - clrbit
   defm : MemOpi_bitPats<ldOpByte, truncstorei8, Clr3ImmPred, u6ExtPred,
                        ADDRriU6_0, CLRMEMIMM_BYTE, MemOPb_CLRBITi_V4, and>;
   // Byte - setbit
   defm : MemOpi_bitPats<ldOpByte, truncstorei8, Set3ImmPred,  u6ExtPred,

 // mem[bhw](Rs+#0) [+-&|]= Rt
 // mem[bhw](Rs+#U6:[012]) [+-&|]= Rt
 //===----------------------------------------------------------------------===//
 
 multiclass MemOpr_Pats <PatFrag ldOp, PatFrag stOp, ComplexPattern addrPred,
                      PatLeaf extPred, InstHexagon MI, SDNode OpNode> {
   let AddedComplexity = 141 in
   // mem[bhw](Rs+#0) [+-&|]= Rt
-  def : Pat <(stOp (OpNode (ldOp addrPred:$addr), (i32 IntRegs:$addend)),
-                   addrPred:$addr),
-             (MI IntRegs:$addr, #0, (i32 IntRegs:$addend) )>;
+  def : Pat <(stOp (OpNode (ldOp (addrPred IntRegs:$addr, extPred:$offset)),
+                           (i32 IntRegs:$addend)),
+                   (addrPred (i32 IntRegs:$addr), extPred:$offset)),
+             (MI IntRegs:$addr, extPred:$offset, (i32 IntRegs:$addend) )>;
 
   // mem[bhw](Rs+#U6:[012]) [+-&|]= Rt
   let AddedComplexity = 150 in
   def : Pat <(stOp (OpNode (ldOp (add IntRegs:$base, extPred:$offset)),
                            (i32 IntRegs:$orend)),
                    (add IntRegs:$base, extPred:$offset)),
              (MI IntRegs:$base, extPred:$offset, (i32 IntRegs:$orend) )>;
 }

utils/TableGen/CodeGenDAGPatterns.h

public:
   /// CodeGenIntrinsic information for it, otherwise return a null pointer.
   const CodeGenIntrinsic *getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const;
 
   /// getComplexPatternInfo - If this node corresponds to a ComplexPattern,
   /// return the ComplexPattern information, otherwise return null.
   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;
 
   /// TreeHasProperty - Return true if any node in this tree has the specified
   /// property.
   bool TreeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const;
 
   /// isCommutativeIntrinsic - Return true if the node is an intrinsic which is
class TreePattern {
 
   /// isInputPattern - True if this is an input pattern, something to match.
   /// False if this is an output pattern, something to emit.
   bool isInputPattern;
 
   /// 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
   /// current record.
   TreePattern(Record *TheRec, ListInit *RawPat, bool isInput,
               CodeGenDAGPatterns &ise);
   TreePattern(Record *TheRec, DagInit *Pat, bool isInput,
               CodeGenDAGPatterns &ise);

utils/TableGen/CodeGenDAGPatterns.cpp

if (P->isLeaf() && isa<IntInit>(P->getLeafValue()))
     Size += 2;
 
   // FIXME: This is a hack to statically increase the priority of patterns
   // which maps a sub-dag to a complex pattern. e.g. favors LEA over ADD.
   // Later we can allow complexity / cost for each pattern to be (optionally)
   // 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())
     ++Size;
 
   // Count children in the count if they are also nodes.
   for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) {
     TreePatternNode *Child = P->getChild(i);
static unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) {
   }
 
   if (Operator->isSubClassOf("SDNodeXForm"))
     return 1;  // FIXME: Generalize SDNodeXForm
 
   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);
 }
 
 void TreePatternNode::print(raw_ostream &OS) const {
   if (isLeaf())
     OS << *getLeafValue();
static EEVT::TypeSet getImplicitType(Record *R, unsigned ResNo,
   }
 
   if (R->getName() == "node" || R->getName() == "srcvalue" ||
       R->getName() == "zero_reg") {
     // Placeholder.
     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);
 }
 
 
 /// getIntrinsicInfo - If this node corresponds to an intrinsic, return the
 /// CodeGenIntrinsic information for it, otherwise return a null pointer.
 const CodeGenIntrinsic *TreePatternNode::
 getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const {
   if (getOperator() != CDP.get_intrinsic_void_sdnode() &&
       getOperator() != CDP.get_intrinsic_w_chain_sdnode() &&
       getOperator() != CDP.get_intrinsic_wo_chain_sdnode())
     return nullptr;
 
   unsigned IID = cast<IntInit>(getChild(0)->getLeafValue())->getValue();
   return &CDP.getIntrinsicInfo(IID);
 }
 
 /// getComplexPatternInfo - If this node corresponds to a ComplexPattern,
 /// 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 && DI->getDef()->isSubClassOf("ComplexPattern"))
-    return &CGP.getComplexPattern(DI->getDef());
+    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();
+    }
+  }
+
+  // Otherwise there is just one result.
+  return 1;
 }
 
 /// NodeHasProperty - Return true if this node has the specified property.
 bool TreePatternNode::NodeHasProperty(SDNP Property,
                                       const CodeGenDAGPatterns &CGP) const {
   if (isLeaf()) {
     if (const ComplexPattern *CP = getComplexPatternInfo(CGP))
       return CP->hasProperty(Property);
if (ChildNo != getNumChildren()) {
       return false;
     }
 
     for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
       MadeChange |= getChild(i)->ApplyTypeConstraints(TP, 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.
   if (getNumChildren() != 1) {
     TP.error("Node transform '" + getOperator()->getName() +
              "' requires one operand!");
     return false;
   }
bool TreePatternNode::canPatternMatch(std::string &Reason,
 
   // 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 (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());
   bool isCommIntrinsic = isCommutativeIntrinsic(CDP);
   if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) {
     // 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))) {
TreePatternNode *TreePattern::ParseTreePattern(Init *TheInit, StringRef OpName){
   }
 
   // Verify that this is something that makes sense for an operator.
   if (!Operator->isSubClassOf("PatFrag") &&
       !Operator->isSubClassOf("SDNode") &&
       !Operator->isSubClassOf("Instruction") &&
       !Operator->isSubClassOf("SDNodeXForm") &&
       !Operator->isSubClassOf("Intrinsic") &&
+      !Operator->isSubClassOf("ComplexPattern") &&
       Operator->getName() != "set" &&
       Operator->getName() != "implicit")
     error("Unrecognized node '" + Operator->getName() + "'!");
 
   //  Check to see if this is something that is illegal in an input pattern.
   if (isInputPattern) {
     if (Operator->isSubClassOf("Instruction") ||
         Operator->isSubClassOf("SDNodeXForm"))
else if (Int.ModRef != CodeGenIntrinsic::NoMem)
       Operator = getDAGPatterns().get_intrinsic_w_chain_sdnode();
     else // Otherwise, no chain.
       Operator = getDAGPatterns().get_intrinsic_wo_chain_sdnode();
 
     TreePatternNode *IIDNode = new TreePatternNode(IntInit::get(IID), 1);
     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);
 
   if (!Dag->getName().empty()) {
     assert(Result->getName().empty());
     Result->setName(Dag->getName());
   }
for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
       AnalyzeNode(N->getChild(i));
 
     // Ignore set nodes, which are not SDNodes.
     if (N->getOperator()->getName() == "set") {
       isBitcast = IsNodeBitcast(N);
       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.
       if (IntInfo->ModRef >= CodeGenIntrinsic::ReadArgMem)
         mayLoad = true;// These may load memory.
 
       if (IntInfo->ModRef >= CodeGenIntrinsic::ReadWriteArgMem)
         mayStore = true;// Intrinsics that can write to memory are 'mayStore'.

 
 /// GenerateVariantsOf - Given a pattern N, generate all permutations we can of
 /// the (potentially recursive) pattern by using algebraic laws.
 ///
 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;
   }
 
   // Look up interesting info about the node.
   const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(N->getOperator());
 
   // If this node is associative, re-associate.

utils/TableGen/DAGISelMatcherGen.cpp

class MatcherGen {
     /// as we scan the tree.
     TreePatternNode *PatWithNoTypes;
 
     /// VariableMap - A map from variable names ('$dst') to the recorded operand
     /// number that they were captured as.  These are biased by 1 to make
     /// 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.
     unsigned NextRecordedOperandNo;
 
     /// MatchedChainNodes - This maintains the position in the recorded nodes
     /// array of all of the recorded input nodes that have chains.
     SmallVector<unsigned, 2> MatchedChainNodes;
 
     /// MatchedGlueResultNodes - This maintains the position in the recorded
     /// nodes array of all of the recorded input nodes that have glue results.
     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;
 
     /// PhysRegInputs - List list has an entry for each explicitly specified
     /// physreg input to the pattern.  The first elt is the Register node, the
     /// second is the recorded slot number the input pattern match saved it in.
     SmallVector<std::pair<Record*, unsigned>, 2> PhysRegInputs;
 
private:
     void InferPossibleTypes();
 
     // Matcher Generation.
     void EmitMatchCode(const TreePatternNode *N, TreePatternNode *NodeNoTypes);
     void EmitLeafMatchCode(const TreePatternNode *N);
     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];
       assert(VarMapEntry != 0 &&
              "Variable referenced but not defined and not caught earlier!");
       return VarMapEntry-1;
     }
 
if (LeafRec->isSubClassOf("ComplexPattern")) {
     // The OPC_CheckComplexPattern operation implicitly records the results.
     if (N->getName().empty()) {
       errs() << "We expect complex pattern uses to have names: " << *N << "\n";
       exit(1);
     }
 
     // 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;
   }
 
   errs() << "Unknown leaf kind: " << *N << "\n";
   abort();
 }
 
 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
   // a constant without a predicate fn that has more that one bit set, handle
   // this as a special case.  This is usually for targets that have special
   // handling of certain large constants (e.g. alpha with it's 8/16/32-bit
   // handling stuff).  Using these instructions is often far more efficient
   // than materializing the constant.  Unfortunately, both the instcombiner
for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) {
     // Get the code suitable for matching this child.  Move to the child, check
     // it then move back to the parent.
     AddMatcher(new MoveChildMatcher(OpNo));
     EmitMatchCode(N->getChild(i), NodeNoTypes->getChild(i));
     AddMatcher(new MoveParentMatcher());
   }
 }
 
+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) {
   // If N and NodeNoTypes don't agree on a type, then this is a case where we
   // need to do a type check.  Emit the check, apply the type to NodeNoTypes and
   // reinfer any correlated types.
   SmallVector<unsigned, 2> ResultsToTypeCheck;
 
   for (unsigned i = 0, e = NodeNoTypes->getNumTypes(); i != e; ++i) {
     if (NodeNoTypes->getExtType(i) == N->getExtType(i)) continue;
     NodeNoTypes->setType(i, N->getExtType(i));
     InferPossibleTypes();
     ResultsToTypeCheck.push_back(i);
   }
 
   // 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);
   else
     EmitOperatorMatchCode(N, NodeNoTypes);
 
   // If there are node predicates for this node, generate their checks.
   for (unsigned i = 0, e = N->getPredicateFns().size(); i != e; ++i)
bool MatcherGen::EmitMatcherCode(unsigned Variant) {
   // Now that we've completed the structural type match, emit any ComplexPattern
   // checks (e.g. addrmode matches).  We emit this after the structural match
   // because they are generally more expensive to evaluate and more difficult to
   // factor.
   for (unsigned i = 0, e = MatchedComplexPatterns.size(); i != e; ++i) {
     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.
     AddMatcher(new CheckComplexPatMatcher(CP, RecNodeEntry,
                                           N->getName(), NextRecordedOperandNo));
 
     // Record the right number of operands.
     NextRecordedOperandNo += CP.getNumOperands();

 //===----------------------------------------------------------------------===//
 // Node Result Generation
 //===----------------------------------------------------------------------===//
 
 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?");
-
-    // 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);
+  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);
+
     return;
   }
 
   unsigned SlotNo = getNamedArgumentSlot(N->getName());
 
   // If this is an 'imm' or 'fpimm' node, make sure to convert it to the target
   // version of the immediate so that it doesn't get selected due to some other
   // node use.
   if (!N->isLeaf()) {
     StringRef OperatorName = N->getOperator()->getName();
     if (OperatorName == "imm" || OperatorName == "fpimm") {
       AddMatcher(new EmitConvertToTargetMatcher(SlotNo));
       ResultOps.push_back(NextRecordedOperandNo++);
       return;
     }
   }
 
-  ResultOps.push_back(SlotNo);
+  for (unsigned i = 0; i < N->getNumMIResults(CGP); ++i)
+    ResultOps.push_back(SlotNo + i);
 }
 
 void MatcherGen::EmitResultLeafAsOperand(const TreePatternNode *N,
                                          SmallVectorImpl<unsigned> &ResultOps) {
   assert(N->isLeaf() && "Must be a leaf");
 
   if (IntInit *II = dyn_cast<IntInit>(N->getLeafValue())) {
     AddMatcher(new EmitIntegerMatcher(II->getValue(), N->getType(0)));