Page MenuHomePhabricator

[InstCombine] Simplify boolean Phis with const inputs using CFG
Needs ReviewPublic

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.Sun, Jun 14, 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.Mon, Jun 15, 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.Mon, Jun 15, 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.Mon, Jun 15, 2:32 AM
mkazantsev marked an inline comment as done.Mon, Jun 15, 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.Tue, Jun 16, 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.Wed, Jun 17, 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.Wed, Jul 1, 11:58 PM
llvm/test/Transforms/InstCombine/simple_phi_condition.ll
4

Remove

nikic added a comment.Thu, Jul 2, 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.Fri, Jul 3, 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!