This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine][CGP] Move swapMayExposeCSEOpportunities() fold
ClosedPublic

Authored by nikic on Jun 9 2023, 7:51 AM.

Details

Summary

InstCombine tries to swap compare operands to match sub instructions in order to expose "CSE opportunities". However, it doesn't really make sense to perform this transform in the middle-end, as we cannot actually CSE the instructions there.

The backend already performs this fold in https://github.com/llvm/llvm-project/blob/18f5446a45da5a61dbfb1b7667d27fb441ac62db/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp#L4236 on the SDAG level, however this only works within a single basic block.

To handle cross-BB cases, we do need to handle this on the IR layer. This patch moves the fold from InstCombine to CGP in the backend, while keeping the same, somewhat dubious, heuristic.

Diff Detail

Event Timeline

nikic created this revision.Jun 9 2023, 7:51 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 9 2023, 7:51 AM
nikic requested review of this revision.Jun 9 2023, 7:51 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 9 2023, 7:51 AM

Looks like this landed all the way back at rG5ab555532b5a - are the cse tests in icmp.ll still relevant?

nikic planned changes to this revision.Jun 9 2023, 2:39 PM

Looks like this landed all the way back at rG5ab555532b5a - are the cse tests in icmp.ll still relevant?

Okay, based on the commit description this is targeted at cross-BB cases, which SDAG doesn't handle. And indeed, something like this survives all the way through the backend: https://llvm.godbolt.org/z/TzT3rEehe I think in that case we can't drop this entirely and should move it from InstCombine into CGP instead.

nikic updated this revision to Diff 531667.Jun 15 2023, 2:49 AM
nikic retitled this revision from [InstCombine] Remove swapMayExposeCSEOpportunities() fold to [InstCombine][CGP] Move swapMayExposeCSEOpportunities() fold.
nikic edited the summary of this revision. (Show Details)

Move the fold to CGP instead of removing it entirely. cmp_sub_different_order shows the desired outcome for cross-BB cmp/sub reuse. All other test changes are noise.

RKSimon accepted this revision.Jun 15 2023, 3:24 AM

LGTM - cheers

llvm/lib/CodeGen/CodeGenPrepare.cpp
1851

I feel like this limiter has a story behind it - but I'm not sure whether we need to do anything about it......

This revision is now accepted and ready to land.Jun 15 2023, 3:24 AM
nikic added inline comments.Jun 15 2023, 3:30 AM
llvm/lib/CodeGen/CodeGenPrepare.cpp
1851

It does: At one point the InstCombine fold tried to inspect the users of a constant like i32 0, with millions of entries. When I fixed that I both added the guard against constants and a limit on the walk, to be doubly sure it doesn't get out of hand...

This revision was landed with ongoing or failed builds.Jun 15 2023, 5:18 AM
This revision was automatically updated to reflect the committed changes.

Hi,

The following starts hanging in CGP with this patch:

llc -march=x86-64 -mcpu=corei7 -o /dev/null stress-11366.ll

The input was generated with

bin/llvm-stress -size 300 -seed 11366

nikic added a comment.Jun 16 2023, 6:51 AM

@uabelho Thanks for the report! Should be fixed by https://github.com/llvm/llvm-project/commit/b7bd3a734c7c08e1a703a4f23e3e854ba94a1bf2.

Guess this didn't happen in InstCombine because this would get folded to a constant.

@uabelho Thanks for the report! Should be fixed by https://github.com/llvm/llvm-project/commit/b7bd3a734c7c08e1a703a4f23e3e854ba94a1bf2.

Guess this didn't happen in InstCombine because this would get folded to a constant.

Yep, thanks!