Page MenuHomePhabricator

[EarlyCSE] avoid crashing when detecting min/max/abs patterns (PR41083)
ClosedPublic

Authored by spatel on Feb 8 2020, 10:57 AM.

Details

Summary

As discussed in PR41083:
https://bugs.llvm.org/show_bug.cgi?id=41083
...we can assert/crash in EarlyCSE using the current hashing scheme and instructions with flags.

ValueTracking's matchSelectPattern() may rely on overflow (nsw, etc) or other flags when detecting patterns such as min/max/abs composed of compare+select. But the value numbering / hashing mechanism used by EarlyCSE intersects those flags to allow more CSE.

Several alternatives to solve this are discussed in the bug report. This patch avoids the issue by doing simple matching of min/max/abs patterns that never requires instruction flags. We give up some CSE power because of that, but that is not expected to result in much actual performance difference because InstCombine will canonicalize these patterns when possible. It even has this comment for abs/nabs:

/// Canonicalize all these variants to 1 pattern.
/// This makes CSE more likely.

I left this code to use ValueTracking's "flavor" enum values, so we don't have to change the callers' code. If we decide to go back to using the ValueTracking call (by changing the hashing algorithm instead), it should be obvious how to replace this chunk.

Diff Detail

Event Timeline

spatel created this revision.Feb 8 2020, 10:57 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 8 2020, 10:57 AM
spatel edited the summary of this revision. (Show Details)Feb 8 2020, 11:02 AM
nikic added a subscriber: nikic.Feb 9 2020, 1:36 AM
samparker added inline comments.Feb 10 2020, 5:05 AM
llvm/test/Transforms/EarlyCSE/commute.ll
344

Probably worth adding a run line to run instcombine before earlycse to test this expectation?

spatel updated this revision to Diff 243548.Feb 10 2020, 6:51 AM
spatel marked 2 inline comments as done.

Patch updated:
Add tests for -O1 to show that the standard pipelines (the combination of -instcombine and -early-cse) can reduce select patterns formed from different basic ops.

llvm/test/Transforms/EarlyCSE/commute.ll
344

Yes, good point. I prefer to make the tests part of "PhaseOrdering" though. That way we can easily test the standard optimization pipelines for each pass manager.

efriedma accepted this revision.Feb 10 2020, 8:11 AM

LGTM. Thanks for looking into this.

This revision is now accepted and ready to land.Feb 10 2020, 8:11 AM
spatel updated this revision to Diff 243650.Feb 10 2020, 12:33 PM

Patch updated:
The phase ordering test results were wrong in the earlier rev - I must have used a stale binary to generate the CHECK lines.
I fixed a bug in instcombine that was hindering the abs/nabs tests with:
rG62ce7e650a5a

There's another bug for min/max, but I don't see a one-liner fix, so I've marked that test with a FIXME note after pushing
the baseline testing with:
rG0ad6e726ec7e

JosephTremoulet accepted this revision.Feb 10 2020, 1:59 PM

LGTM, thanks.

This revision was automatically updated to reflect the committed changes.