This is an archive of the discontinued LLVM Phabricator instance.

[RFC][GlobalISel] Overhauled MIR Patterns Support for Combiners
ClosedPublic

Authored by Pierre-vh on Jul 26 2023, 4:49 AM.

Details

Summary

See https://discourse.llvm.org/t/rfc-overhauled-mir-patterns-for-globalisel-combiners/72264

This is a complete overrhaul of the recently-added GlobalISel Match Table backend which adds
support for MIR patterns for both match and apply patterns.

Diff Detail

Event Timeline

Pierre-vh created this revision.Jul 26 2023, 4:49 AM
Pierre-vh requested review of this revision.Jul 26 2023, 4:49 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 26 2023, 4:49 AM
Pierre-vh updated this revision to Diff 544346.Jul 26 2023, 6:50 AM

Improve findRoot + support variadics

Matt added a subscriber: Matt.Jul 26 2023, 10:34 AM

This is much clearer than what was documented before

llvm/docs/GlobalISel/MIRPatterns.rst
88–90

This is unusably broken? You can't produce a valid G_* instruction with a cimm operand

110

maybe mention somewhere that you need to copy.

How are patterns that discard their outputs handled? Does it error on those?

llvm/include/llvm/CodeGen/GlobalISel/GIMatchTableExecutorImpl.h
730–736

Maybe should invest in having a variable length encoded match table. And/or could have a lookup table of known used wide constants

llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/patfrag-errors.td
222

Could this also state what it actually was instead?

llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/pattern-errors.td
5

Lots of diagnostic tests is very good

173

too little/too few

llvm/utils/TableGen/GlobalISelMatchTable.h
1943–1945

Could this be APInt? Should there be a separate APInt renderer?

1962

Typo ConstantINt

arsenm added inline comments.Jul 26 2023, 1:45 PM
llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-variadics.td
29

How would I go about enforcing element types here?

Pierre-vh marked 6 inline comments as done.

Address comments

llvm/docs/GlobalISel/MIRPatterns.rst
88–90

G_CONSTANT uses a CImm, AFAIK
See MachineIRBuilder::buildConstant with addCImm uses.

Do you have example of instructions that need a direct imm? I can test them and fix them.

I'm also wondering if I should just go ahead and make immediates always emit G_CONSTANT except in specific cases (currently only G_CONSTANT I think?). It'd be a usability improvement.

110

How are patterns that discard their outputs handled? Does it error on those?

Good question, I think it will indeed error out.
Do you mean that there's patterns that just delete instructions? I could add a special case for (apply) to just erase the root. Would that work for you?

llvm/include/llvm/CodeGen/GlobalISel/GIMatchTableExecutorImpl.h
730–736

We can do that in the future, yes, but I think it's too much for now. Aren't most constants small anyway? Do we have patterns with constants >64 bits? In the meantime I'll add it to the limitations.
Also note that for a vector splat, this only takes the scalar element size, so if you want to check that a 4 x i64 has a splat value of 0, that works.

llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-variadics.td
29

This is not yet possible, I forgot to add that but it's not much effort (in theory), all of the infrastructure is there :)

I'll add it. To be sure do you mean something like (i32 $x) to add a check for register type?

llvm/utils/TableGen/GlobalISelMatchTable.h
1943–1945

We'd need a separate renderer APInt that can split the APInt into multiple 64-bit pieces & reassemble it after.
Do we even have a usecase for now for >64 bits here? I thought we didn't have any so I didn't think it was an issue.

Pierre-vh updated this revision to Diff 544740.Jul 27 2023, 6:27 AM
Pierre-vh marked an inline comment as done.

Add typed machine operands

I opted for the syntax type:$name which is more consistent I believe.
It seems to work just fine, I even added some inference to avoid repeating types.
It's also smart enough to not reemit a type check everytime that operand is used again. It only emits it once.

arsenm added inline comments.Jul 27 2023, 6:31 AM
llvm/docs/GlobalISel/MIRPatterns.rst
88–90

addImm uses correspond to immarg arguments. Everything else uses G_CONSTANT with a isCImm argument as a materialized constant

110

We have some special case atomic optimizations that discard the result if use_empty, it's currently dealt with in selection but theoretically could be a combine

Pierre-vh added inline comments.Jul 27 2023, 7:10 AM
llvm/docs/GlobalISel/MIRPatterns.rst
88–90

Right, so I can just look at uses of addImm and special-case all of those instructions, then default to inserting a G_CONSTANT for the rest? Does that work?

Should I just special-case them in code, or add some field to GenericInstruction in TableGen and infer it from there?

110

If I understand correctly it'd look like this?

(match (G_ATOMIC_FOO $x, $y), "return MRI.use_empty(${x}.getReg())"))
(apply) // somehow delete it

Then yeah, that's not supported so far. I can add a special case to just delete the root if there are no apply patterns if you think that'd work?

An easy workaround would be to just set $x to IMPLICIT_DEF, but if G_ATOMIC_FOO has no defs then there's no workaround other than using C++ in the (apply).

Pierre-vh updated this revision to Diff 544761.Jul 27 2023, 7:15 AM

Correctly pre-allocate all temporary registers

Awesome to finally see this, thanks for doing this! I checked the documentation and only had two minor nits.

llvm/docs/GlobalISel/MIRPatterns.rst
291
299
Pierre-vh marked 2 inline comments as done.

Fix docs

Pierre-vh updated this revision to Diff 545048.Jul 28 2023, 1:18 AM

Minor changes + fix the name of anonymous patterns. Before it was very cryptic, now it's more structured.
e.g. __MatchFooPerms_alt0_pattern_0 for the first pattern of the first alternative for the PatFrag MatchFooPerms.

arsenm added inline comments.Jul 28 2023, 4:24 AM
llvm/docs/GlobalISel/MIRPatterns.rst
110

Yes the implicit_def thing should be good enough. It's not that important, but would be nice to document

Pierre-vh updated this revision to Diff 545117.EditedJul 28 2023, 5:41 AM
Pierre-vh marked an inline comment as done.
  • Simplify temp reg emission using insertAction
  • Fix immediate handling in apply patterns (check updated docs for the full breakdown).

Something I also want to point out is that some of the things here haven't been tested
in practice (mostly the register type constraints & the immediates handling stuff in apply). I am confident that most things work just fine, but with this level of
complexity it's completely possible there's silly bugs here and there.
I'm anticipating that a lot of small fix patches will need to be made over time as
people start using MIR patterns and notice issues.

Pierre-vh added inline comments.Jul 31 2023, 12:06 AM
llvm/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp
37

I'd like to point this out: Now, matching constants will also match Splats. This is a harmless change for ISel (DAGISel pattern import in GISel) I think because all immediates are typed there, so even if (i32 0) matches a splat for <4 x i32> the typecheck should fail. I didn't notice any test changes doing this so I assume we're good.

If we want to avoid ISel having the same behavior that's possible, I can just create a derived class and only implement this change there for Combiners.

Pierre-vh added inline comments.Jul 31 2023, 12:46 AM
llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp
1871

Note here too, I'm not sure if I should just do everything in terms for permutations.
I special-cased wip_match_opcode for now because it can only ever be the root pattern, but there might be value in making everything follow the same pattern.

Pierre-vh updated this revision to Diff 546068.Aug 1 2023, 8:00 AM

Split up OperandTable + add named_operands() accessor for InstructionPatterns.
There is one TODO in there about using a pair of OperandTables instead of a complicated RuleOperandTable, I plan to look into that as soon as I can but review can continue in the meantime (I can always fix it later if needed anyway, it's not broken - just a code improvement)

arsenm added inline comments.Aug 1 2023, 8:32 AM
llvm/docs/GlobalISel/MIRPatterns.rst
50

Do these support vectors. i.e. can you use a constant and implicitly get a constant splat? vector constants are a recurring pain point

llvm/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp
37

this is a plus?

arsenm added inline comments.Aug 1 2023, 4:34 PM
llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp
1923

don't need this string copy, can directly check and write out the twine

2136

continue on null and reduce indent?

2178

single quotes

2182

single quotes

2188

single quotes

2428

Move the insert before the move?

Pierre-vh updated this revision to Diff 546720.Aug 3 2023, 12:01 AM
Pierre-vh marked 12 inline comments as done.

Comments

Pierre-vh added inline comments.Aug 3 2023, 1:55 AM
llvm/docs/GlobalISel/MIRPatterns.rst
50

The operand's type is checked, so 0 can match a splat, but i32 0 can only match a constant of type i32 (a register).
See match-table-imms.td InstTest0 vs InstTest1

llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp
2428

I still need to return the pointer after so I need to save it anyway, so it doesn't matter if I do SeenPatFrags.insert(NewPatFrag.get());

Pierre-vh updated this revision to Diff 547165.Aug 4 2023, 4:37 AM

Use a singular, simple OperandTable datastructure for both PatFrags & Rules.
Works a lot better and eliminated about 70 lines of code.

aemerson added inline comments.Aug 8 2023, 5:20 PM
llvm/docs/GlobalISel/MIRPatterns.rst
190–193

It doesn't have to be in the initial patch, but can this be addressed later? If we migrate to using MIR patterns more often, this seems wasteful (generating a new inst, observer call, CSE, DCE)

Similar thing for the replacing a register case, it would be good to have a way to trigger a MRI.replaceRegWith().

349

s/in any all/in all

llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp
677–678

can move this above the definition of Def

1985

I'd prefer to not use single letter variable names, Alt and Op are fine for me.

2197

This method could use some documentation either here or in the definition,

3401–3410

Should we use a SmallVector for these?

Pierre-vh updated this revision to Diff 548500.Aug 9 2023, 12:50 AM
Pierre-vh marked 6 inline comments as done.

Comments

llvm/docs/GlobalISel/MIRPatterns.rst
190–193

Sure, I'm leaning towards adding more apply magic operators so we can do things like (apply (erase $d), (replace $z, $x)) but I haven't looked into it yet. I'd do that in a follow up patch.

It's one of the things I want to look at alongside intrinsics matching support (+ migrating some combiner rules of course)

llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp
677–678

No, we always need to create an entry for any operand in the OperandTable. It's how we can differentiate "this is a live-in" from "this doesn't exist". I'll make it clearer

arsenm accepted this revision.Aug 9 2023, 3:04 PM

At this point I think it's easier to just start using it and file bugs for issues I run into

This revision is now accepted and ready to land.Aug 9 2023, 3:04 PM

@aemerson are you also fine with landing it?
(Note: I'll be away next week for about 10 days so earliest I can pick up bugs is after the 23rd/24th - I don't mind waiting until I'm back to land this if preferred)

@aemerson are you also fine with landing it?
(Note: I'll be away next week for about 10 days so earliest I can pick up bugs is after the 23rd/24th - I don't mind waiting until I'm back to land this if preferred)

I’m fine with landing it.

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