[GlobalISel][utils] Adding the init version of Instruction Select Testgen

[rtereshin]

Summary

This is the first version of the testgen - a tool, currently implemented as an
llc MIR-pass, that generates regression lit-tests for GlobalISel's Instruction
Selector. The generation is done on rule-by-rule basis and currently covers
selection rules automatically imported by TableGen from SelectionDAGISel.

This is a prerequisite for the tests generated for

1. AArch64: https://reviews.llvm.org/D43976
2. ARM: https://reviews.llvm.org/D43979
   1. updated in https://reviews.llvm.org/D43982 (this also demonstrates how the tests could be updated when GlobalISel changes)
3. X86: https://reviews.llvm.org/D43994 (this also demonstrates the usefulness of ABI speculation done by Testgen)

What this tool is and isn't:

1. This is not a fuzzer for Instruction Selector, it isn't trying to come up with a malicious input for it and break it, nor it's trying to discover bugs in it.

2. This is a regression testing tool, it's main goal is to capture the current state of the GlobalISel's InstructionSelect pass providing the best test coverage for it with small and highly targeted tests that pass, and catch any regressions later due to changes in:
   1. *.td-definitions of the instructions and selection patterns;
   2. GlobalISel's emitter (the TableGen backend), including the ones that intend to change rules' priorities and the ones that don't;
   3. manually written parts of the Instruction Selector.

3. Potentially this is also an analysis tool that may make it easier to see and control the actual effects of changes like listed above on the Selector, detect dead rules, etc.

4. It may be extended in the future to generate tests for other passes of the GlobalISel's pipeline, and / or have a fuzzer mode of operation, but currently these aren't the goals.

5. It also may be turned into a benchmark-gen for Instruction Selector relatively easily. That way we could benchmark the Selector on large inputs created in-memory, avoiding huge (~90%) overhead of parsing MIR off disk, and having the input with any desirable probabilities of any pattern supported, as well as having only the patterns supported, avoiding any input that is not selectable, thus getting more stable, targeted, and precise performance data.

Potential user stories:

1. New backend development.
2. Porting an existing backend from SelectionDAG ISel to GlobalISel.

While the first one is promising, it appears that the second one is more
prominent right now and therefore the main target of this tool.

Design goals:

1. As we mostly care about providing regression testing of InstructionSelect pass of GlobalISel's implementations early in the development for pre-existing targets, we can not rely on any other GlobalISel passes being well-developed and fully functional, in particular, we expect InstructionSelect pass to be well ahead everything else due to the semi-automatic porting mechanism.
   
   See https://reviews.llvm.org/rL326396 as an example of breaking ties with the Legalizer, selectUnconstrainedRegBanks of this patch as an example of the same w.r.t. RegBankSelect.

2. We want the testgen to be relatively robust and able to handle gracefully non-functional changes, for instance, changes in the typical order of the MatchTable opcodes for rules, or even presense of specific opcodes, like the number of operands check, or changes in concrete serialization format for MIR.

3. We want the testgen to be as target-independent and generic as possible and impose as less maintainance burden on backend writers as possible.

4. If it's not jeopardizing other goals and not too difficult to do, we want testgen to generate naturally-looking tests that are likely to come out the same if written by a human.

Design decisions made:

1. Current implementation of testgen uses TableGen'erated MatchTable's to generate the tests. We could've branched off input data-wise earlier, but that would mean re-implementing too much of the GlobalISel's emitter.

2. We're using only matching parts of the MatchTable to generate MIR and relying on the selector itself to generate FileCheck's for the expected output for a few major reasons:
   1. it simplifies the implementation;
   2. it reduces the number of tests failing as of time of their generation due to the MIR being selected not by a rule intended, which is desirable as we aren't fuzzing the selector, but trying to generate passing tests;

Usage:

llc -mtriple aarch64-- -run-pass instruction-select-testgen -simplify-mir input.mir -o output.mir

will add a number of Machine Function's, one per every imported *.td-defined
selection rule, into intput.mir and write the result as output.mir.

Command line options:

1. -testgen-from-rule=N -testgen-until-rule=M - generate tests for a subrange of rules only;

2. -testgen-exclude-rules=N{,N} - skip specific rules;

3. -testgen-include-only=N{,N} - generate tests for explicitly listed rules only;

4. -testgen-set-all-features - speculatively satisfy all target / module / and function features requirements to cover feature-specific rules;

5. -testgen-no-abi - don't speculate on ABI boundaries tring to make the test look natural and test COPY's selection, but just IMPLICIT_DEF undefined vregs instead.

Note:
-testgen-no-abi=false tried to emit real RET opcodes at some point by using
CallLowering::lowerReturn and deriving IR Types from LLTs, but it proved
to be unreliable for most targets and created an extra dependency.

This patch also provides utils/update_instruction_select_testgen_tests.sh tool
that would generate a couple of lit-tests:

usage: ./utils/update_instruction_select_testgen_tests.sh <testgen'd file> <llc binary> <target triple> [extra llc args]

for instance, executing

../../utils/update_instruction_select_testgen_tests.sh ../../test/CodeGen/AArch64/GlobalISel/arm64-instruction-select-testgen-testgend.mir ./bin/llc aarch64--

from a build/obj directory would create 2 files:

../../test/CodeGen/AArch64/GlobalISel/arm64-instruction-select-testgen-testgend.mir
and
../../test/CodeGen/AArch64/GlobalISel/arm64-instruction-select-testgen-selected.mir

testing that the testgen outputs the same MIR and the selector selects that MIR
the same way respectively.

Coverage:

Target  | Rules    | Fail to | Tests     | Selected by the
        | Imported | Select  | Generated | Rule Intended
--------+----------+---------+-----------+----------------
AArch64 |  1654    |  0.0%   |  1449     |  85%
ARM     |  1055    |  0.2%   |   991     |  78%
x86     |   887    | 13.8%   |   765     |  68%

"Fail to Select" stands for "a generated test crashed / asserted the selector",
this is something to -testgen-exclude-rules in practice. The major reason
for this right now is a limited support of COPY_TO_REGCLASS in *.td-defined
patterns by the GlobalISel importing mechanism.

"Selected by the Rule Intended" basically means the target coverage provided by
the tool. A test could be selected by a rule different from the rule that was
used to generate it for a variety of reasons, approximately in order from most
prominent ones to the rarest ones:

1. The test generated isn't specific enough due to:
   1. lack of support of complex patterns by the testgen;
   2. too basic support of immediate predicates by the testgen;
   3. rules genuinely intersecting with each other and local approach of the testgen not considering rules partially hiding each other.

2. A rule is genuinely dead and
   1. it was rendered dead by GlobalISel;
   2. it was dead in SelectionDAG ISel to beging with;
   3. it is rendered dead by manually written parts of the selector executing before trying TableGen'erated selectImpl.

Known deficiencies:

1. Testgen could not be currently easily extended by a target to support complex patterns, which should greatly improve coverage.

2. Testgen's way of dealing with features is very sketchy at the moment and needs to improved.

3. Testgen should probably be a separate from llc binary tool

approximately from the most important to fix soon to the least important.

A couple of dependencies for this patch as well as the tests generated
are coming soon in separate patches.

See also test/CodeGen/AArch64/GlobalISel/select-with-no-legality-check.mir
currently committed for an example output of the testgen.

[rtereshin]

Fixing a little non-determinism in picking live-in phys regs used to define input vregs.

[rtereshin]

fixing little formatting issues, NFC

[rtereshin]

Performance

or why all the tests are in a single file?

in short, with test cases in separate test-files it takes at least ~30 times (or at least 2 minutes just for AArch64 and only for the rules currently imported by GlobalISel emitter) longer to update the tests, and at least 15 times (or at least 40 seconds just for AArch64 and only for the rules currently imported by GlobalISel emitter) longer to run the tests on 4-cores SSD-only iMac running macOS depending on a build type. In some cases, the difference reaches 130x / 5 minutes.

With all the tests in a single file it takes about 2 seconds to update them for AArch64 at the moment, and about 1.33 seconds to run them on the same machine as described above (both tests ran in parallel, where the test testing the Testgen itself takes ~1/3 of a second, and the test testing the Instruction Selector takes the full 1.33 seconds).

[rtereshin]

1. Rebased against master.
2. GIM_RecordInsn handler is made more tolerant to alternative orderings of GIM_RecordInsn's with respect to other opcodes while matching multi-instruction patterns.
3. A use-after-free bug is fixed in emitReturnIntoTestCase caught by ASAN.

[aemerson]

Hi Roman,

This is a very large patch with lots of complexity, and is hard to review. While your description outlines the general idea of the tool, there's little documentation in the code of how this actually works under the hood. Can you add more descriptions so someone can follow what's happening when it comes to maintenance later, e.g. what's LiveInRA supposed to do, what are the pre-conditions and expected outputs of each phase of this tool?

Without that I suspect this patch will continue to lie in the review queue for a long while.

Thanks,
Amara

[rtereshin]

In D43962#1048769, @aemerson wrote:

Hi Roman,

This is a very large patch with lots of complexity, and is hard to review. While your description outlines the general idea of the tool, there's little documentation in the code of how this actually works under the hood. Can you add more descriptions so someone can follow what's happening when it comes to maintenance later, e.g. what's LiveInRA supposed to do, what are the pre-conditions and expected outputs of each phase of this tool?

Without that I suspect this patch will continue to lie in the review queue for a long while.

Thanks,
Amara

Hi Amara,

Thanks for taking a look at this! Will do.

[rtereshin]

Brining perf-data up as the comment is hidden due to the diff update: https://reviews.llvm.org/D43962#1026201

[dsanders]

Aside from being a large patch with few function-level comments, some of the non-functional changes also make this difficult to review. It would be helpful to move things like the indentation correction on testImm*(), the introduction of buildTable and getMatchTable(), the changes to coverage, moving the emission of selectImpl() down, etc. into a separate patch(es).

I think the overall approach of parsing the match table, emitting something that matches, and constructing some scaffolding around it is a good plan. We'll need to find a good way of handling immediates, C++ predicates, ComplexPattern and similar but that should definitely be left for later patches.

Some targets have a rather large number of rules (e.g. X86 is around 17k IIRC). Do we have a mechanism for keeping the number of generated tests to a reasonable level?

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

225

Is this comment accurate? GIR_AddRegister is listed as having 2 operands and I only see 2 in my build

include/llvm/CodeGen/GlobalISel/InstructionSelectorTestgen.h

27–29

This one probably isn't harmful since InstructionSelectorTestgen.h isn't going to be widely included but we ought to avoid anonymous namespaces in headers since each compilation unit that includes the header will get it's own version of the declaration. It's probably best to put it in the llvm namespace if we can't push it into the cpp entirely.

InstructionSelectorTestgen doesn't seem to have any state so it looks like generateTestCase() could be a static function outside the class

33–38

Are all of these really needed in the header? Most seem to only be used from InstructionSelectorTestgen.cpp

include/llvm/Support/CodeGenCoverage.h

26

Just a small nit: we should probably have 'const' somewhere in the 'covered_iterator' name.

lib/CodeGen/GlobalISel/InstructionSelectTestgen.cpp

46–48

Could you add a comment indicating that verification is the only thing we do with these functions and why?

lib/CodeGen/GlobalISel/InstructionSelectorTestgen.cpp

59

If the function already exists somehow then this might not return an empty test case due to the getOrInsertFunction() we should probably fail in that case

103

LLT's scalars aren't always integers. So long as we inject bitcasts this will be fine though

124

If I understand correctly, this is a register allocator that is used to generate the live-ins for the test function. This needs some explaining in the comments and possibly also renaming (I don't have a good spelling for it, maybe InputRegAllocator)

274–309

This lambda is getting pretty big. I'd be inclined to make it a static function in its own right

283

I think a word is missing from "of the required by"

307

greadily -> greedily

344–346

As a general thing: Writes to dbgs() should generally be wrapped in DEBUG(...) or DEBUG_ONLY(...) so that we don't format strings we're not going to emit.

354

I'm not sure IMPLICIT_DEF is the right thing to use for these if-statements. IMPLICIT_DEF is a definition with an unknown value (much like UNDEF) so it wouldn't be wrong to propagate it in something like

%0 = IMPLICIT_DEF
%2 = G_ADD %0, %1

to:

%2 = IMPLICIT_DEF

a COPY of a live-in phys-reg would be safer but it's probably ok since constant propagation isn't ISel's job. I think this would only become an issue if we started porting this to combiners.

367

This table is going to be quite fragile. We should at put this somewhere near the GIM_*/GIR_* declarations or at least cross-reference them in the comments. Tablegen-erating them might be sensible if we get additional metadata.

422

If we have a rule with variadic instructions, what do we do about the number of defs?

469

Is this ever false? ensureNumOperands() looks like it adds operands until this is true

485

What is this for?

486–489

This comment explains the reasons behind something but doesn't really explain what that something is

498

I don't think I understand this variable. What does it represent?

503

This should probably indicate what is being skipped

504

In some ways it would be nice to support this (e.g. to check the tests are the same) but I agree it's way too big a task for a first patch.

505–511

Doesn't NDEBUG also disable the dbgs() stream?

That assert can't succeed (NestingLevel > 1 vs NestingLevel == 1). It looks like this ought to be report_fatal_error() or similar

597

I don't think I understand the Def.getReg() part of this. Both the Use and the Def must be the same register so I'd expect to always use one or the other for all cases.

681–682

Function-level features can be handled by listing them in the function attributes:

attributes #0 = { "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" }

The tricky bit will be mapping the enum back to the feature name.

Module-level features are harder since they're only read once per module. You'd have to separate them into multiple files

715

There's no guarantee that 1 will match. There's a few predicates that check they're multiples of N

761–784

One thing to mention here is that if something changes the register number of OtherInsnB.getOperand(OtherOpIdx) after this opcode is processed then these might diverge. I think we're ok on that since setReg() doesn't seem to be called from latePass()

796

As with the other immediate case, '1' might not match all predicates

849

I was confused by this function name at first. It sounded like the regbanks were unconstrained and that didn't make sense. I see it's about assigning regbanks to vregs that don't already check one. I haven't thought of a good spelling ('assignRegBanksToUnconstrainedVregs()' or 'ensureRegistersHaveBanks()' are a couple ideas) but we may be able to find a clearer name.

884

We should have a couple examples of how duplicates can happen (e.g. i32 and f32 both mapping to s32)

utils/TableGen/GlobalISelEmitter.cpp

3983–4073

It seems that this block has been moved down from the other side of the sort. Non-functional changes like this ought to be in separate patches

4005

This definition should probably be wrapped in a #ifdef

utils/update_instruction_select_testgen_tests.sh

40–43

The 'perl' commands might be an issue for the windows bots.

[rtereshin]

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

225

The comments in this section describe an opcode below the comments, not above. So this is all about GIR_AddTempRegister and it appears to have 3 operands (https://github.com/llvm-mirror/llvm/blob/master/include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h#L598-L601)

include/llvm/CodeGen/GlobalISel/InstructionSelectorTestgen.h

27–29

That's a good insight, thanks, I didn't think of that.

generateTestCase calls virtual member-functions and may do so more in the future and I'd rather keep it that way and keep it a class member.

I'm moving the helper class (LiveInRA or however we would (re)name it) in InstructionSelectorTestgenas a member-class instead, I hope that solves the problem well enough.

33–38

Only TestgenSetAllFeatures is required to be here as it's used by the instruction selector itself.

I'm not exactly sure why not to list all the options in a header, in a sense it's part of its interface, CLI in this case, but sure, I'll remove all of those that don't have to be here. After all, nothing would force this list to be complete, so maybe it's better if it's explicitly incomplete, and also this is rarely (if ever) done across other parts of LLVM.

include/llvm/Support/CodeGenCoverage.h

26

Sure, good catch! I'm renaming it to const_covered_iterator

lib/CodeGen/GlobalISel/InstructionSelectTestgen.cpp

46–48

Sure, adding the following comment:

// Generally it is possible to run the Testgen over a non-empty module,
// practically probably a lit-test, and have it add additional test-cases
// to it. The easiest way to limit the number of verification failures on
// the final output caused by initially present machine functions rather
// than the ones added, is to run the verification on those already
// present functions first.

lib/CodeGen/GlobalISel/InstructionSelectorTestgen.cpp

59

True. Let's just MachineFunction::reset() it for now if such a thing happens, that would make llc update the existing test cases if ran over an already generated test-module. It's a sensible thing to do, I think.

Generally, if not reset, it would actually just add another machine basic block and repeat the instruction sequence derived from the selection rule, so we'll end up with a single machine-function test-case with multiple identical basic blocks testing the same pattern. W/ no bug fixes it will screw up the ABI lowering at the moment though, so it will only work for patterns w/ no input vregs, such as having only constants for operands. And that means it will generate a small test-module, it won't fail or crash, but rather just filter out the broken machine functions using machine verifier, as it always does. Or tries to, at least.

Technically, I'm still considering turning this into a sort of a benchmark-gen, not sure at the moment if that could be actually useful though. Theoretically, we could have a tool that will be able to generate long def-use chains of instruction sequences corresponding to a particular pattern or a subset of pattern in a type-driven manner and use them to benchmark the selector as well as other parts of the pipeline.

103

They aren't, but it appears to me that this is the best we could do w/o going to great lengths, as the information about the actual type is pretty much lost at match table level.

At some point, I tried to lower ABI, specifically to insert an appropriate return sequence, by re-using CallLoweringInfo::lowerReturn provided by the target. The method expects an LLVM Value, however, the targets only analyze (or were at the moment) the Value's type, so it seemed sufficient to provide it an IR constant of an appropriate IR type.

It didn't work our for a number of reasons, most notably not all the targets could handle all the types, especially vector types. So I started to use the PATCHABLE_RET instead for this purpose.

So currently deduceIRType is only used to build appropriate machine memory operands to make GIM_CheckAtomicOrdering happy, specifically, figure out a reasonable size and alignment. As the size is directly inferable from LLT, this is mostly to figure out the alignment.

124

Your understanding is correct.

I'm adding the following comment:

+/// A helper providing sensible phys regs to define patterns' input vregs.
+///
+/// It appears that the most portable and robust way to define all the input
+/// vregs (used, but not defined) of an instruction sequence being generated is
+/// to define them as COPY's from appropriate and preferably distinct physical
+/// registers, live-in to the basic containing the instruction sequence and
+/// preferably the entire function as well. The best pick is to have the same
+/// size in bits as the vreg, same register bank, to be allocatable, and from
+/// the beginning of the allocation order. The class also handles the following
+/// issues:
+///
+/// 1) RegisterBankInfo::getRegBankFromRegClass not being defined for
+///   tablegen'erated reg classes.
+/// 2) Register classes containing the same physical register and yet having
+///   different sizes, and therefore physical registers having only weekly
+///   defined size as the maximum of the sizes of all register classes they
+///   belong to.
+/// 3) Register banks not having a full list of register sizes available
+///   directly.
+///
+/// The latter is also used for picking sensible register banks for internal
+/// (defined and used both by the instruction sequence being generated) vregs.

and renaming the class from LiveInRA to InputRegAllocator (from (anonymous namespace)::LiveInRA to llvm::InstructionSelectorTestgen::InputRegAllocator to be exact).

274–309

Agreed, doing that.

I'm also changing Size2RegBanksTy from DenseMap to std::map, that gets rid of the extracting keys (Sizes) and sorting them every time, makes the implementation a little simpler and reduces the number of arguments (former closure captured variables) of the static function being extracted.

283

An example sentence would be "Didn't find a register bank containing allocatable registers of the required by LLT <2 x s16> size of 32 bits or larger for an unconstrained vreg %1".

Breaking it down as follows:
"Didn't find a register bank containing allocatable registers of a compatible size; vreg: %1(<2 x s16>), size: 32 bits (or larger)."

307

Oops, good catch, thanks!

354

COPY of a live-in phys-reg would be safer

It is, this is why I'm using IMPLICIT_DEF only if I couldn't find a phys-reg with the appropriate size and within the required register bank (or if this behavior is explicitly requested by a command line option).

367

Agreed. I'm making this less fragile by doing the following:

1. Specifying a list of pairs implicitly defining a mapping from an opcode to its number of operands instead so
   1. there is no need to maintain the records in a specific order, matching the order of the opcode definitions
   2. opcodes are used directly, not just as a comment, thus making sure there are no non-existent opcodes mentioned in the list
2. adding assertions that would make sure that there are no opcodes missing from the mapping
3. putting the definition right next to the opcode definitions

469

Of course, the number of operands could be greater than OpIdx, ensureNumOperands doesn't add or remove operands in that case.

485

Often I need to create a generic virtual register w/o knowing which type is expected from it yet, and it's not exactly possible to create a virtual register w/o a type. This constant exists to be consistent with the type I use as a default / initial option.

utils/TableGen/GlobalISelEmitter.cpp

3983–4073

I'm extracting a number of patches from this one to break it down a little.

[rtereshin]

Hi Daniel @dsanders,

Thank you for looking into this and the detailed review.

It would be helpful to move things like the indentation correction on testImm*(), the introduction of buildTable and getMatchTable(), the changes to coverage, moving the emission of selectImpl() down, etc. into a separate patch(es).

I believe I have this done, please take a look at the extracted patches:
https://reviews.llvm.org/D46095
https://reviews.llvm.org/D46096
https://reviews.llvm.org/D46097
https://reviews.llvm.org/D46098

I'm also half-through the inline comments.

[rtereshin]

lib/CodeGen/GlobalISel/InstructionSelectorTestgen.cpp

344–346

Done.

so that we don't format strings we're not going to emit.

w/o DEBUG macro we actually emit all of this in assert and release builds likewise.

422

That's a very good question, thanks!

I suppose, I will have to replace NumDefs = InsnB->getDesc().NumDefs; line below with NumDefs = std::max(InsnB->getDesc().NumDefs, InsnB->getNumExplicitDefs()); as soon as we get MachineInstr::getNumExplicitDefs() merged in ;-) (https://reviews.llvm.org/D45640).

It will help, but won't solve the problem.

It's not a problem for now, though, as InstructionSelector can't really handle those either. For instance, record instruction opcode clearly assumes that the definition is always the operand 0.

When it does support the case, however, most likely it won't be doing that by checking how many definitions an instruction has, it will most likely just rely on MIR being valid.

That naturally assumes machine verifier can check this stuff. So I guess at some point machine verifier will special case instructions like G_UNMERGE_VALUES. We can implement that check in the machine verifier as unsigned getNumExplicitDefsExpected(const MachineInstr &I) refactored out and then checking if the actual I has the number of defs expected.

And then we can reuse getNumExplicitDefsExpected right here in Testgen.

If the generic opcode has a very flexible number of defs, as in, it's not derivable from the number of operands and their types (do we even have these?), it will probably be still all right, we just see the highest operand index that the pattern explicitly requires to be a definition (via record instruction opcodes, for instance), and we say that that operand is the last def (and of course every operand with a lower index is also a def). And that should produce a) valid MIR, we started by saying this mysterious opcode is very flexible with defs b) MIR that could be matched by the pattern, and it's all we care about.

Not to mention, if we end up having generic opcodes like this - with non-derivable number of defs and the number of defs having an impact on the instructions' semantics - we will end up having a match table opcode checking the number of defs explicitly.

But again, it's not a problem for now.

486–489

I'm replacing the comment with the following:

// Raw representation of a single match table rule as an ordered union of
// several continuous regions of the match table. The representation tries its
// best to ignore parts of the table that don't affect semantics of a single
// rule in isolation, like labels and rule IDs.
//
// Assuming that all the parts of the MatchTable that don't affect the
// selection process but only identify a rule, like GIR_Coverage opcodes, come
// within a rule as a single continuous block, the meaningful parts of the
// rule could be represented as some prefix (starting from the first
// non-control flow opcode, in other words, skipping GIM_Try and its
// label-operand) and suffix:
using RuleBodyTy = std::pair<ArrayRef<int64_t>, ArrayRef<int64_t>>;

498

I'm renaming the variable from CoverageBlockPassed to ExcludedRegionPassed and adding a bunch of comments that should make it clearer, like this:

// Get a rule descriptor, containing the index of its GIR_Done opcode, RuleID,
// and a raw representation of the entire body.
//
// \pre MatchTable is a non-optimized linear match table.
// \pre CurrentIdx points to the first (and only) GIM_Try opcode of the rule
//   that has all its semantically meaningless opcodes that to be excluded from
//   the body as a single continuous subregion somewhere.
// \post the prefix of the body is a range from the first opcode after the
//   initial GIM_Try until GIR_Coverage (or, more generally, the first
//   semantically meaningless opcode), the suffix is a range from the first
//   opcode after the last semantically meaningless opcode until GIR_Done
//   (exclusive).
static std::tuple<uint64_t, int64_t, RuleBodyTy>
getDoneIdxRuleIDAndBody(const int64_t *MatchTable, uint64_t CurrentIdx) {
  // skipping GIM_Try
  const uint64_t BodyIdx = nextGIOpcodeIdx(MatchTable, CurrentIdx);
  uint64_t ExcludedFirst = BodyIdx;
  uint64_t ExcludedLast = ExcludedFirst;
  // RuleID we discovered so far. Or the first one if we have many O_o
  int64_t FirstRuleID = -1;
  // Did we already iterated over that continuous region of unimportant opcodes
  // we are going to exclude from the body?
  bool ExcludedRegionPassed = false;
  unsigned NestingLevel = 0;
  do {

503

I'm adding the following comment:

// Skipping the OnFail label operand

504

It will be hard to make sure that the tests are the same.

For instance, let's suppose that non-optimized table does some meaningless checks, for instance, checks register banks on internal vregs (the registers defined and used inside the pattern and not being the pattern's overall inputs or outputs), while optimized table doesn't. Semantically they are the same, but in the case of the latter Testgen will have to guess more regbanks, and it might guess it differently (from what is explicitly checked by the non-optimized table). It makes no difference in the selected code, and the *selected test will pass, however, the *testgend test (and that one only tests the Testgen itself, not the selector) will be technically different.

Also, if optimization reorders opcodes, the Testgen might easily end up with different virtual register names, while keeping the actual def-use chain the same, or schedule the def-use chain differently.

Not to mention, it will noticeably increase the maintenance burden, and I think it's best to keep that at a minimum.

505–511

Doesn't NDEBUG also disable the dbgs() stream?

No, the only difference is that NDEBUG resolves dbgs() directly to errs() and therefore sends the output straight to stderr while in assert builds there is a circular buffer in the middle (that smart enough to flush if killed).

That assert can't succeed (NestingLevel > 1 vs NestingLevel == 1). It looks like this ought to be report_fatal_error() or similar

True, good catch, I'm tidying this up.

597

Both the Use and the Def must be the same register so I'd expect to always use one or the other for all cases.

They must be the same register by the end of this case, but we know little in the beginning. We know that Def is a register and that's about it. Either (and we don't know which) or both Def and Use could be %noregs (0). If one of them is an actual vreg (not %noreg) it might have a meaningful type or / and a bank assigned, and we can't loose that assignment. Technically, to make it even more robust we need to intersect both of their constraints here (what if both of them are valid vregs already, one has a bank checked, but not a type yet, and the other has the type checked, but not the bank?), but so far it was working pretty well as is.

681–682

Thanks, I didn't dig into this deep enough yet to know that for myself!

And yes, the mapping is the hardest part. So this is why that ugly TestgenSetAllFeatures command line option for now, to overcome this the cheap and dirty way. Of course, that strips us off testing the checking features part of every pattern and the match table as a whole.

This is for future patches and improvements, though.

715

Absolutely no guarantee. However, I actually took a quick look and it appeared to me that 1 would match more often then any other fixed constant, did't measure it though.

Full support for immediate predicates is for future patches.

761–784

True, and that's the whole point of having more than one pass: satisfying dependencies.

If the number and complexity of the dependencies were much greater, I would probably process the table once, "box" (as in incapsulate) every opcode (with its operands) in an object, and then sort the objects in a way that satisfies the dependencies.

However, the dependencies we've got seem to be simple enough to get away with just a few passes over the table, so I find the "an object per opcode" solution greatly over-engineered and not needed.

782

@dsanders This situation, btw, is very similar to the one with record instruction opcode: we don't know which register is defined and which is not, and we can not afford loosing the definition. With record instruction we don't know which register might already have LLT and / or regbank "checked", and we can't afford loosing that info.

796

For future patches.

849

I'm renaming selectUnconstrainedRegBanks to assignRegBanksToUnconstrainedVRegs and selectRegBank helper function (former lambda) to assignRegBank for consistency.

884

I'm adding the following comment:

// The major source of literal duplicates is the fact that we map MVTs
// like i32 and f32 to the same s32 LLT, therefore 2 or more patterns
// originally written for SelectionDAG ISel get imported as the exact same
// sequence of semantically meaningful match table opcodes, matching and
// rendering opcodes both:

utils/TableGen/GlobalISelEmitter.cpp

4005

It is wrapped in GET_GLOBALISEL_IMPL along with the InstructionSelector implementation. Due to InstructionSelector::getTestgen method we need the class definition even if we aren't planning to use testgen, but why would we not?

utils/update_instruction_select_testgen_tests.sh

40–43

sed is horrible with multiline patterns, hm... This script isn't required to run tests, only to generate / update them, so maybe we could deal with it a bit later. Maybe with a little help from somebody running windows?

[rtereshin]

Hi Daniel @dsanders

I've addressed all of the inline comments, I believe.

We'll need to find a good way of handling immediates, C++ predicates, ComplexPattern and similar but that should definitely be left for later patches.

Yes.

Some targets have a rather large number of rules (e.g. X86 is around 17k IIRC). Do we have a mechanism for keeping the number of generated tests to a reasonable level?

Not yet, but it's not a problem yet either as we import only a fraction of the rules as of now.

with few function-level comments

+ @aemerson (Hi Amara)

there's little documentation in the code of how this actually works under the hood. Can you add more descriptions so someone can follow what's happening when it comes to maintenance later, e.g. what's LiveInRA supposed to do, what are the pre-conditions and expected outputs of each phase of this tool?

All of this improved noticeably, I hope, but not everything is commented and I'll probably add on it later.

Thank you!
Roman

[rtereshin]

1. Improved in-source comments
2. Improved usability and scripts, in particular, added find_failing_instruction_select_rules.sh script that will automatically find the selection rules that will fail if executed (most of the time will crash the selector)
3. Added support for extending loads / truncating stores MatchTable checks
4. Rebased against master and re-solved namespace / visibility issues introduced by AMDGPU backend (the only backend that put its target-specific derived InstructionSelector's declaration in a header)
5. Increased Testgen's tolerance towards register banks quirks: AMD GPU is the only backend that has banks "covering" register classes that span cross multiple banks.
6. Decreased invasiveness of the patch in its surroundings, especially within the global isel emitter.
7. Made sure that if the tests are updated they are updated in place as much as possible (w/o re-ordering machine functions representing selection rules within the test file) and identified by their much more stable Rule IDs rather than number / position or initial index in the MatchTable. This makes diffs much more manageable for a manual review.
8. Other small improvements and bug fixes.

[rtereshin]

I have:

1. Fixed IR-building code that failed to update def-use chains properly until very end of the test generation, rendering GIM_CheckSameOperands fragile and dependent on which operand was already defined / checked explicitly and which one is not
2. Started sorting machine instructions inserted in topological order explicitly (rather than implicity relying on GIM_RecordInsn's opcodes), thus a) reducing the size of the diffs in case of changes b) making GIM_CheckSameOperands less fragile (it could have created uses not dominated by defs previously)
3. Stabilized resulting vreg numbers to reduce the diffs in case of changes

[mgrang]

lib/CodeGen/GlobalISel/InstructionSelectorTestgen.cpp

261

Please use llvm::sort instead of std::sort. See https://llvm.org/docs/CodingStandards.html#beware-of-non-deterministic-sorting-order-of-equal-elements.

[rtereshin]

ping

lib/CodeGen/GlobalISel/InstructionSelectorTestgen.cpp

261

Good catch, thanks, will do!

[rtereshin]

Closing as we decided not to pursue this.

include/llvm/CodeGen/GlobalISel/InstructionSelectTestgen.h

+//===-- GlobalISel/InstructionSelectTestgen.cpp -----------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file This file describes the interface of the ModulePass responsible
+/// for auto-generating regression tests for the InstructionSelect pass of
+/// GlobalISel.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECT_TESTGEN_H
+#define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECT_TESTGEN_H
+
+#include "llvm/Pass.h"
+
+namespace llvm {
+class InstructionSelectTestgen : public ModulePass {
+public:
+  static char ID;
+  InstructionSelectTestgen() : ModulePass(ID) {}
+  StringRef getPassName() const override { return "InstructionSelectTestgen"; }
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+  bool runOnModule(Module &M) override;
+};
+} // End namespace llvm.
+
+#endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECT_TESTGEN_H

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
 #define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/CodeGen/GlobalISel/InstructionSelectorTestgen.h"
 #include "llvm/Support/CodeGenCoverage.h"
 #include <bitset>
 #include <cstddef>
 #include <cstdint>
 #include <functional>
 #include <initializer_list>
 #include <vector>
 
enum {
   GIR_AddImplicitUse,
   /// Add an register to the specified instruction
   /// - InsnID - Instruction ID to modify
   /// - RegNum - The register to add
   GIR_AddRegister,
   /// Add a temporary register to the specified instruction
   /// - InsnID - Instruction ID to modify
   /// - TempRegID - The temporary register ID to add
+  /// - TempRegFlags - The register flags to set
   GIR_AddTempRegister,
   /// Add an immediate to the specified instruction
   /// - InsnID - Instruction ID to modify
   /// - Imm - The immediate to add
   GIR_AddImm,
   /// Render complex operands to the specified instruction
   /// - InsnID - Instruction ID to modify
   /// - RendererID - The renderer to call
enum {
   GIR_MakeTempReg,
 
   /// A successful emission
   GIR_Done,
 
   /// Increment the rule coverage counter.
   /// - RuleID - The ID of the rule that was covered.
   GIR_Coverage,
+
+  GIU_NumberOfOpcodes,
 };
 
 enum {
   /// Indicates the end of the variable-length MergeInsnID list in a
   /// GIR_MergeMemOperands opcode.
   GIU_MergeMemOperands_EndOfList = -1,
 };
 
bool executeMatchTable(
       TgtInstructionSelector &ISel, NewMIVector &OutMIs, MatcherState &State,
       const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, CustomRendererFn>
           &ISelInfo,
       const int64_t *MatchTable, const TargetInstrInfo &TII,
       MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
       const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures,
       CodeGenCoverage &CoverageInfo) const;
 
+  virtual const int64_t *getMatchTable() const {
+    llvm_unreachable("Should have been overridden by tablegen if used");
+  }
+
   virtual bool testImmPredicate_I64(unsigned, int64_t) const {
     llvm_unreachable("Subclasses must override this to use tablegen");
   }
   virtual bool testImmPredicate_APInt(unsigned, const APInt &) const {
     llvm_unreachable("Subclasses must override this to use tablegen");
   }
   virtual bool testImmPredicate_APFloat(unsigned, const APFloat &) const {
     llvm_unreachable("Subclasses must override this to use tablegen");
protected:
   /// means that we don't need to worry about G_OR with equivalent semantics.
   bool isBaseWithConstantOffset(const MachineOperand &Root,
                                 const MachineRegisterInfo &MRI) const;
 
   /// Return true if MI can obviously be folded into IntoMI.
   /// MI and IntoMI do not need to be in the same basic blocks, but MI must
   /// preceed IntoMI.
   bool isObviouslySafeToFold(MachineInstr &MI, MachineInstr &IntoMI) const;
+
+public:
+  virtual std::unique_ptr<const InstructionSelectorTestgen> getTestgen() const {
+    llvm_unreachable("Subclasses must use tablegen'erated GlobalISel "
+                     "implementation to auto-generate test cases");
+  }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

case GIM_RecordInsn: {
         DEBUG_WITH_TYPE(TgtInstructionSelector::getName(),
                         dbgs() << CurrentIdx << ": Is a physical register\n");
         if (handleReject() == RejectAndGiveUp)
           return false;
         break;
       }
 
       MachineInstr *NewMI = MRI.getVRegDef(MO.getReg());
+      assert(NewMI && "Expected a vreg definition");
       if ((size_t)NewInsnID < State.MIs.size())
         State.MIs[NewInsnID] = NewMI;
       else {
         assert((size_t)NewInsnID == State.MIs.size() &&
                "Expected to store MIs in order");
         State.MIs.push_back(NewMI);
       }
       DEBUG_WITH_TYPE(TgtInstructionSelector::getName(),

include/llvm/CodeGen/GlobalISel/InstructionSelectorTestgen.h

+//===- llvm/CodeGen/GlobalISel/InstructionSelectorTestgen.h -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file This file declares the API for the instruction selector testgen.
+/// The class is responsible for auto-generating regression tests for the
+/// InstructionSelect pass of GlobalISel on rule by rule basis.
+/// The basic and fully functional implementation is TableGen'erated, the
+/// class is used by the InstructionSelectTestgen pass.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_TESTGEN_H
+#define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_TESTGEN_H
+
+#include "llvm/ADT/StringRef.h"
+#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/Support/CommandLine.h"
+
+namespace {
+class LiveInRA;
+} // end anonymous namespace
+
+namespace llvm {
+
+extern cl::opt<unsigned> TestgenFromRule;
+extern cl::opt<unsigned> TestgenUntilRule;
+extern cl::list<unsigned> TestgenExcludeRules;
+extern cl::list<unsigned> TestgenIncludeOnly;
+extern cl::opt<bool> TestgenSetAllFeatures;
+extern cl::opt<bool> TestgenNoABI;
+
+class InstructionSelectorTestgen {
+public:
+  virtual ~InstructionSelectorTestgen() = default;
+
+  virtual void generateTestCases(Module &M, MachineModuleInfo &MMI) const = 0;
+
+  virtual bool checkFeatures(unsigned FeatureBitsetID) const = 0;
+  virtual LLT getTypeObject(unsigned TypeObjectID) const = 0;
+  virtual const TargetInstrInfo &getTII() const = 0;
+  virtual const TargetRegisterInfo &getTRI() const = 0;
+  virtual const RegisterBankInfo &getRBI() const = 0;
+  virtual const int64_t *getMatchTable() const = 0;
+
+  static MachineIRBuilder createEmptyTestCase(StringRef Name, Module &M,
+                                              MachineModuleInfo &MMI);
+  static void emitReturnIntoTestCase(MachineIRBuilder &MIRBuilder);
+  static Type *deduceIRType(LLT LLTy, LLVMContext &Context);
+
+protected:
+  InstructionSelectorTestgen() = default;
+
+  void generateTestCasesImpl(Module &M, MachineModuleInfo &MMI) const;
+
+private:
+  void generateTestCase(uint64_t CurrentIdx, LiveInRA &RA,
+                        MachineIRBuilder &MIRBuilder) const;
+};
+
+} // end namespace llvm
+
+#endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_TESTGEN_H

include/llvm/InitializePasses.h

 void initializeInferFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializeInlineCostAnalysisPass(PassRegistry&);
 void initializeInstCountPass(PassRegistry&);
 void initializeInstNamerPass(PassRegistry&);
 void initializeInstSimplifierPass(PassRegistry&);
 void initializeInstrProfilingLegacyPassPass(PassRegistry&);
 void initializeInstructionCombiningPassPass(PassRegistry&);
 void initializeInstructionSelectPass(PassRegistry&);
+void initializeInstructionSelectTestgenPass(PassRegistry&);
 void initializeInterleavedAccessPass(PassRegistry&);
 void initializeInternalizeLegacyPassPass(PassRegistry&);
 void initializeIntervalPartitionPass(PassRegistry&);
 void initializeJumpThreadingPass(PassRegistry&);
 void initializeLCSSAVerificationPassPass(PassRegistry&);
 void initializeLCSSAWrapperPassPass(PassRegistry&);
 void initializeLazyBlockFrequencyInfoPassPass(PassRegistry&);
 void initializeLazyBranchProbabilityInfoPassPass(PassRegistry&);

include/llvm/Support/CodeGenCoverage.h

 class LLVMContext;
 class MemoryBuffer;
 
 class CodeGenCoverage {
 protected:
   BitVector RuleCoverage;
 
 public:
+  using covered_iterator = BitVector::const_set_bits_iterator;
+
   CodeGenCoverage();
 
   void setCovered(uint64_t RuleID);
-  bool isCovered(uint64_t RuleID);
+  bool isCovered(uint64_t RuleID) const;
+  iterator_range<covered_iterator> covered() const;
 
   bool parse(MemoryBuffer &Buffer, StringRef BackendName);
   bool emit(StringRef FilePrefix, StringRef BackendName) const;
   void reset();
 };
 } // end namespace llvm
 
 #endif // ifndef LLVM_SUPPORT_CODEGENCOVERAGE_H

lib/CodeGen/GlobalISel/CMakeLists.txt

 add_llvm_library(LLVMGlobalISel
         CallLowering.cpp
         GlobalISel.cpp
         Combiner.cpp
         CombinerHelper.cpp
         IRTranslator.cpp
         InstructionSelect.cpp
         InstructionSelector.cpp
+        InstructionSelectTestgen.cpp
+        InstructionSelectorTestgen.cpp
         LegalityPredicates.cpp
         LegalizeMutations.cpp
         Legalizer.cpp
         LegalizerHelper.cpp
         LegalizerInfo.cpp
         Localizer.cpp
         MachineIRBuilder.cpp
         RegBankSelect.cpp
         RegisterBank.cpp
         RegisterBankInfo.cpp
         Utils.cpp
 
         DEPENDS
         intrinsics_gen
   )

lib/CodeGen/GlobalISel/GlobalISel.cpp

 using namespace llvm;
 
 void llvm::initializeGlobalISel(PassRegistry &Registry) {
   initializeIRTranslatorPass(Registry);
   initializeLegalizerPass(Registry);
   initializeLocalizerPass(Registry);
   initializeRegBankSelectPass(Registry);
   initializeInstructionSelectPass(Registry);
+  initializeInstructionSelectTestgenPass(Registry);
 }

lib/CodeGen/GlobalISel/InstructionSelect.cpp

if (MF.size() != NumBlocks) {
     R << "inserting blocks is not supported yet";
     reportGISelFailure(MF, TPC, MORE, R);
     return false;
   }
 
   auto &TLI = *MF.getSubtarget().getTargetLowering();
   TLI.finalizeLowering(MF);
 
+  DEBUG({
+    dbgs() << "Rules covered by selecting function: " << MF.getName() << ":";
+    for (auto RuleID : CoverageInfo.covered())
+      dbgs() << " id" << RuleID;
+    dbgs() << "\n\n";
+  });
   CoverageInfo.emit(CoveragePrefix,
                     MF.getSubtarget()
                         .getTargetLowering()
                         ->getTargetMachine()
                         .getTarget()
                         .getBackendName());
 
   // If we successfully selected the function nothing is going to use the vreg
   // types after us (otherwise MIRPrinter would need them). Make sure the types
   // disappear.
   MRI.getVRegToType().clear();
 
   // FIXME: Should we accurately track changes?
   return true;
 }

lib/CodeGen/GlobalISel/InstructionSelectTestgen.cpp

+//===- llvm/CodeGen/GlobalISel/InstructionSelectTestgen.cpp ---------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This file implements the InstructionSelectTestgen class.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GlobalISel/InstructionSelectTestgen.h"
+#include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
+#include "llvm/IR/Verifier.h"
+
+#define DEBUG_TYPE "instruction-select-testgen"
+
+using namespace llvm;
+
+char InstructionSelectTestgen::ID = 0;
+INITIALIZE_PASS(InstructionSelectTestgen, DEBUG_TYPE,
+                "Generate instruction selection test cases", false, false)
+
+void InstructionSelectTestgen::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<MachineModuleInfo>();
+}
+
+static const MachineFunction &createReturnOnlyTestCase(Module &M,
+                                                       MachineModuleInfo &MMI) {
+  MachineIRBuilder MIRBuilder =
+      InstructionSelectorTestgen::createEmptyTestCase("test_return", M, MMI);
+  InstructionSelectorTestgen::emitReturnIntoTestCase(MIRBuilder);
+  MachineFunction &MF = MIRBuilder.getMF();
+  MF.getProperties().set(MachineFunctionProperties::Property::Legalized);
+  MF.getProperties().set(MachineFunctionProperties::Property::RegBankSelected);
+  return MF;
+}
+
+bool InstructionSelectTestgen::runOnModule(Module &M) {
+  assert(!verifyModule(M, &dbgs()) && "Input module is not valid");
+
+  MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
+
+  for (const Function &F : M.functions())
+    if (const MachineFunction *MF = MMI.getMachineFunction(F))
+      MF->verify(this, "Pre-existing function", /*AbortOnErrors*/ true);
+
+  const MachineFunction &MF = createReturnOnlyTestCase(M, MMI);
+  MF.verify(this, "Return only test function", /*AbortOnErrors*/ true);
+
+  const InstructionSelector *ISel = MF.getSubtarget().getInstructionSelector();
+  assert(ISel && "Can not work without InstructionSelector");
+
+  std::unique_ptr<const InstructionSelectorTestgen> Testgen =
+      ISel->getTestgen();
+  assert(Testgen && "Can not work without InstructionSelectorTestgen");
+  Testgen->generateTestCases(M, MMI);
+
+  for (const Function &F : M.functions())
+    if (const MachineFunction *MF = MMI.getMachineFunction(F))
+      MF->verify(this, "Output machine function", /*AbortOnErrors*/ true);
+
+  assert(!verifyModule(M, &dbgs()) && "Output module is not valid");
+  return true;
+}

lib/CodeGen/GlobalISel/InstructionSelectorTestgen.cpp

+//===- llvm/CodeGen/GlobalISel/InstructionSelectorTestgen.cpp -------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file
+/// This file implements the InstructionSelectorTestgen class.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
+#include "llvm/CodeGen/GlobalISel/RegisterBankInfo.h"
+#include "llvm/IR/Verifier.h"
+
+#define DEBUG_TYPE "instructionselector-testgen"
+
+using namespace llvm;
+
+cl::opt<unsigned> llvm::TestgenFromRule(
+    "testgen-from-rule",
+    cl::desc("Generate test cases for instruction selector rules from the one "
+             "specified (by index, inclusive)"),
+    cl::init(std::numeric_limits<unsigned>::min()), cl::Hidden);
+
+cl::opt<unsigned> llvm::TestgenUntilRule(
+    "testgen-until-rule",
+    cl::desc("Generate test cases for instruction selector rules until the one "
+             "specified (by index, inclusive)"),
+    cl::init(std::numeric_limits<unsigned>::max()), cl::Hidden);
+
+cl::list<unsigned> llvm::TestgenExcludeRules(
+    "testgen-exclude-rules",
+    cl::desc("Don't try to generate test cases for the instruction selector "
+             "rules listed (by index)"),
+    cl::CommaSeparated, cl::Hidden);
+
+cl::list<unsigned> llvm::TestgenIncludeOnly(
+    "testgen-include-only",
+    cl::desc("Don't try to generate test cases for any instruction selector "
+             "rules but the ones listed (by index, every other testgen- option "
+             "is ignored)"),
+    cl::CommaSeparated, cl::Hidden);
+
+cl::opt<bool> llvm::TestgenSetAllFeatures(
+    "testgen-set-all-features",
+    cl::desc("Force all target features to be available"), cl::Hidden);
+
+cl::opt<bool>
+    llvm::TestgenNoABI("testgen-no-abi",
+                       cl::desc("Don't try to imitate proper ABI boundaries"),
+                       cl::Hidden);
+
+MachineIRBuilder
+InstructionSelectorTestgen::createEmptyTestCase(StringRef Name, Module &M,
+                                                MachineModuleInfo &MMI) {
+  LLVMContext &Context = M.getContext();
+
+  Function &F = *cast<Function>(M.getOrInsertFunction(
+      Name, FunctionType::get(Type::getVoidTy(Context), false)));
+  BasicBlock *BB = BasicBlock::Create(Context, "entry", &F);
+  new UnreachableInst(Context, BB);
+  assert(!verifyFunction(F, &dbgs()) && "Empty test IR is broken");
+
+  MachineFunction &MF = MMI.getOrCreateMachineFunction(F);
+  MachineBasicBlock *MBB = MF.CreateMachineBasicBlock(BB);
+  MF.push_back(MBB);
+  MF.verify(/*Pass*/ nullptr, "Empty test function", /*AbortOnErrors*/ true);
+
+  MachineIRBuilder MIRBuilder(MF);
+  MIRBuilder.setMBB(*MBB);
+  return MIRBuilder;
+}
+
+void InstructionSelectorTestgen::emitReturnIntoTestCase(
+    MachineIRBuilder &MIRBuilder) {
+  MachineBasicBlock &MBB = MIRBuilder.getMBB();
+  unsigned RetVReg = 0;
+  if (!MBB.empty()) {
+    const MachineInstr &RootInstr = MBB.back();
+    if (RootInstr.getNumOperands()) {
+      const MachineOperand &MO = RootInstr.getOperand(0);
+      if (MO.isReg() && MO.isDef())
+        RetVReg = MO.getReg();
+    }
+  }
+  auto &InsnB = MIRBuilder.buildInstr(TargetOpcode::PATCHABLE_RET).addDef(0);
+  if (RetVReg)
+    InsnB.addUse(RetVReg);
+}
+
+Type *InstructionSelectorTestgen::deduceIRType(LLT LLTy, LLVMContext &Context) {
+  assert(LLTy.isValid() && "Didn't expect an invalid LLT as input");
+  if (LLTy.isVector())
+    return VectorType::get(deduceIRType(LLTy.getElementType(), Context),
+                           LLTy.getNumElements());
+  if (LLTy.isPointer())
+    return PointerType::get(Type::getInt32Ty(Context), LLTy.getAddressSpace());
+  return Type::getIntNTy(Context, LLTy.getSizeInBits());
+}
+
+// RegisterBankInfo's getRegBankFromRegClass is only required to be defined on
+// user-defined register classes. It could be unable to map TableGen'erated
+// register classes (instersections, for instance) to their reg banks
+static const RegisterBank *
+getRegBankFromRegClass(const RegisterBankInfo &RBI,
+                       const TargetRegisterClass *RC) {
+  const RegisterBank *Result = nullptr;
+  for (unsigned i = 0; i < RBI.getNumRegBanks(); ++i) {
+    const RegisterBank &RB = RBI.getRegBank(i);
+    if (RB.covers(*RC)) {
+      assert(!Result && "Register banks should not intersect");
+      Result = &RB;
+    }
+  }
+  return Result;
+}
+
+namespace {
+class LiveInRA {
+public:
+  LiveInRA(const TargetRegisterInfo &TRI, const RegisterBankInfo &RBI,
+           const MachineFunction &MF) {
+    // Classes processed first have the largest impact on the resulting order as
+    // we only append non-visited registers. Therefore, it's better to process
+    // the largest classes first:
+    SmallVector<const TargetRegisterClass *, 32> RegClasses(TRI.regclasses());
+    std::stable_sort(
+        RegClasses.begin(), RegClasses.end(),
+        [](const TargetRegisterClass *RC1, const TargetRegisterClass *RC2) {
+          // For the reg classes of the same size, it's better to start with
+          // more concrete ones so we don't overuse weird stuff like register
+          // tuples (see AArch64) and whatnot, so stable sort this way here,
+          // reverse later:
+          return RC1->getNumRegs() < RC2->getNumRegs();
+        });
+    std::reverse(RegClasses.begin(), RegClasses.end());
+
+    // Every physical register belongs to a unique register bank, but it may
+    // belong to register classes of different sizes. Therefore, "visited"
+    // property needs to be per size:
+    SmallDenseMap<unsigned, BitVector, 16> Size2VisitedPhysRegs;
+    for (const TargetRegisterClass *RC : RegClasses)
+      if (const RegisterBank *RB = getRegBankFromRegClass(RBI, RC)) {
+        const unsigned Size = TRI.getRegSizeInBits(*RC);
+        // RegisterClassInfo::getOrder is not available as the reserved
+        // registers set is not freezed yet:
+        for (MCPhysReg PhysReg : RC->getRawAllocationOrder(MF))
+          if (!setVisited(Size2VisitedPhysRegs[Size], PhysReg))
+            SizeRegBank2Regs[std::make_pair(Size, RB)].first.push_back(PhysReg);
+      }
+    // Initializing TrueSizeRegBank2Regs and Reg2TrueSize
+    SmallVector<SizeRegBank2RegsTy::key_type, 32> Keys;
+    for (const auto &Item : SizeRegBank2Regs)
+      Keys.push_back(Item.first);
+    std::sort(Keys.begin(), Keys.end(), std::greater<decltype(Keys.front())>());
+    BitVector VisitedPhysRegs;
+    for (const auto Key : Keys)
+      for (const MCPhysReg PhysReg : SizeRegBank2Regs[Key].first)
+        if (!setVisited(VisitedPhysRegs, PhysReg)) {
+          Reg2TrueSize[PhysReg] = Key.first;
+          TrueSizeRegBank2Regs[Key].first.push_back(PhysReg);
+        }
+  }
+
+  // Returns an inferred actual size of the physical register: true size.
+  // As a physical register can belong to multiple register classes
+  // with different register sizes (in bits), the actual size of the
+  // register could only be guessed as the maximum of all sizes:
+  unsigned getTrueRegSize(MCPhysReg PhysReg) const {
+    return Reg2TrueSize.find(PhysReg)->second;
+  }
+
+  bool hasNext(unsigned SizeInBits, const RegisterBank &RB,
+               bool ByTrueSize = false) const {
+    const auto &Map = ByTrueSize ? TrueSizeRegBank2Regs : SizeRegBank2Regs;
+    return Map.count(std::make_pair(SizeInBits, &RB));
+  }
+
+  MCPhysReg next(unsigned SizeInBits, const RegisterBank &RB,
+                 bool ByTrueSize = false) {
+    assert(hasNext(SizeInBits, RB, ByTrueSize) && "Didn't find an allocatable "
+                                                  "physical register for the "
+                                                  "register bank and size");
+    auto &Map = ByTrueSize ? TrueSizeRegBank2Regs : SizeRegBank2Regs;
+    auto &Pool = Map[std::make_pair(SizeInBits, &RB)];
+    MCPhysReg AllocatedPhysReg = Pool.first[Pool.second];
+    Pool.second = (Pool.second + 1) % Pool.first.size();
+    return AllocatedPhysReg;
+  }
+
+  LiveInRA &reset() {
+    for (auto &Item : SizeRegBank2Regs)
+      Item.second.second = 0;
+    for (auto &Item : TrueSizeRegBank2Regs)
+      Item.second.second = 0;
+    return *this;
+  }
+
+  using Size2RegBanksTy =
+      DenseMap<unsigned, SmallPtrSet<const RegisterBank *, 2>>;
+
+  const Size2RegBanksTy &getSize2RegBanks() const {
+    if (Size2RegBanks.empty())
+      for (const auto &Item : SizeRegBank2Regs)
+        Size2RegBanks[Item.first.first].insert(Item.first.second);
+    return Size2RegBanks;
+  }
+
+  void dump(const TargetRegisterInfo &TRI) const {
+    for (const auto &Item : SizeRegBank2Regs) {
+      dbgs() << "Phys regs of size " << Item.first.first
+             << " bits from reg bank " << Item.first.second->getName() << ":";
+      for (const MCPhysReg PhysReg : Item.second.first)
+        dbgs() << " " << TRI.getRegAsmName(PhysReg);
+      dbgs() << "\n";
+    }
+  }
+
+private:
+  using SizeRegBank2RegsTy =
+      DenseMap<std::pair<unsigned, const RegisterBank *>,
+               std::pair<SmallVector<MCPhysReg, 32>, unsigned>>;
+
+  // All the physical registers available per bank and size in the preferred
+  // allocation order with an "allocated so far" index attached:
+  SizeRegBank2RegsTy SizeRegBank2Regs;
+
+  // getTrueRegSize's cache
+  DenseMap<MCPhysReg, unsigned> Reg2TrueSize;
+
+  // All the physical registers available per bank and true size in the
+  // preferred allocation order with an "allocated so far" index attached:
+  SizeRegBank2RegsTy TrueSizeRegBank2Regs;
+
+  // getSize2RegBanks' cache
+  mutable Size2RegBanksTy Size2RegBanks;
+
+  static bool setVisited(BitVector &VisitedPhysRegs, MCPhysReg PhysReg) {
+    if (PhysReg >= VisitedPhysRegs.size())
+      VisitedPhysRegs.resize(PhysReg + 1);
+    if (!VisitedPhysRegs[PhysReg]) {
+      VisitedPhysRegs[PhysReg] = true;
+      return false;
+    }
+    return true;
+  }
+};
+} // end anonymous namespace
+
+static void
+selectUnconstrainedRegBanks(const LiveInRA::Size2RegBanksTy &Size2RegBanks,
+                            MachineFunction &MF) {
+  MachineRegisterInfo &MRI = MF.getRegInfo();
+  SmallDenseMap<const RegisterBank *, unsigned, 4> Hist;
+  for (unsigned i = 0; i < MRI.getNumVirtRegs(); ++i) {
+    const unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
+    // Overall in & out vregs of the entire instruction sequence affect the
+    // selection, the internal vregs and their reg banks don't usually matter,
+    // but if the selector went into trouble of checking them, they probably do
+    // so better take them into account as well as the external ones:
+    if (!MRI.def_empty(Reg) || !MRI.use_empty(Reg))
+      // See in which bank the instruction sequence mostly lies in:
+      ++Hist[MRI.getRegBankOrNull(Reg)];
+  }
+  SmallVector<unsigned, 6> Sizes;
+  for (const auto &item : Size2RegBanks)
+    Sizes.push_back(item.first);
+  std::sort(Sizes.begin(), Sizes.end());
+  auto selectRegBank = [&MF, &Sizes, &Size2RegBanks, &Hist](unsigned Reg) {
+    MachineRegisterInfo &MRI = MF.getRegInfo();
+    if (MRI.getRegBankOrNull(Reg))
+      return;
+    const LLT LLTy = MRI.getType(Reg);
+    unsigned Size = LLTy.getSizeInBits();
+    const auto SizeI = std::lower_bound(Sizes.begin(), Sizes.end(), Size);
+    if (SizeI == Sizes.end()) {
+      dbgs() << "- Didn't find a register bank containing allocatable\n"
+                "  registers of the required by LLT " << LLTy << " size of\n"
+                "  " << Size << " bits or larger for an unconstrained vreg %"
+             << TargetRegisterInfo::virtReg2Index(Reg) << "\n";
+      // This test will definitely fail during the actual select due to
+      // register banks not being fully defined yet, but we don't want to
+      // create too much noise on targets early in GlobalISel migration:
+      MF.getProperties().set(MachineFunctionProperties::Property::FailedISel);
+      return;
+    }
+    const auto &Banks = Size2RegBanks.find(*SizeI)->second;
+    assert(!Banks.empty() && "Size2RegBanks is broken: contains empty sets");
+    // Out of the banks that have physical registers of an appropriate size
+    // pick the one that is most common already:
+    const RegisterBank *RB = *std::max_element(
+        Banks.begin(), Banks.end(),
+        [&Hist](const RegisterBank *RB1, const RegisterBank *RB2) {
+          // Add the unique ID as a tiebreaker for determinism
+          return std::make_pair(Hist[RB1], RB1->getID()) <
+                 std::make_pair(Hist[RB2], RB2->getID());
+        });
+    assert(RB && "Size2RegBanks is broken: contains null pointers");
+    MRI.setRegBank(Reg, *RB);
+    // As we might have not picked the most common bank at the previous step
+    // out of all banks, but only out of a subset of them, update the stats so
+    // we could greadily select the locally best result for the next vreg:
+    ++Hist[RB];
+  };
+  // Process in & out "external" vregs first so our choices on internal ones
+  // don't affect our choices on the external ones:
+  for (unsigned i = 0; i < MRI.getNumVirtRegs(); ++i) {
+    const unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
+    if (MRI.def_empty(Reg) ^ MRI.use_empty(Reg))
+      selectRegBank(Reg);
+  }
+  for (unsigned i = 0; i < MRI.getNumVirtRegs(); ++i) {
+    const unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
+    // The internal vregs don't really matter, but we still need to pick
+    // something for them. Technically, out-of-place banks, banks with no
+    // registers big enough or no registers at all are fine here, but just in
+    // case we don't really want to stress selector too much with malicious
+    // input:
+    if (!MRI.def_empty(Reg) && !MRI.use_empty(Reg))
+      selectRegBank(Reg);
+  }
+}
+
+static void defineUndefinedVRegs(const TargetInstrInfo &TII,
+                                 const TargetRegisterInfo &TRI,
+                                 const RegisterBankInfo &RBI, LiveInRA &RA,
+                                 MachineIRBuilder &MIRBuilder) {
+  MachineFunction &MF = MIRBuilder.getMF();
+  MachineRegisterInfo &MRI = MF.getRegInfo();
+  const auto OrigInsertPt = MIRBuilder.getInsertPt();
+  MIRBuilder.setInsertPt(MIRBuilder.getMBB(), MIRBuilder.getMBB().begin());
+  for (unsigned i = 0; i < MRI.getNumVirtRegs(); ++i) {
+    const unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
+    if (MRI.def_empty(Reg) && !MRI.use_empty(Reg)) {
+      LLT LLTy = MRI.getType(Reg);
+      assert(LLTy.isValid() && "Undefined virtual reg doesn't have a type");
+      const RegisterBank *RB = MRI.getRegBankOrNull(Reg);
+      if (!RB) {
+        dbgs() << "- Undefined virtual register %"
+               << TargetRegisterInfo::virtReg2Index(Reg)
+               << " doesn't have a reg bank\n";
+        MIRBuilder.buildInstr(TargetOpcode::IMPLICIT_DEF).addDef(Reg);
+      } else if (!RA.hasNext(LLTy.getSizeInBits(), *RB, true)) {
+        dbgs() << "- Didn't find an allocatable physical register for the\n"
+                  "  register bank " << RB->getName() << " of the required by"
+                  " LLT " << LLTy << "\n  size of " << LLTy.getSizeInBits()
+               << " bits for an undefined virtual register %"
+               << TargetRegisterInfo::virtReg2Index(Reg) << "\n";
+        MIRBuilder.buildInstr(TargetOpcode::IMPLICIT_DEF).addDef(Reg);
+      } else if (TestgenNoABI)
+        MIRBuilder.buildInstr(TargetOpcode::IMPLICIT_DEF).addDef(Reg);
+      else
+        MRI.addLiveIn(RA.next(LLTy.getSizeInBits(), *RB, true), Reg);
+    }
+  }
+  MIRBuilder.setInsertPt(MIRBuilder.getMBB(), OrigInsertPt);
+  MRI.EmitLiveInCopies(&MF.front(), TRI, TII);
+}
+
+static uint64_t nextGIOpcodeIdx(const int64_t *MatchTable,
+                                uint64_t CurrentIdx) {
+  static constexpr unsigned NumberOfOperands[GIU_NumberOfOpcodes] = {
+      1 /*GIM_Try*/,
+      3 /*GIM_RecordInsn*/,
+      1 /*GIM_CheckFeatures*/,
+      2 /*GIM_CheckOpcode*/,
+      2 /*GIM_CheckNumOperands*/,
+      2 /*GIM_CheckI64ImmPredicate*/,
+      2 /*GIM_CheckAPIntImmPredicate*/,
+      2 /*GIM_CheckAPFloatImmPredicate*/,
+      2 /*GIM_CheckAtomicOrdering*/,
+      2 /*GIM_CheckAtomicOrderingOrStronger*/,
+      2 /*GIM_CheckAtomicOrderingWeakerThan*/,
+      3 /*GIM_CheckType*/,
+      3 /*GIM_CheckPointerToAny*/,
+      3 /*GIM_CheckRegBankForClass*/,
+      4 /*GIM_CheckComplexPattern*/,
+      3 /*GIM_CheckConstantInt*/,
+      3 /*GIM_CheckLiteralInt*/,
+      3 /*GIM_CheckIntrinsicID*/,
+      2 /*GIM_CheckIsMBB*/,
+      1 /*GIM_CheckIsSafeToFold*/,
+      4 /*GIM_CheckIsSameOperand*/,
+      0 /*GIM_Reject*/,
+
+      3 /*GIR_MutateOpcode*/,
+      2 /*GIR_BuildMI*/,
+      3 /*GIR_Copy*/,
+      4 /*GIR_CopyOrAddZeroReg*/,
+      4 /*GIR_CopySubReg*/,
+      2 /*GIR_AddImplicitDef*/,
+      2 /*GIR_AddImplicitUse*/,
+      2 /*GIR_AddRegister*/,
+      3 /*GIR_AddTempRegister*/,
+      2 /*GIR_AddImm*/,
+      2 /*GIR_ComplexRenderer*/,
+      3 /*GIR_ComplexSubOperandRenderer*/,
+      3 /*GIR_CustomRenderer*/,
+      2 /*GIR_CopyConstantAsSImm*/,
+      3 /*GIR_ConstrainOperandRC*/,
+      1 /*GIR_ConstrainSelectedInstOperands*/,
+      3 /*GIR_MergeMemOperands*/,
+      1 /*GIR_EraseFromParent*/,
+      2 /*GIR_MakeTempReg*/,
+      0 /*GIR_Done*/,
+      1 /*GIR_Coverage*/,
+  };
+  if (MatchTable[CurrentIdx] == GIR_MergeMemOperands)
+    do {
+      ++CurrentIdx;
+    } while (MatchTable[CurrentIdx] != GIU_MergeMemOperands_EndOfList);
+  else
+    CurrentIdx += NumberOfOperands[MatchTable[CurrentIdx]];
+  return CurrentIdx + 1;
+}
+
+static MachineInstrBuilder &ensureNumOperands(MachineInstrBuilder &InsnB,
+                                              int64_t NumOperands,
+                                              int64_t NumDefs = -1) {
+  if (NumDefs == -1)
+    NumDefs = InsnB->getDesc().NumDefs;
+
+  while (InsnB->getNumOperands() < NumOperands)
+    if (InsnB->getNumOperands() < NumDefs)
+      InsnB.addDef(0);
+    else
+      InsnB.addReg(0);
+
+  for (int I = 0; I < NumDefs; ++I)
+    InsnB->getOperand(I).setIsDef();
+
+  return InsnB;
+}
+
+static void setType(MachineInstrBuilder &InsnB, unsigned OpIdx,
+                    LLT ExpectedType, MachineRegisterInfo &MRI) {
+  SmallVector<unsigned, 3> OpIdxs{OpIdx};
+  const MCInstrDesc &MCID = InsnB->getDesc();
+  if (OpIdx < MCID.getNumOperands() && MCID.OpInfo[OpIdx].isGenericType()) {
+    const unsigned TypeIdx = MCID.OpInfo[OpIdx].getGenericTypeIndex();
+    for (unsigned I = 0;
+         I < std::min(MCID.getNumOperands(), InsnB->getNumOperands()); ++I) {
+      if (I == OpIdx || !MCID.OpInfo[I].isGenericType())
+        continue;
+      if (MCID.OpInfo[I].getGenericTypeIndex() == TypeIdx)
+        OpIdxs.push_back(I);
+    }
+  }
+  ensureNumOperands(InsnB, *std::max_element(OpIdxs.begin(), OpIdxs.end()) + 1);
+  for (auto Idx : OpIdxs) {
+    MachineOperand &MO = InsnB->getOperand(Idx);
+    if (!MO.getReg())
+      MO.setReg(MRI.createGenericVirtualRegister(ExpectedType));
+    else
+      MRI.setType(MO.getReg(), ExpectedType);
+  }
+}
+
+static MachineInstrBuilder &
+setOperand(MachineInstrBuilder &InsnB, int64_t OpIdx,
+           std::function<void(MachineInstrBuilder &)> OperandAdder) {
+  ensureNumOperands(InsnB, OpIdx);
+
+  if (InsnB->getNumOperands() == OpIdx)
+    OperandAdder(InsnB);
+  else {
+    SmallVector<MachineOperand, 4> Uses;
+    for (int64_t I = InsnB->getNumOperands() - 1; I > OpIdx; --I) {
+      Uses.push_back(InsnB->getOperand(I));
+      InsnB->RemoveOperand(I);
+    }
+    InsnB->RemoveOperand(OpIdx);
+    OperandAdder(InsnB);
+    while (!Uses.empty())
+      InsnB.add(Uses.pop_back_val());
+  }
+  return InsnB;
+}
+
+static const LLT DummyLLT = LLT::scalar(32);
+// Assuming that all the parts of the MatchTable that don't affect the selection
+// process but only identify a rule, like GIR_Coverage opcodes, come within a
+// rule as a single continuous block, so the meaningful parts of the rule could
+// be represented as some prefix and suffix:
+using RuleBodyTy = std::pair<ArrayRef<int64_t>, ArrayRef<int64_t>>;
+
+static std::tuple<uint64_t, int64_t, RuleBodyTy>
+getDoneIdxRuleIDAndBody(const int64_t *MatchTable, uint64_t CurrentIdx) {
+  const uint64_t BodyIdx = nextGIOpcodeIdx(MatchTable, CurrentIdx);
+  uint64_t CoverageFirst = BodyIdx;
+  uint64_t CoverageLast = CoverageFirst;
+  int64_t FirstRuleID = -1;
+  bool CoverageBlockPassed = false;
+  unsigned NestingLevel = 0;
+  do {
+    switch (MatchTable[CurrentIdx++]) {
+    case GIM_Try: {
+      CurrentIdx++;
+      if (++NestingLevel > 1) {
+#ifdef NDEBUG
+        dbgs()
+            << "Testgen doesn't support non-linear or optimized Match Tables\n";
+        exit(1);
+#endif
+        assert(NestingLevel == 1 &&
+               "Testgen doesn't support non-linear or optimized Match Tables");
+      }
+      break;
+    }
+    case GIR_Coverage: {
+      int64_t RuleID = MatchTable[CurrentIdx++];
+      assert(RuleID >= 0 && "Expected a non-negative RuleID");
+      if (FirstRuleID < 0) {
+        FirstRuleID = RuleID;
+        CoverageFirst = CurrentIdx - 2;
+      }
+      CoverageLast = CurrentIdx;
+      if (CoverageBlockPassed)
+        CoverageFirst = CoverageLast;
+      break;
+    }
+    default:
+      CoverageBlockPassed = FirstRuleID >= 0;
+      CurrentIdx = nextGIOpcodeIdx(MatchTable, CurrentIdx - 1);
+    }
+  } while (MatchTable[CurrentIdx] != GIR_Done);
+  assert(BodyIdx <= CoverageFirst &&
+         (CoverageFirst < CoverageLast && FirstRuleID >= 0 ||
+          CoverageFirst == CoverageLast) &&
+         CoverageLast <= CurrentIdx && "Broken Coverage Block");
+  const auto &RuleBody = RuleBodyTy(
+      ArrayRef<int64_t>(&MatchTable[BodyIdx], &MatchTable[CoverageFirst]),
+      ArrayRef<int64_t>(&MatchTable[CoverageLast], &MatchTable[CurrentIdx]));
+  return std::make_tuple(CurrentIdx, FirstRuleID, RuleBody);
+}
+
+static void
+initInsnBuilders(const int64_t *MatchTable, uint64_t CurrentIdx,
+                 MachineIRBuilder &MIRBuilder,
+                 SmallVectorImpl<MachineInstrBuilder> &InsnBuilders) {
+  do {
+    switch (MatchTable[CurrentIdx++]) {
+    case GIM_CheckOpcode: {
+      int64_t InsnID = MatchTable[CurrentIdx++];
+      int64_t Expected = MatchTable[CurrentIdx++];
+      dbgs() << "GIM_CheckOpcode " << InsnID << ", " << Expected << "\n";
+      if (static_cast<uint64_t>(InsnID) >= InsnBuilders.size())
+        InsnBuilders.resize(InsnID + 1);
+      InsnBuilders[InsnID] = MIRBuilder.buildInstrNoInsert(Expected);
+
+      // G_CONSTANT's and G_FCONSTANT's are assumed to be well-formed by the
+      // selector w/o actually checking it.
+      if (Expected == TargetOpcode::G_CONSTANT) {
+        ensureNumOperands(InsnBuilders[InsnID], 2);
+        InsnBuilders[InsnID]->getOperand(1).ChangeToImmediate(1);
+      } else if (Expected == TargetOpcode::G_FCONSTANT) {
+        ensureNumOperands(InsnBuilders[InsnID], 2);
+        InsnBuilders[InsnID]->getOperand(1).ChangeToFPImmediate(ConstantFP::get(
+            MIRBuilder.getMF().getFunction().getContext(), APFloat(0.0)));
+      }
+      break;
+    }
+    default:
+      CurrentIdx = nextGIOpcodeIdx(MatchTable, CurrentIdx - 1);
+    }
+  } while (MatchTable[CurrentIdx] != GIR_Done);
+}
+
+static void mainPass(const InstructionSelectorTestgen &Testgen,
+                     uint64_t CurrentIdx, MachineIRBuilder &MIRBuilder,
+                     SmallVectorImpl<MachineInstrBuilder> &InsnBuilders,
+                     SmallVectorImpl<unsigned> &InsnOrder) {
+  MachineFunction &MF = MIRBuilder.getMF();
+  MachineRegisterInfo &MRI = MF.getRegInfo();
+  const TargetRegisterInfo &TRI = Testgen.getTRI();
+  const RegisterBankInfo &RBI = Testgen.getRBI();
+  const int64_t *MatchTable = Testgen.getMatchTable();
+  InsnOrder.push_back(0);
+  do {
+    switch (MatchTable[CurrentIdx++]) {
+    case GIM_RecordInsn: {
+      int64_t NewInsnID = MatchTable[CurrentIdx++];
+      int64_t InsnID = MatchTable[CurrentIdx++];
+      int64_t OpIdx = MatchTable[CurrentIdx++];
+      dbgs() << "GIM_RecordInsn " << NewInsnID << ", " << InsnID << ", "
+             << OpIdx << "\n";
+      InsnOrder.push_back(NewInsnID);
+      MachineInstrBuilder &NewInsnB = InsnBuilders[NewInsnID];
+      if (NewInsnB->getNumOperands() < 1)
+        NewInsnB.addDef(MRI.createGenericVirtualRegister(DummyLLT));
+      MachineOperand &DefMO = NewInsnB->getOperand(0);
+      if (!DefMO.getReg())
+        DefMO.setReg(MRI.createGenericVirtualRegister(DummyLLT));
+      DefMO.setIsDef();
+      InsnBuilders[InsnID]->getOperand(OpIdx).ChangeToRegister(DefMO.getReg(),
+                                                               /*isDef*/ false);
+      break;
+    }
+    case GIM_CheckNumOperands: {
+      int64_t InsnID = MatchTable[CurrentIdx++];
+      int64_t Expected = MatchTable[CurrentIdx++];
+      dbgs() << "GIM_CheckNumOperands " << InsnID << ", " << Expected << "\n";
+      ensureNumOperands(InsnBuilders[InsnID], Expected);
+      break;
+    }
+    case GIM_CheckIntrinsicID: {
+      int64_t InsnID = MatchTable[CurrentIdx++];
+      int64_t OpIdx = MatchTable[CurrentIdx++];
+      int64_t Value = MatchTable[CurrentIdx++];
+      dbgs() << "GIM_CheckIntrinsicID " << InsnID << ", " << OpIdx << ", "
+             << Value << "\n";
+      auto &InsnB = ensureNumOperands(InsnBuilders[InsnID], OpIdx, OpIdx);
+      setOperand(InsnB, OpIdx, [Value](MachineInstrBuilder &InsnB) {
+        InsnB.addIntrinsicID(static_cast<Intrinsic::ID>(Value));
+      });
+      break;
+    }
+    case GIM_CheckIsMBB: {
+      int64_t InsnID = MatchTable[CurrentIdx++];
+      int64_t OpIdx = MatchTable[CurrentIdx++];
+      dbgs() << "GIM_CheckIsMBB " << InsnID << ", " << OpIdx << "\n";
+      setOperand(
+          InsnBuilders[InsnID], OpIdx,
+          [&MF](MachineInstrBuilder &InsnB) { InsnB.addMBB(&MF.back()); });
+      break;
+    }
+    case GIM_CheckType: {
+      int64_t InsnID = MatchTable[CurrentIdx++];
+      int64_t OpIdx = MatchTable[CurrentIdx++];
+      int64_t TypeID = MatchTable[CurrentIdx++];
+      dbgs() << "GIM_CheckType " << InsnID << ", " << OpIdx << ", " << TypeID
+             << "\n";
+      setType(InsnBuilders[InsnID], OpIdx, Testgen.getTypeObject(TypeID), MRI);
+      break;
+    }
+    case GIM_CheckPointerToAny: {
+      int64_t InsnID = MatchTable[CurrentIdx++];
+      int64_t OpIdx = MatchTable[CurrentIdx++];
+      int64_t SizeInBits = MatchTable[CurrentIdx++];
+      dbgs() << "GIM_CheckPointerToAny " << InsnID << ", " << OpIdx << ", "
+             << SizeInBits << "\n";
+      if (!SizeInBits)
+        SizeInBits = MF.getDataLayout().getPointerSizeInBits(0);
+      setType(InsnBuilders[InsnID], OpIdx, LLT::pointer(0, SizeInBits), MRI);
+      break;
+    }
+    case GIM_CheckRegBankForClass: {
+      int64_t InsnID = MatchTable[CurrentIdx++];
+      int64_t OpIdx = MatchTable[CurrentIdx++];
+      int64_t RCEnum = MatchTable[CurrentIdx++];
+      dbgs() << "GIM_CheckRegBankForClass " << InsnID << ", " << OpIdx << ", "
+             << RCEnum << "\n";
+      const TargetRegisterClass *RC = TRI.getRegClass(RCEnum);
+      const RegisterBank *ExpectedRegBank = getRegBankFromRegClass(RBI, RC);
+      MachineOperand &MO =
+          ensureNumOperands(InsnBuilders[InsnID], OpIdx + 1)->getOperand(OpIdx);
+      if (!MO.getReg())
+        MO.setReg(MRI.createGenericVirtualRegister(DummyLLT));
+      if (ExpectedRegBank)
+        MRI.setRegBank(MO.getReg(), *ExpectedRegBank);
+      else {
+        dbgs() << "- Didn't find a register bank covering class "
+               << TRI.getRegClassName(RC) << " for operand #" << OpIdx
+               << " (" << MO << ")" << " of\n"
+               << "  " << *InsnBuilders[InsnID].getInstr() << "\n";
+        // This test will definitely fail during the actual select due to
+        // register banks not being fully defined yet, but we don't want to
+        // create too much noise on targets early in GlobalISel migration:
+        MF.getProperties().set(MachineFunctionProperties::Property::FailedISel);
+      }
+      break;
+    }
+    case GIM_CheckFeatures: {
+      int64_t ExpectedBitsetID = MatchTable[CurrentIdx++];
+      dbgs() << "GIM_CheckFeatures " << ExpectedBitsetID << "\n";
+      if (!Testgen.checkFeatures(ExpectedBitsetID)) {
+        dbgs() << "! Testgen deficiency: Don't know how to satisfy\n"
+               << "  Module & Function Target Features yet!\n";
+        // This test definitely won't match the rule being tested and might not
+        // even select at all, so mark it to be skipped:
+        MF.getProperties().set(MachineFunctionProperties::Property::FailedISel);
+      }
+      break;
+    }
+    case GIM_CheckConstantInt: {
+      int64_t InsnID = MatchTable[CurrentIdx++];
+      int64_t OpIdx = MatchTable[CurrentIdx++];
+      int64_t Value = MatchTable[CurrentIdx++];
+      dbgs() << "GIM_CheckConstantInt " << InsnID << ", " << OpIdx << ", "
+             << Value << "\n";
+      MachineOperand &MO =
+          ensureNumOperands(InsnBuilders[InsnID], OpIdx + 1)->getOperand(OpIdx);
+      if (MO.isReg() && MO.isUse() && MRI.def_empty(MO.getReg())) {
+        if (!MO.getReg())
+          MO.ChangeToRegister(MRI.createGenericVirtualRegister(DummyLLT),
+                              /*isDef*/ false);
+        InsnOrder.push_back(InsnBuilders.size());
+        InsnBuilders.push_back(
+            MIRBuilder.buildInstrNoInsert(TargetOpcode::G_CONSTANT)
+                .addDef(MO.getReg())
+                .addImm(Value));
+      }
+      break;
+    }
+    case GIM_CheckI64ImmPredicate: {
+      int64_t InsnID = MatchTable[CurrentIdx++];
+      int64_t Predicate = MatchTable[CurrentIdx++];
+      dbgs() << "GIM_CheckI64ImmPredicate " << InsnID << ", " << Predicate
+             << "\n";
+      setOperand(InsnBuilders[InsnID], 1,
+                 [](MachineInstrBuilder &InsnB) { InsnB.addImm(1); });
+      break;
+    }
+    default:
+      CurrentIdx = nextGIOpcodeIdx(MatchTable, CurrentIdx - 1);
+    }
+  } while (MatchTable[CurrentIdx] != GIR_Done);
+}
+
+static void latePass(const int64_t *MatchTable, uint64_t CurrentIdx,
+                     MachineFunction &MF,
+                     SmallVectorImpl<MachineInstrBuilder> &InsnBuilders) {
+  MachineRegisterInfo &MRI = MF.getRegInfo();
+  do {
+    switch (MatchTable[CurrentIdx++]) {
+    case GIM_CheckAtomicOrdering: {
+      int64_t InsnID = MatchTable[CurrentIdx++];
+      int64_t OrderingVal = MatchTable[CurrentIdx++];
+      dbgs() << "GIM_CheckAtomicOrdering " << InsnID << ", " << OrderingVal
+             << "\n";
+      MachineInstrBuilder &InsnB = InsnBuilders[InsnID];
+      auto PtrInfo = MachinePointerInfo::getUnknownStack(MF);
+      auto Flags = (InsnB->mayLoad() ? MachineMemOperand::MOLoad
+                                     : MachineMemOperand::MONone) |
+                   (InsnB->mayStore() ? MachineMemOperand::MOStore
+                                      : MachineMemOperand::MOLoad);
+      LLT LLTy = DummyLLT;
+      for (const MachineOperand &MO : InsnB->operands())
+        if (MO.isReg() && MO.getReg() && MRI.getType(MO.getReg()).isValid()) {
+          LLTy = MRI.getType(MO.getReg());
+          break;
+        }
+      Type *ValTy = InstructionSelectorTestgen::deduceIRType(
+          LLTy, MF.getFunction().getContext());
+      auto Size = MF.getDataLayout().getTypeStoreSize(ValTy);
+      auto Alignment = MF.getDataLayout().getABITypeAlignment(ValTy);
+      auto Ordering = static_cast<AtomicOrdering>(OrderingVal);
+      MachineMemOperand *MMO =
+          MF.getMachineMemOperand(PtrInfo, Flags, Size, Alignment, AAMDNodes(),
+                                  nullptr, SyncScope::System, Ordering);
+      if (InsnB->memoperands_empty())
+        InsnB.addMemOperand(MMO);
+      else
+        *InsnB->memoperands_begin() = MMO;
+      break;
+    }
+    case GIM_CheckIsSameOperand: {
+      int64_t InsnID = MatchTable[CurrentIdx++];
+      int64_t OpIdx = MatchTable[CurrentIdx++];
+      int64_t OtherInsnID = MatchTable[CurrentIdx++];
+      int64_t OtherOpIdx = MatchTable[CurrentIdx++];
+      dbgs() << "GIM_CheckIsSameOperand " << InsnID << ", " << OpIdx << ", "
+             << ", " << OtherInsnID << ", " << OtherOpIdx << "\n";
+      auto &InsnB = ensureNumOperands(InsnBuilders[InsnID], OpIdx + 1);
+      auto &OtherInsnB =
+          ensureNumOperands(InsnBuilders[OtherInsnID], OtherOpIdx + 1);
+      const auto &MO = InsnB->getOperand(OpIdx);
+      const auto &OtherMO = OtherInsnB->getOperand(OtherOpIdx);
+      assert(MO.isReg() && OtherMO.isReg() && "Expected regs as same operands");
+      if (MRI.def_empty(OtherMO.getReg()) && MO.getReg())
+        setOperand(OtherInsnB, OtherOpIdx,
+                   [&MO](MachineInstrBuilder &OtherInsnB) {
+                     OtherInsnB.addReg(MO.getReg());
+                   });
+      else
+        setOperand(InsnB, OpIdx, [&OtherMO](MachineInstrBuilder &InsnB) {
+          InsnB.addReg(OtherMO.getReg());
+        });
+      break;
+    }
+    case GIM_CheckAPIntImmPredicate: {
+      int64_t InsnID = MatchTable[CurrentIdx++];
+      int64_t Predicate = MatchTable[CurrentIdx++];
+      dbgs() << "GIM_CheckAPIntImmPredicate " << InsnID << ", " << Predicate
+             << "\n";
+      setOperand(
+          InsnBuilders[InsnID], 1, [&MF, &MRI](MachineInstrBuilder &InsnB) {
+            const MachineOperand &Def = InsnB->getOperand(0);
+            LLT LLTy = Def.isReg() ? MRI.getType(Def.getReg()) : LLT{};
+            LLTy = LLTy.isValid() ? LLTy : DummyLLT;
+            InsnB.addCImm(ConstantInt::get(MF.getFunction().getContext(),
+                                           APInt(LLTy.getSizeInBits(), 1)));
+          });
+      break;
+    }
+    default:
+      CurrentIdx = nextGIOpcodeIdx(MatchTable, CurrentIdx - 1);
+    }
+  } while (MatchTable[CurrentIdx] != GIR_Done);
+}
+
+static std::string buildName(unsigned RuleNum, uint64_t RuleIdx,
+                             int64_t RuleID = -1) {
+  const auto &ID = RuleID < 0 ? Twine{} : "_id" + Twine(RuleID);
+  return ("test_rule" + Twine(RuleNum) + ID + "_at_idx" + Twine(RuleIdx)).str();
+}
+
+static bool skipRule(unsigned RuleNum, uint64_t CurrentIdx,
+                     int64_t RuleID = -1) {
+  static DenseSet<unsigned> ExplicitlyListedRules;
+  if (ExplicitlyListedRules.empty())
+    for (unsigned Idx : TestgenIncludeOnly)
+      ExplicitlyListedRules.insert(Idx);
+
+  if (!ExplicitlyListedRules.empty())
+    return !ExplicitlyListedRules.count(RuleNum);
+
+  if (RuleNum < TestgenFromRule || RuleNum > TestgenUntilRule)
+    return true;
+
+  static SmallDenseSet<unsigned, 32> ExcludedRules;
+  if (ExcludedRules.empty())
+    for (unsigned Idx : TestgenExcludeRules)
+      ExcludedRules.insert(Idx);
+  return ExcludedRules.count(RuleNum);
+}
+
+void InstructionSelectorTestgen::generateTestCase(
+    uint64_t CurrentIdx, LiveInRA &RA, MachineIRBuilder &MIRBuilder) const {
+
+  SmallVector<MachineInstrBuilder, 1> InsnBuilders;
+  initInsnBuilders(getMatchTable(), CurrentIdx, MIRBuilder, InsnBuilders);
+
+  SmallVector<unsigned, 1> InsnOrder;
+  mainPass(*this, CurrentIdx, MIRBuilder, InsnBuilders, InsnOrder);
+
+  MachineFunction &MF = MIRBuilder.getMF();
+  latePass(getMatchTable(), CurrentIdx, MF, InsnBuilders);
+
+  for (auto I = InsnOrder.rbegin(), E = InsnOrder.rend(); I != E; ++I)
+    MIRBuilder.insertInstr(InsnBuilders[*I]);
+
+  // We need all the banks in place so we could speculate on ABI better:
+  dbgs() << "** Selecting RegBanks for VRegs unconstrained by the rule\n";
+  selectUnconstrainedRegBanks(RA.getSize2RegBanks(), MF);
+  // selectUnconstrainedRegBanks relies on the input vregs being undefined,
+  // so run defineUndefinedVRegs later, not before:
+  dbgs() << "** Defining VRegs undefined by the rule\n";
+  defineUndefinedVRegs(getTII(), getTRI(), getRBI(), RA, MIRBuilder);
+  // finalize the MBB with a non-generic terminator that uses the root vreg:
+  InstructionSelectorTestgen::emitReturnIntoTestCase(MIRBuilder);
+
+  MF.getProperties().set(MachineFunctionProperties::Property::Legalized);
+  MF.getProperties().set(MachineFunctionProperties::Property::RegBankSelected);
+}
+
+void InstructionSelectorTestgen::generateTestCasesImpl(
+    Module &M, MachineModuleInfo &MMI) const {
+
+  const MachineFunction *MF = MMI.getMachineFunction(*M.begin());
+  assert(MF && "Expected the Module / MMI to contain an init Machine Function");
+
+  const int64_t *MatchTable = getMatchTable();
+  unsigned RuleNum = 0;
+  uint64_t CurrentIdx = 0;
+  uint64_t CurrentDoneIdx = ~0ULL;
+  int64_t RuleID = -1;
+  using RuleSig = std::tuple<unsigned, uint64_t, int64_t>;
+  RuleBodyTy RuleBody;
+
+  DenseMap<RuleBodyTy, SmallVector<RuleSig, 1>> RuleDuplicates;
+  LiveInRA RA(getTRI(), getRBI(), *MF);
+
+  while (MatchTable[CurrentIdx] != GIM_Reject) {
+    std::tie(CurrentDoneIdx, RuleID, RuleBody) =
+        getDoneIdxRuleIDAndBody(MatchTable, CurrentIdx);
+
+    if (!skipRule(RuleNum, CurrentIdx, RuleID)) {
+      const auto &Name = buildName(RuleNum, CurrentIdx, RuleID);
+      SmallVectorImpl<RuleSig> &Dups = RuleDuplicates[RuleBody];
+      Dups.emplace_back(RuleNum, CurrentIdx, RuleID);
+
+      if (Dups.size() > 1) {
+        dbgs() << "*** Skipping test case " << Name << " as a duplicate of "
+               << buildName(std::get<0>(Dups.front()),
+                            std::get<1>(Dups.front()),
+                            std::get<2>(Dups.front()))
+               << "\n";
+      } else {
+        dbgs() << "\n*** Generating test case " << Name << " ***\n";
+        MachineIRBuilder MIRBuilder =
+            InstructionSelectorTestgen::createEmptyTestCase(Name, M, MMI);
+        generateTestCase(CurrentIdx, RA.reset(), MIRBuilder);
+        if (!MIRBuilder.getMF().verify(nullptr, Name.c_str(), false)) {
+          Function *F = M.getFunction(Name);
+          MMI.deleteMachineFunctionFor(*F);
+          F->eraseFromParent();
+        }
+      }
+    }
+    ++RuleNum;
+    CurrentIdx = nextGIOpcodeIdx(MatchTable, CurrentDoneIdx);
+  }
+}

lib/Support/CodeGenCoverage.cpp

 CodeGenCoverage::CodeGenCoverage() {}
 
 void CodeGenCoverage::setCovered(uint64_t RuleID) {
   if (RuleCoverage.size() <= RuleID)
     RuleCoverage.resize(RuleID + 1, 0);
   RuleCoverage[RuleID] = true;
 }
 
-bool CodeGenCoverage::isCovered(uint64_t RuleID) {
+bool CodeGenCoverage::isCovered(uint64_t RuleID) const {
   if (RuleCoverage.size() <= RuleID)
     return false;
   return RuleCoverage[RuleID];
 }
 
+iterator_range<CodeGenCoverage::covered_iterator>
+CodeGenCoverage::covered() const {
+  return RuleCoverage.set_bits();
+}
+
 bool CodeGenCoverage::parse(MemoryBuffer &Buffer, StringRef BackendName) {
   const char *CurPtr = Buffer.getBufferStart();
 
   while (CurPtr != Buffer.getBufferEnd()) {
     // Read the backend name from the input.
     const char *LexedBackendName = CurPtr;
     while (*CurPtr++ != 0)
       ;

test/TableGen/GlobalISelEmitter.td

 // CHECK-NEXT:    typedef ComplexRendererFns(MyTargetInstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;
 // CHECK-NEXT:    typedef void(MyTargetInstructionSelector::*CustomRendererFn)(MachineInstrBuilder &, const MachineInstr&) const;
 // CHECK-NEXT:    const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, CustomRendererFn> ISelInfo;
 // CHECK-NEXT:    static MyTargetInstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];
 // CHECK-NEXT:    static MyTargetInstructionSelector::CustomRendererFn CustomRenderers[];
 // CHECK-NEXT:    bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const override;
 // CHECK-NEXT:    bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) const override;
 // CHECK-NEXT:    bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat &Imm) const override;
+// CHECK-NEXT:    const int64_t *getMatchTable() const override;
+// CHECK-NEXT:    std::unique_ptr<const InstructionSelectorTestgen> getTestgen() const override;
+// CHECK-NEXT:    friend class MyTargetInstructionSelectorTestgen;
 // CHECK-NEXT:  #endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL
 
 // CHECK-LABEL: #ifdef GET_GLOBALISEL_TEMPORARIES_INIT
 // CHECK-NEXT:    , State(2),
 // CHECK-NEXT:    ISelInfo({TypeObjects, FeatureBitsets, ComplexPredicateFns, CustomRenderers})
 // CHECK-NEXT:  #endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT
 
 // CHECK-LABEL: enum SubtargetFeatureBits : uint8_t {

 // CHECK-NEXT: MachineFunction &MF = *I.getParent()->getParent();
 // CHECK-NEXT: MachineRegisterInfo &MRI = MF.getRegInfo();
 // CHECK:      AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, &MF);
 // CHECK-NEXT: const PredicateBitset AvailableFeatures = getAvailableFeatures();
 // CHECK-NEXT: NewMIVector OutMIs;
 // CHECK-NEXT: State.MIs.clear();
 // CHECK-NEXT: State.MIs.push_back(&I);
 
+// CHECK:      if (executeMatchTable(*this, OutMIs, State, ISelInfo, getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures, CoverageInfo)) {
+// CHECK-NEXT:   return true;
+// CHECK-NEXT: }
+
 //===- Test a pattern with multiple ComplexPatterns in multiple instrs ----===//
 //
 
-// CHECK-LABEL: MatchTable0[] = {
+// CHECK: const int64_t *
+// CHECK-LABEL: MyTargetInstructionSelector::getMatchTable() const {
+// CHECK:   MatchTable0[] = {
 // 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_RecordInsn, /*DefineMI*/1, /*MI*/0, /*OpIdx*/3, // MIs[1]
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/1, /*Expected*/4,
 // NOOPT-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SELECT,
 // OPT-NEXT:      // No instruction predicates

 // 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, ISelInfo, MatchTable0, TII, MRI, TRI, RBI, AvailableFeatures, CoverageInfo)) {
-// CHECK-NEXT:    return true;
-// CHECK-NEXT:  }
+// CHECK-NEXT:  return MatchTable0;

utils/TableGen/GlobalISelEmitter.cpp

assert((!LabelID_.hasValue() || LabelID != ~0u) &&
            "This value is reserved for non-labels");
   }
 
   void emit(raw_ostream &OS, bool LineBreakNextAfterThis,
             const MatchTable &Table) const;
   unsigned size() const { return NumElements; }
 };
 
+class Matcher;
+
 /// Holds the contents of a generated MatchTable to enable formatting and the
 /// necessary index tracking needed to support GIM_Try.
 class MatchTable {
   /// An unique identifier for the table. The generated table will be named
   /// MatchTable${ID}.
   unsigned ID;
   /// The records that make up the table. Also includes comments describing the
   /// values being emitted and line breaks to format it.
   std::vector<MatchTableRecord> Contents;
   /// The currently defined labels.
   DenseMap<unsigned, unsigned> LabelMap;
   /// Tracks the sum of MatchTableRecord::NumElements as the table is built.
-  unsigned CurrentSize;
-
+  unsigned CurrentSize = 0;
   /// A unique identifier for a MatchTable label.
-  static unsigned CurrentLabelID;
+  unsigned CurrentLabelID = 0;
+  /// Determines if the table should be instrumented for rule coverage tracking.
+  bool IsWithCoverage;
 
 public:
   static MatchTableRecord LineBreak;
   static MatchTableRecord Comment(StringRef Comment) {
     return MatchTableRecord(None, Comment, 0, MatchTableRecord::MTRF_Comment);
   }
   static MatchTableRecord Opcode(StringRef Opcode, int IndentAdjust = 0) {
     unsigned ExtraFlags = 0;
public:
   }
   static MatchTableRecord JumpTarget(unsigned LabelID) {
     return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 1,
                             MatchTableRecord::MTRF_JumpTarget |
                                 MatchTableRecord::MTRF_Comment |
                                 MatchTableRecord::MTRF_CommaFollows);
   }
 
-  MatchTable(unsigned ID) : ID(ID), CurrentSize(0) {}
+  static MatchTable buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage);
+
+  MatchTable(bool WithCoverage, unsigned ID = 0)
+      : ID(ID), IsWithCoverage(WithCoverage) {}
+
+  bool isWithCoverage() const { return IsWithCoverage; }
 
   void push_back(const MatchTableRecord &Value) {
     if (Value.Flags & MatchTableRecord::MTRF_Label)
       defineLabel(Value.LabelID);
     Contents.push_back(Value);
     CurrentSize += Value.size();
   }
 
-  unsigned allocateLabelID() const { return CurrentLabelID++; }
+  unsigned allocateLabelID() { return CurrentLabelID++; }
 
   void defineLabel(unsigned LabelID) {
     LabelMap.insert(std::make_pair(LabelID, CurrentSize));
   }
 
   unsigned getLabelIndex(unsigned LabelID) const {
     const auto I = LabelMap.find(LabelID);
     assert(I != LabelMap.end() && "Use of undeclared label");
for (auto I = Contents.begin(), E = Contents.end(); I != E;
 
       if (I->Flags & MatchTableRecord::MTRF_Outdent)
         Indentation -= 2;
     }
     OS << "};\n";
   }
 };
 
-unsigned MatchTable::CurrentLabelID = 0;
-
 MatchTableRecord MatchTable::LineBreak = {
     None, "" /* Emit String */, 0 /* Elements */,
     MatchTableRecord::MTRF_LineBreakFollows};
 
 void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis,
                             const MatchTable &Table) const {
   bool UseLineComment =
       LineBreakIsNextAfterThis | (Flags & MTRF_LineBreakFollows);

 
 class Matcher {
 public:
   virtual ~Matcher() = default;
   virtual void emit(MatchTable &Table) = 0;
   virtual std::unique_ptr<PredicateMatcher> forgetFirstCondition() = 0;
 };
 
+MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules,
+                                  bool WithCoverage) {
+  MatchTable Table(WithCoverage);
+  for (Matcher *Rule : Rules)
+    Rule->emit(Table);
+
+  return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
+}
+
 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));
   }
for (const auto &InsnID : InsnIDs) {
       //          case it may introduce a memory fault. We currentl handle this
       //          by rejecting all loads.
     }
   }
 
   for (const auto &MA : Actions)
     MA->emitActionOpcodes(Table, *this);
 
-  if (GenerateCoverage)
+  if (Table.isWithCoverage())
     Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID)
           << MatchTable::LineBreak;
 
   Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
         << MatchTable::Label(LabelID);
   ++NumPatternEmitted;
 }
 
private:
   /// # Group1_2
   ///  # predicate A // <-- Check is now shared.
   ///  # R1
   ///   # predicate B
   ///  # R2
   ///   # predicate C
   /// \endverbatim
   std::vector<Matcher *> optimizeRules(
-      const std::vector<Matcher *> &Rules,
+      ArrayRef<Matcher *> Rules,
       std::vector<std::unique_ptr<GroupMatcher>> &StorageGroupMatcher);
+
+  MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize,
+                             bool WithCoverage);
 };
 
 void GlobalISelEmitter::gatherNodeEquivs() {
   assert(NodeEquivs.empty());
   for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
     NodeEquivs[Equiv->getValueAsDef("Node")] = Equiv;
 
   assert(ComplexPatternEquivs.empty());
void GlobalISelEmitter::emitImmPredicates(
   if (!MatchedRecords.empty())
     OS << "  }\n";
   OS << "  llvm_unreachable(\"Unknown predicate\");\n"
      << "  return false;\n"
      << "}\n";
 }
 
 std::vector<Matcher *> GlobalISelEmitter::optimizeRules(
-    const std::vector<Matcher *> &Rules,
+    ArrayRef<Matcher *> 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 (Matcher *Rule : Rules) {
     std::unique_ptr<PredicateMatcher> Predicate = Rule->forgetFirstCondition();
if (!CurrentGroup->conditions_empty()) {
     ++NbGroup;
     OptRules.push_back(CurrentGroup.get());
     StorageGroupMatcher.emplace_back(std::move(CurrentGroup));
   }
   DEBUG(dbgs() << "NbGroup: " << NbGroup << "\n");
   return OptRules;
 }
 
+MatchTable
+GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules,
+                                   bool Optimize, bool WithCoverage) {
+  std::vector<Matcher *> InputRules;
+  for (Matcher &Rule : Rules)
+    InputRules.push_back(&Rule);
+
+  if (!Optimize)
+    return MatchTable::buildTable(InputRules, WithCoverage);
+
+  std::vector<std::unique_ptr<GroupMatcher>> StorageGroupMatcher;
+  std::vector<Matcher *> OptRules =
+      optimizeRules(InputRules, StorageGroupMatcher);
+
+  return MatchTable::buildTable(OptRules, WithCoverage);
+}
+
 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 {
<< "InstructionSelector::*CustomRendererFn)(MachineInstrBuilder &, const "
         "const;\n"
      << "  const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, "
         "CustomRendererFn> "
         "ISelInfo;\n";
   OS << "  static " << Target.getName()
      << "InstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];\n"
      << "  static " << Target.getName()
      << "InstructionSelector::CustomRendererFn CustomRenderers[];\n"
-     << "bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const "
+     << "  bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const "
         "override;\n"
-     << "bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) "
+     << "  bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) "
         "const override;\n"
-     << "bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat "
+     << "  bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat "
         "&Imm) const override;\n"
+     << "  const int64_t *getMatchTable() const override;\n"
+     << "  std::unique_ptr<const InstructionSelectorTestgen> "
+        "getTestgen() const override;\n"
+     << "  friend class " << Target.getName() << "InstructionSelectorTestgen;\n"
      << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
 
   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
      << ", State(" << MaxTemporaries << "),\n"
      << "ISelInfo({TypeObjects, FeatureBitsets, ComplexPredicateFns, "
         "CustomRenderers})\n"
      << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
 
OS << Target.getName() << "InstructionSelector::CustomRendererFn\n"
      << Target.getName() << "InstructionSelector::CustomRenderers[] = {\n"
      << "  nullptr, // GICP_Invalid\n";
   for (const auto &Record : CustomRendererFns)
     OS << "  &" << Target.getName()
        << "InstructionSelector::" << Record->getValueAsString("RendererFn")
        << ", // " << Record->getName() << "\n";
   OS << "};\n\n";
 
-  OS << "bool " << Target.getName()
-     << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage "
-        "&CoverageInfo) const {\n"
-     << "  MachineFunction &MF = *I.getParent()->getParent();\n"
-     << "  MachineRegisterInfo &MRI = MF.getRegInfo();\n"
-     << "  // 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) {
     int ScoreA = RuleMatcherScores[A.getRuleID()];
     int ScoreB = RuleMatcherScores[B.getRuleID()];
     if (ScoreA > ScoreB)
       return true;
     if (ScoreB > ScoreA)
       return false;
     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 *> InputRules;
-  for (Matcher &Rule : Rules)
-    InputRules.push_back(&Rule);
+  OS << "bool " << Target.getName()
+     << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage "
+     << "&CoverageInfo) const {\n"
+     << "  MachineFunction &MF = *I.getParent()->getParent();\n"
+     << "  MachineRegisterInfo &MRI = MF.getRegInfo();\n"
+     << "  // 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"
+     << "  if (executeMatchTable(*this, OutMIs, State, ISelInfo"
+     << ", getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures"
+     << ", CoverageInfo)) {\n"
+     << "    return true;\n"
+     << "  }\n\n"
+     << "  return false;\n"
+     << "}\n\n"
 
-  std::vector<Matcher *> OptRules =
-      OptimizeMatchTable ? optimizeRules(InputRules, StorageGroupMatcher)
-                         : InputRules;
+     << "namespace {\n"
+     << "class " << Target.getName() << "InstructionSelectorTestgen\n"
+     << "    : public llvm::InstructionSelectorTestgen {\n"
+     << "public:\n"
+     << "  " << Target.getName() << "InstructionSelectorTestgen(const "
+     << Target.getName() << "InstructionSelector &ISel)\n"
+     << "      : ISel(ISel) {}\n"
+     << "  void "
+     << "generateTestCases(Module &M, MachineModuleInfo &MMI) const override;\n"
+     << "  bool checkFeatures(unsigned FeatureBitsetID) const override;\n"
+     << "  LLT getTypeObject(unsigned TypeObjectID) const override;\n"
+     << "  const TargetInstrInfo &getTII() const override { return ISel.TII;"
+     << " }\n"
+     << "  const TargetRegisterInfo &getTRI() const override { return ISel.TRI;"
+     << " }\n"
+     << "  const RegisterBankInfo &getRBI() const override { return ISel.RBI;"
+     << " }\n"
+     << "  const int64_t *getMatchTable() const override;\n"
+     << "private:\n"
+     << "  const " << Target.getName() << "InstructionSelector &ISel;\n"
+     << "};\n"
+     << "} // end anonymous namespace\n\n"
+
+     << "std::unique_ptr<const llvm::InstructionSelectorTestgen>\n"
+     << Target.getName() << "InstructionSelector::getTestgen() const {\n"
+     << "  return llvm::make_unique<const " << Target.getName()
+     << "InstructionSelectorTestgen>(*this);\n"
+     << "}\n\n"
+
+     << "void " << Target.getName()
+     << "InstructionSelectorTestgen::generateTestCases(Module &M"
+     << ", MachineModuleInfo &MMI) const {\n"
+     << "  MachineFunction *MF = MMI.getMachineFunction(*M.rbegin());\n"
+     << "  ISel.AvailableFunctionFeatures = "
+     << "ISel.computeAvailableFunctionFeatures(&ISel.STI, MF);\n"
+     << "  generateTestCasesImpl(M, MMI);\n"
+     << "}\n\n"
+
+     << "bool " << Target.getName()
+     << "InstructionSelectorTestgen::checkFeatures(unsigned FeatureBitsetID) "
+     << "const {\n"
+     << "  const PredicateBitset &ExpectedFeatures = "
+     << "ISel.ISelInfo.FeatureBitsets[FeatureBitsetID];\n"
+     << "  const PredicateBitset &AvailableFeatures = "
+     << "ISel.getAvailableFeatures();\n"
+     << "  return (ExpectedFeatures & AvailableFeatures) == ExpectedFeatures;\n"
+     << "}\n\n"
+
+     << "LLT " << Target.getName()
+     << "InstructionSelectorTestgen::getTypeObject(unsigned TypeObjectID) "
+     << "const {\n"
+     << "  return ISel.ISelInfo.TypeObjects[TypeObjectID];\n"
+     << "}\n\n";
 
-  MatchTable Table(0);
-  for (Matcher *Rule : OptRules)
-    Rule->emit(Table);
+  OS << "const int64_t *" << Target.getName()
+     << "InstructionSelectorTestgen::getMatchTable() const {\n";
+  if (OptimizeMatchTable || !GenerateCoverage) {
+    const MatchTable VanillaTable = buildMatchTable(Rules, false, true);
+    VanillaTable.emitDeclaration(OS);
+    OS << "  return ";
+    VanillaTable.emitUse(OS);
+  } else
+    OS << "  return ISel.getMatchTable()";
+  OS << ";\n}\n\n";
 
-  Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
+  const MatchTable Table =
+      buildMatchTable(Rules, OptimizeMatchTable, GenerateCoverage);
+  OS << "const int64_t *" << Target.getName()
+     << "InstructionSelector::getMatchTable() const {\n";
   Table.emitDeclaration(OS);
-  OS << "  if (executeMatchTable(*this, OutMIs, State, ISelInfo, ";
+  OS << "  return ";
   Table.emitUse(OS);
-  OS << ", TII, MRI, TRI, RBI, AvailableFeatures, CoverageInfo)) {\n"
-     << "    return true;\n"
-     << "  }\n\n";
+  OS << ";\n}\n";
 
-  OS << "  return false;\n"
-     << "}\n"
-     << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
+  OS << "#endif // ifdef GET_GLOBALISEL_IMPL\n\n";
 
   OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"
      << "PredicateBitset AvailableModuleFeatures;\n"
      << "mutable PredicateBitset AvailableFunctionFeatures;\n"
      << "PredicateBitset getAvailableFeatures() const {\n"
+     << "  if (TestgenSetAllFeatures)\n"
+     << "    return PredicateBitset().set();\n"
      << "  return AvailableModuleFeatures | AvailableFunctionFeatures;\n"
      << "}\n"
      << "PredicateBitset\n"
      << "computeAvailableModuleFeatures(const " << Target.getName()
      << "Subtarget *Subtarget) const;\n"
      << "PredicateBitset\n"
      << "computeAvailableFunctionFeatures(const " << Target.getName()
      << "Subtarget *Subtarget,\n"

utils/update_instruction_select_testgen_tests.sh

+#!/bin/bash -e
+
+testgend="$1"
+llc="$2"
+triple="$3"
+testgen_extra_args="${@:4}"
+
+if [ -z "$testgend" -o -z "$llc" -o -z "$triple" ]; then
+  echo "usage: $0 <testgen'd file> <llc binary> <target triple> [extra llc args]"
+  exit 1
+fi
+
+selected="${testgend%-testgend.mir}-selected.mir"
+
+testgen_command="$llc -x mir -mtriple $triple -testgen-set-all-features \
+    -run-pass instruction-select-testgen $testgen_extra_args \
+    -verify-machineinstrs -simplify-mir -o -"
+
+text="$(echo | $testgen_command 2> /dev/null | perl -pe 's/\s+$/\n/')"
+
+test0_line_number=$(echo "$text" | grep -n 'name:\s*test_' \
+                                 | head -n 1 | cut -d: -f 1)
+if [ -z "$test0_line_number" ]; then
+  echo "Couldn't generate any tests by running the following testgen command:"
+  echo "echo | $testgen_command"
+  exit 2
+fi
+tests=$(echo "$text" | tail +$((test0_line_number - 1)))
+
+echo "# NOTE: This test has been autogenerated by utils/$(basename $0)" > "$testgend"
+echo "# RUN: llc -mtriple $triple -run-pass instruction-select-testgen \\" >> "$testgend"
+if [ -n "$testgen_extra_args" ]; then
+  echo "# RUN:     $testgen_extra_args \\" >> "$testgend"
+fi
+echo "# RUN:     -testgen-set-all-features -verify-machineinstrs -simplify-mir %s \\" >> "$testgend"
+echo "# RUN:     -o - 2>&1 | FileCheck %s --check-prefix=TESTGEND" >> "$testgend"
+echo "#" >> "$testgend"
+echo "$tests" \
+    | perl -pe 's/(test_rule\d+)(_id\d+)?_at_idx\d+/\1/' \
+    | perl -pe 's/^(name:\s*test_rule\d+)/# TESTGEND-LABEL: \1/' \
+    | perl -pe 's/^([^#\n])/# TESTGEND:       \1/' \
+    | perl -pe 's/^\n$/#\n/' >> "$testgend"
+
+echo "# RUN: llc -mtriple $triple -run-pass instruction-select \\" > "$selected"
+echo "# RUN:     -testgen-set-all-features -disable-gisel-legality-check \\" >> "$selected"
+echo "# RUN:     -verify-machineinstrs -simplify-mir %s -o - 2>&1 \\" >> "$selected"
+echo "# RUN:   | FileCheck %s --check-prefix=SELECTED" >> "$selected"
+echo "#" >> "$selected"
+echo "# Test if this file is in sync with the current state of the selector:" >> "$selected"
+echo "$text" >> "$selected"
+
+$(dirname $0)/update_mir_test_checks.py --llc-binary="$llc" "$selected"
+
+sed -i '' -e "/^# Test if this file is in sync with the current state of the selector:$/ a\\
+    # RUN: cat %s | FileCheck --check-prefix=TESTGEND \\\\\\
+    # RUN:     %S/$(basename $testgend)
+    " "$selected"
+
+sed -i '' -e "1 i\\
+    # NOTE: This test has been autogenerated by utils/$(basename $0)\\
+    #
+    " "$selected"