[TableGen] Remove & Replace old GICombiner Backend

[Pierre-vh]

Summary

The MatchTable-based GlobalISel Combiner backend is the new default. There are no in-tree users left of the old backend.

• Removed implementation of old MatchDAG-based Combiner, including tests, the backend itself and all supporting code.
• Renamed MatchTable backend to GlobalISelCombinerEmitter.cpp + removed "-matchtable" from its CL option.
  • no need to have a verbose name as it's the only backend left now.

[Pierre-vh]

ping

[aemerson]

I’ve checked with Daniel and no objections from the Apple side.

llvm/docs/CommandGuide/tblgen.rst

.. option:: -optimize-match-table
   Make -gen-global-isel generate an optimized version of the match table.
 
 .. option:: -warn-on-skipped-patterns
 
   Make -gen-global-isel explain why a pattern was skipped for inclusion.
 
 .. option:: -gen-global-isel-combiner
 
-  (Deprecated, pending removal)
-  Generate legacy GlobalISel combiner.
-
-.. option:: -gen-global-isel-combiner-matchtable
-
-  Generate MatchTable-based GlobalISel combiner.
+  Generate GlobalISel combiner.
 
 .. option:: -combiners=list
 
-  Make -gen-global-isel-combiner and -gen-global-isel-combiner-matchtable
-  emit the specified combiners.
-
-.. option:: -gicombiner-show-expansions
-
-  Make -gen-global-isel-combiner use C++ comments to indicate occurrences
-  of code expansion.
+  Make -gen-global-isel-combiner emit the specified combiners.
 
-.. option:: -gicombiner-stop-after-build
+.. option:: -gicombiner-debug-cxxpreds
 
-  Make -gen-global-isel-combiner stop processing after building the match tree.
+  Add debug comments to all C++ predicates emitted by -gen-global-isel-combiner
 
 .. option:: -gicombiner-stop-after-parse
 
-  Make -gen-global-isel-combiner and -gen-global-isel-combiner-matchtable stop
-  processing after parsing rules and dump state.
+  Make -gen-global-isel-combiner stop processing after parsing rules and dump state.
 
 .. option:: -gen-instr-info
 
  Generate instruction descriptions.
 
 .. option:: -gen-instr-docs
 
  Generate instruction documentation.

llvm/lib/Target/AArch64/CMakeLists.txt

 add_llvm_component_group(AArch64 HAS_JIT)
 
 set(LLVM_TARGET_DEFINITIONS AArch64.td)
 
 tablegen(LLVM AArch64GenAsmMatcher.inc -gen-asm-matcher)
 tablegen(LLVM AArch64GenAsmWriter.inc -gen-asm-writer)
 tablegen(LLVM AArch64GenAsmWriter1.inc -gen-asm-writer -asmwriternum=1)
 tablegen(LLVM AArch64GenCallingConv.inc -gen-callingconv)
 tablegen(LLVM AArch64GenDAGISel.inc -gen-dag-isel)
 tablegen(LLVM AArch64GenDisassemblerTables.inc -gen-disassembler)
 tablegen(LLVM AArch64GenFastISel.inc -gen-fast-isel)
 tablegen(LLVM AArch64GenGlobalISel.inc -gen-global-isel)
-tablegen(LLVM AArch64GenO0PreLegalizeGICombiner.inc -gen-global-isel-combiner-matchtable
+tablegen(LLVM AArch64GenO0PreLegalizeGICombiner.inc -gen-global-isel-combiner
               -combiners="AArch64O0PreLegalizerCombiner")
-tablegen(LLVM AArch64GenPreLegalizeGICombiner.inc -gen-global-isel-combiner-matchtable
+tablegen(LLVM AArch64GenPreLegalizeGICombiner.inc -gen-global-isel-combiner
               -combiners="AArch64PreLegalizerCombiner")
-tablegen(LLVM AArch64GenPostLegalizeGICombiner.inc -gen-global-isel-combiner-matchtable
+tablegen(LLVM AArch64GenPostLegalizeGICombiner.inc -gen-global-isel-combiner
               -combiners="AArch64PostLegalizerCombiner")
-tablegen(LLVM AArch64GenPostLegalizeGILowering.inc -gen-global-isel-combiner-matchtable
+tablegen(LLVM AArch64GenPostLegalizeGILowering.inc -gen-global-isel-combiner
               -combiners="AArch64PostLegalizerLowering")
 tablegen(LLVM AArch64GenInstrInfo.inc -gen-instr-info)
 tablegen(LLVM AArch64GenMCCodeEmitter.inc -gen-emitter)
 tablegen(LLVM AArch64GenMCPseudoLowering.inc -gen-pseudo-lowering)
 tablegen(LLVM AArch64GenRegisterBank.inc -gen-register-bank)
 tablegen(LLVM AArch64GenRegisterInfo.inc -gen-register-info)
 tablegen(LLVM AArch64GenSubtargetInfo.inc -gen-subtarget)
 tablegen(LLVM AArch64GenSystemOperands.inc -gen-searchable-tables)

llvm/lib/Target/AMDGPU/CMakeLists.txt

 tablegen(LLVM AMDGPUGenMCPseudoLowering.inc -gen-pseudo-lowering)
 tablegen(LLVM AMDGPUGenRegisterBank.inc -gen-register-bank)
 tablegen(LLVM AMDGPUGenRegisterInfo.inc -gen-register-info)
 tablegen(LLVM AMDGPUGenSearchableTables.inc -gen-searchable-tables)
 tablegen(LLVM AMDGPUGenSubtargetInfo.inc -gen-subtarget)
 
 set(LLVM_TARGET_DEFINITIONS AMDGPUGISel.td)
 tablegen(LLVM AMDGPUGenGlobalISel.inc -gen-global-isel)
-tablegen(LLVM AMDGPUGenPreLegalizeGICombiner.inc -gen-global-isel-combiner-matchtable
+tablegen(LLVM AMDGPUGenPreLegalizeGICombiner.inc -gen-global-isel-combiner
               -combiners="AMDGPUPreLegalizerCombiner")
-tablegen(LLVM AMDGPUGenPostLegalizeGICombiner.inc -gen-global-isel-combiner-matchtable
+tablegen(LLVM AMDGPUGenPostLegalizeGICombiner.inc -gen-global-isel-combiner
               -combiners="AMDGPUPostLegalizerCombiner")
-tablegen(LLVM AMDGPUGenRegBankGICombiner.inc -gen-global-isel-combiner-matchtable
+tablegen(LLVM AMDGPUGenRegBankGICombiner.inc -gen-global-isel-combiner
               -combiners="AMDGPURegBankCombiner")
 
 set(LLVM_TARGET_DEFINITIONS R600.td)
 tablegen(LLVM R600GenAsmWriter.inc -gen-asm-writer)
 tablegen(LLVM R600GenCallingConv.inc -gen-callingconv)
 tablegen(LLVM R600GenDAGISel.inc -gen-dag-isel)
 tablegen(LLVM R600GenDFAPacketizer.inc -gen-dfa-packetizer)
 tablegen(LLVM R600GenInstrInfo.inc -gen-instr-info)

llvm/lib/Target/Mips/CMakeLists.txt

 add_llvm_component_group(Mips HAS_JIT)
 
 set(LLVM_TARGET_DEFINITIONS Mips.td)
 
 tablegen(LLVM MipsGenAsmMatcher.inc -gen-asm-matcher)
 tablegen(LLVM MipsGenAsmWriter.inc -gen-asm-writer)
 tablegen(LLVM MipsGenCallingConv.inc -gen-callingconv)
 tablegen(LLVM MipsGenDAGISel.inc -gen-dag-isel)
 tablegen(LLVM MipsGenDisassemblerTables.inc -gen-disassembler)
 tablegen(LLVM MipsGenFastISel.inc -gen-fast-isel)
 tablegen(LLVM MipsGenGlobalISel.inc -gen-global-isel)
-tablegen(LLVM MipsGenPostLegalizeGICombiner.inc -gen-global-isel-combiner-matchtable
+tablegen(LLVM MipsGenPostLegalizeGICombiner.inc -gen-global-isel-combiner
               -combiners="MipsPostLegalizerCombiner")
 tablegen(LLVM MipsGenInstrInfo.inc -gen-instr-info)
 tablegen(LLVM MipsGenMCCodeEmitter.inc -gen-emitter)
 tablegen(LLVM MipsGenMCPseudoLowering.inc -gen-pseudo-lowering)
 tablegen(LLVM MipsGenRegisterBank.inc -gen-register-bank)
 tablegen(LLVM MipsGenRegisterInfo.inc -gen-register-info)
 tablegen(LLVM MipsGenSubtargetInfo.inc -gen-subtarget)
 tablegen(LLVM MipsGenExegesis.inc -gen-exegesis)

llvm/test/TableGen/GICombinerEmitter/defs-invalid.td

-// RUN: not llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \
-// RUN:     -combiners=MyCombiner %s 2>&1 | \
-// RUN:     FileCheck -implicit-check-not=error: %s
-
-include "llvm/Target/Target.td"
-include "llvm/Target/GlobalISel/Combine.td"
-
-def MyTargetISA : InstrInfo;
-def MyTarget : Target { let InstructionSet = MyTargetISA; }
-
-def dummy;
-
-def missing_defs_node : GICombineRule<
-  (dummy),
-  (dummy),
-  (dummy)>;
-// CHECK: :[[@LINE-4]]:{{[0-9]+}}: error: Expected defs operator
-// CHECK-NEXT: def missing_defs_node : GICombineRule<
-// CHECK: :[[@LINE-6]]:{{[0-9]+}}: error: Failed to parse rule
-
-def no_roots : GICombineRule<
-  (defs),
-  (dummy),
-  (dummy)>;
-// CHECK: :[[@LINE-4]]:{{[0-9]+}}: error: Combine rules must have at least one root
-// CHECK-NEXT: def no_roots : GICombineRule<
-// CHECK: :[[@LINE-6]]:{{[0-9]+}}: error: Failed to parse rule
-
-def unknown_kind : GICombineRule<
-  (defs dummy:$a),
-  (dummy),
-  (dummy)>;
-// CHECK: :[[@LINE-4]]:{{[0-9]+}}: error: Expected a subclass of GIDefKind or a sub-dag whose operator is of type GIDefKindWithArgs
-// CHECK-NEXT: def unknown_kind : GICombineRule<
-// CHECK: :[[@LINE-6]]:{{[0-9]+}}: error: Failed to parse rule
-
-def MyCombiner: GICombinerHelper<"GenMyCombiner", [
-// CHECK: :[[@LINE-1]]:{{[0-9]+}}: error: Failed to parse one or more rules
-  missing_defs_node,
-  no_roots,
-  unknown_kind
-]>;

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

-// RUN: not llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \
-// RUN:     -combiners=MyCombiner %s 2>&1 | \
-// RUN:     FileCheck -implicit-check-not=error: %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 missing_match_node : GICombineRule<
-  (defs root:$a),
-  (dummy),
-  (dummy)>;
-// CHECK: :[[@LINE-4]]:{{[0-9]+}}: error: Expected match operator
-// CHECK-NEXT: def missing_match_node : GICombineRule<
-// CHECK: :[[@LINE-6]]:{{[0-9]+}}: error: Failed to parse rule
-
-def null_matcher : GICombineRule<
-  (defs root:$a),
-  (match),
-  (dummy)>;
-// CHECK: :[[@LINE-4]]:{{[0-9]+}}: error: Matcher is empty
-// CHECK-NEXT: def null_matcher : GICombineRule<
-// CHECK: :[[@LINE-6]]:{{[0-9]+}}: error: Failed to parse rule
-
-def unknown_kind1 : GICombineRule<
-  (defs root:$a),
-  (match 0),
-  (dummy)>;
-// CHECK: :[[@LINE-4]]:{{[0-9]+}}: error: Expected a subclass of GIMatchKind or a sub-dag whose operator is either of a GIMatchKindWithArgs or Instruction
-// CHECK-NEXT: def unknown_kind1 : GICombineRule<
-// CHECK: :[[@LINE-6]]:{{[0-9]+}}: error: Failed to parse rule
-
-def unknown_kind2 : GICombineRule<
-  (defs root:$a),
-  (match (dummy)),
-  (dummy)>;
-// CHECK: :[[@LINE-4]]:{{[0-9]+}}: error: Expected a subclass of GIMatchKind or a sub-dag whose operator is either of a GIMatchKindWithArgs or Instruction
-// CHECK-NEXT: def unknown_kind2 : GICombineRule<
-// CHECK: :[[@LINE-6]]:{{[0-9]+}}: error: Failed to parse rule
-
-def multidef : GICombineRule<
-  (defs root:$a),
-  (match (MOV $a, $b),
-         (MOV $a, $b)),
-  (dummy)>;
-// CHECK: :[[@LINE-5]]:{{[0-9]+}}: error: Two different MachineInstrs cannot def the same vreg
-// CHECK-NEXT: def multidef : GICombineRule<
-// CHECK: :[[@LINE-7]]:{{[0-9]+}}: error: Failed to parse rule
-
-def multidef_but_not_an_error: GICombineRule<
-  (defs root:$a),
-  (match (MOV $a, $b),
-         (MOV $a, $b)),
-  (dummy)>;
-// CHECK-NOT: :[[@LINE-5]]:{{[0-9]+}}: error:
-
-def MyCombiner: GICombinerHelper<"GenMyCombiner", [
-// CHECK: :[[@LINE-1]]:{{[0-9]+}}: error: Failed to parse one or more rules
-  missing_match_node,
-  null_matcher,
-  unknown_kind1,
-  unknown_kind2,
-  multidef
-  // Rules omitted from a matcher can be as broken as you like. They will not be read.
-  // multidef_but_not_an_error
-]>;

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 %t.inc | FileCheck %s
-//
-// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \
-// RUN:     -combiners=MyCombinerHelper %s | \
-// RUN: FileCheck --check-prefix=CODE %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 ICMP : I<(outs GPR32:$dst), (ins GPR32:$tst, GPR32:$src1, GPR32:$src2), []>;
-
-def HasFoo : Predicate<"Subtarget->hasFoo()">;
-def HasAnswerToEverything : Predicate<"Subtarget->getAnswerToUniverse() == 42 && Subtarget->getAnswerToLife() == 42">;
-
-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 }])>;
-
-let Predicates = [HasFoo] in
-def Rule5 : GICombineRule<
-  (defs root:$d),
-  (match (SUB $d, $s1, $s2)),
-  (apply [{ APPLY }])>;
-
-let Predicates = [HasFoo, HasAnswerToEverything] in
-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 }])>;
-
-// Rules 8&9 check that the partitions are formed correctly if
-// - there is an edge different from Operand(1) -> Operand(0)
-// - more than one leaf is ignored because the leaf does not
-//   care about the instruction
-// - a single instruction has more operands than all others
-// These conditions triggered a crash when emitting the
-// resulting source code.
-def Rule8 : GICombineRule<
-  (defs root:$d),
-  (match (ICMP $ic, $cc, $s2, $s3),
-         (ZEXT $z, $ic),
-         (MUL $d, $t, $z),
-         [{ MATCH }]),
-  (apply [{ APPLY }])>;
-
-def Rule9 : GICombineRule<
-  (defs root:$d),
-  (match (MUL $d, $t, $z)),
-  (apply [{ APPLY }])>;
-
-def MyCombinerHelper: GICombinerHelper<"GenMyCombinerHelper", [
-  Rule0,
-  Rule1,
-  Rule2,
-  Rule3,
-  Rule4,
-  Rule5,
-  Rule6,
-  Rule7,
-  Rule8,
-  Rule9
-]>;
-
-// CHECK-LABEL: digraph "matchtree" {
-// CHECK-DAG:   Node[[N0:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[0].getOpcode()|5 partitions|Rule0,Rule1,Rule2,Rule3,Rule4,Rule5,Rule6,Rule7,Rule8,Rule9}"]
-// CHECK-DAG:   Node[[N1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|2 partitions|Rule0,Rule5}"]
-// CHECK-DAG:   Node[[N2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule0,Rule5}"]
-// CHECK-DAG:   Node[[N3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule0}"]
-// CHECK-DAG:   Node[[N4:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule5}"]
-// CHECK-DAG:   Node[[N5:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule5}"]
-// CHECK-DAG:   Node[[N6:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|2 partitions|Rule1,Rule2}"]
-// CHECK-DAG:   Node[[N7:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule1,Rule2}"]
-// CHECK-DAG:   Node[[N8:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule1}"]
-// CHECK-DAG:   Node[[N9:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule2}"]
-// CHECK-DAG:   Node[[N10:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule2}"]
-// CHECK-DAG:   Node[[N11:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|2 partitions|Rule3,Rule4}"]
-// CHECK-DAG:   Node[[N12:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule3,Rule4}"]
-// CHECK-DAG:   Node[[N13:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule3,Rule4}",color=red]
-// CHECK-DAG:   Node[[N14:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule4}"]
-// CHECK-DAG:   Node[[N15:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule4}"]
-// CHECK-DAG:   Node[[N16:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|1 partitions|Rule6,Rule7}"]
-// CHECK-DAG:   Node[[N17:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule6,Rule7}"]
-// CHECK-DAG:   Node[[N18:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule6}"]
-// CHECK-DAG:   Node[[N19:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule7}"]
-// CHECK-DAG:   Node[[N20:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(2))|2 partitions|Rule8,Rule9}"]
-// CHECK-DAG:   Node[[N21:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule8,Rule9}"]
-// CHECK-DAG:   Node[[N22:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[2] = getVRegDef(MI[1].getOperand(1))|1 partitions|Rule8,Rule9}"]
-// CHECK-DAG:   Node[[N23:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[2].getOpcode()|2 partitions|Rule8,Rule9}"]
-// CHECK-DAG:   Node[[N24:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule8,Rule9}",color=red]
-// CHECK-DAG:   Node[[N25:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule9}"]
-// CHECK-DAG:   Node[[N26:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule9}"]
-// CHECK-DAG:   Node[[N27:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule9}"]
-
-// 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"]
-// CHECK-DAG:   Node[[N0]] -> Node[[N20]] [label="#4 MyTarget::MUL"]
-
-// 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"]
-
-// Follow the links for MI[0].getOpcode() == MUL.
-// CHECK-DAG:   Node[[N20]] -> Node[[N21]] [label="#0 true"]
-// CHECK-DAG:   Node[[N20]] -> Node[[N27]] [label="#1 false"]
-
-// CHECK-DAG:   Node[[N21]] -> Node[[N22]] [label="#0 MyTarget::ZEXT"]
-// CHECK-DAG:   Node[[N21]] -> Node[[N26]] [label="#1 * or nullptr"]
-
-// CHECK-DAG:   Node[[N22]] -> Node[[N23]] [label="#0 true"]
-
-// CHECK-DAG:   Node[[N23]] -> Node[[N24]] [label="#0 MyTarget::ICMP"]
-// CHECK-DAG:   Node[[N23]] -> Node[[N25]] [label="#1 * or nullptr"]
-
-
-// CHECK-LABEL: {{^}$}}
-
-
-// Check the generated source code.
-
-// CODE-LABEL: GenMyCombinerHelper::tryCombineAll
-
-// Check the first partition. The numbers correspond to the labels above.
-// CODE:      switch (MIs[0]->getOpcode()) {
-// CODE-NEXT:   case MyTarget::SUB: Partition = 0; break;
-// CODE-NEXT:   case MyTarget::MOV: Partition = 1; break;
-// CODE-NEXT:   case MyTarget::ADD: Partition = 2; break;
-// CODE-NEXT:   case MyTarget::TRUNC: Partition = 3; break;
-// CODE-NEXT:   case MyTarget::MUL: Partition = 4; break;
-// CODE-NEXT: }
-
-// Check that the correct partition is choosen if operand 1 is a register.
-
-// CODE:       if (Partition == 0 /* MyTarget::SUB */) {
-// CODE-NEXT:    Partition = -1;
-// CODE-NEXT:    if (MIs.size() <= 1) MIs.resize(2);
-// CODE-NEXT:    MIs[1] = nullptr;
-// CODE-NEXT:    if (MIs[0]->getOperand(1).isReg())
-// CODE-NEXT:      MIs[1] = MRI.getVRegDef(MIs[0]->getOperand(1).getReg());
-// CODE-NEXT:    if (MIs[1] == nullptr) Partition = 1;
-// CODE-NEXT:    if (MIs[1] != nullptr) Partition = 0;
-
-
-// Check that the MUL opcode is tested.
-
-// CODE:         if (Partition == 0 /* true */) {
-// CODE-NEXT:      Partition = -1;
-// CODE-NEXT:      switch (MIs[1]->getOpcode()) {
-// CODE-NEXT:      case MyTarget::MUL: Partition = 0; break;
-// CODE-NEXT:      default: Partition = 1; break;
-// CODE-NEXT:      }
-
-// Check that action for MUL is executed.
-
-// CODE:          if (Partition == 0 /* MyTarget::MUL */) {
-// CODE-NEXT:       // Leaf name: Rule0
-// CODE-NEXT:        // Rule: Rule0
-// CODE-NEXT:        if (!RuleConfig->isRuleDisabled(0)) {
-// CODE-NEXT:          if (1
-// CODE-NEXT:) {
-// CODE-NEXT:            LLVM_DEBUG(dbgs() << "Applying rule 'Rule0'\n");
-// CODE-NEXT:            APPLY
-// CODE-NEXT:            return true;
-// CODE-NEXT:          }
-// CODE-NEXT:        }
-// CODE-NEXT:        llvm_unreachable("Combine rule elision was incorrect");
-// CODE-NEXT:        return false;
-// CODE-NEXT:     }
-
-// Check that the other rule involving SUB (Rule5) is run otherwise.
-
-// CODE-NEXT:      if (Partition == 1 /* * or nullptr */) {
-// CODE-NEXT:        // Leaf name: Rule5
-// CODE-NEXT:        // Rule: Rule5
-// CODE-NEXT:        if (!RuleConfig->isRuleDisabled(5)) {
-// CODE-NEXT:          if (1
-// CODE-NEXT:               && (
-// CODE-NEXT:               // Predicate: HasFoo
-// CODE-NEXT:               Subtarget->hasFoo()
-// CODE-NEXT:               )
-// CODE-NEXT:) {
-// CODE-NEXT:            LLVM_DEBUG(dbgs() << "Applying rule 'Rule5'\n");
-// CODE-NEXT:            APPLY
-// CODE-NEXT:            return true;
-// CODE-NEXT:          }
-// CODE-NEXT:        }
-// CODE-NEXT:        llvm_unreachable("Combine rule elision was incorrect");
-// CODE-NEXT:        return false;
-// CODE-NEXT:      }
-// CODE-NEXT:    }
-
-// Check that Rule5 is run if operand 1 is not MUL.
-
-// CODE-NEXT:    if (Partition == 1 /* false */) {
-// CODE-NEXT:      // Leaf name: Rule5
-// CODE-NEXT:      // Rule: Rule5
-// CODE-NEXT:      if (!RuleConfig->isRuleDisabled(5)) {
-// CODE-NEXT:        if (1
-// CODE-NEXT:             && (
-// CODE-NEXT:             // Predicate: HasFoo
-// CODE-NEXT:             Subtarget->hasFoo()
-// CODE-NEXT:             )
-// CODE-NEXT:      ) {
-// CODE-NEXT:          LLVM_DEBUG(dbgs() << "Applying rule 'Rule5'\n");
-// CODE-NEXT:          APPLY
-// CODE-NEXT:          return true;
-// CODE-NEXT:        }
-// CODE-NEXT:      }
-// CODE-NEXT:      llvm_unreachable("Combine rule elision was incorrect");
-// CODE-NEXT:      return false;
-// CODE-NEXT:    }
-// CODE-NEXT:  }
-
-
-// Check multiple predicates are correctly emitted
-
-// CODE:      // Leaf name: Rule6
-// CODE-NEXT: // Rule: Rule6
-// CODE-NEXT: if (!RuleConfig->isRuleDisabled(6)) {
-// CODE-NEXT:   if (1
-// CODE-NEXT:       && (
-// CODE-NEXT:            // Predicate: HasFoo
-// CODE-NEXT:            Subtarget->hasFoo()
-// CODE-NEXT:          )
-// CODE-NEXT:       && (
-// CODE-NEXT:            // Predicate: HasAnswerToEverything
-// CODE-NEXT:            Subtarget->getAnswerToUniverse() == 42 && Subtarget->getAnswerToLife() == 42
-// CODE-NEXT:          )
-// CODE-NEXT:      ) {
-// CODE-NEXT:     LLVM_DEBUG(dbgs() << "Applying rule 'Rule6'\n");
-// CODE-NEXT:     APPLY
-// CODE-NEXT:     return true;
-// CODE-NEXT:   }
-// CODE-NEXT: }

llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td

-// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \
-// RUN:     -combiners=MyCombiner -gicombiner-stop-after-parse %s \
-// RUN:     -o /dev/null -debug 2>&1 | FileCheck %s
-// REQUIRES: asserts
-
-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 MOV2 : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
-
-def trivial : GICombineRule<
-  (defs root:$d),
-  (match (MOV $d, $s)),
-  (apply [{ APPLY }])>;
-
-// CHECK-LABEL: Parsed rule defs/match for 'trivial'
-
-// The matchdag block is a fairly direct dump of the information that was read.
-// It's oriented towards the data structures within tablegen.
-// CHECK-NEXT: matchdag {
-// CHECK-NEXT:     (MOV 0:dst<def>, 1:src1):$__anon0_0 // $d=getOperand(0), $s=getOperand(1)
-// CHECK-NEXT:     <<$mi.getOpcode() == MOV>>:$__anonpred0_1
-// CHECK-NEXT:     __anon0_0 ==> __anonpred0_1[mi]
-// CHECK-NEXT: {{^}$}}
-
-// The digraph block is a human-oriented dump of the information that was read.
-// Run it through graphviz to produce a nice DAG showing the matcher behaviour.
-// CHECK-NEXT: digraph "trivial" {
-// CHECK-NEXT:   rankdir="BT"
-// CHECK-NEXT:   Node[[N1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon0_0|MOV|Match starts here|$d=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $dst|<d1>#1 $src1}}",color=red]
-// CHECK-NEXT:   Pred[[P1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred0_1|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
-// CHECK-NEXT:   Node[[N1]]:e -> Pred[[P1]]:d1:s [style=dotted]
-// CHECK-NEXT: {{^}$}}
-
-def simple : GICombineRule<
-  (defs root:$d),
-  (match (MOV $t, $s),
-         (MOV $d, $t)),
-  (apply [{ APPLY }])>;
-
-// CHECK-LABEL: Parsed rule defs/match for 'simple'
-
-// CHECK-NEXT: matchdag {
-// CHECK-NEXT:     (MOV 0:dst<def>, 1:src1):$__anon1_0 // $t=getOperand(0), $s=getOperand(1)
-// CHECK-NEXT:     (MOV 0:dst<def>, 1:src1):$__anon1_2 // $d=getOperand(0), $t=getOperand(1)
-// CHECK-NEXT:     __anon1_2[src1] --[t]--> __anon1_0[dst]
-// CHECK-NEXT:     <<$mi.getOpcode() == MOV>>:$__anonpred1_1
-// CHECK-NEXT:     <<$mi.getOpcode() == MOV>>:$__anonpred1_3
-// CHECK-NEXT:     __anon1_0 ==> __anonpred1_1[mi]
-// CHECK-NEXT:     __anon1_2 ==> __anonpred1_3[mi]
-// CHECK-NEXT: {{^}$}}
-
-// CHECK-NEXT: digraph "simple" {
-// CHECK-NEXT:   rankdir="BT"
-// CHECK-NEXT:   Node[[N1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon1_0|MOV|$t=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $dst|<d1>#1 $src1}}"]
-// CHECK-NEXT:   Node[[N2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon1_2|MOV|Match starts here|$d=getOperand(0), $t=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $dst|<d1>#1 $src1}}",color=red]
-// CHECK-NEXT:   Node[[N2]]:s1:n -> Node[[N1]]:d0:s [label="$t"]
-// CHECK-NEXT:   Pred[[P1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred1_1|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
-// CHECK-NEXT:   Pred[[P2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred1_3|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
-// CHECK-NEXT:   Node[[N1]]:e -> Pred[[P1]]:d1:s [style=dotted]
-// CHECK-NEXT:   Node[[N2]]:e -> Pred[[P2]]:d1:s [style=dotted]
-// CHECK-NEXT: {{^}$}}
-
-def multiroot : GICombineRule<
-  (defs root:$d1, root:$d2),
-  (match (MOV $s, $s2),
-         (MOV $d1, $s),
-         (MOV $d2, $s)),
-  (apply [{ APPLY }])>;
-
-// CHECK-LABEL: Parsed rule defs/match for 'multiroot'
-
-// CHECK-NEXT: matchdag {
-// CHECK-NEXT:     (MOV 0:dst<def>, 1:src1):$__anon2_0 // $s=getOperand(0), $s2=getOperand(1)
-// CHECK-NEXT:     (MOV 0:dst<def>, 1:src1):$__anon2_2 // $d1=getOperand(0), $s=getOperand(1)
-// CHECK-NEXT:     (MOV 0:dst<def>, 1:src1):$__anon2_4 // $d2=getOperand(0), $s=getOperand(1)
-// CHECK-NEXT:     __anon2_2[src1] --[s]--> __anon2_0[dst]
-// CHECK-NEXT:     __anon2_4[src1] --[s]--> __anon2_0[dst]
-// CHECK-NEXT:     <<$mi.getOpcode() == MOV>>:$__anonpred2_1
-// CHECK-NEXT:     <<$mi.getOpcode() == MOV>>:$__anonpred2_3
-// CHECK-NEXT:     <<$mi.getOpcode() == MOV>>:$__anonpred2_5
-// CHECK-NEXT:     <<$mi0 == $mi1>>:$__anonpred2_6
-// CHECK-NEXT:     __anon2_0 ==> __anonpred2_1[mi]
-// CHECK-NEXT:     __anon2_2 ==> __anonpred2_3[mi]
-// CHECK-NEXT:     __anon2_4 ==> __anonpred2_5[mi]
-// CHECK-NEXT:     __anon2_2[src1] ==> __anonpred2_6[mi0]
-// CHECK-NEXT:     __anon2_4[src1] ==> __anonpred2_6[mi1]
-// CHECK-NEXT: {{^}$}}
-
-// CHECK-NEXT: digraph "multiroot" {
-// CHECK-NEXT:   rankdir="BT"
-// CHECK-NEXT:   Node[[N1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon2_0|MOV|$s=getOperand(0), $s2=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $dst|<d1>#1 $src1}}"]
-// CHECK-NEXT:   Node[[N2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon2_2|MOV|Match starts here|$d1=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $dst|<d1>#1 $src1}}",color=red]
-// CHECK-NEXT:   Node[[N3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon2_4|MOV|Match starts here|$d2=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $dst|<d1>#1 $src1}}",color=red]
-// CHECK-NEXT:   Node[[N2]]:s1:n -> Node[[N1]]:d0:s [label="$s"]
-// CHECK-NEXT:   Node[[N3]]:s1:n -> Node[[N1]]:d0:s [label="$s"]
-// CHECK-NEXT:   Pred[[P1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred2_1|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
-// CHECK-NEXT:   Pred[[P2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred2_3|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
-// CHECK-NEXT:   Pred[[P3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred2_5|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
-// CHECK-NEXT:   Pred[[P4:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi0|<s2>#2 $mi1}|__anonpred2_6|$mi0 == $mi1|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $$|<d1>#1 $mi0|<d2>#2 $mi1}}",style=dotted]
-// CHECK-NEXT:   Node[[N1]]:e -> Pred[[P1]]:d1:s [style=dotted]
-// CHECK-NEXT:   Node[[N2]]:e -> Pred[[P2]]:d1:s [style=dotted]
-// CHECK-NEXT:   Node[[N3]]:e -> Pred[[P3]]:d1:s [style=dotted]
-// CHECK-NEXT:   Node[[N2]]:s1:n -> Pred[[P4]]:d1:s [style=dotted]
-// CHECK-NEXT:   Node[[N3]]:s1:n -> Pred[[P4]]:d2:s [style=dotted]
-// CHECK-NEXT: {{^}$}}
-
-def nonstandardroot : GICombineRule<
-  (defs root:$s),
-  (match (MOV $s, $s2),
-         (MOV $d1, $s),
-         (MOV $d2, $s)),
-  (apply [{ APPLY }])>;
-
-// CHECK-LABEL: Parsed rule defs/match for 'nonstandardroot'
-
-// CHECK-NEXT: matchdag {
-// CHECK-NEXT:     (MOV 0:dst<def>, 1:src1):$__anon3_0 // $s=getOperand(0), $s2=getOperand(1)
-// CHECK-NEXT:     (MOV 0:dst<def>, 1:src1):$__anon3_2 // $d1=getOperand(0), $s=getOperand(1)
-// CHECK-NEXT:     (MOV 0:dst<def>, 1:src1):$__anon3_4 // $d2=getOperand(0), $s=getOperand(1)
-// CHECK-NEXT:     __anon3_0[dst] --[s]--> __anon3_2[src1]
-// CHECK-NEXT:     __anon3_0[dst] --[s]--> __anon3_4[src1]
-// CHECK-NEXT:     <<$mi.getOpcode() == MOV>>:$__anonpred3_1
-// CHECK-NEXT:     <<$mi.getOpcode() == MOV>>:$__anonpred3_3
-// CHECK-NEXT:     <<$mi.getOpcode() == MOV>>:$__anonpred3_5
-// CHECK-NEXT:     <<$mi0 == $mi1>>:$__anonpred3_6
-// CHECK-NEXT:     __anon3_0 ==> __anonpred3_1[mi]
-// CHECK-NEXT:     __anon3_2 ==> __anonpred3_3[mi]
-// CHECK-NEXT:     __anon3_4 ==> __anonpred3_5[mi]
-// CHECK-NEXT:     __anon3_2[src1] ==> __anonpred3_6[mi0]
-// CHECK-NEXT:     __anon3_4[src1] ==> __anonpred3_6[mi1]
-// CHECK-NEXT: {{^}$}}
-
-// CHECK-NEXT: digraph "nonstandardroot" {
-// CHECK-NEXT:   rankdir="BT"
-// CHECK-NEXT:   Node[[N1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon3_0|MOV|Match starts here|$s=getOperand(0), $s2=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $dst|<d1>#1 $src1}}",color=red]
-// CHECK-NEXT:   Node[[N2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon3_2|MOV|$d1=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $dst|<d1>#1 $src1}}"]
-// CHECK-NEXT:   Node[[N3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon3_4|MOV|$d2=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $dst|<d1>#1 $src1}}"]
-// CHECK-NEXT:   Node[[N2]]:s1:n -> Node[[N1]]:d0:s [label="$s",dir=back,arrowtail=crow]
-// CHECK-NEXT:   Node[[N3]]:s1:n -> Node[[N1]]:d0:s [label="$s",dir=back,arrowtail=crow]
-// CHECK-NEXT:   Pred[[P1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred3_1|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
-// CHECK-NEXT:   Pred[[P2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred3_3|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
-// CHECK-NEXT:   Pred[[P3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred3_5|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
-// CHECK-NEXT:   Pred[[P4:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi0|<s2>#2 $mi1}|__anonpred3_6|$mi0 == $mi1|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $$|<d1>#1 $mi0|<d2>#2 $mi1}}",style=dotted]
-// CHECK-NEXT:   Node[[N1]]:e -> Pred[[P1]]:d1:s [style=dotted]
-// CHECK-NEXT:   Node[[N2]]:e -> Pred[[P2]]:d1:s [style=dotted]
-// CHECK-NEXT:   Node[[N3]]:e -> Pred[[P3]]:d1:s [style=dotted]
-// CHECK-NEXT:   Node[[N2]]:s1:n -> Pred[[P4]]:d1:s [style=dotted]
-// CHECK-NEXT:   Node[[N3]]:s1:n -> Pred[[P4]]:d2:s [style=dotted]
-// CHECK-NEXT: {{^}$}}
-
-def multiref_use : GICombineRule<
-  (defs root:$d1, root:$d2),
-  (match (MOV $d1, $s),
-         (MOV $d2, $s)),
-  (apply [{ APPLY }])>;
-
-// CHECK-LABEL: Parsed rule defs/match for 'multiref_use'
-
-// CHECK-NEXT: matchdag {
-// CHECK-NEXT:     (MOV 0:dst<def>, 1:src1):$__anon4_0 // $d1=getOperand(0), $s=getOperand(1)
-// CHECK-NEXT:     (MOV 0:dst<def>, 1:src1):$__anon4_2 // $d2=getOperand(0), $s=getOperand(1)
-// CHECK-NEXT:     <<$mi.getOpcode() == MOV>>:$__anonpred4_1
-// CHECK-NEXT:     <<$mi.getOpcode() == MOV>>:$__anonpred4_3
-// CHECK-NEXT:     <<$mi0 == $mi1>>:$__anonpred4_4
-// CHECK-NEXT:     __anon4_0 ==> __anonpred4_1[mi]
-// CHECK-NEXT:     __anon4_2 ==> __anonpred4_3[mi]
-// CHECK-NEXT:     __anon4_0[src1] ==> __anonpred4_4[mi0]
-// CHECK-NEXT:     __anon4_2[src1] ==> __anonpred4_4[mi1]
-// CHECK-NEXT: {{^}$}}
-
-// CHECK-NEXT: digraph "multiref_use" {
-// CHECK-NEXT:   rankdir="BT"
-// CHECK-NEXT:   Node[[N1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon4_0|MOV|Match starts here|$d1=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $dst|<d1>#1 $src1}}",color=red]
-// CHECK-NEXT:   Node[[N2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon4_2|MOV|Match starts here|$d2=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $dst|<d1>#1 $src1}}",color=red]
-// CHECK-NEXT:   Pred[[P1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred4_1|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
-// CHECK-NEXT:   Pred[[P2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred4_3|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
-// CHECK-NEXT:   Pred[[P3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi0|<s2>#2 $mi1}|__anonpred4_4|$mi0 == $mi1|{{(0x)?[0-9a-fA-F]+}}|{<d0>#0 $$|<d1>#1 $mi0|<d2>#2 $mi1}}",style=dotted]
-// CHECK-NEXT:   Node[[N1]]:e -> Pred[[P1]]:d1:s [style=dotted]
-// CHECK-NEXT:   Node[[N2]]:e -> Pred[[P2]]:d1:s [style=dotted]
-// CHECK-NEXT:   Node[[N1]]:s1:n -> Pred[[P3]]:d1:s [style=dotted]
-// CHECK-NEXT:   Node[[N2]]:s1:n -> Pred[[P3]]:d2:s [style=dotted]
-// CHECK-NEXT: {{^}$}}
-
-def MyCombiner: GICombinerHelper<"GenMyCombiner", [
-  trivial,
-  simple,
-  multiroot,
-  nonstandardroot,
-  multiref_use
-]>;
-
-// Verify we're sharing operand lists correctly
-// CHECK-LABEL: GIMatchDagOperandListContext {
-// CHECK-NEXT:    OperandLists {
-// CHECK-NEXT:      0:dst<def>, 1:src1{{$}}
-// CHECK-NEXT:      0:$<def>, 1:mi{{$}}
-// CHECK-NEXT:      0:$<def>, 1:mi0, 2:mi1{{$}}
-// CHECK-NEXT:    }
-// CHECK-NEXT:  }

llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-imms.td

-// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \
+// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \
 // RUN:     -combiners=MyCombiner %s | \
 // RUN: FileCheck %s
 
 include "llvm/Target/Target.td"
 include "llvm/Target/GlobalISel/Combine.td"
 
 def MyTargetISA : InstrInfo;
 def MyTarget : Target { let InstructionSet = MyTargetISA; }

llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-operand-types.td

-// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \
+// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \
 // RUN:     -combiners=MyCombiner %s | \
 // RUN: FileCheck %s
 
 include "llvm/Target/Target.td"
 include "llvm/Target/GlobalISel/Combine.td"
 
 def MyTargetISA : InstrInfo;
 def MyTarget : Target { let InstructionSet = MyTargetISA; }

llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-patfrag-root.td

-// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \
-// RUN:     -combiners=MyCombiner -gicombiner-matchtable-debug-cxxpreds %s | \
+// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \
+// RUN:     -combiners=MyCombiner -gicombiner-debug-cxxpreds %s | \
 // RUN: FileCheck %s
 
 include "llvm/Target/Target.td"
 include "llvm/Target/GlobalISel/Combine.td"
 
 def MyTargetISA : InstrInfo;
 def MyTarget : Target { let InstructionSet = MyTargetISA; }
 

llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-permutations.td

-// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \
-// RUN:     -combiners=MyCombiner -gicombiner-matchtable-debug-cxxpreds %s | \
+// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \
+// RUN:     -combiners=MyCombiner -gicombiner-debug-cxxpreds %s | \
 // RUN: FileCheck %s
 
 include "llvm/Target/Target.td"
 include "llvm/Target/GlobalISel/Combine.td"
 
 def MyTargetISA : InstrInfo;
 def MyTarget : Target { let InstructionSet = MyTargetISA; }
 

llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-variadics.td

-// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \
+// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \
 // RUN:     -combiners=MyCombiner %s | \
 // RUN: FileCheck %s
 
 include "llvm/Target/Target.td"
 include "llvm/Target/GlobalISel/Combine.td"
 
 def MyTargetISA : InstrInfo;
 def MyTarget : Target { let InstructionSet = MyTargetISA; }

llvm/test/TableGen/GlobalISelCombinerEmitter/match-table.td

-// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \
+// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \
 // RUN:     -combiners=MyCombiner %s | \
 // RUN: FileCheck %s
 
 include "llvm/Target/Target.td"
 include "llvm/Target/GlobalISel/Combine.td"
 
 def MyTargetISA : InstrInfo;
 def MyTarget : Target { let InstructionSet = MyTargetISA; }

llvm/test/TableGen/GlobalISelCombinerEmitter/operand-types.td

-// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \
+// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \
 // RUN:     -gicombiner-stop-after-parse -combiners=MyCombiner %s | \
 // RUN: FileCheck %s
 
 include "llvm/Target/Target.td"
 include "llvm/Target/GlobalISel/Combine.td"
 
 def MyTargetISA : InstrInfo;
 def MyTarget : Target { let InstructionSet = MyTargetISA; }

llvm/test/TableGen/GlobalISelCombinerEmitter/patfrag-errors.td

-// RUN: not llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \
+// RUN: not llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \
 // RUN:     -combiners=MyCombiner %s 2>&1| \
 // RUN: FileCheck %s -implicit-check-not=error:
 
 include "llvm/Target/Target.td"
 include "llvm/Target/GlobalISel/Combine.td"
 
 def MyTargetISA : InstrInfo;
 def MyTarget : Target { let InstructionSet = MyTargetISA; }

llvm/test/TableGen/GlobalISelCombinerEmitter/pattern-errors.td

-// RUN: not llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \
+// RUN: not llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \
 // RUN:     -combiners=MyCombiner %s 2>&1| \
 // RUN: FileCheck %s -implicit-check-not=error:
 
 include "llvm/Target/Target.td"
 include "llvm/Target/GlobalISel/Combine.td"
 
 def MyTargetISA : InstrInfo;
 def MyTarget : Target { let InstructionSet = MyTargetISA; }

llvm/test/TableGen/GlobalISelCombinerEmitter/pattern-parsing.td

-// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \
+// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \
 // RUN:     -gicombiner-stop-after-parse -combiners=MyCombiner %s | \
 // RUN: FileCheck %s
 
 include "llvm/Target/Target.td"
 include "llvm/Target/GlobalISel/Combine.td"
 
 def MyTargetISA : InstrInfo;
 def MyTarget : Target { let InstructionSet = MyTargetISA; }

llvm/utils/TableGen/CMakeLists.txt

add_tablegen(llvm-tblgen LLVM
   DAGISelMatcher.cpp
   DecoderEmitter.cpp
   DFAEmitter.cpp
   DFAPacketizerEmitter.cpp
   DisassemblerEmitter.cpp
   DXILEmitter.cpp
   ExegesisEmitter.cpp
   FastISelEmitter.cpp
-  GICombinerEmitter.cpp
-  GlobalISelCombinerMatchTableEmitter.cpp
+  GlobalISelCombinerEmitter.cpp
   GlobalISelEmitter.cpp
   GlobalISelMatchTable.cpp
   GlobalISelMatchTableExecutorEmitter.cpp
   InfoByHwMode.cpp
   InstrInfoEmitter.cpp
   InstrDocsEmitter.cpp
   OptEmitter.cpp
   OptParserEmitter.cpp

llvm/utils/TableGen/GICombinerEmitter.cpp

-//===- GlobalCombinerEmitter.cpp - Generate a combiner --------------------===//
-//
-// 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
-//
-//===----------------------------------------------------------------------===//
-//
-/// \file Generate a combiner implementation for GlobalISel from a declarative
-/// syntax
-///
-//===----------------------------------------------------------------------===//
-
-#include "CodeGenTarget.h"
-#include "GlobalISel/CodeExpander.h"
-#include "GlobalISel/CodeExpansions.h"
-#include "GlobalISel/CombinerUtils.h"
-#include "GlobalISel/GIMatchDag.h"
-#include "GlobalISel/GIMatchDagEdge.h"
-#include "GlobalISel/GIMatchDagInstr.h"
-#include "GlobalISel/GIMatchDagOperands.h"
-#include "GlobalISel/GIMatchDagPredicate.h"
-#include "GlobalISel/GIMatchTree.h"
-#include "llvm/ADT/SmallSet.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/StringSet.h"
-#include "llvm/Support/CommandLine.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/ScopedPrinter.h"
-#include "llvm/TableGen/Error.h"
-#include "llvm/TableGen/Record.h"
-#include "llvm/TableGen/StringMatcher.h"
-#include "llvm/TableGen/TableGenBackend.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");
-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));
-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;
-
-public:
-  MatchDataInfo(StringRef PatternSymbol, StringRef Type, StringRef VariableName)
-      : PatternSymbol(PatternSymbol), Type(Type), VariableName(VariableName) {}
-
-  StringRef getPatternSymbol() const { return PatternSymbol; };
-  StringRef getType() const { return Type; };
-  StringRef getVariableName() const { return VariableName; };
-};
-
-class RootInfo {
-  StringRef PatternSymbol;
-
-public:
-  RootInfo(StringRef PatternSymbol) : PatternSymbol(PatternSymbol) {}
-
-  StringRef getPatternSymbol() const { return PatternSymbol; }
-};
-
-class CombineRule {
-public:
-
-  using const_matchdata_iterator = std::vector<MatchDataInfo>::const_iterator;
-
-  struct VarInfo {
-    const GIMatchDagInstr *N;
-    const GIMatchDagOperand *Op;
-    const DagInit *Matcher;
-
-  public:
-    VarInfo(const GIMatchDagInstr *N, const GIMatchDagOperand *Op,
-            const DagInit *Matcher)
-        : N(N), Op(Op), Matcher(Matcher) {}
-  };
-
-protected:
-  /// A unique ID for this rule
-  /// ID's are used for debugging and run-time disabling of rules among other
-  /// things.
-  RuleID ID;
-
-  /// A unique ID that can be used for anonymous objects belonging to this rule.
-  /// Used to create unique names in makeNameForAnon*() without making tests
-  /// overly fragile.
-  unsigned UID = 0;
-
-  /// The record defining this rule.
-  const Record &TheDef;
-
-  /// The roots of a match. These are the leaves of the DAG that are closest to
-  /// the end of the function. I.e. the nodes that are encountered without
-  /// following any edges of the DAG described by the pattern as we work our way
-  /// from the bottom of the function to the top.
-  std::vector<RootInfo> Roots;
-
-  GIMatchDag MatchDag;
-
-  /// A block of arbitrary C++ to finish testing the match.
-  /// FIXME: This is a temporary measure until we have actual pattern matching
-  const StringInit *MatchingFixupCode = nullptr;
-
-  /// The MatchData defined by the match stage and required by the apply stage.
-  /// This allows the plumbing of arbitrary data from C++ predicates between the
-  /// stages.
-  ///
-  /// For example, suppose you have:
-  ///   %A = <some-constant-expr>
-  ///   %0 = G_ADD %1, %A
-  /// you could define a GIMatchPredicate that walks %A, constant folds as much
-  /// as possible and returns an APInt containing the discovered constant. You
-  /// could then declare:
-  ///   def apint : GIDefMatchData<"APInt">;
-  /// add it to the rule with:
-  ///   (defs root:$root, apint:$constant)
-  /// evaluate it in the pattern with a C++ function that takes a
-  /// MachineOperand& and an APInt& with:
-  ///   (match [{MIR %root = G_ADD %0, %A }],
-  ///             (constantfold operand:$A, apint:$constant))
-  /// and finally use it in the apply stage with:
-  ///   (apply (create_operand
-  ///                [{ MachineOperand::CreateImm(${constant}.getZExtValue());
-  ///                ]}, apint:$constant),
-  ///             [{MIR %root = FOO %0, %constant }])
-  std::vector<MatchDataInfo> MatchDataDecls;
-
-  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();
-  bool parseMatcher(const CodeGenTarget &Target);
-
-  RuleID getID() const { return ID; }
-  unsigned allocUID() { return UID++; }
-  StringRef getName() const { return TheDef.getName(); }
-  const Record &getDef() const { return TheDef; }
-  const StringInit *getMatchingFixupCode() const { return MatchingFixupCode; }
-  size_t getNumRoots() const { return Roots.size(); }
-
-  GIMatchDag &getMatchDag() { return MatchDag; }
-  const GIMatchDag &getMatchDag() const { return MatchDag; }
-
-  using const_root_iterator = std::vector<RootInfo>::const_iterator;
-  const_root_iterator roots_begin() const { return Roots.begin(); }
-  const_root_iterator roots_end() const { return Roots.end(); }
-  iterator_range<const_root_iterator> roots() const {
-    return llvm::make_range(Roots.begin(), Roots.end());
-  }
-
-  iterator_range<const_matchdata_iterator> matchdata_decls() const {
-    return make_range(MatchDataDecls.begin(), MatchDataDecls.end());
-  }
-
-  /// Export expansions for this rule
-  void declareExpansions(CodeExpansions &Expansions) const {
-    for (const auto &I : matchdata_decls())
-      Expansions.declare(I.getPatternSymbol(), I.getVariableName());
-  }
-
-  /// The matcher will begin from the roots and will perform the match by
-  /// traversing the edges to cover the whole DAG. This function reverses DAG
-  /// edges such that everything is reachable from a root. This is part of the
-  /// preparation work for flattening the DAG into a tree.
-  void reorientToRoots() {
-    SmallSet<const GIMatchDagInstr *, 5> Roots;
-    SmallSet<const GIMatchDagInstr *, 5> Visited;
-    SmallSet<GIMatchDagEdge *, 20> EdgesRemaining;
-
-    for (auto &I : MatchDag.roots()) {
-      Roots.insert(I);
-      Visited.insert(I);
-    }
-    for (auto &I : MatchDag.edges())
-      EdgesRemaining.insert(I);
-
-    bool Progressed = false;
-    SmallSet<GIMatchDagEdge *, 20> EdgesToRemove;
-    while (!EdgesRemaining.empty()) {
-      for (auto *EI : EdgesRemaining) {
-        if (Visited.count(EI->getFromMI())) {
-          if (Roots.count(EI->getToMI()))
-            PrintError(TheDef.getLoc(), "One or more roots are unnecessary");
-          Visited.insert(EI->getToMI());
-          EdgesToRemove.insert(EI);
-          Progressed = true;
-        }
-      }
-      for (GIMatchDagEdge *ToRemove : EdgesToRemove)
-        EdgesRemaining.erase(ToRemove);
-      EdgesToRemove.clear();
-
-      for (auto EI = EdgesRemaining.begin(), EE = EdgesRemaining.end();
-           EI != EE; ++EI) {
-        if (Visited.count((*EI)->getToMI())) {
-          (*EI)->reverse();
-          Visited.insert((*EI)->getToMI());
-          EdgesToRemove.insert(*EI);
-          Progressed = true;
-        }
-        for (GIMatchDagEdge *ToRemove : EdgesToRemove)
-          EdgesRemaining.erase(ToRemove);
-        EdgesToRemove.clear();
-      }
-
-      if (!Progressed) {
-        LLVM_DEBUG(dbgs() << "No progress\n");
-        return;
-      }
-      Progressed = false;
-    }
-  }
-};
-
-StringRef makeNameForAnonInstr(CombineRule &Rule) {
-  return insertStrTab(to_string(
-      format("__anon%" PRIu64 "_%u", Rule.getID(), Rule.allocUID())));
-}
-
-StringRef makeDebugName(CombineRule &Rule, StringRef Name) {
-  return insertStrTab(Name.empty() ? makeNameForAnonInstr(Rule) : StringRef(Name));
-}
-
-StringRef makeNameForAnonPredicate(CombineRule &Rule) {
-  return insertStrTab(to_string(
-      format("__anonpred%" PRIu64 "_%u", Rule.getID(), Rule.allocUID())));
-}
-
-void CombineRule::declareMatchData(StringRef PatternSymbol, StringRef Type,
-                                   StringRef VarName) {
-  MatchDataDecls.emplace_back(PatternSymbol, Type, VarName);
-}
-
-bool CombineRule::parseDefs() {
-  DagInit *Defs = TheDef.getValueAsDag("Defs");
-
-  if (Defs->getOperatorAsDef(TheDef.getLoc())->getName() != "defs") {
-    PrintError(TheDef.getLoc(), "Expected defs operator");
-    return false;
-  }
-
-  for (unsigned I = 0, E = Defs->getNumArgs(); I < E; ++I) {
-    // Roots should be collected into Roots
-    if (isSpecificDef(*Defs->getArg(I), "root")) {
-      Roots.emplace_back(Defs->getArgNameStr(I));
-      continue;
-    }
-
-    // Subclasses of GIDefMatchData should declare that this rule needs to pass
-    // data from the match stage to the apply stage, and ensure that the
-    // generated matcher has a suitable variable for it to do so.
-    if (Record *MatchDataRec =
-            getDefOfSubClass(*Defs->getArg(I), "GIDefMatchData")) {
-      declareMatchData(Defs->getArgNameStr(I),
-                       MatchDataRec->getValueAsString("Type"),
-                       llvm::to_string(llvm::format("MatchData%" PRIu64, ID)));
-      continue;
-    }
-
-    // Otherwise emit an appropriate error message.
-    if (getDefOfSubClass(*Defs->getArg(I), "GIDefKind"))
-      PrintError(TheDef.getLoc(),
-                 "This GIDefKind not implemented in tablegen");
-    else if (getDefOfSubClass(*Defs->getArg(I), "GIDefKindWithArgs"))
-      PrintError(TheDef.getLoc(),
-                 "This GIDefKindWithArgs not implemented in tablegen");
-    else
-      PrintError(TheDef.getLoc(),
-                 "Expected a subclass of GIDefKind or a sub-dag whose "
-                 "operator is of type GIDefKindWithArgs");
-    return false;
-  }
-
-  if (Roots.empty()) {
-    PrintError(TheDef.getLoc(), "Combine rules must have at least one root");
-    return false;
-  }
-  return true;
-}
-
-// Parse an (Instruction $a:Arg1, $b:Arg2, ...) matcher. Edges are formed
-// between matching operand names between different matchers.
-bool CombineRule::parseInstructionMatcher(
-    const CodeGenTarget &Target, StringInit *ArgName, const Init &Arg,
-    StringMap<std::vector<VarInfo>> &NamedEdgeDefs,
-    StringMap<std::vector<VarInfo>> &NamedEdgeUses) {
-  if (const DagInit *Matcher =
-          getDagWithOperatorOfSubClass(Arg, "Instruction")) {
-    auto &Instr =
-        Target.getInstruction(Matcher->getOperatorAsDef(TheDef.getLoc()));
-
-    StringRef Name = ArgName ? ArgName->getValue() : "";
-
-    GIMatchDagInstr *N =
-        MatchDag.addInstrNode(makeDebugName(*this, Name), insertStrTab(Name),
-                              MatchDag.getContext().makeOperandList(Instr));
-
-    N->setOpcodeAnnotation(&Instr);
-    const auto &P = MatchDag.addPredicateNode<GIMatchDagOpcodePredicate>(
-        makeNameForAnonPredicate(*this), Instr);
-    MatchDag.addPredicateDependency(N, nullptr, P, &P->getOperandInfo()["mi"]);
-    unsigned OpIdx = 0;
-    for (const auto &NameInit : Matcher->getArgNames()) {
-      StringRef Name = insertStrTab(NameInit->getAsUnquotedString());
-      if (Name.empty())
-        continue;
-      N->assignNameToOperand(OpIdx, Name);
-
-      // Record the endpoints of any named edges. We'll add the cartesian
-      // product of edges later.
-      const auto &InstrOperand = N->getOperandInfo()[OpIdx];
-      if (InstrOperand.isDef()) {
-        NamedEdgeDefs.try_emplace(Name);
-        NamedEdgeDefs[Name].emplace_back(N, &InstrOperand, Matcher);
-      } else {
-        NamedEdgeUses.try_emplace(Name);
-        NamedEdgeUses[Name].emplace_back(N, &InstrOperand, Matcher);
-      }
-
-      if (InstrOperand.isDef()) {
-        if (any_of(Roots, [&](const RootInfo &X) {
-              return X.getPatternSymbol() == Name;
-            })) {
-          N->setMatchRoot();
-        }
-      }
-
-      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 (any_of(Roots, [&](const RootInfo &X) {
-          return ArgName && X.getPatternSymbol() == ArgName->getValue();
-        })) {
-      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) {
-  StringMap<std::vector<VarInfo>> NamedEdgeDefs;
-  StringMap<std::vector<VarInfo>> NamedEdgeUses;
-  DagInit *Matchers = TheDef.getValueAsDag("Match");
-
-  if (Matchers->getOperatorAsDef(TheDef.getLoc())->getName() != "match") {
-    PrintError(TheDef.getLoc(), "Expected match operator");
-    return false;
-  }
-
-  if (Matchers->getNumArgs() == 0) {
-    PrintError(TheDef.getLoc(), "Matcher is empty");
-    return false;
-  }
-
-  // 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 StringInit *StringI = dyn_cast<StringInit>(Matchers->getArg(I))) {
-      assert(!MatchingFixupCode &&
-             "Only one block of arbitrary code is currently permitted");
-      MatchingFixupCode = StringI;
-      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;
-  }
-
-  // Add the cartesian product of use -> def edges.
-  bool FailedToAddEdges = false;
-  for (const auto &NameAndDefs : NamedEdgeDefs) {
-    if (NameAndDefs.getValue().size() > 1) {
-      PrintError(TheDef.getLoc(),
-                 "Two different MachineInstrs cannot def the same vreg");
-      for (const auto &NameAndDefOp : NameAndDefs.getValue())
-        PrintNote("in " + to_string(*NameAndDefOp.N) + " created from " +
-                  to_string(*NameAndDefOp.Matcher) + "");
-      FailedToAddEdges = true;
-    }
-    const auto &Uses = NamedEdgeUses[NameAndDefs.getKey()];
-    for (const VarInfo &DefVar : NameAndDefs.getValue()) {
-      for (const VarInfo &UseVar : Uses) {
-        MatchDag.addEdge(insertStrTab(NameAndDefs.getKey()), UseVar.N, UseVar.Op,
-                         DefVar.N, DefVar.Op);
-      }
-    }
-  }
-  if (FailedToAddEdges)
-    return false;
-
-  // If a variable is referenced in multiple use contexts then we need a
-  // predicate to confirm they are the same operand. We can elide this if it's
-  // also referenced in a def context and we're traversing the def-use chain
-  // from the def to the uses but we can't know which direction we're going
-  // until after reorientToRoots().
-  for (const auto &NameAndUses : NamedEdgeUses) {
-    const auto &Uses = NameAndUses.getValue();
-    if (Uses.size() > 1) {
-      const auto &LeadingVar = Uses.front();
-      for (const auto &Var : ArrayRef<VarInfo>(Uses).drop_front()) {
-        // Add a predicate for each pair until we've covered the whole
-        // equivalence set. We could test the whole set in a single predicate
-        // but that means we can't test any equivalence until all the MO's are
-        // available which can lead to wasted work matching the DAG when this
-        // predicate can already be seen to have failed.
-        //
-        // We have a similar problem due to the need to wait for a particular MO
-        // before being able to test any of them. However, that is mitigated by
-        // the order in which we build the DAG. We build from the roots outwards
-        // so by using the first recorded use in all the predicates, we are
-        // making the dependency on one of the earliest visited references in
-        // the DAG. It's not guaranteed once the generated matcher is optimized
-        // (because the factoring the common portions of rules might change the
-        // visit order) but this should mean that these predicates depend on the
-        // first MO to become available.
-        const auto &P = MatchDag.addPredicateNode<GIMatchDagSameMOPredicate>(
-            makeNameForAnonPredicate(*this));
-        MatchDag.addPredicateDependency(LeadingVar.N, LeadingVar.Op, P,
-                                        &P->getOperandInfo()["mi0"]);
-        MatchDag.addPredicateDependency(Var.N, Var.Op, P,
-                                        &P->getOperandInfo()["mi1"]);
-      }
-    }
-  }
-  return true;
-}
-
-class GICombinerEmitter {
-  RecordKeeper &Records;
-  StringRef Name;
-  const CodeGenTarget &Target;
-  Record *Combiner;
-  std::vector<std::unique_ptr<CombineRule>> Rules;
-  GIMatchDagContext MatchDagCtx;
-
-  std::unique_ptr<CombineRule> makeCombineRule(const Record &R);
-
-  void gatherRules(std::vector<std::unique_ptr<CombineRule>> &ActiveRules,
-                   const std::vector<Record *> &&RulesAndGroups);
-
-public:
-  explicit GICombinerEmitter(RecordKeeper &RK, const CodeGenTarget &Target,
-                             StringRef Name, Record *Combiner);
-  ~GICombinerEmitter() {}
-
-  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 generateCodeForTree(raw_ostream &OS, const GIMatchTree &Tree,
-                           StringRef Indent) const;
-};
-
-GICombinerEmitter::GICombinerEmitter(RecordKeeper &RK,
-                                     const CodeGenTarget &Target,
-                                     StringRef Name, Record *Combiner)
-    : Records(RK), Name(Name), Target(Target), Combiner(Combiner) {}
-
-void GICombinerEmitter::emitNameMatcher(raw_ostream &OS) const {
-  std::vector<std::pair<std::string, std::string>> Cases;
-  Cases.reserve(Rules.size());
-
-  for (const CombineRule &EnumeratedRule : make_pointee_range(Rules)) {
-    std::string Code;
-    raw_string_ostream SS(Code);
-    SS << "return " << EnumeratedRule.getID() << ";\n";
-    Cases.push_back(
-        std::make_pair(std::string(EnumeratedRule.getName()), Code));
-  }
-
-  OS << "static std::optional<uint64_t> getRuleIdxForIdentifier(StringRef "
-        "RuleIdentifier) {\n"
-     << "  uint64_t I;\n"
-     << "  // getAtInteger(...) returns false on success\n"
-     << "  bool Parsed = !RuleIdentifier.getAsInteger(0, I);\n"
-     << "  if (Parsed)\n"
-     << "    return I;\n\n"
-     << "#ifndef NDEBUG\n";
-  StringMatcher Matcher("RuleIdentifier", Cases, OS);
-  Matcher.Emit();
-  OS << "#endif // ifndef NDEBUG\n\n"
-     << "  return std::nullopt;\n"
-     << "}\n";
-}
-
-std::unique_ptr<CombineRule>
-GICombinerEmitter::makeCombineRule(const Record &TheDef) {
-  std::unique_ptr<CombineRule> Rule =
-      std::make_unique<CombineRule>(Target, MatchDagCtx, NumPatternTotal, TheDef);
-
-  if (!Rule->parseDefs())
-    return nullptr;
-  if (!Rule->parseMatcher(Target))
-    return nullptr;
-
-  Rule->reorientToRoots();
-
-  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;
-}
-
-/// Recurse into GICombineGroup's and flatten the ruleset into a simple list.
-void GICombinerEmitter::gatherRules(
-    std::vector<std::unique_ptr<CombineRule>> &ActiveRules,
-    const std::vector<Record *> &&RulesAndGroups) {
-  for (Record *R : RulesAndGroups) {
-    if (R->isValueUnset("Rules")) {
-      std::unique_ptr<CombineRule> Rule = makeCombineRule(*R);
-      if (Rule == nullptr) {
-        PrintError(R->getLoc(), "Failed to parse rule");
-        continue;
-      }
-      ActiveRules.emplace_back(std::move(Rule));
-      ++NumPatternTotal;
-    } else
-      gatherRules(ActiveRules, R->getValueAsListOfDefs("Rules"));
-  }
-}
-
-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 (!RuleConfig->isRuleDisabled(" << Rule->getID()
-       << ")) {\n";
-
-    CodeExpansions Expansions;
-    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 in Apply DAG");
-      return;
-    }
-
-    OS << Indent << "  if (1\n";
-
-    // Emit code for C++ Predicates.
-    if (RuleDef.getValue("Predicates")) {
-      ListInit *Preds = RuleDef.getValueAsListInit("Predicates");
-      for (Init *I : Preds->getValues()) {
-        if (DefInit *Pred = dyn_cast<DefInit>(I)) {
-          Record *Def = Pred->getDef();
-          if (!Def->isSubClassOf("Predicate")) {
-            PrintError(Def->getLoc(), "Unknown 'Predicate' Type");
-            return;
-          }
-
-          StringRef CondString = Def->getValueAsString("CondString");
-          if (CondString.empty())
-            continue;
-
-          OS << Indent << "      && (\n"
-             << Indent << "           // Predicate: " << Def->getName() << "\n"
-             << Indent << "           " << CondString << "\n"
-             << Indent << "         )\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
-      // mechanism with the Combiner.
-      OS << Indent << "      && [&]() {\n"
-         << Indent << "      "
-         << CodeExpander(Rule->getMatchingFixupCode()->getValue(), Expansions,
-                         RuleDef.getLoc(), ShowExpansions)
-         << '\n'
-         << Indent << "      return true;\n"
-         << Indent << "  }()";
-    }
-    OS << Indent << "     ) {\n" << Indent << "   ";
-
-    if (const StringInit *Code = dyn_cast<StringInit>(Applyer->getArg(0))) {
-      OS << "    LLVM_DEBUG(dbgs() << \"Applying rule '"
-         << RuleDef.getName()
-         << "'\\n\");\n"
-         << CodeExpander(Code->getAsUnquotedString(), Expansions,
-                         RuleDef.getLoc(), ShowExpansions)
-         << '\n'
-         << 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";
-}
-
-static void emitAdditionalHelperMethodArguments(raw_ostream &OS,
-                                                Record *Combiner) {
-  for (Record *Arg : Combiner->getValueAsListOfDefs("AdditionalArguments"))
-    OS << ",\n    " << Arg->getValueAsString("Type")
-       << " " << Arg->getValueAsString("Name");
-}
-
-void GICombinerEmitter::run(raw_ostream &OS) {
-  Records.startTimer("Gather rules");
-  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;
-  Records.startTimer("Optimize combiner");
-  {
-    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;
-  }
-
-  Records.startTimer("Emit combiner");
-  OS << "#ifdef " << Name.upper() << "_GENCOMBINERHELPER_DEPS\n"
-     << "#include \"llvm/ADT/SparseBitVector.h\"\n"
-     << "namespace llvm {\n"
-     << "extern cl::OptionCategory GICombinerOptionCategory;\n"
-     << "} // end namespace llvm\n"
-     << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_DEPS\n\n";
-
-  OS << "#ifdef " << Name.upper() << "_GENCOMBINERHELPER_H\n"
-     << "class " << getClassName() << "RuleConfig {\n"
-     << "  SparseBitVector<> DisabledRules;\n"
-     << "\n"
-     << "public:\n"
-     << "  bool parseCommandLineOption();\n"
-     << "  bool isRuleDisabled(unsigned ID) const;\n"
-     << "  bool setRuleEnabled(StringRef RuleIdentifier);\n"
-     << "  bool setRuleDisabled(StringRef RuleIdentifier);\n"
-     << "};\n"
-     << "\n"
-     << "class " << getClassName();
-  StringRef StateClass = Combiner->getValueAsString("StateClass");
-  if (!StateClass.empty())
-    OS << " : public " << StateClass;
-  OS << " {\n"
-     << "  const " << getClassName() << "RuleConfig *RuleConfig;\n"
-     << "\n"
-     << "public:\n"
-     << "  template <typename... Args>" << getClassName() << "(const "
-     << getClassName() << "RuleConfig &RuleConfig, Args &&... args) : ";
-  if (!StateClass.empty())
-    OS << StateClass << "(std::forward<Args>(args)...), ";
-  OS << "RuleConfig(&RuleConfig) {}\n"
-     << "\n"
-     << "  bool tryCombineAll(\n"
-     << "    GISelChangeObserver &Observer,\n"
-     << "    MachineInstr &MI,\n"
-     << "    MachineIRBuilder &B";
-  emitAdditionalHelperMethodArguments(OS, Combiner);
-  OS << ") const;\n";
-  OS << "};\n\n";
-
-  emitNameMatcher(OS);
-
-  OS << "static std::optional<std::pair<uint64_t, uint64_t>> "
-        "getRuleRangeForIdentifier(StringRef RuleIdentifier) {\n"
-     << "  std::pair<StringRef, StringRef> RangePair = "
-        "RuleIdentifier.split('-');\n"
-     << "  if (!RangePair.second.empty()) {\n"
-     << "    const auto First = "
-        "getRuleIdxForIdentifier(RangePair.first);\n"
-     << "    const auto Last = "
-        "getRuleIdxForIdentifier(RangePair.second);\n"
-     << "    if (!First || !Last)\n"
-     << "      return std::nullopt;\n"
-     << "    if (First >= Last)\n"
-     << "      report_fatal_error(\"Beginning of range should be before "
-        "end of range\");\n"
-     << "    return {{*First, *Last + 1}};\n"
-     << "  }\n"
-     << "  if (RangePair.first == \"*\") {\n"
-     << "    return {{0, " << Rules.size() << "}};\n"
-     << "  }\n"
-     << "  const auto I = getRuleIdxForIdentifier(RangePair.first);\n"
-     << "  if (!I)\n"
-     << "    return std::nullopt;\n"
-     << "  return {{*I, *I + 1}};\n"
-     << "}\n\n";
-
-  for (bool Enabled : {true, false}) {
-    OS << "bool " << getClassName() << "RuleConfig::setRule"
-       << (Enabled ? "Enabled" : "Disabled") << "(StringRef RuleIdentifier) {\n"
-       << "  auto MaybeRange = getRuleRangeForIdentifier(RuleIdentifier);\n"
-       << "  if (!MaybeRange)\n"
-       << "    return false;\n"
-       << "  for (auto I = MaybeRange->first; I < MaybeRange->second; ++I)\n"
-       << "    DisabledRules." << (Enabled ? "reset" : "set") << "(I);\n"
-       << "  return true;\n"
-       << "}\n\n";
-  }
-
-  OS << "bool " << getClassName()
-     << "RuleConfig::isRuleDisabled(unsigned RuleID) const {\n"
-     << "  return DisabledRules.test(RuleID);\n"
-     << "}\n";
-  OS << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_H\n\n";
-
-  OS << "#ifdef " << Name.upper() << "_GENCOMBINERHELPER_CPP\n"
-     << "\n"
-     << "std::vector<std::string> " << Name << "Option;\n"
-     << "cl::list<std::string> " << Name << "DisableOption(\n"
-     << "    \"" << Name.lower() << "-disable-rule\",\n"
-     << "    cl::desc(\"Disable one or more combiner rules temporarily in "
-     << "the " << Name << " pass\"),\n"
-     << "    cl::CommaSeparated,\n"
-     << "    cl::Hidden,\n"
-     << "    cl::cat(GICombinerOptionCategory),\n"
-     << "    cl::callback([](const std::string &Str) {\n"
-     << "      " << Name << "Option.push_back(Str);\n"
-     << "    }));\n"
-     << "cl::list<std::string> " << Name << "OnlyEnableOption(\n"
-     << "    \"" << Name.lower() << "-only-enable-rule\",\n"
-     << "    cl::desc(\"Disable all rules in the " << Name
-     << " pass then re-enable the specified ones\"),\n"
-     << "    cl::Hidden,\n"
-     << "    cl::cat(GICombinerOptionCategory),\n"
-     << "    cl::callback([](const std::string &CommaSeparatedArg) {\n"
-     << "      StringRef Str = CommaSeparatedArg;\n"
-     << "      " << Name << "Option.push_back(\"*\");\n"
-     << "      do {\n"
-     << "        auto X = Str.split(\",\");\n"
-     << "        " << Name << "Option.push_back((\"!\" + X.first).str());\n"
-     << "        Str = X.second;\n"
-     << "      } while (!Str.empty());\n"
-     << "    }));\n"
-     << "\n"
-     << "bool " << getClassName() << "RuleConfig::parseCommandLineOption() {\n"
-     << "  for (StringRef Identifier : " << Name << "Option) {\n"
-     << "    bool Enabled = Identifier.consume_front(\"!\");\n"
-     << "    if (Enabled && !setRuleEnabled(Identifier))\n"
-     << "      return false;\n"
-     << "    if (!Enabled && !setRuleDisabled(Identifier))\n"
-     << "      return false;\n"
-     << "  }\n"
-     << "  return true;\n"
-     << "}\n\n";
-
-  OS << "bool " << getClassName() << "::tryCombineAll(\n"
-     << "    GISelChangeObserver &Observer,\n"
-     << "    MachineInstr &MI,\n"
-     << "    MachineIRBuilder &B";
-  emitAdditionalHelperMethodArguments(OS, Combiner);
-  OS << ") 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; (void)RuleConfig;\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";
-
-  OS << "  int Partition = -1;\n";
-  generateCodeForTree(OS, *Tree, "  ");
-  OS << "\n  return false;\n"
-     << "}\n"
-     << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_CPP\n";
-}
-
-} // end anonymous namespace
-
-//===----------------------------------------------------------------------===//
-
-static void EmitGICombiner(RecordKeeper &RK, raw_ostream &OS) {
-  PrintWarning(
-      "'-gen-global-isel-combiner' is deprecated and will be removed soon; "
-      "please use '-gen-global-isel-combiner-match-table' instead");
-  PrintNote(
-      "See "
-      "https://discourse.llvm.org/t/rfc-matchtable-based-globalisel-combiners");
-
-  CodeGenTarget Target(RK);
-  emitSourceFileHeader("Global Combiner", OS);
-
-  if (SelectedCombiners.empty())
-    PrintFatalError("No combiners selected with -combiners");
-  for (const auto &Combiner : SelectedCombiners) {
-    Record *CombinerDef = RK.getDef(Combiner);
-    if (!CombinerDef)
-      PrintFatalError("Could not find " + Combiner);
-    GICombinerEmitter(RK, Target, Combiner, CombinerDef).run(OS);
-  }
-  NumPatternTotalStatistic = NumPatternTotal;
-}
-
-static TableGen::Emitter::Opt X("gen-global-isel-combiner", EmitGICombiner,
-                                "Generate GlobalISel combiner");

llvm/utils/TableGen/GlobalISel/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
-  CodeGenTypes
   Support
   TableGen
   )
 
 add_llvm_library(LLVMTableGenGlobalISel STATIC DISABLE_LLVM_LINK_LLVM_DYLIB
   CodeExpander.cpp
-  GIMatchDag.cpp
-  GIMatchDagEdge.cpp
-  GIMatchDagInstr.cpp
-  GIMatchDagOperands.cpp
-  GIMatchDagPredicate.cpp
-  GIMatchDagPredicateDependencyEdge.cpp
-  GIMatchTree.cpp
 
   DEPENDS
   vt_gen
   )
 
 # Users may include its headers as "GlobalISel/*.h"
 target_include_directories(LLVMTableGenGlobalISel
   INTERFACE
   $<BUILD_INTERFACE:${CMAKE_CURRENT_SOURCE_DIR}/..>
   )

llvm/utils/TableGen/GlobalISel/GIMatchDag.h

-//===- GIMatchDag.h - Represent a DAG to be matched -------------*- C++ -*-===//
-//
-// 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_GIMATCHDAG_H
-#define LLVM_UTILS_TABLEGEN_GIMATCHDAG_H
-
-#include "GIMatchDagEdge.h"
-#include "GIMatchDagInstr.h"
-#include "GIMatchDagOperands.h"
-#include "GIMatchDagPredicate.h"
-#include "GIMatchDagPredicateDependencyEdge.h"
-
-namespace llvm {
-
-/// This class manages lifetimes for data associated with the GIMatchDag object.
-class GIMatchDagContext {
-  GIMatchDagOperandListContext OperandListCtx;
-
-public:
-  const GIMatchDagOperandList &makeEmptyOperandList() {
-    return OperandListCtx.makeEmptyOperandList();
-  }
-
-  const GIMatchDagOperandList &makeOperandList(const CodeGenInstruction &I) {
-    return OperandListCtx.makeOperandList(I);
-  }
-
-  const GIMatchDagOperandList &makeMIPredicateOperandList() {
-    return OperandListCtx.makeMIPredicateOperandList();
-  }
-
-
-  const GIMatchDagOperandList &makeTwoMOPredicateOperandList() {
-    return OperandListCtx.makeTwoMOPredicateOperandList();
-  }
-
-  void print(raw_ostream &OS) const {
-    OperandListCtx.print(OS);
-  }
-
-#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) {}
-  GIMatchDag(const GIMatchDag &) = delete;
-
-  GIMatchDagContext &getContext() const { return Ctx; }
-  edge_iterator edges_begin() {
-    return raw_pointer_iterator<EdgesVec::iterator>(Edges.begin());
-  }
-  edge_iterator edges_end() {
-    return raw_pointer_iterator<EdgesVec::iterator>(Edges.end());
-  }
-  const_edge_iterator edges_begin() const {
-    return raw_pointer_iterator<EdgesVec::const_iterator>(Edges.begin());
-  }
-  const_edge_iterator edges_end() const {
-    return raw_pointer_iterator<EdgesVec::const_iterator>(Edges.end());
-  }
-  iterator_range<edge_iterator> edges() {
-    return make_range(edges_begin(), edges_end());
-  }
-  iterator_range<const_edge_iterator> edges() const {
-    return make_range(edges_begin(), edges_end());
-  }
-  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;
-  }
-
-  template <class T, class... Args>
-  T *addPredicateNode(Args &&... args) {
-    auto Obj = std::make_unique<T>(getContext(), std::forward<Args>(args)...);
-    auto ObjRaw = Obj.get();
-    PredicateNodes.push_back(std::move(Obj));
-    return ObjRaw;
-  }
-
-  template <class... Args> GIMatchDagEdge *addEdge(Args &&... args) {
-    auto Obj = std::make_unique<GIMatchDagEdge>(std::forward<Args>(args)...);
-    auto ObjRaw = Obj.get();
-    Edges.push_back(std::move(Obj));
-    return ObjRaw;
-  }
-
-  template <class... Args>
-  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/GIMatchDag.cpp

-//===- GIMatchDag.cpp - A DAG representation of a pattern to be matched ---===//
-//
-// 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 "GIMatchDag.h"
-
-#include "llvm/Support/Format.h"
-#include "llvm/TableGen/Record.h"
-#include "../CodeGenInstruction.h"
-
-using namespace llvm;
-
-void GIMatchDag::writeDOTGraph(raw_ostream &OS, StringRef ID) const {
-  const auto writePorts = [&](StringRef Prefix,
-                              const GIMatchDagOperandList &Operands) {
-    StringRef Separator = "";
-    OS << "{";
-    for (const auto &Op : enumerate(Operands)) {
-      OS << Separator << "<" << Prefix << format("%d", Op.index()) << ">"
-         << "#" << Op.index() << " $" << Op.value().getName();
-      Separator = "|";
-    }
-    OS << "}";
-  };
-
-  OS << "digraph \"" << ID << "\" {\n"
-     << "  rankdir=\"BT\"\n";
-  for (const auto &N : InstrNodes) {
-    OS << "  " << format("Node%p", &*N) << " [shape=record,label=\"{";
-    writePorts("s", N->getOperandInfo());
-    OS << "|" << N->getName();
-    if (N->getOpcodeAnnotation())
-      OS << "|" << N->getOpcodeAnnotation()->TheDef->getName();
-    if (N->isMatchRoot())
-      OS << "|Match starts here";
-    OS << "|";
-    SmallVector<std::pair<unsigned, StringRef>, 8> ToPrint;
-    for (const auto &Assignment : N->user_assigned_operand_names())
-      ToPrint.emplace_back(Assignment.first, Assignment.second);
-    llvm::sort(ToPrint);
-    StringRef Separator = "";
-    for (const auto &Assignment : ToPrint) {
-      OS << Separator << "$" << Assignment.second << "=getOperand("
-         << Assignment.first << ")";
-      Separator = ", ";
-    }
-    OS << llvm::format("|%p|", &N);
-    writePorts("d", N->getOperandInfo());
-    OS << "}\"";
-    if (N->isMatchRoot())
-      OS << ",color=red";
-    OS << "]\n";
-  }
-
-  for (const auto &E : Edges) {
-    const char *FromFmt = "Node%p:s%d:n";
-    const char *ToFmt = "Node%p:d%d:s";
-    if (E->getFromMO()->isDef() && !E->getToMO()->isDef())
-      std::swap(FromFmt, ToFmt);
-    auto From = format(FromFmt, E->getFromMI(), E->getFromMO()->getIdx());
-    auto To = format(ToFmt, E->getToMI(), E->getToMO()->getIdx());
-    if (E->getFromMO()->isDef() && !E->getToMO()->isDef())
-      std::swap(From, To);
-
-    OS << "  " << From << " -> " << To << " [label=\"$" << E->getName();
-    if (E->getFromMO()->isDef() == E->getToMO()->isDef())
-      OS << " INVALID EDGE!";
-    OS << "\"";
-    if (E->getFromMO()->isDef() == E->getToMO()->isDef())
-      OS << ",color=red";
-    else if (E->getFromMO()->isDef() && !E->getToMO()->isDef())
-      OS << ",dir=back,arrowtail=crow";
-    OS << "]\n";
-  }
-
-  for (const auto &N : PredicateNodes) {
-    OS << "  " << format("Pred%p", &*N) << " [shape=record,label=\"{";
-    writePorts("s", N->getOperandInfo());
-    OS << "|" << N->getName() << "|";
-    N->printDescription(OS);
-    OS << llvm::format("|%p|", &N);
-    writePorts("d", N->getOperandInfo());
-    OS << "}\",style=dotted]\n";
-  }
-
-  for (const auto &E : PredicateDependencies) {
-    const char *FromMIFmt = "Node%p:e";
-    const char *FromMOFmt = "Node%p:s%d:n";
-    const char *ToFmt = "Pred%p:d%d:s";
-    auto To = format(ToFmt, E->getPredicate(), E->getPredicateOp()->getIdx());
-    auto Style = "[style=dotted]";
-    if (E->getRequiredMO()) {
-      auto From =
-          format(FromMOFmt, E->getRequiredMI(), E->getRequiredMO()->getIdx());
-      OS << "  " << From << " -> " << To << " " << Style << "\n";
-      continue;
-    }
-    auto From = format(FromMIFmt, E->getRequiredMI());
-    OS << "  " << From << " -> " << To << " " << Style << "\n";
-  }
-
-  OS << "}\n";
-}
-
-LLVM_DUMP_METHOD void GIMatchDag::print(raw_ostream &OS) const {
-  OS << "matchdag {\n";
-  for (const auto &N : InstrNodes) {
-    OS << "  ";
-    N->print(OS);
-    OS << "\n";
-  }
-  for (const auto &E : Edges) {
-    OS << "  ";
-    E->print(OS);
-    OS << "\n";
-  }
-
-  for (const auto &P : PredicateNodes) {
-    OS << "  ";
-    P->print(OS);
-    OS << "\n";
-  }
-  for (const auto &D : PredicateDependencies) {
-    OS << "  ";
-    D->print(OS);
-    OS << "\n";
-  }
-  OS << "}\n";
-}
-
-raw_ostream &llvm::operator<<(raw_ostream &OS, const GIMatchDag &G) {
-  G.print(OS);
-  return OS;
-}

llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.h

-//===- GIMatchDagEdge.h - Represent node shared operand lists ---*- C++ -*-===//
-//
-// 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_GIMATCHDAGEDGE_H
-#define LLVM_UTILS_TABLEGEN_GIMATCHDAGEDGE_H
-
-#include "llvm/ADT/StringRef.h"
-
-namespace llvm {
-class raw_ostream;
-class GIMatchDagInstr;
-class GIMatchDagOperand;
-
-/// Represents an edge that connects two instructions together via a pair of
-/// operands. For example:
-///     %a = FOO ...
-///     %0 = BAR %a
-///     %1 = BAZ %a
-/// would have two edges for %a like so:
-///     BAR:Op#1 --[a]----> Op#0:FOO
-///                         ^
-///     BAZ:Op#1 --[a]------/
-/// Ideally, all edges in the DAG are from a use to a def as this is a many
-/// to one edge but edges from defs to uses are supported too.
-class GIMatchDagEdge {
-  /// The name of the edge. For example,
-  ///     (FOO $a, $b, $c)
-  ///     (BAR $d, $e, $a)
-  /// will create an edge named 'a' to connect FOO to BAR. Although the name
-  /// refers to the edge, the canonical value of 'a' is the operand that defines
-  /// it.
-  StringRef Name;
-  const GIMatchDagInstr *FromMI;
-  const GIMatchDagOperand *FromMO;
-  const GIMatchDagInstr *ToMI;
-  const GIMatchDagOperand *ToMO;
-
-public:
-  GIMatchDagEdge(StringRef Name, const GIMatchDagInstr *FromMI, const GIMatchDagOperand *FromMO,
-            const GIMatchDagInstr *ToMI, const GIMatchDagOperand *ToMO)
-      : Name(Name), FromMI(FromMI), FromMO(FromMO), ToMI(ToMI), ToMO(ToMO) {}
-
-  StringRef getName() const { return Name; }
-  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

-//===- GIMatchDagEdge.cpp - An edge describing a def/use lookup -----------===//
-//
-// 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 "GIMatchDagEdge.h"
-#include "GIMatchDagInstr.h"
-#include "GIMatchDagOperands.h"
-#include "llvm/Support/raw_ostream.h"
-
-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

-//===- GIMatchDagInstr.h - Represent instruction to be matched --*- C++ -*-===//
-//
-// 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_GIMATCHDAGINSTR_H
-#define LLVM_UTILS_TABLEGEN_GIMATCHDAGINSTR_H
-
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/StringRef.h"
-#include "llvm/Support/raw_ostream.h"
-
-namespace llvm {
-class CodeGenInstruction;
-class GIMatchDag;
-class GIMatchDagOperandList;
-
-/// Represents an instruction in the match DAG. This object knows very little
-/// about the actual instruction to be matched as the bulk of that is in
-/// predicates that are associated with the match DAG. It merely knows the names
-/// and indices of any operands that need to be matched in order to allow edges
-/// to link to them.
-///
-/// Instances of this class objects are owned by the GIMatchDag and are not
-/// shareable between instances of GIMatchDag. This is because the Name,
-/// IsMatchRoot, and OpcodeAnnotation are likely to differ between GIMatchDag
-/// instances.
-class GIMatchDagInstr {
-public:
-  using const_user_assigned_operand_names_iterator =
-      DenseMap<unsigned, StringRef>::const_iterator;
-
-protected:
-  /// The match DAG this instruction belongs to.
-  GIMatchDag &Dag;
-
-  /// The name of the instruction in the pattern. For example:
-  ///     (FOO $a, $b, $c):$name
-  /// will cause name to be assigned to this member. Anonymous instructions will
-  /// have a name assigned for debugging purposes.
-  StringRef Name;
-
-  /// The name of the instruction in the pattern as assigned by the user. For
-  /// example:
-  ///     (FOO $a, $b, $c):$name
-  /// will cause name to be assigned to this member. If a name is not provided,
-  /// this will be empty. This name is used to bind variables from rules to the
-  /// matched instruction.
-  StringRef UserAssignedName;
-
-  /// The name of each operand (if any) that was assigned by the user. For
-  /// example:
-  ///     (FOO $a, $b, $c):$name
-  /// will cause {0, "a"}, {1, "b"}, {2, "c} to be inserted into this map.
-  DenseMap<unsigned, StringRef> UserAssignedNamesForOperands;
-
-  /// The operand list for this instruction. This object may be shared with
-  /// other instructions of a similar 'shape'.
-  const GIMatchDagOperandList &OperandInfo;
-
-  /// For debugging purposes, it's helpful to have access to a description of
-  /// the Opcode. However, this object shouldn't use it for more than debugging
-  /// output since predicates are expected to be handled outside the DAG.
-  CodeGenInstruction *OpcodeAnnotation = nullptr;
-
-  /// When true, this instruction will be a starting point for a match attempt.
-  bool IsMatchRoot = false;
-
-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();
-  }
-  const_user_assigned_operand_names_iterator
-  user_assigned_operand_names_end() const {
-    return UserAssignedNamesForOperands.end();
-  }
-  iterator_range<const_user_assigned_operand_names_iterator>
-  user_assigned_operand_names() const {
-    return make_range(user_assigned_operand_names_begin(),
-                      user_assigned_operand_names_end());
-  }
-
-  /// Mark this instruction as being a root of the match. This means that the
-  /// matcher will start from this node when attempting to match MIR.
-  void setMatchRoot();
-  bool isMatchRoot() const { return IsMatchRoot; }
-
-  void setOpcodeAnnotation(CodeGenInstruction *I) { OpcodeAnnotation = I; }
-  CodeGenInstruction *getOpcodeAnnotation() const { return OpcodeAnnotation; }
-
-  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)
-};
-
-raw_ostream &operator<<(raw_ostream &OS, const GIMatchDagInstr &N);
-
-} // end namespace llvm
-#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGINSTR_H

llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.cpp

-//===- GIMatchDagInstr.cpp - A shared operand list for nodes --------------===//
-//
-// 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 "GIMatchDagInstr.h"
-#include "../CodeGenInstruction.h"
-#include "GIMatchDag.h"
-#include "llvm/TableGen/Record.h"
-
-using namespace llvm;
-
-void GIMatchDagInstr::print(raw_ostream &OS) const {
-  OS << "(";
-  if (const auto *Annotation = getOpcodeAnnotation())
-    OS << Annotation->TheDef->getName();
-  else
-    OS << "<unknown>";
-  OS << " ";
-  OperandInfo.print(OS);
-  OS << "):$" << Name;
-  if (!UserAssignedNamesForOperands.empty()) {
-    OS << " // ";
-    SmallVector<std::pair<unsigned, StringRef>, 8> ToPrint;
-    for (const auto &Assignment : UserAssignedNamesForOperands)
-      ToPrint.emplace_back(Assignment.first, Assignment.second);
-    llvm::sort(ToPrint);
-    StringRef Separator = "";
-    for (const auto &Assignment : ToPrint) {
-      OS << Separator << "$" << Assignment.second << "=getOperand("
-         << Assignment.first << ")";
-      Separator = ", ";
-    }
-  }
-}
-
-void GIMatchDagInstr::setMatchRoot() {
-  IsMatchRoot = true;
-  Dag.addMatchRoot(this);
-}
-
-raw_ostream &llvm::operator<<(raw_ostream &OS, const GIMatchDagInstr &N) {
-  N.print(OS);
-  return OS;
-}

llvm/utils/TableGen/GlobalISel/GIMatchDagOperands.h

-//===- GIMatchDagOperands.h - Represent operand lists for nodes -*- C++ -*-===//
-//
-// 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_GIMATCHDAGOPERANDS_H
-#define LLVM_UTILS_TABLEGEN_GIMATCHDAGOPERANDS_H
-
-#include "llvm/ADT/FoldingSet.h"
-#include "llvm/ADT/StringMap.h"
-#include "llvm/ADT/StringRef.h"
-#include "llvm/Support/raw_ostream.h"
-
-#include <vector>
-
-namespace llvm {
-class CodeGenInstruction;
-/// Describes an operand of a MachineInstr w.r.t the DAG Matching. This
-/// information is derived from CodeGenInstruction::Operands but is more
-/// readily available for context-less access as we don't need to know which
-/// instruction it's used with or know how many defs that instruction had.
-///
-/// There may be multiple GIMatchDagOperand's with the same contents. However,
-/// they are uniqued within the set of instructions that have the same overall
-/// operand list. For example, given:
-///     Inst1 operands ($dst:<def>, $src1, $src2)
-///     Inst2 operands ($dst:<def>, $src1, $src2)
-///     Inst3 operands ($dst:<def>, $src)
-/// $src1 will have a single instance of GIMatchDagOperand shared by Inst1 and
-/// Inst2, as will $src2. $dst however, will have two instances one shared
-/// between Inst1 and Inst2 and one unique to Inst3. We could potentially
-/// fully de-dupe the GIMatchDagOperand instances but the saving is not expected
-/// to be worth the overhead.
-///
-/// The result of this is that the address of the object can be relied upon to
-/// trivially identify commonality between two instructions which will be useful
-/// when generating the matcher. When the pointers differ, the contents can be
-/// inspected instead.
-class GIMatchDagOperand {
-  unsigned Idx;
-  StringRef Name;
-  bool IsDef;
-
-public:
-  GIMatchDagOperand(unsigned Idx, StringRef Name, bool IsDef)
-      : Idx(Idx), Name(Name), IsDef(IsDef) {}
-
-  unsigned getIdx() const { return Idx; }
-  StringRef getName() const { return Name; }
-  bool isDef() const { return IsDef; }
-
-  /// This object isn't a FoldingSetNode but it's part of one. See FoldingSet
-  /// for details on the Profile function.
-  void Profile(FoldingSetNodeID &ID) const;
-
-  /// A helper that behaves like Profile() but is also usable without the object.
-  /// We use size_t here to match enumerate<...>::index(). If we don't match
-  /// that the hashes won't be equal.
-  static void Profile(FoldingSetNodeID &ID, size_t Idx, StringRef Name,
-                      bool IsDef);
-};
-
-/// A list of GIMatchDagOperands for an instruction without any association with
-/// a particular instruction.
-///
-/// An important detail to be aware of with this class is that they are shared
-/// with other instructions of a similar 'shape'. For example, all the binary
-/// instructions are likely to share a single GIMatchDagOperandList. This is
-/// primarily a memory optimization as it's fairly common to have a large number
-/// of instructions but only a few 'shapes'.
-///
-/// See GIMatchDagOperandList::Profile() for the details on how they are folded.
-class GIMatchDagOperandList : public FoldingSetNode {
-public:
-  using value_type = GIMatchDagOperand;
-
-protected:
-  using vector_type = SmallVector<GIMatchDagOperand, 3>;
-
-public:
-  using iterator = vector_type::iterator;
-  using const_iterator = vector_type::const_iterator;
-
-protected:
-  vector_type Operands;
-  StringMap<unsigned> OperandsByName;
-
-public:
-  void add(StringRef Name, unsigned Idx, bool IsDef);
-
-  /// See FoldingSet for details.
-  void Profile(FoldingSetNodeID &ID) const;
-
-  iterator begin() { return Operands.begin(); }
-  const_iterator begin() const { return Operands.begin(); }
-  iterator end() { return Operands.end(); }
-  const_iterator end() const { return Operands.end(); }
-
-  const value_type &operator[](unsigned I) const { return Operands[I]; }
-  const value_type &operator[](StringRef K) const;
-
-  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)
-};
-
-/// This is the portion of GIMatchDagContext that directly relates to
-/// GIMatchDagOperandList and GIMatchDagOperandList.
-class GIMatchDagOperandListContext {
-  FoldingSet<GIMatchDagOperandList> OperandLists;
-  std::vector<std::unique_ptr<GIMatchDagOperandList>> OperandListsOwner;
-
-public:
-  const GIMatchDagOperandList &makeEmptyOperandList();
-  const GIMatchDagOperandList &makeOperandList(const CodeGenInstruction &I);
-  const GIMatchDagOperandList &makeMIPredicateOperandList();
-  const GIMatchDagOperandList &makeTwoMOPredicateOperandList();
-
-  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)
-};
-
-} // end namespace llvm
-#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGOPERANDS_H

llvm/utils/TableGen/GlobalISel/GIMatchDagOperands.cpp

-//===- GIMatchDagOperands.cpp - A shared operand list for nodes -----------===//
-//
-// 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 "GIMatchDagOperands.h"
-
-#include "../CodeGenInstruction.h"
-
-using namespace llvm;
-
-void GIMatchDagOperand::Profile(FoldingSetNodeID &ID) const {
-  Profile(ID, Idx, Name, IsDef);
-}
-
-void GIMatchDagOperand::Profile(FoldingSetNodeID &ID, size_t Idx,
-                                       StringRef Name, bool IsDef) {
-  ID.AddInteger(Idx);
-  ID.AddString(Name);
-  ID.AddBoolean(IsDef);
-}
-
-void GIMatchDagOperandList::add(StringRef Name, unsigned Idx, bool IsDef) {
-  assert(Idx == Operands.size() && "Operands added in wrong order");
-  Operands.emplace_back(Operands.size(), Name, IsDef);
-  OperandsByName.try_emplace(Operands.back().getName(), Operands.size() - 1);
-}
-
-void GIMatchDagOperandList::Profile(FoldingSetNodeID &ID) const {
-  for (const auto &I : enumerate(Operands))
-    GIMatchDagOperand::Profile(ID, I.index(), I.value().getName(),
-                               I.value().isDef());
-}
-
-void GIMatchDagOperandList::print(raw_ostream &OS) const {
-  if (Operands.empty()) {
-    OS << "<empty>";
-    return;
-  }
-  StringRef Separator = "";
-  for (const auto &I : Operands) {
-    OS << Separator << I.getIdx() << ":" << I.getName();
-    if (I.isDef())
-      OS << "<def>";
-    Separator = ", ";
-  }
-}
-
-const GIMatchDagOperandList::value_type &GIMatchDagOperandList::
-operator[](StringRef K) const {
-  const auto &I = OperandsByName.find(K);
-  assert(I != OperandsByName.end() && "Operand not found by name");
-  return Operands[I->second];
-}
-
-const GIMatchDagOperandList &
-GIMatchDagOperandListContext::makeEmptyOperandList() {
-  FoldingSetNodeID ID;
-
-  void *InsertPoint;
-  GIMatchDagOperandList *Value =
-      OperandLists.FindNodeOrInsertPos(ID, InsertPoint);
-  if (Value)
-    return *Value;
-
-  std::unique_ptr<GIMatchDagOperandList> NewValue =
-      std::make_unique<GIMatchDagOperandList>();
-  OperandLists.InsertNode(NewValue.get(), InsertPoint);
-  OperandListsOwner.push_back(std::move(NewValue));
-  return *OperandListsOwner.back().get();
-}
-
-const GIMatchDagOperandList &
-GIMatchDagOperandListContext::makeOperandList(const CodeGenInstruction &I) {
-  FoldingSetNodeID ID;
-  for (unsigned i = 0; i < I.Operands.size(); ++i)
-    GIMatchDagOperand::Profile(ID, i, I.Operands[i].Name,
-                               i < I.Operands.NumDefs);
-
-  void *InsertPoint;
-  GIMatchDagOperandList *Value =
-      OperandLists.FindNodeOrInsertPos(ID, InsertPoint);
-  if (Value)
-    return *Value;
-
-  std::unique_ptr<GIMatchDagOperandList> NewValue =
-      std::make_unique<GIMatchDagOperandList>();
-  for (unsigned i = 0; i < I.Operands.size(); ++i)
-    NewValue->add(I.Operands[i].Name, i, i < I.Operands.NumDefs);
-  OperandLists.InsertNode(NewValue.get(), InsertPoint);
-  OperandListsOwner.push_back(std::move(NewValue));
-  return *OperandListsOwner.back().get();
-}
-
-const GIMatchDagOperandList &
-GIMatchDagOperandListContext::makeMIPredicateOperandList() {
-  FoldingSetNodeID ID;
-  GIMatchDagOperand::Profile(ID, 0, "$", true);
-  GIMatchDagOperand::Profile(ID, 1, "mi", false);
-
-  void *InsertPoint;
-  GIMatchDagOperandList *Value =
-      OperandLists.FindNodeOrInsertPos(ID, InsertPoint);
-  if (Value)
-    return *Value;
-
-  std::unique_ptr<GIMatchDagOperandList> NewValue =
-      std::make_unique<GIMatchDagOperandList>();
-  NewValue->add("$", 0, true);
-  NewValue->add("mi", 1, false);
-  OperandLists.InsertNode(NewValue.get(), InsertPoint);
-  OperandListsOwner.push_back(std::move(NewValue));
-  return *OperandListsOwner.back().get();
-}
-
-
-const GIMatchDagOperandList &
-GIMatchDagOperandListContext::makeTwoMOPredicateOperandList() {
-  FoldingSetNodeID ID;
-  GIMatchDagOperand::Profile(ID, 0, "$", true);
-  GIMatchDagOperand::Profile(ID, 1, "mi0", false);
-  GIMatchDagOperand::Profile(ID, 2, "mi1", false);
-
-  void *InsertPoint;
-  GIMatchDagOperandList *Value =
-      OperandLists.FindNodeOrInsertPos(ID, InsertPoint);
-  if (Value)
-    return *Value;
-
-  std::unique_ptr<GIMatchDagOperandList> NewValue =
-      std::make_unique<GIMatchDagOperandList>();
-  NewValue->add("$", 0, true);
-  NewValue->add("mi0", 1, false);
-  NewValue->add("mi1", 2, false);
-  OperandLists.InsertNode(NewValue.get(), InsertPoint);
-  OperandListsOwner.push_back(std::move(NewValue));
-  return *OperandListsOwner.back().get();
-}
-
-void GIMatchDagOperandListContext::print(raw_ostream &OS) const {
-  OS << "GIMatchDagOperandListContext {\n"
-     << "  OperandLists {\n";
-  for (const auto &I : OperandListsOwner) {
-    OS << "    ";
-    I->print(OS);
-    OS << "\n";
-  }
-  OS << "  }\n"
-     << "}\n";
-}

llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.h

-//===- GIMatchDagPredicate - Represent a predicate to check -----*- C++ -*-===//
-//
-// 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/SmallVector.h"
-#include "llvm/ADT/StringRef.h"
-
-#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-#include "llvm/Support/raw_ostream.h"
-#endif
-
-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)
-  /// will cause 's32' to be assigned to this member for the $a predicate.
-  /// Similarly, the opcode predicate will cause 'FOO' to be assigned to this
-  /// member. Anonymous instructions will have a name assigned for debugging
-  /// purposes.
-  StringRef Name;
-
-  /// The operand list for this predicate. This object may be shared with
-  /// other predicates of a similar 'shape'.
-  const GIMatchDagOperandList &OperandInfo;
-
-public:
-  GIMatchDagPredicate(GIMatchDagPredicateKind Kind, StringRef Name,
-                      const GIMatchDagOperandList &OperandInfo)
-      : 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)
-};
-
-class GIMatchDagOpcodePredicate : public GIMatchDagPredicate {
-  const CodeGenInstruction &Instr;
-
-public:
-  GIMatchDagOpcodePredicate(GIMatchDagContext &Ctx, StringRef Name,
-                            const CodeGenInstruction &Instr);
-
-  static bool classof(const GIMatchDagPredicate *P) {
-    return P->getKind() == GIMatchDagPredicateKind_Opcode;
-  }
-
-  const CodeGenInstruction *getInstr() const { return &Instr; }
-
-  void printDescription(raw_ostream &OS) const override;
-
-#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-  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)
-  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;
-  }
-
-  void printDescription(raw_ostream &OS) const override;
-
-#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-  LLVM_DUMP_METHOD void dump() const override { print(errs()); }
-#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-};
-
-raw_ostream &operator<<(raw_ostream &OS, const GIMatchDagPredicate &N);
-raw_ostream &operator<<(raw_ostream &OS, const GIMatchDagOpcodePredicate &N);
-
-} // end namespace llvm
-#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATE_H

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 "../CodeGenInstruction.h"
-#include "GIMatchDag.h"
-
-using namespace llvm;
-
-void GIMatchDagPredicate::print(raw_ostream &OS) const {
-  OS << "<<";
-  printDescription(OS);
-  OS << ">>:$" << Name;
-}
-
-void GIMatchDagPredicate::printDescription(raw_ostream &OS) const { OS << ""; }
-
-GIMatchDagOpcodePredicate::GIMatchDagOpcodePredicate(
-    GIMatchDagContext &Ctx, StringRef Name, const CodeGenInstruction &Instr)
-    : 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";
-}
-
-raw_ostream &llvm::operator<<(raw_ostream &OS, const GIMatchDagPredicate &N) {
-  N.print(OS);
-  return OS;
-}
-
-raw_ostream &llvm::operator<<(raw_ostream &OS,
-                              const GIMatchDagOpcodePredicate &N) {
-  N.print(OS);
-  return OS;
-}

llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.h

-//===- GIMatchDagPredicateDependencyEdge - Ensure predicates have inputs --===//
-//
-// 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_GIMATCHDAGPREDICATEEDGE_H
-#define LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATEEDGE_H
-
-#include "llvm/Support/Compiler.h"
-
-namespace llvm {
-class GIMatchDagInstr;
-class GIMatchDagPredicate;
-class GIMatchDagOperand;
-
-class raw_ostream;
-
-/// Represents a dependency that must be met to evaluate a predicate.
-///
-/// Instances of this class objects are owned by the GIMatchDag and are not
-/// shareable between instances of GIMatchDag.
-class GIMatchDagPredicateDependencyEdge {
-  /// The MI that must be available in order to test the predicate.
-  const GIMatchDagInstr *RequiredMI;
-  /// The MO that must be available in order to test the predicate. May be
-  /// nullptr when only the MI is required.
-  const GIMatchDagOperand *RequiredMO;
-  /// The Predicate that requires information from RequiredMI/RequiredMO.
-  const GIMatchDagPredicate *Predicate;
-  /// The Predicate operand that requires information from
-  /// RequiredMI/RequiredMO.
-  const GIMatchDagOperand *PredicateOp;
-
-public:
-  GIMatchDagPredicateDependencyEdge(const GIMatchDagInstr *RequiredMI,
-                                    const GIMatchDagOperand *RequiredMO,
-                                    const GIMatchDagPredicate *Predicate,
-                                    const GIMatchDagOperand *PredicateOp)
-      : RequiredMI(RequiredMI), RequiredMO(RequiredMO), Predicate(Predicate),
-        PredicateOp(PredicateOp) {}
-
-  const GIMatchDagInstr *getRequiredMI() const { return RequiredMI; }
-  const GIMatchDagOperand *getRequiredMO() const { return RequiredMO; }
-  const GIMatchDagPredicate *getPredicate() const { return Predicate; }
-  const GIMatchDagOperand *getPredicateOp() const { return PredicateOp; }
-
-  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 GIMatchDagPredicateDependencyEdge &N);
-
-} // end namespace llvm
-#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATEEDGE_H

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 "GIMatchDagOperands.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() << "["
-     << getPredicateOp()->getName() << "]";
-}
-
-#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-LLVM_DUMP_METHOD void GIMatchDagPredicateDependencyEdge::dump() const {
-  print(errs());
-}
-#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-
-raw_ostream &llvm::operator<<(raw_ostream &OS,
-                              const GIMatchDagPredicateDependencyEdge &E) {
-  E.print(OS);
-  return OS;
-}

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.
-  std::optional<unsigned> OpIdx;
-
-public:
-  GIMatchTreeVariableBinding(StringRef Name, unsigned InstrID,
-                             std::optional<unsigned> OpIdx = std::nullopt)
-      : Name(Name), InstrID(InstrID), OpIdx(OpIdx) {}
-
-  bool isInstr() const { return !OpIdx; }
-  StringRef getName() const { return Name; }
-  unsigned getInstrID() const { return InstrID; }
-  unsigned getOpIdx() const {
-    assert(OpIdx && "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 {
-    return InstrIDToInfo.lookup(ID);
-  }
-
-  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 = nullptr;
-  /// 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;
-  BitVector 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 "GIMatchDagPredicate.h"
-
-#include "../CodeGenInstruction.h"
-
-#include "llvm/Support/Debug.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),
-      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 (const auto &[Idx, P] : enumerate(MatchDag.predicates())) {
-    PredicateIDs.insert(std::make_pair(P, Idx));
-  }
-
-  // Number all the predicate dependencies in this DAG and set up a bitvector
-  // for each predicate indicating the unsatisfied dependencies.
-  for (const auto &[Idx, Dep] : enumerate(MatchDag.predicate_edges())) {
-    PredicateDepIDs.insert(std::make_pair(Dep, Idx));
-  }
-  UnsatisfiedPredDepsForPred.resize(MatchDag.getNumPredicates(),
-                                    BitVector(PredicateDepIDs.size()));
-  for (const auto &[Idx, Dep] : enumerate(MatchDag.predicate_edges())) {
-    unsigned ID = PredicateIDs.lookup(Dep->getPredicate());
-    UnsatisfiedPredDepsForPred[ID].set(Idx);
-  }
-}
-
-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 = find(MatchDag.instr_nodes(), 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 (const auto &Dep : enumerate(MatchDag.predicate_edges())) {
-    if (Dep.value()->getRequiredMI() == Instr &&
-        Dep.value()->getRequiredMO() == nullptr) {
-      for (const 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 (const auto &[Idx, E] : enumerate(MatchDag.edges())) {
-    if (E->getFromMI() == Instr && E->getFromMO()->getIdx() == OpIdx) {
-      TraversableEdges.set(Idx);
-    }
-  }
-
-  // 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 (const auto &Dep : enumerate(MatchDag.predicate_edges())) {
-    if (Dep.value()->getRequiredMI() == Instr && Dep.value()->getRequiredMO() &&
-        Dep.value()->getRequiredMO()->getIdx() == OpIdx) {
-      for (const 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
-
-  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 =
-          llvm::find_if(Leaves, [](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 (const auto &[Idx, Child] : enumerate(TreeNode->children())) {
-    SubtreeBuilders.emplace_back(&Child, NextInstrID);
-    Partitioner->applyForPartition(Idx, *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 (unsigned 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");
-        append_range(OpcodesForThisPredicate, OpcodeP->getInstrs());
-      }
-
-      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 (const auto &[Index, EnumeratedLeaf] :
-       enumerate(Builder.getPossibleLeaves())) {
-    if (!PossibleLeaves[Index])
-      continue;
-
-    const auto &TestedPredicatesForLeaf = TestedPredicates[Index];
-
-    for (unsigned PredIdx : TestedPredicatesForLeaf.set_bits()) {
-      LLVM_DEBUG(dbgs() << "    " << EnumeratedLeaf.getName()
-                        << " tested predicate #" << PredIdx << " of "
-                        << TestedPredicatesForLeaf.size() << " "
-                        << *EnumeratedLeaf.getPredicate(PredIdx) << "\n");
-      EnumeratedLeaf.RemainingPredicates.reset(PredIdx);
-      EnumeratedLeaf.TestablePredicates.reset(PredIdx);
-    }
-    SubBuilder.addLeaf(EnumeratedLeaf);
-  }
-
-  // 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 (const auto &E : Leaf.getMatchDag().edges()) {
-      if (E->getFromMI() == Instr &&
-          E->getFromMO()->getIdx() < CGI->Operands.size()) {
-        ReferencedOperands.resize(E->getFromMO()->getIdx() + 1);
-        ReferencedOperands.set(E->getFromMO()->getIdx());
-      }
-    }
-  }
-  for (auto &Leaf : NewLeaves) {
-    // Skip any leaves that don't care about this instruction.
-    if (!Leaf.getInstrInfo(InstrID))
-      continue;
-
-    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 {
-  // Make sure not to emit empty switch or switch with just default
-  if (PartitionToInstr.size() == 1 && PartitionToInstr[0] == nullptr) {
-    OS << Indent << "Partition = 0;\n";
-  } else if (PartitionToInstr.size()) {
-    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";
-  }
-  OS << 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 (unsigned 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;
-    }
-
-    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.resize(Leaf.index() + 1);
-        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 (const auto &[Index, EnumeratedLeaf] :
-       enumerate(Builder.getPossibleLeaves())) {
-    if (!PossibleLeaves[Index])
-      continue;
-
-    const auto &TraversedEdgesForLeaf = TraversedEdges[Index];
-    TraversedEdgesByNewLeaves.push_back(TraversedEdgesForLeaf);
-    EnumeratedLeaf.RemainingEdges.reset(TraversedEdgesForLeaf);
-    EnumeratedLeaf.TraversableEdges.reset(TraversedEdgesForLeaf);
-    SubBuilder.addLeaf(EnumeratedLeaf);
-  }
-
-  // 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 (unsigned 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";
-}

llvm/utils/TableGen/GlobalISelCombinerEmitter.cpp

 #include "llvm/TableGen/Record.h"
 #include "llvm/TableGen/StringMatcher.h"
 #include "llvm/TableGen/TableGenBackend.h"
 #include <cstdint>
 
 using namespace llvm;
 using namespace llvm::gi;
 
-#define DEBUG_TYPE "gicombiner-matchtable-emitter"
+#define DEBUG_TYPE "gicombiner-emitter"
 
-extern cl::list<std::string> SelectedCombiners;
-extern cl::opt<bool> StopAfterParse;
-extern cl::OptionCategory GICombinerEmitterCat;
-
-static cl::opt<bool> DebugCXXPreds(
-    "gicombiner-matchtable-debug-cxxpreds",
+namespace {
+cl::OptionCategory
+    GICombinerEmitterCat("Options for -gen-global-isel-combiner");
+cl::opt<bool> StopAfterParse(
+    "gicombiner-stop-after-parse",
+    cl::desc("Stop processing after parsing rules and dump state"),
+    cl::cat(GICombinerEmitterCat));
+cl::list<std::string>
+    SelectedCombiners("combiners", cl::desc("Emit the specified combiners"),
+                      cl::cat(GICombinerEmitterCat), cl::CommaSeparated);
+cl::opt<bool> DebugCXXPreds(
+    "gicombiner-debug-cxxpreds",
     cl::desc("Add Contextual/Debug comments to all C++ predicates"),
     cl::cat(GICombinerEmitterCat));
-namespace {
+
 constexpr StringLiteral CXXApplyPrefix = "GICXXCustomAction_CombineApply";
 constexpr StringLiteral CXXPredPrefix = "GICXXPred_MI_Predicate_";
 constexpr StringLiteral PatFragClassName = "GICombinePatFrag";
 
 std::string getIsEnabledPredicateEnumName(unsigned CombinerRuleID) {
   return "GICXXPred_Simple_IsRule" + to_string(CombinerRuleID) + "Enabled";
 }
 
static void EmitGICombiner(RecordKeeper &RK, raw_ostream &OS) {
   for (const auto &Combiner : SelectedCombiners) {
     Record *CombinerDef = RK.getDef(Combiner);
     if (!CombinerDef)
       PrintFatalError("Could not find " + Combiner);
     GICombinerEmitter(RK, Target, Combiner, CombinerDef).run(OS);
   }
 }
 
-static TableGen::Emitter::Opt X("gen-global-isel-combiner-matchtable",
-                                EmitGICombiner,
-                                "Generate GlobalISel combiner Match Table");
+static TableGen::Emitter::Opt X("gen-global-isel-combiner", EmitGICombiner,
+                                "Generate GlobalISel Combiner");

llvm/utils/gn/secondary/llvm/lib/Target/AArch64/BUILD.gn

tablegen("AArch64GenFastISel") {
   visibility = [ ":LLVMAArch64CodeGen" ]
   args = [ "-gen-fast-isel" ]
   td_file = "AArch64.td"
 }
 
 tablegen("AArch64GenO0PreLegalizeGICombiner") {
   visibility = [ ":LLVMAArch64CodeGen" ]
   args = [
-    "-gen-global-isel-combiner-matchtable",
+    "-gen-global-isel-combiner",
     "-combiners=AArch64O0PreLegalizerCombiner",
   ]
   td_file = "AArch64.td"
 }
 
 tablegen("AArch64GenGlobalISel") {
   visibility = [ ":LLVMAArch64CodeGen" ]
   args = [ "-gen-global-isel" ]
   td_file = "AArch64.td"
 }
 
 tablegen("AArch64GenMCPseudoLowering") {
   visibility = [ ":LLVMAArch64CodeGen" ]
   args = [ "-gen-pseudo-lowering" ]
   td_file = "AArch64.td"
 }
 
 tablegen("AArch64GenPostLegalizeGICombiner") {
   visibility = [ ":LLVMAArch64CodeGen" ]
   args = [
-    "-gen-global-isel-combiner-matchtable",
+    "-gen-global-isel-combiner",
     "-combiners=AArch64PostLegalizerCombiner",
   ]
   td_file = "AArch64.td"
 }
 
 tablegen("AArch64GenPreLegalizeGICombiner") {
   visibility = [ ":LLVMAArch64CodeGen" ]
   args = [
-    "-gen-global-isel-combiner-matchtable",
+    "-gen-global-isel-combiner",
     "-combiners=AArch64PreLegalizerCombiner",
   ]
   td_file = "AArch64.td"
 }
 
 tablegen("AArch64GenPostLegalizeGILowering") {
   visibility = [ ":LLVMAArch64CodeGen" ]
   args = [
-    "-gen-global-isel-combiner-matchtable",
+    "-gen-global-isel-combiner",
     "-combiners=AArch64PostLegalizerLowering",
   ]
   td_file = "AArch64.td"
 }
 
 tablegen("AArch64GenRegisterBank") {
   visibility = [ ":LLVMAArch64CodeGen" ]
   args = [ "-gen-register-bank" ]

llvm/utils/gn/secondary/llvm/lib/Target/AMDGPU/BUILD.gn

tablegen("AMDGPUGenGlobalISel") {
   visibility = [ ":LLVMAMDGPUCodeGen" ]
   args = [ "-gen-global-isel" ]
   td_file = "AMDGPUGISel.td"
 }
 
 tablegen("AMDGPUGenPreLegalizeGICombiner") {
   visibility = [ ":LLVMAMDGPUCodeGen" ]
   args = [
-    "-gen-global-isel-combiner-matchtable",
+    "-gen-global-isel-combiner",
     "-combiners=AMDGPUPreLegalizerCombiner",
   ]
   td_file = "AMDGPUGISel.td"
 }
 
 tablegen("AMDGPUGenPostLegalizeGICombiner") {
   visibility = [ ":LLVMAMDGPUCodeGen" ]
   args = [
-    "-gen-global-isel-combiner-matchtable",
+    "-gen-global-isel-combiner",
     "-combiners=AMDGPUPostLegalizerCombiner",
   ]
   td_file = "AMDGPUGISel.td"
 }
 
 tablegen("AMDGPUGenRegBankGICombiner") {
   visibility = [ ":LLVMAMDGPUCodeGen" ]
   args = [
-    "-gen-global-isel-combiner-matchtable",
+    "-gen-global-isel-combiner",
     "-combiners=AMDGPURegBankCombiner",
   ]
   td_file = "AMDGPUGISel.td"
 }
 
 tablegen("AMDGPUGenMCPseudoLowering") {
   visibility = [ ":LLVMAMDGPUCodeGen" ]
   args = [ "-gen-pseudo-lowering" ]

llvm/utils/gn/secondary/llvm/lib/Target/Mips/BUILD.gn

tablegen("MipsGenMCPseudoLowering") {
   visibility = [ ":LLVMMipsCodeGen" ]
   args = [ "-gen-pseudo-lowering" ]
   td_file = "Mips.td"
 }
 
 tablegen("MipsGenPostLegalizeGICombiner") {
   visibility = [ ":LLVMMipsCodeGen" ]
   args = [
-    "-gen-global-isel-combiner-matchtable",
+    "-gen-global-isel-combiner",
     "-combiners=MipsPostLegalizerCombiner",
   ]
   td_file = "Mips.td"
 }
 
 tablegen("MipsGenRegisterBank") {
   visibility = [ ":LLVMMipsCodeGen" ]
   args = [ "-gen-register-bank" ]

utils/bazel/llvm-project-overlay/llvm/BUILD.bazel

llvm_target_lib_list = [lib for lib in [
             ("-gen-emitter", "lib/Target/AArch64/AArch64GenMCCodeEmitter.inc"),
             ("-gen-pseudo-lowering", "lib/Target/AArch64/AArch64GenMCPseudoLowering.inc"),
             ("-gen-asm-writer", "lib/Target/AArch64/AArch64GenAsmWriter.inc"),
             ("-gen-asm-writer -asmwriternum=1", "lib/Target/AArch64/AArch64GenAsmWriter1.inc"),
             ("-gen-asm-matcher", "lib/Target/AArch64/AArch64GenAsmMatcher.inc"),
             ("-gen-dag-isel", "lib/Target/AArch64/AArch64GenDAGISel.inc"),
             ("-gen-fast-isel", "lib/Target/AArch64/AArch64GenFastISel.inc"),
             ("-gen-global-isel", "lib/Target/AArch64/AArch64GenGlobalISel.inc"),
-            ("-gen-global-isel-combiner-matchtable -combiners=AArch64O0PreLegalizerCombiner", "lib/Target/AArch64/AArch64GenO0PreLegalizeGICombiner.inc"),
-            ("-gen-global-isel-combiner-matchtable -combiners=AArch64PreLegalizerCombiner", "lib/Target/AArch64/AArch64GenPreLegalizeGICombiner.inc"),
-            ("-gen-global-isel-combiner-matchtable -combiners=AArch64PostLegalizerCombiner", "lib/Target/AArch64/AArch64GenPostLegalizeGICombiner.inc"),
-            ("-gen-global-isel-combiner-matchtable -combiners=AArch64PostLegalizerLowering", "lib/Target/AArch64/AArch64GenPostLegalizeGILowering.inc"),
+            ("-gen-global-isel-combiner -combiners=AArch64O0PreLegalizerCombiner", "lib/Target/AArch64/AArch64GenO0PreLegalizeGICombiner.inc"),
+            ("-gen-global-isel-combiner -combiners=AArch64PreLegalizerCombiner", "lib/Target/AArch64/AArch64GenPreLegalizeGICombiner.inc"),
+            ("-gen-global-isel-combiner -combiners=AArch64PostLegalizerCombiner", "lib/Target/AArch64/AArch64GenPostLegalizeGICombiner.inc"),
+            ("-gen-global-isel-combiner -combiners=AArch64PostLegalizerLowering", "lib/Target/AArch64/AArch64GenPostLegalizeGILowering.inc"),
             ("-gen-callingconv", "lib/Target/AArch64/AArch64GenCallingConv.inc"),
             ("-gen-subtarget", "lib/Target/AArch64/AArch64GenSubtargetInfo.inc"),
             ("-gen-disassembler", "lib/Target/AArch64/AArch64GenDisassemblerTables.inc"),
             ("-gen-searchable-tables", "lib/Target/AArch64/AArch64GenSystemOperands.inc"),
             ("-gen-exegesis", "lib/Target/AArch64/AArch64GenExegesis.inc"),
         ],
     },
     {
llvm_target_lib_list = [lib for lib in [
             ("-gen-asm-writer", "lib/Target/Mips/MipsGenAsmWriter.inc"),
             ("-gen-callingconv", "lib/Target/Mips/MipsGenCallingConv.inc"),
             ("-gen-dag-isel", "lib/Target/Mips/MipsGenDAGISel.inc"),
             ("-gen-disassembler", "lib/Target/Mips/MipsGenDisassemblerTables.inc"),
             ("-gen-emitter", "lib/Target/Mips/MipsGenMCCodeEmitter.inc"),
             ("-gen-exegesis", "lib/Target/Mips/MipsGenExegesis.inc"),
             ("-gen-fast-isel", "lib/Target/Mips/MipsGenFastISel.inc"),
             ("-gen-global-isel", "lib/Target/Mips/MipsGenGlobalISel.inc"),
-            ("-gen-global-isel-combiner-matchtable -combiners=MipsPostLegalizerCombiner", "lib/Target/Mips/MipsGenPostLegalizeGICombiner.inc"),
+            ("-gen-global-isel-combiner -combiners=MipsPostLegalizerCombiner", "lib/Target/Mips/MipsGenPostLegalizeGICombiner.inc"),
             ("-gen-instr-info", "lib/Target/Mips/MipsGenInstrInfo.inc"),
             ("-gen-pseudo-lowering", "lib/Target/Mips/MipsGenMCPseudoLowering.inc"),
             ("-gen-register-bank", "lib/Target/Mips/MipsGenRegisterBank.inc"),
             ("-gen-register-info", "lib/Target/Mips/MipsGenRegisterInfo.inc"),
             ("-gen-subtarget", "lib/Target/Mips/MipsGenSubtargetInfo.inc"),
         ],
     },
     {
filegroup(
     ]),
 )
 
 gentbl(
     name = "amdgpu_isel_target_gen",
     strip_include_prefix = "lib/Target/AMDGPU",
     tbl_outs = [
         ("-gen-global-isel", "lib/Target/AMDGPU/AMDGPUGenGlobalISel.inc"),
-        ("-gen-global-isel-combiner-matchtable -combiners=AMDGPUPreLegalizerCombiner", "lib/Target/AMDGPU/AMDGPUGenPreLegalizeGICombiner.inc"),
-        ("-gen-global-isel-combiner-matchtable -combiners=AMDGPUPostLegalizerCombiner", "lib/Target/AMDGPU/AMDGPUGenPostLegalizeGICombiner.inc"),
-        ("-gen-global-isel-combiner-matchtable -combiners=AMDGPURegBankCombiner", "lib/Target/AMDGPU/AMDGPUGenRegBankGICombiner.inc"),
+        ("-gen-global-isel-combiner -combiners=AMDGPUPreLegalizerCombiner", "lib/Target/AMDGPU/AMDGPUGenPreLegalizeGICombiner.inc"),
+        ("-gen-global-isel-combiner -combiners=AMDGPUPostLegalizerCombiner", "lib/Target/AMDGPU/AMDGPUGenPostLegalizeGICombiner.inc"),
+        ("-gen-global-isel-combiner -combiners=AMDGPURegBankCombiner", "lib/Target/AMDGPU/AMDGPUGenRegBankGICombiner.inc"),
     ],
     tblgen = ":llvm-tblgen",
     td_file = "lib/Target/AMDGPU/AMDGPUGISel.td",
     td_srcs = [
         ":common_target_td_sources",
     ] + glob([
         "lib/Target/AMDGPU/*.td",
     ]),