[RFC][GlobalISel] Replace the current GlobalISel matcher with a bottom-up matcher

[Kai]

Summary

The GICombiner can match an instruction pattern, but in the current implementation this feature is basically
not used. One reason is that the matching capability is somewhat limited. Let's look at some examples.

I can easily match a G_ICMP/G_ZEXT/GSUB sequence:

(match (G_ICMP $icmp, $cc, $srcb, $srcc),
       (G_ZEXT $zext, $icmp),
       (G_SUB $dst, $srca, $zext))

Just change G_SUB to G_ADD:

(match (G_ICMP $icmp, $cc, $srcb, $srcc),
       (G_ZEXT $zext, $icmp),
       (G_ADD $dst, $srca, $zext))

and it does not work as expected, because the current implementation does not handle commutable instructions like the C++ mi_match(). In order to get the desired outcome, you have to add another combine rule, just with the $srca and $zext operand swapped. Obviously, just using C++ code seems easier.

Even more annoying, turning to a simple tree pattern like

(match (G_AND $srca, $t1, $t2),
       (G_AND $srcb, $t3, $t4),
       (G_OR $dst, $srca, $srcb))

just crashes TableGen.

The proposal is to replace the current matcher implementation with a bottom-up matcher.

The basic idea of a bottom-up matcher is to associate each instruction the set of matching patterns, called the match set. For an instruction without use operands (a leaf) the match set is easily determined. For any other instruction, the match set is retrieved via a table lookup, using the use operands as table indices. As a result, all matching patterns can be found in linear time.

Commutable instructions are handled by adding the variant patterns resulting from swapping the subpatterns. For the resulting code, the implication is that only the variable binding varies. The rule code is not duplicated.

This implementation is based in the algorithm from Chase. See https://dl.acm.org/doi/10.1145/41625.41640.
It is a drop-in replacement for the existing matcher, with no changes in the result.

Some numbers from Linux on Z (orig vs change applied):
Compiling LLVM is slightly longer with this change applied: 25m35.471s vs 28m51.797s
The resulting llc binary is slightly smaller: 145.899.472 bytes vs 145.849.704 bytes
I got similar results in Linux on Power.
I have not yet measured the impact of the resulting matcher on the compile time.

Update on the numbers:
Compiling on Linux on Z (that is, only llvm-tblgen is changed) is now (current/bottom-up) 24m32.520s vs. 25m29.169s

Running LLVM test suite with -fglobal-isel on an AArch64 EC2 instance (2 CPUs, 4GB):
Current implementation: 22m43.224s
Bottom-up implementation: 22m47.165s

Size of the binaries:
Current implementation: llc 127.280.024, clang 217.540.416
Bottom-up implementation: llc 127.026.960, clang 217.291.456

One interesting point to note:
The current combiner implementation loops over the basic blocks of a machine functions until a fixpoint is reached. The bottom up matcher matches all patterns, so in theory a single loop of the instructions should be enough. However, there are 2 reasons why this is not implemented:

• The last loop over the instructions removes trivially dead instructions, which would not happen if only a single loop over the instructions is done. This has no functional impact. The next combiner, or latest the instruction selector removes trivially dead instructions. However, lot of test case would need to be changed because they do not expect those dead instructions. A simple solution would be to make a second loop over the instructions, just removing the trivially dead instructions, which would be faster than doing a full iteration.
• More important, not all patterns would be matched! The reason is that there are C++ matchers which perform a top-down match. One example is the rule fold_global_offset from the AArch64PreLegalizerCombiner. This rule matches a G_GLOBAL_VALUE only, but the C++ matcher looks at the uses of the defined value, which basically means that the matcher reverses the order in which matches are made. As a result, the bottom-up matcher is not aware that it has to apply another rule. I think this case can be fixed by changing the matching pattern. The question is if this is desirable, because it would add restrictions to what a C++ matcher is allowed to do.

There are some open todos/ideas to discuss:

• Measure runtime of the matcher
• The information required for tests is print in YAML format. However, the output is not yet the same on all platforms. The current solution is to re-assign the encoding in a deterministic way. This code is responsible for the larger part of the increased compile time, and should be removed.
• The old matcher generator implementation is still there, but not used.
• Adding the new parameter to tryCombineAll() should possibly be a separate PR. I think that introducing a new class CombinerState, which is just a thin wrapper around a DenseMap<MachineInstr *, unsigned>, would also make sense.

[arsenm]

Compiling LLVM is slightly longer with this change applied: 25m35.471s vs 28m51.797

This is huge. I don't understand this part. Surely you don't have bootstrapped globalisel working? Why this slowdown?

However, lot of test case would need to be changed because they do not expect those dead instructions. A simple solution would be to make a second loop over the instructions, just removing the trivially dead instructions, which would be faster than doing a full iteration.

We can also just update tests. Avoiding test changes isn't a good reason to do something

[arsenm]

Adding the new parameter to tryCombineAll() should possibly be a separate PR. I think that introducing a new class CombinerState, which is just a thin wrapper around a DenseMap<MachineInstr *, unsigned>, would also make sense.

Like D81899?

[arsenm]

llvm/lib/CodeGen/GlobalISel/Combiner.cpp

155

can just directly print *MI

164–165

Should move construction of these out of the loop too?

llvm/lib/Target/AArch64/GISel/AArch64O0PreLegalizerCombiner.cpp

75

Should use a typedef/using for the set type

llvm/utils/TableGen/GlobalISel/GIMatchTreeAutomaton.cpp

71

Avoid relative include paths

171

ArrayRefs should be passed by value

354

!empty()

363

Single quotes here and elsewhere for single character printing

673–679

Can this just be a standalone function if you're passing in the two items explicitly anyway?

752

Typo DAAGRoot

809

Don't need llvm::

979

Hoist construction out of loop?

llvm/utils/TableGen/GlobalISel/GIMatchTreeAutomaton.h

30

Should avoid relative include paths

[Kai]

In D141135#4031482, @arsenm wrote:

Compiling LLVM is slightly longer with this change applied: 25m35.471s vs 28m51.797

This is huge. I don't understand this part. Surely you don't have bootstrapped globalisel working? Why this slowdown?

The slowdown comes from llvm-tblgen and is due to the sorting at the end of createMatchSets(). This is currently required to get a stable encoding for testing. I currently work on changing the test structure, with the goal to remove the sorting completely.
Another reason for the slowdown is that my implementation still calculations to much. I always loop over all representer sets, but only sets added in the last round can actually add another set. This can clearly improved.

I have not yet measured bootstrapping with globalisel. The only reason for that is that I struggle a bit with setting up a cross-compile environment. I guess aarch64 is the best architecture to test the impact.

[Kai]

In D141135#4031482, @arsenm wrote:

We can also just update tests. Avoiding test changes isn't a good reason to do something

Of course. It just makes the change even bigger.

[Kai]

In D141135#4031488, @arsenm wrote:

Adding the new parameter to tryCombineAll() should possibly be a separate PR. I think that introducing a new class CombinerState, which is just a thin wrapper around a DenseMap<MachineInstr *, unsigned>, would also make sense.

Like D81899?

I think this does not go far enough. To be able to look over the boundary of a basic block the state must be available for the while MachineFunction.
Therefore I store the state in the Combiner, and pass it down to CombinerInfo::combine. An alternative would be to add a new member to CombinerInfo. This is just for the life time requirement, the usage is only in the tryCombineAll(), but I have not yet found a better solution.

[Kai]

I restructured the YAML output used for the test. As a result I could remove the sorting code, which caused a longer running time of the algorithm. The construction of the matcher is much faster now. However, testing got more challenging. I also made some minor changes in other parts of the algorithm. The generated matcher code is unchanged..

[Pierre-vh]

Note: I didn't quite review the algorithm/logic in itself (I'll come back to it later when I'm sure I understand it fully to make meaningful comments), so I focused mostly on code style and general comments

The old matcher generator implementation is still there, but not used.

I would add a follow-up diff to remove it entirely, else I get the feeling it will stay there a very long time

The information required for tests is print in YAML format. However, the output is not yet the same on all platforms. The current solution is to re-assign the encoding in a deterministic way. This code is responsible for the larger part of the increased compile time, and should be removed.

Could it be a separate diff?

I also share the worries about compilation time, it would be nice to have some more detailed measurement (ideally both on AMDGPU and AArch64) and maybe make some additional optimizations before this gets the green light.
(IMHO) Since this is a pretty big change I'd like to make sure it doesn't affect compilation times negatively, as a recurring theme in LLVM is slow compilation times and we don't want to make huge steps backwards.

llvm/include/llvm/CodeGen/GlobalISel/GISelWorkList.h

115–118

llvm/lib/CodeGen/GlobalISel/Combiner.cpp

132

The class doesn't look like it repairs anything so the name could be better. If I understand correctly it builds a worklist from a list of changed instructions, adding the "parent" instructions as well. Maybe it should just be named TreeWorklistBuilder or something like that? I feel like it could also just be a pair of recursive function and the class itself adds no value.

Lastly, as this recursively adds all "parent" instructions I'm afraid it could "explode" in some cases and add almost all instructions. Is that possible?. Can you maybe look for optimizations/opportunities to skip some instructions? If there is none/they are rare, please add some comment explaining why we need to aggressively add everything

134

nit: I would move typedefs to the top and not mix them with variable declarations for readability

155

nit: I would split it in two lines

IMO debug statements like this are only useful with added context, so I would also print something before the loop runs, e.g. "Running TreeRepairer on N changed instructions". It would also be nice after each iteration to print how many instructions were added to the worklist. It could make it easier to spot cases where this "explodes" and greatly increases the number of instructions added to the worklist.

164–165

If we're always passing a new set, can we just not pass it by reference to WorklistMaintainer and instead let it create it & use an acccessor to retrieve it later?

llvm/utils/TableGen/GICombinerEmitter.cpp

731–734

742

744–747

It's one statement but more than one physical line so IIRC we want braces here

757–758

small nit: I'm not sure I like for loops without the increment part, could this just be a while loop?

llvm/utils/TableGen/GlobalISel/GIMatchTreeAutomaton.cpp

19

27

34

84

Unnecessary as all your code is inside namespace llvm

86

Are those TO-DO's to be done before this diff lands, or will they stay?

If they're here to stay, use // instead of /* */: https://llvm.org/docs/CodingStandards.html#comment-formatting

113

A bit scary to read and it would be useful to elaborate. Does it leak? Is it inefficient in terms of space (allocates too much) or time (e.g. chains of owned ptrs need to be freed and it takes time) ?

138

Could this (& its derived class) move to a separate header? (or just GIMatchTreeAutomaton.h)
This file is already pretty big and takes time to understand, having a whole datastructure definition in there doesn't help

158

Why int here but unsigned in other places? (same above)

187

Ditto - newline after } and before next function

203

262

331–332

nit: I would avoid 2 letter variable names like those. Maybe just use OpenParen/CloseParen?

645

660

Typedef this to make it less verbose?

805–807

814

Hmm, this works but feels like a weird use for "for". Perhaps a while loop is better here?

822–824

970

973

1000–1002

1147–1149

llvm/utils/TableGen/GlobalISel/GIMatchTreeAutomaton.h

106

112

128

small nit: Can you add a blank line between the } and the next function definitions to make it easier to read?

187

nit: comment doesn't add anything, it just repeats the variable name. I would either remove it or elaborate.

190

Ditto

191

If the key here is a number that starts at a fixed index and is always incremented by 1, you could just use a vector instead of a map

[Kai]

• Visit of changed instructions in the Combiner is now done iteratively.
• The array with the rules to execute in the generated source is a bit more compact.

Running LLVM test suite with -fglobal-isel on an AArch64 EC2 instance (2 CPUs, 4GB):
Current implementation: 22m43.224s
Bottom-up implementation: 22m47.165s

Size of the binaries:
Current implementation: llc 127.280.024, clang 217.540.416
Bottom-up implementation: llc 127.026.960, clang 217.291.456

[arsenm]

In D141135#4031707, @Kai wrote:

Therefore I store the state in the Combiner, and pass it down to CombinerInfo::combine. An alternative would be to add a new member to CombinerInfo. This is just for the life time requirement, the usage is only in the tryCombineAll(), but I have not yet found a better solution.

I think putting in CombinerInfo would be better

llvm/include/llvm/CodeGen/GlobalISel/CombinerInfo.h

70

I think this need to be a using/typedef

llvm/lib/CodeGen/GlobalISel/Combiner.cpp

106

llvm/utils/TableGen/GICombinerEmitter.cpp

59

I'd assume compact would be the default?

llvm/utils/TableGen/GlobalISel/GIMatchTreeAutomaton.cpp

117

Don't need llvm namespace?

337

single quotes

358

Single quotes

366

Single quotes

818

Typo missmatch

llvm/utils/TableGen/GlobalISel/GIMatchTreeAutomaton.h

29

Should still avoid relative include paths

[aemerson]

In D141135#4036756, @Kai wrote:

• Visit of changed instructions in the Combiner is now done iteratively.
• The array with the rules to execute in the generated source is a bit more compact.

Running LLVM test suite with -fglobal-isel on an AArch64 EC2 instance (2 CPUs, 4GB):
Current implementation: 22m43.224s
Bottom-up implementation: 22m47.165s

Size of the binaries:
Current implementation: llc 127.280.024, clang 217.540.416
Bottom-up implementation: llc 127.026.960, clang 217.291.456

I haven't had time to properly look at the implementation, but a question on this. When you say "running the test suite", are you talking about building the test suite with -fglobal-isel? Not running the generated code right?

Secondly, you mentioned that this is a drop on replacement for the existing matcher, yet we're seeing some code size differences. Do you know why?

[Kai]

In D141135#4046071, @aemerson wrote:

In D141135#4036756, @Kai wrote:

• Visit of changed instructions in the Combiner is now done iteratively.
• The array with the rules to execute in the generated source is a bit more compact.

Running LLVM test suite with -fglobal-isel on an AArch64 EC2 instance (2 CPUs, 4GB):
Current implementation: 22m43.224s
Bottom-up implementation: 22m47.165s

Size of the binaries:
Current implementation: llc 127.280.024, clang 217.540.416
Bottom-up implementation: llc 127.026.960, clang 217.291.456

I haven't had time to properly look at the implementation, but a question on this. When you say "running the test suite", are you talking about building the test suite with -fglobal-isel? Not running the generated code right?

Yes, for the time measurement I referred to building the test suite, as this shows the impact of my code on the compile time. (I also ran the test suite to make sure that there are no regressions.)

Secondly, you mentioned that this is a drop on replacement for the existing matcher, yet we're seeing some code size differences. Do you know why?

Yes. The matcher my code generates has a simpler structure. It is basically:

• Calculate the match set number for the current instruction, which is either a constant assignment or a table lookup.
• Translate the match set number to a list of rules to execute, which is another table lookup.
• Run the rules

The current matcher has a couple of if and switch statements before the rules are run. I noted that the generated tables are much more compact than the code generated from if and switch. The overall price my implementation pays is a greater construction time in llvm-tblgen.

[dsanders]

I don't have time for a proper review at the moment as I'm still dealing with a lot of downstream problems but I have a few comments

The basic idea of a bottom-up matcher is to associate each instruction the set of matching patterns, called the match set. For an instruction without use operands (a leaf) the match set is easily determined. For any other instruction, the match set is retrieved via a table lookup, using the use operands as table indices. As a result, all matching patterns can be found in linear time.

Aside from the 'bottom-up' part, that's pretty consistent with where I wanted to end up. I was pretty worried about the 'bottom-up' part as there's some top-down and middle-out combines that were making better decisions with their visiblity of all the uses after applying the rule but you mentioned that those are still available later on. I definitely don't want to lose that capability

One thing the original matcher was aiming to do was to to merge rules that were very similar but diverged near the root of the match. The intent was that given multiple rules with the same structure and predicates but different opcodes, it could still match the commonality and only diverge at the point it needs to. I guess one concrete example of that is ((x << y) >> y) -> x & M or sext(x, y) depending on whether the shift right is logical or arithmetic. The matchers used by DAGISel and GISel's instruction selector essentially treat these as two fully independent matchers as they test for the G_LSHR/G_ASHR opcodes first, but those rules could share common matching code right up to the last check. Even if we don't make use of it at the moment, it would be good if we can make this matcher change without making a future change along those lines impossible.

At one point I had a draft algorithm for handling multiple mutually exclusive choices based on their relative improvement on the code but the way things have gone over the last couple years I'm never going to find time to implement that. There are some things worth thinking about from it though. Most of those mutually exclusive choices arise from our frequent use of hasOneUse(). Upstream uses it a bit but downstream we use it a lot. This predicate is a proxy for what we really want to be checking which is "will this value become unused after the combine?". Essentially, it's a test that the combine is going to save on work rather than break even or increase it. For example, fadd + fmul -> fma doesn't save anything if the fmul result is needed for something else. It would be good if it were possible for "will be unused" tests to account for more than one applied combine. For example, maybe multiply-add and multiply-sub combine match the same mul so it has two uses both of which will go away after the combines. Ideally we'd apply both rather than blocking them because each rule sees it doesn't eliminate all the uses by itself.
Side note: An unresolved problem in this area is that DBG_VALUE counts as a use but hasOneNonDbgUse() can get a bit expensive.

Running LLVM test suite with -fglobal-isel on an AArch64 EC2 instance (2 CPUs, 4GB):
Current implementation: 22m43.224s
Bottom-up implementation: 22m47.165s

I see Amara asked if for clarification on this and it's just compile time. Was runtime similar too?

More important, not all patterns would be matched! The reason is that there are C++ matchers which perform a top-down match. One example is the rule fold_global_offset from the AArch64PreLegalizerCombiner. This rule matches a G_GLOBAL_VALUE only, but the C++ matcher looks at the uses of the defined value, which basically means that the matcher reverses the order in which matches are made. As a result, the bottom-up matcher is not aware that it has to apply another rule. I think this case can be fixed by changing the matching pattern. The question is if this is desirable, because it would add restrictions to what a C++ matcher is allowed to do.

I'm certain there's more cases like that. FWIW, we try not to do that in our target but there's occasions where doing it allows better decisions.

The information required for tests is print in YAML format. However, the output is not yet the same on all platforms. The current solution is to re-assign the encoding in a deterministic way. This code is responsible for the larger part of the increased compile time, and should be removed.

It's not important but I'm a little sad to lose the graphviz output. I found being able to render the matcher in dot pretty useful for the early debugging

The old matcher generator implementation is still there, but not used.

If the code is no longer reachable then we should remove it. That said, I would expect this change to have a fairly big effect on our tests and perf so we might be glad of a temporary escape route when it reaches our downstream repo to avoid blocking further intake of upstream commits until we've sorted out the consequences on our target. As a result, I'd say the old one should be kept for the moment but be deleted a couple weeks after this.

[aemerson]

In D141135#4047516, @Kai wrote:

In D141135#4046071, @aemerson wrote:

In D141135#4036756, @Kai wrote:

• Visit of changed instructions in the Combiner is now done iteratively.
• The array with the rules to execute in the generated source is a bit more compact.

Running LLVM test suite with -fglobal-isel on an AArch64 EC2 instance (2 CPUs, 4GB):
Current implementation: 22m43.224s
Bottom-up implementation: 22m47.165s

Size of the binaries:
Current implementation: llc 127.280.024, clang 217.540.416
Bottom-up implementation: llc 127.026.960, clang 217.291.456

I haven't had time to properly look at the implementation, but a question on this. When you say "running the test suite", are you talking about building the test suite with -fglobal-isel? Not running the generated code right?

Yes, for the time measurement I referred to building the test suite, as this shows the impact of my code on the compile time. (I also ran the test suite to make sure that there are no regressions.)

Secondly, you mentioned that this is a drop on replacement for the existing matcher, yet we're seeing some code size differences. Do you know why?

Yes. The matcher my code generates has a simpler structure. It is basically:

• Calculate the match set number for the current instruction, which is either a constant assignment or a table lookup.
• Translate the match set number to a list of rules to execute, which is another table lookup.
• Run the rules

The current matcher has a couple of if and switch statements before the rules are run. I noted that the generated tables are much more compact than the code generated from if and switch. The overall price my implementation pays is a greater construction time in llvm-tblgen.

Oh I thought the llc/clang binaries were different because of the codegen being different. If it's because of implementation of the combiner itself being different then it's fine.

[aemerson]

From my reading of this review, it seems no one has a fundamental disagreement with the overall direction. In that case, I think it's ready to go into a conventional implementation review.

llvm/utils/TableGen/GlobalISel/GIMatchTreeAutomaton.cpp

89

dimension

113

Yes, if this leaks (even harmlessly in the case of llvm-tblgen) it could break bots running valgrind etc.

862

Please document more what you mean by Chase and HOD sets and why this mapping is needed. It wasn't obvious to me that HOD here meant "Hoffman and O'Donnell".

869–870

std::fill()?

[Pierre-vh]

Hi,
Just checking in - is this something that you're still interested in landing?

I was excited to see the GISel TableGen backend getting some love, especially since it enables better MIR pattern matching (which I'm interested in) so I was looking forward to this eventually landing.
Of course no pressure, after all GISel isn't the default so this isn't a priority - I was just wondering what the state of this diff was :)
Thanks

[Pierre-vh]

(Marking as request changes to remove this from review queues)
See https://discourse.llvm.org/t/rfc-matchtable-based-globalisel-combiners/71457/13 which is another implementation that makes this unfortunately obsolete.

llvm/include/llvm/CodeGen/GlobalISel/CombinerInfo.h

 
 #ifndef LLVM_CODEGEN_GLOBALISEL_COMBINERINFO_H
 #define LLVM_CODEGEN_GLOBALISEL_COMBINERINFO_H
 
 #include <cassert>
 namespace llvm {
 
 class GISelChangeObserver;
+template <typename KeyT, typename ValueT,
+          typename KeyInfoT,
+          typename BucketT>
+class DenseMap;
 class LegalizerInfo;
 class MachineInstr;
 class MachineIRBuilder;
 
 // Contains information relevant to enabling/disabling various combines for a
 // pass.
 class CombinerInfo {
 public:
public:
   /// Use Observer to report the creation, modification, and erasure of
   /// instructions. GISelChangeObserver will automatically report certain
   /// kinds of operations. These operations are:
   /// * Instructions that are newly inserted into the MachineFunction
   /// * Instructions that are erased from the MachineFunction.
   ///
   /// However, it is important to report instruction modification and this is
   /// not automatic.
-  virtual bool combine(GISelChangeObserver &Observer, MachineInstr &MI,
+  virtual bool combine(DenseMap<MachineInstr *, unsigned> &MatchSets,
+                       GISelChangeObserver &Observer, MachineInstr &MI,
                        MachineIRBuilder &B) const = 0;
 };
 } // namespace llvm
 
 #endif

llvm/include/llvm/CodeGen/GlobalISel/GISelWorkList.h

#endif
     MachineInstr *I;
     do {
       I = Worklist.pop_back_val();
     } while(!I);
     assert(I && "Pop back on empty worklist");
     WorklistMap.erase(I);
     return I;
   }
+
+  bool contains(const MachineInstr *I) {
+    auto It = WorklistMap.find(I);
+    return It != WorklistMap.end();
+  }
 };
 
 } // end namespace llvm.
 
 #endif

llvm/lib/CodeGen/GlobalISel/Combiner.cpp

 } // end namespace llvm
 
 namespace {
 /// This class acts as the glue the joins the CombinerHelper to the overall
 /// Combine algorithm. The CombinerHelper is intended to report the
 /// modifications it makes to the MIR to the GISelChangeObserver and the
 /// observer subclass will act on these events. In this case, instruction
 /// erasure will cancel any future visits to the erased instruction and
-/// instruction creation will schedule that instruction for a future visit.
+/// instruction creation and change will schedule that instruction for a future
+/// visit. In addition, all instructions which lay on paths between the
+/// created/changed instructions and the scheduled instructions are scheduled
+/// for a revisit.
 /// Other Combiner implementations may require more complex behaviour from
 /// their GISelChangeObserver subclass.
 class WorkListMaintainer : public GISelChangeObserver {
+  MachineRegisterInfo *MRI;
   using WorkListTy = GISelWorkList<512>;
   WorkListTy &WorkList;
   /// The instructions that have been created but we want to report once they
   /// have their operands. This is only maintained if debug output is requested.
 #ifndef NDEBUG
   SetVector<const MachineInstr *> CreatedInstrs;
 #endif
 
+  SmallVector<std::pair<MachineInstr *, bool>, 512> WorkStack;
+
 public:
-  WorkListMaintainer(WorkListTy &WorkList) : WorkList(WorkList) {}
+  WorkListMaintainer(MachineRegisterInfo *MRI, WorkListTy &WorkList)
+      : MRI(MRI), WorkList(WorkList) {}
   virtual ~WorkListMaintainer() = default;
 
   void erasingInstr(MachineInstr &MI) override {
     LLVM_DEBUG(dbgs() << "Erasing: " << MI << "\n");
     WorkList.remove(&MI);
   }
   void createdInstr(MachineInstr &MI) override {
     LLVM_DEBUG(dbgs() << "Creating: " << MI << "\n");
-    WorkList.insert(&MI);
+    WorkStack.emplace_back(&MI, false);
     LLVM_DEBUG(CreatedInstrs.insert(&MI));
   }
   void changingInstr(MachineInstr &MI) override {
     LLVM_DEBUG(dbgs() << "Changing: " << MI << "\n");
-    WorkList.insert(&MI);
+    // No need to record the annoucement.
   }
   void changedInstr(MachineInstr &MI) override {
     LLVM_DEBUG(dbgs() << "Changed: " << MI << "\n");
-    WorkList.insert(&MI);
+    WorkStack.emplace_back(&MI, false);
   }
 
   void reportFullyCreatedInstrs() {
     LLVM_DEBUG(for (const auto *MI
                     : CreatedInstrs) {
       dbgs() << "Created: ";
       MI->print(dbgs());
     });
     LLVM_DEBUG(CreatedInstrs.clear());
   }
-};
+
+  // For each changed/created node, add the path from the node to the root of
+  // the tree by following the use edges. For these nodes, the match sets in the
+  // underlying combiner may be invalid, and adding them to the WorkList ensures
+  // that the match sets are recalculated in the correct order.
+  void updateWorklist() {
+    SmallPtrSet<MachineInstr *, 4> Visited;
+
+    while (!WorkStack.empty()) {
+      auto &MIFlagPair = WorkStack.back();
+      MachineInstr *MI = MIFlagPair.first;
+      if (WorkList.contains(MI)) {
+        WorkStack.pop_back();
+      } else if (MIFlagPair.second) {
+        WorkStack.pop_back();
+        WorkList.insert(MI);
+      } else if (!Visited.contains(MI)) {
+        Visited.insert(MI);
+        MIFlagPair.second = true;
+        for (auto Op : MI->operands()) {
+          if (!Op.isReg() || !Op.isDef())
+            continue;
+          for (auto &UseMI : MRI->use_nodbg_instructions(Op.getReg()))
+            WorkStack.emplace_back(&UseMI, false);
         }
+      } else
+        WorkStack.pop_back();
+    }
+  }
+};
+} // namespace
 
 Combiner::Combiner(CombinerInfo &Info, const TargetPassConfig *TPC)
     : CInfo(Info), TPC(TPC) {
   (void)this->TPC; // FIXME: Remove when used.
 }
 
 bool Combiner::combineMachineInstrs(MachineFunction &MF,
                                     GISelCSEInfo *CSEInfo) {
   // If the ISel pipeline failed, do not bother running this pass.
   // FIXME: Should this be here or in individual combiner passes.
   if (MF.getProperties().hasProperty(
           MachineFunctionProperties::Property::FailedISel))
     return false;
 
   Builder =
       CSEInfo ? std::make_unique<CSEMIRBuilder>() : std::make_unique<MachineIRBuilder>();
   MRI = &MF.getRegInfo();
   Builder->setMF(MF);
   if (CSEInfo)
     Builder->setCSEInfo(CSEInfo);
 
   LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n');
 
   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
 
   bool MFChanged = false;
   bool Changed;
   MachineIRBuilder &B = *Builder;
+  DenseMap<MachineInstr *, unsigned> MatchSets;
 
   do {
     // Collect all instructions. Do a post order traversal for basic blocks and
     // insert with list bottom up, so while we pop_back_val, we'll traverse top
     // down RPOT.
     Changed = false;
     GISelWorkList<512> WorkList;
-    WorkListMaintainer Observer(WorkList);
+    WorkListMaintainer Observer(MRI, WorkList);
     GISelObserverWrapper WrapperObserver(&Observer);
     if (CSEInfo)
       WrapperObserver.addObserver(CSEInfo);
     RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
     for (MachineBasicBlock *MBB : post_order(&MF)) {
       for (MachineInstr &CurMI :
            llvm::make_early_inc_range(llvm::reverse(*MBB))) {
         // Erase dead insts before even adding to the list.
         if (isTriviallyDead(CurMI, *MRI)) {
           LLVM_DEBUG(dbgs() << CurMI << "Is dead; erasing.\n");
           llvm::salvageDebugInfo(*MRI, CurMI);
           CurMI.eraseFromParent();
           continue;
         }
         WorkList.deferred_insert(&CurMI);
       }
     }
     WorkList.finalize();
+    MatchSets.reserve(WorkList.size());
     // Main Loop. Process the instructions here.
     while (!WorkList.empty()) {
       MachineInstr *CurrInst = WorkList.pop_back_val();
       LLVM_DEBUG(dbgs() << "\nTry combining " << *CurrInst;);
-      Changed |= CInfo.combine(WrapperObserver, *CurrInst, B);
+      Changed |= CInfo.combine(MatchSets, WrapperObserver, *CurrInst, B);
+      Observer.updateWorklist();
       Observer.reportFullyCreatedInstrs();
     }
     MFChanged |= Changed;
   } while (Changed);
 
 #ifndef NDEBUG
   if (CSEInfo) {
     if (auto E = CSEInfo->verify()) {
       errs() << E << '\n';
       assert(false && "CSEInfo is not consistent. Likely missing calls to "
                       "observer on mutations.");
     }
   }
 #endif
   return MFChanged;
 }

llvm/lib/Target/AArch64/GISel/AArch64O0PreLegalizerCombiner.cpp

AArch64O0PreLegalizerCombinerInfo(bool EnableOpt, bool OptSize, bool MinSize,
                                     MachineDominatorTree *MDT)
       : CombinerInfo(/*AllowIllegalOps*/ true, /*ShouldLegalizeIllegal*/ false,
                      /*LegalizerInfo*/ nullptr, EnableOpt, OptSize, MinSize),
         KB(KB), MDT(MDT) {
     if (!GeneratedRuleCfg.parseCommandLineOption())
       report_fatal_error("Invalid rule identifier");
   }
 
-  bool combine(GISelChangeObserver &Observer, MachineInstr &MI,
+  bool combine(DenseMap<MachineInstr *, unsigned> &MatchSets,
+               GISelChangeObserver &Observer, MachineInstr &MI,
                MachineIRBuilder &B) const override;
 };
 
-bool AArch64O0PreLegalizerCombinerInfo::combine(GISelChangeObserver &Observer,
-                                                MachineInstr &MI,
-                                                MachineIRBuilder &B) const {
+bool AArch64O0PreLegalizerCombinerInfo::combine(
+    DenseMap<MachineInstr *, unsigned> &MatchSets,
+    GISelChangeObserver &Observer, MachineInstr &MI,
   CombinerHelper Helper(Observer, B, /*IsPreLegalize*/ true, KB, MDT);
   AArch64GenO0PreLegalizerCombinerHelper Generated(GeneratedRuleCfg, Helper);
 
-  if (Generated.tryCombineAll(Observer, MI, B))
+  if (Generated.tryCombineAll(MatchSets, Observer, MI, B))
     return true;
 
   unsigned Opc = MI.getOpcode();
   switch (Opc) {
   case TargetOpcode::G_CONCAT_VECTORS:
     return Helper.tryCombineConcatVectors(MI);
   case TargetOpcode::G_SHUFFLE_VECTOR:
     return Helper.tryCombineShuffleVector(MI);

llvm/lib/Target/AArch64/GISel/AArch64PostLegalizerCombiner.cpp

AArch64PostLegalizerCombinerInfo(bool EnableOpt, bool OptSize, bool MinSize,
                                    MachineDominatorTree *MDT)
       : CombinerInfo(/*AllowIllegalOps*/ true, /*ShouldLegalizeIllegal*/ false,
                      /*LegalizerInfo*/ nullptr, EnableOpt, OptSize, MinSize),
         KB(KB), MDT(MDT) {
     if (!GeneratedRuleCfg.parseCommandLineOption())
       report_fatal_error("Invalid rule identifier");
   }
 
-  bool combine(GISelChangeObserver &Observer, MachineInstr &MI,
+  bool combine(DenseMap<MachineInstr *, unsigned> &MatchSets,
+               GISelChangeObserver &Observer, MachineInstr &MI,
                MachineIRBuilder &B) const override;
 };
 
-bool AArch64PostLegalizerCombinerInfo::combine(GISelChangeObserver &Observer,
-                                               MachineInstr &MI,
-                                               MachineIRBuilder &B) const {
+bool AArch64PostLegalizerCombinerInfo::combine(
+    DenseMap<MachineInstr *, unsigned> &MatchSets,
+    GISelChangeObserver &Observer, MachineInstr &MI,
   const auto *LI =
       MI.getParent()->getParent()->getSubtarget().getLegalizerInfo();
   CombinerHelper Helper(Observer, B, /*IsPreLegalize*/ false, KB, MDT, LI);
   AArch64GenPostLegalizerCombinerHelper Generated(GeneratedRuleCfg);
-  return Generated.tryCombineAll(Observer, MI, B, Helper);
+  return Generated.tryCombineAll(MatchSets, Observer, MI, B, Helper);
 }
 
 #define AARCH64POSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_CPP
 #include "AArch64GenPostLegalizeGICombiner.inc"
 #undef AARCH64POSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_CPP
 
 class AArch64PostLegalizerCombiner : public MachineFunctionPass {
 public:

llvm/lib/Target/AArch64/GISel/AArch64PostLegalizerLowering.cpp

public:
   AArch64PostLegalizerLoweringInfo(bool OptSize, bool MinSize)
       : CombinerInfo(/*AllowIllegalOps*/ true, /*ShouldLegalizeIllegal*/ false,
                      /*LegalizerInfo*/ nullptr, /*OptEnabled = */ true, OptSize,
                      MinSize) {
     if (!GeneratedRuleCfg.parseCommandLineOption())
       report_fatal_error("Invalid rule identifier");
   }
 
-  bool combine(GISelChangeObserver &Observer, MachineInstr &MI,
+  bool combine(DenseMap<MachineInstr *, unsigned> &MatchSets,
+               GISelChangeObserver &Observer, MachineInstr &MI,
                MachineIRBuilder &B) const override;
 };
 
-bool AArch64PostLegalizerLoweringInfo::combine(GISelChangeObserver &Observer,
-                                               MachineInstr &MI,
-                                               MachineIRBuilder &B) const {
+bool AArch64PostLegalizerLoweringInfo::combine(
+    DenseMap<MachineInstr *, unsigned> &MatchSets,
+    GISelChangeObserver &Observer, MachineInstr &MI,
   CombinerHelper Helper(Observer, B, /* IsPreLegalize*/ false);
   AArch64GenPostLegalizerLoweringHelper Generated(GeneratedRuleCfg);
-  return Generated.tryCombineAll(Observer, MI, B, Helper);
+  return Generated.tryCombineAll(MatchSets, Observer, MI, B, Helper);
 }
 
 #define AARCH64POSTLEGALIZERLOWERINGHELPER_GENCOMBINERHELPER_CPP
 #include "AArch64GenPostLegalizeGILowering.inc"
 #undef AARCH64POSTLEGALIZERLOWERINGHELPER_GENCOMBINERHELPER_CPP
 
 class AArch64PostLegalizerLowering : public MachineFunctionPass {
 public:

llvm/lib/Target/AArch64/GISel/AArch64PreLegalizerCombiner.cpp

AArch64PreLegalizerCombinerInfo(bool EnableOpt, bool OptSize, bool MinSize,
                                   GISelKnownBits *KB, MachineDominatorTree *MDT)
       : CombinerInfo(/*AllowIllegalOps*/ true, /*ShouldLegalizeIllegal*/ false,
                      /*LegalizerInfo*/ nullptr, EnableOpt, OptSize, MinSize),
         KB(KB), MDT(MDT) {
     if (!GeneratedRuleCfg.parseCommandLineOption())
       report_fatal_error("Invalid rule identifier");
   }
 
-  bool combine(GISelChangeObserver &Observer, MachineInstr &MI,
+  bool combine(DenseMap<MachineInstr *, unsigned> &MatchSets,
+               GISelChangeObserver &Observer, MachineInstr &MI,
                MachineIRBuilder &B) const override;
 };
 
-bool AArch64PreLegalizerCombinerInfo::combine(GISelChangeObserver &Observer,
-                                              MachineInstr &MI,
-                                              MachineIRBuilder &B) const {
+bool AArch64PreLegalizerCombinerInfo::combine(
+    DenseMap<MachineInstr *, unsigned> &MatchSets,
+    GISelChangeObserver &Observer, MachineInstr &MI,
   const auto *LI = MI.getMF()->getSubtarget().getLegalizerInfo();
   CombinerHelper Helper(Observer, B, /* IsPreLegalize*/ true, KB, MDT, LI);
   AArch64GenPreLegalizerCombinerHelper Generated(GeneratedRuleCfg, Helper);
 
-  if (Generated.tryCombineAll(Observer, MI, B))
+  if (Generated.tryCombineAll(MatchSets, Observer, MI, B))
     return true;
 
   unsigned Opc = MI.getOpcode();
   switch (Opc) {
   case TargetOpcode::G_CONCAT_VECTORS:
     return Helper.tryCombineConcatVectors(MI);
   case TargetOpcode::G_SHUFFLE_VECTOR:
     return Helper.tryCombineShuffleVector(MI);

llvm/lib/Target/AMDGPU/AMDGPUPostLegalizerCombiner.cpp

AMDGPUPostLegalizerCombinerInfo(const GCNSubtarget &Subtarget, bool EnableOpt,
                                   GISelKnownBits *KB, MachineDominatorTree *MDT)
       : CombinerInfo(/*AllowIllegalOps*/ false, /*ShouldLegalizeIllegal*/ true,
                      /*LegalizerInfo*/ LI, EnableOpt, OptSize, MinSize),
         KB(KB), MDT(MDT), Subtarget(Subtarget) {
     if (!GeneratedRuleCfg.parseCommandLineOption())
       report_fatal_error("Invalid rule identifier");
   }
 
-  bool combine(GISelChangeObserver &Observer, MachineInstr &MI,
+  bool combine(DenseMap<MachineInstr *, unsigned> &MatchSets,
+               GISelChangeObserver &Observer, MachineInstr &MI,
                MachineIRBuilder &B) const override;
 };
 
-bool AMDGPUPostLegalizerCombinerInfo::combine(GISelChangeObserver &Observer,
+bool AMDGPUPostLegalizerCombinerInfo::combine(DenseMap<MachineInstr *, unsigned> &MatchSets,
+                                              GISelChangeObserver &Observer,
                                               MachineInstr &MI,
                                               MachineIRBuilder &B) const {
   AMDGPUCombinerHelper Helper(Observer, B, /*IsPreLegalize*/ false, KB, MDT,
                               LInfo);
   AMDGPUPostLegalizerCombinerHelper PostLegalizerHelper(B, Helper);
   AMDGPUGenPostLegalizerCombinerHelper Generated(
       GeneratedRuleCfg, Helper, PostLegalizerHelper, Subtarget);
 
-  if (Generated.tryCombineAll(Observer, MI, B))
+  if (Generated.tryCombineAll(MatchSets, Observer, MI, B))
     return true;
 
   switch (MI.getOpcode()) {
   case TargetOpcode::G_SHL:
   case TargetOpcode::G_LSHR:
   case TargetOpcode::G_ASHR:
     // On some subtargets, 64-bit shift is a quarter rate instruction. In the
     // common case, splitting this into a move and a 32-bit shift is faster and

llvm/lib/Target/AMDGPU/AMDGPUPreLegalizerCombiner.cpp

AMDGPUPreLegalizerCombinerInfo(bool EnableOpt, bool OptSize, bool MinSize,
                                   GISelKnownBits *KB, MachineDominatorTree *MDT)
       : CombinerInfo(/*AllowIllegalOps*/ true, /*ShouldLegalizeIllegal*/ false,
                      /*LegalizerInfo*/ nullptr, EnableOpt, OptSize, MinSize),
         KB(KB), MDT(MDT) {
     if (!GeneratedRuleCfg.parseCommandLineOption())
       report_fatal_error("Invalid rule identifier");
   }
 
-  bool combine(GISelChangeObserver &Observer, MachineInstr &MI,
+  bool combine(DenseMap<MachineInstr *, unsigned> &MatchSets,
+               GISelChangeObserver &Observer, MachineInstr &MI,
                MachineIRBuilder &B) const override;
 };
 
-bool AMDGPUPreLegalizerCombinerInfo::combine(GISelChangeObserver &Observer,
+bool AMDGPUPreLegalizerCombinerInfo::combine(DenseMap<MachineInstr *, unsigned> &MatchSets,
+                                              GISelChangeObserver &Observer,
                                               MachineInstr &MI,
                                               MachineIRBuilder &B) const {
   const auto *LI = MI.getMF()->getSubtarget().getLegalizerInfo();
   AMDGPUCombinerHelper Helper(Observer, B, /*IsPreLegalize*/ true, KB, MDT, LI);
   AMDGPUPreLegalizerCombinerHelper PreLegalizerHelper(B, Helper);
   AMDGPUGenPreLegalizerCombinerHelper Generated(GeneratedRuleCfg, Helper,
                                                 PreLegalizerHelper);
 
-  if (Generated.tryCombineAll(Observer, MI, B))
+  if (Generated.tryCombineAll(MatchSets, Observer, MI, B))
     return true;
 
   switch (MI.getOpcode()) {
   case TargetOpcode::G_CONCAT_VECTORS:
     return Helper.tryCombineConcatVectors(MI);
   case TargetOpcode::G_SHUFFLE_VECTOR:
     return Helper.tryCombineShuffleVector(MI);
   }

llvm/lib/Target/AMDGPU/AMDGPURegBankCombiner.cpp

AMDGPURegBankCombinerInfo(bool EnableOpt, bool OptSize, bool MinSize,
                                   GISelKnownBits *KB, MachineDominatorTree *MDT)
       : CombinerInfo(/*AllowIllegalOps*/ false, /*ShouldLegalizeIllegal*/ true,
                      /*LegalizerInfo*/ LI, EnableOpt, OptSize, MinSize),
         KB(KB), MDT(MDT) {
     if (!GeneratedRuleCfg.parseCommandLineOption())
       report_fatal_error("Invalid rule identifier");
   }
 
-  bool combine(GISelChangeObserver &Observer, MachineInstr &MI,
+  bool combine(DenseMap<MachineInstr *, unsigned> &MatchSets,
+               GISelChangeObserver &Observer, MachineInstr &MI,
                MachineIRBuilder &B) const override;
 };
 
-bool AMDGPURegBankCombinerInfo::combine(GISelChangeObserver &Observer,
+bool AMDGPURegBankCombinerInfo::combine(DenseMap<MachineInstr *, unsigned> &MatchSets,
+                                              GISelChangeObserver &Observer,
                                               MachineInstr &MI,
                                               MachineIRBuilder &B) const {
   CombinerHelper Helper(Observer, B, /* IsPreLegalize*/ false, KB, MDT);
   AMDGPURegBankCombinerHelper RegBankHelper(B, Helper);
   AMDGPUGenRegBankCombinerHelper Generated(GeneratedRuleCfg, Helper,
                                            RegBankHelper);
 
-  if (Generated.tryCombineAll(Observer, MI, B))
+  if (Generated.tryCombineAll(MatchSets, Observer, MI, B))
     return true;
 
   return false;
 }
 
 #define AMDGPUREGBANKCOMBINERHELPER_GENCOMBINERHELPER_CPP
 #include "AMDGPUGenRegBankGICombiner.inc"
 #undef AMDGPUREGBANKCOMBINERHELPER_GENCOMBINERHELPER_CPP

llvm/lib/Target/Mips/MipsPostLegalizerCombiner.cpp

MipsPostLegalizerCombinerInfo(bool EnableOpt, bool OptSize, bool MinSize,
                                 GISelKnownBits *KB, const MipsLegalizerInfo *LI)
       : CombinerInfo(/*AllowIllegalOps*/ false, /*ShouldLegalizeIllegal*/ true,
                      /*LegalizerInfo*/ LI, EnableOpt, OptSize, MinSize),
         KB(KB) {
     if (!GeneratedRuleCfg.parseCommandLineOption())
       report_fatal_error("Invalid rule identifier");
   }
 
-  bool combine(GISelChangeObserver &Observer, MachineInstr &MI,
+  bool combine(DenseMap<MachineInstr *, unsigned> &MatchSets,
+               GISelChangeObserver &Observer, MachineInstr &MI,
                MachineIRBuilder &B) const override;
 };
 
-bool MipsPostLegalizerCombinerInfo::combine(GISelChangeObserver &Observer,
+bool MipsPostLegalizerCombinerInfo::combine(DenseMap<MachineInstr *, unsigned> &MatchSets,
+                                            GISelChangeObserver &Observer,
                                             MachineInstr &MI,
                                             MachineIRBuilder &B) const {
 
   CombinerHelper Helper(Observer, B, /* IsPreLegalize*/ false, KB,
                         /*DominatorTree*/ nullptr, LInfo);
   MipsGenPostLegalizerCombinerHelper Generated(GeneratedRuleCfg, Helper);
-  return Generated.tryCombineAll(Observer, MI, B, Helper);
+  return Generated.tryCombineAll(MatchSets, Observer, MI, B, Helper);
 }
 
 #define MIPSPOSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_CPP
 #include "MipsGenPostLegalizeGICombiner.inc"
 #undef MIPSPOSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_CPP
 
 // Pass boilerplate
 // ================

llvm/lib/Target/Mips/MipsPreLegalizerCombiner.cpp

 
 namespace {
 class MipsPreLegalizerCombinerInfo : public CombinerInfo {
 public:
   MipsPreLegalizerCombinerInfo()
       : CombinerInfo(/*AllowIllegalOps*/ true, /*ShouldLegalizeIllegal*/ false,
                      /*LegalizerInfo*/ nullptr, /*EnableOpt*/ false,
                      /*EnableOptSize*/ false, /*EnableMinSize*/ false) {}
-  bool combine(GISelChangeObserver &Observer, MachineInstr &MI,
+  bool combine(DenseMap<MachineInstr *, unsigned> &MatchSets,
+               GISelChangeObserver &Observer, MachineInstr &MI,
                MachineIRBuilder &B) const override;
 };
 
-bool MipsPreLegalizerCombinerInfo::combine(GISelChangeObserver &Observer,
+bool MipsPreLegalizerCombinerInfo::combine(DenseMap<MachineInstr *, unsigned> &MatchSets,
+                                           GISelChangeObserver &Observer,
                                            MachineInstr &MI,
                                            MachineIRBuilder &B) const {
   CombinerHelper Helper(Observer, B, /*IsPreLegalize*/ true);
 
   switch (MI.getOpcode()) {
   default:
     return false;
   case TargetOpcode::G_MEMCPY_INLINE:

llvm/test/TableGen/GICombinerEmitter/match-tree-automaton-1.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
+
+// This is the example from the paper of Chase. Please note the values in the
+// lookup table are not exactly the same. The encoding of the match sets depends
+// on the order of calculation, which is not described. However, it is easy to
+// see that the structure is the same, and a bijective function from the values
+// in the paper to the values here in the test case can be easily defined.
+
+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 A : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>;
+def B : I<(outs GPR32:$dst), (ins), []>;
+def C : I<(outs GPR32:$dst), (ins), []>;
+
+def Rule0 : GICombineRule<
+  (defs root:$d),
+  (match (B $t2),
+         (B $t3),
+         (A $t1, $t3, $s1),
+         (A $d, $t1, $t2)),
+  (apply [{ APPLY }])>;
+
+def Rule1 : GICombineRule<
+  (defs root:$d),
+  (match (C $t2),
+         (C $t3),
+         (A $t1, $s1, $t3),
+         (A $d, $t1, $t2)),
+  (apply [{ APPLY }])>;
+
+def MyCombinerHelper: GICombinerHelper<"GenMyCombinerHelper", [
+  Rule0,
+  Rule1
+]>;
+
+// CHECK:     PatternForest: # PF
+// CHECK-DAG:  - 1: B [ ]
+// CHECK-DAG:  - 6: A [ 5, 4 ]
+// CHECK-DAG:  - 3: A [ 2, 1 ]
+// CHECK-DAG:  - 4: C [ ]
+// CHECK-DAG:  - 2: A [ 1, 0 ]
+// CHECK-DAG:  - 0: *
+// CHECK-DAG:  - 5: A [ 0, 4 ]
+// CHECK-NEXT:MatchSets: # R
+// CHECK-DAG:  - [[MS0:[0-9]+]]: [ 0 ]
+// CHECK-DAG:  - [[MS1:[0-9]+]]: [ 0, 1 ]
+// CHECK-DAG:  - [[MS2:[0-9]+]]: [ 0, 2 ]
+// CHECK-DAG:  - [[MS3:[0-9]+]]: [ 0, 3 ]
+// CHECK-DAG:  - [[MS4:[0-9]+]]: [ 0, 4 ]
+// CHECK-DAG:  - [[MS5:[0-9]+]]: [ 0, 5 ]
+// CHECK-DAG:  - [[MS6:[0-9]+]]: [ 0, 2, 5 ]
+// CHECK-DAG:  - [[MS7:[0-9]+]]: [ 0, 5, 6 ]
+// CHECK-NEXT:ChildPatternSets: # P_A
+// CHECK-NEXT:  A:
+// CHECK-NEXT:    - 0: [ 0, 1, 2, 5 ]
+// CHECK-NEXT:    - 1: [ 0, 1, 4 ]
+// CHECK-NEXT:  B:
+// CHECK-NEXT:  C:
+// CHECK-NEXT:RepresenterSets: # S_A
+// CHECK-NEXT:  A:
+// CHECK-NEXT:    - 0:
+// CHECK-DAG:      - [ 0 ]
+// CHECK-DAG:      - [ 0, 1 ]
+// CHECK-DAG:      - [ 0, 2 ]
+// CHECK-DAG:      - [ 0, 5 ]
+// CHECK-DAG:      - [ 0, 2, 5 ]
+// CHECK-NEXT:    - 1:
+// CHECK-DAG:      - [ 0 ]
+// CHECK-DAG:      - [ 0, 1 ]
+// CHECK-DAG:      - [ 0, 4 ]
+// CHECK-NEXT:  B:
+// CHECK-NEXT:  C:
+// CHECK-NEXT:LeafTables:
+// CHECK-DAG:  B: [[MS1]]
+// CHECK-DAG:  C: [[MS4]]
+// CHECK-NEXT:Tables:
+// CHECK-NEXT:  A:
+// CHECK-NEXT:    C:
+// CHECK-DAG:      - [ 0, [[MS0]], [[X00:[0-9]+]] ]
+// CHECK-DAG:      - [ 0, [[MS1]], [[X01:[0-9]+]] ]
+// CHECK-DAG:      - [ 0, [[MS2]], [[X02:[0-9]+]] ]
+// CHECK-DAG:      - [ 0, [[MS3]], [[X00]] ]
+// CHECK-DAG:      - [ 0, [[MS4]], [[X00]] ]
+// CHECK-DAG:      - [ 0, [[MS5]], [[X03:[0-9]+]] ]
+// CHECK-DAG:      - [ 0, [[MS6]], [[X04:[0-9]+]] ]
+// CHECK-DAG:      - [ 0, [[MS7]], [[X03]] ]
+// CHECK-DAG:      - [ 1, [[MS0]], [[X10:[0-9]+]] ]
+// CHECK-DAG:      - [ 1, [[MS1]], [[X11:[0-9]+]] ]
+// CHECK-DAG:      - [ 1, [[MS2]], [[X10]] ]
+// CHECK-DAG:      - [ 1, [[MS3]], [[X10]] ]
+// CHECK-DAG:      - [ 1, [[MS4]], [[X12:[0-9]+]] ]
+// CHECK-DAG:      - [ 1, [[MS5]], [[X10]] ]
+// CHECK-DAG:      - [ 1, [[MS6]], [[X10]] ]
+// CHECK-DAG:      - [ 1, [[MS7]], [[X10]] ]
+// CHECK-NEXT:    T:
+// CHECK-DAG:      - [ [[X00]], [[X10]], [[MS0]] ]
+// CHECK-DAG:      - [ [[X00]], [[X11]], [[MS0]] ]
+// CHECK-DAG:      - [ [[X00]], [[X12]], [[MS5]] ]
+// CHECK-DAG:      - [ [[X01]], [[X10]], [[MS2]] ]
+// CHECK-DAG:      - [ [[X01]], [[X11]], [[MS2]] ]
+// CHECK-DAG:      - [ [[X01]], [[X12]], [[MS6]] ]
+// CHECK-DAG:      - [ [[X02]], [[X10]], [[MS0]] ]
+// CHECK-DAG:      - [ [[X02]], [[X11]], [[MS3]] ]
+// CHECK-DAG:      - [ [[X02]], [[X12]], [[MS5]] ]
+// CHECK-DAG:      - [ [[X03]], [[X10]], [[MS0]] ]
+// CHECK-DAG:      - [ [[X03]], [[X11]], [[MS0]] ]
+// CHECK-DAG:      - [ [[X03]], [[X12]], [[MS7]] ]
+// CHECK-DAG:      - [ [[X04]], [[X10]], [[MS0]] ]
+// CHECK-DAG:      - [ [[X04]], [[X11]], [[MS3]] ]
+// CHECK-DAG:      - [ [[X04]], [[X12]], [[MS7]] ]

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/utils/TableGen/GICombinerEmitter.cpp

 //===----------------------------------------------------------------------===//
 
 #include "CodeGenTarget.h"
 #include "GlobalISel/CodeExpander.h"
 #include "GlobalISel/CodeExpansions.h"
 #include "GlobalISel/GIMatchDag.h"
 #include "GlobalISel/GIMatchDagPredicate.h"
 #include "GlobalISel/GIMatchTree.h"
+#include "GlobalISel/GIMatchTreeAutomaton.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/StringMatcher.h"

 static cl::opt<bool> StopAfterParse(
     "gicombiner-stop-after-parse",
     cl::desc("Stop processing after parsing rules and dump state"),
     cl::cat(GICombinerEmitterCat));
 static cl::opt<bool> StopAfterBuild(
     "gicombiner-stop-after-build",
     cl::desc("Stop processing after building the match tree"),
     cl::cat(GICombinerEmitterCat));
+static cl::opt<bool> CompactYAML(
+    "gicombiner-compact-yaml",
+    cl::desc("Use compact representation of tables in YAML"),
+    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;
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;
+  void generateCodeForTree(raw_ostream &OS,
+                           const GIMatchTreeAutomaton &TreeAutomaton,
+                           unsigned 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 {
if (R->isValueUnset("Rules")) {
       }
       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";
-    }
+void GICombinerEmitter::generateCodeForTree(
+    raw_ostream &OS, const GIMatchTreeAutomaton &TreeAutomaton,
+    unsigned Indent) const {
+
+  // Emit code to calculate the resulting match set number.
+  OS.indent(Indent) << "unsigned MS = 0;\n";
+  TreeAutomaton.emitTransitions(OS, Indent);
+  OS.indent(Indent) << "MatchSets[&MI] = MS;\n";
+
+  // Emit code to select matching rules.
+  TreeAutomaton.emitRuleMapping(OS, Indent);
+
+  // Emit code to execute a rule.
+  if (TreeAutomaton.getMatchingRuleInfos().empty())
     return;
+  OS.indent(Indent) << "for (const unsigned *PatternRuleID = MSToRule[MS]; ; ++PatternRuleID) {\n";
+  OS.indent(Indent + 2) << "switch (*PatternRuleID) {\n";
+  OS.indent(Indent + 2) << "case 0:\n";
+  OS.indent(Indent + 4) << "return false;\n";
+  for (auto &[Idx, Info] : enumerate(TreeAutomaton.getMatchingRuleInfos())) {
+    if (Info.isVariant())
+      continue;
+    OS.indent(Indent + 2) << "case " << (Idx+1) << ":\n";
+    for (unsigned VariantId : Info.getVariants()) {
+      OS.indent(Indent + 2) << "case " << (VariantId+1) << ":\n";
     }
 
-  bool AnyFullyTested = false;
-  for (const auto &Leaf : Tree.possible_leaves()) {
-    OS << Indent << "// Leaf name: " << Leaf.getName() << "\n";
-
-    const CombineRule *Rule = Leaf.getTargetData<CombineRule>();
+    const CombineRule *Rule = Info.getTargetData<CombineRule>();
     const Record &RuleDef = Rule->getDef();
-
-    OS << Indent << "// Rule: " << RuleDef.getName() << "\n"
-       << Indent << "if (!RuleConfig->isRuleDisabled(" << Rule->getID()
+    OS.indent(Indent + 4) << "// Rule: " << RuleDef.getName() << "\n";
+    OS.indent(Indent + 4) << "if (!RuleConfig->isRuleDisabled(" << Rule->getID()
                           << ")) {\n";
 
+    // Emit the MIs[] array.
+    auto EmitMIs = [&OS](unsigned Indent, const GIMatchPatternInfo &Info) {
+      for (auto [Index, Value] : enumerate(Info.instr_infos())) {
+        if (Index)
+          OS.indent(Indent) << "MIs[" << Index << "] = MRI.getVRegDef(MIs["
+                            << Value.getBaseInstrID() << "]->getOperand("
+                            << Value.getFromOpIdx() << ").getReg());\n";
+        else
+          OS.indent(Indent) << "MIs[0] = &MI;\n";
+      }
+    };
+    OS.indent(Indent + 6) << "MachineInstr* MIs[" << Info.getNumInstrInfo()
+                          << "];\n";
+    if (Info.hasVariants()) {
+      OS.indent(Indent + 6) << "if (PatternRuleID == " << Idx << ") {\n";
+      EmitMIs(Indent + 8, Info);
+      for (auto I = Info.getVariants().begin(), E = Info.getVariants().end();
+           I != E;) {
+        unsigned VarId = *I;
+        OS.indent(Indent + 6) << "} else";
+        ++I;
+        if (I != E)
+          OS << " if (PatternRuleID == " << VarId << ")";
+        OS << " {\n";
+        EmitMIs(Indent + 8, TreeAutomaton.getMatchingRuleInfos()[VarId]);
+      }
+      OS.indent(Indent + 6) << "}\n";
+    } else
+      EmitMIs(Indent + 6, Info);
+
+    // Create the set of variable expansions.
     CodeExpansions Expansions;
-    for (const auto &VarBinding : Leaf.var_bindings()) {
+    for (const auto &VarBinding : Info.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);
 
+    // Check that the apply function is defined.
     DagInit *Applyer = RuleDef.getValueAsDag("Apply");
-    if (Applyer->getOperatorAsDef(RuleDef.getLoc())->getName() !=
-        "apply") {
+    if (Applyer->getOperatorAsDef(RuleDef.getLoc())->getName() != "apply") {
       PrintError(RuleDef.getLoc(), "Expected 'apply' operator in Apply DAG");
       return;
     }
 
-    OS << Indent << "  if (1\n";
+    OS.indent(Indent + 6) << "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";
+          OS.indent(Indent + 6) << "  && (\n";
+          OS.indent(Indent + 6)
+              << "       // Predicate: " << Def->getName() << "\n";
+          OS.indent(Indent + 6) << "       " << CondString << "\n";
+          OS.indent(Indent + 6) << "     )\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 << "      "
+      OS.indent(Indent + 6) << "  && [&]() {\n";
+      OS.indent(Indent + 8)
           << CodeExpander(Rule->getMatchingFixupCode()->getValue(), Expansions,
                           RuleDef.getLoc(), ShowExpansions)
-         << '\n'
-         << Indent << "      return true;\n"
-         << Indent << "  }()";
+          << '\n';
+      OS.indent(Indent + 8) << "return true;\n";
+      OS.indent(Indent + 6) << "}()";
     }
-    OS << Indent << "     ) {\n" << Indent << "   ";
+    OS << ") {\n";
 
     if (const StringInit *Code = dyn_cast<StringInit>(Applyer->getArg(0))) {
-      OS << "    LLVM_DEBUG(dbgs() << \"Applying rule '"
-         << RuleDef.getName()
-         << "'\\n\");\n"
+      OS.indent(Indent + 8) << "LLVM_DEBUG(dbgs() << \"Applying rule '"
+                            << RuleDef.getName() << "'\\n\");\n";
+      OS.indent(Indent + 8)
           << CodeExpander(Code->getAsUnquotedString(), Expansions,
                           RuleDef.getLoc(), ShowExpansions)
-         << '\n'
-         << Indent << "    return true;\n"
-         << Indent << "  }\n";
+          << '\n';
+      OS.indent(Indent + 8) << "return true;\n";
+      OS.indent(Indent + 6) << "}\n";
     } else {
       PrintError(RuleDef.getLoc(), "Expected apply code block");
       return;
     }
 
-    OS << Indent << "}\n";
+    OS.indent(Indent + 4) << "}\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";
+    OS.indent(Indent + 4) << "break;\n";
+  } // end of loop over matching rules.
+  OS.indent(Indent + 2) << "}\n";
+  OS.indent(Indent) << "}\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");
+  std::unique_ptr<GIMatchTreeAutomaton> TreeAutomaton;
+  Records.startTimer("Create automaton");
   {
-    GIMatchTreeBuilder TreeBuilder(0);
+    GIMatchTreeAutomatonBuilder TreeBuilder(Records);
     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());
+        TreeBuilder.addLeaf(Rule->getName(), Rule->getID(), Root.index(),
+                            Rule->getMatchDag(), Rule.get());
         HadARoot = true;
       }
       if (!HadARoot)
         PrintFatalError(Rule->getDef().getLoc(), "All rules must have a root");
     }
 
-    Tree = TreeBuilder.run();
+    TreeAutomaton = TreeBuilder.run();
+    if (StopAfterBuild)
+      TreeBuilder.writeYAML(outs());
   }
   if (StopAfterBuild) {
-    Tree->writeDOTGraph(outs());
+    TreeAutomaton->writeYAML(outs(), CompactYAML);
     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"
OS << " {\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"
+     << "    DenseMap<MachineInstr *, unsigned> &MatchSets,\n"
      << "    GISelChangeObserver &Observer,\n"
      << "    MachineInstr &MI,\n"
      << "    MachineIRBuilder &B";
   emitAdditionalHelperMethodArguments(OS, Combiner);
   OS << ") const;\n";
   OS << "};\n\n";
 
   emitNameMatcher(OS);
OS << "#ifdef " << Name.upper() << "_GENCOMBINERHELPER_CPP\n"
      << "      return false;\n"
      << "    if (!Enabled && !setRuleDisabled(Identifier))\n"
      << "      return false;\n"
      << "  }\n"
      << "  return true;\n"
      << "}\n\n";
 
   OS << "bool " << getClassName() << "::tryCombineAll(\n"
+     << "    DenseMap<MachineInstr *, unsigned> &MatchSets,\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, "  ");
+  generateCodeForTree(OS, *TreeAutomaton, 2);
   OS << "\n  return false;\n"
      << "}\n"
      << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_CPP\n";
 }
 
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//

llvm/utils/TableGen/GlobalISel/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   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
+                 GIMatchTreeAutomaton.cpp
                 )

llvm/utils/TableGen/GlobalISel/GIMatchTreeAutomaton.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
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// The general approach is to generate a bottom-up tree matcher as described by
+/// Chase.
+///
+/// References:
+/// Hoffmann, O'Donnel: Pattern Matching in Trees (1982)
+/// https://dl.acm.org/doi/10.1145/322290.322295
+///
+/// Chase: An Improvement to Bottom-up Tree Pattern Matching (1987)
+/// https://dl.acm.org/doi/10.1145/41625.41640
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREEAUTOMATON_H
+#define LLVM_UTILS_TABLEGEN_GIMATCHTREEAUTOMATON_H
+
+#include "GIMatchDag.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+
+#include "../CodeGenTarget.h" // For enumerating instructions.
+
+namespace llvm {
+class raw_ostream;
+class CodeGenInstruction;
+class PatternForestBuilder;
+
+/// Describes the binding of a variable to the matched MIR.
+class GIMatchPatternVariableBinding {
+  /// The name of the variable described by this binding.
+  StringRef Name;
+  // The matched instruction it is bound to.
+  unsigned InstrID;
+  // The matched operand (if appropriate) it is bound to.
+  Optional<unsigned> OpIdx;
+
+public:
+  GIMatchPatternVariableBinding(StringRef Name, unsigned InstrID,
+                                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;
+  }
+};
+
+class GIMatchPatternInstrInfo {
+  // The ID of the instruction which this instruction refers too.
+  unsigned BaseInstrID;
+  // The defining operand.
+  unsigned FromOpIdx;
+
+public:
+  GIMatchPatternInstrInfo(unsigned BaseInstrID, unsigned FromOpIdx)
+      : BaseInstrID(BaseInstrID), FromOpIdx(FromOpIdx) {}
+  unsigned getBaseInstrID() const { return BaseInstrID; }
+  unsigned getFromOpIdx() const { return FromOpIdx; }
+};
+
+class GIMatchPatternInfo {
+public:
+  using const_instr_infos_iterator =
+      SmallVector<GIMatchPatternInstrInfo, 0>::const_iterator;
+  using const_var_binding_iterator =
+      SmallVector<GIMatchPatternVariableBinding, 0>::const_iterator;
+
+private:
+  /// A name for the pattern. This is primarily for debugging.
+  StringRef Name;
+  /// Opaque data the caller of the tree building code understands.
+  void *Data;
+
+  // List of the instructions used in the pattern.
+  // The elements of this list form a tree, with the first element being the
+  // root.
+  SmallVector<GIMatchPatternInstrInfo, 0> InstrInfos;
+
+  // The variable bindings associated with this pattern.
+  SmallVector<GIMatchPatternVariableBinding, 0> VarBindings;
+
+  // Is this info a variant of another info?
+  bool IsVariant;
+
+  // List of variants.
+  SmallVector<unsigned, 8> Variants;
+
+public:
+  GIMatchPatternInfo(StringRef Name, void *Data, bool IsVariant = false)
+      : Name(Name), Data(Data), IsVariant(IsVariant) {}
+
+  StringRef getName() const { return Name; }
+
+  template <class Ty> Ty *getTargetData() const {
+    return static_cast<Ty *>(Data);
+  }
+
+  unsigned add(const GIMatchDagInstr *Instr, unsigned BaseInstrID,
+               unsigned FromOpIdx) {
+    unsigned ID = addInstrInfo(BaseInstrID, FromOpIdx);
+
+    if (Instr) {
+      if (!Instr->getUserAssignedName().empty())
+        bindInstrVariable(Instr->getUserAssignedName(), ID);
+      for (const auto &VarBinding : Instr->user_assigned_operand_names())
+        bindOperandVariable(VarBinding.second, ID, VarBinding.first);
+    }
+
+    return ID;
+  };
+
+  unsigned addInstrInfo(unsigned BaseInstrID, unsigned FromOpIdx) {
+    unsigned ID = InstrInfos.size();
+    InstrInfos.emplace_back(BaseInstrID, FromOpIdx);
+    return ID;
+  }
+  size_t getNumInstrInfo() const { return InstrInfos.size(); }
+  const_instr_infos_iterator instr_infos_begin() const {
+    return InstrInfos.begin();
+  }
+  const_instr_infos_iterator instr_infos_end() const {
+    return InstrInfos.end();
+  }
+  iterator_range<const_instr_infos_iterator> instr_infos() const {
+    return make_range(InstrInfos.begin(), InstrInfos.end());
+  }
+
+  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());
+  }
+
+  bool isVariant() const { return IsVariant; }
+  bool hasVariants() const { return !Variants.empty(); }
+  void addVariant(unsigned VariantID) {
+    Variants.push_back(VariantID);
+  }
+  const SmallVectorImpl<unsigned> &getVariants() const { return Variants; }
+};
+
+class GIMatchTreeAutomaton {
+  friend class PatternForestBuilder;
+
+public:
+  struct Table {
+    // The label.
+    const CodeGenInstruction *Inst;
+    // Dimension of the compression table.
+    unsigned DimC;
+    // The compression table. Dimension is DimC X DimMatchSets.
+    OwningArrayRef<unsigned> C;
+    // Dimension and data of the transition table.
+    OwningArrayRef<unsigned> DimT;
+    OwningArrayRef<unsigned> T;
+  };
+
+private:
+  // Number of match sets. This determines the dimension of the C array.
+  unsigned DimMatchSets;
+
+  // The compression and transistion tables.
+  SmallVector<Table, 0> Tables;
+
+  // LeafTables.
+  SmallVector<std::pair<const CodeGenInstruction *, unsigned>, 0> LeafTables;
+
+  // The matching rules.
+  DenseMap<unsigned, SmallVector<unsigned, 0>> MatchingRules;
+  SmallVector<GIMatchPatternInfo, 0> MatchingRuleInfos;
+
+  void emitTable(raw_ostream &OS, const Table &T, unsigned Indent) const;
+
+public:
+  GIMatchTreeAutomaton(unsigned DimMatchSets);
+  const DenseMap<unsigned, SmallVector<unsigned, 0>> &getMatchingRules() const {
+    return MatchingRules;
+  }
+  const SmallVector<GIMatchPatternInfo, 0> &getMatchingRuleInfos() const {
+    return MatchingRuleInfos;
+  }
+  void emitTransitions(raw_ostream &OS, unsigned Indent) const;
+  void emitRuleMapping(raw_ostream &OS, unsigned Indent) const;
+  void writeYAML(raw_ostream &OS, bool Compact = false) const;
+  void dump() const;
+};
+
+class GIMatchTreeAutomatonBuilder {
+  /// For information about target instructions.
+  const CodeGenTarget Target;
+
+  std::unique_ptr<PatternForestBuilder> PFBuilder;
+
+public:
+  GIMatchTreeAutomatonBuilder(RecordKeeper &Records);
+  ~GIMatchTreeAutomatonBuilder();
+
+  void addLeaf(StringRef Name, uint64_t ID, unsigned RootIdx,
+               const GIMatchDag &MatchDag, void *Data);
+
+  /// Construct the bottom up tree matcher.
+  std::unique_ptr<GIMatchTreeAutomaton> run();
+
+  void writeYAML(raw_ostream &OS) const;
+  void dump() const;
+};
+
+} // end namespace llvm
+#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREEAUTOMATON_H

llvm/utils/TableGen/GlobalISel/GIMatchTreeAutomaton.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
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// Generate a bottom-up tree matcher as described by Chase (1987).
+///
+/// The basic idea of a bottom-up matcher is to associate with each instruction
+/// the set of matching patterns, called the match set. For an instruction
+/// without use operands (a leaf) the match set is easily determined. For any
+/// other instruction, the match set is retrieved with a table lookup, using the
+/// use operands as table indices. As a result, all matching patterns can be
+/// found in linear time.
+///
+/// All patterns to match are known at compile. From these patterns, the match
+/// sets and the table lookups are constructed. The algorithm was first
+/// described by Hoffmann and O'Donnel.
+///  - First enumerate the pattern forest (the set of all subpatterns), and
+///    assign a number to each pattern
+///  - Then calculate the match sets. First, the match sets of patterns with
+///    height 0 are calculated. Based on the result, patterns of height 1 can be
+///    calculated, and so on.
+///  - Finally, the lookup tables con be constructed.
+///
+/// The main disadvantage of this algorithm is that the tables can get very
+/// large. This affects the preprocessing time and space requirements in the
+/// resulting matcher. Chase modified the algorithm to include compression of
+/// the tables. The basic idea is to define an equivalence relation on the set
+/// of of patterns, which can appear as subpatterns of a pattern. Using these
+/// representer sets, the calculation is speed up, and the tables are much
+/// smaller.
+///
+/// The modification to the algorithm includes:
+///  - The representer sets are calculated along the match sets, and the
+///    calculation of the match sets uses the representer sets.
+///  - The lookup tables are only computed for the representer sets.
+///  - An additional mapping from the match sets to the representer sets is
+///    required.
+///
+/// Implementation notes
+/// The nodes of the pattern tree are labled with the instruction name. These
+/// lables are singletons, and implemented using a FoldingVector.
+/// Each pattern is given a numeric encoding. The set of all subpatterns,
+/// called the pattern forest, is also implemented using a FoldingSet.
+/// A set of patterns is implemented as a BitVector, and also given a numeric
+/// encoding. The match sets, which are sets of sets of patterns, are stored in
+/// a DenseMap, using the set of patterns as key, and its numerical encoding as
+/// value.
+/// The implementation assumes that the placeholder * (v in paper of Chase) is
+/// always a member of the pattern forest. It further assumes that the
+/// placeholder * and the set only containing the placeholder have the encoding
+/// 0.
+///
+/// References:
+/// Hoffmann, O'Donnel: Pattern Matching in Trees (1982)
+/// https://dl.acm.org/doi/10.1145/322290.322295
+///
+/// Chase: An Improvement to Bottom-up Tree Pattern Matching (1987)
+/// https://dl.acm.org/doi/10.1145/41625.41640
+//===----------------------------------------------------------------------===//
+
+#include "GIMatchTreeAutomaton.h"
+#include "GIMatchDagPredicate.h"
+
+#include "../CodeGenInstruction.h"
+
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/MapVector.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/TableGen/Error.h"
+#include "llvm/TableGen/Record.h"
+
+#include <map>
+
+#define DEBUG_TYPE "gimatchtreeautomaton"
+
+using namespace llvm;
+
+/*
+  Some remarks about performance and memory usage
+
+  (a)
+  If a dimension of the lookup table is 1 then that dimenion, the corresponding
+  row of the compression table, and the corresponding operand can be omitted.
+
+  (b)
+  The Label and the Pattern class have 1 or 2 OwningArrayRef members. The size
+  of the array is known when the objects are allocated. These additional memory
+  allocations can be avoided by managing that memory together with the object.
+  E.g.
+      static Label *create(const CodeGenInstruction *Inst) {
+      unsigned NumOpnds = Inst->Operands.size() - Inst->Operands.NumDefs;
+      size_t Ofs = alignTo(sizeof(Label), alignof(BitVector));
+      void *Mem = operator new[](Ofs + NumOpnds * sizeof(BitVector));
+      BitVector *PAj = reinterpret_cast<BitVector *>(
+          reinterpret_cast<unsigned char *>(Mem) + Ofs);
+      for (unsigned I = 0, E = NumOpnds; I < E; ++I)
+        new (&PAj[I]) BitVector();
+      return new (Mem) Label(Inst, MutableArrayRef<BitVector>(PAj, NumOpnds));
+    }
+  The objects could also be made smaller by exploting the facts that the size of
+  the array only need to be stored once, and that the pointer(s) to the array(s)
+  are at known offsets from the this pointer.
+
+  (c)
+  The implementation does not care about memory management. A context object
+  holding a bump allocator could be introduced to free most of the memory after
+  the matcher is created.
+*/
+
+namespace llvm {
+
+namespace {
+// The algorithm requires to enumerate all elements of an n-dimensional set
+// product. That is, given sets R_1, ..., R_n, all tuples (r_1, ..., r_n) of
+// R_1 x ... x R_n are enumerated.
+// For convenience and easy understanding, that enumeration is implemented as a
+// C++ range. The template implementation needs to know that type of the set
+// (SetT), and the type of the set elements (ElemT). The only other requirement
+// is that the set type provides a const_iterator.
+// Two specialized version are provided. One uses a BitVector as set type and
+// unsigned as element type. This is mainly provided for performance reasons, as
+// this range is used in the innermost loop, and the implementeation requires
+// less temporary memory. The other version enumerates a set product [0..N_0] x
+// ... X [0..N_n] of integer intervals. The rightmost element changes the
+// fastest, which is compatible with multi-dimensional C++ arrays.
+
+// This version uses iterators to loop over elements of the sets R_i.
+// TODO The implementation is not completely generic - it assumes that the set
+// contains key-value pairs as DenseMap does.
+template <typename SetT, typename ElemT> class EnumSetRangeImpl {
+  const ArrayRef<SetT> &Dimension;
+  SmallVector<typename SetT::const_iterator, 3>
+      Iter;                   // The iterator for each dimension.
+  SmallVector<ElemT, 3> Elem; // The current element for each dimension.
+  bool AtEnd;
+
+public:
+  EnumSetRangeImpl(const ArrayRef<SetT> &Dimension, bool IsAtEnd = false)
+      : Dimension(Dimension), AtEnd(IsAtEnd || !Dimension.size()) {
+    if (AtEnd)
+      return;
+
+    const size_t Dim = Dimension.size();
+
+    // Make room for the iterators and element data.
+    Iter.resize_for_overwrite(Dim);
+    Elem.resize_for_overwrite(Dim);
+
+    // Initialize first element. Return if one of the sets is empty.
+    for (int I = 0, E = Dim; I < E; ++I) {
+      Iter[I] = Dimension[I].begin();
+      if (Iter[I] == Dimension[I].end()) {
+        AtEnd = true;
+        break;
+      }
+      Elem[I] = Iter[I]->first;
+    }
+  }
+
+  EnumSetRangeImpl &operator++() {
+    assert(!AtEnd && "Incrementing iterator over end");
+    for (unsigned I = 0, E = Dimension.size(); I < E; ++I) {
+      unsigned Idx = E - I - 1;
+      if (++Iter[Idx] != Dimension[Idx].end()) {
+        Elem[Idx] = Iter[Idx]->first;
+        break;
+      }
+
+      // Overflow in the left most position indicates all elements are
+      // enumerated.
+      if (Idx == 0) {
+        AtEnd = true;
+        return *this;
+      }
+      Iter[Idx] = Dimension[Idx].begin();
+      Elem[Idx] = Iter[Idx]->first;
+    }
+    return *this;
+  }
+  ArrayRef<ElemT> operator*() const { return Elem; }
+  bool operator!=(const EnumSetRangeImpl &Other) const {
+    assert(Dimension == Other.Dimension && "Comparing different enumerations");
+    if (AtEnd != Other.AtEnd)
+      return true;
+    if (AtEnd && Other.AtEnd)
+      return false;
+    return Elem != Other.Elem;
+  }
+};
+
+// Specialization for sets represented as BitVector.
+template <> class EnumSetRangeImpl<BitVector, unsigned> {
+  const ArrayRef<BitVector> &Dimension;
+  SmallVector<unsigned, 3> Elem;
+  int AtEnd;
+
+public:
+  EnumSetRangeImpl(const ArrayRef<BitVector> &Dimension, bool IsAtEnd = false)
+      : Dimension(Dimension), AtEnd(IsAtEnd || !Dimension.size()) {
+    if (AtEnd)
+      return;
+
+    const size_t Dim = Dimension.size();
+
+    // Make room for the element data.
+    Elem.resize_for_overwrite(Dim);
+
+    // Initialize first element. Return if one of the sets is empty.
+    for (int I = 0, E = Dim; I < E; ++I) {
+      int N = Dimension[I].find_first();
+      if (N == -1) {
+        AtEnd = true;
+        break;
+      }
+      Elem[I] = N;
+    }
+  }
+
+  EnumSetRangeImpl &operator++() {
+    assert(!AtEnd && "Incrementing iterator over end");
+    for (unsigned I = 0, E = Dimension.size(); I < E; ++I) {
+      unsigned Idx = E - I - 1;
+      int N = Dimension[Idx].find_next(Elem[Idx]);
+      if (N != -1) {
+        Elem[Idx] = N;
+        break;
+      }
+
+      // Overflow in the left most position indicates all elements are
+      // enumerated.
+      if (Idx == 0) {
+        AtEnd = true;
+        return *this;
+      }
+      Elem[Idx] = Dimension[Idx].find_first();
+    }
+    return *this;
+  }
+  ArrayRef<unsigned> operator*() const { return Elem; }
+  bool operator!=(const EnumSetRangeImpl &Other) const {
+    assert(Dimension == Other.Dimension && "Comparing different enumerations");
+    if (AtEnd != Other.AtEnd)
+      return true;
+    if (AtEnd && Other.AtEnd)
+      return false;
+    return Elem != Other.Elem;
+  }
+};
+
+// Specialization for set product of integer intervals.
+template <> class EnumSetRangeImpl<unsigned, unsigned> {
+  const ArrayRef<unsigned> &Dimension;
+  SmallVector<unsigned, 3> Elem;
+  int AtEnd;
+
+public:
+  EnumSetRangeImpl(const ArrayRef<unsigned> &Dimension, bool IsAtEnd = false)
+      : Dimension(Dimension), AtEnd(IsAtEnd || !Dimension.size()) {
+    if (AtEnd)
+      return;
+
+    const size_t Dim = Dimension.size();
+
+    // Make room for the element data.
+    Elem.resize_for_overwrite(Dim);
+
+    // Initialize first element. Return if one of the sets is empty.
+    for (int I = 0, E = Dim; I < E; ++I)
+      Elem[I] = 0;
+  }
+
+  EnumSetRangeImpl &operator++() {
+    assert(!AtEnd && "Incrementing iterator over end");
+    for (unsigned I = 0, E = Dimension.size(); I < E; ++I) {
+      unsigned Idx = E - I - 1;
+      unsigned N = Elem[Idx] + 1;
+      if (N < Dimension[Idx]) {
+        Elem[Idx] = N;
+        break;
+      }
+
+      // Overflow in the left most position indicates all elements are
+      // enumerated.
+      if (Idx == 0) {
+        AtEnd = true;
+        return *this;
+      }
+      Elem[Idx] = 0;
+    }
+    return *this;
+  }
+  ArrayRef<unsigned> operator*() const { return Elem; }
+  bool operator!=(const EnumSetRangeImpl &Other) const {
+    assert(Dimension == Other.Dimension && "Comparing different enumerations");
+    if (AtEnd != Other.AtEnd)
+      return true;
+    if (AtEnd && Other.AtEnd)
+      return false;
+    return Elem != Other.Elem;
+  }
+};
+
+template <typename SetT, typename ElemT> class EnumSet {
+
+  using iterator = EnumSetRangeImpl<SetT, ElemT>;
+
+  const ArrayRef<SetT> Dimension;
+
+public:
+  EnumSet(ArrayRef<SetT> Dimension) : Dimension(Dimension) {}
+  iterator begin() { return std::move(iterator(Dimension)); }
+  iterator end() { return std::move(iterator(Dimension, true)); }
+};
+
+// Emit a multi-dimensional array. The dimenions are given in array Dim, and the
+// data is in array Data. The symbols used for opening and closing parenthesis
+// must be provided in Paren.
+void emitMultiDimTable(raw_ostream &OS, unsigned Indent,
+                       const ArrayRef<unsigned> Dim,
+                       const ArrayRef<unsigned> Data, StringRef Paren) {
+  assert(Dim.size() > 0 && "Expected at least one dimension");
+  assert(Paren.size() == 2 && "Expected pair of parenthesis");
+  const char PO = Paren[0];
+  const char PC = Paren[1];
+  const unsigned LastDim = Dim[Dim.size() - 1];
+
+  for (unsigned Idx = 0, End = Data.size(); Idx < End; ++Idx) {
+    // Emit prefix: either chain of opening parenthesis, or a comma.
+    if (Idx % LastDim)
+      OS << ",";
+    else {
+      if (Idx)
+        OS.indent(Indent);
+      OS << PO;
+      for (unsigned PrevFac = LastDim, I = 0, E = Dim.size() - 1; I < E; ++I) {
+        unsigned Fac = PrevFac * Dim[Dim.size() - I - 2];
+        if ((Idx % Fac) != 0)
+          break;
+        Indent += 2;
+        OS << "\n";
+        OS.indent(Indent) << PO;
+        PrevFac = Fac;
+      }
+    }
+
+    // Emit the data element.
+    OS << format(" %u", Data[Idx]);
+
+    // Emit chain of closing parenthesis if required.
+    if ((Idx + 1) % LastDim == 0) {
+      OS << " " << PC;
+      for (unsigned PrevFac = LastDim, I = 0, E = Dim.size() - 1; I < E; ++I) {
+        unsigned Fac = PrevFac * Dim[Dim.size() - I - 2];
+        if (((Idx + 1) % Fac) != 0) {
+          OS << ",\n";
+          break;
+        }
+        Indent -= 2;
+        OS << "\n";
+        OS.indent(Indent) << PC;
+        PrevFac = Fac;
+      }
+    }
+  }
+}
+
+// Ouput a BitVector as a sequence of the set bit's number.
+raw_ostream &operator<<(raw_ostream &OS, const BitVector &BV) {
+  int B = BV.find_first();
+  if (B != -1) {
+    OS << B;
+    while ((B = BV.find_next(B)) != -1)
+      OS << ", " << B;
+  }
+  return OS;
+}
+} // namespace
+
+class PatternForestBuilder {
+  // Each bit vector represents a match set (aka a set of patterns). The value
+  // of the map is the encoding of the match set.
+  using SetOfSetOfPatterns = DenseMap<BitVector, unsigned>;
+
+  // Data structure to represent the label and the patterns that appear as the
+  // j-th child of that label. In Chase's description, a pattern is described as
+  // A[p_0, ..., p_n]. This structure store A (the instruction), the set of
+  // patterns appearing as children P_A (for every operand j), and the
+  // representer set S_A.
+  struct Label : public FoldingSetNode {
+    const CodeGenInstruction *Inst;
+
+    // P_A_j is the set of patterns which appears as the j-th child of patterns
+    // with label A in PF.
+    OwningArrayRef<llvm::BitVector> PA;
+
+    // S_A_j is the set of representer set, basically the intersection of the
+    // match sets R with P_A_j.
+    OwningArrayRef<SetOfSetOfPatterns> SA;
+
+  private:
+    Label(const CodeGenInstruction *Inst)
+        : Inst(Inst), PA(Inst->Operands.size() - Inst->Operands.NumDefs),
+          SA(PA.size()) {}
+
+  public:
+    static Label *create(const CodeGenInstruction *Inst) {
+      assert(Inst && "Expected instruction");
+      return new Label(Inst);
+    }
+
+    void Profile(FoldingSetNodeID &ID) const { ID.AddPointer(Inst->TheDef); }
+
+    bool isCommutable() { return Inst->isCommutable; }
+
+    bool isLeaf() { return getNumUseOpnds() == 0; }
+
+    unsigned getNumDefOpnds() const { return Inst->Operands.NumDefs; }
+    unsigned getNumUseOpnds() const {
+      return Inst->Operands.size() - Inst->Operands.NumDefs;
+    }
+    unsigned getNumOpnds() const { return Inst->Operands.size(); }
+
+    // Update the P_A sets.
+    void updatePA(ArrayRef<unsigned> Opnds) {
+      assert(getNumUseOpnds() == Opnds.size() &&
+             "Unexpected number of operands");
+      for (unsigned J = 0, E = getNumUseOpnds(); J != E; ++J) {
+        if (PA[J].size() <= Opnds[J])
+          PA[J].resize(Opnds[J] + 1);
+        PA[J].set(Opnds[J]);
+      }
+    }
+
+    // Make sure that the P_A sets all have the same size.
+    void normalizePA(unsigned NumOfPatterns) {
+      for (unsigned J = 0, E = PA.size(); J < E; ++J) {
+        if (PA[J].size() != NumOfPatterns) {
+          assert(PA[J].size() <= NumOfPatterns &&
+                 "P_A_j larger than number of patterns");
+          PA[J].resize(NumOfPatterns);
+        }
+      }
+    }
+
+    // Update the representer sets S_A.
+    // Given a match set MS, calculate MS /\ P_A_j for each operand j, and
+    // insert the result into S_A_j. Return true if a new element was inserted
+    // into S_A_j.
+    bool updateSA(const BitVector &MS) {
+      bool Changes = false;
+      for (unsigned J = 0, E = getNumUseOpnds(); J < E; ++J) {
+        BitVector B(MS); // R
+        B &= PA[J];      // R /\ P_A_j
+        if (B.any()) {
+          if (SA[J].insert(std::pair(B, SA[J].size())).second)
+            Changes = true;
+        }
+      }
+      return Changes;
+    }
+  };
+
+  // A pattern, consisting of the label and the children (which are also
+  // patterns). In Chase's paper it is A[p_0, ..., p_n]. Each pattern is encoded
+  // as an integer. The placeholder * (or v in the paper) is modelled as having
+  // no label and no children.
+  struct Pattern : public FoldingSetNode {
+    const Label *A;
+    const OwningArrayRef<unsigned> Opnds;
+    const unsigned Enc; // Numeric encoding of the pattern.
+
+  private:
+    Pattern(const Label *A, unsigned Enc, ArrayRef<unsigned> Opnds)
+        : A(A), Opnds(Opnds), Enc(Enc) {}
+
+  public:
+    static Pattern *create(const Label *A, unsigned Enc,
+                           ArrayRef<unsigned> Opnds) {
+      return new Pattern(A, Enc, Opnds);
+    }
+
+    void Profile(FoldingSetNodeID &ID) const {
+      ID.AddPointer(A);
+      for (unsigned I = 0, E = Opnds.size(); I < E; ++I)
+        ID.AddInteger(Opnds[I]);
+    }
+
+    void dump();
+    void writeYAML(raw_ostream &OS, unsigned Indent) const;
+  };
+
+  // The labels are singletons.
+  FoldingSet<Label> Labels;
+
+  // Set of all patterns, ordered by encoding. The first slot is the placeholder
+  // *.
+  FoldingSet<Pattern> Patterns;
+
+  // Number of patterns. Should always be same as Patterns.size().
+  unsigned NumOfPatterns;
+
+  // The set of the calculated match sets R.
+  SetOfSetOfPatterns MatchSets;
+
+  // Returns the label instance used for the instruction. It ensures that there
+  // is exactly one label for it.
+  Label *getLabel(const CodeGenInstruction *Inst);
+
+  // Binding information for matching rules.
+  SmallVector<GIMatchPatternInfo, 0> MatchingRuleInfos;
+
+  // Mapping between pattern encoding and matching rule info.
+  MapVector<unsigned, SmallVector<unsigned, 0>> MatchingRules;
+
+  // Look up a pattern using its label and the subpatterns.
+  Pattern *lookup(Label *A, ArrayRef<unsigned> Opnds);
+
+  // Add the pattern A [ Opnds ] to the pattern forest.
+  unsigned addPatternToForest(Label *A, ArrayRef<unsigned> Opnds);
+
+  // Update the match set MS with the pattern L [ child patterns ].
+  // Returns true if the pattern was found.
+  bool updateMatchSetWithPattern(BitVector &MS, Label &L,
+                                 ArrayRef<unsigned> ChildPatterns);
+
+#ifndef NDEBUG
+  // Dump a match set.
+  template <typename T> void dumpMS(T Sets, StringRef Name, unsigned No) const;
+#endif
+
+public:
+  PatternForestBuilder();
+  ~PatternForestBuilder();
+  void addPattern(StringRef Name, unsigned RootIdx, const GIMatchDag &MatchDag,
+                  void *Data);
+  void createMatchSets();
+  GIMatchTreeAutomaton *createAutomaton();
+  void dump() const;
+  void writeYAML(raw_ostream &OS) const;
+};
+
+PatternForestBuilder::PatternForestBuilder() : NumOfPatterns(1) {
+  Patterns.InsertNode(Pattern::create(nullptr, 0, ArrayRef<unsigned>()));
+}
+
+PatternForestBuilder::~PatternForestBuilder() = default;
+
+PatternForestBuilder::Label *
+PatternForestBuilder::getLabel(const CodeGenInstruction *Inst) {
+  assert(Inst && "Need instruction to create a label");
+  FoldingSetNodeID ID;
+  ID.AddPointer(Inst->TheDef);
+  void *InsertPoint;
+  Label *L = Labels.FindNodeOrInsertPos(ID, InsertPoint);
+  if (L == nullptr) {
+    L = Label::create(Inst);
+    Labels.InsertNode(L, InsertPoint);
+  }
+  return L;
+}
+
+void PatternForestBuilder::Pattern::dump() { writeYAML(llvm::dbgs(), 0); }
+
+void PatternForestBuilder::Pattern::writeYAML(raw_ostream &OS,
+                                              unsigned Indent) const {
+  OS.indent(Indent) << "- " << Enc << ": ";
+  if (A) {
+    OS << A->Inst->TheDef->getName() << " [";
+    for (unsigned I = 0, E = Opnds.size(); I < E; ++I) {
+      OS << (I ? ", " : " ") << Opnds[I];
+    }
+    OS << " ]";
+  } else {
+    OS << "*";
+  }
+  OS << "\n";
+}
+
+PatternForestBuilder::Pattern *
+PatternForestBuilder::lookup(Label *A, ArrayRef<unsigned> Opnds) {
+  FoldingSetNodeID ID;
+  ID.AddPointer(A);
+  for (unsigned I = 0, E = Opnds.size(); I < E; ++I)
+    ID.AddInteger(Opnds[I]);
+  void *InsertPoint;
+  return Patterns.FindNodeOrInsertPos(ID, InsertPoint);
+}
+
+unsigned PatternForestBuilder::addPatternToForest(Label *A,
+                                                  ArrayRef<unsigned> Opnds) {
+  FoldingSetNodeID ID;
+  ID.AddPointer(A);
+  for (unsigned I = 0, E = Opnds.size(); I < E; ++I)
+    ID.AddInteger(Opnds[I]);
+  void *InsertPoint;
+  Pattern *P = Patterns.FindNodeOrInsertPos(ID, InsertPoint);
+  if (P)
+    return P->Enc;
+  P = Pattern::create(A, NumOfPatterns, Opnds);
+  // Udate P_A_j.
+  A->updatePA(Opnds);
+  Patterns.InsertNode(P, InsertPoint);
+  ++NumOfPatterns;
+  assert(NumOfPatterns == Patterns.size() && "Counters out of sync");
+  return P->Enc;
+}
+
+void PatternForestBuilder::addPattern(StringRef Name, unsigned RootIdx,
+                                      const GIMatchDag &MatchDag, void *Data) {
+  // Mapping from GIMatchDagInstr to outgoing GIMatchDagEdges.
+  DenseMap<const GIMatchDagInstr *, std::vector<const GIMatchDagEdge *>> Edges;
+
+  // Mapping from GIMatchDagInstr to associated
+  // GIMatchDagPredicateDependencyEdge.
+  DenseMap<const GIMatchDagInstr *,
+           std::vector<const GIMatchDagPredicateDependencyEdge *>>
+      PredEdges;
+
+  // Initializes maps.
+  for (auto *Edge : MatchDag.edges()) {
+    Edges[Edge->getFromMI()].push_back(Edge);
+  }
+  for (auto *PredEdge : MatchDag.predicate_edges()) {
+    PredEdges[PredEdge->getRequiredMI()].push_back(PredEdge);
+  }
+
+  // Lambda to find root element.
+  auto getRoot = [&RootIdx, &MatchDag]() -> const GIMatchDagInstr * {
+    for (const auto &Root : enumerate(MatchDag.roots())) {
+      if (Root.index() == RootIdx)
+        return Root.value();
+    }
+    return nullptr;
+  };
+
+  // Lambda to retrieve the opcode predicate for an instruction.
+  auto getOpcodePredicate =
+      [&](const GIMatchDagInstr *Instr) -> const GIMatchDagOpcodePredicate * {
+    for (auto &PredEgde : PredEdges[Instr]) {
+      if (auto *P =
+              dyn_cast<GIMatchDagOpcodePredicate>(PredEgde->getPredicate())) {
+        assert(PredEgde->getRequiredMO() == nullptr && "Unexpected operand");
+        return P;
+      }
+    }
+    return nullptr;
+  };
+
+  // Recursive lambda to add all edges of tree. It combines 2 traversals:
+  //  - It adds instruction/variable bindings in pre-order.
+  //  - it adds edges in post-order.
+  std::function<unsigned(const GIMatchDagInstr *, GIMatchPatternInfo &,
+                         unsigned, unsigned, unsigned, unsigned &)>
+      addEdge;
+  addEdge = [&](const GIMatchDagInstr *T, GIMatchPatternInfo &Info,
+                unsigned BaseInstrID, unsigned FromMoIdx, unsigned Mask,
+                unsigned &Count) -> unsigned {
+    auto &EdgeList = Edges[T];
+    const CodeGenInstruction *Inst = getOpcodePredicate(T)->getInstr();
+    Label *A = getLabel(Inst);
+    const unsigned MaxOpnds = A->getNumOpnds();
+    const unsigned DefOpnds = A->getNumDefOpnds();
+    BitVector OperandsWithEdge(MaxOpnds);
+    SmallVector<unsigned, 0> Encoding;
+    Encoding.resize(MaxOpnds);
+
+    BaseInstrID = Info.add(T, BaseInstrID, FromMoIdx);
+
+    bool SwapOpnds = false;
+    if (A->isCommutable()) {
+      SwapOpnds = (Mask & (1 << Count)) != 0;
+      ++Count;
+    }
+
+    for (auto &E : EdgeList) {
+      assert(E->getFromMI() == T && "Wrong edge?");
+
+      unsigned Idx = E->getFromMO()->getIdx();
+      if (SwapOpnds) {
+        if (Idx == DefOpnds)
+          Idx = DefOpnds + 1;
+        else if (Idx == DefOpnds + 1)
+          Idx = DefOpnds;
+      }
+      unsigned Enc = addEdge(E->getToMI(), Info, BaseInstrID, Idx, Mask, Count);
+      Encoding[Idx] = Enc;
+      OperandsWithEdge.set(Idx);
+    }
+
+    SmallVector<unsigned, 3> Opnds;
+    // Add accepting Opnd nodes for all other operands.
+    for (auto &Opnd : T->getOperandInfo()) {
+      if (Opnd.isDef())
+        continue;
+      if (OperandsWithEdge[Opnd.getIdx()])
+        Opnds.push_back(Encoding[Opnd.getIdx()]);
+      else
+        Opnds.push_back(0);
+    }
+    assert(A->getNumUseOpnds() == Opnds.size() && "Wrong number of operands");
+    return addPatternToForest(A, Opnds);
+  };
+
+  const GIMatchDagInstr *DAGRoot = getRoot();
+  assert(DAGRoot != nullptr && "Missing root element of DAG");
+
+  // If DAGRoot is an instruction, then traverse all edges originating there.
+  if (getOpcodePredicate(DAGRoot)) {
+    GIMatchPatternInfo Info(Name, Data);
+    unsigned Mask = 0;
+    unsigned Count = 0;
+    unsigned Enc = addEdge(DAGRoot, Info, 0, 0, Mask, Count);
+    unsigned BaseInfoId = MatchingRuleInfos.size();
+    MatchingRuleInfos.push_back(Info);
+    MatchingRules[Enc].push_back(BaseInfoId);
+    for (unsigned I = 1, E = 1 << Count; I < E; ++I) {
+      GIMatchPatternInfo Info(Name, Data, true);
+      Count = 0;
+      Enc = addEdge(DAGRoot, Info, 0, 0, I, Count);
+      if (MatchingRules.find(Enc) == MatchingRules.end()) {
+        unsigned InfoId = MatchingRuleInfos.size();
+        MatchingRuleInfos.push_back(Info);
+        MatchingRules[Enc].push_back(InfoId);
+        MatchingRuleInfos[BaseInfoId].addVariant(InfoId);
+      }
+    }
+  }
+
+  // Process one-of-opcode predicates.
+  std::optional<unsigned> InfoId;
+  SmallVector<unsigned, 3> Opnds;
+  for (auto *PredEdge : PredEdges[DAGRoot]) {
+    if (auto *P = dyn_cast<GIMatchDagOneOfOpcodesPredicate>(
+            PredEdge->getPredicate())) {
+      for (auto *Inst : P->getInstrs()) {
+        if (!InfoId) {
+          // All matches share the same (empty) variable bindings.
+          GIMatchPatternInfo Info(Name, Data);
+          Info.add(DAGRoot, 0, 0);
+          InfoId = MatchingRuleInfos.size();
+          MatchingRuleInfos.push_back(Info);
+        }
+        Label *A = getLabel(Inst);
+        Opnds.resize(A->getNumUseOpnds());
+        unsigned Enc = addPatternToForest(A, Opnds);
+        MatchingRules[Enc].push_back(*InfoId);
+      }
+    }
+  }
+}
+
+bool PatternForestBuilder::updateMatchSetWithPattern(
+    BitVector &MS, Label &L, ArrayRef<unsigned> ChildPatterns) {
+  if (Pattern *P = lookup(&L, ChildPatterns)) {
+    MS.set(P->Enc);
+    return true;
+  }
+  return false;
+}
+
+#ifndef NDEBUG
+template <typename T>
+void PatternForestBuilder::dumpMS(T Sets, StringRef Name, unsigned No) const {
+  llvm::dbgs() << Name << "_" << No << " =\n";
+  for (auto &MS : Sets) {
+    llvm::dbgs() << llvm::format("%6d", MS.second) << " = { " << MS.first
+                 << " }\n";
+  }
+  llvm::dbgs() << "\n";
+}
+#endif
+
+void PatternForestBuilder::createMatchSets() {
+  // Normalize P_A_j, the set of patterns that appear as the j-th child of A.
+  for (auto &L : Labels)
+    L.normalizePA(NumOfPatterns);
+
+  // Initialize match set for placeholder *.
+  const BitVector SetOfStar = BitVector(NumOfPatterns).set(0);
+  MatchSets[SetOfStar] = 0;
+  LLVM_DEBUG(dumpMS(MatchSets, "R", 0));
+
+  // Add the match sets for height 0.
+  for (auto &L : Labels) {
+    if (L.isLeaf()) {
+      if (Pattern *P = lookup(&L, ArrayRef<unsigned>())) {
+        BitVector MS(SetOfStar);
+        MS.set(P->Enc);
+        MatchSets.insert(std::pair(MS, MatchSets.size()));
+      }
+    }
+  }
+  LLVM_DEBUG(dumpMS(MatchSets, "R", 1));
+
+  // Calculate S_A_j_0.
+  for (auto &L : Labels) {
+    for (auto &MS : MatchSets) {
+      L.updateSA(MS.first);
+    }
+    LLVM_DEBUG(for (unsigned I = 0, E = L.getNumUseOpnds(); I < E; ++I)
+                   dumpMS(L.SA[I], Twine("S_A_j_").concat(Twine(I)).str(), 1));
+  }
+
+  unsigned H = 2;
+  // Compute all match sets.
+  for (bool Changes = true; Changes; ++H) {
+    Changes = false;
+
+    // Calculation next match set.
+    for (auto &L : Labels) {
+      assert(L.SA.size() == L.getNumUseOpnds() && "Size missmatch");
+      for (auto PatternSet : EnumSet<SetOfSetOfPatterns, BitVector>(L.SA)) {
+        BitVector MS(NumOfPatterns);
+        for (auto P : EnumSet<BitVector, unsigned>(PatternSet)) {
+          updateMatchSetWithPattern(MS, L, P);
+        }
+        if (MS.any())
+          MatchSets.insert(std::pair(MS.set(0), MatchSets.size()));
+      }
+    }
+    LLVM_DEBUG(dumpMS(MatchSets, "R", H));
+
+    // Calculate S_A_j_i.
+    for (auto &L : Labels) {
+      for (auto &MS : MatchSets) {
+        if (L.updateSA(MS.first))
+          Changes = true;
+      }
+      LLVM_DEBUG(
+          for (unsigned I = 0, E = L.getNumUseOpnds(); I < E; ++I)
+              dumpMS(L.SA[I], Twine("S_A_j_").concat(Twine(I)).str(), H));
+    }
+  }
+}
+
+GIMatchTreeAutomaton *PatternForestBuilder::createAutomaton() {
+  const BitVector SetOfStar = BitVector(NumOfPatterns).set(0);
+
+  const unsigned DimMatchSets = MatchSets.size();
+  GIMatchTreeAutomaton *Automaton = new GIMatchTreeAutomaton(DimMatchSets);
+  for (auto &L : Labels) {
+    // Handle leafs aka instructions with zero operands.
+    if (L.isLeaf()) {
+      // Look up encoding for match set { *, L }.
+      BitVector MS(SetOfStar);
+      updateMatchSetWithPattern(MS, L, ArrayRef<unsigned>());
+      Automaton->LeafTables.emplace_back(L.Inst, MatchSets[MS]);
+      continue;
+    }
+
+    // Handle all other patterns.
+    auto &SA = L.SA;
+    SmallVector<unsigned, 3> DimT;
+    SmallVector<SmallVector<BitVector, 32>, 3>
+        ChaseToHOD; // Mapping from the Chase set encoding to a HOD match set.
+    GIMatchTreeAutomaton::Table T;
+    T.Inst = L.Inst;
+    T.DimC = L.getNumUseOpnds();
+
+    // Initialize the compression tables.
+    T.C = OwningArrayRef<unsigned>(T.DimC * DimMatchSets);
+    for (unsigned I = 0, E = T.C.size(); I < E; ++I)
+      T.C[I] = 0;
+
+    // This loops performs several tasks:
+    // (a) It calculates the size one each dimension of the lookup table.
+    // (b) It calculates the size of the flat lookup table.
+    // (c) It creates the mapping from a Chase set encoding to a HOD set.
+    unsigned Size = 1;
+    for (unsigned Op = 0; Op < T.DimC; ++Op) {
+      // The assign encoding needs some small tweaking, because
+      // the set containing the placeholder * must have 0 as encoding.
+      bool ContainsSetOfStar;
+      unsigned Swap;
+      if (auto It = SA[Op].find(SetOfStar); It != SA[Op].end()) {
+        ContainsSetOfStar = true;
+        Swap = It->second;
+      } else {
+        ContainsSetOfStar = false;
+        Swap = 0;
+      }
+
+      unsigned Sz = SA[Op].size() + !ContainsSetOfStar;
+      SmallVector<BitVector, 32> M;
+      M.resize_for_overwrite(Sz);
+      if (!ContainsSetOfStar)
+        M[0] = SetOfStar;
+      auto &PAj = L.PA[Op];
+      for (auto &[MS, HODSetEnc] : MatchSets) {
+        BitVector B(MS);
+        B &= PAj;
+        auto It = SA[Op].find(B);
+        if (It != SA[Op].end()) {
+          unsigned ChaseSetEnc = It->second;
+          if (ContainsSetOfStar) {
+            if (ChaseSetEnc == Swap)
+              ChaseSetEnc = 0;
+            else if (ChaseSetEnc == 0)
+              ChaseSetEnc = Swap;
+          } else
+            ++ChaseSetEnc;
+          T.C[Op * DimMatchSets + HODSetEnc] = ChaseSetEnc;
+          M[ChaseSetEnc] = MS;
+        }
+      }
+      ChaseToHOD.push_back(std::move(M));
+
+      // Calculate size of flat array and save size of this dimension.
+      Size *= Sz;
+      DimT.push_back(Sz);
+    }
+
+    // Initialize the lookup table.
+    T.T = OwningArrayRef<unsigned>(Size);
+    unsigned TOffset = 0; // Offset into T array.
+    for (auto OpndsChase : EnumSet<unsigned, unsigned>(DimT)) {
+      // OpndsChase[] is Chase set encoding.
+      // Opnds[] is the Hoffmann/O'Donnel match set.
+      SmallVector<BitVector, 3> Opnds;
+      Opnds.resize_for_overwrite(T.DimC);
+      for (unsigned I = 0; I < T.DimC; ++I)
+        Opnds[I] = ChaseToHOD[I][OpndsChase[I]];
+
+      BitVector MS(SetOfStar);
+      for (auto P : EnumSet<BitVector, unsigned>(Opnds))
+        updateMatchSetWithPattern(MS, L, P);
+      auto It = MatchSets.find(MS);
+      if (It != MatchSets.end())
+        T.T[TOffset] = It->second;
+      else
+        T.T[TOffset] = 0;
+      ++TOffset;
+    }
+    // Check for special case size equals 1. It means that the state transition
+    // table contains exactly one element. This happens when the only use of a
+    // non-leaf label has only * appearing as child patterns. E.g. G_AND [*, *].
+    // We can treat this similar to a leaf.
+    if (Size == 1) {
+      Automaton->LeafTables.emplace_back(L.Inst, T.T[0]);
+      continue;
+    }
+    T.DimT = OwningArrayRef<unsigned>(DimT);
+    Automaton->Tables.push_back(std::move(T));
+  }
+
+  // Add the matching rules.
+  for (auto &[MS, MSEnc] : MatchSets) {
+    for (auto R : MatchingRules) {
+      if (MS[R.first]) {
+        Automaton->MatchingRules[MSEnc].append(R.second);
+      }
+    }
+  }
+  Automaton->MatchingRuleInfos = MatchingRuleInfos;
+
+  return Automaton;
+}
+
+void PatternForestBuilder::dump() const { writeYAML(llvm::dbgs()); }
+
+void PatternForestBuilder::writeYAML(raw_ostream &OS) const {
+  auto WriteSet = [&OS](BitVector Set) {
+    OS << "[ " << Set << (Set.any() ? " " : "") << "]";
+  };
+  auto WriteSetOfSets = [&OS, &WriteSet](SetOfSetOfPatterns Sets,
+                                         unsigned Indent, bool EmitIdx) {
+    SmallVector<BitVector, 0> Tmp;
+    Tmp.resize_for_overwrite(Sets.size());
+    for (auto &MS : Sets)
+      Tmp[MS.second] = MS.first;
+    for (auto [Index, MS] : enumerate(Tmp)) {
+      OS.indent(Indent) << "- ";
+      if (EmitIdx)
+        OS << Index << ": ";
+      WriteSet(MS);
+      OS << "\n";
+    }
+  };
+
+  // Sort the labels by name. Printing in sorted order helps with testing.
+  // This can be removed when FileCheck supports CHECK-DAG-NEXT.
+  std::vector<const Label *> SortedLabels;
+  SortedLabels.reserve(Labels.size());
+  for (const Label &L : Labels)
+    SortedLabels.push_back(&L);
+  std::sort(SortedLabels.begin(), SortedLabels.end(),
+            [](const Label *L, const Label *R) {
+                return L->Inst->TheDef->getName() < R->Inst->TheDef->getName();
+            });
+
+  OS << "PatternForest: # PF\n";
+  for (const Pattern &P : Patterns) {
+    P.writeYAML(OS, 2);
+  }
+  OS << "MatchSets: # R\n";
+  WriteSetOfSets(MatchSets, 2, true);
+  OS << "ChildPatternSets: # P_A\n";
+  for (auto *L : SortedLabels) {
+    OS.indent(2) << L->Inst->TheDef->getName() << ":\n";
+    for (unsigned I = 0, E = L->getNumUseOpnds(); I < E; ++I) {
+      OS.indent(4) << "- " << I << ": ";
+      WriteSet(L->PA[I]);
+      OS << "\n";
+    }
+  }
+  OS << "RepresenterSets: # S_A\n";
+  for (auto *L : SortedLabels) {
+    OS.indent(2) << L->Inst->TheDef->getName() << ":\n";
+    for (unsigned I = 0, E = L->getNumUseOpnds(); I < E; ++I) {
+      OS.indent(4) << "- " << I << ": \n";
+      WriteSetOfSets(L->SA[I], 6, false);
+    }
+  }
+}
+
+GIMatchTreeAutomaton::GIMatchTreeAutomaton(unsigned DimMatchSets)
+    : DimMatchSets(DimMatchSets) {}
+
+void GIMatchTreeAutomaton::emitTable(raw_ostream &OS, const Table &T,
+                                     unsigned Indent) const {
+  // Emit compression array.
+  OS.indent(Indent) << "static unsigned C[" << T.DimC << "][" << DimMatchSets
+                    << "] = ";
+  emitMultiDimTable(OS, Indent, {T.DimC, DimMatchSets}, T.C, "{}");
+  OS << ";\n\n";
+
+  // Emit transition table.
+  OS.indent(Indent) << "static unsigned T";
+  for (unsigned I = 0, E = T.DimT.size(); I < E; ++I)
+    OS << "[" << T.DimT[I] << "]";
+  OS << " = ";
+  emitMultiDimTable(OS, Indent, T.DimT, T.T, "{}");
+  OS << ";\n\n";
+}
+
+void GIMatchTreeAutomaton::emitTransitions(raw_ostream &OS,
+                                           unsigned Indent) const {
+  // Avoid emitting an empty switch statement.
+  if (LeafTables.empty() && Tables.empty())
+    return;
+  // Emit code to calculate the match set.
+  OS.indent(Indent) << "switch (MI.getOpcode()) {\n";
+  // First emit the leaf transitions.
+  for (auto &[Inst, MS] : LeafTables) {
+    OS.indent(Indent) << "case " << Inst->Namespace
+                      << "::" << Inst->TheDef->getName() << ":\n";
+    OS.indent(Indent + 2) << "MS = " << MS << ";\n";
+    OS.indent(Indent + 2) << "break;\n";
+  }
+  // Then emit all other transitions.
+  for (auto &T : Tables) {
+    OS.indent(Indent) << "case " << T.Inst->Namespace
+                      << "::" << T.Inst->TheDef->getName() << ": {\n";
+    for (unsigned I = 0, E = T.DimT.size(); I < E; ++I) {
+      unsigned OpNo = T.Inst->Operands.NumDefs + I;
+      OS.indent(Indent + 2) << "unsigned Idx" << I << " = MI.getOperand("
+                            << OpNo << ").isReg()\n";
+      OS.indent(Indent + 2)
+          << "                    ? MatchSets[MRI.getVRegDef(MI.getOperand("
+          << OpNo << ").getReg())]\n";
+      OS.indent(Indent + 2) << "                    : 0;\n";
+    }
+    OS << "\n";
+    emitTable(OS, T, 4);
+    OS.indent(Indent + 2) << "MS = T";
+    for (unsigned I = 0, E = T.DimT.size(); I < E; ++I)
+      OS << "[C[" << I << "][Idx" << I << "]]";
+    OS << ";\n";
+    OS.indent(Indent + 2) << "break;\n  }\n";
+  }
+  OS.indent(Indent) << "}\n";
+}
+
+void GIMatchTreeAutomaton::emitRuleMapping(raw_ostream &OS,
+                                           unsigned Indent) const {
+  OwningArrayRef<unsigned> MSToRule(DimMatchSets);
+  for (auto &I : MSToRule)
+    I = 0;
+  SmallVector<SmallVector<unsigned, 0>, 0> Rules;
+  Rules.push_back(SmallVector<unsigned, 0>());
+  unsigned SizeOfAllRules = 1;
+  for (auto MR : getMatchingRules()) {
+    MSToRule[MR.first] = SizeOfAllRules;
+    SmallVector<unsigned, 0> RulesToExecute;
+    BitVector Filter(getMatchingRuleInfos().size() + 1, true);
+    for (auto PatternRuleID : MR.second) {
+      if (Filter[PatternRuleID]) {
+        RulesToExecute.push_back(PatternRuleID);
+        Filter[PatternRuleID] = false;
+      }
+    }
+    SizeOfAllRules += RulesToExecute.size() + 1;
+    Rules.push_back(RulesToExecute);
+  }
+  // Do not output the tables in case there are no rules to execute.
+  if (Rules.empty())
+    return ;
+  OS.indent(Indent) << "static const unsigned Rules[" << SizeOfAllRules
+                    << "] = {\n";
+  for (auto &[Idx, R] : enumerate(Rules)) {
+    OS.indent(Indent + 2) << "/* " << Idx << " */ ";
+    for (unsigned Val : R)
+      OS << (Val+1) << ", ";
+    OS << "0,\n";
+  }
+  OS.indent(Indent) << "};\n";
+
+  OS.indent(Indent) << "static const unsigned *MSToRule[" << DimMatchSets
+                    << "] = {\n";
+  for (auto &[Idx, Ofs] : enumerate(MSToRule)) {
+    OS.indent(Indent + 2) << "/* " << Idx << " */ &Rules[" << Ofs << "],\n";
+  }
+  OS.indent(Indent) << "};\n";
+}
+
+void GIMatchTreeAutomaton::dump() const { writeYAML(llvm::dbgs(), true); }
+
+void GIMatchTreeAutomaton::writeYAML(raw_ostream &OS, bool Compact) const {
+  // Sort the tables using an index.
+  SmallVector<unsigned, 0> IdxTables;
+  IdxTables.resize_for_overwrite(Tables.size());
+  for (unsigned I = 0, E = Tables.size(); I < E; ++I)
+    IdxTables[I] = I;
+  std::sort(IdxTables.begin(), IdxTables.end(),
+            [&](const unsigned L, const unsigned R) {
+              return Tables[L].Inst->TheDef->getName() <
+                     Tables[R].Inst->TheDef->getName();
+            });
+
+  OS << "LeafTables:\n";
+  for (auto &[Inst, MS] : LeafTables) {
+    OS << "  " << Inst->TheDef->getName() << ": " << MS << "\n";
+  }
+
+  OS << "Tables:\n";
+  if (Compact) {
+    for (auto I : IdxTables) {
+      auto &T = Tables[I];
+      OS << "  " << T.Inst->TheDef->getName() << ":\n";
+      OS << "    C: ";
+      emitMultiDimTable(OS, 8, {T.DimC, DimMatchSets}, T.C, "[]");
+      OS << "\n    T: ";
+      emitMultiDimTable(OS, 8, T.DimT, T.T, "[]");
+      OS << "\n";
+    }
+  } else {
+    for (auto I : IdxTables) {
+      auto &T = Tables[I];
+      OS << "  " << T.Inst->TheDef->getName() << ":\n";
+      OS << "    C:\n";
+      for (unsigned I = 0; I < T.DimC; ++I) {
+        for (unsigned J = 0; J < DimMatchSets; ++J) {
+          OS << "      - [ " << I << ", " << J << ", "
+             << T.C[I * DimMatchSets + J] << " ]\n";
+        }
+      }
+      OS << "    T:\n";
+      unsigned TOffset = 0; // Offset into T array.
+      for (auto Elem : EnumSet<unsigned, unsigned>(T.DimT)) {
+        OS << "      - [ ";
+        for (unsigned I = 0, E = T.DimT.size(); I < E; ++I) {
+          if (I)
+            OS << ", ";
+          OS << Elem[I];
+        }
+        OS << ", " << T.T[TOffset] << " ]\n";
+        ++TOffset;
+      }
+    }
+  }
+}
+
+GIMatchTreeAutomatonBuilder::GIMatchTreeAutomatonBuilder(RecordKeeper &Records)
+    : Target(Records) {
+  PFBuilder = std::make_unique<PatternForestBuilder>();
+}
+
+void GIMatchTreeAutomatonBuilder::addLeaf(StringRef Name, uint64_t ID,
+                                          unsigned RootIdx,
+                                          const GIMatchDag &MatchDag,
+                                          void *Data) {
+  PFBuilder->addPattern(Name, RootIdx, MatchDag, Data);
+}
+
+GIMatchTreeAutomatonBuilder::~GIMatchTreeAutomatonBuilder() = default;
+
+std::unique_ptr<GIMatchTreeAutomaton> GIMatchTreeAutomatonBuilder::run() {
+  PFBuilder->createMatchSets();
+  return std::unique_ptr<GIMatchTreeAutomaton>(PFBuilder->createAutomaton());
+}
+
+void GIMatchTreeAutomatonBuilder::dump() const { writeYAML(llvm::dbgs()); }
+
+void GIMatchTreeAutomatonBuilder::writeYAML(raw_ostream &OS) const {
+  PFBuilder->writeYAML(OS);
+}
+} // namespace llvm