This is an archive of the discontinued LLVM Phabricator instance.

[RFC][TableGen][GlobalISel] Add Combiner Match Table Backend
ClosedPublic

Authored by Pierre-vh on Jun 26 2023, 4:55 AM.

Details

Summary

Adds a new backend to power the GISel Combiners using the InstructionSelector's match tables.
This does not depend on any of the data structures created for the current combiner and is intended to replace it entirely.

See the RFC for more details: https://discourse.llvm.org/t/rfc-matchtable-based-globalisel-combiners/71457/6
Note: this would replace D141135.

Diff Detail

Event Timeline

Pierre-vh created this revision.Jun 26 2023, 4:55 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 26 2023, 4:55 AM
Pierre-vh requested review of this revision.Jun 26 2023, 4:55 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 26 2023, 4:55 AM
Pierre-vh edited the summary of this revision. (Show Details)Jun 26 2023, 5:00 AM
Pierre-vh updated this revision to Diff 534888.Jun 27 2023, 2:53 AM
Pierre-vh edited the summary of this revision. (Show Details)

Rebase

Pierre-vh updated this revision to Diff 534946.Jun 27 2023, 6:02 AM

Change include guards to remove redundancy

Merge GICXXPred_Invalid flags

arsenm added inline comments.Jun 30 2023, 12:21 PM
llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table.td
75–78

I'd expect all of this boilerplate to be in member / per function state initialization in the combiner info

arsenm added inline comments.Jun 30 2023, 12:22 PM
llvm/utils/TableGen/GlobalISelMatchTable.cpp
883

Yes, I don't see how this would be avoidable

Pierre-vh marked an inline comment as done.Jul 4 2023, 3:00 AM
Pierre-vh added inline comments.
llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table.td
75–78

MF/MRI maybe (see D153756), the others too?
Note ST is simply to shorten the code a bit, it's just used to fetch InstrInfo/RegBankInfo.

Pierre-vh updated this revision to Diff 537018.Jul 4 2023, 3:00 AM

Comments + rebase

Pierre-vh updated this revision to Diff 537659.Jul 6 2023, 4:11 AM

Some cleanups/tidying the file.

One problem I had with the existing combiner was that it was difficult to understand for someone unfamiliar with it. I think it would be helpful to have some more documentation in some places, for example some of the methods in CombineRuleBuilder. If we can make this code more accessible it will lower the friction for new contributors to make improvements and fixes.

Another useful piece of docs is a comment somewhere describing the ownership semantics. I see unique_ptr allocations and ownership transfers but it's not clear looking at the code why some pointer is being moved. On that topic, just freestyling here: would it be possible to use SpecificBumpPtrAllocator so we can just destroy all the objects at once later and remove the need for keeping track of ownership?

llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp
150

Should this strip leading whitespace?

266

Can bump this to 4 since we often have >2 opcodes to wip_match_opcode

672

Use structured binding to unpack?

675–682

Invert condition to early-exit if !Operand.IsDef

692

ditto

695

ditto

Pierre-vh updated this revision to Diff 538014.Jul 7 2023, 12:37 AM
Pierre-vh marked 6 inline comments as done.

Add more comments, try to improve readability a bit.

One problem I had with the existing combiner was that it was difficult to understand for someone unfamiliar with it. I think it would be helpful to have some more documentation in some places, for example some of the methods in CombineRuleBuilder. If we can make this code more accessible it will lower the friction for new contributors to make improvements and fixes.

Definitely agree, I've tried to add as much docs as I could think of without making it too verbose, please let me know if you think it still needs more.

I also thought about splitting this up in different files to make it more readable but I feel like the logic is so connected everywhere that it'd have the opposite effect - I'd probably end up making things more confusing/verbose by trying to over-split things. Maybe the Patterns hierarchy could go in a separate file but that's about it. It's only 200 or so lines saved.

Another useful piece of docs is a comment somewhere describing the ownership semantics. I see unique_ptr allocations and ownership transfers but it's not clear looking at the code why some pointer is being moved. On that topic, just freestyling here: would it be possible to use SpecificBumpPtrAllocator so we can just destroy all the objects at once later and remove the need for keeping track of ownership?

SpecificBumpPtrAllocator is an interesting idea, if we'd prefer that I can add it. Though in this case ownership semantics are simple: every Pattern is owned by the CombineRuleBuilder's StringMaps, unique_ptr is just used to transfer ownership and keep pointers stable. Once a pattern is moved into one of the maps, it never moves again.
I like it because it's a way to express that a pattern isn't part of the builder yet. I'll make that clearer in the documentation but please let me know if that's not enough, then I can use the SpecificBumpPtrAllocator.

I've also moved some definitions out of line to improve readability.

llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp
150

This object is only created through CXXPattern, which already trims all leading/trailing whitespace in the constructor. I'll document it

672

It's a struct so I'd rather avoid it in this case, it could lead to subtle issues if fields are reordered.

aemerson accepted this revision.Jul 7 2023, 11:15 AM

Thanks. This LGTM. @arsenm ok with you?

This revision is now accepted and ready to land.Jul 7 2023, 11:15 AM
arsenm accepted this revision.Jul 7 2023, 11:57 AM
arsenm added inline comments.
llvm/include/llvm/CodeGen/GlobalISel/GIMatchTableExecutor.h
389

typo, s/instruction/instructions

This revision was landed with ongoing or failed builds.Jul 11 2023, 12:43 AM
This revision was automatically updated to reflect the committed changes.
Pierre-vh marked an inline comment as done.
RKSimon added inline comments.
llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp
1393

@Pierre-vh I'm seeing build warnings due to empty switch statements:

E:\llvm\ninja\lib\Target\Mips\MipsGenPostLegalizeGICombiner.inc(249): warning C4060: switch statement contains no 'case' or 'default' labels

Please can you wrap this in a if (!ApplyCode.empty()) like you did above?

Pierre-vh marked an inline comment as done.Jul 11 2023, 2:53 AM
Pierre-vh added inline comments.
llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp
1393

Sure, apologies for the inconvenience. Will do ASAP.

The test LLVM :: TableGen/GlobalISelCombinerMatchTableEmitter/pattern-parsing.td relies on the iteration order of StringMap, which is not guaranteed. The bug is caught by D155789.

I have fixed one bug 6de2735c2428789f99a26bee66030ddfb0841b9e, but there are more.

curl -L 'https://reviews.llvm.org/D155789?download=1' | patch -p1
cmake ... -DLLVM_ENABLE_REVERSE_ITERATION=on
ninja -C ... check-llvm-tablegen
Pierre-vh marked an inline comment as done.Jul 20 2023, 5:24 AM

The test LLVM :: TableGen/GlobalISelCombinerMatchTableEmitter/pattern-parsing.td relies on the iteration order of StringMap, which is not guaranteed. The bug is caught by D155789.

I have fixed one bug 6de2735c2428789f99a26bee66030ddfb0841b9e, but there are more.

curl -L 'https://reviews.llvm.org/D155789?download=1' | patch -p1
cmake ... -DLLVM_ENABLE_REVERSE_ITERATION=on
ninja -C ... check-llvm-tablegen

D155821