[SimplifyCFG] Update FoldBranchToCommonDest to be poison-safe

[aqjune]

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.

[aqjune]

Fix test

[aqjune]

llvm/lib/Target/BPF/BPFAdjustOpt.cpp

118 ↗

(On Diff #317793)

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

[aqjune]

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.

[aqjune]

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]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

3073–3084

This needs changing, too

[aqjune]

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]

Rebase

[aqjune]

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]

clang-format

[nikic]

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.

[nikic]

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]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2970

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

[aqjune]

Use impliesPoison, remove cast

[lebedev.ri]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2970

Please add a FIXME: remove once select form is canonical

[aqjune]

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]

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.

[mehdi_amini]

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

[aqjune]

In D95026#2610334, @mehdi_amini wrote:

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

Thank you, I'll look into it.

[aqjune]

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.

[nickdesaulniers]

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