This is an archive of the discontinued LLVM Phabricator instance.

[TableGen] Store predicates in PatternToMatch as ListInit *. Add string for HwModeFeatures
ClosedPublic

Authored by craig.topper on Apr 16 2021, 4:09 PM.

Details

Summary

This uses to be how predicates were handled prior to HwMode being
added. When the Predicates were converted to a std::vector it
significantly increased the cost of a compare in GenerateVariants.
Since ListInit's are uniquified by tablegen, we can use a simple
pointer comparison to check for identical lists.

In order to store the HwMode, we now add a separate string to
PatternToMatch. This will be appended separately to the predicate
string in getPredicateCheck. A new getPredicateRecords is added
to allow GlobalISel and getPredicateCheck to both get the sorted
list of Records. GlobalISel was ignoring any HwMode predicates
before and still is.

There is one slight change here, ListInits with different predicate
orders aren't sorted so the filtering in GenerateVariants might
fail to detect two isomorphic patterns with different predicate
orders. This doesn't seem to be happening in tree today.

My hope is this will allow us to remove all the BitVector tracking
in GenerateVariants that was making up for predicates beeing
expensive to compare. There's a decent amount of heap allocations
there on large targets like X86, AMDGPU, and RISCV.

Diff Detail

Event Timeline

craig.topper created this revision.Apr 16 2021, 4:09 PM
craig.topper requested review of this revision.Apr 16 2021, 4:10 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 16 2021, 4:10 PM
craig.topper edited the summary of this revision. (Show Details)Apr 16 2021, 4:10 PM

I presume this passes all the TableGen tests.

How else did you test it? Knowing this may help me in the future.

llvm/utils/TableGen/CodeGenDAGPatterns.cpp
1436

No need to mention initial size ", 4" in the function definition, is there?

1477

Any reason you didn't combine the catenations with '+' ?

I presume this passes all the TableGen tests.

How else did you test it? Knowing this may help me in the future.

All output files for all targets are identical before and after this patch.

llvm/utils/TableGen/CodeGenDAGPatterns.cpp
1436

I think it's needed because I'm returning the vector object, not a reference. Maybe I should make the caller pass it by reference.

1477

Concatenating them would produce a temporary std::string that would need a heap allocation. That would then need to be copied into the SmallString. If the total string is small enough the SmallString won't heap allocate. If we copy each piece in separately we avoid heap allocations for temporaries.

Have caller create the SmallVector and pass by reference. This is much more common in the code base.

llvm/utils/TableGen/CodeGenDAGPatterns.cpp
1477

Sounds like there's room for an optimization that looks at the complete sequence of catenations to decide whether there is room in the SmallString. But good to know.

For my future reference: What is the sequence you go through to ensure that no target output files change? Do you just build with the current system, then build with the revision and check that no output file dates changed?

Does the revision title want an "[NFC]"?

Just a minor thing: the description has a typo in PatterntToMatch with an extra 't'.

llvm/utils/TableGen/CodeGenDAGPatterns.h
1080

Just wondering: would StringRef be more appropriate here? Maybe it's not idiomatic to tablegen code.

Return StringRef instead of const std::string &. Fix compilation errors form that.

craig.topper edited the summary of this revision. (Show Details)Apr 19 2021, 11:44 AM
kparzysz added inline comments.Apr 19 2021, 12:12 PM
llvm/utils/TableGen/CodeGenDAGPatterns.cpp
1477

Isn't Twine specifically designed to optimize concatenations?

4363

Is this part removed in your patch? The "default" case could be vacuously true if there are no conditions attached to it, and it could be applied when a more specialized case should be applied instead.
The "default" was originally invented for situations where the specific modes don't cover all possibilities when combined. I guess in practice the "default" ends up being one of the explicitly defined modes, so this "accidental application" may not be happening.

craig.topper added inline comments.Apr 19 2021, 12:24 PM
llvm/utils/TableGen/CodeGenDAGPatterns.cpp
1477

Yes, but Twine is used almost exclusively as an unnamed temporary object that is either passed to a function that takes a Twine argument or it is converted to a string before it goes out of scope. It has no operator+= so you can't incrementally update it.

4363

I removed it because it wasn't doing what the comment said, the DefaultPred vector is only pushed to it's not used otherwise. Since it was incomplete, I didn't know how to update it.

RKSimon added inline comments.Apr 20 2021, 2:54 AM
llvm/utils/TableGen/CodeGenDAGPatterns.cpp
1451

Use llvm::sort ?

Use llvm::sort

kparzysz added inline comments.Apr 20 2021, 9:41 AM
llvm/utils/TableGen/CodeGenDAGPatterns.cpp
4363

Yeah, see the comment below. It's a latent bug, unfortunately.

I added this change on top of the current main branch (i.e. without your changes) and both check-llvm and check-clang passed for all targets. I guess it hasn't caused trouble for the reasons I stated, but it could eventually. Another variant of the intent described above was to make sure that the predicated patterns can be tried in any order without affecting the result.

I'm not sure how you want to proceed. There is always the possibility of changing the initial intent if it doesn't break the current code...

4375

This should be

if (HasDefault) {
  ModeChecks[DefaultMode] = DefaultPred;
  AppendPattern(P, DefaultMode);
}
craig.topper added inline comments.Apr 20 2021, 11:16 AM
llvm/utils/TableGen/CodeGenDAGPatterns.cpp
4375

That ends up not really working. The ModeChecks are cached for all patterns, but the DefaultPred vector lives inside the loop for a particular pattern. The DefaultPred vector only gets populated when a pattern contains a non-default mode that has never been seen by any pattern before due to the ModeChecks.find(M) != ModeChecks.end() in the first mode loop.

So only one or zero patterns end up getting a default check depending on whether the pattern applies in the default mode.

Is the DefaultPred supposed to be the inverse of the modes that apply to a particular pattern, or the inverse of the predicates for all modes? If the latter you can't calculate it inside the pattern loops and would need to calculate it based on the complete list of modes not just which modes apply to a particular pattern.

kparzysz added inline comments.Apr 20 2021, 2:01 PM
llvm/utils/TableGen/CodeGenDAGPatterns.cpp
4375

Sorry, you're right. Here's a second attempt to fix this: https://reviews.llvm.org/D100889. That's not a real review, I just didn't want to clutter this one.

Rebase after the change to have negative predicates for HwMode. Now I'm building the full string when we add HwMode so I can do the negation without additional state.

kparzysz accepted this revision.Apr 28 2021, 11:52 AM
This revision is now accepted and ready to land.Apr 28 2021, 11:52 AM
This revision was landed with ongoing or failed builds.Apr 28 2021, 12:09 PM
This revision was automatically updated to reflect the committed changes.