This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Canonicalize SPF to min/max intrinsics
ClosedPublic

Authored by nikic on Mar 7 2021, 1:21 PM.

Details

Summary

Now that min/max intrinsics have good support in both InstCombine and other passes, start canonicalizing SPF min/max to intrinsic min/max.

Once this sticks, we can stop matching SPF min/max in various places, and can remove hacks we have for preventing infinite loops / breaking SPF canonicalization.

Diff Detail

Event Timeline

nikic created this revision.Mar 7 2021, 1:21 PM
nikic requested review of this revision.Mar 7 2021, 1:21 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 7 2021, 1:21 PM
nikic added inline comments.Mar 7 2021, 1:56 PM
llvm/test/Transforms/InstCombine/2007-12-18-AddSelCmpSub.ll
24

Not clear to me whether these are regressions or not. Depends on how much we prefer to have min/max over other select structures.

llvm/test/Transforms/InstCombine/adjust-for-minmax.ll
250

We explicitly fold min/max to work on the narrower type, so I'm counting these as improvements.

llvm/test/Transforms/InstCombine/div-shift.ll
66

Regression

llvm/test/Transforms/InstCombine/max-of-nots.ll
9

Regression

llvm/test/Transforms/InstCombine/max_known_bits.ll
40

Regression (missing nsw flag)

llvm/test/Transforms/InstCombine/min-positive.ll
11

Regression

llvm/test/Transforms/InstCombine/minmax-demandbits.ll
8

Regression

llvm/test/Transforms/InstCombine/minmax-fold.ll
283

Regression

739

Regression

887

This looks neutral.

1103

Regression

1351

Regression

llvm/test/Transforms/InstCombine/sadd_sat.ll
15

Regression

llvm/test/Transforms/InstCombine/sub-minmax.ll
23

Regression

llvm/test/Transforms/PhaseOrdering/X86/vector-reductions-expanded.ll
153

No longer vectorized?

spatel added a subscriber: spatel.Mar 9 2021, 9:47 AM

Thanks for sharing this! I added a couple of 'not' op enhancements to instcombine, so we should be slightly closer now.

llvm/test/Transforms/PhaseOrdering/X86/vector-reductions-expanded.ll
153

This requires rework in SLP. It assumes that min/max patterns are only in cmp+sel form. I made it work for FP (maxnum/minnum) already, so I'll take a look.

nikic added a comment.Mar 9 2021, 10:03 AM

Thanks for sharing this! I added a couple of 'not' op enhancements to instcombine, so we should be slightly closer now.

Thanks! I've updated with new results. It looks like we still need a few more folds for not to reach parity.

llvm/test/Transforms/InstCombine/max-of-nots.ll
9

Fixed

85

Still regresses

111

Still regresses

198

Still regresses -- in this case we'd want to push the not into NOT_VALUE and drop the other two.

356

These all still regress

RKSimon added inline comments.
llvm/test/Transforms/PhaseOrdering/minmax.ll
23

Any ideas whats causing this code bloat?

spatel added inline comments.Mar 15 2021, 7:50 AM
llvm/test/Transforms/PhaseOrdering/minmax.ll
23

We probably need to implement some reassociation folds for the intrinsics like instcombine's factorizeMinMaxTree():
https://github.com/llvm/llvm-project/blob/da55af7f1d348c133774d8e8117d60462363fef5/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp#L2222

D88287 might also help, but NaryReassociate isn't in the default optimization pipeline?

spatel added inline comments.Mar 23 2021, 8:38 AM
llvm/test/Transforms/PhaseOrdering/X86/vector-reductions-expanded.ll
153

SLP and test updated:
3c8473ba534d / 9d45daf4656e
...so this diff should be gone now.

spatel added inline comments.Mar 28 2021, 10:45 AM
llvm/test/Transforms/PhaseOrdering/minmax.ll
23

Should be helped by:
01ae6e5ead64
...but still need to adapt at least 1 more fold and/or analysis to recognize intrinsics.

@nikic What do you think is left to do before taking this forward for general review?

prof metadata support for abs/min/max is still missing.

llvm/test/Transforms/InstCombine/minmax-fold.ll
1117

Regression.

spatel added inline comments.Sep 26 2021, 6:53 AM
llvm/test/Transforms/InstCombine/max-of-nots.ll
356

There's probably still at least one gap in the matching for this kind of larger pattern, but we should get all of the existing tests after:
28afaed691a0a7ca

llvm/test/Transforms/InstCombine/minmax-fold.ll
1117

This should make it better:
6063e6b499c7829b

xbolva00 added inline comments.Sep 26 2021, 7:18 AM
llvm/test/Transforms/InstCombine/select_meta.ll
163–165

Regression.

llvm/test/Transforms/InstCombine/sub-minmax.ll
23

Not done?

106

Regression

Matt added a subscriber: Matt.Oct 2 2021, 6:43 AM

@nikic @spatel Where have we gotten to with this? Is now the time to get it finished in plenty of time for 15.x ?

A local rebase indicates that after rGaca355a3bb99 the most obvious regressions have been squashed

llvm/test/Transforms/InstCombine/select-pr39595.ll
8

We lose pgo data here - I'm not sure whether this is an issue or not - PR39595 had branch weight metadata but it doesn't appear to have been critical to the bug.

@nikic @spatel Where have we gotten to with this? Is now the time to get it finished in plenty of time for 15.x ?

I think we're close. Even if there are some regressions still visible, the benefits should outweigh those? We could file issues for whatever is known left to do based on a rebased patch.

nikic added inline comments.Feb 14 2022, 8:22 AM
llvm/test/Transforms/InstCombine/minmax-fold.ll
283

This looks like a valuable fold.

spatel added inline comments.Feb 14 2022, 8:36 AM
llvm/test/Transforms/InstCombine/minmax-fold.ll
283

Agree - I'll work on that one.
There should be some family of patterns like this:
https://alive2.llvm.org/ce/z/8nsAMp

spatel added inline comments.Feb 14 2022, 8:41 AM
llvm/test/Transforms/InstCombine/minmax-fold.ll
283

On 2nd thought, this is just a reassociation/simplify fold when we have 2 constant operands and matching min/max:
https://alive2.llvm.org/ce/z/wW5HVM

RKSimon added inline comments.Feb 14 2022, 9:00 AM
llvm/test/Transforms/InstCombine/minmax-fold.ll
283

Is a check for constants enough here or do we need full value tracking analysis?

spatel added inline comments.Feb 14 2022, 11:19 AM
llvm/test/Transforms/InstCombine/minmax-fold.ll
283

A general check/fold for constants would already be an improvement over the corresponding fold for select patterns, so I'd start with that alone. I'm not seeing any regression test evidence that we need to try harder so far.

RKSimon added inline comments.Feb 16 2022, 5:05 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
1444

NewAbs -> NewSPF

nikic updated this revision to Diff 409222.Feb 16 2022, 5:50 AM
nikic marked an inline comment as done.

Rebase

nikic added a comment.Feb 23 2022, 2:36 AM

I just went through all the tests again, and these are the remaining regressions I spotted. (There are some differences in canonicalization, but these are the ones where it's clearly worse now.)

llvm/test/Transforms/InstCombine/div-shift.ll
66

This regression still exists.

llvm/test/Transforms/InstCombine/max_known_bits.ll
40

Regression still exists.

78

Regression.

llvm/test/Transforms/InstCombine/sub-minmax.ll
23

Still regresses.

nikic updated this revision to Diff 410811.Feb 23 2022, 6:59 AM
nikic edited the summary of this revision. (Show Details)
nikic added reviewers: spatel, RKSimon, lebedev.ri.

Rebase. The three remaining regressions are fixed now.

spatel accepted this revision.Feb 23 2022, 7:51 AM

Rebase. The three remaining regressions are fixed now.

That was fast! I was going to look at the remaining bits, but too late. :)

Thank you for pushing it forward. LGTM.

For reference, these were at least some of the commits to handle the last round of missing folds:
e2f627e5e385
6777ec9e4df7
5ccb0582c2b1
03e6efb8c23f
587c7ff15c26

This revision is now accepted and ready to land.Feb 23 2022, 7:51 AM
This revision was landed with ongoing or failed builds.Feb 24 2022, 12:09 AM
This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptFeb 24 2022, 12:09 AM
Herald added a subscriber: cfe-commits. · View Herald Transcript
nlopes added a subscriber: nlopes.Feb 25 2022, 2:13 AM

This fixed 9 bugs reports by Alive2:

  • Transforms/InstCombine/max-of-nots.ll
  • Transforms/InstCombine/max_known_bits.ll
  • Transforms/InstCombine/minmax-fold.ll
  • Transforms/InstCombine/saturating-add-sub.ll
  • Transforms/InstCombine/select-pr39595.ll
  • Transforms/InstCombine/select_meta.ll
  • Transforms/InstCombine/sext.ll
  • Transforms/InstCombine/sub.ll
  • Transforms/InstCombine/with_overflow.ll

Thank you!

Herald added a project: Restricted Project. · View Herald TranscriptMay 21 2022, 11:20 PM