[gicombiner] Add GIMatchTree and use it for the code generation

[dsanders]

Summary

GIMatchTree's job is to build a decision tree by zipping all the
GIMatchDag's together.

Each DAG is added to the tree builder as a leaf and partitioners are used
to subdivide each node until there are no more partitioners to apply. At
this point, the code generator is responsible for testing any untested
predicates and following any unvisited traversals (there shouldn't be any
of the latter as the getVRegDef partitioner handles them all).

Note that the leaves don't always fit into partitions cleanly and the
partitions may overlap as a result. This is resolved by cloning the leaf
into every partition it belongs to. One example of this is a rule that can
match one of N opcodes. The leaf for this rule would end up in N partitions
when processed by the opcode partitioner. A similar example is the
getVRegDef partitioner where having rules (add $a, $b), and (add ($a, $b), $c)
will result in the former being in the partition for successfully
following the vreg-def and failing to do so as it doesn't care which
happens.

Depends on D69151

[dsanders]

Rebase

[dsanders]

Rebase

[volkan]

LGTM.

llvm/include/llvm/Target/GlobalISel/Combine.td

106–108

Missing wip_match_opcode for COPY?

[dsanders]

llvm/include/llvm/Target/GlobalISel/Combine.td

106–108

It's not needed here as COPY is the only thing it matches. wip_match_opcode is a temporary way of matching one of a set of opcodes until the feature that supports a choice of patterns becomes available.

[thakis]

This broke tests on Windows: http://45.33.8.238/win/5239/step_11.txt

Probably the "%p doesn't include 0x on Windows" thing again.

[dsanders]

In D69152#1808445, @thakis wrote:

This broke tests on Windows: http://45.33.8.238/win/5239/step_11.txt

Probably the "%p doesn't include 0x on Windows" thing again.

It looks like I undid the fixup I did the last time I committed this. It should be fixed in 19110fd982b (I cherry-picked 77d4b5f5fef to re-apply the fix)

[thakis]

Thanks, the bot is happy again. (Looks like the commit landed just now though.)

llvm/include/llvm/Target/GlobalISel/Combine.td

 /// * A MIR code block (deprecated)
 /// The GIMatchKind and GIMatchKindWithArgs cases are described in more detail
 /// in their definitions below.
 /// For the Instruction case, these are collected into a DAG where operand names
 /// that occur multiple times introduce edges.
 class GIMatchKind;
 class GIMatchKindWithArgs;
 
+/// In lieu of having proper macro support. Trivial one-off opcode checks can be
+/// performed with this.
+def wip_match_opcode : GIMatchKindWithArgs;
+
 /// The operator at the root of a GICombineRule.Apply dag.
 def apply;
 /// All arguments of the apply operator must be subclasses of GIApplyKind, or
 /// sub-dags whose operator is GIApplyKindWithArgs, or an MIR block
 /// (deprecated).
 class GIApplyKind;
 class GIApplyKindWithArgs;
 
 def copy_prop : GICombineRule<
   (defs root:$d),
-  (match [{ return Helper.matchCombineCopy(${d}); }]),
-  (apply [{ Helper.applyCombineCopy(${d}); }])>;
+  (match (COPY $d, $s):$mi,
+         [{ return Helper.matchCombineCopy(*${mi}); }]),
+  (apply [{ Helper.applyCombineCopy(*${mi}); }])>;
 def trivial_combines : GICombineGroup<[copy_prop]>;
 
 def extending_loads : GICombineRule<
   (defs root:$root, extending_load_matchdata:$matchinfo),
-  (match [{ return Helper.matchCombineExtendingLoads(${root}, ${matchinfo}); }]),
-  (apply [{ Helper.applyCombineExtendingLoads(${root}, ${matchinfo}); }])>;
+  (match (wip_match_opcode G_LOAD, G_SEXTLOAD, G_ZEXTLOAD):$root,
+         [{ return Helper.matchCombineExtendingLoads(*${root}, ${matchinfo}); }]),
+  (apply [{ Helper.applyCombineExtendingLoads(*${root}, ${matchinfo}); }])>;
 def combines_for_extload: GICombineGroup<[extending_loads]>;
 
 def combine_indexed_load_store : GICombineRule<
   (defs root:$root, indexed_load_store_matchdata:$matchinfo),
-  (match [{ return Helper.matchCombineIndexedLoadStore(${root}, ${matchinfo}); }]),
-  (apply [{ Helper.applyCombineIndexedLoadStore(${root}, ${matchinfo}); }])>;
+  (match (wip_match_opcode G_LOAD, G_SEXTLOAD, G_ZEXTLOAD, G_STORE):$root,
+         [{ return Helper.matchCombineIndexedLoadStore(*${root}, ${matchinfo}); }]),
+  (apply [{ Helper.applyCombineIndexedLoadStore(*${root}, ${matchinfo}); }])>;
 
 // FIXME: Is there a reason this wasn't in tryCombine? I've left it out of
 //        all_combines because it wasn't there.
 def elide_br_by_inverting_cond : GICombineRule<
-  (defs root:$d),
-  (match [{ return Helper.matchElideBrByInvertingCond(${d}); }]),
-  (apply [{ Helper.applyElideBrByInvertingCond(${d}); }])>;
+  (defs root:$root),
+  (match (wip_match_opcode G_BR):$root,
+         [{ return Helper.matchElideBrByInvertingCond(*${root}); }]),
+  (apply [{ Helper.applyElideBrByInvertingCond(*${root}); }])>;
 
 def all_combines : GICombineGroup<[trivial_combines, combines_for_extload, combine_indexed_load_store]>;

llvm/test/TableGen/GICombinerEmitter/match-tree.td

+// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \
+// RUN:     -combiners=MyCombinerHelper -gicombiner-stop-after-build %s \
+// RUN:     -o /dev/null -debug 2>&1 | FileCheck %s
+
+include "llvm/Target/Target.td"
+include "llvm/Target/GlobalISel/Combine.td"
+
+def MyTargetISA : InstrInfo;
+def MyTarget : Target { let InstructionSet = MyTargetISA; }
+
+def dummy;
+
+def R0 : Register<"r0"> { let Namespace = "MyTarget"; }
+def GPR32 : RegisterClass<"MyTarget", [i32], 32, (add R0)>;
+class I<dag OOps, dag IOps, list<dag> Pat>
+  : Instruction {
+  let Namespace = "MyTarget";
+  let OutOperandList = OOps;
+  let InOperandList = IOps;
+  let Pattern = Pat;
+}
+def MOV : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
+def ADD : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>;
+def SUB : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>;
+def MUL : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>;
+def TRUNC : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
+def SEXT : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
+def ZEXT : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
+
+def Rule0 : GICombineRule<
+  (defs root:$d),
+  (match (MUL $t, $s1, $s2),
+         (SUB $d, $t, $s3)),
+  (apply [{ APPLY }])>;
+
+def Rule1 : GICombineRule<
+  (defs root:$d),
+  (match (MOV $s1, $s2),
+         (MOV $d, $s1)),
+  (apply [{ APPLY }])>;
+
+def Rule2 : GICombineRule<
+  (defs root:$d),
+  (match (MOV $d, $s)),
+  (apply [{ APPLY }])>;
+
+def Rule3 : GICombineRule<
+  (defs root:$d),
+  (match (MUL $t, $s1, $s2),
+         (ADD $d, $t, $s3), [{ A }]),
+  (apply [{ APPLY }])>;
+
+def Rule4 : GICombineRule<
+  (defs root:$d),
+  (match (ADD $d, $s1, $s2)),
+  (apply [{ APPLY }])>;
+
+def Rule5 : GICombineRule<
+  (defs root:$d),
+  (match (SUB $d, $s1, $s2)),
+  (apply [{ APPLY }])>;
+
+def Rule6 : GICombineRule<
+  (defs root:$d),
+  (match (SEXT $t, $s1),
+         (TRUNC $d, $t)),
+  (apply [{ APPLY }])>;
+
+def Rule7 : GICombineRule<
+  (defs root:$d),
+  (match (ZEXT $t, $s1),
+         (TRUNC $d, $t)),
+  (apply [{ APPLY }])>;
+
+def MyCombinerHelper: GICombinerHelper<"GenMyCombinerHelper", [
+  Rule0,
+  Rule1,
+  Rule2,
+  Rule3,
+  Rule4,
+  Rule5,
+  Rule6,
+  Rule7
+]>;
+
+// CHECK-LABEL: digraph "matchtree" {
+// CHECK-DAG:   Node[[N0:0x[0-9a-f]+]] [shape=record,label="{MI[0].getOpcode()|4 partitions|Rule0,Rule1,Rule2,Rule3,Rule4,Rule5,Rule6,Rule7}"]
+// CHECK-DAG:   Node[[N1:0x[0-9a-f]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|2 partitions|Rule0,Rule5}"]
+// CHECK-DAG:   Node[[N2:0x[0-9a-f]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule0,Rule5}"]
+// CHECK-DAG:   Node[[N3:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule0}"]
+// CHECK-DAG:   Node[[N4:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule5}"]
+// CHECK-DAG:   Node[[N5:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule5}"]
+// CHECK-DAG:   Node[[N6:0x[0-9a-f]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|2 partitions|Rule1,Rule2}"]
+// CHECK-DAG:   Node[[N7:0x[0-9a-f]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule1,Rule2}"]
+// CHECK-DAG:   Node[[N8:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule1}"]
+// CHECK-DAG:   Node[[N9:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule2}"]
+// CHECK-DAG:   Node[[N10:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule2}"]
+// CHECK-DAG:   Node[[N11:0x[0-9a-f]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|2 partitions|Rule3,Rule4}"]
+// CHECK-DAG:   Node[[N12:0x[0-9a-f]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule3,Rule4}"]
+// CHECK-DAG:   Node[[N13:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule3,Rule4}",color=red]
+// CHECK-DAG:   Node[[N14:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule4}"]
+// CHECK-DAG:   Node[[N15:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule4}"]
+// CHECK-DAG:   Node[[N16:0x[0-9a-f]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|1 partitions|Rule6,Rule7}"]
+// CHECK-DAG:   Node[[N17:0x[0-9a-f]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule6,Rule7}"]
+// CHECK-DAG:   Node[[N18:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule6}"]
+// CHECK-DAG:   Node[[N19:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule7}"]
+
+// The most important partitioner is on the first opcode:
+// CHECK-DAG:   Node[[N0]] -> Node[[N1]] [label="#0 MyTarget::SUB"]
+// CHECK-DAG:   Node[[N0]] -> Node[[N6]] [label="#1 MyTarget::MOV"]
+// CHECK-DAG:   Node[[N0]] -> Node[[N11]] [label="#2 MyTarget::ADD"]
+// CHECK-DAG:   Node[[N0]] -> Node[[N16]] [label="#3 MyTarget::TRUNC"]
+
+// For, MI[0].getOpcode() == SUB, then has to determine whether it has a reg
+// operand and follow that link. If it can't then Rule5 is the only choice as
+// that rule is not constrained to a reg.
+// CHECK-DAG:   Node[[N1]] -> Node[[N2]] [label="#0 true"]
+// CHECK-DAG:   Node[[N1]] -> Node[[N5]] [label="#1 false"]
+
+// For, MI[0].getOpcode() == SUB && MI[0].getOperand(1).isReg(), if MI[1] is a
+// MUL then it must be either Rule0 or Rule5. Rule0 is fully tested so Rule5 is
+// unreachable. If it's not MUL then it must be Rule5.
+// CHECK-DAG:   Node[[N2]] -> Node[[N3]] [label="#0 MyTarget::MUL"]
+// CHECK-DAG:   Node[[N2]] -> Node[[N4]] [label="#1 * or nullptr"]
+
+// CHECK-DAG:   Node[[N6]] -> Node[[N7]] [label="#0 true"]
+// CHECK-DAG:   Node[[N6]] -> Node[[N10]] [label="#1 false"]
+
+// CHECK-DAG:   Node[[N7]] -> Node[[N8]] [label="#0 MyTarget::MOV"]
+// CHECK-DAG:   Node[[N7]] -> Node[[N9]] [label="#1 * or nullptr"]
+
+// CHECK-DAG:   Node[[N11]] -> Node[[N12]] [label="#0 true"]
+// CHECK-DAG:   Node[[N11]] -> Node[[N15]] [label="#1 false"]
+
+// CHECK-DAG:   Node[[N12]] -> Node[[N13]] [label="#0 MyTarget::MUL"]
+// CHECK-DAG:   Node[[N12]] -> Node[[N14]] [label="#1 * or nullptr"]
+
+// CHECK-DAG:   Node[[N16]] -> Node[[N17]] [label="#0 true"]
+
+// CHECK-DAG:   Node[[N17]] -> Node[[N18]] [label="#0 MyTarget::SEXT"]
+// CHECK-DAG:   Node[[N17]] -> Node[[N19]] [label="#1 MyTarget::ZEXT"]
+// CHECK-LABEL: {{^}$}}

llvm/utils/TableGen/GICombinerEmitter.cpp

 #include "llvm/Support/Timer.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/StringMatcher.h"
 #include "llvm/TableGen/TableGenBackend.h"
 #include "CodeGenTarget.h"
 #include "GlobalISel/CodeExpander.h"
 #include "GlobalISel/CodeExpansions.h"
 #include "GlobalISel/GIMatchDag.h"
+#include "GlobalISel/GIMatchTree.h"
 #include <cstdint>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "gicombiner-emitter"
 
 // FIXME: Use ALWAYS_ENABLED_STATISTIC once it's available.
 unsigned NumPatternTotal = 0;
 STATISTIC(NumPatternTotalStatistic, "Total number of patterns");
 
 cl::OptionCategory
     GICombinerEmitterCat("Options for -gen-global-isel-combiner");
 static cl::list<std::string>
     SelectedCombiners("combiners", cl::desc("Emit the specified combiners"),
                       cl::cat(GICombinerEmitterCat), cl::CommaSeparated);
 static cl::opt<bool> ShowExpansions(
     "gicombiner-show-expansions",
     cl::desc("Use C++ comments to indicate occurence of code expansion"),
     cl::cat(GICombinerEmitterCat));
 static cl::opt<bool> StopAfterParse(
     "gicombiner-stop-after-parse",
     cl::desc("Stop processing after parsing rules and dump state"),
     cl::cat(GICombinerEmitterCat));
+static cl::opt<bool> StopAfterBuild(
+    "gicombiner-stop-after-build",
+    cl::desc("Stop processing after building the match tree"),
+    cl::cat(GICombinerEmitterCat));
 
 namespace {
 typedef uint64_t RuleID;
 
 // We're going to be referencing the same small strings quite a lot for operand
 // names and the like. Make their lifetime management simple with a global
 // string table.
 StringSet<> StrTab;
 
 StringRef insertStrTab(StringRef S) {
   if (S.empty())
     return S;
   return StrTab.insert(S).first->first();
 }
 
+class format_partition_name {
+  const GIMatchTree &Tree;
+  unsigned Idx;
+
+public:
+  format_partition_name(const GIMatchTree &Tree, unsigned Idx)
+      : Tree(Tree), Idx(Idx) {}
+  void print(raw_ostream &OS) const {
+    Tree.getPartitioner()->emitPartitionName(OS, Idx);
+  }
+};
+raw_ostream &operator<<(raw_ostream &OS, const format_partition_name &Fmt) {
+  Fmt.print(OS);
+  return OS;
+}
+
 /// Declares data that is passed from the match stage to the apply stage.
 class MatchDataInfo {
   /// The symbol used in the tablegen patterns
   StringRef PatternSymbol;
   /// The data type for the variable
   StringRef Type;
   /// The name of the variable as declared in the generated matcher.
   std::string VariableName;
protected:
 
   void declareMatchData(StringRef PatternSymbol, StringRef Type,
                         StringRef VarName);
 
   bool parseInstructionMatcher(const CodeGenTarget &Target, StringInit *ArgName,
                                const Init &Arg,
                                StringMap<std::vector<VarInfo>> &NamedEdgeDefs,
                                StringMap<std::vector<VarInfo>> &NamedEdgeUses);
+  bool parseWipMatchOpcodeMatcher(const CodeGenTarget &Target,
+                                  StringInit *ArgName, const Init &Arg);
 
 public:
   CombineRule(const CodeGenTarget &Target, GIMatchDagContext &Ctx, RuleID ID,
               const Record &R)
       : ID(ID), TheDef(R), MatchDag(Ctx) {}
   CombineRule(const CombineRule &) = delete;
 
   bool parseDefs();

 static Record *getDefOfSubClass(const Init &N, StringRef Cls) {
   if (const DefInit *OpI = dyn_cast<DefInit>(&N))
     if (OpI->getDef()->isSubClassOf(Cls))
       return OpI->getDef();
   return nullptr;
 }
 
 /// A convenience function to check that an Init refers to a dag whose operator
+/// is a specific def and coerce it to a dag if it is. This is primarily useful
+/// for testing for subclasses of GIMatchKind and similar in DagInit's since
+/// DagInit's support any type inside them.
+static const DagInit *getDagWithSpecificOperator(const Init &N,
+                                                 StringRef Name) {
+  if (const DagInit *I = dyn_cast<DagInit>(&N))
+    if (I->getNumArgs() > 0)
+      if (const DefInit *OpI = dyn_cast<DefInit>(I->getOperator()))
+        if (OpI->getDef()->getName() == Name)
+          return I;
+  return nullptr;
+}
+
+/// A convenience function to check that an Init refers to a dag whose operator
 /// is a def that is a subclass of the given class and coerce it to a dag if it
 /// is. This is primarily useful for testing for subclasses of GIMatchKind and
 /// similar in DagInit's since DagInit's support any type inside them.
 static const DagInit *getDagWithOperatorOfSubClass(const Init &N,
                                                    StringRef Cls) {
   if (const DagInit *I = dyn_cast<DagInit>(&N))
     if (I->getNumArgs() > 0)
       if (const DefInit *OpI = dyn_cast<DefInit>(I->getOperator()))
for (const auto &NameInit : Matcher->getArgNames()) {
       OpIdx++;
     }
 
     return true;
   }
   return false;
 }
 
+// Parse the wip_match_opcode placeholder that's temporarily present in lieu of
+// implementing macros or choices between two matchers.
+bool CombineRule::parseWipMatchOpcodeMatcher(const CodeGenTarget &Target,
+                                             StringInit *ArgName,
+                                             const Init &Arg) {
+  if (const DagInit *Matcher =
+          getDagWithSpecificOperator(Arg, "wip_match_opcode")) {
+    StringRef Name = ArgName ? ArgName->getValue() : "";
+
+    GIMatchDagInstr *N =
+        MatchDag.addInstrNode(makeDebugName(*this, Name), insertStrTab(Name),
+                              MatchDag.getContext().makeEmptyOperandList());
+
+    if (find_if(Roots, [&](const RootInfo &X) {
+          return ArgName && X.getPatternSymbol() == ArgName->getValue();
+        }) != Roots.end()) {
+      N->setMatchRoot();
+    }
+
+    const auto &P = MatchDag.addPredicateNode<GIMatchDagOneOfOpcodesPredicate>(
+        makeNameForAnonPredicate(*this));
+    MatchDag.addPredicateDependency(N, nullptr, P, &P->getOperandInfo()["mi"]);
+    // Each argument is an opcode that will pass this predicate. Add them all to
+    // the predicate implementation
+    for (const auto &Arg : Matcher->getArgs()) {
+      Record *OpcodeDef = getDefOfSubClass(*Arg, "Instruction");
+      if (OpcodeDef) {
+        P->addOpcode(&Target.getInstruction(OpcodeDef));
+        continue;
+      }
+      PrintError(TheDef.getLoc(),
+                 "Arguments to wip_match_opcode must be instructions");
+      return false;
+    }
+    return true;
+  }
+  return false;
+}
 bool CombineRule::parseMatcher(const CodeGenTarget &Target) {
   NamedRegionTimer T("parseMatcher", "Time spent parsing the matcher",
                      "Rule Parsing", "Time spent on rule parsing", TimeRegions);
   StringMap<std::vector<VarInfo>> NamedEdgeDefs;
   StringMap<std::vector<VarInfo>> NamedEdgeUses;
   DagInit *Matchers = TheDef.getValueAsDag("Match");
 
   if (Matchers->getOperatorAsDef(TheDef.getLoc())->getName() != "match") {
bool CombineRule::parseMatcher(const CodeGenTarget &Target) {
   // The match section consists of a list of matchers and predicates. Parse each
   // one and add the equivalent GIMatchDag nodes, predicates, and edges.
   for (unsigned I = 0; I < Matchers->getNumArgs(); ++I) {
     if (parseInstructionMatcher(Target, Matchers->getArgName(I),
                                 *Matchers->getArg(I), NamedEdgeDefs,
                                 NamedEdgeUses))
       continue;
 
+    if (parseWipMatchOpcodeMatcher(Target, Matchers->getArgName(I),
+                                   *Matchers->getArg(I)))
+      continue;
+
 
     // Parse arbitrary C++ code we have in lieu of supporting MIR matching
     if (const CodeInit *CodeI = dyn_cast<CodeInit>(Matchers->getArg(I))) {
       assert(!MatchingFixupCode &&
              "Only one block of arbitrary code is currently permitted");
       MatchingFixupCode = CodeI;
+      MatchDag.setHasPostMatchPredicate(true);
       continue;
     }
 
     PrintError(TheDef.getLoc(),
                "Expected a subclass of GIMatchKind or a sub-dag whose "
                "operator is either of a GIMatchKindWithArgs or Instruction");
     PrintNote("Pattern was `" + Matchers->getArg(I)->getAsString() + "'");
     return false;
public:
   StringRef getClassName() const {
     return Combiner->getValueAsString("Classname");
   }
   void run(raw_ostream &OS);
 
   /// Emit the name matcher (guarded by #ifndef NDEBUG) used to disable rules in
   /// response to the generated cl::opt.
   void emitNameMatcher(raw_ostream &OS) const;
-  void generateCodeForRule(raw_ostream &OS, const CombineRule *Rule,
+
+  void generateDeclarationsCodeForTree(raw_ostream &OS, const GIMatchTree &Tree) const;
+  void generateCodeForTree(raw_ostream &OS, const GIMatchTree &Tree,
                            StringRef Indent) const;
 };
 
 GICombinerEmitter::GICombinerEmitter(RecordKeeper &RK,
                                      const CodeGenTarget &Target,
                                      StringRef Name, Record *Combiner)
     : Name(Name), Target(Target), Combiner(Combiner) {}
 
GICombinerEmitter::makeCombineRule(const Record &TheDef) {
   LLVM_DEBUG({
     dbgs() << "Parsed rule defs/match for '" << Rule->getName() << "'\n";
     Rule->getMatchDag().dump();
     Rule->getMatchDag().writeDOTGraph(dbgs(), Rule->getName());
   });
   if (StopAfterParse)
     return Rule;
 
+  // For now, don't support traversing from def to use. We'll come back to
+  // this later once we have the algorithm changes to support it.
+  bool EmittedDefToUseError = false;
+  for (const auto &E : Rule->getMatchDag().edges()) {
+    if (E->isDefToUse()) {
+      if (!EmittedDefToUseError) {
+        PrintError(
+            TheDef.getLoc(),
+            "Generated state machine cannot lookup uses from a def (yet)");
+        EmittedDefToUseError = true;
+      }
+      PrintNote("Node " + to_string(*E->getFromMI()));
+      PrintNote("Node " + to_string(*E->getToMI()));
+      PrintNote("Edge " + to_string(*E));
+    }
+  }
+  if (EmittedDefToUseError)
+    return nullptr;
+
   // For now, don't support multi-root rules. We'll come back to this later
   // once we have the algorithm changes to support it.
   if (Rule->getNumRoots() > 1) {
     PrintError(TheDef.getLoc(), "Multi-root matches are not supported (yet)");
     return nullptr;
   }
   return Rule;
 }
if (R->isValueUnset("Rules")) {
       }
       ActiveRules.emplace_back(std::move(Rule));
       ++NumPatternTotal;
     } else
       gatherRules(ActiveRules, R->getValueAsListOfDefs("Rules"));
   }
 }
 
-void GICombinerEmitter::generateCodeForRule(raw_ostream &OS,
-                                            const CombineRule *Rule,
+void GICombinerEmitter::generateCodeForTree(raw_ostream &OS,
+                                            const GIMatchTree &Tree,
                                             StringRef Indent) const {
-  {
+  if (Tree.getPartitioner() != nullptr) {
+    Tree.getPartitioner()->generatePartitionSelectorCode(OS, Indent);
+    for (const auto &EnumChildren : enumerate(Tree.children())) {
+      OS << Indent << "if (Partition == " << EnumChildren.index() << " /* "
+         << format_partition_name(Tree, EnumChildren.index()) << " */) {\n";
+      generateCodeForTree(OS, EnumChildren.value(), (Indent + "  ").str());
+      OS << Indent << "}\n";
+    }
+    return;
+  }
+
+  bool AnyFullyTested = false;
+  for (const auto &Leaf : Tree.possible_leaves()) {
+    OS << Indent << "// Leaf name: " << Leaf.getName() << "\n";
+
+    const CombineRule *Rule = Leaf.getTargetData<CombineRule>();
     const Record &RuleDef = Rule->getDef();
 
     OS << Indent << "// Rule: " << RuleDef.getName() << "\n"
        << Indent << "if (!isRuleDisabled(" << Rule->getID() << ")) {\n";
 
     CodeExpansions Expansions;
-    for (const RootInfo &Root : Rule->roots()) {
-      Expansions.declare(Root.getPatternSymbol(), "MI");
+    for (const auto &VarBinding : Leaf.var_bindings()) {
+      if (VarBinding.isInstr())
+        Expansions.declare(VarBinding.getName(),
+                           "MIs[" + to_string(VarBinding.getInstrID()) + "]");
+      else
+        Expansions.declare(VarBinding.getName(),
+                           "MIs[" + to_string(VarBinding.getInstrID()) +
+                               "]->getOperand(" +
+                               to_string(VarBinding.getOpIdx()) + ")");
     }
     Rule->declareExpansions(Expansions);
 
     DagInit *Applyer = RuleDef.getValueAsDag("Apply");
     if (Applyer->getOperatorAsDef(RuleDef.getLoc())->getName() !=
         "apply") {
       PrintError(RuleDef.getLoc(), "Expected apply operator");
       return;
     }
 
     OS << Indent << "  if (1\n";
 
+    // Attempt to emit code for any untested predicates left over. Note that
+    // isFullyTested() will remain false even if we succeed here and therefore
+    // combine rule elision will not be performed. This is because we do not
+    // know if there's any connection between the predicates for each leaf and
+    // therefore can't tell if one makes another unreachable. Ideally, the
+    // partitioner(s) would be sufficiently complete to prevent us from having
+    // untested predicates left over.
+    for (const GIMatchDagPredicate *Predicate : Leaf.untested_predicates()) {
+      if (Predicate->generateCheckCode(OS, (Indent + "      ").str(),
+                                       Expansions))
+        continue;
+      PrintError(RuleDef.getLoc(),
+                 "Unable to test predicate used in rule");
+      PrintNote(SMLoc(),
+                "This indicates an incomplete implementation in tablegen");
+      Predicate->print(errs());
+      errs() << "\n";
+      OS << Indent
+         << "llvm_unreachable(\"TableGen did not emit complete code for this "
+            "path\");\n";
+      break;
+    }
+
     if (Rule->getMatchingFixupCode() &&
         !Rule->getMatchingFixupCode()->getValue().empty()) {
       // FIXME: Single-use lambda's like this are a serious compile-time
       // performance and memory issue. It's convenient for this early stage to
       // defer some work to successive patches but we need to eliminate this
       // before the ruleset grows to small-moderate size. Last time, it became
       // a big problem for low-mem systems around the 500 rule mark but by the
       // time we grow that large we should have merged the ISel match table
if (const CodeInit *Code = dyn_cast<CodeInit>(Applyer->getArg(0))) {
          << Indent << "    return true;\n"
          << Indent << "  }\n";
     } else {
       PrintError(RuleDef.getLoc(), "Expected apply code block");
       return;
     }
 
     OS << Indent << "}\n";
+
+    assert(Leaf.isFullyTraversed());
+
+    // If we didn't have any predicates left over and we're not using the
+    // trap-door we have to support arbitrary C++ code while we're migrating to
+    // the declarative style then we know that subsequent leaves are
+    // unreachable.
+    if (Leaf.isFullyTested() &&
+        (!Rule->getMatchingFixupCode() ||
+         Rule->getMatchingFixupCode()->getValue().empty())) {
+      AnyFullyTested = true;
+      OS << Indent
+         << "llvm_unreachable(\"Combine rule elision was incorrect\");\n"
+         << Indent << "return false;\n";
+    }
   }
+  if (!AnyFullyTested)
+    OS << Indent << "return false;\n";
 }
 
 void GICombinerEmitter::run(raw_ostream &OS) {
   gatherRules(Rules, Combiner->getValueAsListOfDefs("Rules"));
   if (StopAfterParse) {
     MatchDagCtx.print(errs());
     PrintNote(Combiner->getLoc(),
               "Terminating due to -gicombiner-stop-after-parse");
     return;
   }
   if (ErrorsPrinted)
     PrintFatalError(Combiner->getLoc(), "Failed to parse one or more rules");
+  LLVM_DEBUG(dbgs() << "Optimizing tree for " << Rules.size() << " rules\n");
+  std::unique_ptr<GIMatchTree> Tree;
+  {
+    NamedRegionTimer T("Optimize", "Time spent optimizing the combiner",
+                       "Code Generation", "Time spent generating code",
+                       TimeRegions);
+
+    GIMatchTreeBuilder TreeBuilder(0);
+    for (const auto &Rule : Rules) {
+      bool HadARoot = false;
+      for (const auto &Root : enumerate(Rule->getMatchDag().roots())) {
+        TreeBuilder.addLeaf(Rule->getName(), Root.index(), Rule->getMatchDag(),
+                            Rule.get());
+        HadARoot = true;
+      }
+      if (!HadARoot)
+        PrintFatalError(Rule->getDef().getLoc(), "All rules must have a root");
+    }
+
+    Tree = TreeBuilder.run();
+  }
+  if (StopAfterBuild) {
+    Tree->writeDOTGraph(outs());
+    PrintNote(Combiner->getLoc(),
+              "Terminating due to -gicombiner-stop-after-build");
+    return;
+  }
 
   NamedRegionTimer T("Emit", "Time spent emitting the combiner",
                      "Code Generation", "Time spent generating code",
                      TimeRegions);
   OS << "#ifdef " << Name.upper() << "_GENCOMBINERHELPER_DEPS\n"
      << "#include \"llvm/ADT/SparseBitVector.h\"\n"
      << "namespace llvm {\n"
      << "extern cl::OptionCategory GICombinerOptionCategory;\n"
void GICombinerEmitter::run(raw_ostream &OS) {
   OS << "bool " << getClassName() << "::tryCombineAll(\n"
      << "    GISelChangeObserver &Observer,\n"
      << "    MachineInstr &MI,\n"
      << "    MachineIRBuilder &B,\n"
      << "    CombinerHelper &Helper) const {\n"
      << "  MachineBasicBlock *MBB = MI.getParent();\n"
      << "  MachineFunction *MF = MBB->getParent();\n"
      << "  MachineRegisterInfo &MRI = MF->getRegInfo();\n"
+     << "  SmallVector<MachineInstr *, 8> MIs = { &MI };\n\n"
      << "  (void)MBB; (void)MF; (void)MRI;\n\n";
 
   OS << "  // Match data\n";
   for (const auto &Rule : Rules)
     for (const auto &I : Rule->matchdata_decls())
       OS << "  " << I.getType() << " " << I.getVariableName() << ";\n";
   OS << "\n";
 
-  for (const auto &Rule : Rules)
-    generateCodeForRule(OS, Rule.get(), "  ");
+  OS << "  int Partition = -1;\n";
+  generateCodeForTree(OS, *Tree, "  ");
   OS << "\n  return false;\n"
      << "}\n"
      << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_CPP\n";
 }
 
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//

llvm/utils/TableGen/GlobalISel/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 llvm_add_library(LLVMTableGenGlobalISel STATIC DISABLE_LLVM_LINK_LLVM_DYLIB
                  CodeExpander.cpp
                  GIMatchDag.cpp
                  GIMatchDagEdge.cpp
                  GIMatchDagInstr.cpp
                  GIMatchDagOperands.cpp
                  GIMatchDagPredicate.cpp
                  GIMatchDagPredicateDependencyEdge.cpp
+                 GIMatchTree.cpp
                 )

llvm/utils/TableGen/GlobalISel/GIMatchDag.h

 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   LLVM_DUMP_METHOD void dump() const { print(errs()); }
 #endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 };
 
 class GIMatchDag {
 public:
   using InstrNodesVec = std::vector<std::unique_ptr<GIMatchDagInstr>>;
+  using instr_node_iterator = raw_pointer_iterator<InstrNodesVec::iterator>;
+  using const_instr_node_iterator =
+      raw_pointer_iterator<InstrNodesVec::const_iterator>;
+
   using EdgesVec = std::vector<std::unique_ptr<GIMatchDagEdge>>;
   using edge_iterator = raw_pointer_iterator<EdgesVec::iterator>;
   using const_edge_iterator = raw_pointer_iterator<EdgesVec::const_iterator>;
 
   using PredicateNodesVec = std::vector<std::unique_ptr<GIMatchDagPredicate>>;
+  using predicate_iterator = raw_pointer_iterator<PredicateNodesVec::iterator>;
+  using const_predicate_iterator =
+      raw_pointer_iterator<PredicateNodesVec::const_iterator>;
 
   using PredicateDependencyEdgesVec =
       std::vector<std::unique_ptr<GIMatchDagPredicateDependencyEdge>>;
+  using predicate_edge_iterator =
+      raw_pointer_iterator<PredicateDependencyEdgesVec::iterator>;
+  using const_predicate_edge_iterator =
+      raw_pointer_iterator<PredicateDependencyEdgesVec::const_iterator>;
 
 protected:
   GIMatchDagContext &Ctx;
   InstrNodesVec InstrNodes;
   PredicateNodesVec PredicateNodes;
   EdgesVec Edges;
   PredicateDependencyEdgesVec PredicateDependencies;
   std::vector<GIMatchDagInstr *> MatchRoots;
+  // FIXME: This is a temporary measure while we still accept arbitrary code
+  //        blocks to fix up the matcher while it's being developed.
+  bool HasPostMatchPredicate = false;
 
 public:
   GIMatchDag(GIMatchDagContext &Ctx)
       : Ctx(Ctx), InstrNodes(), PredicateNodes(), Edges(),
         PredicateDependencies() {}
   GIMatchDag(const GIMatchDag &) = delete;
 
   GIMatchDagContext &getContext() const { return Ctx; }
public:
   }
   iterator_range<std::vector<GIMatchDagInstr *>::iterator> roots() {
     return make_range(MatchRoots.begin(), MatchRoots.end());
   }
   iterator_range<std::vector<GIMatchDagInstr *>::const_iterator> roots() const {
     return make_range(MatchRoots.begin(), MatchRoots.end());
   }
 
+  instr_node_iterator instr_nodes_begin() {
+    return raw_pointer_iterator<InstrNodesVec::iterator>(InstrNodes.begin());
+  }
+  instr_node_iterator instr_nodes_end() {
+    return raw_pointer_iterator<InstrNodesVec::iterator>(InstrNodes.end());
+  }
+  const_instr_node_iterator instr_nodes_begin() const {
+    return raw_pointer_iterator<InstrNodesVec::const_iterator>(
+        InstrNodes.begin());
+  }
+  const_instr_node_iterator instr_nodes_end() const {
+    return raw_pointer_iterator<InstrNodesVec::const_iterator>(
+        InstrNodes.end());
+  }
+  iterator_range<instr_node_iterator> instr_nodes() {
+    return make_range(instr_nodes_begin(), instr_nodes_end());
+  }
+  iterator_range<const_instr_node_iterator> instr_nodes() const {
+    return make_range(instr_nodes_begin(), instr_nodes_end());
+  }
+  predicate_edge_iterator predicate_edges_begin() {
+    return raw_pointer_iterator<PredicateDependencyEdgesVec::iterator>(
+        PredicateDependencies.begin());
+  }
+  predicate_edge_iterator predicate_edges_end() {
+    return raw_pointer_iterator<PredicateDependencyEdgesVec::iterator>(
+        PredicateDependencies.end());
+  }
+  const_predicate_edge_iterator predicate_edges_begin() const {
+    return raw_pointer_iterator<PredicateDependencyEdgesVec::const_iterator>(
+        PredicateDependencies.begin());
+  }
+  const_predicate_edge_iterator predicate_edges_end() const {
+    return raw_pointer_iterator<PredicateDependencyEdgesVec::const_iterator>(
+        PredicateDependencies.end());
+  }
+  iterator_range<predicate_edge_iterator> predicate_edges() {
+    return make_range(predicate_edges_begin(), predicate_edges_end());
+  }
+  iterator_range<const_predicate_edge_iterator> predicate_edges() const {
+    return make_range(predicate_edges_begin(), predicate_edges_end());
+  }
+  predicate_iterator predicates_begin() {
+    return raw_pointer_iterator<PredicateNodesVec::iterator>(
+        PredicateNodes.begin());
+  }
+  predicate_iterator predicates_end() {
+    return raw_pointer_iterator<PredicateNodesVec::iterator>(
+        PredicateNodes.end());
+  }
+  const_predicate_iterator predicates_begin() const {
+    return raw_pointer_iterator<PredicateNodesVec::const_iterator>(
+        PredicateNodes.begin());
+  }
+  const_predicate_iterator predicates_end() const {
+    return raw_pointer_iterator<PredicateNodesVec::const_iterator>(
+        PredicateNodes.end());
+  }
+  iterator_range<predicate_iterator> predicates() {
+    return make_range(predicates_begin(), predicates_end());
+  }
+  iterator_range<const_predicate_iterator> predicates() const {
+    return make_range(predicates_begin(), predicates_end());
+  }
+
   template <class... Args> GIMatchDagInstr *addInstrNode(Args &&... args) {
     auto Obj =
         std::make_unique<GIMatchDagInstr>(*this, std::forward<Args>(args)...);
     auto ObjRaw = Obj.get();
     InstrNodes.push_back(std::move(Obj));
     return ObjRaw;
   }
 
public:
   GIMatchDagPredicateDependencyEdge *addPredicateDependency(Args &&... args) {
     auto Obj = std::make_unique<GIMatchDagPredicateDependencyEdge>(
         std::forward<Args>(args)...);
     auto ObjRaw = Obj.get();
     PredicateDependencies.push_back(std::move(Obj));
     return ObjRaw;
   }
 
+  size_t getInstrNodeIdx(instr_node_iterator I) {
+    return std::distance(instr_nodes_begin(), I);
+  }
+  size_t getInstrNodeIdx(const_instr_node_iterator I) const {
+    return std::distance(instr_nodes_begin(), I);
+  }
+  size_t getNumInstrNodes() const { return InstrNodes.size(); }
+  size_t getNumEdges() const { return Edges.size(); }
+  size_t getNumPredicates() const { return PredicateNodes.size(); }
+
+  void setHasPostMatchPredicate(bool V) { HasPostMatchPredicate = V; }
+  bool hasPostMatchPredicate() const { return HasPostMatchPredicate; }
+
   void addMatchRoot(GIMatchDagInstr *N) { MatchRoots.push_back(N); }
 
   LLVM_DUMP_METHOD void print(raw_ostream &OS) const;
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   LLVM_DUMP_METHOD void dump() const { print(errs()); }
 #endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 
   void writeDOTGraph(raw_ostream &OS, StringRef ID) const;
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const GIMatchDag &G);
 
 } // end namespace llvm
 
 #endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAG_H

llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.h

public:
   const GIMatchDagInstr *getFromMI() const { return FromMI; }
   const GIMatchDagOperand *getFromMO() const { return FromMO; }
   const GIMatchDagInstr *getToMI() const { return ToMI; }
   const GIMatchDagOperand *getToMO() const { return ToMO; }
 
   /// Flip the direction of the edge.
   void reverse();
 
+  /// Does this edge run from a def to (one of many) uses?
+  bool isDefToUse() const;
+
   LLVM_DUMP_METHOD void print(raw_ostream &OS) const;
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   LLVM_DUMP_METHOD void dump() const;
 #endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const GIMatchDagEdge &E);
 
 } // end namespace llvm
 #endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGEDGE_H

llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.cpp

 using namespace llvm;
 
 LLVM_DUMP_METHOD void GIMatchDagEdge::print(raw_ostream &OS) const {
   OS << getFromMI()->getName() << "[" << getFromMO()->getName() << "] --["
      << Name << "]--> " << getToMI()->getName() << "[" << getToMO()->getName()
      << "]";
 }
 
+bool GIMatchDagEdge::isDefToUse() const {
+  // Def -> Def is invalid so we only need to check FromMO.
+  return FromMO->isDef();
+}
+
 void GIMatchDagEdge::reverse() {
   std::swap(FromMI, ToMI);
   std::swap(FromMO, ToMO);
 }
 
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+LLVM_DUMP_METHOD void GIMatchDagEdge::dump() const { print(errs()); }
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const GIMatchDagEdge &E) {
+  E.print(OS);
+  return OS;
+}

llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h

 public:
   GIMatchDagInstr(GIMatchDag &Dag, StringRef Name, StringRef UserAssignedName,
                   const GIMatchDagOperandList &OperandInfo)
       : Dag(Dag), Name(Name), UserAssignedName(UserAssignedName),
         OperandInfo(OperandInfo) {}
 
   const GIMatchDagOperandList &getOperandInfo() const { return OperandInfo; }
   StringRef getName() const { return Name; }
+  StringRef getUserAssignedName() const { return UserAssignedName; }
   void assignNameToOperand(unsigned Idx, StringRef Name) {
     assert(UserAssignedNamesForOperands[Idx].empty() && "Cannot assign twice");
     UserAssignedNamesForOperands[Idx] = Name;
   }
 
   const_user_assigned_operand_names_iterator
   user_assigned_operand_names_begin() const {
     return UserAssignedNamesForOperands.begin();

llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.h

 //===- GIMatchDagPredicate - Represent a predicate to check ---------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATE_H
 #define LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATE_H
 
 #include "llvm/ADT/StringRef.h"
 #include "GIMatchDag.h"
+
 namespace llvm {
+class CodeExpansions;
 class CodeGenInstruction;
 class GIMatchDagOperandList;
 class GIMatchDagContext;
 class raw_ostream;
 
 /// Represents a predicate on the match DAG. This records the details of the
 /// predicate. The dependencies are stored in the GIMatchDag as edges.
 ///
 /// Instances of this class objects are owned by the GIMatchDag and are not
 /// shareable between instances of GIMatchDag.
 class GIMatchDagPredicate {
 public:
   enum GIMatchDagPredicateKind {
     GIMatchDagPredicateKind_Opcode,
+    GIMatchDagPredicateKind_OneOfOpcodes,
     GIMatchDagPredicateKind_SameMO,
   };
 
 protected:
   const GIMatchDagPredicateKind Kind;
 
   /// The name of the predicate. For example:
   ///     (FOO $a:s32, $b, $c)
GIMatchDagPredicate(GIMatchDagPredicateKind Kind, StringRef Name,
       : Kind(Kind), Name(Name), OperandInfo(OperandInfo) {}
   virtual ~GIMatchDagPredicate() {}
 
   GIMatchDagPredicateKind getKind() const { return Kind; }
 
   StringRef getName() const { return Name; }
   const GIMatchDagOperandList &getOperandInfo() const { return OperandInfo; }
 
+  // Generate C++ code to check this predicate. If a partitioner has already
+  // tested this predicate then this function won't be called. If this function
+  // is called, it must emit code and return true to indicate that it did so. If
+  // it ever returns false, then the caller will abort due to an untested
+  // predicate.
+  virtual bool generateCheckCode(raw_ostream &OS, StringRef Indent,
+                                 const CodeExpansions &Expansions) const {
+    return false;
+  }
+
   virtual void print(raw_ostream &OS) const;
   virtual void printDescription(raw_ostream &OS) const;
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   virtual LLVM_DUMP_METHOD void dump() const { print(errs()); }
 #endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 };
 
public:
 
   void printDescription(raw_ostream &OS) const override;
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   virtual LLVM_DUMP_METHOD void dump() const override { print(errs()); }
 #endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 };
 
+class GIMatchDagOneOfOpcodesPredicate : public GIMatchDagPredicate {
+  SmallVector<const CodeGenInstruction *, 4> Instrs;
+
+public:
+  GIMatchDagOneOfOpcodesPredicate(GIMatchDagContext &Ctx, StringRef Name);
+
+  void addOpcode(const CodeGenInstruction *Instr) { Instrs.push_back(Instr); }
+
+  static bool classof(const GIMatchDagPredicate *P) {
+    return P->getKind() == GIMatchDagPredicateKind_OneOfOpcodes;
+  }
+
+  const SmallVectorImpl<const CodeGenInstruction *> &getInstrs() const {
+    return Instrs;
+  }
+
+  void printDescription(raw_ostream &OS) const override;
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  virtual LLVM_DUMP_METHOD void dump() const override { print(errs()); }
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+};
+
 class GIMatchDagSameMOPredicate : public GIMatchDagPredicate {
 public:
   GIMatchDagSameMOPredicate(GIMatchDagContext &Ctx, StringRef Name);
 
   static bool classof(const GIMatchDagPredicate *P) {
     return P->getKind() == GIMatchDagPredicateKind_SameMO;
   }
 

llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.cpp

 //===- GIMatchDagPredicate.cpp - Represent a predicate to check -----------===//
 //
 // 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 "GIMatchDagPredicate.h"
+
 #include "llvm/TableGen/Record.h"
 
 #include "GIMatchDagOperands.h"
 #include "../CodeGenInstruction.h"
 
 using namespace llvm;
 
 void GIMatchDagPredicate::print(raw_ostream &OS) const {
GIMatchDagOpcodePredicate::GIMatchDagOpcodePredicate(
     : GIMatchDagPredicate(GIMatchDagPredicateKind_Opcode, Name,
                           Ctx.makeMIPredicateOperandList()),
       Instr(Instr) {}
 
 void GIMatchDagOpcodePredicate::printDescription(raw_ostream &OS) const {
   OS << "$mi.getOpcode() == " << Instr.TheDef->getName();
 }
 
+GIMatchDagOneOfOpcodesPredicate::GIMatchDagOneOfOpcodesPredicate(
+    GIMatchDagContext &Ctx, StringRef Name)
+    : GIMatchDagPredicate(GIMatchDagPredicateKind_OneOfOpcodes, Name,
+                          Ctx.makeMIPredicateOperandList()) {}
+
+void GIMatchDagOneOfOpcodesPredicate::printDescription(raw_ostream &OS) const {
+  OS << "$mi.getOpcode() == oneof(";
+  StringRef Separator = "";
+  for (const CodeGenInstruction *Instr : Instrs) {
+    OS << Separator << Instr->TheDef->getName();
+    Separator = ",";
+  }
+  OS << ")";
+}
+
 GIMatchDagSameMOPredicate::GIMatchDagSameMOPredicate(GIMatchDagContext &Ctx,
                                                      StringRef Name)
     : GIMatchDagPredicate(GIMatchDagPredicateKind_SameMO, Name,
                           Ctx.makeTwoMOPredicateOperandList()) {}
 
 void GIMatchDagSameMOPredicate::printDescription(raw_ostream &OS) const {
   OS << "$mi0 == $mi1";
 }

llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.cpp

 //===- GIMatchDagPredicateDependencyEdge.cpp - Have inputs before check ---===//
 //
 // 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 "GIMatchDagPredicateDependencyEdge.h"
 
 #include "GIMatchDagInstr.h"
 #include "GIMatchDagPredicate.h"
 
+#include "llvm/Support/raw_ostream.h"
+
 using namespace llvm;
 
 LLVM_DUMP_METHOD void
 GIMatchDagPredicateDependencyEdge::print(raw_ostream &OS) const {
   OS << getRequiredMI()->getName();
   if (getRequiredMO())
     OS << "[" << getRequiredMO()->getName() << "]";
   OS << " ==> " << getPredicate()->getName() << "["

llvm/utils/TableGen/GlobalISel/GIMatchTree.h

+//===- GIMatchTree.h - A decision tree to match GIMatchDag's --------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREE_H
+#define LLVM_UTILS_TABLEGEN_GIMATCHTREE_H
+
+#include "GIMatchDag.h"
+#include "llvm/ADT/BitVector.h"
+
+namespace llvm {
+class raw_ostream;
+
+class GIMatchTreeBuilder;
+class GIMatchTreePartitioner;
+
+/// Describes the binding of a variable to the matched MIR
+class GIMatchTreeVariableBinding {
+  /// The name of the variable described by this binding.
+  StringRef Name;
+  // The matched instruction it is bound to. 
+  unsigned InstrID;
+  // The matched operand (if appropriate) it is bound to. 
+  Optional<unsigned> OpIdx;
+
+public:
+  GIMatchTreeVariableBinding(StringRef Name, unsigned InstrID,
+                             Optional<unsigned> OpIdx = None)
+      : Name(Name), InstrID(InstrID), OpIdx(OpIdx) {}
+
+  bool isInstr() const { return !OpIdx.hasValue(); }
+  StringRef getName() const { return Name; }
+  unsigned getInstrID() const { return InstrID; }
+  unsigned getOpIdx() const {
+    assert(OpIdx.hasValue() && "Is not an operand binding");
+    return *OpIdx;
+  }
+};
+
+/// Associates a matchable with a leaf of the decision tree.
+class GIMatchTreeLeafInfo {
+public:
+  using const_var_binding_iterator =
+      std::vector<GIMatchTreeVariableBinding>::const_iterator;
+  using UntestedPredicatesTy = SmallVector<const GIMatchDagPredicate *, 1>;
+  using const_untested_predicates_iterator = UntestedPredicatesTy::const_iterator;
+
+protected:
+  /// A name for the matchable. This is primarily for debugging.
+  StringRef Name;
+  /// Where rules have multiple roots, this is which root we're starting from.
+  unsigned RootIdx;
+  /// Opaque data the caller of the tree building code understands.
+  void *Data;
+  /// Has the decision tree covered every edge traversal? If it hasn't then this
+  /// is an unrecoverable error indicating there's something wrong with the
+  /// partitioners.
+  bool IsFullyTraversed;
+  /// Has the decision tree covered every predicate test? If it has, then
+  /// subsequent matchables on the same leaf are unreachable. If it hasn't, the
+  /// code that requested the GIMatchTree is responsible for finishing off any
+  /// remaining predicates.
+  bool IsFullyTested;
+  /// The variable bindings associated with this leaf so far.
+  std::vector<GIMatchTreeVariableBinding> VarBindings;
+  /// Any predicates left untested by the time we reach this leaf.
+  UntestedPredicatesTy UntestedPredicates;
+
+public:
+  GIMatchTreeLeafInfo() { llvm_unreachable("Cannot default-construct"); }
+  GIMatchTreeLeafInfo(StringRef Name, unsigned RootIdx, void *Data)
+      : Name(Name), RootIdx(RootIdx), Data(Data), IsFullyTraversed(false),
+        IsFullyTested(false) {}
+
+  StringRef getName() const { return Name; }
+  unsigned getRootIdx() const { return RootIdx; }
+  template <class Ty> Ty *getTargetData() const {
+    return static_cast<Ty *>(Data);
+  }
+  bool isFullyTraversed() const { return IsFullyTraversed; }
+  void setIsFullyTraversed(bool V) { IsFullyTraversed = V; }
+  bool isFullyTested() const { return IsFullyTested; }
+  void setIsFullyTested(bool V) { IsFullyTested = V; }
+
+  void bindInstrVariable(StringRef Name, unsigned InstrID) {
+    VarBindings.emplace_back(Name, InstrID);
+  }
+  void bindOperandVariable(StringRef Name, unsigned InstrID, unsigned OpIdx) {
+    VarBindings.emplace_back(Name, InstrID, OpIdx);
+  }
+
+  const_var_binding_iterator var_bindings_begin() const {
+    return VarBindings.begin();
+  }
+  const_var_binding_iterator var_bindings_end() const {
+    return VarBindings.end();
+  }
+  iterator_range<const_var_binding_iterator> var_bindings() const {
+    return make_range(VarBindings.begin(), VarBindings.end());
+  }
+  iterator_range<const_untested_predicates_iterator> untested_predicates() const {
+    return make_range(UntestedPredicates.begin(), UntestedPredicates.end());
+  }
+  void addUntestedPredicate(const GIMatchDagPredicate *P) {
+    UntestedPredicates.push_back(P);
+  }
+};
+
+/// The nodes of a decision tree used to perform the match.
+/// This will be used to generate the C++ code or state machine equivalent.
+///
+/// It should be noted that some nodes of this tree (most notably nodes handling
+/// def -> use edges) will need to iterate over several possible matches. As
+/// such, code generated from this will sometimes need to support backtracking.
+class GIMatchTree {
+  using LeafVector = std::vector<GIMatchTreeLeafInfo>;
+
+  /// The partitioner that has been chosen for this node. This may be nullptr if
+  /// a partitioner hasn't been chosen yet or if the node is a leaf.
+  std::unique_ptr<GIMatchTreePartitioner> Partitioner;
+  /// All the leaves that are possible for this node of the tree.
+  /// Note: This should be emptied after the tree is built when there are
+  /// children but this currently isn't done to aid debuggability of the DOT
+  /// graph for the decision tree.
+  LeafVector PossibleLeaves;
+  /// The children of this node. The index into this array must match the index
+  /// chosen by the partitioner.
+  std::vector<GIMatchTree> Children;
+
+  void writeDOTGraphNode(raw_ostream &OS) const;
+  void writeDOTGraphEdges(raw_ostream &OS) const;
+
+public:
+  void writeDOTGraph(raw_ostream &OS) const;
+
+  void setNumChildren(unsigned Num) { Children.resize(Num); }
+  void addPossibleLeaf(const GIMatchTreeLeafInfo &V, bool IsFullyTraversed,
+                       bool IsFullyTested) {
+    PossibleLeaves.push_back(V);
+    PossibleLeaves.back().setIsFullyTraversed(IsFullyTraversed);
+    PossibleLeaves.back().setIsFullyTested(IsFullyTested);
+  }
+  void dropLeavesAfter(size_t Length) {
+    if (PossibleLeaves.size() > Length)
+      PossibleLeaves.resize(Length);
+  }
+  void setPartitioner(std::unique_ptr<GIMatchTreePartitioner> &&V) {
+    Partitioner = std::move(V);
+  }
+  GIMatchTreePartitioner *getPartitioner() const { return Partitioner.get(); }
+
+  std::vector<GIMatchTree>::iterator children_begin() {
+    return Children.begin();
+  }
+  std::vector<GIMatchTree>::iterator children_end() { return Children.end(); }
+  iterator_range<std::vector<GIMatchTree>::iterator> children() {
+    return make_range(children_begin(), children_end());
+  }
+  std::vector<GIMatchTree>::const_iterator children_begin() const {
+    return Children.begin();
+  }
+  std::vector<GIMatchTree>::const_iterator children_end() const {
+    return Children.end();
+  }
+  iterator_range<std::vector<GIMatchTree>::const_iterator> children() const {
+    return make_range(children_begin(), children_end());
+  }
+
+  LeafVector::const_iterator possible_leaves_begin() const {
+    return PossibleLeaves.begin();
+  }
+  LeafVector::const_iterator possible_leaves_end() const {
+    return PossibleLeaves.end();
+  }
+  iterator_range<LeafVector::const_iterator>
+  possible_leaves() const {
+    return make_range(possible_leaves_begin(), possible_leaves_end());
+  }
+  LeafVector::iterator possible_leaves_begin() {
+    return PossibleLeaves.begin();
+  }
+  LeafVector::iterator possible_leaves_end() {
+    return PossibleLeaves.end();
+  }
+  iterator_range<LeafVector::iterator> possible_leaves() {
+    return make_range(possible_leaves_begin(), possible_leaves_end());
+  }
+};
+
+/// Record information that is known about the instruction bound to this ID and
+/// GIMatchDagInstrNode. Every rule gets its own set of
+/// GIMatchTreeInstrInfo to bind the shared IDs to an instr node in its
+/// DAG.
+///
+/// For example, if we know that there are 3 operands. We can record it here to
+/// elide duplicate checks.
+class GIMatchTreeInstrInfo {
+  /// The instruction ID for the matched instruction.
+  unsigned ID;
+  /// The corresponding instruction node in the MatchDAG.
+  const GIMatchDagInstr *InstrNode;
+
+public:
+  GIMatchTreeInstrInfo(unsigned ID, const GIMatchDagInstr *InstrNode)
+      : ID(ID), InstrNode(InstrNode) {}
+
+  unsigned getID() const { return ID; }
+  const GIMatchDagInstr *getInstrNode() const { return InstrNode; }
+};
+
+/// Record information that is known about the operand bound to this ID, OpIdx,
+/// and GIMatchDagInstrNode. Every rule gets its own set of
+/// GIMatchTreeOperandInfo to bind the shared IDs to an operand of an
+/// instr node from its DAG.
+///
+/// For example, if we know that there the operand is a register. We can record
+/// it here to elide duplicate checks.
+class GIMatchTreeOperandInfo {
+  /// The corresponding instruction node in the MatchDAG that the operand
+  /// belongs to.
+  const GIMatchDagInstr *InstrNode;
+  unsigned OpIdx;
+
+public:
+  GIMatchTreeOperandInfo(const GIMatchDagInstr *InstrNode, unsigned OpIdx)
+      : InstrNode(InstrNode), OpIdx(OpIdx) {}
+
+  const GIMatchDagInstr *getInstrNode() const { return InstrNode; }
+  unsigned getOpIdx() const { return OpIdx; }
+};
+
+/// Represent a leaf of the match tree and any working data we need to build the
+/// tree.
+///
+/// It's important to note that each rule can have multiple
+/// GIMatchTreeBuilderLeafInfo's since the partitioners do not always partition
+/// into mutually-exclusive partitions. For example:
+///   R1: (FOO ..., ...)
+///   R2: (oneof(FOO, BAR) ..., ...)
+/// will partition by opcode into two partitions FOO=>[R1, R2], and BAR=>[R2]
+///
+/// As an optimization, all instructions, edges, and predicates in the DAGs are
+/// numbered and tracked in BitVectors. As such, the GIMatchDAG must not be
+/// modified once construction of the tree has begun.
+class GIMatchTreeBuilderLeafInfo {
+protected:
+  GIMatchTreeBuilder &Builder;
+  GIMatchTreeLeafInfo Info;
+  const GIMatchDag &MatchDag;
+  /// The association between GIMatchDagInstr* and GIMatchTreeInstrInfo.
+  /// The primary reason for this members existence is to allow the use of
+  /// InstrIDToInfo.lookup() since that requires that the value is
+  /// default-constructible.
+  DenseMap<const GIMatchDagInstr *, GIMatchTreeInstrInfo> InstrNodeToInfo;
+  /// The instruction information for a given ID in the context of this
+  /// particular leaf.
+  DenseMap<unsigned, GIMatchTreeInstrInfo *> InstrIDToInfo;
+  /// The operand information for a given ID and OpIdx in the context of this
+  /// particular leaf.
+  DenseMap<std::pair<unsigned, unsigned>, GIMatchTreeOperandInfo>
+      OperandIDToInfo;
+
+public:
+  /// The remaining instrs/edges/predicates to visit
+  BitVector RemainingInstrNodes;
+  BitVector RemainingEdges;
+  BitVector RemainingPredicates;
+
+  // The remaining predicate dependencies for each predicate
+  std::vector<BitVector> UnsatisfiedPredDepsForPred;
+
+  /// The edges/predicates we can visit as a result of the declare*() calls we
+  /// have already made. We don't need an instrs version since edges imply the
+  /// instr.
+  BitVector TraversableEdges;
+  BitVector TestablePredicates;
+
+  /// Map predicates from the DAG to their position in the DAG predicate
+  /// iterators.
+  DenseMap<GIMatchDagPredicate *, unsigned> PredicateIDs;
+  /// Map predicate dependency edges from the DAG to their position in the DAG
+  /// predicate dependency iterators.
+  DenseMap<GIMatchDagPredicateDependencyEdge *, unsigned> PredicateDepIDs;
+
+public:
+  GIMatchTreeBuilderLeafInfo(GIMatchTreeBuilder &Builder, StringRef Name,
+                             unsigned RootIdx, const GIMatchDag &MatchDag,
+                             void *Data);
+
+  StringRef getName() const { return Info.getName(); }
+  GIMatchTreeLeafInfo &getInfo() { return Info; }
+  const GIMatchTreeLeafInfo &getInfo() const { return Info; }
+  const GIMatchDag &getMatchDag() const { return MatchDag; }
+  unsigned getRootIdx() const { return Info.getRootIdx(); }
+
+  /// Has this DAG been fully traversed. This must be true by the time the tree
+  /// builder finishes.
+  bool isFullyTraversed() const {
+    // We don't need UnsatisfiedPredDepsForPred because RemainingPredicates
+    // can't be all-zero without satisfying all the dependencies. The same is
+    // almost true for Edges and Instrs but it's possible to have Instrs without
+    // Edges.
+    return RemainingInstrNodes.none() && RemainingEdges.none();
+  }
+
+  /// Has this DAG been fully tested. This hould be true by the time the tree
+  /// builder finishes but clients can finish any untested predicates left over
+  /// if it's not true.
+  bool isFullyTested() const {
+    // We don't need UnsatisfiedPredDepsForPred because RemainingPredicates
+    // can't be all-zero without satisfying all the dependencies. The same is
+    // almost true for Edges and Instrs but it's possible to have Instrs without
+    // Edges.
+    return RemainingInstrNodes.none() && RemainingEdges.none() &&
+           RemainingPredicates.none();
+  }
+
+  const GIMatchDagInstr *getInstr(unsigned Idx) const {
+    return *(MatchDag.instr_nodes_begin() + Idx);
+  }
+  const GIMatchDagEdge *getEdge(unsigned Idx) const {
+    return *(MatchDag.edges_begin() + Idx);
+  }
+  GIMatchDagEdge *getEdge(unsigned Idx) {
+    return *(MatchDag.edges_begin() + Idx);
+  }
+  const GIMatchDagPredicate *getPredicate(unsigned Idx) const {
+    return *(MatchDag.predicates_begin() + Idx);
+  }
+  iterator_range<llvm::BitVector::const_set_bits_iterator>
+  untested_instrs() const {
+    return RemainingInstrNodes.set_bits();
+  }
+  iterator_range<llvm::BitVector::const_set_bits_iterator>
+  untested_edges() const {
+    return RemainingEdges.set_bits();
+  }
+  iterator_range<llvm::BitVector::const_set_bits_iterator>
+  untested_predicates() const {
+    return RemainingPredicates.set_bits();
+  }
+
+  /// Bind an instr node to the given ID and clear any blocking dependencies
+  /// that were waiting for it.
+  void declareInstr(const GIMatchDagInstr *Instr, unsigned ID);
+
+  /// Bind an operand to the given ID and OpIdx and clear any blocking
+  /// dependencies that were waiting for it.
+  void declareOperand(unsigned InstrID, unsigned OpIdx);
+
+  GIMatchTreeInstrInfo *getInstrInfo(unsigned ID) const {
+    auto I = InstrIDToInfo.find(ID);
+    if (I != InstrIDToInfo.end())
+      return I->second;
+    return nullptr;
+  }
+
+  void dump(raw_ostream &OS) const {
+    OS << "Leaf " << getName() << " for root #" << getRootIdx() << "\n";
+    MatchDag.print(OS);
+    for (const auto &I : InstrIDToInfo)
+      OS << "Declared Instr #" << I.first << "\n";
+    for (const auto &I : OperandIDToInfo)
+      OS << "Declared Instr #" << I.first.first << ", Op #" << I.first.second
+         << "\n";
+    OS << RemainingInstrNodes.count() << " untested instrs of "
+       << RemainingInstrNodes.size() << "\n";
+    OS << RemainingEdges.count() << " untested edges of "
+       << RemainingEdges.size() << "\n";
+    OS << RemainingPredicates.count() << " untested predicates of "
+       << RemainingPredicates.size() << "\n";
+
+    OS << TraversableEdges.count() << " edges could be traversed\n";
+    OS << TestablePredicates.count() << " predicates could be tested\n";
+  }
+};
+
+/// The tree builder has a fairly tough job. It's purpose is to merge all the
+/// DAGs from the ruleset into a decision tree that walks all of them
+/// simultaneously and identifies the rule that was matched. In addition to
+/// that, it also needs to find the most efficient order to make decisions
+/// without violating any dependencies and ensure that every DAG covers every
+/// instr/edge/predicate.
+class GIMatchTreeBuilder {
+public:
+  using LeafVec = std::vector<GIMatchTreeBuilderLeafInfo>;
+
+protected:
+  /// The leaves that the resulting decision tree will distinguish.
+  LeafVec Leaves;
+  /// The tree node being constructed.
+  GIMatchTree *TreeNode;
+  /// The builders for each subtree resulting from the current decision.
+  std::vector<GIMatchTreeBuilder> SubtreeBuilders;
+  /// The possible partitioners we could apply right now.
+  std::vector<std::unique_ptr<GIMatchTreePartitioner>> Partitioners;
+  /// The next instruction ID to allocate when requested by the chosen
+  /// Partitioner.
+  unsigned NextInstrID;
+
+  /// Use any context we have stored to cull partitioners that only test things
+  /// we already know. At the time of writing, there's no need to do anything
+  /// here but it will become important once, for example, there is a
+  /// num-operands and an opcode partitioner. This is because applying an opcode
+  /// partitioner (usually) makes the number of operands known which makes
+  /// additional checking pointless.
+  void filterRedundantPartitioners();
+
+  /// Evaluate the available partioners and select the best one at the moment.
+  void evaluatePartitioners();
+
+  /// Construct the current tree node.
+  void runStep();
+
+public:
+  GIMatchTreeBuilder(unsigned NextInstrID) : NextInstrID(NextInstrID) {}
+  GIMatchTreeBuilder(GIMatchTree *TreeNode, unsigned NextInstrID)
+      : TreeNode(TreeNode), NextInstrID(NextInstrID) {}
+
+  void addLeaf(StringRef Name, unsigned RootIdx, const GIMatchDag &MatchDag,
+               void *Data) {
+    Leaves.emplace_back(*this, Name, RootIdx, MatchDag, Data);
+  }
+  void addLeaf(const GIMatchTreeBuilderLeafInfo &L) { Leaves.push_back(L); }
+  void addPartitioner(std::unique_ptr<GIMatchTreePartitioner> P) {
+    Partitioners.push_back(std::move(P));
+  }
+  void addPartitionersForInstr(unsigned InstrIdx);
+  void addPartitionersForOperand(unsigned InstrID, unsigned OpIdx);
+
+  LeafVec &getPossibleLeaves() { return Leaves; }
+
+  unsigned allocInstrID() { return NextInstrID++; }
+
+  /// Construct the decision tree.
+  std::unique_ptr<GIMatchTree> run();
+};
+
+/// Partitioners are the core of the tree builder and are unfortunately rather
+/// tricky to write.
+class GIMatchTreePartitioner {
+protected:
+  /// The partitions resulting from applying the partitioner to the possible
+  /// leaves. The keys must be consecutive integers starting from 0. This can
+  /// lead to some unfortunate situations where partitioners test a predicate
+  /// and use 0 for success and 1 for failure if the ruleset encounters a
+  /// success case first but is necessary to assign the partition to one of the
+  /// tree nodes children. As a result, you usually need some kind of
+  /// indirection to map the natural keys (e.g. ptrs/bools) to this linear
+  /// sequence. The values are a bitvector indicating which leaves belong to
+  /// this partition.
+  DenseMap<unsigned, BitVector> Partitions;
+
+public:
+  virtual ~GIMatchTreePartitioner() {}
+  virtual std::unique_ptr<GIMatchTreePartitioner> clone() const = 0;
+
+  /// Determines which partitions the given leaves belong to. A leaf may belong
+  /// to multiple partitions in which case it will be duplicated during
+  /// applyForPartition().
+  ///
+  /// This function can be rather complicated. A few particular things to be
+  /// aware of include:
+  /// * One leaf can be assigned to multiple partitions when there's some
+  ///   ambiguity.
+  /// * Not all DAG's for the leaves may be able to perform the test. For
+  ///   example, the opcode partitiioner must account for one DAG being a
+  ///   superset of another such as [(ADD ..., ..., ...)], and [(MUL t, ...,
+  ///   ...), (ADD ..., t, ...)]
+  /// * Attaching meaning to a particular partition index will generally not
+  ///   work due to the '0, 1, ..., n' requirement. You might encounter cases
+  ///   where only partition 1 is seen, leaving a missing 0.
+  /// * Finding a specific predicate such as the opcode predicate for a specific
+  ///   instruction is non-trivial. It's often O(NumPredicates), leading to
+  ///   O(NumPredicates*NumRules) when applied to the whole ruleset. The good
+  ///   news there is that n is typically small thanks to predicate dependencies
+  ///   limiting how many are testable at once. Also, with opcode and type
+  ///   predicates being so frequent the value of m drops very fast too. It
+  ///   wouldn't be terribly surprising to see a 10k ruleset drop down to an
+  ///   average of 100 leaves per partition after a single opcode partitioner.
+  /// * The same goes for finding specific edges. The need to traverse them in
+  ///   dependency order dramatically limits the search space at any given
+  ///   moment.
+  /// * If you need to add a leaf to all partitions, make sure you don't forget
+  ///   them when adding partitions later.
+  virtual void repartition(GIMatchTreeBuilder::LeafVec &Leaves) = 0;
+
+  /// Delegate the leaves for a given partition to the corresponding subbuilder,
+  /// update any recorded context for this partition (e.g. allocate instr id's
+  /// for instrs recorder by the current node), and clear any blocking
+  /// dependencies this partitioner resolved.
+  virtual void applyForPartition(unsigned PartitionIdx,
+                                 GIMatchTreeBuilder &Builder,
+                                 GIMatchTreeBuilder &SubBuilder) = 0;
+
+  /// Return a BitVector indicating which leaves should be transferred to the
+  /// specified partition. Note that the same leaf can be indicated for multiple
+  /// partitions.
+  BitVector getPossibleLeavesForPartition(unsigned Idx) {
+    const auto &I = Partitions.find(Idx);
+    assert(I != Partitions.end() && "Requested non-existant partition");
+    return I->second;
+  }
+
+  size_t getNumPartitions() const { return Partitions.size(); }
+  size_t getNumLeavesWithDupes() const {
+    size_t S = 0;
+    for (const auto &P : Partitions)
+      S += P.second.size();
+    return S;
+  }
+
+  /// Emit a brief description of the partitioner suitable for debug printing or
+  /// use in a DOT graph.
+  virtual void emitDescription(raw_ostream &OS) const = 0;
+  /// Emit a label for the given partition suitable for debug printing or use in
+  /// a DOT graph.
+  virtual void emitPartitionName(raw_ostream &OS, unsigned Idx) const = 0;
+
+  /// Emit a long description of how the partitioner partitions the leaves.
+  virtual void emitPartitionResults(raw_ostream &OS) const = 0;
+
+  /// Generate code to select between partitions based on the MIR being matched.
+  /// This is typically a switch statement that picks a partition index.
+  virtual void generatePartitionSelectorCode(raw_ostream &OS,
+                                             StringRef Indent) const = 0;
+};
+
+/// Partition according to the opcode of the instruction.
+///
+/// Numbers CodeGenInstr ptrs for use as partition ID's. One special partition,
+/// nullptr, represents the case where the instruction isn't known.
+///
+/// * If the opcode can be tested and is a single opcode, create the partition
+///   for that opcode and assign the leaf to it. This partition no longer needs
+///   to test the opcode, and many details about the instruction will usually
+///   become known (e.g. number of operands for non-variadic instrs) via the
+///   CodeGenInstr ptr.
+/// * (not implemented yet) If the opcode can be tested and is a choice of
+///   opcodes, then the leaf can be treated like the single-opcode case but must
+///   be added to all relevant partitions and not quite as much becomes known as
+///   a result. That said, multiple-choice opcodes are likely similar enough
+///   (because if they aren't then handling them together makes little sense)
+///   that plenty still becomes known. The main implementation issue with this
+///   is having a description to represent the commonality between instructions.
+/// * If the opcode is not tested, the leaf must be added to all partitions
+///   including the wildcard nullptr partition. What becomes known as a result
+///   varies between partitions.
+/// * If the instruction to be tested is not declared then add the leaf to all
+///   partitions. This occurs when we encounter one rule that is a superset of
+///   the other and we are still matching the remainder of the superset. The
+///   result is that the cases that don't match the superset will match the
+///   subset rule, while the ones that do match the superset will match either
+///   (which one is algorithm dependent but will usually be the superset).
+class GIMatchTreeOpcodePartitioner : public GIMatchTreePartitioner {
+  unsigned InstrID;
+  DenseMap<const CodeGenInstruction *, unsigned> InstrToPartition;
+  std::vector<const CodeGenInstruction *> PartitionToInstr;
+  std::vector<BitVector> TestedPredicates;
+
+public:
+  GIMatchTreeOpcodePartitioner(unsigned InstrID) : InstrID(InstrID) {}
+
+  std::unique_ptr<GIMatchTreePartitioner> clone() const override {
+    return std::make_unique<GIMatchTreeOpcodePartitioner>(*this);
+  }
+
+  void emitDescription(raw_ostream &OS) const override {
+    OS << "MI[" << InstrID << "].getOpcode()";
+  }
+
+  void emitPartitionName(raw_ostream &OS, unsigned Idx) const override;
+
+  void repartition(GIMatchTreeBuilder::LeafVec &Leaves) override;
+  void applyForPartition(unsigned Idx, GIMatchTreeBuilder &SubBuilder,
+                         GIMatchTreeBuilder &Builder) override;
+
+  void emitPartitionResults(raw_ostream &OS) const override;
+
+  void generatePartitionSelectorCode(raw_ostream &OS,
+                                     StringRef Indent) const override;
+};
+
+class GIMatchTreeVRegDefPartitioner : public GIMatchTreePartitioner {
+  unsigned NewInstrID = -1;
+  unsigned InstrID;
+  unsigned OpIdx;
+  std::vector<BitVector> TraversedEdges;
+  DenseMap<unsigned, unsigned> ResultToPartition;
+  std::vector<bool> PartitionToResult;
+
+  void addToPartition(bool Result, unsigned LeafIdx);
+
+public:
+  GIMatchTreeVRegDefPartitioner(unsigned InstrID, unsigned OpIdx)
+      : InstrID(InstrID), OpIdx(OpIdx) {}
+
+  std::unique_ptr<GIMatchTreePartitioner> clone() const override {
+    return std::make_unique<GIMatchTreeVRegDefPartitioner>(*this);
+  }
+
+  void emitDescription(raw_ostream &OS) const override {
+    OS << "MI[" << NewInstrID << "] = getVRegDef(MI[" << InstrID
+       << "].getOperand(" << OpIdx << "))";
+  }
+
+  void emitPartitionName(raw_ostream &OS, unsigned Idx) const override {
+    bool Result = PartitionToResult[Idx];
+    if (Result)
+      OS << "true";
+    else
+      OS << "false";
+  }
+
+  void repartition(GIMatchTreeBuilder::LeafVec &Leaves) override;
+  void applyForPartition(unsigned PartitionIdx, GIMatchTreeBuilder &Builder,
+                         GIMatchTreeBuilder &SubBuilder) override;
+  void emitPartitionResults(raw_ostream &OS) const override;
+
+  void generatePartitionSelectorCode(raw_ostream &OS,
+                                     StringRef Indent) const override;
+};
+
+} // end namespace llvm
+#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREE_H

llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp

+//===- GIMatchTree.cpp - A decision tree to match GIMatchDag's ------------===//
+//
+// 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 "GIMatchTree.h"
+
+#include "../CodeGenInstruction.h"
+
+#include "llvm/Support/Format.h"
+#include "llvm/Support/ScopedPrinter.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/TableGen/Error.h"
+#include "llvm/TableGen/Record.h"
+
+#define DEBUG_TYPE "gimatchtree"
+
+using namespace llvm;
+
+void GIMatchTree::writeDOTGraph(raw_ostream &OS) const {
+  OS << "digraph \"matchtree\" {\n";
+  writeDOTGraphNode(OS);
+  OS << "}\n";
+}
+
+void GIMatchTree::writeDOTGraphNode(raw_ostream &OS) const {
+  OS << format("  Node%p", this) << " [shape=record,label=\"{";
+  if (Partitioner) {
+    Partitioner->emitDescription(OS);
+    OS << "|" << Partitioner->getNumPartitions() << " partitions|";
+  } else
+    OS << "No partitioner|";
+  bool IsFullyTraversed = true;
+  bool IsFullyTested = true;
+  StringRef Separator = "";
+  for (const auto &Leaf : PossibleLeaves) {
+    OS << Separator << Leaf.getName();
+    Separator = ",";
+    if (!Leaf.isFullyTraversed())
+      IsFullyTraversed = false;
+    if (!Leaf.isFullyTested())
+      IsFullyTested = false;
+  }
+  if (!Partitioner && !IsFullyTraversed)
+    OS << "|Not fully traversed";
+  if (!Partitioner && !IsFullyTested) {
+    OS << "|Not fully tested";
+    if (IsFullyTraversed) {
+      for (const GIMatchTreeLeafInfo &Leaf : PossibleLeaves) {
+        if (Leaf.isFullyTested())
+          continue;
+        OS << "\\n" << Leaf.getName() << ": " << &Leaf;
+        for (const GIMatchDagPredicate *P : Leaf.untested_predicates())
+          OS << *P;
+      }
+    }
+  }
+  OS << "}\"";
+  if (!Partitioner &&
+      (!IsFullyTraversed || !IsFullyTested || PossibleLeaves.size() > 1))
+    OS << ",color=red";
+  OS << "]\n";
+  for (const auto &C : Children)
+    C.writeDOTGraphNode(OS);
+  writeDOTGraphEdges(OS);
+}
+
+void GIMatchTree::writeDOTGraphEdges(raw_ostream &OS) const {
+  for (const auto &Child : enumerate(Children)) {
+    OS << format("  Node%p", this) << " -> " << format("Node%p", &Child.value())
+       << " [label=\"#" << Child.index() << " ";
+    Partitioner->emitPartitionName(OS, Child.index());
+    OS << "\"]\n";
+  }
+}
+
+GIMatchTreeBuilderLeafInfo::GIMatchTreeBuilderLeafInfo(
+    GIMatchTreeBuilder &Builder, StringRef Name, unsigned RootIdx,
+    const GIMatchDag &MatchDag, void *Data)
+    : Builder(Builder), Info(Name, RootIdx, Data), MatchDag(MatchDag),
+      InstrNodeToInfo(),
+      RemainingInstrNodes(BitVector(MatchDag.getNumInstrNodes(), true)),
+      RemainingEdges(BitVector(MatchDag.getNumEdges(), true)),
+      RemainingPredicates(BitVector(MatchDag.getNumPredicates(), true)),
+      TraversableEdges(MatchDag.getNumEdges()),
+      TestablePredicates(MatchDag.getNumPredicates()) {
+  // Number all the predicates in this DAG
+  for (auto &P : enumerate(MatchDag.predicates())) {
+    PredicateIDs.insert(std::make_pair(P.value(), P.index()));
+  }
+
+  // Number all the predicate dependencies in this DAG and set up a bitvector
+  // for each predicate indicating the unsatisfied dependencies.
+  for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
+    PredicateDepIDs.insert(std::make_pair(Dep.value(), Dep.index()));
+  }
+  UnsatisfiedPredDepsForPred.resize(MatchDag.getNumPredicates(),
+                                    BitVector(PredicateDepIDs.size()));
+  for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
+    unsigned ID = PredicateIDs.lookup(Dep.value()->getPredicate());
+    UnsatisfiedPredDepsForPred[ID].set(Dep.index());
+  }
+}
+
+void GIMatchTreeBuilderLeafInfo::declareInstr(const GIMatchDagInstr *Instr, unsigned ID) {
+  // Record the assignment of this instr to the given ID.
+  auto InfoI = InstrNodeToInfo.insert(std::make_pair(
+      Instr, GIMatchTreeInstrInfo(ID, Instr)));
+  InstrIDToInfo.insert(std::make_pair(ID, &InfoI.first->second));
+
+  if (Instr == nullptr)
+    return;
+
+  if (!Instr->getUserAssignedName().empty())
+    Info.bindInstrVariable(Instr->getUserAssignedName(), ID);
+  for (const auto &VarBinding : Instr->user_assigned_operand_names())
+    Info.bindOperandVariable(VarBinding.second, ID, VarBinding.first);
+
+  // Clear the bit indicating we haven't visited this instr.
+  const auto &NodeI = std::find(MatchDag.instr_nodes_begin(),
+                            MatchDag.instr_nodes_end(), Instr);
+  assert(NodeI != MatchDag.instr_nodes_end() && "Instr isn't in this DAG");
+  unsigned InstrIdx = MatchDag.getInstrNodeIdx(NodeI);
+  RemainingInstrNodes.reset(InstrIdx);
+
+  // When we declare an instruction, we don't expose any traversable edges just
+  // yet. A partitioner has to check they exist and are registers before they
+  // are traversable.
+
+  // When we declare an instruction, we potentially activate some predicates.
+  // Mark the dependencies that are now satisfied as a result of this
+  // instruction and mark any predicates whose dependencies are fully
+  // satisfied.
+  for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
+    if (Dep.value()->getRequiredMI() == Instr &&
+        Dep.value()->getRequiredMO() == nullptr) {
+      for (auto &DepsFor : enumerate(UnsatisfiedPredDepsForPred)) {
+        DepsFor.value().reset(Dep.index());
+        if (DepsFor.value().none())
+          TestablePredicates.set(DepsFor.index());
+      }
+    }
+  }
+}
+
+void GIMatchTreeBuilderLeafInfo::declareOperand(unsigned InstrID,
+                                                unsigned OpIdx) {
+  const GIMatchDagInstr *Instr = InstrIDToInfo.lookup(InstrID)->getInstrNode();
+
+  OperandIDToInfo.insert(std::make_pair(
+      std::make_pair(InstrID, OpIdx),
+      GIMatchTreeOperandInfo(Instr, OpIdx)));
+
+  // When an operand becomes reachable, we potentially activate some traversals.
+  // Record the edges that can now be followed as a result of this
+  // instruction.
+  for (auto &E : enumerate(MatchDag.edges())) {
+    if (E.value()->getFromMI() == Instr &&
+        E.value()->getFromMO()->getIdx() == OpIdx) {
+      TraversableEdges.set(E.index());
+    }
+  }
+
+  // When an operand becomes reachable, we potentially activate some predicates.
+  // Clear the dependencies that are now satisfied as a result of this
+  // operand and activate any predicates whose dependencies are fully
+  // satisfied.
+  for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
+    if (Dep.value()->getRequiredMI() == Instr && Dep.value()->getRequiredMO() &&
+        Dep.value()->getRequiredMO()->getIdx() == OpIdx) {
+      for (auto &DepsFor : enumerate(UnsatisfiedPredDepsForPred)) {
+        DepsFor.value().reset(Dep.index());
+        if (DepsFor.value().none())
+          TestablePredicates.set(DepsFor.index());
+      }
+    }
+  }
+}
+
+void GIMatchTreeBuilder::addPartitionersForInstr(unsigned InstrIdx) {
+  // Find the partitioners that can be used now that this node is
+  // uncovered. Our choices are:
+  // - Test the opcode
+  addPartitioner(std::make_unique<GIMatchTreeOpcodePartitioner>(InstrIdx));
+}
+
+void GIMatchTreeBuilder::addPartitionersForOperand(unsigned InstrID,
+                                                   unsigned OpIdx) {
+  LLVM_DEBUG(dbgs() << "Add partitioners for Instrs[" << InstrID
+                    << "].getOperand(" << OpIdx << ")\n");
+  addPartitioner(
+      std::make_unique<GIMatchTreeVRegDefPartitioner>(InstrID, OpIdx));
+}
+
+void GIMatchTreeBuilder::filterRedundantPartitioners() {
+  // TODO: Filter partitioners for facts that are already known
+  // - If we know the opcode, we can elide the num operand check so long as
+  //   the instruction has a fixed number of operands.
+  // - If we know an exact number of operands then we can elide further number
+  //   of operand checks.
+  // - If the current min number of operands exceeds the one we want to check
+  //   then we can elide it.
+}
+
+void GIMatchTreeBuilder::evaluatePartitioners() {
+  // Determine the partitioning the partitioner would produce
+  for (auto &Partitioner : Partitioners) {
+    LLVM_DEBUG(dbgs() << "    Weighing up ";
+               Partitioner->emitDescription(dbgs()); dbgs() << "\n");
+    Partitioner->repartition(Leaves);
+    LLVM_DEBUG(Partitioner->emitPartitionResults(dbgs()));
+  }
+}
+
+void GIMatchTreeBuilder::runStep() {
+  LLVM_DEBUG(dbgs() << "Building match tree node for " << TreeNode << "\n");
+  LLVM_DEBUG(dbgs() << "  Rules reachable at this node:\n");
+  for (const auto &Leaf : Leaves) {
+    LLVM_DEBUG(dbgs() << "    " << Leaf.getName() << " (" << &Leaf.getInfo() << "\n");
+    TreeNode->addPossibleLeaf(Leaf.getInfo(), Leaf.isFullyTraversed(),
+                              Leaf.isFullyTested());
+  }
+
+  LLVM_DEBUG(dbgs() << "  Partitioners available at this node:\n");
+#ifndef NDEBUG
+  for (const auto &Partitioner : Partitioners)
+    LLVM_DEBUG(dbgs() << "    "; Partitioner->emitDescription(dbgs());
+               dbgs() << "\n");
+#endif // ifndef NDEBUG
+
+  // Check for unreachable rules. Rules are unreachable if they are preceeded by
+  // a fully tested rule.
+  // Note: This is only true for the current algorithm, if we allow the
+  //       algorithm to compare equally valid rules then they will become
+  //       reachable.
+  {
+    auto FullyTestedLeafI = Leaves.end();
+    for (auto LeafI = Leaves.begin(), LeafE = Leaves.end();
+         LeafI != LeafE; ++LeafI) {
+      if (LeafI->isFullyTraversed() && LeafI->isFullyTested())
+        FullyTestedLeafI = LeafI;
+      else if (FullyTestedLeafI != Leaves.end()) {
+        PrintError("Leaf " + LeafI->getName() + " is unreachable");
+        PrintNote("Leaf " + FullyTestedLeafI->getName() +
+                  " will have already matched");
+      }
+    }
+  }
+
+  LLVM_DEBUG(dbgs() << "  Eliminating redundant partitioners:\n");
+  filterRedundantPartitioners();
+  LLVM_DEBUG(dbgs() << "  Partitioners remaining:\n");
+#ifndef NDEBUG
+  for (const auto &Partitioner : Partitioners)
+    LLVM_DEBUG(dbgs() << "    "; Partitioner->emitDescription(dbgs());
+               dbgs() << "\n");
+#endif // ifndef NDEBUG
+
+  if (Partitioners.empty()) {
+    // Nothing left to do but check we really did identify a single rule.
+    if (Leaves.size() > 1) {
+      LLVM_DEBUG(dbgs() << "Leaf contains multiple rules, drop after the first "
+                           "fully tested rule\n");
+      auto FirstFullyTested =
+          std::find_if(Leaves.begin(), Leaves.end(),
+                       [](const GIMatchTreeBuilderLeafInfo &X) {
+                         return X.isFullyTraversed() && X.isFullyTested() &&
+                                !X.getMatchDag().hasPostMatchPredicate();
+                       });
+      if (FirstFullyTested != Leaves.end())
+        FirstFullyTested++;
+
+#ifndef NDEBUG
+      for (auto &Leaf : make_range(Leaves.begin(), FirstFullyTested))
+        LLVM_DEBUG(dbgs() << "  Kept " << Leaf.getName() << "\n");
+      for (const auto &Leaf : make_range(FirstFullyTested, Leaves.end()))
+        LLVM_DEBUG(dbgs() << "  Dropped " << Leaf.getName() << "\n");
+#endif // ifndef NDEBUG
+      TreeNode->dropLeavesAfter(
+          std::distance(Leaves.begin(), FirstFullyTested));
+    }
+    for (const auto &Leaf : Leaves) {
+      if (!Leaf.isFullyTraversed()) {
+        PrintError("Leaf " + Leaf.getName() + " is not fully traversed");
+        PrintNote("This indicates a missing partitioner within tblgen");
+        Leaf.dump(errs());
+        for (unsigned InstrIdx : Leaf.untested_instrs())
+          PrintNote("Instr " + llvm::to_string(*Leaf.getInstr(InstrIdx)));
+        for (unsigned EdgeIdx : Leaf.untested_edges())
+          PrintNote("Edge " + llvm::to_string(*Leaf.getEdge(EdgeIdx)));
+      }
+    }
+
+    // Copy out information about untested predicates so the user of the tree
+    // can deal with them.
+    for (auto LeafPair : zip(Leaves, TreeNode->possible_leaves())) {
+      const GIMatchTreeBuilderLeafInfo &BuilderLeaf = std::get<0>(LeafPair);
+      GIMatchTreeLeafInfo &TreeLeaf = std::get<1>(LeafPair);
+      if (!BuilderLeaf.isFullyTested())
+        for (unsigned PredicateIdx : BuilderLeaf.untested_predicates())
+          TreeLeaf.addUntestedPredicate(BuilderLeaf.getPredicate(PredicateIdx));
+    }
+    return;
+  }
+
+  LLVM_DEBUG(dbgs() << "  Weighing up partitioners:\n");
+  evaluatePartitioners();
+
+  // Select the best partitioner by its ability to partition
+  // - Prefer partitioners that don't distinguish between partitions. This
+  //   is to fail early on decisions that must go a single way.
+  auto PartitionerI = std::max_element(
+      Partitioners.begin(), Partitioners.end(),
+      [](const std::unique_ptr<GIMatchTreePartitioner> &A,
+         const std::unique_ptr<GIMatchTreePartitioner> &B) {
+        // We generally want partitioners that subdivide the
+        // ruleset as much as possible since these take fewer
+        // checks to converge on a particular rule. However,
+        // it's important to note that one leaf can end up in
+        // multiple partitions if the check isn't mutually
+        // exclusive (e.g. getVRegDef() vs isReg()).
+        // We therefore minimize average leaves per partition.
+        return (double)A->getNumLeavesWithDupes() / A->getNumPartitions() >
+               (double)B->getNumLeavesWithDupes() / B->getNumPartitions();
+      });
+
+  // Select a partitioner and partition the ruleset
+  // Note that it's possible for a single rule to end up in multiple
+  // partitions. For example, an opcode test on a rule without an opcode
+  // predicate will result in it being passed to all partitions.
+  std::unique_ptr<GIMatchTreePartitioner> Partitioner = std::move(*PartitionerI);
+  Partitioners.erase(PartitionerI);
+  LLVM_DEBUG(dbgs() << "  Selected partitioner: ";
+             Partitioner->emitDescription(dbgs()); dbgs() << "\n");
+
+  assert(Partitioner->getNumPartitions() > 0 &&
+         "Must always partition into at least one partition");
+
+  TreeNode->setNumChildren(Partitioner->getNumPartitions());
+  for (auto &C : enumerate(TreeNode->children())) {
+    SubtreeBuilders.emplace_back(&C.value(), NextInstrID);
+    Partitioner->applyForPartition(C.index(), *this, SubtreeBuilders.back());
+  }
+
+  TreeNode->setPartitioner(std::move(Partitioner));
+
+  // Recurse into the subtree builders. Each one must get a copy of the
+  // remaining partitioners as each path has to check everything.
+  for (auto &SubtreeBuilder : SubtreeBuilders) {
+    for (const auto &Partitioner : Partitioners)
+      SubtreeBuilder.addPartitioner(Partitioner->clone());
+    SubtreeBuilder.runStep();
+  }
+}
+
+std::unique_ptr<GIMatchTree> GIMatchTreeBuilder::run() {
+  unsigned NewInstrID = allocInstrID();
+  // Start by recording the root instruction as instr #0 and set up the initial
+  // partitioners.
+  for (auto &Leaf : Leaves) {
+    LLVM_DEBUG(Leaf.getMatchDag().writeDOTGraph(dbgs(), Leaf.getName()));
+    GIMatchDagInstr *Root =
+        *(Leaf.getMatchDag().roots().begin() + Leaf.getRootIdx());
+    Leaf.declareInstr(Root, NewInstrID);
+  }
+
+  addPartitionersForInstr(NewInstrID);
+
+  std::unique_ptr<GIMatchTree> TreeRoot = std::make_unique<GIMatchTree>();
+  TreeNode = TreeRoot.get();
+  runStep();
+
+  return TreeRoot;
+}
+
+void GIMatchTreeOpcodePartitioner::emitPartitionName(raw_ostream &OS, unsigned Idx) const {
+  if (PartitionToInstr[Idx] == nullptr) {
+    OS << "* or nullptr";
+    return;
+  }
+  OS << PartitionToInstr[Idx]->Namespace
+     << "::" << PartitionToInstr[Idx]->TheDef->getName();
+}
+
+void GIMatchTreeOpcodePartitioner::repartition(
+    GIMatchTreeBuilder::LeafVec &Leaves) {
+  Partitions.clear();
+  InstrToPartition.clear();
+  PartitionToInstr.clear();
+  TestedPredicates.clear();
+
+  for (const auto &Leaf : enumerate(Leaves)) {
+    bool AllOpcodes = true;
+    GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
+    BitVector TestedPredicatesForLeaf(
+        Leaf.value().getMatchDag().getNumPredicates());
+
+    // If the instruction isn't declared then we don't care about it. Ignore
+    // it for now and add it to all partitions later once we know what
+    // partitions we have.
+    if (!InstrInfo) {
+      LLVM_DEBUG(dbgs() << "      " << Leaf.value().getName()
+                        << " doesn't care about Instr[" << InstrID << "]\n");
+      assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates());
+      TestedPredicates.push_back(TestedPredicatesForLeaf);
+      continue;
+    }
+
+    // If the opcode is available to test then any opcode predicates will have
+    // been enabled too.
+    for (const auto &PIdx : Leaf.value().TestablePredicates.set_bits()) {
+      const auto &P = Leaf.value().getPredicate(PIdx);
+      SmallVector<const CodeGenInstruction *, 1> OpcodesForThisPredicate;
+      if (const auto *OpcodeP = dyn_cast<const GIMatchDagOpcodePredicate>(P)) {
+        // We've found _an_ opcode predicate, but we don't know if it's
+        // checking this instruction yet.
+        bool IsThisPredicate = false;
+        for (const auto &PDep : Leaf.value().getMatchDag().predicate_edges()) {
+          if (PDep->getRequiredMI() == InstrInfo->getInstrNode() &&
+              PDep->getRequiredMO() == nullptr && PDep->getPredicate() == P) {
+            IsThisPredicate = true;
+            break;
+          }
+        }
+        if (!IsThisPredicate)
+          continue;
+
+        // If we get here twice then we've somehow ended up with two opcode
+        // predicates for one instruction in the same DAG. That should be
+        // impossible.
+        assert(AllOpcodes && "Conflicting opcode predicates");
+        const CodeGenInstruction *Expected = OpcodeP->getInstr();
+        OpcodesForThisPredicate.push_back(Expected);
+      }
+
+      if (const auto *OpcodeP =
+              dyn_cast<const GIMatchDagOneOfOpcodesPredicate>(P)) {
+        // We've found _an_ oneof(opcodes) predicate, but we don't know if it's
+        // checking this instruction yet.
+        bool IsThisPredicate = false;
+        for (const auto &PDep : Leaf.value().getMatchDag().predicate_edges()) {
+          if (PDep->getRequiredMI() == InstrInfo->getInstrNode() &&
+              PDep->getRequiredMO() == nullptr && PDep->getPredicate() == P) {
+            IsThisPredicate = true;
+            break;
+          }
+        }
+        if (!IsThisPredicate)
+          continue;
+
+        // If we get here twice then we've somehow ended up with two opcode
+        // predicates for one instruction in the same DAG. That should be
+        // impossible.
+        assert(AllOpcodes && "Conflicting opcode predicates");
+        for (const CodeGenInstruction *Expected : OpcodeP->getInstrs())
+          OpcodesForThisPredicate.push_back(Expected);
+      }
+
+      for (const CodeGenInstruction *Expected : OpcodesForThisPredicate) {
+        // Mark this predicate as one we're testing.
+        TestedPredicatesForLeaf.set(PIdx);
+
+        // Partitions must be numbered 0, 1, .., N but instructions don't meet
+        // that requirement. Assign a partition number to each opcode if we
+        // lack one ...
+        auto Partition = InstrToPartition.find(Expected);
+        if (Partition == InstrToPartition.end()) {
+          BitVector Contents(Leaves.size());
+          Partition = InstrToPartition
+                          .insert(std::make_pair(Expected, Partitions.size()))
+                          .first;
+          PartitionToInstr.push_back(Expected);
+          Partitions.insert(std::make_pair(Partitions.size(), Contents));
+        }
+        // ... and mark this leaf as being in that partition.
+        Partitions.find(Partition->second)->second.set(Leaf.index());
+        AllOpcodes = false;
+        LLVM_DEBUG(dbgs() << "      " << Leaf.value().getName()
+                          << " is in partition " << Partition->second << "\n");
+      }
+
+      // TODO: This is where we would handle multiple choices of opcode
+      //       the end result will be that this leaf ends up in multiple
+      //       partitions similarly to AllOpcodes.
+    }
+
+    // If we never check the opcode, add it to every partition.
+    if (AllOpcodes) {
+      // Add a partition for the default case if we don't already have one.
+      if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) {
+        PartitionToInstr.push_back(nullptr);
+        BitVector Contents(Leaves.size());
+        Partitions.insert(std::make_pair(Partitions.size(), Contents));
+      }
+      LLVM_DEBUG(dbgs() << "      " << Leaf.value().getName()
+                        << " is in all partitions (opcode not checked)\n");
+      for (auto &Partition : Partitions)
+        Partition.second.set(Leaf.index());
+    }
+
+    assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates());
+    TestedPredicates.push_back(TestedPredicatesForLeaf);
+  }
+
+  if (Partitions.size() == 0) {
+    // Add a partition for the default case if we don't already have one.
+    if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) {
+      PartitionToInstr.push_back(nullptr);
+      BitVector Contents(Leaves.size());
+      Partitions.insert(std::make_pair(Partitions.size(), Contents));
+    }
+  }
+
+  // Add any leaves that don't care about this instruction to all partitions.
+  for (const auto &Leaf : enumerate(Leaves)) {
+    GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
+    if (!InstrInfo) {
+      // Add a partition for the default case if we don't already have one.
+      if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) {
+        PartitionToInstr.push_back(nullptr);
+        BitVector Contents(Leaves.size());
+        Partitions.insert(std::make_pair(Partitions.size(), Contents));
+      }
+      for (auto &Partition : Partitions)
+        Partition.second.set(Leaf.index());
+    }
+  }
+
+}
+
+void GIMatchTreeOpcodePartitioner::applyForPartition(
+    unsigned PartitionIdx, GIMatchTreeBuilder &Builder, GIMatchTreeBuilder &SubBuilder) {
+  LLVM_DEBUG(dbgs() << "  Making partition " << PartitionIdx << "\n");
+  const CodeGenInstruction *CGI = PartitionToInstr[PartitionIdx];
+
+  BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx);
+  // Consume any predicates we handled.
+  for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) {
+    if (!PossibleLeaves[EnumeratedLeaf.index()])
+      continue;
+
+    auto &Leaf = EnumeratedLeaf.value();
+    const auto &TestedPredicatesForLeaf =
+        TestedPredicates[EnumeratedLeaf.index()];
+
+    for (unsigned PredIdx : TestedPredicatesForLeaf.set_bits()) {
+      LLVM_DEBUG(dbgs() << "    " << Leaf.getName() << " tested predicate #"
+                        << PredIdx << " of " << TestedPredicatesForLeaf.size()
+                        << " " << *Leaf.getPredicate(PredIdx) << "\n");
+      Leaf.RemainingPredicates.reset(PredIdx);
+      Leaf.TestablePredicates.reset(PredIdx);
+    }
+    SubBuilder.addLeaf(Leaf);
+  }
+
+  // Nothing to do, we don't know anything about this instruction as a result
+  // of this partitioner.
+  if (CGI == nullptr)
+    return;
+
+  GIMatchTreeBuilder::LeafVec &NewLeaves = SubBuilder.getPossibleLeaves();
+  // Find all the operands we know to exist and are referenced. This will
+  // usually be all the referenced operands but there are some cases where
+  // instructions are variadic. Such operands must be handled by partitioners
+  // that check the number of operands.
+  BitVector ReferencedOperands(1);
+  for (auto &Leaf : NewLeaves) {
+    GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID);
+    // Skip any leaves that don't care about this instruction.
+    if (!InstrInfo)
+      continue;
+    const GIMatchDagInstr *Instr = InstrInfo->getInstrNode();
+    for (auto &E : enumerate(Leaf.getMatchDag().edges())) {
+      if (E.value()->getFromMI() == Instr &&
+          E.value()->getFromMO()->getIdx() < CGI->Operands.size()) {
+        ReferencedOperands.resize(E.value()->getFromMO()->getIdx() + 1);
+        ReferencedOperands.set(E.value()->getFromMO()->getIdx());
+      }
+    }
+  }
+  for (auto &Leaf : NewLeaves) {
+    for (unsigned OpIdx : ReferencedOperands.set_bits()) {
+      Leaf.declareOperand(InstrID, OpIdx);
+    }
+  }
+  for (unsigned OpIdx : ReferencedOperands.set_bits()) {
+    SubBuilder.addPartitionersForOperand(InstrID, OpIdx);
+  }
+}
+
+void GIMatchTreeOpcodePartitioner::emitPartitionResults(
+    raw_ostream &OS) const {
+  OS << "Partitioning by opcode would produce " << Partitions.size()
+     << " partitions\n";
+  for (const auto &Partition : InstrToPartition) {
+    if (Partition.first == nullptr)
+      OS << "Default: ";
+    else
+      OS << Partition.first->TheDef->getName() << ": ";
+    StringRef Separator = "";
+    for (unsigned I : Partitions.find(Partition.second)->second.set_bits()) {
+      OS << Separator << I;
+      Separator = ", ";
+    }
+    OS << "\n";
+  }
+}
+
+void GIMatchTreeOpcodePartitioner::generatePartitionSelectorCode(
+    raw_ostream &OS, StringRef Indent) const {
+  OS << Indent << "Partition = -1;\n"
+     << Indent << "switch (MIs[" << InstrID << "]->getOpcode()) {\n";
+  for (const auto &EnumInstr : enumerate(PartitionToInstr)) {
+    if (EnumInstr.value() == nullptr)
+      OS << Indent << "default:";
+    else
+      OS << Indent << "case " << EnumInstr.value()->Namespace
+         << "::" << EnumInstr.value()->TheDef->getName() << ":";
+    OS << " Partition = " << EnumInstr.index() << "; break;\n";
+  }
+  OS << Indent << "}\n"
+     << Indent
+     << "// Default case but without conflicting with potential default case "
+        "in selection.\n"
+     << Indent << "if (Partition == -1) return false;\n";
+}
+
+void GIMatchTreeVRegDefPartitioner::addToPartition(bool Result,
+                                                   unsigned LeafIdx) {
+  auto I = ResultToPartition.find(Result);
+  if (I == ResultToPartition.end()) {
+    ResultToPartition.insert(std::make_pair(Result, PartitionToResult.size()));
+    PartitionToResult.push_back(Result);
+  }
+  I = ResultToPartition.find(Result);
+  auto P = Partitions.find(I->second);
+  if (P == Partitions.end())
+    P = Partitions.insert(std::make_pair(I->second, BitVector())).first;
+  P->second.resize(LeafIdx + 1);
+  P->second.set(LeafIdx);
+};
+
+void GIMatchTreeVRegDefPartitioner::repartition(
+    GIMatchTreeBuilder::LeafVec &Leaves) {
+  Partitions.clear();
+
+  for (const auto &Leaf : enumerate(Leaves)) {
+    GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
+    BitVector TraversedEdgesForLeaf(Leaf.value().getMatchDag().getNumEdges());
+
+    // If the instruction isn't declared then we don't care about it. Ignore
+    // it for now and add it to all partitions later once we know what
+    // partitions we have.
+    if (!InstrInfo) {
+      TraversedEdges.push_back(TraversedEdgesForLeaf);
+      continue;
+    }
+
+    // If this node has an use -> def edge from this operand then this
+    // instruction must be in partition 1 (isVRegDef()).
+    bool WantsEdge = false;
+    for (const auto &EIdx : Leaf.value().TraversableEdges.set_bits()) {
+      const auto &E = Leaf.value().getEdge(EIdx);
+      if (E->getFromMI() != InstrInfo->getInstrNode() ||
+          E->getFromMO()->getIdx() != OpIdx || E->isDefToUse())
+        continue;
+
+      // We're looking at the right edge. This leaf wants a vreg def so we'll
+      // put it in partition 1.
+      addToPartition(true, Leaf.index());
+      TraversedEdgesForLeaf.set(EIdx);
+      WantsEdge = true;
+    }
+
+    bool isNotReg = false;
+    if (!WantsEdge && isNotReg) {
+      // If this leaf doesn't have an edge and we _don't_ want a register,
+      // then add it to partition 0.
+      addToPartition(false, Leaf.index());
+    } else if (!WantsEdge) {
+      // If this leaf doesn't have an edge and we don't know what we want,
+      // then add it to partition 0 and 1.
+      addToPartition(false, Leaf.index());
+      addToPartition(true, Leaf.index());
+    }
+
+    TraversedEdges.push_back(TraversedEdgesForLeaf);
+  }
+
+  // Add any leaves that don't care about this instruction to all partitions.
+  for (const auto &Leaf : enumerate(Leaves)) {
+    GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
+    if (!InstrInfo)
+      for (auto &Partition : Partitions)
+        Partition.second.set(Leaf.index());
+  }
+}
+
+void GIMatchTreeVRegDefPartitioner::applyForPartition(
+    unsigned PartitionIdx, GIMatchTreeBuilder &Builder,
+    GIMatchTreeBuilder &SubBuilder) {
+  BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx);
+
+  std::vector<BitVector> TraversedEdgesByNewLeaves;
+  // Consume any edges we handled.
+  for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) {
+    if (!PossibleLeaves[EnumeratedLeaf.index()])
+      continue;
+
+    auto &Leaf = EnumeratedLeaf.value();
+    const auto &TraversedEdgesForLeaf = TraversedEdges[EnumeratedLeaf.index()];
+    TraversedEdgesByNewLeaves.push_back(TraversedEdgesForLeaf);
+    Leaf.RemainingEdges.reset(TraversedEdgesForLeaf);
+    Leaf.TraversableEdges.reset(TraversedEdgesForLeaf);
+    SubBuilder.addLeaf(Leaf);
+  }
+
+  // Nothing to do. The only thing we know is that it isn't a vreg-def.
+  if (PartitionToResult[PartitionIdx] == false)
+    return;
+
+  NewInstrID = SubBuilder.allocInstrID();
+
+  GIMatchTreeBuilder::LeafVec &NewLeaves = SubBuilder.getPossibleLeaves();
+  for (const auto &I : zip(NewLeaves, TraversedEdgesByNewLeaves)) {
+    auto &Leaf = std::get<0>(I);
+    auto &TraversedEdgesForLeaf = std::get<1>(I);
+    GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID);
+    // Skip any leaves that don't care about this instruction.
+    if (!InstrInfo)
+      continue;
+    for (const auto &EIdx : TraversedEdgesForLeaf.set_bits()) {
+      const GIMatchDagEdge *E = Leaf.getEdge(EIdx);
+      Leaf.declareInstr(E->getToMI(), NewInstrID);
+    }
+  }
+  SubBuilder.addPartitionersForInstr(NewInstrID);
+}
+
+void GIMatchTreeVRegDefPartitioner::emitPartitionResults(
+    raw_ostream &OS) const {
+  OS << "Partitioning by vreg-def would produce " << Partitions.size()
+     << " partitions\n";
+  for (const auto &Partition : Partitions) {
+    OS << Partition.first << " (";
+    emitPartitionName(OS, Partition.first);
+    OS << "): ";
+    StringRef Separator = "";
+    for (unsigned I : Partition.second.set_bits()) {
+      OS << Separator << I;
+      Separator = ", ";
+    }
+    OS << "\n";
+  }
+}
+
+void GIMatchTreeVRegDefPartitioner::generatePartitionSelectorCode(
+    raw_ostream &OS, StringRef Indent) const {
+  OS << Indent << "Partition = -1\n"
+     << Indent << "if (MIs.size() <= NewInstrID) MIs.resize(NewInstrID + 1);\n"
+     << Indent << "MIs[" << NewInstrID << "] = nullptr;\n"
+     << Indent << "if (MIs[" << InstrID << "].getOperand(" << OpIdx
+     << ").isReg()))\n"
+     << Indent << "  MIs[" << NewInstrID << "] = MRI.getVRegDef(MIs[" << InstrID
+     << "].getOperand(" << OpIdx << ").getReg()));\n";
+
+  for (const auto &Pair : ResultToPartition)
+    OS << Indent << "if (MIs[" << NewInstrID << "] "
+       << (Pair.first ? "==" : "!=")
+       << " nullptr) Partition = " << Pair.second << ";\n";
+
+  OS << Indent << "if (Partition == -1) return false;\n";
+}
+