[TableGen] Enable multiple instructions in patterns

[tmatheson]

Summary

Tablegen patterns for instrucion selection can generate multiple
instructions, but only if there is a data dependency between them so
that they can be expressed as a DAG. For example, something like:

(store (load %src), %dst)

For some patterns, we might want to generate a sequence of instructions
which do not have a data dependency. For example on AArch64 some atomic
instructions are implemented like this:

LDP %ptr
DMB ISH

Currently, sequences like this can not be selected with tablegen
patterns. To work around this we need to do custom selection, which has
several disadvantages compared to using patterns, such as needing
separate implementations for SelectionDAG and GlobalISel.

This patch adds basic support for tablegen Patterns which have a list
of output instructions. Pattern already has the ability to express this
but it looks like it was never implemented.

Multiple result instructions in an output pattern will be chained
together.

The GlobalISel pattern importer will skip these patterns for now. I
intend to implement this soon.

There are still some problems processing existing patterns for a few
backends. I am looking into these but don't expect them to require
major changes, and I would like feedback on the general approach of
this patch in the meantime.

[craig.topper]

llvm/utils/TableGen/CodeGenDAGPatterns.cpp

3766

Add blank line between functions

4309

You can avoid the loop with something like

const std::vector<TypeSetByHwMode> Types = OutTree->getExtTypes();
FlatOutTypes.insert(FlatOutTypes.end(), Types.begin(), Types.end());

llvm/utils/TableGen/CodeGenDAGPatterns.h

926

const std::vector<TreePatternNodePtr> &

llvm/utils/TableGen/DAGISelEmitter.cpp

40

Can these changes be pre-committed?

71

Can the changes to this function be pre-commited?

llvm/utils/TableGen/DAGISelMatcherGen.cpp

796

Can you capitalize the variable namings per the coding standards?

945

Capitalize

1107

Drop curly braces

llvm/test/TableGen/dag-isel-multiple-instructions.td

+// RUN: llvm-tblgen -gen-dag-isel -I %p/../../include %s | FileCheck %s
+
+include "llvm/Target/Target.td"
+
+def TestTargetInstrInfo : InstrInfo;
+
+def TestTarget : Target {
+  let InstructionSet = TestTargetInstrInfo;
+}
+
+def REG : Register<"REG">;
+def GPR : RegisterClass<"TestTarget", [i32], 32, (add REG)>;
+
+
+def FENCE : Instruction {
+  let OutOperandList = (outs);
+  let InOperandList = (ins);
+}
+
+def LOAD : Instruction {
+  let OutOperandList = (outs GPR:$r0);
+  let InOperandList = (ins GPR:$t0);
+  let mayLoad = 1;
+}
+
+def STORE : Instruction {
+  let OutOperandList = (outs);
+  let InOperandList = (ins GPR:$t0,  GPR:$t1);
+  let mayStore = 1;
+}
+
+class BINOP : Instruction {
+  let OutOperandList = (outs GPR:$r0);
+  let InOperandList = (ins GPR:$t0,  GPR:$t1);
+}
+def ADD : BINOP;
+def SUB : BINOP;
+def MUL : BINOP;
+def DIV : BINOP;
+
+def UDIVREM : Instruction {
+  let OutOperandList = (outs GPR:$r1, GPR:$r0);
+  let InOperandList = (ins GPR:$t0, GPR:$t1);
+}
+
+// The patterns are written here in the order that the emitter sorts them, so
+// that the CHECK lines can stay next to them.
+
+// CHECK-LABEL: /*     0*/ OPC_SwitchOpcode /*5 cases */, 64, TARGET_VAL(ISD::STORE),// ->68
+// CHECK-NEXT: /*     4*/  OPC_RecordMemRef,
+// CHECK-NEXT: /*     5*/  OPC_RecordNode, // #0 = 'st' chained node
+// CHECK-NEXT: /*     6*/  OPC_RecordChild1, // #1 = $val
+// CHECK-NEXT: /*     7*/  OPC_CheckChild1Type, MVT::i32,
+// CHECK-NEXT: /*     9*/  OPC_MoveChild2,
+// CHECK-NEXT: /*    10*/  OPC_CheckOpcode, TARGET_VAL(ISD::LOAD),
+// CHECK-NEXT: /*    13*/  OPC_RecordMemRef,
+// CHECK-NEXT: /*    14*/  OPC_RecordNode, // #2 = 'ld' chained node
+// CHECK-NEXT: /*    15*/  OPC_CheckFoldableChainNode,
+// CHECK-NEXT: /*    16*/  OPC_MoveChild1,
+// CHECK-NEXT: /*    17*/  OPC_CheckOpcode, TARGET_VAL(ISD::ADD),
+// CHECK-NEXT: /*    20*/  OPC_RecordChild0, // #3 = $ptr
+// CHECK-NEXT: /*    21*/  OPC_RecordChild1, // #4 = $offset
+// CHECK-NEXT: /*    22*/  OPC_MoveParent,
+// CHECK-NEXT: /*    23*/  OPC_CheckPredicate, 0, // Predicate_unindexedload
+// CHECK-NEXT: /*    25*/  OPC_CheckPredicate, 1, // Predicate_load
+// CHECK-NEXT: /*    27*/  OPC_MoveParent,
+// CHECK-NEXT: /*    28*/  OPC_CheckPredicate, 2, // Predicate_unindexedstore
+// CHECK-NEXT: /*    30*/  OPC_CheckPredicate, 3, // Predicate_store
+// CHECK-NEXT: /*    32*/  OPC_EmitMergeInputChains, 2, 0, 2,
+// CHECK-NEXT: /*    36*/  OPC_EmitNode0, TARGET_VAL(::FENCE), 0|OPFL_Chain|OPFL_MemRefs,
+// CHECK-NEXT:                 0/*#Ops*/,
+// CHECK-NEXT: /*    41*/  OPC_EmitNode1, TARGET_VAL(::ADD), 0|OPFL_Chain,
+// CHECK-NEXT:                 MVT::i32, 2/*#Ops*/, 3, 4,  // Results = #5
+// CHECK-NEXT: /*    49*/  OPC_EmitNode1, TARGET_VAL(::LOAD), 0|OPFL_Chain,
+// CHECK-NEXT:                 MVT::i32, 1/*#Ops*/, 5,  // Results = #6
+// CHECK-NEXT: /*    56*/  OPC_EmitNode0, TARGET_VAL(::STORE), 0|OPFL_Chain|OPFL_MemRefs,
+// CHECK-NEXT:                 2/*#Ops*/, 1, 6,
+// CHECK-NEXT: /*    63*/  OPC_MorphNodeTo0, TARGET_VAL(::FENCE), 0|OPFL_Chain|OPFL_MemRefs,
+// CHECK-NEXT:                 0/*#Ops*/,
+// CHECK-NEXT:             // Src: (st i32:{ *:[i32] }:$val, (ld:{ *:[iPTR] } (add:{ *:[i32] } i32:{ *:[i32] }:$ptr, i32:{ *:[i32] }:$offset))<<P:Predicate_unindexedload>><<P:Predicate_load>>)<<P:Predicate_unindexedstore>><<P:Predicate_store>> - Complexity = 11
+// CHECK-NEXT:             // Dst: ONE_TO_MANY: [(FENCE), (STORE i32:{ *:[i32] }:$val, (LOAD:{ *:[i32] } (ADD:{ *:[i32] } i32:{ *:[i32] }:$ptr, i32:{ *:[i32] }:$offset))), (FENCE), ]
+def ONE_TO_MANY : Pattern<(store i32:$val, (load (add i32:$ptr, i32:$offset))),
+  [
+    (FENCE),
+    (STORE i32:$val, (LOAD (ADD i32:$ptr, i32:$offset))),
+    (FENCE)
+  ]>;
+
+
+// CHECK-LABEL: /*    68*/ /*SwitchOpcode*/ 22, TARGET_VAL(ISD::CALLSEQ_START),// ->93
+// CHECK-NEXT: /*    71*/  OPC_RecordNode, // #0 = 'AArch64callseq_start' chained node
+// CHECK-NEXT: /*    72*/  OPC_RecordChild1, // #1 = $amt1
+// CHECK-NEXT: /*    73*/  OPC_MoveChild1,
+// CHECK-NEXT: /*    74*/  OPC_CheckOpcode, TARGET_VAL(ISD::TargetConstant),
+// CHECK-NEXT: /*    77*/  OPC_MoveParent,
+// CHECK-NEXT: /*    78*/  OPC_RecordChild2, // #2 = $amt2
+// CHECK-NEXT: /*    79*/  OPC_MoveChild2,
+// CHECK-NEXT: /*    80*/  OPC_CheckOpcode, TARGET_VAL(ISD::TargetConstant),
+// CHECK-NEXT: /*    83*/  OPC_MoveParent,
+// CHECK-NEXT: /*    84*/  OPC_EmitMergeInputChains1_0,
+// CHECK-NEXT: /*    85*/  OPC_MorphNodeTo1, TARGET_VAL(::ADJCALLSTACKDOWN), 0|OPFL_Chain|OPFL_GlueOutput,
+// CHECK-NEXT:                 MVT::i32, 2/*#Ops*/, 1, 2,
+// CHECK-NEXT:             // Src: (AArch64callseq_start (timm:{ *:[i32] }):$amt1, (timm:{ *:[i32] }):$amt2) - Complexity = 9
+// CHECK-NEXT:             // Dst: ADJCALLSTACKDOWN: (ADJCALLSTACKDOWN:{ *:[i32] } (timm:{ *:[i32] }):$amt1, (timm:{ *:[i32] }):$amt2),
+// Instruction with an implicit result (REG) in output pattern
+def AArch64callseq_start : SDNode<"ISD::CALLSEQ_START",
+                                SDCallSeqStart<[ SDTCisVT<0, i32>, SDTCisVT<1, i32> ]>,
+                                [SDNPHasChain, SDNPOutGlue]>;
+def ADJCALLSTACKDOWN : Instruction {
+  dag OutOperandList = (outs);
+  dag InOperandList  = (ins i32imm:$amt1, i32imm:$amt2);
+  let Pattern        = [(AArch64callseq_start timm:$amt1, timm:$amt2)];
+  let Defs = [REG];
+}
+
+
+// CHECK-LABEL: /*    93*/ /*SwitchOpcode*/ 48, TARGET_VAL(ISD::UDIVREM),// ->144
+// CHECK-NEXT: /*    96*/  OPC_RecordChild0, // #0 = $t0
+// CHECK-NEXT: /*    97*/  OPC_RecordChild1, // #1 = $t1
+// CHECK-NEXT: /*    98*/  OPC_Scope, 13, /*->113*/ // 2 children in Scope
+// CHECK-NEXT: /*   100*/   OPC_EmitNode2, TARGET_VAL(::INSTR), 0,
+// CHECK-NEXT:                  MVT::i32, MVT::i32, 2/*#Ops*/, 0, 1,  // Results = #2 #3
+// CHECK-NEXT: /*   109*/   OPC_CompleteMatch, 2, 3, 2,
+// CHECK-NEXT:               // Src: (udivrem:{ *:[i32] }:{ *:[i32] } i32:{ *:[i32] }:$t0, i32:{ *:[i32] }:$t1) - Complexity = 3
+// CHECK-NEXT:               // Dst: INSTR: (INSTR:{ *:[i32] }:{ *:[i32] } i32:{ *:[i32] }:$t0, i32:{ *:[i32] }:$t1),
+// An instruction with a pattern
+def INSTR : Instruction {
+  let OutOperandList = (outs GPR:$r1, GPR:$r0);
+  let InOperandList = (ins GPR:$t0, GPR:$t1);
+  let Pattern = [(set i32:$r0, i32:$r1, (udivrem i32:$t0, i32:$t1))];
+}
+
+// CHECK-NEXT: /*   113*/  /*Scope*/ 29, /*->143*/
+// CHECK-NEXT: /*   114*/   OPC_EmitNode0, TARGET_VAL(::FENCE), 0|OPFL_Chain,
+// CHECK-NEXT:                  0/*#Ops*/,
+// CHECK-NEXT: /*   119*/   OPC_EmitNode1, TARGET_VAL(::DIV), 0|OPFL_Chain,
+// CHECK-NEXT:                  MVT::i32, 2/*#Ops*/, 0, 1,  // Results = #2
+// CHECK-NEXT: /*   127*/   OPC_EmitNode0, TARGET_VAL(::FENCE), 0|OPFL_Chain,
+// CHECK-NEXT:                  0/*#Ops*/,
+// CHECK-NEXT: /*   132*/   OPC_EmitNode1, TARGET_VAL(::LOAD), 0|OPFL_Chain,
+// CHECK-NEXT:                  MVT::i32, 1/*#Ops*/, 0,  // Results = #3
+// CHECK-NEXT: /*   139*/   OPC_CompleteMatch, 2, 2, 3,
+// CHECK-NEXT:               // Src: (udivrem:{ *:[i32] }:{ *:[i32] } i32:{ *:[i32] }:$t0, i32:{ *:[i32] }:$t1) - Complexity = 3
+// CHECK-NEXT:               // Dst: COLLECT_RESULTS: [(FENCE), (DIV:{ *:[i32] } i32:{ *:[i32] }:$t0, i32:{ *:[i32] }:$t1), (FENCE), (LOAD:{ *:[i32] } i32:{ *:[i32] }:$t0), ]
+def COLLECT_RESULTS : Pattern<(udivrem i32:$t0, i32:$t1),
+  [
+    (FENCE),
+    (DIV i32:$t0, i32:$t1),
+    (FENCE),
+    (LOAD i32:$t0),
+  ]>;
+
+
+// CHECK-LABEL: /*   144*/ /*SwitchOpcode*/ 10, TARGET_VAL(ISD::SUB),// ->157
+// CHECK-NEXT: /*   147*/  OPC_RecordChild0, // #0 = $t0
+// CHECK-NEXT: /*   148*/  OPC_RecordChild1, // #1 = $t1
+// CHECK-NEXT: /*   149*/  OPC_MorphNodeTo1, TARGET_VAL(::SUB), 0,
+// CHECK-NEXT:                 MVT::i32, 2/*#Ops*/, 0, 1,
+// CHECK-NEXT:             // Src: (sub:{ *:[i32] } i32:{ *:[i32] }:$t0, i32:{ *:[i32] }:$t1) - Complexity = 3
+// CHECK-NEXT:             // Dst: ONE_TO_ONE: (SUB:{ *:[i32] } i32:{ *:[i32] }:$t0, i32:{ *:[i32] }:$t1),
+def ONE_TO_ONE : Pattern<(sub i32:$t0, i32:$t1),
+  [
+    (SUB i32:$t0, i32:$t1)
+  ]>;
+
+
+// CHECK-LABEL: /*   157*/ /*SwitchOpcode*/ 18, TARGET_VAL(ISD::MUL),// ->178
+// CHECK-NEXT: /*   160*/  OPC_RecordChild0, // #0 = $t0
+// CHECK-NEXT: /*   161*/  OPC_RecordChild1, // #1 = $t1
+// CHECK-NEXT: /*   162*/  OPC_EmitNode1, TARGET_VAL(::MUL), 0|OPFL_Chain,
+// CHECK-NEXT:                 MVT::i32, 2/*#Ops*/, 0, 1,  // Results = #2
+// CHECK-NEXT: /*   170*/  OPC_EmitNode0, TARGET_VAL(::FENCE), 0|OPFL_Chain,
+// CHECK-NEXT:                 0/*#Ops*/,
+// CHECK-NEXT: /*   175*/  OPC_CompleteMatch, 1, 2,
+// CHECK-NEXT:              // Src: (mul:{ *:[i32] } i32:{ *:[i32] }:$t0, i32:{ *:[i32] }:$t1) - Complexity = 3
+// CHECK-NEXT:              // Dst: ONE_TO_TWO: [(MUL:{ *:[i32] } i32:{ *:[i32] }:$t0, i32:{ *:[i32] }:$t1), (FENCE), ]
+def ONE_TO_TWO : Pattern<(mul i32:$t0, i32:$t1),
+  [
+    (MUL i32:$t0, i32:$t1),
+    (FENCE)
+  ]>;

llvm/utils/TableGen/CodeGenDAGPatterns.h

 private:
   unsigned PtrAddrSpace = std::numeric_limits<unsigned>::max();
   /// Intersect two sets. Return true if anything has changed.
   bool intersect(SetType &Out, const SetType &In);
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const TypeSetByHwMode &T);
 
+/// Only ever used by TreePattern
 struct TypeInfer {
   TypeInfer(TreePattern &T) : TP(T) {}
 
   bool isConcrete(const TypeSetByHwMode &VTS, bool AllowEmpty) const {
     return VTS.isValueTypeByHwMode(AllowEmpty);
   }
   ValueTypeByHwMode getConcrete(const TypeSetByHwMode &VTS,
                                 bool AllowEmpty) const {
struct SuppressValidation {
     }
     ~SuppressValidation() {
       Infer.Validate = SavedValidate;
     }
     TypeInfer &Infer;
     bool SavedValidate;
   };
 
+  /// Reference to the TreePattern which owns this TypeInfer instance.
   TreePattern &TP;
   bool Validate = true;   // Indicate whether to validate types.
 
 private:
   const TypeSetByHwMode &getLegalTypes() const;
 
   /// Cached legal types (in default mode).
   mutable bool LegalTypesCached = false;

 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);
+  /// Construct from a single pattern
   TreePattern(Record *TheRec, TreePatternNodePtr Pat, bool isInput,
               CodeGenDAGPatterns &ise);
+  /// Construct from multiple patterns
+  TreePattern(Record *TheRec, std::vector<TreePatternNodePtr> &Pat,
+              bool isInput, CodeGenDAGPatterns &ise);
 
   /// getTrees - Return the tree patterns which corresponds to this pattern.
   ///
   const std::vector<TreePatternNodePtr> &getTrees() const { return Trees; }
   unsigned getNumTrees() const { return Trees.size(); }
   const TreePatternNodePtr &getTree(unsigned i) const { return Trees[i]; }
   void setTree(unsigned i, TreePatternNodePtr Tree) { Trees[i] = Tree; }
   const TreePatternNodePtr &getOnlyTree() const {
bool hasError() const {
     return HasError;
   }
   void resetError() {
     HasError = false;
   }
 
   TypeInfer &getInfer() { return Infer; }
 
+  bool hasProperTypeByHwMode() const;
+
   void print(raw_ostream &OS) const;
   void dump() const;
 
 private:
   TreePatternNodePtr ParseTreePattern(Init *DI, StringRef OpName);
   void ComputeNamedNodes();
   void ComputeNamedNodes(TreePatternNode *N);
 };
 
+inline raw_ostream &operator<<(raw_ostream &OS, const TreePattern &TP) {
+  TP.print(OS);
+  return OS;
+}
 
 inline bool TreePatternNode::UpdateNodeType(unsigned ResNo,
                                             const TypeSetByHwMode &InTy,
                                             TreePattern &TP) {
   TypeSetByHwMode VTS(InTy);
   TP.getInfer().expandOverloads(VTS);
   return TP.getInfer().MergeInTypeInfo(Types[ResNo], VTS);
 }
public:
 
   TreePatternNodePtr getSrcPattern() const { return SrcPattern; }
   TreePatternNodePtr getResultPattern() const { return ResultPattern; }
 };
 
 /// PatternToMatch - Used by CodeGenDAGPatterns to keep tab of patterns
 /// processed to produce isel.
 class PatternToMatch {
-  Record          *SrcRecord;   // Originating Record for the pattern.
-  ListInit        *Predicates;  // Top level predicate conditions to match.
-  TreePatternNodePtr SrcPattern;      // Source pattern to match.
-  TreePatternNodePtr DstPattern;      // Resulting pattern.
-  std::vector<Record*> Dstregs; // Physical register defs being matched.
-  std::string      HwModeFeatures;
-  int              AddedComplexity; // Add to matching pattern complexity.
-  unsigned         ID;          // Unique ID for the record.
+  Record *SrcRecord;          // Originating Record for the pattern.
+  ListInit *Predicates;       // Top level predicate conditions to match.
+  TreePatternNodePtr SrcTree; // Source pattern to match.
+  TreePattern DstPattern;     // Resulting pattern. May contain multiple nodes.
+  std::vector<Record *> Dstregs; // Physical register defs being matched.
+  std::string HwModeFeatures;
+  int AddedComplexity; // Add to matching pattern complexity.
+  unsigned ID;         // Unique ID for the record.
 
 public:
   PatternToMatch(Record *srcrecord, ListInit *preds, TreePatternNodePtr src,
-                 TreePatternNodePtr dst, std::vector<Record *> dstregs,
-                 int complexity, unsigned uid,
-                 const Twine &hwmodefeatures = "")
-      : SrcRecord(srcrecord), Predicates(preds), SrcPattern(src),
-        DstPattern(dst), Dstregs(std::move(dstregs)),
-        HwModeFeatures(hwmodefeatures.str()), AddedComplexity(complexity),
-        ID(uid) {}
+                 TreePattern dst, std::vector<Record *> dstregs, int complexity,
+                 unsigned uid, const Twine &hwmodefeatures = "")
+      : SrcRecord(srcrecord), Predicates(preds), SrcTree(src), DstPattern(dst),
+        Dstregs(std::move(dstregs)), HwModeFeatures(hwmodefeatures.str()),
+        AddedComplexity(complexity), ID(uid) {}
 
   Record          *getSrcRecord()  const { return SrcRecord; }
   ListInit        *getPredicates() const { return Predicates; }
-  TreePatternNode *getSrcPattern() const { return SrcPattern.get(); }
-  TreePatternNodePtr getSrcPatternShared() const { return SrcPattern; }
-  TreePatternNode *getDstPattern() const { return DstPattern.get(); }
-  TreePatternNodePtr getDstPatternShared() const { return DstPattern; }
+  TreePatternNode *getSrcPattern() const { return SrcTree.get(); }
+  TreePatternNodePtr getSrcPatternShared() const { return SrcTree; }
+  const TreePattern &getDstPattern() const { return DstPattern; }
   const std::vector<Record*> &getDstRegs() const { return Dstregs; }
   StringRef   getHwModeFeatures() const { return HwModeFeatures; }
   int         getAddedComplexity() const { return AddedComplexity; }
   unsigned getID() const { return ID; }
 
   std::string getPredicateCheck() const;
   void getPredicateRecords(SmallVectorImpl<Record *> &PredicateRecs) const;
 

llvm/utils/TableGen/CodeGenDAGPatterns.cpp

 
 TreePattern::TreePattern(Record *TheRec, TreePatternNodePtr Pat, bool isInput,
                          CodeGenDAGPatterns &cdp)
     : TheRecord(TheRec), CDP(cdp), isInputPattern(isInput), HasError(false),
       Infer(*this) {
   Trees.push_back(Pat);
 }
 
+TreePattern::TreePattern(Record *TheRec, std::vector<TreePatternNodePtr> &Pats,
+                         bool isInput, CodeGenDAGPatterns &cdp)
+    : TheRecord(TheRec), CDP(cdp), isInputPattern(isInput), HasError(false),
+      Infer(*this) {
+  Trees = Pats;
+}
+
 void TreePattern::error(const Twine &Msg) {
   if (HasError)
     return;
   dump();
   PrintError(TheRecord->getLoc(), "In " + TheRecord->getName() + ": " + Msg);
   HasError = true;
 }
 
InferAllTypes(const StringMap<SmallVector<TreePatternNode*,1> > *InNamedTypes) {
   }
 
   bool HasUnresolvedTypes = false;
   for (const TreePatternNodePtr &Tree : Trees)
     HasUnresolvedTypes |= Tree->ContainsUnresolvedType(*this);
   return !HasUnresolvedTypes;
 }
 
+bool TreePattern::hasProperTypeByHwMode() const {
+  return llvm::any_of(getTrees(),
+                      [](auto &T) { return T->hasProperTypeByHwMode(); });
+}
+
 void TreePattern::print(raw_ostream &OS) const {
   OS << getRecord()->getName();
   if (!Args.empty()) {
     OS << "(";
     ListSeparator LS;
     for (const std::string &Arg : Args)
       OS << LS << Arg;
     OS << ")";
   }
   OS << ": ";
 
   if (Trees.size() > 1)
-    OS << "[\n";
+    OS << "[";
   for (const TreePatternNodePtr &Tree : Trees) {
-    OS << "\t";
     Tree->print(OS);
-    OS << "\n";
+    OS << ", ";
   }
 
   if (Trees.size() > 1)
     OS << "]\n";
 }
 
 void TreePattern::dump() const { print(errs()); }
 
for (Init *I : LI->getValues()) {
     assert(DI && "non-dag in an instruction Pattern list?!");
     if (hasNullFragReference(DI))
       return true;
   }
   return false;
 }
 
 /// Get all the instructions in a tree.
-static void
-getInstructionsInTree(TreePatternNode *Tree, SmallVectorImpl<Record*> &Instrs) {
+static void getInstructionsInTree(const TreePatternNode *Tree,
+                                  SmallVectorImpl<Record *> &Instrs) {
   if (Tree->isLeaf())
     return;
   if (Tree->getOperator()->isSubClassOf("Instruction"))
     Instrs.push_back(Tree->getOperator());
   for (unsigned i = 0, e = Tree->getNumChildren(); i != e; ++i)
     getInstructionsInTree(Tree->getChild(i), Instrs);
 }
+/// Get all the instructions in all trees in a pattern.
+static void getInstructionsInPattern(const TreePattern &Pat,
+                                     SmallVectorImpl<Record *> &Instrs) {
+  for (const auto &Tree : Pat.getTrees())
+    getInstructionsInTree(Tree.get(), Instrs);
+}
 
 /// Check the class of a pattern leaf node against the instruction operand it
 /// represents.
 static bool checkOperandClass(CGIOperandList::OperandInfo &OI,
                               Record *Leaf) {
   if (OI.Rec == Leaf)
     return true;
 
if (CP->getRootNodes().empty())
       Pattern->error("ComplexPattern at root must specify list of opcodes it"
                      " could match");
 
 
   // Find all of the named values in the input and output, ensure they have the
   // same type.
   std::map<std::string, NameRecord> SrcNames, DstNames;
   FindNames(PTM.getSrcPattern(), SrcNames, Pattern);
-  FindNames(PTM.getDstPattern(), DstNames, Pattern);
+  for (const auto &Tree : PTM.getDstPattern().getTrees())
+    FindNames(Tree.get(), DstNames, Pattern);
 
   // Scan all of the named values in the destination pattern, rejecting them if
   // they don't exist in the input pattern.
   for (const auto &Entry : DstNames) {
     if (SrcNames[Entry.first].first == nullptr)
       Pattern->error("Pattern has input without matching name in output: $" +
                      Entry.first);
   }
void CodeGenDAGPatterns::InferInstructionFlags() {
 
   // Try to infer flags from all patterns in PatternToMatch.  These include
   // both the primary instruction patterns (which always come first) and
   // patterns defined outside the instruction.
   for (const PatternToMatch &PTM : ptms()) {
     // We can only infer from single-instruction patterns, otherwise we won't
     // know which instruction should get the flags.
     SmallVector<Record*, 8> PatInstrs;
-    getInstructionsInTree(PTM.getDstPattern(), PatInstrs);
+    getInstructionsInPattern(PTM.getDstPattern(), PatInstrs);
     if (PatInstrs.size() != 1)
       continue;
 
     // Get the single instruction.
     CodeGenInstruction &InstInfo = Target.getInstruction(PatInstrs.front());
 
     // Only infer properties from the first pattern. We'll verify the others.
     if (InstInfo.InferredFrom)

 }
 
 
 /// Verify instruction flags against pattern node properties.
 void CodeGenDAGPatterns::VerifyInstructionFlags() {
   unsigned Errors = 0;
   for (const PatternToMatch &PTM : ptms()) {
     SmallVector<Record*, 8> Instrs;
-    getInstructionsInTree(PTM.getDstPattern(), Instrs);
+    getInstructionsInPattern(PTM.getDstPattern(), Instrs);
     if (Instrs.empty())
       continue;
 
     // Count the number of instructions with each flag set.
     unsigned NumSideEffects = 0;
     unsigned NumStores = 0;
     unsigned NumLoads = 0;
     for (const Record *Instr : Instrs) {
static TreePatternNodePtr PromoteXForms(TreePatternNodePtr N) {
   if (!N->isLeaf())
     for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) {
       TreePatternNodePtr Child = N->getChildShared(i);
       N->setChild(i, PromoteXForms(Child));
     }
   return N;
 }
 
-void CodeGenDAGPatterns::ParseOnePattern(Record *TheDef,
-       TreePattern &Pattern, TreePattern &Result,
-       const std::vector<Record *> &InstImpResults) {
+void CodeGenDAGPatterns::ParseOnePattern(
+    Record *TheDef, TreePattern &InPattern, TreePattern &OutPattern,
 
   // Inline pattern fragments and expand multiple alternatives.
-  Pattern.InlinePatternFragments();
-  Result.InlinePatternFragments();
-
-  if (Result.getNumTrees() != 1)
-    Result.error("Cannot use multi-alternative fragments in result pattern!");
+  InPattern.InlinePatternFragments();
+  OutPattern.InlinePatternFragments();
 
   // Infer types.
   bool IterateInference;
   bool InferredAllPatternTypes, InferredAllResultTypes;
   do {
     // Infer as many types as possible.  If we cannot infer all of them, we
     // can never do anything with this pattern: report it to the user.
     InferredAllPatternTypes =
-        Pattern.InferAllTypes(&Pattern.getNamedNodesMap());
+        InPattern.InferAllTypes(&InPattern.getNamedNodesMap());
 
     // Infer as many types as possible.  If we cannot infer all of them, we
     // can never do anything with this pattern: report it to the user.
     InferredAllResultTypes =
-        Result.InferAllTypes(&Pattern.getNamedNodesMap());
+        OutPattern.InferAllTypes(&InPattern.getNamedNodesMap());
 
     IterateInference = false;
 
-    // Apply the type of the result to the source pattern.  This helps us
-    // resolve cases where the input type is known to be a pointer type (which
-    // is considered resolved), but the result knows it needs to be 32- or
-    // 64-bits.  Infer the other way for good measure.
-    for (const auto &T : Pattern.getTrees())
-      for (unsigned i = 0, e = std::min(Result.getOnlyTree()->getNumTypes(),
-                                        T->getNumTypes());
-         i != e; ++i) {
-        IterateInference |= T->UpdateNodeType(
-            i, Result.getOnlyTree()->getExtType(i), Result);
-        IterateInference |= Result.getOnlyTree()->UpdateNodeType(
-            i, T->getExtType(i), Result);
-      }
+    // For output patterns with multiple trees, the result types of each tree
+    // are simply concatenated. We need to track which of the output trees each
+    // result corresponds to, and how many results that tree produced.
+    std::vector<TypeSetByHwMode> FlatOutTypes;
+    using FlatInstrRange =
+        std::pair<unsigned, unsigned>; // instr idx, number of results
+    std::vector<FlatInstrRange> FlatOutRanges;
+    for (unsigned iTree = 0; iTree < OutPattern.getNumTrees(); ++iTree) {
+      const TreePatternNodePtr &OutTree = OutPattern.getTree(iTree);
+      // Note: getNumTypes() may include one(?) implicit def.
+      FlatOutRanges.emplace_back(iTree, OutTree->getNumTypes());
+      for (const TypeSetByHwMode &TypeSet : OutTree->getExtTypes()) {
+        FlatOutTypes.push_back(TypeSet);
+      }
+    }
+
+    // Apply the type of each result to each source pattern and vice versa. This
+    // helps us resolve cases where the input type is known to be a pointer type
+    // (which is considered resolved), but the result knows it needs to be 32-
+    // or 64-bits.
+    for (const TreePatternNodePtr &InTree : InPattern.getTrees()) {
+      // Apply output pattern types to input tree
+      const unsigned N =
+          std::min(InTree->getNumTypes(), (unsigned)FlatOutTypes.size());
+      for (unsigned i = 0; i < N; ++i)
+        IterateInference |=
+            InTree->UpdateNodeType(i, FlatOutTypes[i], OutPattern);
+      // Apply input pattern types to output tree
+      for (const FlatInstrRange &Range : FlatOutRanges) {
+        unsigned InstrIdx = Range.first;
+        unsigned NumResults = Range.second;
+        unsigned gIdx = 0; // total number of results handled so far
+        for (unsigned i = 0; i < NumResults; ++i) {
+          // If implicit def type has been added to the result types, we can
+          // end up with NumResults exceeding the number of input results.
+          // However, in the case of multiple results, we don't know which
+          // instruction the implicit def(s) came from. So just make sure we
+          // don't go out of bounds.
+          // FIXME all of the implicit def handling needs cleaned up.
+          if (gIdx >= InTree->getNumResults())
+            break;
+          IterateInference |= OutPattern.getTree(InstrIdx)->UpdateNodeType(
+              i, InTree->getExtType(gIdx++), OutPattern);
+        }
+      }
 
     // If our iteration has converged and the input pattern's types are fully
     // resolved but the result pattern is not fully resolved, we may have a
     // situation where we have two instructions in the result pattern and
     // the instructions require a common register class, but don't care about
     // what actual MVT is used.  This is actually a bug in our modelling:
     // output patterns should have register classes, not MVTs.
     //
     // In any case, to handle this, we just go through and disambiguate some
     // arbitrary types to the result pattern's nodes.
-    if (!IterateInference && InferredAllPatternTypes &&
-        !InferredAllResultTypes)
-      IterateInference =
-          ForceArbitraryInstResultType(Result.getTree(0).get(), Result);
+    if (!IterateInference && InferredAllPatternTypes && !InferredAllResultTypes)
+      for (const TreePatternNodePtr &OT : OutPattern.getTrees())
+        IterateInference = ForceArbitraryInstResultType(OT.get(), OutPattern);
   } while (IterateInference);
 
   // Verify that we inferred enough types that we can do something with the
   // pattern and result.  If these fire the user has to add type casts.
   if (!InferredAllPatternTypes)
-    Pattern.error("Could not infer all types in pattern!");
+    InPattern.error("Could not infer all types in pattern!");
   if (!InferredAllResultTypes) {
-    Pattern.dump();
-    Result.error("Could not infer all types in pattern result!");
+    InPattern.dump();
+    OutPattern.error("Could not infer all types in pattern result!");
   }
 
   // Promote xform function to be an explicit node wherever set.
-  TreePatternNodePtr DstShared = PromoteXForms(Result.getOnlyTree());
-
-  TreePattern Temp(Result.getRecord(), DstShared, false, *this);
-  Temp.InferAllTypes();
+  std::vector<TreePatternNodePtr> ExpandedOutTrees;
+  for (auto &RT : OutPattern.getTrees())
+    ExpandedOutTrees.push_back(PromoteXForms(RT));
+
+  TreePattern ExpandedOutPattern(OutPattern.getRecord(), ExpandedOutTrees,
+                                 false, *this);
+  ExpandedOutPattern.InferAllTypes();
 
   ListInit *Preds = TheDef->getValueAsListInit("Predicates");
   int Complexity = TheDef->getValueAsInt("AddedComplexity");
 
   if (PatternRewriter)
-    PatternRewriter(&Pattern);
+    PatternRewriter(&InPattern);
 
   // A pattern may end up with an "impossible" type, i.e. a situation
   // where all types have been eliminated for some node in this pattern.
   // This could occur for intrinsics that only make sense for a specific
   // value type, and use a specific register class. If, for some mode,
   // that register class does not accept that type, the type inference
   // will lead to a contradiction, which is not an error however, but
   // a sign that this pattern will simply never match.
-  if (Temp.getOnlyTree()->hasPossibleType()) {
-    for (const auto &T : Pattern.getTrees()) {
-      if (T->hasPossibleType())
-        AddPatternToMatch(&Pattern,
-                          PatternToMatch(TheDef, Preds, T, Temp.getOnlyTree(),
-                                         InstImpResults, Complexity,
-                                         TheDef->getID()));
-    }
-  } else {
+  for (const auto &OutTree : ExpandedOutPattern.getTrees()) {
+    if (!OutTree->hasPossibleType()) {
       // Show a message about a dropped pattern with some info to make it
       // easier to identify it in the .td files.
       LLVM_DEBUG({
         dbgs() << "Dropping: ";
-      Pattern.dump();
-      Temp.getOnlyTree()->dump();
+        InPattern.dump();
+        ExpandedOutPattern.dump();
+        dbgs() << "\n";
+        if (ExpandedOutPattern.getNumTrees() > 1) {
+          dbgs() << "  ...because this result tree has no possible types: ";
+          OutTree->dump();
           dbgs() << "\n";
+        }
       });
+      return;
+    }
+  }
+
+  // All result trees have possible types. Add a PatternToMatch for each input
+  // tree which has possible types.
+  for (const auto &InTree : InPattern.getTrees()) {
+    if (InTree->hasPossibleType())
+      AddPatternToMatch(&InPattern,
+                        PatternToMatch(TheDef, Preds, InTree,
+                                       ExpandedOutPattern, InstImpResults,
+                                       Complexity, TheDef->getID()));
   }
 }
 
 void CodeGenDAGPatterns::ParsePatterns() {
   std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern");
 
   for (Record *CurPattern : Patterns) {
     DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch");
 
     // If the pattern references the null_frag, there's nothing to do.
     if (hasNullFragReference(Tree))
       continue;
 
     TreePattern Pattern(CurPattern, Tree, true, *this);
 
     ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs");
     if (LI->empty()) continue;  // no pattern.
 
     // Parse the instruction.
     TreePattern Result(CurPattern, LI, false, *this);
 
-    if (Result.getNumTrees() != 1)
-      Result.error("Cannot handle instructions producing instructions "
-                   "with temporaries yet!");
-
     // Validate that the input pattern is correct.
     std::map<std::string, TreePatternNodePtr> InstInputs;
     MapVector<std::string, TreePatternNodePtr, std::map<std::string, unsigned>>
         InstResults;
     std::vector<Record*> InstImpResults;
     for (unsigned j = 0, ee = Pattern.getNumTrees(); j != ee; ++j)
       FindPatternInputsAndOutputs(Pattern, Pattern.getTree(j), InstInputs,
                                   InstResults, InstImpResults);
 
     ParseOnePattern(CurPattern, Pattern, Result, InstImpResults);
   }
 }
 
 static void collectModes(std::set<unsigned> &Modes, const TreePatternNode *N) {
   for (const TypeSetByHwMode &VTS : N->getExtTypes())
     for (const auto &I : VTS)
       Modes.insert(I.first);
 
   for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
     collectModes(Modes, N->getChild(i));
 }
 
+static void collectModes(std::set<unsigned> &Modes,
+                         const TreePattern &Pattern) {
+  for (const auto &Tree : Pattern.getTrees())
+    collectModes(Modes, Tree.get());
+}
+
 void CodeGenDAGPatterns::ExpandHwModeBasedTypes() {
   const CodeGenHwModes &CGH = getTargetInfo().getHwModes();
   if (CGH.getNumModeIds() == 1)
     return;
 
   std::vector<PatternToMatch> Copy;
   PatternsToMatch.swap(Copy);
 
   auto AppendPattern = [this](PatternToMatch &P, unsigned Mode,
                               StringRef Check) {
     TreePatternNodePtr NewSrc = P.getSrcPattern()->clone();
-    TreePatternNodePtr NewDst = P.getDstPattern()->clone();
-    if (!NewSrc->setDefaultMode(Mode) || !NewDst->setDefaultMode(Mode)) {
+    TreePattern NewDst = P.getDstPattern();
+    if (!NewSrc->setDefaultMode(Mode))
+      return;
+    for (auto &DstTree : NewDst.getTrees())
+      if (!DstTree->setDefaultMode(Mode))
         return;
-    }
 
     PatternsToMatch.emplace_back(P.getSrcRecord(), P.getPredicates(),
                                  std::move(NewSrc), std::move(NewDst),
                                  P.getDstRegs(), P.getAddedComplexity(),
                                  Record::getNewUID(Records), Check);
   };
 
   for (PatternToMatch &P : Copy) {
-    const TreePatternNode *SrcP = nullptr, *DstP = nullptr;
+    const TreePatternNode *SrcP = nullptr;
+    const TreePattern *DstP = nullptr;
     if (P.getSrcPattern()->hasProperTypeByHwMode())
       SrcP = P.getSrcPattern();
-    if (P.getDstPattern()->hasProperTypeByHwMode())
-      DstP = P.getDstPattern();
+    if (P.getDstPattern().hasProperTypeByHwMode())
+      DstP = &P.getDstPattern();
     if (!SrcP && !DstP) {
       PatternsToMatch.push_back(P);
       continue;
     }
 
     std::set<unsigned> Modes;
     if (SrcP)
       collectModes(Modes, SrcP);
     if (DstP)
-      collectModes(Modes, DstP);
+      collectModes(Modes, *DstP);
 
     // The predicate for the default mode needs to be constructed for each
     // pattern separately.
     // Since not all modes must be present in each pattern, if a mode m is
     // absent, then there is no point in constructing a check for m. If such
     // a check was created, it would be equivalent to checking the default
     // mode, except not all modes' predicates would be a part of the checking
     // code. The subsequently generated check for the default mode would then
for (unsigned v = 0, e = Variants.size(); v != e; ++v) {
         }
       }
       // If we already have it, ignore the variant.
       if (AlreadyExists) continue;
 
       // Otherwise, add it to the list of patterns we have.
       PatternsToMatch.emplace_back(
           PatternsToMatch[i].getSrcRecord(), PatternsToMatch[i].getPredicates(),
-          Variant, PatternsToMatch[i].getDstPatternShared(),
+          Variant, PatternsToMatch[i].getDstPattern(),
           PatternsToMatch[i].getDstRegs(),
           PatternsToMatch[i].getAddedComplexity(), Record::getNewUID(Records),
           PatternsToMatch[i].getHwModeFeatures());
     }
 
     LLVM_DEBUG(errs() << "\n");
   }
 }

llvm/utils/TableGen/DAGISelEmitter.cpp

public:
   void run(raw_ostream &OS);
 };
 } // End anonymous namespace
 
 //===----------------------------------------------------------------------===//
 // DAGISelEmitter Helper methods
 //
 
-/// getResultPatternCost - Compute the number of instructions for this pattern.
+/// Compute the number of instructions for this tree.
 /// This is a temporary hack.  We should really include the instruction
 /// latencies in this calculation.
-static unsigned getResultPatternCost(TreePatternNode *P,
-                                     CodeGenDAGPatterns &CGP) {
-  if (P->isLeaf()) return 0;
+static unsigned getResultPatternCost(const TreePatternNode *P,
+                                     const CodeGenDAGPatterns &CGP) {
+  if (P->isLeaf())
+    return 0;
 
   unsigned Cost = 0;
   Record *Op = P->getOperator();
   if (Op->isSubClassOf("Instruction")) {
     Cost++;
     CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(Op);
     if (II.usesCustomInserter)
       Cost += 10;
   }
   for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i)
     Cost += getResultPatternCost(P->getChild(i), CGP);
   return Cost;
 }
 
-/// getResultPatternCodeSize - Compute the code size of instructions for this
-/// pattern.
-static unsigned getResultPatternSize(TreePatternNode *P,
-                                     CodeGenDAGPatterns &CGP) {
-  if (P->isLeaf()) return 0;
+/// Compute the number of instructions for this pattern.
+static unsigned getResultPatternCost(const TreePattern &P,
+                                     const CodeGenDAGPatterns &CGP) {
+  unsigned Cost = 0;
+  for (const TreePatternNodePtr &Tree : P.getTrees())
+    Cost += getResultPatternCost(Tree.get(), CGP);
+  return Cost;
+}
+
+/// Compute the code size of instructions for this tree.
+static unsigned getResultPatternSize(const TreePatternNode *P,
+                                     const CodeGenDAGPatterns &CGP) {
+  if (P->isLeaf())
+    return 0;
 
   unsigned Cost = 0;
   Record *Op = P->getOperator();
   if (Op->isSubClassOf("Instruction")) {
     Cost += Op->getValueAsInt("CodeSize");
   }
   for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i)
     Cost += getResultPatternSize(P->getChild(i), CGP);
   return Cost;
 }
 
+/// Compute the code size of instructions for this pattern.
+static unsigned getResultPatternSize(const TreePattern &P,
+                                     const CodeGenDAGPatterns &CGP) {
+  unsigned Size = 0;
+  for (const TreePatternNodePtr &Tree : P.getTrees())
+    Size += getResultPatternSize(Tree.get(), CGP);
+  return Size;
+}
+
 namespace {
 // PatternSortingPredicate - return true if we prefer to match LHS before RHS.
 // In particular, we want to match maximal patterns first and lowest cost within
 // a particular complexity first.
 struct PatternSortingPredicate {
   PatternSortingPredicate(CodeGenDAGPatterns &cgp) : CGP(cgp) {}
   CodeGenDAGPatterns &CGP;
 
void DAGISelEmitter::run(raw_ostream &OS) {
 
   LLVM_DEBUG(errs() << "\n\nALL PATTERNS TO MATCH:\n\n";
              for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),
                   E = CGP.ptm_end();
                   I != E; ++I) {
                errs() << "PATTERN: ";
                I->getSrcPattern()->dump();
                errs() << "\nRESULT:  ";
-               I->getDstPattern()->dump();
+               I->getDstPattern().dump();
                errs() << "\n";
              });
 
   // Add all the patterns to a temporary list so we can sort them.
   Records.startTimer("Sort patterns");
   std::vector<const PatternToMatch*> Patterns;
   for (const PatternToMatch &PTM : CGP.ptms())
     Patterns.push_back(&PTM);

llvm/utils/TableGen/DAGISelMatcher.cpp

void EmitNodeMatcherCommon::printImpl(raw_ostream &OS, unsigned indent) const {
   for (unsigned i = 0, e = Operands.size(); i != e; ++i)
     OS << Operands[i] << ' ';
   OS << ")\n";
 }
 
 void CompleteMatchMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
   OS.indent(indent) << "CompleteMatch <todo args>\n";
   OS.indent(indent) << "Src = " << *Pattern.getSrcPattern() << "\n";
-  OS.indent(indent) << "Dst = " << *Pattern.getDstPattern() << "\n";
+  OS.indent(indent) << "Dst = " << Pattern.getDstPattern() << "\n";
 }
 
 bool CheckOpcodeMatcher::isEqualImpl(const Matcher *M) const {
   // Note: pointer equality isn't enough here, we have to check the enum names
   // to ensure that the nodes are for the same opcode.
   return cast<CheckOpcodeMatcher>(M)->Opcode.getEnumName() ==
           Opcode.getEnumName();
 }

llvm/utils/TableGen/DAGISelMatcherEmitter.cpp

 #include "DAGISelMatcher.h"
 #include "SDNodeProperties.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Format.h"
+#include "llvm/Support/ScopedPrinter.h" // for llvm::to_string
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/Record.h"
 
 using namespace llvm;
 
 enum {
   IndexWidth = 6,
if (Entry == 0) {
       Entry = NodeXForms.size();
     }
     return Entry-1;
   }
 
 };
 } // end anonymous namespace.
 
-static std::string GetPatFromTreePatternNode(const TreePatternNode *N) {
-  std::string str;
-  raw_string_ostream Stream(str);
-  Stream << *N;
-  return str;
-}
-
 static unsigned GetVBRSize(unsigned Val) {
   if (Val <= 127) return 1;
 
   unsigned NumBytes = 0;
   while (Val >= 128) {
     Val >>= 7;
     ++NumBytes;
   }
case Matcher::CheckType:
 
   case Matcher::EmitNode:
   case Matcher::MorphNodeTo: {
     auto NumCoveredBytes = 0;
     if (InstrumentCoverage) {
       if (const MorphNodeToMatcher *SNT = dyn_cast<MorphNodeToMatcher>(N)) {
         NumCoveredBytes = 3;
         OS << "OPC_Coverage, ";
-        std::string src =
-            GetPatFromTreePatternNode(SNT->getPattern().getSrcPattern());
-        std::string dst =
-            GetPatFromTreePatternNode(SNT->getPattern().getDstPattern());
+        std::string src = to_string(*SNT->getPattern().getSrcPattern());
+        std::string dst = to_string(SNT->getPattern().getDstPattern());
         Record *PatRecord = SNT->getPattern().getSrcRecord();
         std::string include_src = getIncludePath(PatRecord);
         unsigned Offset =
             getPatternIdxFromTable(src + " -> " + dst, std::move(include_src));
         OS << "TARGET_VAL(" << Offset << "),\n";
         OS.indent(FullIndexWidth + Indent);
       }
     }
if (!OmitComments) {
         }
       }
       OS << '\n';
 
       if (const MorphNodeToMatcher *SNT = dyn_cast<MorphNodeToMatcher>(N)) {
         OS.indent(FullIndexWidth + Indent) << "// Src: "
           << *SNT->getPattern().getSrcPattern() << " - Complexity = "
           << SNT->getPattern().getPatternComplexity(CGP) << '\n';
-        OS.indent(FullIndexWidth + Indent) << "// Dst: "
-          << *SNT->getPattern().getDstPattern() << '\n';
+        OS.indent(FullIndexWidth + Indent)
+            << "// Dst: " << SNT->getPattern().getDstPattern() << '\n';
       }
     } else
       OS << '\n';
 
     return 5 + !CompressVTs + EN->getNumVTs() + NumOperandBytes +
            NumCoveredBytes;
   }
   case Matcher::CompleteMatch: {
     const CompleteMatchMatcher *CM = cast<CompleteMatchMatcher>(N);
     auto NumCoveredBytes = 0;
     if (InstrumentCoverage) {
       NumCoveredBytes = 3;
       OS << "OPC_Coverage, ";
-      std::string src =
-          GetPatFromTreePatternNode(CM->getPattern().getSrcPattern());
-      std::string dst =
-          GetPatFromTreePatternNode(CM->getPattern().getDstPattern());
+      std::string src = to_string(*CM->getPattern().getSrcPattern());
+      std::string dst = to_string(CM->getPattern().getDstPattern());
       Record *PatRecord = CM->getPattern().getSrcRecord();
       std::string include_src = getIncludePath(PatRecord);
       unsigned Offset =
           getPatternIdxFromTable(src + " -> " + dst, std::move(include_src));
       OS << "TARGET_VAL(" << Offset << "),\n";
       OS.indent(FullIndexWidth + Indent);
     }
     OS << "OPC_CompleteMatch, " << CM->getNumResults() << ", ";
     unsigned NumResultBytes = 0;
     for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i)
       NumResultBytes += EmitVBRValue(CM->getResult(i), OS);
     OS << '\n';
     if (!OmitComments) {
       OS.indent(FullIndexWidth + Indent) << " // Src: "
         << *CM->getPattern().getSrcPattern() << " - Complexity = "
         << CM->getPattern().getPatternComplexity(CGP) << '\n';
-      OS.indent(FullIndexWidth + Indent) << " // Dst: "
-        << *CM->getPattern().getDstPattern();
+      OS.indent(FullIndexWidth + Indent)
+          << " // Dst: " << CM->getPattern().getDstPattern();
     }
     OS << '\n';
     return 2 + NumResultBytes + NumCoveredBytes;
   }
   }
   llvm_unreachable("Unreachable");
 }
 

llvm/utils/TableGen/DAGISelMatcherGen.cpp

 //===- DAGISelMatcherGen.cpp - Matcher generator --------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "CodeGenDAGPatterns.h"
 #include "CodeGenInstruction.h"
 #include "CodeGenRegisters.h"
 #include "CodeGenTarget.h"
 #include "DAGISelMatcher.h"
 #include "InfoByHwMode.h"
 #include "SDNodeProperties.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
+#include "llvm/Support/ErrorHandling.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/Record.h"
 #include <utility>
 using namespace llvm;
 
 
 /// getRegisterValueType - Look up and return the ValueType of the specified
 /// register. If the register is a member of multiple register classes, they
if (mayInstNodeLoadOrStore(N, CGP))
     ++Count;
 
   for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
     Count += numNodesThatMayLoadOrStore(N->getChild(i), CGP);
 
   return Count;
 }
 
+static unsigned numNodesThatMayLoadOrStore(const TreePattern &Pattern,
+                                           const CodeGenDAGPatterns &CGP) {
+  unsigned Count = 0;
+  for (const auto &Tree : Pattern.getTrees())
+    Count += numNodesThatMayLoadOrStore(Tree.get(), CGP);
+  return Count;
+}
+
 void MatcherGen::
 EmitResultInstructionAsOperand(const TreePatternNode *N,
                                SmallVectorImpl<unsigned> &OutputOps) {
   Record *Op = N->getOperator();
   const CodeGenTarget &CGT = CGP.getTargetInfo();
   CodeGenInstruction &II = CGT.getInstruction(Op);
   const DAGInstruction &Inst = CGP.getInstruction(Op);
 
-  bool isRoot = N == Pattern.getDstPattern();
+  // Is this the root of the first/last tree in the output TreePattern?
+  const bool isFirstRoot = N == Pattern.getDstPattern().getTrees().front();
+  const bool isLastRoot = N == Pattern.getDstPattern().getTrees().back();
+  // Is this any one of the roots?
+  const bool isAnyRoot = llvm::any_of(Pattern.getDstPattern().getTrees(),
+                                      [&](auto &T) { return N == T; });
 
-  // TreeHasOutGlue - True if this tree has glue.
-  bool TreeHasInGlue = false, TreeHasOutGlue = false;
-  if (isRoot) {
-    const TreePatternNode *SrcPat = Pattern.getSrcPattern();
+
+  bool TreeHasInGlue = false;
+  if (isFirstRoot) {
     TreeHasInGlue = SrcPat->TreeHasProperty(SDNPOptInGlue, CGP) ||
                     SrcPat->TreeHasProperty(SDNPInGlue, CGP);
-
-    // FIXME2: this is checking the entire pattern, not just the node in
-    // question, doing this just for the root seems like a total hack.
-    TreeHasOutGlue = SrcPat->TreeHasProperty(SDNPOutGlue, CGP);
-  }
+  }
+  const bool TreeHasOutGlue =
+      isLastRoot && SrcPat->TreeHasProperty(SDNPOutGlue, CGP);
 
   // NumResults - This is the number of results produced by the instruction in
   // the "outs" list.
   unsigned NumResults = Inst.getNumResults();
 
   // Number of operands we know the output instruction must have. If it is
   // variadic, we could have more operands.
   unsigned NumFixedOperands = II.Operands.size();
EmitResultInstructionAsOperand(const TreePatternNode *N,
   if (II.Operands.isVariadic) {
     for (unsigned I = ChildNo, E = N->getNumChildren(); I < E; ++I)
       EmitResultOperand(N->getChild(I), InstOps);
   }
 
   // If this node has input glue or explicitly specified input physregs, we
   // need to add chained and glued copyfromreg nodes and materialize the glue
   // input.
-  if (isRoot && !PhysRegInputs.empty()) {
+  if (isFirstRoot && !PhysRegInputs.empty()) {
     // Emit all of the CopyToReg nodes for the input physical registers.  These
     // occur in patterns like (mul:i8 AL:i8, GR8:i8:$src).
     for (unsigned i = 0, e = PhysRegInputs.size(); i != e; ++i) {
       const CodeGenRegister *Reg =
         CGP.getTargetInfo().getRegBank().getReg(PhysRegInputs[i].first);
       AddMatcher(new EmitCopyToRegMatcher(PhysRegInputs[i].second,
                                           Reg));
     }
 
     // Even if the node has no other glue inputs, the resultant node must be
     // glued to the CopyFromReg nodes we just generated.
     TreeHasInGlue = true;
   }
 
   // Result order: node results, chain, glue
 
   // Determine the result types.
   SmallVector<MVT::SimpleValueType, 4> ResultVTs;
   for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i)
     ResultVTs.push_back(N->getSimpleType(i));
 
-  // If this is the root instruction of a pattern that has physical registers in
-  // its result pattern, add output VTs for them.  For example, X86 has:
+  // If this is the last root instruction of a pattern that has physical
+  // registers in its result pattern, add output VTs for them.  For example, X86
+  // has:
   //   (set AL, (mul ...))
   // This also handles implicit results like:
   //   (implicit EFLAGS)
-  if (isRoot && !Pattern.getDstRegs().empty()) {
+  if (isLastRoot && !Pattern.getDstRegs().empty()) {
     // If the root came from an implicit def in the instruction handling stuff,
     // don't re-add it.
     Record *HandledReg = nullptr;
     if (II.HasOneImplicitDefWithKnownVT(CGT) != MVT::Other)
       HandledReg = II.ImplicitDefs[0];
 
     for (Record *Reg : Pattern.getDstRegs()) {
       if (!Reg->isSubClassOf("Register") || Reg == HandledReg) continue;
       ResultVTs.push_back(getRegisterValueType(Reg, CGT));
     }
   }
 
   // If this is the root of the pattern and the pattern we're matching includes
   // a node that is variadic, mark the generated node as variadic so that it
   // gets the excess operands from the input DAG.
+  const bool srcIsVariadic =
+      Pattern.getSrcPattern()->NodeHasProperty(SDNPVariadic, CGP);
+  if (Pattern.getDstPattern().getNumTrees() > 1 && srcIsVariadic)
+    llvm_unreachable("Unimplemented: Variadic patterns with multiple outputs");
   int NumFixedArityOperands = -1;
-  if (isRoot &&
-      Pattern.getSrcPattern()->NodeHasProperty(SDNPVariadic, CGP))
+  if (isFirstRoot && srcIsVariadic)
     NumFixedArityOperands = Pattern.getSrcPattern()->getNumChildren();
 
-  // If this is the root node and multiple matched nodes in the input pattern
-  // have MemRefs in them, have the interpreter collect them and plop them onto
-  // this node. If there is just one node with MemRefs, leave them on that node
-  // even if it is not the root.
+  // NodeTakesMemRefs indicates that OPFL_MemRefs will be set for the node,
+  // which results in *all* of the MemRefs from the input pattern being applied
+  // to it. This should be modelled more accurately, but for now we
+  // conservatively set it for *all* top level (root) instructions (unless we
+  // can identify a unique memory-accessing instruction).
   //
   // FIXME3: This is actively incorrect for result patterns with multiple
   // memory-referencing instructions.
-  bool PatternHasMemOperands =
-    Pattern.getSrcPattern()->TreeHasProperty(SDNPMemOperand, CGP);
-
-  bool NodeHasMemRefs = false;
-  if (PatternHasMemOperands) {
-    unsigned NumNodesThatLoadOrStore =
+  bool NodeTakesMemRefs = false;
+  if (Pattern.getSrcPattern()->TreeHasProperty(SDNPMemOperand, CGP)) {
+    const unsigned NumNodesThatLoadOrStore =
         numNodesThatMayLoadOrStore(Pattern.getDstPattern(), CGP);
-    bool NodeIsUniqueLoadOrStore = mayInstNodeLoadOrStore(N, CGP) &&
-                                   NumNodesThatLoadOrStore == 1;
-    NodeHasMemRefs =
-      NodeIsUniqueLoadOrStore || (isRoot && (mayInstNodeLoadOrStore(N, CGP) ||
-                                             NumNodesThatLoadOrStore != 1));
+    const bool NMayLoadOrStore = mayInstNodeLoadOrStore(N, CGP);
+    const bool NodeIsUniqueLoadOrStore =
+        NMayLoadOrStore && NumNodesThatLoadOrStore == 1;
+    NodeTakesMemRefs =
+        NodeIsUniqueLoadOrStore ||
+        (isAnyRoot && (NMayLoadOrStore || NumNodesThatLoadOrStore != 1));
   }
 
   // Determine whether we need to attach a chain to this node.
   bool NodeHasChain = false;
   if (Pattern.getSrcPattern()->TreeHasProperty(SDNPHasChain, CGP)) {
     // For some instructions, we were able to infer from the pattern whether
-    // they should have a chain.  Otherwise, attach the chain to the root.
+    // they should have a chain.  Otherwise, attach the chain to all top level
+    // instructions (roots).
     //
     // FIXME2: This is extremely dubious for several reasons, not the least of
     // which it gives special status to instructions with patterns that Pat<>
     // nodes can't duplicate.
     if (II.hasChain_Inferred)
       NodeHasChain = II.hasChain;
     else
-      NodeHasChain = isRoot;
+      NodeHasChain = isAnyRoot;
     // Instructions which load and store from memory should have a chain,
     // regardless of whether they happen to have a pattern saying so.
     if (II.hasCtrlDep || II.mayLoad || II.mayStore || II.canFoldAsLoad ||
         II.hasSideEffects)
       NodeHasChain = true;
   }
+  // Any instruction which is one of multiple outputs must have a chain
+  if (Pattern.getDstPattern().getNumTrees() > 1)
+    NodeHasChain = true;
 
-  assert((!ResultVTs.empty() || TreeHasOutGlue || NodeHasChain) &&
-         "Node has no result");
+  if ((ResultVTs.empty() && !TreeHasOutGlue && !NodeHasChain)) {
+    errs() << *N << '\n';
+    PrintFatalError("Node has no results");
+  }
 
-  AddMatcher(new EmitNodeMatcher(II, ResultVTs, InstOps, NodeHasChain,
-                                 TreeHasInGlue, TreeHasOutGlue, NodeHasMemRefs,
-                                 NumFixedArityOperands, NextRecordedOperandNo));
+  AddMatcher(new EmitNodeMatcher(
+      II, ResultVTs, InstOps, NodeHasChain, TreeHasInGlue, TreeHasOutGlue,
+      NodeTakesMemRefs, NumFixedArityOperands, NextRecordedOperandNo));
 
   // The non-chain and non-glue results of the newly emitted node get recorded.
   for (unsigned i = 0, e = ResultVTs.size(); i != e; ++i) {
     if (ResultVTs[i] == MVT::Other || ResultVTs[i] == MVT::Glue) break;
     OutputOps.push_back(NextRecordedOperandNo++);
   }
 }
 
void MatcherGen::EmitResultCode() {
   // Patterns that match nodes with (potentially multiple) chain inputs have to
   // merge them together into a token factor.  This informs the generated code
   // what all the chained nodes are.
   if (!MatchedChainNodes.empty())
     AddMatcher(new EmitMergeInputChainsMatcher(MatchedChainNodes));
 
   // Codegen the root of the result pattern, capturing the resulting values.
   SmallVector<unsigned, 8> Ops;
-  EmitResultOperand(Pattern.getDstPattern(), Ops);
+  for (const TreePatternNodePtr &Tree : Pattern.getDstPattern().getTrees()) {
+    SmallVector<unsigned, 8> Tmp;
+    EmitResultOperand(Tree.get(), Tmp);
+    Ops.append(Tmp);
+  }
 
   // At this point, we have however many values the result pattern produces.
   // However, the input pattern might not need all of these.  If there are
   // excess values at the end (such as implicit defs of condition codes etc)
   // just lop them off.  This doesn't need to worry about glue or chains, just
   // explicit results.
   //
   unsigned NumSrcResults = Pattern.getSrcPattern()->getNumTypes();
 
   // If the pattern also has (implicit) results, count them as well.
   if (!Pattern.getDstRegs().empty()) {
     // If the root came from an implicit def in the instruction handling stuff,
     // don't re-add it.
     Record *HandledReg = nullptr;
-    const TreePatternNode *DstPat = Pattern.getDstPattern();
+    const TreePatternNodePtr DstPat = Pattern.getDstPattern().getOnlyTree();
     if (!DstPat->isLeaf() &&DstPat->getOperator()->isSubClassOf("Instruction")){
       const CodeGenTarget &CGT = CGP.getTargetInfo();
       CodeGenInstruction &II = CGT.getInstruction(DstPat->getOperator());
 
       if (II.HasOneImplicitDefWithKnownVT(CGT) != MVT::Other)
         HandledReg = II.ImplicitDefs[0];
     }
 
     for (Record *Reg : Pattern.getDstRegs()) {
       if (!Reg->isSubClassOf("Register") || Reg == HandledReg) continue;
       ++NumSrcResults;
     }
   }
 
-  SmallVector<unsigned, 8> Results(Ops);
+  SmallVector<unsigned, 8> Results(Ops.size());
 
   // Apply result permutation.
-  for (unsigned ResNo = 0; ResNo < Pattern.getDstPattern()->getNumResults();
-       ++ResNo) {
-    Results[ResNo] = Ops[Pattern.getDstPattern()->getResultIndex(ResNo)];
+  // If there are multiple result instructions, the results of each root are
+  // added in order but each set may be permuted.
+  //
+  // e.g. inst1 and inst2 results appear in order, but inst2 results are
+  // permuted:
+  //   src pattern: a, b, c = some_ops();
+  //   dst pattern: [a = inst1(); c, b = inst2();]
+  unsigned ResBase = 0;
+  for (const auto &Tree : Pattern.getDstPattern().getTrees()) {
+    for (unsigned i = 0; i < Tree->getNumTypes(); ++i) {
+      Results[ResBase + i] = Ops[ResBase + Tree->getResultIndex(i)];
+    }
+    ResBase += Tree->getNumTypes();
   }
 
   Results.resize(NumSrcResults);
   AddMatcher(new CompleteMatchMatcher(Results, Pattern));
 }
 
 
 /// ConvertPatternToMatcher - Create the matcher for the specified pattern with

llvm/utils/TableGen/FastISelEmitter.cpp

void FastISelMap::collectPatterns(CodeGenDAGPatterns &CGP) {
 
   // Scan through all the patterns and record the simple ones.
   for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),
        E = CGP.ptm_end(); I != E; ++I) {
     const PatternToMatch &Pattern = *I;
 
     // For now, just look at Instructions, so that we don't have to worry
     // about emitting multiple instructions for a pattern.
-    TreePatternNode *Dst = Pattern.getDstPattern();
-    if (Dst->isLeaf()) continue;
+    if (Pattern.getDstPattern().getNumTrees() > 1)
+      continue;
+    const TreePatternNodePtr &Dst = Pattern.getDstPattern().getOnlyTree();
+    if (Dst->isLeaf())
+      continue;
     Record *Op = Dst->getOperator();
     if (!Op->isSubClassOf("Instruction"))
       continue;
     CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(Op);
     if (II.Operands.empty())
       continue;
 
     // Allow instructions to be marked as unavailable for FastISel for
if (!StringSwitch<bool>(ManglingSuffix)
         .Default(false))
       continue;
 
     // Get the predicate that guards this pattern.
     std::string PredicateCheck = Pattern.getPredicateCheck();
 
     // Ok, we found a pattern that we can handle. Remember it.
     InstructionMemo Memo(
-      Pattern.getDstPattern()->getOperator()->getName(),
-      DstRC,
-      SubRegNo,
-      PhysRegInputs,
-      PredicateCheck
-    );
+        Pattern.getDstPattern().getOnlyTree()->getOperator()->getName(), DstRC,
+        SubRegNo, PhysRegInputs, PredicateCheck);
 
     int complexity = Pattern.getPatternComplexity(CGP);
 
     auto inserted_simple_pattern = SimplePatternsCheck.insert(
         std::make_tuple(Operands, OpcodeName, VT, RetVT, PredicateCheck));
     if (!inserted_simple_pattern.second) {
       PrintFatalError(Pattern.getSrcRecord()->getLoc(),
                     "Duplicate predicate in FastISel table!");

llvm/utils/TableGen/GlobalISelEmitter.cpp

std::optional<CodeGenSubRegIndex *> GlobalISelEmitter::inferSubRegIndexForNode(
   return CGRegs.getSubRegIdx(SubRegInit->getDef());
 }
 
 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
   // Keep track of the matchers and actions to emit.
   int Score = P.getPatternComplexity(CGP);
   RuleMatcher M(P.getSrcRecord()->getLoc());
   RuleMatcherScores[M.getRuleID()] = Score;
-  M.addAction<DebugCommentAction>(llvm::to_string(*P.getSrcPattern()) +
-                                  "  =>  " +
-                                  llvm::to_string(*P.getDstPattern()));
+
+  if (P.getDstPattern().getNumTrees() > 1)
+    return failedImport("Dst pattern with multiple roots not implemented yet.");
+
+  TreePatternNode *Dst = P.getDstPattern().getOnlyTree().get();
+  TreePatternNode *Src = P.getSrcPattern();
+
+  M.addAction<DebugCommentAction>(llvm::to_string(*Src) + "  =>  " +
+                                  llvm::to_string(*Dst));
 
   SmallVector<Record *, 4> Predicates;
   P.getPredicateRecords(Predicates);
   if (auto Error = importRulePredicates(M, Predicates))
     return std::move(Error);
 
   // Next, analyze the pattern operators.
-  TreePatternNode *Src = P.getSrcPattern();
-  TreePatternNode *Dst = P.getDstPattern();
 
   // If the root of either pattern isn't a simple operator, ignore it.
   if (auto Err = isTrivialOperatorNode(Dst))
     return failedImport("Dst pattern root isn't a trivial operator (" +
                         toString(std::move(Err)) + ")");
   if (auto Err = isTrivialOperatorNode(Src))
     return failedImport("Src pattern root isn't a trivial operator (" +
                         toString(std::move(Err)) + ")");