Page MenuHomePhabricator

[SimplifyCFG] Update FoldBranchToCommonDest to be poison-safe
ClosedPublic

Authored by aqjune on Jan 20 2021, 12:16 AM.

Details

Summary

This patch makes FoldBranchToCommonDest merge branch conditions into select i1 rather than and/or i1 when it is called by SimplifyCFG.
It is known that merging conditions into and/or is poison-unsafe, and this is towards making things *more* correct by removing possible miscompilations.
Currently, InstCombine simply consumes these selects into and/or of i1 (which is also unsafe), so the visible effect would be very small. The unsafe select -> and/or transformation will be removed in the future.
There has been efforts for updating optimizations to support the select form as well, and they are linked to D93065.

The safe transformation is fired when it is called by SimplifyCFG only. This is done by setting the new PoisonSafe argument as true.
Another place that calls FoldBranchToCommonDest is LoopSimplify. PoisonSafe flag is set to false in this case because enabling it has a nontrivial impact in performance because SCEV is more conservative with select form and InductiveRangeCheckElimination isn't aware of select form of and/or i1.

Diff Detail

Event Timeline

aqjune created this revision.Jan 20 2021, 12:16 AM
aqjune requested review of this revision.Jan 20 2021, 12:16 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 20 2021, 12:16 AM
aqjune added inline comments.Jan 20 2021, 12:22 AM
llvm/lib/Target/BPF/BPFAdjustOpt.cpp
118 ↗(On Diff #317793)

This update was needed to support llvm/test/CodeGen/BPF/adjust-opt-icmp1.ll .

Another place that calls FoldBranchToCommonDest is LoopSimplify. I think this will have a nontrivial impact since SCEV is more conservative in this case.

Enabling PoisonSafe when called by LoopSimplify requires performance evaluation.
For any patches that require experiment, I'd like to write on Feb; right now I don't have enough bandwidth.

Ping
I'd like to leave the select i1 -> and/or folding in InstCombine as a single point where such transformation happens. This patch is a step to it.

lebedev.ri added inline comments.Jan 24 2021, 11:33 PM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
3073–3084

This needs changing, too

aqjune added inline comments.Jan 25 2021, 2:44 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
3073–3084

The created selects are semantically equivalent to and/or - but would it be more correct to count them as having select costs? (I'm not familiar with the instruction cost things)

aqjune added a comment.EditedMar 3 2021, 12:35 AM

Combined with D97756, running LLVM test suite using -O3 emits 20 (among 1978) assembly files differently from the vanilla clang (main branch).
Among 20 diffs, 17 are due to the swapped operand or variable renaming (which causes diffs in comments).
2 are due to EarlyCSE treating select and and/or i1 differently (speculative), 1 due to SimplifyCFG::FoldBranchToCommonDest.
I believe the overall impact is minor ATM, and my upcoming fixes will fix all of these.

Turning on PoisonUnsafe flag for LoopSimplify creates quite a few more unoptimized assemblies, and this should be enabled after further updates.

aqjune updated this revision to Diff 327701.Mar 3 2021, 12:54 AM

clang-format

aqjune edited the summary of this revision. (Show Details)Mar 4 2021, 7:59 AM
nikic accepted this revision.Mar 4 2021, 8:48 AM

Sorry for the delay. This LG with a nit, but please land this only after the loop unswitch change.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2970

Why do we need NewCondV and NewCond? setCondition should accept a Value without the Instruction cast.

This revision is now accepted and ready to land.Mar 4 2021, 8:48 AM
nikic added inline comments.Mar 4 2021, 9:15 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2970

Actually, one more note: What do you think about adding an impliesPoison check here? Otherwise, we may have a phase ordering issue for passes that run between SimplifyCFG and InstCombine, where one creates logical and/or and the other converts to binary. It's not a problem for folds performed by InstCombine itself, but there could be regressions for and/or folds by InstSimplify that can't happen in the meantime. Possibly this could also help LoopSimplify?

aqjune added inline comments.Mar 4 2021, 7:58 PM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2970

This is a great idea!
Cast is not necessary, yes. I'll fix it.

aqjune updated this revision to Diff 328392.Mar 4 2021, 10:46 PM

Use impliesPoison, remove cast

lebedev.ri added inline comments.Mar 4 2021, 10:59 PM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2970

Please add a FIXME: remove once select form is canonical

aqjune added inline comments.Mar 7 2021, 3:18 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2970

Safely folding select into and/or helps SCEV do further analysis: https://reviews.llvm.org/D93065#2472644 I think it might be a good idea to fold select to and/or whenever it is correct.

nikic accepted this revision.Mar 7 2021, 6:51 AM
nikic added inline comments.
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2965

I would write this as bool UseBinOp = !PoisonSafe || impliesPoison(BICond, PBI->getCondition()); rather than a separate if. Or inline the condition entirely.

This revision was landed with ongoing or failed builds.Mar 7 2021, 8:38 AM
This revision was automatically updated to reflect the committed changes.
aqjune marked an inline comment as done.Mar 7 2021, 8:45 AM

Reverted in 8d5a981a135a ; clang seems to miscompile LLVM. Provided some reproduction in the revert commit message.

aqjune added a comment.Mar 7 2021, 4:43 PM

Reverted in 8d5a981a135a ; clang seems to miscompile LLVM. Provided some reproduction in the revert commit message.

Thank you, I'll look into it.

I could reproduce the failures from two-stage build and submitted a bug report: https://bugs.llvm.org/show_bug.cgi?id=49495

Consider this code snippet:

vector<ty> v; // empty
ty* b = v.begin(), *e = v.end()
if (b != e && b < (e - 1))
  // reverse items in [b, e)

After the patch, LLVM was optimizing it into

vector<ty> v; // empty
ty* b = v.begin(), *e = v.end()
if (b < (e - 1))
  // reverse items in [b, e)

But this is wrong. Since v is empty, v.begin() and v.end() can return NULL. e - 1 raises overflow, hence the branch is taken, which is wrong.

PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::insertIntoLoop was containing a code snippet that looked like this.

Hello friends, it seems the reland of this (5c2e50b5d2412f4e1fdb48bce04917e1b6a29cf9) exposed what looks like either a regression or optimization opportunity in clang-13.
https://github.com/llvm/llvm-project/issues/53861
PTAL

Herald added a project: Restricted Project. · View Herald TranscriptMar 24 2022, 2:10 PM