This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Simplify boolean Phis with const inputs using CFG
ClosedPublic

Authored by mkazantsev on Jun 8 2020, 4:29 AM.

Details

Summary

This patch adds simplification for pattern:

  if (cond)
  /       \
 ...      ...
  \       /
p = phi [true] [false]
...
br p, succ_1, succ_2

If we can prove that top block's branches dominate respective
inputs of a block that has a Phi with constant inputs, we can
use the branch condition (maybe inverted) instead of Phi.
This will make proofs of implication for further jump threading
more transparent.

Diff Detail

Event Timeline

mkazantsev created this revision.Jun 8 2020, 4:29 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 8 2020, 4:29 AM
mkazantsev edited the summary of this revision. (Show Details)Jun 8 2020, 4:29 AM
mkazantsev updated this revision to Diff 269172.Jun 8 2020, 4:35 AM
mkazantsev updated this revision to Diff 269173.Jun 8 2020, 4:38 AM
mkazantsev updated this revision to Diff 269174.Jun 8 2020, 4:40 AM
mkazantsev updated this revision to Diff 269441.Jun 9 2020, 2:08 AM
mkazantsev updated this revision to Diff 269449.Jun 9 2020, 2:15 AM
mkazantsev updated this revision to Diff 269518.Jun 9 2020, 6:15 AM
mkazantsev planned changes to this revision.Jun 10 2020, 3:44 AM

Found some bugs internally, need to investigate.

mkazantsev requested review of this revision.Jun 10 2020, 10:38 PM

False alarm.

xbolva00 added inline comments.
llvm/test/Transforms/InstCombine/select.ll
512–513

Regressed

llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll
43 ↗(On Diff #269518)

Unwanted

mkazantsev planned changes to this revision.Jun 14 2020, 9:08 PM
mkazantsev marked an inline comment as done.

Some underlying transforms are missing it seems.

llvm/test/Transforms/InstCombine/select.ll
512–513

Because we are missing the respective transform for select. I can implement it first I guess...

mkazantsev marked an inline comment as done.Jun 15 2020, 1:27 AM
mkazantsev added inline comments.
llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll
43 ↗(On Diff #269518)

SimplifyCFG does something stupid here it seems. Not related to InstCombine.

mkazantsev marked an inline comment as done.Jun 15 2020, 2:02 AM
mkazantsev added inline comments.
llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll
43 ↗(On Diff #269518)

Added a test on that:

./test/Transforms/SimplifyCFG/unprofitable-pr.ll

SimplifyCFG bases its choice on block size, and sometimes does something particularly stupid.

nikic added a reviewer: nikic.Jun 15 2020, 2:32 AM
mkazantsev marked an inline comment as done.Jun 15 2020, 3:45 AM
mkazantsev added inline comments.
llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll
43 ↗(On Diff #269518)
mkazantsev edited the summary of this revision. (Show Details)

Fixed underlying bug, limited transform for branch/ret arguments only (yet it might be expanded further).

nikic added a comment.Jun 16 2020, 1:00 PM

Why is this being limited to phis used in ret and br?

Why is this being limited to phis used in ret and br?

There is a problem with selects:

  if (cond)
  /       \
 ...      ...
  \       /
p = phi [true] [false]
s = select p, v1, v2

The way how InstCombine currently works will turn it into

  if (cond)
  /       \
 ...      ...
  \       /
s = select cond, v1, v2

instead of

  if (cond)
  /       \
 ...      ...
  \       /
s = phi [v1] [v2]

This limitation is temporarily, until we know how to fix this (and maybe other similar) cases.

mkazantsev planned changes to this revision.Jun 17 2020, 1:05 AM

Maybe it makes sense to implement transform for select first, and then lift limitation on branches & returns.

@nikic please take a look at https://reviews.llvm.org/D82005. I will repace this one on top of it once it's merged, so we should no longer have problems with selects.

Rebased on top of underlying fixes.

xbolva00 added inline comments.Jul 1 2020, 11:58 PM
llvm/test/Transforms/InstCombine/simple_phi_condition.ll
4

Remove

nikic added a comment.Jul 2 2020, 12:17 PM

Now that the other issues have been fixed, change this back to start at the phi node, rather than return/branch?

mkazantsev planned changes to this revision.Jul 3 2020, 10:28 PM

Err, you're right @nikic. Will do.

Still missing cases found for selects... It's getting not worth it.

At least 2 another transforms for selects are missing that we need to avoid regressions. I'm depreoritizing this as these efforts don't pay off.

mkazantsev marked an inline comment as done.

At last!

This revision was not accepted when it landed; it landed in state Needs Review.Jul 15 2020, 10:12 PM
This revision was automatically updated to reflect the committed changes.

Looks like some clang tests need update too...

One of clang tests shown that we are still missing some case...

mkazantsev added a comment.EditedJul 16 2020, 1:27 AM

SimplifyCFG's attempts to perform PR are outrageously stupid. It re-inserts (worse version of) removed Phi in order to perform threading, but does not actually thread. I'll fix it separately, it's not blocking this one (it inserts phi anyway, just now it's worse).

Follow-up fix for one of clang tests: https://reviews.llvm.org/D83936

kazu added a subscriber: kazu.Aug 10 2020, 11:10 AM

Would you mind if I revert this patch temporarily? This patch makes it easier to trigger bugs like https://bugs.llvm.org/show_bug.cgi?id=46940. Although I don't think this patch itself is the root cause, reverting this patch would allow me to fix the bug above while the compiler is in a more usable state. Thanks!