[WIP][GlobalISel][TableGen] Optimize MatchTable for faster instruction selection

[qcolombet]

Summary

Hi,

This is a WIP, if people like it, I can add comments and stuff and push behind an experimental option (or just use it by default). This is the full diff, in particular, I've squashed the whole history to show the full picture.

• Context ***

Right now, the table generated for matching instruction is straight forward but highly inefficient. Basically, each pattern generates its own set of self contained checks and actions.
E.g., TableGen generates:
First pattern
CheckNumOperand 3
CheckOpcode G_ADD
...
Build ADDrr
Second pattern
CheckNumOperand 3
CheckOpcode G_ADD
...
Build ADDri
// Third pattern
CheckNumOperand 3
CheckOpcode G_SUB
...
Build SUBrr

• Problem ***

Because of that generation, a *lot* of check are redundant between each pattern and are checked every single time until we reach the pattern that matches.
E.g., Taking the previous table, let say we are matching a G_SUB, that means we are going to check all the rules for G_ADD before looking at the G_SUB rule. In particular we are going to do:
check 3 operands; PASS
check G_ADD; FAIL
; Next rule
check 3 operands; PASS (but we already knew that!)
check G_ADD; FAIL (well it is still not true
; Next rule
check 3 operands; PASS (really!!)
check G_SUB; PASS (at last :P)

• Proposed Solution ***

This patch introduced a concept of group of rules (GroupMatcher) that share some predicates and only get checked once for the whole group.

As a proof of concept this patch only creates groups with one nesting level, but really there is nothing preventing it to do more.

In particular, for the given example it would generate:
// First group
CheckOpcode G_ADD

// First pattern
CheckNumOperand 3
...
Build ADDrr
// Second pattern
CheckNumOperand 3
...
Build ADDri

// Second group
CheckOpcode G_SUB

// Third pattern
CheckNumOperand 3
...
Build SUBrr

But it could also create a sub group for the checknumoperand 3 (we would just need to add a OptimizeRules on the rules within a group).

• Result ***

With only one level of nesting, the instruction selection pass was up to 4x faster. For instance, one instruction takes 500 checks, instead of 24k! With more nesting we could get in the tens I believe.

What do people think?

Cheers,
-Quentin

[qcolombet]

For the record, what the grouping does is pretty much flattening the predicate class hierarchy. Long term, we may want to have a simpler class hierarchy.
Also, I have tried to same on memory comsumption and speed of tablegen, in particular, we duplicate operand indices and instruction identifier all over the place to make the checking of predicate correct. (isIdentical)

[qcolombet]

Ping?

[dsanders]

There are a lot of changes in this patch so I haven't gone through the detail but this seems to be heading in the general direction I had in mind for when we got to optimizing the rules.

After importing and sorting the ruleset into priority order. I was thinking of having a collection of partitioners which would subdivide the ruleset into groups without changing that priority order. So for example, assuming the priority was this (it wouldn't be but ignore that for now):

(G_FNEG (G_FADD x, y))
(G_FADD x, y)
(G_FSUB x, y)
(G_FNEG x)

one partitioner would partition based on InstructionMatcher::Operands::size() like so:

(G_FNEG (G_FADD x, y))
---
(G_FADD x, y)
(G_FSUB x, y)
---
(G_FNEG x)

Even though the first and last rules only have one operand at the top level, they aren't grouped because of the priority of the G_FADD/G_FSUB in between. This way, we can ensure priority is being respected. The partitioner would then remove the relevant check from the rules and move them to the partition boundaries with appropriate GIM_Try's, much like you're doing in this patch. Each sub-ruleset would then be further partitioned forming a decision tree. Finally, when we run out of partitioners that produce >=2 partitions we generate the remaining rules in the ruleset as we do now.

Choosing which partitioner to apply at any given time is somewhat tricky. For this, I was thinking there would be two kinds of partitioner. Those that deal with structure (number of operands, opcodes?*, nested instructions, etc.) and those that deal with predicates. The structural ones would apply first, leaving the resulting sub-rulesets to test predicates using common instruction-id's and operand indices. For example:

(G_FADD x, simm16)
(G_FADD x, y)
(G_FNEG (G_FADD x, y))
(G_FNEG x)

would be divided by the structural partitioners like so

GIM_Try, ...
	GIM_CheckNumOperands, Insn0, 3,
	GIM_Try, ...
		GIM_CheckOpcode, Insn0, G_FADD,
		# (G_FADD x, simm16)
		# (G_FADD x, y)
GIM_Try, ...
	GIM_CheckNumOperands, Insn0, 2,
	GIM_RecordInsn, Insn1, Insn0, 1,
	GIM_Try, ...
		GIM_CheckOpcode, Insn0, G_FNEG,
		GIM_CheckOpcode, Insn1, G_FADD,
		# (G_FNEG (G_FADD x, y))
	GIM_Try, ...
		GIM_CheckNumOperands, Insn0, 2,
		# (G_FNEG x)

The G_FADD cases:

(G_FADD x, simm16)
(G_FADD x, y)

would then be further sub-divided by the predicate-based partitioners like so:

GIM_Try, ...
	GIM_CheckNumOperands, Insn0, 3,
	GIM_Try, ...
		GIM_CheckOpcode, Insn0, G_FADD,
		GIM_Try, ...
			GIM_CheckPredicate, Insn0, 2, simm16
			# (G_FADD x, simm16)
		GIM_Try, ...
			# (G_FADD x, y)
GIM_Try, ...
	GIM_CheckNumOperands, Insn0, 2,
	GIM_RecordInsn, Insn1, Insn0, 1,  // MIs[1] = getVRegDef(MIs[0].getOperand(1))
	GIM_Try, ...
		GIM_CheckOpcode, Insn0, G_FNEG,
		GIM_CheckOpcode, Insn1, G_FADD,
		# (G_FNEG (G_FADD x, y))
	GIM_Try, ...
		GIM_CheckNumOperands, Insn0, 2,
		# (G_FNEG x)

Within each set of partitioners, we'd need some heuristics to select an optimal one (and prevent the tree builder from getting too expensive). This is another reason for separating structural partitioners from predicate-based partitioners. The structural set have a more-or-less fixed order they can be applied (because they directly walk the tree) while still being near-optimal, then by the time we're onto the predicate-based ones (which have more freedom) we should have a small enough set to be a bit more thorough and evaluate which one produces the better tree. Somewhere in here, I also wanted to factor in the relative frequency of instructions so that rare instructions are checked last and frequent instructions require fewer checks. I was thinking this could be done as a tie-breaker in isHigherPriorityThan().

One thing the structual partitioners will want in order to maximize sharing of the structure predicates is a predictable numbering of instructions. A simple numbering scheme wouldn't work for variadic instructions so I think it's probably best to build the tree first and number the instructions afterwards. This is the reason instruction ID's were assigned during the emit*() functions and not stored in the matcher objects themselves.

*It's a bit debatable whether the opcode is structural or not. Technically you don't need it for structure but it seems wasteful to walk the def-use chain if the opcode is already going to prevent the match. On the other hand, if it's structural then (G_ADD (G_MUL x, y), z) and (G_SUB (G_MUL x, y), z) have different structure. It may be worth having a GIM_CheckOpcodeIsInSet or similar to balance the two extremes.

utils/TableGen/GlobalISelEmitter.cpp

594–597 ↗

(On Diff #119422)

I don't understand why this is needed.

3053–3062 ↗

(On Diff #119422)

This bit is correctness rather than optimization

[qcolombet]

For this, I was thinking there would be two kinds of partitioner. Those that deal with structure (number of operands, opcodes?*, nested instructions, etc.) and those that deal with predicates.

I would rather avoid the partitioners to be kind of "semantic-aware". If at all possible I would rather stick to simple concept like put "actions" that are identical together. On a different topic, the same apply for the matcher. Right now, we do the distinction between capturing, matching and so on, but all in all, this is just actions.

What I am saying is the design is more complicated than I would have thought and I wonder if on the long run it won't get in the way of modifying it... Unless it is well documented, in particular the intent :).

utils/TableGen/GlobalISelEmitter.cpp

594–597 ↗

(On Diff #119422)

Admittedly, this is a hack around the fact that capturing a variable is not an action, but instead something that happen somewhat magically when we need to access something (defineInsnVar).

Now, how does this work:

1. The "predicates" are self contained now, i.e., they reference all the InsnID and OpIdx they are going to access. In particular, they don't rely on a Rule at emission time to get this information (though the information needs to be in sync for this to work, thus the bunch of asserts added) Thanks to that, we can check that two predicates are really identical (as opposed to checking the same thing, but on different variables).
2. When building the predicates we implicitly defines all the variables that are going to be accessed in Rule.
3. We clean the implicit def in Rule (this method)
4. When we emit Rule we check that the defined variables are equal to what we chose at build time for the predicate

If we skip #3, Rule is going to keep increasing the InsnVarID and the numbers we came up at build time won't reference the right thing.

Does it make sense? (look line 2842 for the call to that method)

3053–3062 ↗

(On Diff #119422)

You're right, this is supposed to happen before the call to OptimizeRules.
Looks like I screwed up my squash :P.
I'll update the patch.

[qcolombet]

One thing to note: When you try a group, there is no way out. I.e., the assumption is that groups are mutually independent. This is actually why I haven't push for more nesting level, because the patch doesn't provide a way to check that this is true.

[qcolombet]

Move back the sorting of the Rules in main function.
This is not part of the optimization process.

[dsanders]

In D39034#905807, @qcolombet wrote:

For this, I was thinking there would be two kinds of partitioner. Those that deal with structure (number of operands, opcodes?*, nested instructions, etc.) and those that deal with predicates.

I would rather avoid the partitioners to be kind of "semantic-aware". If at all possible I would rather stick to simple concept like put "actions" that are identical together. On a different topic, the same apply for the matcher. Right now, we do the distinction between capturing, matching and so on, but all in all, this is just actions.

What I am saying is the design is more complicated than I would have thought and I wonder if on the long run it won't get in the way of modifying it... Unless it is well documented, in particular the intent :).

I'm also trying to avoid semantic awareness but a certain amount of it is necessary on the structure side of things since we need to walk the tree (occasionally it's a DAG but predicates deal with that). For example, you need to record an instruction with GIM_RecordInsn before you can test predicates on the instruction or its operands. The current separation between capturing and everything else is intended to keep the table optimization simple since the artificial barrier avoids the need to worry about putting an opcode check before the instruction has been recorded.

On the structure side, there's limited scope for re-ordering in any case due to the need to walk the tree. However, at this level it's also easy to group rules that share the same structure but have different predicates. For example:

(G_FADD (G_FMUL a, b), c) // 1
(G_FSUB (G_FMUL a, b), c)  // 2
(G_ADD a, imm16) // 3
(G_SUB a, imm16) // 4
(G_MUL a, imm16) // 5
(G_ADD a, b) // 6
(G_SUB a, b) // 7
(G_MUL a, b) // 8
(G_FADD a, b) // 9
...

only has three distinct structures:

(X (Y a, b), c) // 1 and 2
(X c, (Y a, b)) // 1 (commutative G_FADD)
(X a, b) // 3 (including commutative), 4, 5 (including commutative), 6 (including commutative), 7, 8 (including commutative), and 9 (including commutative)

I'd expect the main structure partitioner to simply group rules with the same shapes together. This should be a big win optimization-wise since there's a small number of distinct shapes in the ruleset. Once you're past structure matching and have captured all the relevant instructions, there's no relevant semantics left to preserve and you're free to re-order the predicates as much as you like.

The artificial boundary between the semantic-aware structure and the semantic-ignorant predicates does come at a cost though. We limit the potential optimization slightly since we can't rule particular structures out based on predicates. I suspect we may eventually want to allow some predicates (e.g. a check for whether an opcode is in a particular set) to cross that boundary but doing so requires more semantic awareness.

As a side note, I'd eventually like to be able to have a GIM_BuildMI/GIM_MutateOpcode that can directly map input opcodes to output opcodes so that multiple rules can share the same actions. Maybe something like:

GIM_CheckOpcodeInSet ... G_ADD, G_SUB, 0
GIR_BuildMIWithMap, ..., G_ADD, ADDWrr, G_SUB, SUBWrr, 0,
... other actions ...

but I haven't given that much thought yet. The reason I'd like it is that there are an awful lot of near-identical binary rules (e.g. (G_ADD a, b)) that differ only by the opcodes involved.

In D39034#905811, @qcolombet wrote:

One thing to note: When you try a group, there is no way out. I.e., the assumption is that groups are mutually independent. This is actually why I haven't push for more nesting level, because the patch doesn't provide a way to check that this is true.

That was true when I first introduced GIM_Try but it's not the case anymore. GIM_Reject is equivalent to a failed predicate and will resume processing from the label specified by the GIM_Try. If there is no active GIM_Try then it will give up matching entirely.

It's handled by these lines in InstructionSelectorImpl.h:

if (handleReject() == RejectAndGiveUp)
  return false;

[qcolombet]

If there is no active GIM_Try then it will give up matching entirely.

My bad, you're totally right. That means that I could theoretically already push for more than one level of nesting in the matching table without worrying about rejecting rules that would match later.
That's good to know!

Do you have any other comments on the code itself or should I push my changes? (With clean-ups like more comments and tests!)

[dsanders]

utils/TableGen/GlobalISelEmitter.cpp

533 ↗

(On Diff #120145)

This function is a bit confusing. Going by it's name, I think it's trying to detect whether the Predicate is already in the Conditions array but the code only checks the last condition (which is enough given how we generate the table)

700 ↗

(On Diff #120145)

predicates().begin() could be predicate_begin() which is more direct. Also this will need to be guarded against release builds otherwise some of the bots will object to the unused variable

719–731 ↗

(On Diff #120145)

What should be the relative priority of the IPM_* and OPM_* predicates. They act on different things so I don't think there's a meaningful one but I also don't think we should have an artificial one.

2338 ↗

(On Diff #120145)

I think we should have InstructionMatcher::addPredicate forward its ID onto the predicates that are added to it

2390 ↗

(On Diff #120145)

Similarly, OperandMatcher::addPredicate should forward the Instruction ID and Operand Index to the predicates added to it

3052 ↗

(On Diff #120145)

OptimizeRules -> optimizeRules

Also, I think this code will break if it ever manages to hoist a predicate that uses InsnID>0 or any OpIdx. There's currently no code to ensure an appropriate GIM_RecordInsn or GIM_CheckNumOperands has occurred before the hoisted predicate. At the moment, we're only managing to hoist the GIM_CheckOpcode for InsnID=0 which is always safe so we're getting away with it for now.

Here's roughly how I think we should go about fixing this:

• We should prepare the way for GroupMatcher by changing the following:
  • RuleMatcher should have a PredicateListMatcher
  • Feature bit tests should be handled by a PredicateMatcher in the RuleMatcher
  • InstructionMatcher and OperandMatcher should not have a PredicateListMatcher. Everything that was there should move to the RuleMatcher except for InstructionOperandMatcher's which should become a simple member of the OperandMatcher
• Then we should introduce the GroupMatcher which should have an array of InstructionMatchers (just like RuleMatcher) to define the structure, and a PredicateListMatcher to define the conditions. We should distribute rules into groups based on the shape of the InstructionMatcher/OperandMatcher structure while preserving priority order. After grouping them, RuleMatcher should not hold any representation of structure.
• Finally, for each nested GroupMatcher we should do what this code currently does

The overall effect will be that the top-level GIM_Try's will define the structure and emit the relevant GIM_RecordInsn's and GIM_CheckNumOperands. Deeper levels of GIM_Try's will only test conditions. Later on, we can then start breaking up the structure level into finer grain groupings and/or improve the intelligence of the grouping of the condition levels.

That said, it would be good to make some progress towards saner tables quickly. We could just adapt this code to intentionally hoist only the opcode for InsnID == 0 and improve things from there.

3054 ↗

(On Diff #120145)

StorageGroupMacther -> StorageGroupMatcher

3365–3367 ↗

(On Diff #120145)

This doesn't look right. It's removing the whole instruction matcher if its first operand matcher runs out of predicates. There may be other operand matchers left which do have predicates.

594–597 ↗

(On Diff #119422)

If we're going to put InsnID/OpIdx in the matchers, why not use those and skip step 3 and 4?

[qcolombet]

I'll upload a new version on Monday.

utils/TableGen/GlobalISelEmitter.cpp

533 ↗

(On Diff #120145)

Yeah, the name is not great (suggestion welcome :)), but the code does exactly what I wanted to. The incentive was to keep the building of groups cheap and the idea was if two rules don't have the same order in their predicates, they are not going to be grouped together. Although this is a weakness of the current grouping (in other words, it won't group thing that may have been commuted between two rules), the assumption is that the predicates are sorted in the same relative order and thus it should be that relevant.

> that's intentional :)

700 ↗

(On Diff #120145)

Both good catches!

719–731 ↗

(On Diff #120145)

I mainly followed what I believe was the layout of the table: Instruction then Operand. (General to Special.)

2338 ↗

(On Diff #120145)

Good point!
I made the change mechanically, I didn't notice the pattern.

2390 ↗

(On Diff #120145)

Yep!

3052 ↗

(On Diff #120145)

Given the record "directives" are not explicitly part of the predicate, I don't think we can mess them up. Indeed, we won't be able to hoist or reorder (which we don't do anyway) them, thus we cannot end up with a non-recorded use, right?

In other words, I don't think we need to restrict ourselves to InsnID == 0.
Am I missing something?

3052 ↗

(On Diff #120145)

The plan makes sense to me. It matches what I have in mind when I said we should flat the hierarchy.

3054 ↗

(On Diff #120145)

Good catch.

3365–3367 ↗

(On Diff #120145)

Good catch, this check is supposed to check that OpMatcher was the last one!

594–597 ↗

(On Diff #119422)

That's the long term plan, but it involves a bigger refactoring and I was not willing to pull that into this patch.
Is that fine with you?

(Admittedly, I was not planning to do that refactoring any time soon!)

[dsanders]

utils/TableGen/GlobalISelEmitter.cpp

533 ↗

(On Diff #120145)

lastConditionMatches()? Alternatively, the caller could use Predicate.isIdenticalTo(group.conditions_back())

719–731 ↗

(On Diff #120145)

I think we'll get better tables if opcodes are allowed to have low priority. For example, binary operations can check for reg <op> reg => reg, and reg <op> imm => reg before testing the opcode.

That said, looking at it again it's not a problem since PredicateMatcher doesn't define a isHigherPriorityThan(). They're in OperandPredicateMatcher and InstructionPredicateMatcher so the two families are never compared.

Could you add to the comment saying the relative priority of IPM_* and OPM_* doesn't matter?

3052 ↗

(On Diff #120145)

Suppose you've hoisted a couple checks and have some rules in a group of the form:

GIM_Try,
  GIM_CheckOpcode, /*InsnID*/0, G_ADD
  GIM_Try
    GIM_RecordInsn, /*InsnID*/1, ...
    GIM_CheckOpcode, /*InsnID*/1, G_MUL
    ...
  GIM_Try
    GIM_RecordInsn, /*InsnID*/1, ...
    GIM_CheckOpcode, /*InsnID*/1, G_MUL
    ...

Both rules have the same leading check, so that check is also hoisted by this code to get:

GIM_Try,
  GIM_CheckOpcode, /*InsnID*/0, G_ADD
  GIM_CheckOpcode, /*InsnID*/1, G_MUL    // <-- InsnID 1 has not been defined by a GIM_RecordInsn yet
  GIM_Try
    GIM_RecordInsn, /*InsnID*/1, ... // <-- Was emitted by emitCaptureOpcodes()
      ...
  GIM_Try
    GIM_RecordInsn, /*InsnID*/1, ...
    ...

At the moment the only thing that seems to prevent this is that all the rules differ in the second predicate so it doesn't check whether the GIM_CheckOpcode for InsnID 1 can be hoisted.

594–597 ↗

(On Diff #119422)

That makes sense to me but we should follow up with the refactor asap. In the mean-time, we should comment on the requirement that the numbering comes out the same and explain the plan to fix it.

[qcolombet]

utils/TableGen/GlobalISelEmitter.cpp

3052 ↗

(On Diff #120145)

Good catch. I mis-remembered that record insn stuff was also emitted as part of the emitPredicates thing.
Do you think I should add a emitCaptureOpcodes as part of the GroupMatcher as well?

Anyhow, for now, I will just bail out on InsnID != 0 or use OpIdx.

[qcolombet]

• Address nitpicks
• Push InsnID and OpIdx in addPredicate
• Bail on sharing when InsnID != 0 or OpIdx is specified
• Make NumOperands a member variable instead of computed from the size of the list

[qcolombet]

utils/TableGen/GlobalISelEmitter.cpp

3365–3367 ↗

(On Diff #120145)

Actually, I've checked the implementation of InstructionMatcher::pop_front and it only does what I intended: removing the first operand.

Talking with Daniel offline there was something else to fix: getNumOperands, so that the related check remains correct (it was looking at the size of this list).

[dsanders]

LGTM. We need to follow up with the refactor to eliminate clearImplicitMap() though. We ought to follow up with the simplification of PredicateListMatcher too. The templating isn’t very useful anymore now that predicates have a common base class

utils/TableGen/GlobalISelEmitter.cpp

756 ↗

(On Diff #126205)

Some of this predates this patch but we seem to have three naming conventions for operations affecting Matchers:

• insnmatchers_front
• matchers_empty
• pop_front

We should pick one, my preference is for the first two. Of those two I have a slight preference for insnmatchers_front

811 ↗

(On Diff #126205)

This will crash if predicates_begin() == predicates_end()

920 ↗

(On Diff #126205)

This seems to have undone the TiedTo -> MatchingName change I was asked to make when I committed SameOperandMatcher

3365–3367 ↗

(On Diff #120145)

Sorry about that.

There’s also the operand index which uses the position within this list

594–597 ↗

(On Diff #119422)

I dont think the comment has been added

[qcolombet]

utils/TableGen/GlobalISelEmitter.cpp

756 ↗

(On Diff #126205)

Good catch.

811 ↗

(On Diff #126205)

We check this case in the previous statement, right?

920 ↗

(On Diff #126205)

Bad merge when I rebased I suppose. Will fix.

3365–3367 ↗

(On Diff #120145)

Okay, looking.

594–597 ↗

(On Diff #119422)

I missed that one. Thanks.

[dsanders]

utils/TableGen/GlobalISelEmitter.cpp

811 ↗

(On Diff #126205)

Scratch this one. We check it a little earlier, I just didn’t notice because it was off screen

[qcolombet]

utils/TableGen/GlobalISelEmitter.cpp

3365–3367 ↗

(On Diff #120145)

Seems like InstMatcher::getOperand would already do the right thing (it checks that getOperandIndex == OpIdx) and AFAICT the uses of OperandMatcher::getOperandIndex are fine.
What else should I check?

[dsanders]

utils/TableGen/GlobalISelEmitter.cpp

3365–3367 ↗

(On Diff #120145)

Sorry, forgot to come back to this.

There's the emit*() functions but this patch already rewrites the code that might be affected so I think we're fine.

llvm/trunk/test/TableGen/GlobalISelEmitter.td

-// RUN: llvm-tblgen -gen-global-isel -I %p/../../include %s | FileCheck %s
+// RUN: llvm-tblgen -optimize-match-table=false -gen-global-isel -I %p/../../include %s | FileCheck %s --check-prefix=CHECK --check-prefix=NOOPT
+//
+// The optimized table can reorder predicates between rules, but the rules
+// order must remain the same.
+// RUN: llvm-tblgen -optimize-match-table=true -gen-global-isel -I %p/../../include %s | FileCheck %s --check-prefix=CHECK --check-prefix=OPT
+//
+// Make sure the default is to optimize the table.
+// RUN: llvm-tblgen -gen-global-isel -I %p/../../include %s | FileCheck %s --check-prefix=CHECK --check-prefix=OPT
 
 include "llvm/Target/Target.td"
 
 //===- Define the necessary boilerplate for our test target. --------------===//
 
 def MyTargetISA : InstrInfo;
 def MyTarget : Target { let InstructionSet = MyTargetISA; }
 

 // CHECK-NEXT: NewMIVector OutMIs;
 // CHECK-NEXT: State.MIs.clear();
 // CHECK-NEXT: State.MIs.push_back(&I);
 
 //===- Test a pattern with multiple ComplexPatterns in multiple instrs ----===//
 //
 
 // CHECK-LABEL: MatchTable0[] = {
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 0*/ [[LABEL:[0-9]+]],
+// OPT-NEXT:  GIM_Try, /*On fail goto*//*Label [[GRP_LABEL_NUM:[0-9]+]]*/ [[GRP_LABEL:[0-9]+]],
+// OPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SELECT,
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/4,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SELECT,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SELECT,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src1
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src2
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckComplexPattern, /*MI*/0, /*Op*/2, /*Renderer*/0, GICP_gi_complex,
 // CHECK-NEXT:    // MIs[0] src3
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/3, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckComplexPattern, /*MI*/0, /*Op*/3, /*Renderer*/1, GICP_gi_complex,
 // CHECK-NEXT:    // (select:{ *:[i32] } GPR32:{ *:[i32] }:$src1, complex:{ *:[i32] }:$src2, complex:{ *:[i32] }:$src3) => (INSN2:{ *:[i32] } GPR32:{ *:[i32] }:$src1, complex:{ *:[i32] }:$src3, complex:{ *:[i32] }:$src2)
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::INSN2,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/1, // src1
 // CHECK-NEXT:    GIR_ComplexRenderer, /*InsnID*/0, /*RendererID*/1,
 // CHECK-NEXT:    GIR_ComplexRenderer, /*InsnID*/0, /*RendererID*/0,
 // CHECK-NEXT:    GIR_MergeMemOperands, /*InsnID*/0, /*MergeInsnID's*/0, GIU_MergeMemOperands_EndOfList,
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 0: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
 
 def INSN3 : I<(outs GPR32:$dst),
               (ins GPR32Op:$src1, GPR32:$src2a, GPR32:$src2b, GPR32:$scr), []>;
 def INSN4 : I<(outs GPR32:$scr),
               (ins GPR32:$src3, complex:$src4, i32imm:$src5a, i32imm:$src5b), []>;
 def : Pat<(select GPR32:$src1, (complex_rr GPR32:$src2a, GPR32:$src2b),
                                (select GPR32:$src3,
                                        complex:$src4,
                                        (complex i32imm:$src5a, i32imm:$src5b))),
           (INSN3 GPR32:$src1, GPR32:$src2b, GPR32:$src2a,
                  (INSN4 GPR32:$src3, complex:$src4, i32imm:$src5a,
                         i32imm:$src5b))>;
 
 //===- Test a pattern with multiple ComplexPattern operands. --------------===//
 //
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 1*/ [[LABEL:[0-9]+]],
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/4,
 // CHECK-NEXT:    GIM_RecordInsn, /*DefineMI*/1, /*MI*/0, /*OpIdx*/3, // MIs[1]
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/1, /*Expected*/4,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SELECT,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SELECT,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src1
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 2
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,

 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/1, // src1
 // CHECK-NEXT:    GIR_ComplexSubOperandRenderer, /*InsnID*/0, /*RendererID*/0, /*SubOperand*/1, // src2b
 // CHECK-NEXT:    GIR_ComplexSubOperandRenderer, /*InsnID*/0, /*RendererID*/0, /*SubOperand*/0, // src2a
 // CHECK-NEXT:    GIR_AddTempRegister, /*InsnID*/0, /*TempRegID*/0, /*TempRegFlags*/0,
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 1: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
+// Closing the G_SELECT group.
+// OPT-NEXT:      GIM_Reject,
+// OPT-NEXT:  GIR_Done,
+// OPT-NEXT:  // Label [[GRP_LABEL_NUM]]: @[[GRP_LABEL]]
 
 def : GINodeEquiv<G_SELECT, select>;
 let mayLoad = 1 in {
   def INSN2 : I<(outs GPR32:$dst), (ins GPR32Op:$src1, complex:$src2, complex:$src3), []>;
 }
 def : Pat<(select GPR32:$src1, complex:$src2, complex:$src3),
           (INSN2 GPR32:$src1, complex:$src3, complex:$src2)>;
 
 //===- Test a simple pattern with regclass operands. ----------------------===//
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 2*/ [[LABEL:[0-9]+]],
+// OPT-NEXT:  GIM_Try, /*On fail goto*//*Label [[GRP_LABEL_NUM:[0-9]+]]*/ [[GRP_LABEL:[0-9]+]],
+// OPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_ADD,
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_ADD,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_ADD,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src1
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID
 // CHECK-NEXT:    // MIs[0] src2
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/2, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // (add:{ *:[i32] } GPR32:{ *:[i32] }:$src1, GPR32:{ *:[i32] }:$src2) => (ADD:{ *:[i32] } GPR32:{ *:[i32] }:$src1, GPR32:{ *:[i32] }:$src2)
 // CHECK-NEXT:    GIR_MutateOpcode, /*InsnID*/0, /*RecycleInsnID*/0, /*Opcode*/MyTarget::ADD,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 2: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
 
 def ADD : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2),
             [(set GPR32:$dst, (add GPR32:$src1, GPR32:$src2))]>;
 
 //===- Test a pattern with a tied operand in the matcher ------------------===//
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 3*/ [[LABEL:[0-9]+]],
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_ADD,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_ADD,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src{{$}}
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src{{$}}
 // CHECK-NEXT:    GIM_CheckIsSameOperand, /*MI*/0, /*OpIdx*/2, /*OtherMI*/0, /*OtherOpIdx*/1,
 // CHECK-NEXT:    // (add:{ *:[i32] } GPR32:{ *:[i32] }:$src, GPR32:{ *:[i32] }:$src) => (DOUBLE:{ *:[i32] } GPR32:{ *:[i32] }:$src)
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::DOUBLE,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/1, // src
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 3: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
 
 def DOUBLE : I<(outs GPR32:$dst), (ins GPR32:$src), [(set GPR32:$dst, (add GPR32:$src, GPR32:$src))]>;
 
 //===- Test a simple pattern with ValueType operands. ----------------------===//
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 4*/ [[LABEL:[0-9]+]],
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_ADD,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_ADD,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src1
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // CHECK-NEXT:    // MIs[0] src2
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
 // CHECK-NEXT:    // (add:{ *:[i32] } i32:{ *:[i32] }:$src1, i32:{ *:[i32] }:$src2) => (ADD:{ *:[i32] } i32:{ *:[i32] }:$src1, i32:{ *:[i32] }:$src2)
 // CHECK-NEXT:    GIR_MutateOpcode, /*InsnID*/0, /*RecycleInsnID*/0, /*Opcode*/MyTarget::ADD,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 4: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
+// Closing the G_ADD group.
+// OPT-NEXT:      GIM_Reject,
+// OPT-NEXT:  GIR_Done,
+// OPT-NEXT:  // Label [[GRP_LABEL_NUM]]: @[[GRP_LABEL]]
 
 def : Pat<(add i32:$src1, i32:$src2),
           (ADD i32:$src1, i32:$src2)>;
 
 //===- Test a simple pattern with an intrinsic. ---------------------------===//
 //
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 5*/ [[LABEL:[0-9]+]],
+// OPT-NEXT:  GIM_Try, /*On fail goto*//*Label [[GRP_LABEL_NUM:[0-9]+]]*/ [[GRP_LABEL:[0-9]+]],
+// OPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_INTRINSIC,
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_INTRINSIC,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_INTRINSIC,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 1
 // CHECK-NEXT:    GIM_CheckIntrinsicID, /*MI*/0, /*Op*/1, Intrinsic::mytarget_nop,
 // CHECK-NEXT:    // MIs[0] src1
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/2, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // (intrinsic_wo_chain:{ *:[i32] } [[ID:[0-9]+]]:{ *:[iPTR] }, GPR32:{ *:[i32] }:$src1) => (MOV:{ *:[i32] } GPR32:{ *:[i32] }:$src1)
 
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::MOV,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/2, // src1
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 5: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
+// Closing the G_INTRINSIC group.
+// OPT-NEXT:      GIM_Reject,
+// OPT-NEXT:  GIR_Done,
+// OPT-NEXT:  // Label [[GRP_LABEL_NUM]]: @[[GRP_LABEL]]
 
 def MOV : I<(outs GPR32:$dst), (ins GPR32:$src1),
             [(set GPR32:$dst, (int_mytarget_nop GPR32:$src1))]>;
 
 //===- Test a nested instruction match. -----------------------------------===//
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 6*/ [[LABEL:[0-9]+]],
+// OPT-NEXT:  GIM_Try, /*On fail goto*//*Label [[GRP_LABEL_NUM:[0-9]+]]*/ [[GRP_LABEL:[0-9]+]],
+// OPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_MUL,
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckFeatures, GIFBS_HasA,
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
 // CHECK-NEXT:    GIM_RecordInsn, /*DefineMI*/1, /*MI*/0, /*OpIdx*/1, // MIs[1]
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/1, /*Expected*/3,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_MUL,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_MUL,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 1
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckOpcode, /*MI*/1, TargetOpcode::G_ADD,
 // CHECK-NEXT:    // MIs[1] Operand 0
 // CHECK-NEXT:    GIM_CheckType, /*MI*/1, /*Op*/0, /*Type*/GILLT_s32,

 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::MULADD,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/1, /*OpIdx*/1, // src1
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/1, /*OpIdx*/2, // src2
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/2, // src3
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 6: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
 
 // We also get a second rule by commutativity.
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 7*/ [[LABEL:[0-9]+]],
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckFeatures, GIFBS_HasA,
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
 // CHECK-NEXT:    GIM_RecordInsn, /*DefineMI*/1, /*MI*/0, /*OpIdx*/2,
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/1, /*Expected*/3,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_MUL,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_MUL,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src3
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 2
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,

 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::MULADD,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/1, /*OpIdx*/1, // src1
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/1, /*OpIdx*/2, // src2
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/1, // src3
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 7: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
 
 def MULADD : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2, GPR32:$src3),
                [(set GPR32:$dst,
                      (mul (add GPR32:$src1, GPR32:$src2), GPR32:$src3))]>,
              Requires<[HasA]>;
 
 //===- Test another simple pattern with regclass operands. ----------------===//
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 8*/ [[LABEL:[0-9]+]],
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckFeatures, GIFBS_HasA_HasB_HasC,
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_MUL,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_MUL,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src1
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src2
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/2, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // (mul:{ *:[i32] } GPR32:{ *:[i32] }:$src1, GPR32:{ *:[i32] }:$src2) => (MUL:{ *:[i32] } GPR32:{ *:[i32] }:$src2, GPR32:{ *:[i32] }:$src1)
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::MUL,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/2, // src2
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/1, // src1
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 8: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
+// Closing the G_MUL group.
+// OPT-NEXT:      GIM_Reject,
+// OPT-NEXT:  GIR_Done,
+// OPT-NEXT:  // Label [[GRP_LABEL_NUM]]: @[[GRP_LABEL]]
 
 def MUL : I<(outs GPR32:$dst), (ins GPR32:$src2, GPR32:$src1),
              [(set GPR32:$dst, (mul GPR32:$src1, GPR32:$src2))]>,
           Requires<[HasA, HasB, HasC]>;
 
 //===- Test a more complex multi-instruction match. -----------------------===//
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 9*/ [[LABEL:[0-9]+]],
+// OPT-NEXT:  GIM_Try, /*On fail goto*//*Label [[GRP_LABEL_NUM:[0-9]+]]*/ [[GRP_LABEL:[0-9]+]],
+// OPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SUB,
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckFeatures, GIFBS_HasA,
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
 // CHECK-NEXT:    GIM_RecordInsn, /*DefineMI*/1, /*MI*/0, /*OpIdx*/1, // MIs[1]
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/1, /*Expected*/3,
 // CHECK-NEXT:    GIM_RecordInsn, /*DefineMI*/2, /*MI*/0, /*OpIdx*/2, // MIs[2]
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/2, /*Expected*/3,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SUB,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SUB,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 1
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckOpcode, /*MI*/1, TargetOpcode::G_SUB,
 // CHECK-NEXT:    // MIs[1] Operand 0
 // CHECK-NEXT:    GIM_CheckType, /*MI*/1, /*Op*/0, /*Type*/GILLT_s32,

 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/1, /*OpIdx*/1, // src1
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/1, /*OpIdx*/2, // src2
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/2, /*OpIdx*/1, // src3
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/2, /*OpIdx*/2, // src4
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 9: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
 
 def INSNBOB : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2, GPR32:$src3, GPR32:$src4),
                  [(set GPR32:$dst,
                       (sub (sub GPR32:$src1, GPR32:$src2), (sub GPR32:$src3, GPR32:$src4)))]>,
                Requires<[HasA]>;
 
 //===- Test a pattern with ComplexPattern operands. -----------------------===//
 //
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 10*/ [[LABEL:[0-9]+]],
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SUB,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SUB,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src1
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src2
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckComplexPattern, /*MI*/0, /*Op*/2, /*Renderer*/0, GICP_gi_complex,
 // CHECK-NEXT:    // (sub:{ *:[i32] } GPR32:{ *:[i32] }:$src1, complex:{ *:[i32] }:$src2) => (INSN1:{ *:[i32] } GPR32:{ *:[i32] }:$src1, complex:{ *:[i32] }:$src2)
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::INSN1,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/1, // src1
 // CHECK-NEXT:    GIR_ComplexRenderer, /*InsnID*/0, /*RendererID*/0,
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 10: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
+// Closing the G_SUB group.
+// OPT-NEXT:      GIM_Reject,
+// OPT-NEXT:  GIR_Done,
+// OPT-NEXT:  // Label [[GRP_LABEL_NUM]]: @[[GRP_LABEL]]
 
 def INSN1 : I<(outs GPR32:$dst), (ins GPR32:$src1, complex:$src2), []>;
 def : Pat<(sub GPR32:$src1, complex:$src2), (INSN1 GPR32:$src1, complex:$src2)>;
 
 //===- Test a simple pattern with a default operand. ----------------------===//
 //
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 11*/ [[LABEL:[0-9]+]],
+// OPT-NEXT:  GIM_Try, /*On fail goto*//*Label [[GRP_LABEL_NUM:[0-9]+]]*/ [[GRP_LABEL:[0-9]+]],
+// OPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_XOR,
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_XOR,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_XOR,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src1
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 2
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckConstantInt, /*MI*/0, /*Op*/2, -2
 // CHECK-NEXT:    // (xor:{ *:[i32] } GPR32:{ *:[i32] }:$src1, -2:{ *:[i32] }) => (XORI:{ *:[i32] } GPR32:{ *:[i32] }:$src1)
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::XORI,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_AddImm, /*InsnID*/0, /*Imm*/-1,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/1, // src1
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 11: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
 
 // The -2 is just to distinguish it from the 'not' case below.
 def XORI : I<(outs GPR32:$dst), (ins m1:$src2, GPR32:$src1),
              [(set GPR32:$dst, (xor GPR32:$src1, -2))]>;
 
 //===- Test a simple pattern with a default register operand. -------------===//
 //
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 12*/ [[LABEL:[0-9]+]],
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_XOR,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_XOR,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src1
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 2
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckConstantInt, /*MI*/0, /*Op*/2, -3
 // CHECK-NEXT:    // (xor:{ *:[i32] } GPR32:{ *:[i32] }:$src1, -3:{ *:[i32] }) => (XOR:{ *:[i32] } GPR32:{ *:[i32] }:$src1)
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::XOR,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_AddRegister, /*InsnID*/0, MyTarget::R0,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/1, // src1
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 12: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
 
 // The -3 is just to distinguish it from the 'not' case below and the other default op case above.
 def XOR : I<(outs GPR32:$dst), (ins Z:$src2, GPR32:$src1),
             [(set GPR32:$dst, (xor GPR32:$src1, -3))]>;
 
 //===- Test a simple pattern with a multiple default operands. ------------===//
 //
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 13*/ [[LABEL:[0-9]+]],
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_XOR,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_XOR,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src1
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 2
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckConstantInt, /*MI*/0, /*Op*/2, -4
 // CHECK-NEXT:    // (xor:{ *:[i32] } GPR32:{ *:[i32] }:$src1, -4:{ *:[i32] }) => (XORlike:{ *:[i32] } GPR32:{ *:[i32] }:$src1)
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::XORlike,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_AddImm, /*InsnID*/0, /*Imm*/-1,
 // CHECK-NEXT:    GIR_AddRegister, /*InsnID*/0, MyTarget::R0,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/1, // src1
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 13: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
 
 // The -4 is just to distinguish it from the other 'not' cases.
 def XORlike : I<(outs GPR32:$dst), (ins m1Z:$src2, GPR32:$src1),
                 [(set GPR32:$dst, (xor GPR32:$src1, -4))]>;
 
 //===- Test a simple pattern with multiple operands with defaults. --------===//
 //
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 14*/ [[LABEL:[0-9]+]],
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_XOR,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_XOR,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src1
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 2
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckConstantInt, /*MI*/0, /*Op*/2, -5,
 // CHECK-NEXT:    // (xor:{ *:[i32] } GPR32:{ *:[i32] }:$src1, -5:{ *:[i32] }) => (XORManyDefaults:{ *:[i32] } GPR32:{ *:[i32] }:$src1)
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::XORManyDefaults,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_AddImm, /*InsnID*/0, /*Imm*/-1,
 // CHECK-NEXT:    GIR_AddRegister, /*InsnID*/0, MyTarget::R0,
 // CHECK-NEXT:    GIR_AddRegister, /*InsnID*/0, MyTarget::R0,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/1, // src1
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 14: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
 
 // The -5 is just to distinguish it from the other cases.
 def XORManyDefaults : I<(outs GPR32:$dst), (ins m1Z:$src3, Z:$src2, GPR32:$src1),
                         [(set GPR32:$dst, (xor GPR32:$src1, -5))]>;
 
 //===- Test a simple pattern with constant immediate operands. ------------===//
 //
 // This must precede the 3-register variants because constant immediates have
 // priority over register banks.
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 15*/ [[LABEL:[0-9]+]],
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_XOR,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_XOR,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Wm
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 2
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckConstantInt, /*MI*/0, /*Op*/2, -1,
 // CHECK-NEXT:    // (xor:{ *:[i32] } GPR32:{ *:[i32] }:$Wm, -1:{ *:[i32] }) => (ORN:{ *:[i32] } R0:{ *:[i32] }, GPR32:{ *:[i32] }:$Wm)
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::ORN,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_AddRegister, /*InsnID*/0, MyTarget::R0,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/1, // Wm
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 15: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
+// Closing the G_XOR group.
+// OPT-NEXT:      GIM_Reject,
+// OPT-NEXT:  GIR_Done,
+// OPT-NEXT:  // Label [[GRP_LABEL_NUM]]: @[[GRP_LABEL]]
 
 def ORN : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>;
 def : Pat<(not GPR32:$Wm), (ORN R0, GPR32:$Wm)>;
 
 //===- Test a COPY_TO_REGCLASS --------------------------------------------===//
 //
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 16*/ [[LABEL:[0-9]+]],
+// OPT-NEXT:  GIM_Try, /*On fail goto*//*Label [[GRP_LABEL_NUM:[0-9]+]]*/ [[GRP_LABEL:[0-9]+]],
+// OPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_BITCAST,
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/2,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_BITCAST,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_BITCAST,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src1
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::FPR32RegClassID,
 // CHECK-NEXT:    // (bitconvert:{ *:[i32] } FPR32:{ *:[f32] }:$src1) => (COPY_TO_REGCLASS:{ *:[i32] } FPR32:{ *:[f32] }:$src1, GPR32:{ *:[i32] })
 // CHECK-NEXT:    GIR_MutateOpcode, /*InsnID*/0, /*RecycleInsnID*/0, /*Opcode*/TargetOpcode::COPY,
 // CHECK-NEXT:    GIR_ConstrainOperandRC, /*InsnID*/0, /*Op*/0, /*RC GPR32*/1,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 16: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
+// Closing the G_BITCAST group.
+// OPT-NEXT:      GIM_Reject,
+// OPT-NEXT:  GIR_Done,
+// OPT-NEXT:  // Label [[GRP_LABEL_NUM]]: @[[GRP_LABEL]]
 
 def : Pat<(i32 (bitconvert FPR32:$src1)),
           (COPY_TO_REGCLASS FPR32:$src1, GPR32)>;
 
 //===- Test a simple pattern with just a specific leaf immediate. ---------===//
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 17*/ [[LABEL:[0-9]+]],
+// OPT-NEXT:  GIM_Try, /*On fail goto*//*Label [[GRP_LABEL_NUM:[0-9]+]]*/ [[GRP_LABEL:[0-9]+]],
+// OPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_CONSTANT,
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/2,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_CONSTANT,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_CONSTANT,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 1
 // CHECK-NEXT:    GIM_CheckLiteralInt, /*MI*/0, /*Op*/1, 1,
 // CHECK-NEXT:    // 1:{ *:[i32] }  =>  (MOV1:{ *:[i32] })
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::MOV1,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 17: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
 
 def MOV1 : I<(outs GPR32:$dst), (ins), [(set GPR32:$dst, 1)]>;
 
 //===- Test a simple pattern with a leaf immediate and a predicate. -------===//
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 18*/ [[LABEL:[0-9]+]],
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/2,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_CONSTANT,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_CONSTANT,
 // CHECK-NEXT:    GIM_CheckI64ImmPredicate, /*MI*/0, /*Predicate*/GIPFP_I64_Predicate_simm8,
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 1
 // CHECK-NEXT:    // No operand predicates
 // CHECK-NEXT:    // (imm:{ *:[i32] })<<P:Predicate_simm8>>:$imm => (MOVimm8:{ *:[i32] } (imm:{ *:[i32] }):$imm)
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::MOVimm8,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_CopyConstantAsSImm, /*NewInsnID*/0, /*OldInsnID*/0, // imm
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 18: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
 
 def simm8 : ImmLeaf<i32, [{ return isInt<8>(Imm); }]>;
 def MOVimm8 : I<(outs GPR32:$dst), (ins i32imm:$imm), [(set GPR32:$dst, simm8:$imm)]>;
 
 //===- Same again but use an IntImmLeaf. ----------------------------------===//
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 19*/ [[LABEL:[0-9]+]],
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/2,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_CONSTANT,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_CONSTANT,
 // CHECK-NEXT:    GIM_CheckAPIntImmPredicate, /*MI*/0, /*Predicate*/GIPFP_APInt_Predicate_simm9,
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 1
 // CHECK-NEXT:    // No operand predicates
 // CHECK-NEXT:    // (imm:{ *:[i32] })<<P:Predicate_simm9>>:$imm =>  (MOVimm9:{ *:[i32] } (imm:{ *:[i32] }):$imm)
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::MOVimm9,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_CopyConstantAsSImm, /*NewInsnID*/0, /*OldInsnID*/0, // imm
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 19: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
 
 def simm9 : IntImmLeaf<i32, [{ return isInt<9>(Imm->getSExtValue()); }]>;
 def MOVimm9 : I<(outs GPR32:$dst), (ins i32imm:$imm), [(set GPR32:$dst, simm9:$imm)]>;
 
 //===- Test a simple pattern with just a leaf immediate. ------------------===//
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 20*/ [[LABEL:[0-9]+]],
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/2,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_CONSTANT,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_CONSTANT,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 1
 // CHECK-NEXT:    // No operand predicates
 // CHECK-NEXT:    // (imm:{ *:[i32] }):$imm =>  (MOVimm:{ *:[i32] } (imm:{ *:[i32] }):$imm)
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::MOVimm,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_CopyConstantAsSImm, /*NewInsnID*/0, /*OldInsnID*/0, // imm
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 20: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
+// Closing the G_CONSTANT group.
+// OPT-NEXT:      GIM_Reject,
+// OPT-NEXT:  GIR_Done,
+// OPT-NEXT:  // Label [[GRP_LABEL_NUM]]: @[[GRP_LABEL]]
 
 def MOVimm : I<(outs GPR32:$dst), (ins i32imm:$imm), [(set GPR32:$dst, imm:$imm)]>;
 
 //===- Test a simple pattern with a FP immediate and a predicate. ---------===//
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 21*/ [[LABEL:[0-9]+]],
+// OPT-NEXT:  GIM_Try, /*On fail goto*//*Label [[GRP_LABEL_NUM:[0-9]+]]*/ [[GRP_LABEL:[0-9]+]],
+// OPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_FCONSTANT,
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/2,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_FCONSTANT,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_FCONSTANT,
 // CHECK-NEXT:    GIM_CheckAPFloatImmPredicate, /*MI*/0, /*Predicate*/GIPFP_APFloat_Predicate_fpimmz,
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::FPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 1
 // CHECK-NEXT:    // No operand predicates
 // CHECK-NEXT:    // (fpimm:{ *:[f32] })<<P:Predicate_fpimmz>>:$imm =>  (MOVfpimmz:{ *:[f32] } (fpimm:{ *:[f32] }):$imm)
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::MOVfpimmz,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_CopyFConstantAsFPImm, /*NewInsnID*/0, /*OldInsnID*/0, // imm
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 21: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
+// Closing the G_FCONSTANT group.
+// OPT-NEXT:      GIM_Reject,
+// OPT-NEXT:  GIR_Done,
+// OPT-NEXT:  // Label [[GRP_LABEL_NUM]]: @[[GRP_LABEL]]
 
 def fpimmz : FPImmLeaf<f32, [{ return Imm->isExactlyValue(0.0); }]>;
 def MOVfpimmz : I<(outs FPR32:$dst), (ins f32imm:$imm), [(set FPR32:$dst, fpimmz:$imm)]>;
 
 //===- Test a simple pattern with inferred pointer operands. ---------------===//
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 22*/ [[LABEL:[0-9]+]],
+// OPT-NEXT:  GIM_Try, /*On fail goto*//*Label [[GRP_LABEL_NUM:[0-9]+]]*/ [[GRP_LABEL:[0-9]+]],
+// OPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_LOAD,
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/2,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_LOAD,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_LOAD,
 // CHECK-NEXT:    GIM_CheckAtomicOrdering, /*MI*/0, /*Order*/(int64_t)AtomicOrdering::NotAtomic,
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] src1
 // CHECK-NEXT:    GIM_CheckPointerToAny, /*MI*/0, /*Op*/1, /*SizeInBits*/32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // (ld:{ *:[i32] } GPR32:{ *:[i32] }:$src1)<<P:Predicate_unindexedload>><<P:Predicate_load>> => (LOAD:{ *:[i32] } GPR32:{ *:[i32] }:$src1)
 // CHECK-NEXT:    GIR_MutateOpcode, /*InsnID*/0, /*RecycleInsnID*/0, /*Opcode*/MyTarget::LOAD,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 22: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
+// Closing the G_LOAD group.
+// OPT-NEXT:      GIM_Reject,
+// OPT-NEXT:  GIR_Done,
+// OPT-NEXT:  // Label [[GRP_LABEL_NUM]]: @[[GRP_LABEL]]
 
 def LOAD : I<(outs GPR32:$dst), (ins GPR32:$src1),
             [(set GPR32:$dst, (load GPR32:$src1))]>;
 
 //===- Test a simple pattern with a sextload -------------------------------===//
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 23*/ [[LABEL:[0-9]+]],
+// OPT-NEXT:  GIM_Try, /*On fail goto*//*Label [[GRP_LABEL_NUM:[0-9]+]]*/ [[GRP_LABEL:[0-9]+]],
+// OPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SEXT,
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/2,
 // CHECK-NEXT:    GIM_RecordInsn, /*DefineMI*/1, /*MI*/0, /*OpIdx*/1, // MIs[1]
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/1, /*Expected*/2,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SEXT,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SEXT,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 1
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s16,
 // CHECK-NEXT:    GIM_CheckOpcode, /*MI*/1, TargetOpcode::G_LOAD,
 // CHECK-NEXT:    GIM_CheckAtomicOrdering, /*MI*/1, /*Order*/(int64_t)AtomicOrdering::NotAtomic,
 // CHECK-NEXT:    // MIs[1] Operand 0
 // CHECK-NEXT:    GIM_CheckType, /*MI*/1, /*Op*/0, /*Type*/GILLT_s16,
 // CHECK-NEXT:    // MIs[1] src1
 // CHECK-NEXT:    GIM_CheckPointerToAny, /*MI*/1, /*Op*/1, /*SizeInBits*/32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/1, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    GIM_CheckIsSafeToFold, /*InsnID*/1,
 // CHECK-NEXT:    // (sext:{ *:[i32] } (ld:{ *:[i16] } GPR32:{ *:[i32] }:$src1)<<P:Predicate_unindexedload>>)  =>  (SEXTLOAD:{ *:[i32] } GPR32:{ *:[i32] }:$src1)
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::SEXTLOAD,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/1, /*OpIdx*/1, // src1
 // CHECK-NEXT:    GIR_MergeMemOperands, /*InsnID*/0, /*MergeInsnID's*/0, 1, GIU_MergeMemOperands_EndOfList,
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 23: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
+// Closing the G_SEXT group.
+// OPT-NEXT:      GIM_Reject,
+// OPT-NEXT:  GIR_Done,
+// OPT-NEXT:  // Label [[GRP_LABEL_NUM]]: @[[GRP_LABEL]]
 
 def SEXTLOAD : I<(outs GPR32:$dst), (ins GPR32:$src1),
                  [(set GPR32:$dst, (sextloadi16 GPR32:$src1))]>;
 
 //===- Test a pattern with an MBB operand. --------------------------------===//
 
-// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 24*/ [[LABEL:[0-9]+]],
+// OPT-NEXT:  GIM_Try, /*On fail goto*//*Label [[GRP_LABEL_NUM:[0-9]+]]*/ [[GRP_LABEL:[0-9]+]],
+// OPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_BR,
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/1,
-// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_BR,
+// NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_BR,
+// OPT-NEXT:      // No instruction predicates
 // CHECK-NEXT:    // MIs[0] target
 // CHECK-NEXT:    GIM_CheckIsMBB, /*MI*/0, /*Op*/0,
 // CHECK-NEXT:    // (br (bb:{ *:[Other] }):$target) => (BR (bb:{ *:[Other] }):$target)
 // CHECK-NEXT:    GIR_MutateOpcode, /*InsnID*/0, /*RecycleInsnID*/0, /*Opcode*/MyTarget::BR,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 24: @[[LABEL]]
+// CHECK-NEXT:  // Label [[LABEL_NUM]]: @[[LABEL]]
+// Closing the G_BR group.
+// OPT-NEXT:      GIM_Reject,
+// OPT-NEXT:  GIR_Done,
+// OPT-NEXT:  // Label [[GRP_LABEL_NUM]]: @[[GRP_LABEL]]
 
 def BR : I<(outs), (ins unknown:$target),
             [(br bb:$target)]>;
 
 // CHECK-NEXT:    GIM_Reject,
 // CHECK-NEXT:  };
 // CHECK-NEXT:  if (executeMatchTable(*this, OutMIs, State, MatcherInfo, MatchTable0, TII, MRI, TRI, RBI, AvailableFeatures, CoverageInfo)) {
 // CHECK-NEXT:    return true;
 // CHECK-NEXT:  }

llvm/trunk/utils/TableGen/GlobalISelEmitter.cpp

static cl::opt<bool> GenerateCoverage(
     cl::desc("Generate coverage instrumentation for GlobalISel"),
     cl::init(false), cl::cat(GlobalISelEmitterCat));
 
 static cl::opt<std::string> UseCoverageFile(
     "gisel-coverage-file", cl::init(""),
     cl::desc("Specify file to retrieve coverage information from"),
     cl::cat(GlobalISelEmitterCat));
 
+static cl::opt<bool> OptimizeMatchTable(
+    "optimize-match-table",
+    cl::desc("Generate an optimized version of the match table"),
+    cl::init(true), cl::cat(GlobalISelEmitterCat));
+
 namespace {
 //===- Helper functions ---------------------------------------------------===//
 
-
 /// Get the name of the enum value used to number the predicate function.
 std::string getEnumNameForPredicate(const TreePredicateFn &Predicate) {
   return "GIPFP_" + Predicate.getImmTypeIdentifier().str() + "_" +
          Predicate.getFnName();
 }
 
 /// Get the opcode used to check this predicate.
 std::string getMatchOpcodeForPredicate(const TreePredicateFn &Predicate) {
MatchTable &operator<<(MatchTable &Table, const MatchTableRecord &Value) {
   Table.push_back(Value);
   return Table;
 }
 
 //===- Matchers -----------------------------------------------------------===//
 
 class OperandMatcher;
 class MatchAction;
+class PredicateMatcher;
+class RuleMatcher;
+
+class Matcher {
+public:
+  virtual ~Matcher() = default;
+  virtual void emit(MatchTable &Table) = 0;
+};
+
+class GroupMatcher : public Matcher {
+  SmallVector<std::unique_ptr<PredicateMatcher>, 8> Conditions;
+  SmallVector<Matcher *, 8> Rules;
+
+public:
+  void addCondition(std::unique_ptr<PredicateMatcher> &&Predicate) {
+    Conditions.emplace_back(std::move(Predicate));
+  }
+  void addRule(Matcher &Rule) { Rules.push_back(&Rule); }
+  const std::unique_ptr<PredicateMatcher> &conditions_back() const {
+    return Conditions.back();
+  }
+  bool lastConditionMatches(const PredicateMatcher &Predicate) const;
+  bool conditions_empty() const { return Conditions.empty(); }
+  void clear() {
+    Conditions.clear();
+    Rules.clear();
+  }
+  void emit(MatchTable &Table) override;
+};
 
 /// Generates code to check that a match rule matches.
-class RuleMatcher {
+class RuleMatcher : public Matcher {
 public:
   using ActionVec = std::vector<std::unique_ptr<MatchAction>>;
   using action_iterator = ActionVec::iterator;
 
 protected:
   /// A list of matchers that all need to succeed for the current rule to match.
   /// FIXME: This currently supports a single match position but could be
   /// extended to support multiple positions to support div/rem fusion or
getComplexSubOperand(StringRef SymbolicName) const {
     return I->second;
   }
 
   const InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const;
   const OperandMatcher &getOperandMatcher(StringRef Name) const;
 
   void emitCaptureOpcodes(MatchTable &Table);
 
-  void emit(MatchTable &Table);
+  void emit(MatchTable &Table) override;
 
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
   bool isHigherPriorityThan(const RuleMatcher &B) const;
 
   /// Report the maximum number of temporary operands needed by the rule
   /// matcher.
   unsigned countRendererFns() const;
 
+  std::unique_ptr<PredicateMatcher> forgetFirstCondition();
+
   // FIXME: Remove this as soon as possible
-  InstructionMatcher &insnmatcher_front() const { return *Matchers.front(); }
+  InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); }
 
   unsigned allocateOutputInsnID() { return NextOutputInsnID++; }
   unsigned allocateTempRegID() { return NextTempRegID++; }
+
+  bool insnmatchers_empty() const { return Matchers.empty(); }
+  void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); }
 };
 
 uint64_t RuleMatcher::NextRuleID = 0;
 
 using action_iterator = RuleMatcher::action_iterator;
 
 template <class PredicateTy> class PredicateListMatcher {
 private:
typename PredicateVec::const_iterator predicates_end() const {
     return Predicates.end();
   }
   iterator_range<typename PredicateVec::const_iterator> predicates() const {
     return make_range(predicates_begin(), predicates_end());
   }
   typename PredicateVec::size_type predicates_size() const {
     return Predicates.size();
   }
+  bool predicates_empty() const { return Predicates.empty(); }
+
+  std::unique_ptr<PredicateTy> predicates_pop_front() {
+    std::unique_ptr<PredicateTy> Front = std::move(Predicates.front());
+    Predicates.erase(Predicates.begin());
+    return Front;
+  }
 
   /// Emit MatchTable opcodes that tests whether all the predicates are met.
   template <class... Args>
   void emitPredicateListOpcodes(MatchTable &Table, Args &&... args) const {
     if (Predicates.empty()) {
       Table << MatchTable::Comment(getNoPredicateComment())
             << MatchTable::LineBreak;
       return;
public:
   iterator_range<OperandVec::iterator> operands() {
     return make_range(operands_begin(), operands_end());
   }
   OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
   OperandVec::const_iterator operands_end() const { return Operands.end(); }
   iterator_range<OperandVec::const_iterator> operands() const {
     return make_range(operands_begin(), operands_end());
   }
+  bool operands_empty() const { return Operands.empty(); }
+
+  void pop_front() { Operands.erase(Operands.begin()); }
 
   /// Emit MatchTable opcodes to check the shape of the match and capture
   /// instructions into the MIs table.
   void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) {
     Table << MatchTable::Opcode("GIM_CheckNumOperands")
           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
           << MatchTable::Comment("Expected")
           << MatchTable::IntValue(getNumOperands()) << MatchTable::LineBreak;
private:
   /// Analyze pattern \p P, returning a matcher for it if possible.
   /// Otherwise, return an Error explaining why we don't support it.
   Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
 
   void declareSubtargetFeature(Record *Predicate);
 
   TreePatternNode *fixupPatternNode(TreePatternNode *N);
   void fixupPatternTrees(TreePattern *P);
+
+  /// Takes a sequence of \p Rules and group them based on the predicates
+  /// they share. \p StorageGroupMatcher is used as a memory container
+  /// for the the group that are created as part of this process.
+  /// The optimization process does not change the relative order of
+  /// the rules. In particular, we don't try to share predicates if
+  /// that means reordering the rules (e.g., we won't group R1 and R3
+  /// in the following example as it would imply reordering R2 and R3
+  /// => R1 p1, R2 p2, R3 p1).
+  ///
+  /// What this optimization does looks like:
+  /// Output without optimization:
+  /// \verbatim
+  /// # R1
+  ///  # predicate A
+  ///  # predicate B
+  ///  ...
+  /// # R2
+  ///  # predicate A // <-- effectively this is going to be checked twice.
+  ///                //     Once in R1 and once in R2.
+  ///  # predicate C
+  /// \endverbatim
+  /// Output with optimization:
+  /// \verbatim
+  /// # Group1_2
+  ///  # predicate A // <-- Check is now shared.
+  ///  # R1
+  ///   # predicate B
+  ///  # R2
+  ///   # predicate C
+  /// \endverbatim
+  std::vector<Matcher *> optimizeRules(
+      std::vector<RuleMatcher> &Rules,
+      std::vector<std::unique_ptr<GroupMatcher>> &StorageGroupMatcher);
 };
 
 void GlobalISelEmitter::gatherNodeEquivs() {
   assert(NodeEquivs.empty());
   for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
     NodeEquivs[Equiv->getValueAsDef("Node")] = Equiv;
 
   assert(ComplexPatternEquivs.empty());
void GlobalISelEmitter::emitImmPredicates(
   OS << "static InstructionSelector::" << TypeIdentifier
      << "ImmediatePredicateFn " << TypeIdentifier << "ImmPredicateFns[] = {\n"
      << "  nullptr,\n";
   for (const auto *Record : MatchedRecords)
     OS << "  Predicate_" << Record->getName() << ",\n";
   OS << "};\n";
 }
 
+std::vector<Matcher *> GlobalISelEmitter::optimizeRules(
+    std::vector<RuleMatcher> &Rules,
+    std::vector<std::unique_ptr<GroupMatcher>> &StorageGroupMatcher) {
+  std::vector<Matcher *> OptRules;
+  // Start with a stupid grouping for now.
+  std::unique_ptr<GroupMatcher> CurrentGroup = make_unique<GroupMatcher>();
+  assert(CurrentGroup->conditions_empty());
+  unsigned NbGroup = 0;
+  for (RuleMatcher &Rule : Rules) {
+    std::unique_ptr<PredicateMatcher> Predicate = Rule.forgetFirstCondition();
+    if (!CurrentGroup->conditions_empty() &&
+        !CurrentGroup->lastConditionMatches(*Predicate)) {
+      // Start a new group.
+      ++NbGroup;
+      OptRules.push_back(CurrentGroup.get());
+      StorageGroupMatcher.emplace_back(std::move(CurrentGroup));
+      CurrentGroup = make_unique<GroupMatcher>();
+      assert(CurrentGroup->conditions_empty());
+    }
+    if (CurrentGroup->conditions_empty())
+      CurrentGroup->addCondition(std::move(Predicate));
+    CurrentGroup->addRule(Rule);
+  }
+  if (!CurrentGroup->conditions_empty()) {
+    ++NbGroup;
+    OptRules.push_back(CurrentGroup.get());
+    StorageGroupMatcher.emplace_back(std::move(CurrentGroup));
+  }
+  DEBUG(dbgs() << "NbGroup: " << NbGroup << "\n");
+  return OptRules;
+}
+
 void GlobalISelEmitter::run(raw_ostream &OS) {
   if (!UseCoverageFile.empty()) {
     RuleCoverage = CodeGenCoverage();
     auto RuleCoverageBufOrErr = MemoryBuffer::getFile(UseCoverageFile);
     if (!RuleCoverageBufOrErr) {
       PrintWarning(SMLoc(), "Missing rule coverage data");
       RuleCoverage = None;
     } else {
if (RuleCoverage) {
         ++NumPatternsTested;
       else
         PrintWarning(Pat.getSrcRecord()->getLoc(),
                      "Pattern is not covered by a test");
     }
     Rules.push_back(std::move(MatcherOrErr.get()));
   }
 
-  std::stable_sort(Rules.begin(), Rules.end(),
-            [&](const RuleMatcher &A, const RuleMatcher &B) {
-              if (A.isHigherPriorityThan(B)) {
-                assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
-                                                     "and less important at "
-                                                     "the same time");
-                return true;
-              }
-              return false;
-            });
-
   std::vector<Record *> ComplexPredicates =
       RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
   std::sort(ComplexPredicates.begin(), ComplexPredicates.end(),
             [](const Record *A, const Record *B) {
               if (A->getName() < B->getName())
                 return true;
               return false;
             });
<< "  // FIXME: This should be computed on a per-function basis rather "
         "than per-insn.\n"
      << "  AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, "
         "&MF);\n"
      << "  const PredicateBitset AvailableFeatures = getAvailableFeatures();\n"
      << "  NewMIVector OutMIs;\n"
      << "  State.MIs.clear();\n"
      << "  State.MIs.push_back(&I);\n\n";
 
+  std::stable_sort(Rules.begin(), Rules.end(), [&](const RuleMatcher &A,
+                                                   const RuleMatcher &B) {
+    if (A.isHigherPriorityThan(B)) {
+      assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
+                                           "and less important at "
+                                           "the same time");
+      return true;
+    }
+    return false;
+  });
+  std::vector<std::unique_ptr<GroupMatcher>> StorageGroupMatcher;
+
+  std::vector<Matcher *> OptRules;
+  if (OptimizeMatchTable)
+    OptRules = optimizeRules(Rules, StorageGroupMatcher);
+  else
+    for (Matcher &Rule : Rules)
+      OptRules.push_back(&Rule);
+
   MatchTable Table(0);
-  for (auto &Rule : Rules) {
-    Rule.emit(Table);
+  for (Matcher *Rule : OptRules) {
+    Rule->emit(Table);
     ++NumPatternEmitted;
   }
   Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
   Table.emitDeclaration(OS);
   OS << "  if (executeMatchTable(*this, OutMIs, State, MatcherInfo, ";
   Table.emitUse(OS);
   OS << ", TII, MRI, TRI, RBI, AvailableFeatures, CoverageInfo)) {\n"
      << "    return true;\n"
void GlobalISelEmitter::fixupPatternTrees(TreePattern *P) {
   for (unsigned I = 0, E = P->getNumTrees(); I < E; ++I) {
     TreePatternNode *OrigTree = P->getTree(I);
     TreePatternNode *NewTree = fixupPatternNode(OrigTree);
     if (OrigTree != NewTree)
       P->setTree(I, NewTree);
   }
 }
 
+std::unique_ptr<PredicateMatcher> RuleMatcher::forgetFirstCondition() {
+  assert(!insnmatchers_empty() &&
+         "Trying to forget something that does not exist");
+
+  InstructionMatcher &Matcher = insnmatchers_front();
+  std::unique_ptr<PredicateMatcher> Condition;
+  if (!Matcher.predicates_empty())
+    Condition = Matcher.predicates_pop_front();
+  if (!Condition) {
+    // If there is no more predicate on the instruction itself, look at its
+    // operands.
+    assert(!Matcher.operands_empty() &&
+           "Empty instruction should have been discarded");
+    OperandMatcher &OpMatcher = **Matcher.operands_begin();
+    assert(!OpMatcher.predicates_empty() && "no operand constraint");
+    Condition = OpMatcher.predicates_pop_front();
+    // If this operand is free of constraints, rip it off.
+    if (OpMatcher.predicates_empty())
+      Matcher.pop_front();
+  }
+  // Rip the instruction off when it is empty.
+  if (Matcher.operands_empty() && Matcher.predicates_empty())
+    insnmatchers_pop_front();
+  return Condition;
+}
+
+bool GroupMatcher::lastConditionMatches(
+    const PredicateMatcher &Predicate) const {
+  const auto &LastCondition = conditions_back();
+  return Predicate.isIdentical(*LastCondition);
+}
+
+void GroupMatcher::emit(MatchTable &Table) {
+  unsigned LabelID = Table.allocateLabelID();
+  if (!conditions_empty()) {
+    Table << MatchTable::Opcode("GIM_Try", +1)
+          << MatchTable::Comment("On fail goto")
+          << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
+    for (auto &Condition : Conditions)
+      Condition->emitPredicateOpcodes(
+          Table, *static_cast<RuleMatcher *>(*Rules.begin()));
+  }
+  // Emit the conditions.
+  // Then checks apply the rules.
+  for (const auto &Rule : Rules)
+    Rule->emit(Table);
+  // If we don't succeeded for that block, that means we are not going to select
+  // this instruction.
+  if (!conditions_empty()) {
+    Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
+    Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
+          << MatchTable::Label(LabelID);
+  }
+}
+
 unsigned OperandMatcher::getInsnVarID() const { return Insn.getVarID(); }
 
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//
 
 namespace llvm {
 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
   GlobalISelEmitter(RK).run(OS);
 }
 } // End llvm namespace