Page MenuHomePhabricator

[InstCombine] Combine select & Phi by same condition
ClosedPublic

Authored by mkazantsev on Thu, Jun 18, 12:45 AM.

Details

Summary

This patch transforms

p = phi [x, y]
s = select cond, z, p

with

s = phi[x, z]

if we can prove that the Phi node takes values basing on select's condition.

Diff Detail

Event Timeline

mkazantsev created this revision.Thu, Jun 18, 12:45 AM
Herald added a project: Restricted Project. · View Herald TranscriptThu, Jun 18, 12:45 AM
xbolva00 added inline comments.Thu, Jun 18, 1:19 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2505

@spatel can you look at this fixme?

spatel added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2505

That was added with D35811.

I don't know exact status, but I think there are still several steps to go before we can start adding freeze instructions to IR early in the optimization pipeline and not cause perf regressions.

cc @aqjune @nlopes

aqjune added inline comments.Thu, Jun 18, 5:58 PM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2505

I'll be able to work on addressing performance regressions happening from freeze insertions from the middle of July.
There are two things that I have in my mind: (1) we need a function attribute saying that the argument has a frozen value (I also suggested it at https://reviews.llvm.org/D81678 ), (2) we need to update InstCombine patterns to work well on frozen arguments too.
For the former one, I'm seeing how the patch goes; if it it goes into a different direction, I'll suggest a patch by myself. For the latter one, my plan is to enable insertion of freeze from the later-most instcombine/simplifycfg pass first, and see which optimization needs to be updated.

nikic added a comment.Sat, Jun 20, 3:12 AM

I'm probably missing something here, but wouldn't it be possible to phi-translate IfTrue and IfFalse (Inputs[Pred] = IfTrue->DoPHITranslation(BB, Pred) etc) and the existing code would already work? Why perform the conversion to a different select first, rather than going directly to the phi? (That should also be more powerful, because it removes the limitation that you need a single value.)

mkazantsev marked an inline comment as done.Mon, Jun 22, 10:42 PM
mkazantsev added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2505

Hi, just to make sure: this discussion has nothing to do with the patch, right? From this thread, I could not figure out if some action is required from me regarding this patch or not.

I'm probably missing something here, but wouldn't it be possible to phi-translate IfTrue and IfFalse (Inputs[Pred] = IfTrue->DoPHITranslation(BB, Pred) etc) and the existing code would already work? Why perform the conversion to a different select first, rather than going directly to the phi? (That should also be more powerful, because it removes the limitation that you need a single value.)

Thanks for pointing that out, I wasn't aware we already have this API. I'll rework the patch using it.

mkazantsev planned changes to this revision.Mon, Jun 22, 10:51 PM
mkazantsev retitled this revision from [InstCombine] Combile select & Phi by same condition to [InstCombine] Combine select & Phi by same condition.
mkazantsev edited the summary of this revision. (Show Details)

Reworked using DoPHITranslation.

This patch looks like a straightforward extension of the existing code, but I don't have a good sense for control-flow corner cases, so please wait for another LGTM.

I think we should have at least one other test that has a switch...something like this:

define i32 @select_phi_same_condition_switch(i1 %cond, i32 %x, i32 %y) {
entry:
  br i1 %cond, label %if.true, label %if.false

if.true:
  switch i32 %x, label %exit [
  i32 1, label %merge
  i32 2, label %merge
  ]

exit:
  ret i32 0

if.false:
  br label %merge

merge:
  %phi = phi i32 [0, %if.true], [0, %if.true], [%y, %if.false]
  %s = select i1 %cond, i32 %x, i32 %phi
  ret i32 %s
}
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2472

It would help to add a code comment and/or example that describes what we are doing in this block.

2505

Correct - these comments don't affect this patch AFAIK.

Two more test cases:

define i32 @test1(i1 %cond, i1 %cond2) {
; CHECK-LABEL: @test1(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
; CHECK:       if.true:
; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[IF_TRUE_1:%.*]], label [[IF_TRUE_2:%.*]]
; CHECK:       if.true.1:
; CHECK-NEXT:    br label [[MERGE:%.*]]
; CHECK:       if.true.2:
; CHECK-NEXT:    br label [[MERGE]]
; CHECK:       if.false:
; CHECK-NEXT:    br label [[MERGE]]
; CHECK:       merge:
; CHECK-NEXT:    [[S:%.*]] = phi i32 [ 3, [[IF_FALSE]] ], [ 2, [[IF_TRUE_2]] ], [ 1, [[IF_TRUE_1]] ]
; CHECK-NEXT:    ret i32 [[S]]
; CHECK:       exit:
; CHECK-NEXT:    ret i32 0
;
entry:
  br i1 %cond, label %if.true, label %if.false

if.true:
  br i1 %cond2, label %if.true.1, label %if.true.2

if.true.1:
  br label %merge

if.true.2:
  br label %merge

if.false:
  br label %merge

merge:
  %p = phi i32 [ 1, %if.true.1 ], [ 2, %if.true.2 ], [ 4, %if.false ]
  %s = select i1 %cond, i32 %p, i32 3
  ret i32 %s

exit:
  ret i32 0
}

This shows that one select operand does not need to have the same incoming values in the phi (a weakness of the previous version of this patch, I believe).

define i32 @test2(i1 %cond, i1 %cond2) {
; CHECK-LABEL: @test2(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[COND:%.*]], label [[LOOP:%.*]], label [[EXIT:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[SELECT:%.*]] = phi i32 [ [[IV_INC:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
; CHECK-NEXT:    [[IV_INC]] = add i32 [[SELECT]], 1
; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP]], label [[EXIT2:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret i32 0
; CHECK:       exit2:
; CHECK-NEXT:    ret i32 [[IV_INC]]
;
entry:
  br i1 %cond, label %loop, label %exit

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
  %select = select i1 %cond, i32 %iv, i32 -1
  %iv.inc = add i32 %select, 1
  br i1 %cond2, label %loop, label %exit2

exit:
  ret i32 0

exit2:
  ret i32 %iv.inc
}

This is a degenerate case where everything is dominated by the true edge, and the select is just equal to the phi.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2486

We should add && Insn != Pred->getTerminator() here to make the @test_invoke_2_neg test case work. What we really want to express is that DT.dominates(Insn, Incoming), but as there is no dominates(Instruction *, BasicBlockEdge) API, this would be the closest replacement. (We could also add that API of course).

nikic accepted this revision.Wed, Jun 24, 12:16 AM

LGTM with test additions.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2486

Actually, let's leave this to a separate patch. We should really do this via a DominatorTree API that can distinguish normal&unwind edges properly.

This revision is now accepted and ready to land.Wed, Jun 24, 12:16 AM
mkazantsev marked an inline comment as done.Wed, Jun 24, 8:01 PM
mkazantsev added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2486

This can be just properlyDominates.

mkazantsev marked an inline comment as done.Wed, Jun 24, 8:02 PM
mkazantsev added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2472

Will add a follow-up NFC comment.

mkazantsev marked an inline comment as done.Wed, Jun 24, 8:24 PM
mkazantsev added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2486

Actually current naming in DomTree is misleading. This method is called dominates, but in fact it is properlyDominates because of this check:

bool DominatorTree::dominates(const Instruction *Def,
                              const Instruction *User) const {
...
  // An instruction doesn't dominate a use in itself.
  if (Def == User)
    return false;

So it's not a dominance check between 2 instructions, but they are also implicitly supposed to be def and user, which is counter-intuitive. I now see what you mean and agree that example with invoke should work. We need to make a global rework of this method to separate proper and usual dominance between instructions.

mkazantsev marked 2 inline comments as done.Wed, Jun 24, 8:43 PM
mkazantsev added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2505

Ok, thanks! Just wanted to make sure. :)

mkazantsev closed this revision.Wed, Jun 24, 8:56 PM
mkazantsev marked an inline comment as done.
commit 1eeb7147878edb7c0c0fbf54bc3dffd43db271b8
Author: Max Kazantsev <mkazantsev@azul.com>
Date:   Thu Jun 25 10:42:16 2020 +0700

    [InstCombine] Combine select & Phi by same condition

    This patch transforms
p = phi [x, y]
s = select cond, z, p
```
with
```
s = phi[x, z]
```
if we can prove that the Phi node takes values basing on select's condition.

Differential Revision: https://reviews.llvm.org/D82072
Reviewed By: nikic
Extra tests added as

commit 4c6548222b3c41d024581d28f42b3f02510bcfe3
Author: Max Kazantsev <mkazantsev@azul.com>
Date: Thu Jun 25 10:54:07 2020 +0700

[Test] Add more tests for selects & phis