[InstCombine] Combine select & Phi by same condition

[mkazantsev]

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.

[xbolva00]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2505

@spatel can you look at this fixme?

[spatel]

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]

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]

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]

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.

[mkazantsev]

In D82072#2105248, @nikic wrote:

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]

Reworked using DoPHITranslation.

[spatel]

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.

[nikic]

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]

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.

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2486

This can be just properlyDominates.

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2472

Will add a follow-up NFC comment.

[mkazantsev]

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]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2505

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

[mkazantsev]

commit 1eeb7147878edb7c0c0fbf54bc3dffd43db271b8
Author: Max Kazantsev <[e-mail]>
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 <[e-mail]>
Date: Thu Jun 25 10:54:07 2020 +0700

[Test] Add more tests for selects & phis

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

static Instruction *foldSelectToPhi(SelectInst &Sel, const DominatorTree &DT,
   } else if (match(IDom->getTerminator(),
                    m_Br(m_Not(m_Specific(Cond)), m_BasicBlock(TrueSucc),
                         m_BasicBlock(FalseSucc)))) {
     IfTrue = Sel.getFalseValue();
     IfFalse = Sel.getTrueValue();
   } else
     return nullptr;
 
   BasicBlockEdge TrueEdge(IDom, TrueSucc);
   BasicBlockEdge FalseEdge(IDom, FalseSucc);
   DenseMap<BasicBlock *, Value *> Inputs;
   for (auto *Pred : predecessors(BB)) {
     // Check implication.
     BasicBlockEdge Incoming(Pred, BB);
     if (DT.dominates(TrueEdge, Incoming))
-      Inputs[Pred] = IfTrue;
+      Inputs[Pred] = IfTrue->DoPHITranslation(BB, Pred);
     else if (DT.dominates(FalseEdge, Incoming))
-      Inputs[Pred] = IfFalse;
+      Inputs[Pred] = IfFalse->DoPHITranslation(BB, Pred);
     else
       return nullptr;
     // Check availability.
     if (auto *Insn = dyn_cast<Instruction>(Inputs[Pred]))
       if (!DT.dominates(Insn, Pred->getTerminator()))
         return nullptr;
   }
 
   Builder.SetInsertPoint(&*BB->begin());
   auto *PN = Builder.CreatePHI(Sel.getType(), Inputs.size());
   for (auto *Pred : predecessors(BB))
     PN->addIncoming(Inputs[Pred], Pred);
   PN->takeName(&Sel);
   return PN;
 }
 
 Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
   Value *CondVal = SI.getCondition();
   Value *TrueVal = SI.getTrueValue();
   Value *FalseVal = SI.getFalseValue();
   Type *SelType = SI.getType();
 
   // FIXME: Remove this workaround when freeze related patches are done.
   // For select with undef operand which feeds into an equality comparison,
   // don't simplify it so loop unswitch can know the equality comparison
   // may have an undef operand. This is a workaround for PR31652 caused by
   // descrepancy about branch on undef between LoopUnswitch and GVN.
   if (isa<UndefValue>(TrueVal) || isa<UndefValue>(FalseVal)) {
     if (llvm::any_of(SI.users(), [&](User *U) {
           ICmpInst *CI = dyn_cast<ICmpInst>(U);
           if (CI && CI->isEquality())
             return true;

llvm/test/Transforms/InstCombine/select.ll

 if.false:
   br label %merge
 
 merge:
   %s = select i1 %cond, i32 %a, i32 %b
   ret i32 %s
 }
 
-; TODO: Replace with phi[x, z].
 define i32 @select_phi_same_condition(i1 %cond, i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_phi_same_condition(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ 0, [[IF_TRUE]] ], [ [[Z:%.*]], [[IF_FALSE]] ]
-; CHECK-NEXT:    [[S:%.*]] = select i1 [[COND]], i32 [[X:%.*]], i32 [[PHI]]
+; CHECK-NEXT:    [[S:%.*]] = phi i32 [ [[Z:%.*]], [[IF_FALSE]] ], [ [[X:%.*]], [[IF_TRUE]] ]
 ; CHECK-NEXT:    ret i32 [[S]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
 
 if.true:
   br label %merge