[gicombiner] Add the MatchDag structure and parse instruction DAG's from the input

[dsanders]

Summary

The MatchDag structure is a representation of the checks that need to be
performed and the dependencies that limit when they can happen.

There are two kinds of node in the MatchDag:

• Instrs - Represent a MachineInstr
• Predicates - Represent a check that needs to be performed (i.e. opcode, is register, same machine operand, etc.)

and two kinds of edges:

• (Traversal) Edges - Represent a register that can be traversed to find one instr from another
• Predicate Dependency Edges - Indicate that a predicate requires a piece of information to be tested.

For example, the matcher:
(match (MOV $t, $s),

(MOV $d, $t))

with MOV declared as an instruction of the form:

%dst = MOV %src1

becomes the following MatchDag with the following instruction nodes:

__anon0_0 // $t=getOperand(0), $s=getOperand(1)
__anon0_1 // $d=getOperand(0), $t=getOperand(1)

traversal edges:

__anon0_1[src1] --[t]--> __anon0_0[dst]

predicate nodes:

<<$mi.getOpcode() == MOV>>:$__anonpred0_2
<<$mi.getOpcode() == MOV>>:$__anonpred0_3

and predicate dependencies:

__anon0_0 ==> __anonpred0_2[mi]
__anon0_0 ==> __anonpred0_3[mi]

The result of this parse is currently unused but can be tested
using -gicombiner-stop-after-parse as done in parse-match-pattern.td. The
dump for testing includes a graphviz format dump to allow the rule to be
viewed visually.

Later on, these MatchDag's will be used to generate code and to build an
efficient decision tree.

[dsanders]

Ping

[arsenm]

Is there a mechanism here for supporting hasOneUse checks?

llvm/utils/TableGen/GICombinerEmitter.cpp

453–456

merge into one LLVM_DEBUG block?

[dsanders]

In D69077#1721805, @arsenm wrote:

Is there a mechanism here for supporting hasOneUse checks?

At the moment it's available using the code-block escape hatch:

(match ...
       [{ ...
          if (!MRI.hasOneUse(${root}.getOperand(1).getReg()))
            return false;
          ...
       }])

There's a patch that I haven't posted yet (just to keep the patches under review to a reasonable number) that adds the arbitrary C++ predicate feature (GIMatchPredicate from the original proposal) and that will be the preferred way to use it unless/until we decide that GIMatchTree (D69152) needs to be aware of it

[dsanders]

Merge LLVM_DEBUG's

[volkan]

LGTM with a few nits.

llvm/utils/TableGen/GICombinerEmitter.cpp

334

Is there a reason not to add continue here? Do we want to keep processing if it failed to add edges?

458

Nit: curly braces can be removed.

llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.cpp

12

Nit: empty lines

21

Nit: this can be replaced with if (auto Annotation = getOpcodeAnnotation())

llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h

14

Nit: empty line

[dsanders]

llvm/utils/TableGen/GICombinerEmitter.cpp

334

It's so that we print more errors (if there are any) before we give up. This helps the developer fix all their mistakes in fewer attempts.

[dsanders]

llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.cpp

12

These empty lines were intended to separate the groups of includes from (http://llvm.org/docs/CodingStandards.html#include-style). However, it turns out clang-format is smart enough for that anyway. Removed them

llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h

14

Likewise for this one

[uweigand]

The new test case causes build bot failures (hidden by another failure that was already present):
http://lab.llvm.org:8011/builders/clang-s390x-linux/builds/28934/steps/ninja%20check%201/logs/FAIL%3A%20LLVM%3A%3Aparse-match-pattern.td

/home/uweigand/sandbox/buildbot/clang-s390x-linux/llvm/llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td:212:16: error: CHECK-NEXT: expected string not found in input
// CHECK-NEXT: 0:$<def>, 1:mi0, 2:mi1
               ^
<stdin>:129:16: note: scanning from here
 0:$<def>, 1:mi0, 2:mi1
               ^
<stdin>:130:2: note: possible intended match here
 0:$<def>, 1:mi
 ^

[thakis]

The test also fails on Windows: http://45.33.8.238/win/4272/step_11.txt

Looks like %p doesn't prefix pointers with 0x there.

[phosek]

We're seeing a different failure on our 2-stage bots (in second stage):

/b/s/w/ir/k/llvm-project/llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td:30:17: error: CHECK-LABEL: expected string not found in input
// CHECK-LABEL: Parsed rule defs/match for 'trivial'
                ^
<stdin>:1:1: note: scanning from here
llvm-tblgen: for the -d option: may not occur within a group!
^
<stdin>:3:11: note: possible intended match here
llvm-tblgen: Did you mean '-d'?
          ^

[dsanders]

In D69077#1788377, @uweigand wrote:

The new test case causes build bot failures (hidden by another failure that was already present):
http://lab.llvm.org:8011/builders/clang-s390x-linux/builds/28934/steps/ninja%20check%201/logs/FAIL%3A%20LLVM%3A%3Aparse-match-pattern.td

/home/uweigand/sandbox/buildbot/clang-s390x-linux/llvm/llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td:212:16: error: CHECK-NEXT: expected string not found in input
// CHECK-NEXT: 0:$<def>, 1:mi0, 2:mi1
               ^
<stdin>:129:16: note: scanning from here
 0:$<def>, 1:mi0, 2:mi1
               ^
<stdin>:130:2: note: possible intended match here
 0:$<def>, 1:mi
 ^

I think I can hazard a reasonable guess what this one is going to be. It's probably printed in a slightly different order. I'll look into it

In D69077#1788787, @thakis wrote:

The test also fails on Windows: http://45.33.8.238/win/4272/step_11.txt

Looks like %p doesn't prefix pointers with 0x there.

Windows always has to be different :-). Ok, I can fix this by relaxing the regexes a bit

In D69077#1788903, @phosek wrote:

We're seeing a different failure on our 2-stage bots (in second stage):

/b/s/w/ir/k/llvm-project/llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td:30:17: error: CHECK-LABEL: expected string not found in input
// CHECK-LABEL: Parsed rule defs/match for 'trivial'
                ^
<stdin>:1:1: note: scanning from here
llvm-tblgen: for the -d option: may not occur within a group!
^
<stdin>:3:11: note: possible intended match here
llvm-tblgen: Did you mean '-d'?
          ^

Could you give me more information on this? Which bots is it? For now, I'm going to hazard a guess that the test just needs a 'REQUIRES: asserts'. Though it's a bit surprising that I don't have an email from one of the release-build bots if that were the problem

[dsanders]

I've pushed 7ea2e5195a8 which should address these three issues

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

 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/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
+
+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-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-f]+}}|{<d0>#0 $dst|<d1>#1 $src1}}",color=red]
+// CHECK-NEXT:   Pred[[P1:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred0_1|$mi.getOpcode() == MOV|{{0x[0-9a-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-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon1_0|MOV|$t=getOperand(0), $s=getOperand(1)|{{0x[0-9a-f]+}}|{<d0>#0 $dst|<d1>#1 $src1}}"]
+// CHECK-NEXT:   Node[[N2:0x[0-9a-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-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-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred1_1|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
+// CHECK-NEXT:   Pred[[P2:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred1_3|$mi.getOpcode() == MOV|{{0x[0-9a-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-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon2_0|MOV|$s=getOperand(0), $s2=getOperand(1)|{{0x[0-9a-f]+}}|{<d0>#0 $dst|<d1>#1 $src1}}"]
+// CHECK-NEXT:   Node[[N2:0x[0-9a-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-f]+}}|{<d0>#0 $dst|<d1>#1 $src1}}",color=red]
+// CHECK-NEXT:   Node[[N3:0x[0-9a-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-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-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred2_1|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
+// CHECK-NEXT:   Pred[[P2:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred2_3|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
+// CHECK-NEXT:   Pred[[P3:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred2_5|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
+// CHECK-NEXT:   Pred[[P4:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi0|<s2>#2 $mi1}|__anonpred2_6|$mi0 == $mi1|{{0x[0-9a-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_2[src1] --[s]--> __anon3_0[dst]
+// CHECK-NEXT:     __anon3_4[src1] --[s]--> __anon3_0[dst]
+// 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-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-f]+}}|{<d0>#0 $dst|<d1>#1 $src1}}",color=red]
+// CHECK-NEXT:   Node[[N2:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon3_2|MOV|$d1=getOperand(0), $s=getOperand(1)|{{0x[0-9a-f]+}}|{<d0>#0 $dst|<d1>#1 $src1}}"]
+// CHECK-NEXT:   Node[[N3:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon3_4|MOV|$d2=getOperand(0), $s=getOperand(1)|{{0x[0-9a-f]+}}|{<d0>#0 $dst|<d1>#1 $src1}}"]
+// 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-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred3_1|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
+// CHECK-NEXT:   Pred[[P2:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred3_3|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
+// CHECK-NEXT:   Pred[[P3:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred3_5|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
+// CHECK-NEXT:   Pred[[P4:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi0|<s2>#2 $mi1}|__anonpred3_6|$mi0 == $mi1|{{0x[0-9a-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-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-f]+}}|{<d0>#0 $dst|<d1>#1 $src1}}",color=red]
+// CHECK-NEXT:   Node[[N2:0x[0-9a-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-f]+}}|{<d0>#0 $dst|<d1>#1 $src1}}",color=red]
+// CHECK-NEXT:   Pred[[P1:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred4_1|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
+// CHECK-NEXT:   Pred[[P2:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred4_3|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
+// CHECK-NEXT:   Pred[[P3:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi0|<s2>#2 $mi1}|__anonpred4_4|$mi0 == $mi1|{{0x[0-9a-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/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 "llvm/ADT/Statistic.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ScopedPrinter.h"
 #include "llvm/Support/Timer.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/StringMatcher.h"
 #include "llvm/TableGen/TableGenBackend.h"
 #include "CodeGenTarget.h"
 #include "GlobalISel/CodeExpander.h"
 #include "GlobalISel/CodeExpansions.h"
+#include "GlobalISel/GIMatchDag.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "gicombiner-emitter"
 
 // FIXME: Use ALWAYS_ENABLED_STATISTIC once it's available.
 unsigned NumPatternTotal = 0;
 STATISTIC(NumPatternTotalStatistic, "Total number of patterns");
 
 cl::OptionCategory
     GICombinerEmitterCat("Options for -gen-global-isel-combiner");
 static cl::list<std::string>
     SelectedCombiners("combiners", cl::desc("Emit the specified combiners"),
                       cl::cat(GICombinerEmitterCat), cl::CommaSeparated);
 static cl::opt<bool> ShowExpansions(
     "gicombiner-show-expansions",
     cl::desc("Use C++ comments to indicate occurence of code expansion"),
     cl::cat(GICombinerEmitterCat));
+static cl::opt<bool> StopAfterParse(
+    "gicombiner-stop-after-parse",
+    cl::desc("Stop processing after parsing rules and dump state"),
+    cl::cat(GICombinerEmitterCat));
 
 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 RootInfo {
   StringRef PatternSymbol;
 
 public:
   RootInfo(StringRef PatternSymbol) : PatternSymbol(PatternSymbol) {}
 
   StringRef getPatternSymbol() const { return PatternSymbol; }
 };
 
 class CombineRule {
+  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 CodeInit *MatchingFixupCode = nullptr;
+
+  bool parseInstructionMatcher(const CodeGenTarget &Target, StringInit *ArgName,
+                               const Init &Arg,
+                               StringMap<std::vector<VarInfo>> &NamedEdgeDefs,
+                               StringMap<std::vector<VarInfo>> &NamedEdgeUses);
+
 public:
-  CombineRule(const CodeGenTarget &Target, RuleID ID, const Record &R)
-      : ID(ID), TheDef(R) {}
+  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 CodeInit *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());
   }
 };
 

 /// DagInit's since DagInit's support any type inside them.
 static Record *getDefOfSubClass(const Init &N, StringRef Cls) {
   if (const DefInit *OpI = dyn_cast<DefInit>(&N))
     if (OpI->getDef()->isSubClassOf(Cls))
       return OpI->getDef();
   return nullptr;
 }
 
+/// A convenience function to check that an Init refers to a dag whose operator
+/// is a def that is a subclass of the given class and coerce it to a dag if it
+/// is. This is primarily useful for testing for subclasses of GIMatchKind and
+/// similar in DagInit's since DagInit's support any type inside them.
+static const DagInit *getDagWithOperatorOfSubClass(const Init &N,
+                                                   StringRef Cls) {
+  if (const DagInit *I = dyn_cast<DagInit>(&N))
+    if (I->getNumArgs() > 0)
+      if (const DefInit *OpI = dyn_cast<DefInit>(I->getOperator()))
+        if (OpI->getDef()->isSubClassOf(Cls))
+          return I;
+  return nullptr;
+}
+
+StringRef makeNameForAnonInstr(CombineRule &Rule) {
+  return insertStrTab(
+      to_string(format("__anon%d_%d", 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%d_%d", Rule.getID(), Rule.allocUID())));
+}
+
 bool CombineRule::parseDefs() {
   NamedRegionTimer T("parseDefs", "Time spent parsing the defs", "Rule Parsing",
                      "Time spent on rule parsing", TimeRegions);
   DagInit *Defs = TheDef.getValueAsDag("Defs");
 
   if (Defs->getOperatorAsDef(TheDef.getLoc())->getName() != "defs") {
     PrintError(TheDef.getLoc(), "Expected defs operator");
     return false;
bool CombineRule::parseDefs() {
 
   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 (find_if(Roots, [&](const RootInfo &X) {
+              return X.getPatternSymbol() == Name;
+            }) != Roots.end()) {
+          N->setMatchRoot();
+        }
+      }
+
+      OpIdx++;
+    }
+
+    return true;
+  }
+  return false;
+}
+
 bool CombineRule::parseMatcher(const CodeGenTarget &Target) {
   NamedRegionTimer T("parseMatcher", "Time spent parsing the matcher",
                      "Rule Parsing", "Time spent on rule parsing", TimeRegions);
+  StringMap<std::vector<VarInfo>> NamedEdgeDefs;
+  StringMap<std::vector<VarInfo>> NamedEdgeUses;
   DagInit *Matchers = TheDef.getValueAsDag("Match");
 
   if (Matchers->getOperatorAsDef(TheDef.getLoc())->getName() != "match") {
     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;
+
 
     // Parse arbitrary C++ code we have in lieu of supporting MIR matching
     if (const CodeInit *CodeI = dyn_cast<CodeInit>(Matchers->getArg(I))) {
       assert(!MatchingFixupCode &&
              "Only one block of arbitrary code is currently permitted");
       MatchingFixupCode = CodeI;
       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 {
   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);
void GICombinerEmitter::emitNameMatcher(raw_ostream &OS) const {
   OS << "#endif // ifndef NDEBUG\n\n"
      << "  return None;\n"
      << "}\n";
 }
 
 std::unique_ptr<CombineRule>
 GICombinerEmitter::makeCombineRule(const Record &TheDef) {
   std::unique_ptr<CombineRule> Rule =
-      std::make_unique<CombineRule>(Target, NumPatternTotal, TheDef);
+      std::make_unique<CombineRule>(Target, MatchDagCtx, NumPatternTotal, TheDef);
 
   if (!Rule->parseDefs())
     return nullptr;
   if (!Rule->parseMatcher(Target))
     return nullptr;
+  LLVM_DEBUG(dbgs() << "Parsed rule defs/match for '" << Rule->getName()
+                    << "'\n");
+  LLVM_DEBUG(Rule->getMatchDag().dump());
+  LLVM_DEBUG(Rule->getMatchDag().writeDOTGraph(dbgs(), Rule->getName()));
+  if (StopAfterParse) {
+    return Rule;
+  }
+
   // 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;
 }
void GICombinerEmitter::generateCodeForRule(raw_ostream &OS,
     }
 
     OS << Indent << "}\n";
   }
 }
 
 void GICombinerEmitter::run(raw_ostream &OS) {
   gatherRules(Rules, Combiner->getValueAsListOfDefs("Rules"));
+  if (StopAfterParse) {
+    MatchDagCtx.print(errs());
+    PrintNote(Combiner->getLoc(),
+              "Terminating due to -gicombiner-stop-after-parse");
+    return;
+  }
   if (ErrorsPrinted)
     PrintFatalError(Combiner->getLoc(), "Failed to parse one or more rules");
 
   NamedRegionTimer T("Emit", "Time spent emitting the combiner",
                      "Code Generation", "Time spent generating code",
                      TimeRegions);
   OS << "#ifdef " << Name.upper() << "_GENCOMBINERHELPER_DEPS\n"
      << "#include \"llvm/ADT/SparseBitVector.h\"\n"

llvm/utils/TableGen/GlobalISel/CMakeLists.txt

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

llvm/utils/TableGen/GlobalISel/GIMatchDag.h

+//===- GIMatchDag.h - Represent a DAG 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
+//
+//===----------------------------------------------------------------------===//
+
+#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 {
+class GIMatchDag;
+
+/// 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 EdgesVec = std::vector<std::unique_ptr<GIMatchDagEdge>>;
+  using PredicateNodesVec = std::vector<std::unique_ptr<GIMatchDagPredicate>>;
+
+  using PredicateDependencyEdgesVec =
+      std::vector<std::unique_ptr<GIMatchDagPredicateDependencyEdge>>;
+
+protected:
+  GIMatchDagContext &Ctx;
+  InstrNodesVec InstrNodes;
+  PredicateNodesVec PredicateNodes;
+  EdgesVec Edges;
+  PredicateDependencyEdgesVec PredicateDependencies;
+  std::vector<GIMatchDagInstr *> MatchRoots;
+
+public:
+  GIMatchDag(GIMatchDagContext &Ctx)
+      : Ctx(Ctx), InstrNodes(), PredicateNodes(), Edges(),
+        PredicateDependencies() {}
+  GIMatchDag(const GIMatchDag &) = delete;
+
+  GIMatchDagContext &getContext() const { return Ctx; }
+
+  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;
+  }
+
+  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.begin(), ToPrint.end());
+    StringRef Separator = "";
+    for (const auto &Assignment : ToPrint) {
+      OS << Separator << "$" << Assignment.second << "=getOperand("
+         << Assignment.first << ")";
+      Separator = ", ";
+    }
+    OS << 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 << 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 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
+//
+//===----------------------------------------------------------------------===//
+
+#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; }
+
+  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 "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()
+     << "]";
+}
+

llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h

+//===- GIMatchDagInstr.h - Represent a instruction 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGINSTR_H
+#define LLVM_UTILS_TABLEGEN_GIMATCHDAGINSTR_H
+
+#include "GIMatchDagOperands.h"
+
+#include "llvm/ADT/DenseMap.h"
+
+namespace llvm {
+class GIMatchDag;
+
+/// 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 = 0;
+
+  /// 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; }
+  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 "GIMatchDag.h"
+
+#include "llvm/TableGen/Record.h"
+
+#include "../CodeGenInstruction.h"
+
+using namespace llvm;
+
+void GIMatchDagInstr::print(raw_ostream &OS) const {
+  OS << "(";
+  if (getOpcodeAnnotation())
+    OS << getOpcodeAnnotation()->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.begin(), ToPrint.end());
+    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 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
+//
+//===----------------------------------------------------------------------===//
+//
+//
+//===----------------------------------------------------------------------===//
+
+#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 : OperandLists) {
+    OS << "    ";
+    I.print(OS);
+    OS << "\n";
+  }
+  OS << "  }\n"
+     << "}\n";
+}

llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.h

+//===- GIMatchDagPredicate - Represent a predicate to check ---------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATE_H
+#define LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATE_H
+
+#include "llvm/ADT/StringRef.h"
+#include "GIMatchDag.h"
+namespace llvm {
+class 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_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; }
+
+  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)
+  virtual LLVM_DUMP_METHOD void dump() const override { print(errs()); }
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+};
+
+class GIMatchDagSameMOPredicate : public GIMatchDagPredicate {
+public:
+  GIMatchDagSameMOPredicate(GIMatchDagContext &Ctx, StringRef Name);
+
+  static bool classof(const GIMatchDagPredicate *P) {
+    return P->getKind() == GIMatchDagPredicateKind_SameMO;
+  }
+
+  void printDescription(raw_ostream &OS) const override;
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  virtual LLVM_DUMP_METHOD void dump() const override { print(errs()); }
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+};
+
+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 "GIMatchDagOperands.h"
+#include "../CodeGenInstruction.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();
+}
+
+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 "GIMatchDagOperands.h"
+
+namespace llvm {
+class GIMatchDag;
+class GIMatchDagInstr;
+class GIMatchDagEdge;
+class GIMatchDagPredicate;
+
+/// 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 "GIMatchDagPredicate.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;
+}