[InstCombine] Replace selects with Phis

[mkazantsev]

Summary

We can sometimes replace a select with a Phi node if all of its values
are available on respective incoming edges.

[xbolva00]

Recent work by @lebedev.ri went opposite way; phi -> select (mainly to exploit cmov on x86) so I am wondering why should we go this way..

[spatel]

I'm not sure what direction we want to take this, but forming phis out of selects may conflict with SimplifyCFG. It can create select from phi in cases like this:

declare void @call(i32)

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

if.true:
  call void @call(i32 %x)
  br label %merge

if.false:
  call void @call(i32 %y)
  br label %merge

merge:
  %r1 = phi i32 [ %y, %if.false ], [ %x, %if.true ]
  %r2 = select i1 %cond, i32 %x, i32 %y
  %r = add i32 %r1, %r2
  ret i32 %r
}

$ opt -O1 phi.ll -S

declare void @call(i32)

define i32 @select_or_phi(i1 %cond, i32 %x, i32 %y) {
entry:
  %y.sink = select i1 %cond, i32 %x, i32 %y
  %r1 = select i1 %cond, i32 %x, i32 %y
  call void @call(i32 %y.sink)
  %r2 = select i1 %cond, i32 %x, i32 %y
  %r = add i32 %r1, %r2
  ret i32 %r
}

[xbolva00]

I believe selects are better for other optimizations than phis

[nikic]

Canonicalization between phis and select in either direction are pretty dangerous I think, I remember seeing discussions around this a couple times on llvm-dev, for example https://groups.google.com/d/msg/llvm-dev/VcJnLMI7Deg/20b3kBGMCgAJ.

We might want to look at some of the specific issues that D81375 ran into. Here is one: https://llvm.godbolt.org/z/KN9GFh We should be replacing %s with %c, but nothing in the pipeline does that. This looks like something we should be addressing anyway, because I don't think this patch does.

[mkazantsev]

In D82005#2097999, @xbolva00 wrote:

Recent work by @lebedev.ri went opposite way; phi -> select (mainly to exploit cmov on x86) so I am wondering why should we go this way..

In D82005#2098421, @xbolva00 wrote:

I believe selects are better for other optimizations than phis

If you look at the test select_dominating_cond_and_sink at select.ll, it shows an opportunity how we can reduce the amount of work on each execution path by sinking TrueValue and FalseValue to different branches. Maybe it will be even more obvious if TrueValue and FalseValue will be not as simple as mul and add, but some huge formulas, such that moving them to one of branches gives great benefit. Compared to this benefit, advantage of having a cmov is negligible.

If we turn Phis into Selects, we will always have all those values on common path. If we think more of it, Phis open up great opportunities for jump threading and PRE while selects don't.

If the only reason of preferring selects over phis is their better lowering on some platforms, then there should be a backend transform that does it. From optimizer's perspective, Phi has more advantages.

[mkazantsev]

In D82005#2098196, @spatel wrote:

I'm not sure what direction we want to take this, but forming phis out of selects may conflict with SimplifyCFG. It can create select from phi in cases like this:

There is no contradiction here. It's OK to turn Phi into select if we also reduce number of blocks. Add volatile stores to every branch of your example and SimplifyCFG will stop working.
But Select into a Phi provides opportunity for redundancy elimination (see my comment above) and will potentially help Jump Threading.

[mkazantsev]

In general, I'm pretty sure that InstCombine is just a wrong place to do any backend-targeted optimizations (we've seen these in transforms that turn analyzable comparison conditions into weird mixture of shifts and xors that no other pass understands).

[nikic]

@mkazantsev I don't think this is about backend-specific optimizations (which indeed InstCombine should not be concerned about), phis and selects generally have different weak points in mid-level optimization. While you are right that the use of phis enables better jump threading, phis will usually not work with redundancy elimination and code motion optimizations. E.g. I don't think CSE or GVN do anything with phis right now.

That said, I can definitely see the argument that if you already have a branch, it is beneficial to represent a select as a phi, and leave the decision on whether to turn the whole branch into a sequence of selects to SimplifyCFG.

[mkazantsev]

In D82005#2100058, @nikic wrote:

@mkazantsev I don't think this is about backend-specific optimizations (which indeed InstCombine should not be concerned about), phis and selects generally have different weak points in mid-level optimization. While you are right that the use of phis enables better jump threading, phis will usually not work with redundancy elimination and code motion optimizations. E.g. I don't think CSE or GVN do anything with phis right now.

That said, I can definitely see the argument that if you already have a branch, it is beneficial to represent a select as a phi, and leave the decision on whether to turn the whole branch into a sequence of selects to EarlyCSE.

Well, my patch doesn't break any existing test. I also have tests that get improved and may be potentially improved further. If you say that it might *not* be a profitable transform, please come up with a particular example.

Actually, GVN does *a lot* about Phis (and mostly Phis) in PRE. And EarlyCSE does not walk above merge points anyways.

[spatel]

In D82005#2100372, @mkazantsev wrote:

In D82005#2100058, @nikic wrote:

@mkazantsev I don't think this is about backend-specific optimizations (which indeed InstCombine should not be concerned about), phis and selects generally have different weak points in mid-level optimization. While you are right that the use of phis enables better jump threading, phis will usually not work with redundancy elimination and code motion optimizations. E.g. I don't think CSE or GVN do anything with phis right now.

That said, I can definitely see the argument that if you already have a branch, it is beneficial to represent a select as a phi, and leave the decision on whether to turn the whole branch into a sequence of selects to EarlyCSE.

Well, my patch doesn't break any existing test. I also have tests that get improved and may be potentially improved further. If you say that it might *not* be a profitable transform, please come up with a particular example.

Actually, GVN does *a lot* about Phis (and mostly Phis) in PRE. And EarlyCSE does not walk above merge points anyways.

This discussion reminds me of:
https://bugs.llvm.org/show_bug.cgi?id=34603
cc @efriedma @hfinkel @reames

This patch converts an explicit use of the condition value into an implicit use via control-flow, so that seems like a good choice if we're early in optimization. Given that instcombine is used at every stage of the 'opt -Ox' pipeline though, I'm not sure what the overall implications will be.

So I don't object to this patch, but it would be good to hear from others if there are concerns.

[efriedma]

I think this makes sense as a canonicalization: if we could express a select idiom using either a PHI or a select, the PHI probably makes sense as the canonical form. We clearly wouldn't want to canonicalize the other way. (The more general discussion of select vs. control flow is more centered around whether we should have the control flow in the first place; that's outside the scope of instcombine.)

The test coverage here seems a little slim; I'd like to see more coverage for interesting cases (in particular, cases where the PHI node doesn't have exactly two incoming edges).

We could try to generalize this transform to try to insert the PHI in blocks other than the block that contains the select; maybe leave that as a followup, though.

[hfinkel]

In D82005#2101927, @efriedma wrote:

I think this makes sense as a canonicalization: if we could express a select idiom using either a PHI or a select, the PHI probably makes sense as the canonical form. We clearly wouldn't want to canonicalize the other way. (The more general discussion of select vs. control flow is more centered around whether we should have the control flow in the first place; that's outside the scope of instcombine.)

The test coverage here seems a little slim; I'd like to see more coverage for interesting cases (in particular, cases where the PHI node doesn't have exactly two incoming edges).

We could try to generalize this transform to try to insert the PHI in blocks other than the block that contains the select; maybe leave that as a followup, though.

I agree. We did discuss this general question in https://bugs.llvm.org/show_bug.cgi?id=34603#c10 and I think the conclusion is still valid: Assuming we don't cause regressions because of passes that don't handle control flow (and don't cause significant compile-time slowdowns or memory overhead), canonicalizing in favor of PHIs is where we should be aiming.

[mkazantsev]

Added multi-entry block tests.

[nikic]

Some more test cases I would suggest:

• An incoming multi-edge (same predecessor occurring multiple times) from a switch.
• A select operand coming from the terminator of a predecessor block, e.g. an invoke result.
• A select with a very obviously non-dominating input. All the existing examples look "salvageable" in some way (via phi translation or hoisting).

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2466

This looks like dead code, as we canonicalize branch of not by swapping successors. Might change with D81089, but for now it should be fine to just drop it.

2494

Nit: Unnecessary braces.

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2466

WDYM dead code? This code is needed to initialize variables TrueSucc and FalseSucc.

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2466

By the moment when we process this Phi, we did not process its dominator block yet. So no, this branch will not be canonicalized when we are handling this one.

[mkazantsev]

An incoming multi-edge (same predecessor occurring multiple times) from a switch.

Not sure why it is important, but ok, will do.

A select operand coming from the terminator of a predecessor block, e.g. an invoke result.

We do not support that. Do you want a negative test?

A select with a very obviously non-dominating input.

A select cannot have a non-dominating input.

[mkazantsev]

Added test with duplicating preds and negative test with invokes. Removed braces.

[nikic]

In D82005#2105903, @mkazantsev wrote:

An incoming multi-edge (same predecessor occurring multiple times) from a switch.

Not sure why it is important, but ok, will do.

Thanks!

A select operand coming from the terminator of a predecessor block, e.g. an invoke result.

We do not support that. Do you want a negative test?

What I actually had in mind here is something along these lines:

declare i32 @__gxx_personality_v0(...)
declare i32 @foo()

define i32 @test_invoke_neg(i1 %cond, i32 %x, i32 %y) nounwind uwtable ssp personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
; CHECK-LABEL: @test_invoke_neg(
; 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:    [[RESULT:%.*]] = invoke i32 @foo()
; CHECK-NEXT:    to label [[MERGE]] unwind label [[LPAD:%.*]]
; CHECK:       merge:
; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ 0, [[IF_TRUE]] ], [ [[RESULT]], [[IF_FALSE]] ]
; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND]], i32 1, i32 [[PHI]]
; CHECK-NEXT:    ret i32 [[SEL]]
; CHECK:       lpad:
; CHECK-NEXT:    [[LP:%.*]] = landingpad { i1, i32 }
; CHECK-NEXT:    filter [0 x i1] zeroinitializer
; CHECK-NEXT:    unreachable
;
entry:
  br i1 %cond, label %if.true, label %if.false

if.true:
  br label %merge

if.false:
  %result = invoke i32 @foo()
  to label %merge unwind label %lpad

merge:
  %phi = phi i32 [ 0, %if.true ], [ %result, %if.false ]
  %sel = select i1 %cond, i32 1, i32 %phi
  ret i32 %sel

lpad:
  %lp = landingpad { i1, i32 }
  filter [0 x i1] zeroinitializer
  unreachable
}

That is, a case where the select input exactly dominates the terminator of the predecessor. But now that I wrote that, it's not really applicable to this patch, because there's the phi node sitting in between, so this is more a test for D82072 than this one.

A select with a very obviously non-dominating input.

A select cannot have a non-dominating input.

Sorry, what I meant here is that the input does not dominate the terminator of the predecessor. You do have some tests of this kind, but only as a side-effect of instructions being sunk into the block that contains the select, while the original test cases could be transformed. The suggestion here is to add one true-negative test case that will not transform even once the possible extensions (phi translation, hoisting instructions back) to this patch are implemented. Something like:

define i32 @test(i1 %cond, i32 %a, i32 %b) {
; CHECK-LABEL: @test(
; 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 [ [[A:%.*]], [[IF_TRUE]] ], [ [[B:%.*]], [[IF_FALSE]] ]
; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[PHI]], 1
; CHECK-NEXT:    [[S:%.*]] = select i1 [[COND]], i32 0, i32 [[ADD]]
; CHECK-NEXT:    ret i32 [[S]]
;
entry:
  br i1 %cond, label %if.true, label %if.false

if.true:
  br label %merge

if.false:
  br label %merge

merge:
  %phi = phi i32 [%a, %if.true], [%b, %if.false]
  %add = add i32 %phi, 1
  %s = select i1 %cond, i32 0, i32 %add
  ret i32 %s
}

In any case, this LGTM.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2466

Hm, you're right. If I add an assert(0) in here, I do get some test-suite failures. D75362 should guarantee that the branch is canonicalized first, but until then it's not dead code indeed (though it should still picked up by fixpoint iteration, but best not rely on that).

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2466

It's because InstCombine iterates blocks in post-order, so dominators go after dominated blocks.

[mkazantsev]

Ok, thanks. I'll add the test with invoke as one of selected values. As for another one (select argument does not dominate terminator), it already has coverage in exsting tests.

[mkazantsev]

commit 9bff376e5c10ea384a6eee93f7d7668d670a66e7
Author: Max Kazantsev <[e-mail]>
Date:   Tue Jun 23 11:46:59 2020 +0700

    [InstCombine] Replace selects with Phis

    We can sometimes replace a select with a Phi node if all of its values
    are available on respective incoming edges.

    Differential Revision: https://reviews.llvm.org/D82005
    Reviewed By: nikic

[uabelho]

Hi,

We've noticed a crash that started occuring with this patch.
Running

opt -S -o - bbi-50827.ll -instcombine

results in

opt: ../include/llvm/ADT/DenseMap.h:1241: llvm::DenseMapIterator::pointer llvm::DenseMapIterator<llvm::BasicBlock *, std::unique_ptr<llvm::DomTreeNodeBase<llvm::BasicBlock>, std::default_delete<llvm::DomTreeNodeBase<llvm::BasicBlock> > >, llvm::DenseMapInfo<llvm::BasicBlock *>, llvm::detail::DenseMapPair<llvm::BasicBlock *, std::unique_ptr<llvm::DomTreeNodeBase<llvm::BasicBlock>, std::default_delete<llvm::DomTreeNodeBase<llvm::BasicBlock> > > >, true>::operator->() const [KeyT = llvm::BasicBlock *, ValueT = std::unique_ptr<llvm::DomTreeNodeBase<llvm::BasicBlock>, std::default_delete<llvm::DomTreeNodeBase<llvm::BasicBlock> > >, KeyInfoT = llvm::DenseMapInfo<llvm::BasicBlock *>, Bucket = llvm::detail::DenseMapPair<llvm::BasicBlock *, std::unique_ptr<llvm::DomTreeNodeBase<llvm::BasicBlock>, std::default_delete<llvm::DomTreeNodeBase<llvm::BasicBlock> > > >, IsConst = true]: Assertion `Ptr != End && "dereferencing end() iterator"' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace.

with bbi-50827.ll being

@a = external global i1, align 1

define i16 @g()  {
entry:
  %.b = load i1, i1* @a, align 1
  %0 = select i1 %.b, i16 0, i16 5
  br label %for.body.i

for.body.i:                                       ; preds = %for.body.i, %entry
  br label %for.body.i

f.exit:                                           ; No predecessors!
  ret i16 %0
}

Note the use of %0 in f.exit, which is not reachable from entry.

[spatel]

In D82005#2445338, @uabelho wrote:

Note the use of %0 in f.exit, which is not reachable from entry.

This looks similar to the problem in 94f6d365 ( https://llvm.org/PR48369 ). I'll take a look.

[spatel]

In D82005#2446264, @spatel wrote:

In D82005#2445338, @uabelho wrote:

Note the use of %0 in f.exit, which is not reachable from entry.

This looks similar to the problem in 94f6d365 ( https://llvm.org/PR48369 ). I'll take a look.

This should handle the test shown: 4f051fe
If there are still variations of this bug present, we might want to try a different fix in instcombine and/or domtree.

[uabelho]

In D82005#2446532, @spatel wrote:

This should handle the test shown: 4f051fe

Yes, thanks!

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

if (Y == TVal) {
       Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
       return new ShuffleVectorInst(NewSel, Y, Mask);
     }
   }
 
   return nullptr;
 }
 
+static Instruction *foldSelectToPhi(SelectInst &Sel, const DominatorTree &DT,
+                                    InstCombiner::BuilderTy &Builder) {
+  // Find the block's immediate dominator that ends with a conditional branch
+  // that matches select's condition (maybe inverted).
+  BasicBlock *BB = Sel.getParent();
+  auto *IDomNode = DT[BB]->getIDom();
+  if (!IDomNode)
+    return nullptr;
+  BasicBlock *IDom = IDomNode->getBlock();
+
+  Value *Cond = Sel.getCondition();
+  Value *IfTrue, *IfFalse;
+  BasicBlock *TrueSucc, *FalseSucc;
+  if (match(IDom->getTerminator(),
+            m_Br(m_Specific(Cond), m_BasicBlock(TrueSucc),
+                 m_BasicBlock(FalseSucc)))) {
+    IfTrue = Sel.getTrueValue();
+    IfFalse = Sel.getFalseValue();
+  } 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;
+    else if (DT.dominates(FalseEdge, Incoming))
+      Inputs[Pred] = IfFalse;
+    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,
if (Instruction *Select = foldSelectBinOpIdentity(SI, TLI, *this))
     return Select;
 
   if (Instruction *Rot = foldSelectRotate(SI))
     return Rot;
 
   if (Instruction *Copysign = foldSelectToCopysign(SI, Builder))
     return Copysign;
 
+  if (Instruction *PN = foldSelectToPhi(SI, DT, Builder))
+    return replaceInstUsesWith(SI, PN);
+
   return nullptr;
 }

llvm/test/Transforms/InstCombine/select.ll

 ; CHECK-LABEL: @select_dominating_cond(
 ; 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:    [[S:%.*]] = select i1 [[COND]], i32 [[X:%.*]], i32 [[Y:%.*]]
+; CHECK-NEXT:    [[S:%.*]] = phi i32 [ [[Y:%.*]], [[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
 
 if.false:
   br label %merge
 
 merge:
   %s = select i1 %cond, i32 %x, i32 %y
   ret i32 %s
 }
 
+define i32 @select_dominating_inverted(i1 %cond, i32 %x, i32 %y) {
+; CHECK-LABEL: @select_dominating_inverted(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_FALSE:%.*]], label [[IF_TRUE:%.*]]
+; CHECK:       if.true:
+; CHECK-NEXT:    br label [[MERGE:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       merge:
+; CHECK-NEXT:    [[S:%.*]] = phi i32 [ [[X:%.*]], [[IF_FALSE]] ], [ [[Y:%.*]], [[IF_TRUE]] ]
+; CHECK-NEXT:    ret i32 [[S]]
+;
+entry:
+  %inverted = xor i1 %cond, 1
+  br i1 %inverted, label %if.true, label %if.false
+
+if.true:
+  br label %merge
+
+if.false:
+  br label %merge
+
+merge:
+  %s = select i1 %cond, i32 %x, i32 %y
+  ret i32 %s
+}
+
 ; More complex CFG: the block with select has multiple predecessors.
 define i32 @select_dominating_cond_multiple_preds(i1 %cond, i1 %cond2, i1 %cond3, i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_dominating_cond_multiple_preds(
 ; 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 i1 [[COND3:%.*]], label [[IF_FALSE_1:%.*]], label [[EXIT:%.*]]
 ; CHECK:       if.false.1:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[S:%.*]] = select i1 [[COND]], i32 [[X:%.*]], i32 [[Y:%.*]]
+; CHECK-NEXT:    [[S:%.*]] = phi i32 [ [[Y:%.*]], [[IF_FALSE_1]] ], [ [[X:%.*]], [[IF_TRUE_2]] ], [ [[X]], [[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:

 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       if.true.2:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[IF_FALSE_1:%.*]], label [[EXIT:%.*]]
 ; CHECK:       if.false.1:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[S:%.*]] = select i1 [[COND]], i32 [[X:%.*]], i32 [[Y:%.*]]
+; CHECK-NEXT:    [[S:%.*]] = phi i32 [ [[X:%.*]], [[IF_FALSE_1]] ], [ [[Y:%.*]], [[IF_TRUE_2]] ], [ [[Y]], [[IF_TRUE_1]] ]
 ; CHECK-NEXT:    ret i32 [[S]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   %inverted = xor i1 %cond, 1
   br i1 %inverted, label %if.true, label %if.false
 

 merge:
   %s = select i1 %cond, i32 %x, i32 %y
   ret i32 %s
 
 exit:
   ret i32 0
 }
 
+; More complex CFG for inverted case: the block with select has multiple predecessors that can duplicate.
+define i32 @select_dominating_cond_inverted_multiple_duplicating_preds(i1 %cond, i32 %cond2, i1 %cond3, i32 %x, i32 %y) {
+; CHECK-LABEL: @select_dominating_cond_inverted_multiple_duplicating_preds(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_FALSE:%.*]], label [[IF_TRUE:%.*]]
+; CHECK:       if.true:
+; CHECK-NEXT:    switch i32 [[COND2:%.*]], label [[SWITCH_CASE_1:%.*]] [
+; CHECK-NEXT:    i32 1, label [[MERGE:%.*]]
+; CHECK-NEXT:    i32 2, label [[MERGE]]
+; CHECK-NEXT:    i32 3, label [[MERGE]]
+; CHECK-NEXT:    ]
+; CHECK:       switch.case.1:
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       if.false:
+; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[IF_FALSE_1:%.*]], label [[EXIT:%.*]]
+; CHECK:       if.false.1:
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       merge:
+; CHECK-NEXT:    [[S:%.*]] = phi i32 [ [[X:%.*]], [[IF_FALSE_1]] ], [ [[Y:%.*]], [[SWITCH_CASE_1]] ], [ [[Y]], [[IF_TRUE]] ], [ [[Y]], [[IF_TRUE]] ], [ [[Y]], [[IF_TRUE]] ]
+; CHECK-NEXT:    ret i32 [[S]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %inverted = xor i1 %cond, 1
+  br i1 %inverted, label %if.true, label %if.false
+
+if.true:
+  switch i32 %cond2, label %switch.case.1 [
+  i32 1, label %merge
+  i32 2, label %merge
+  i32 3, label %merge
+  ]
+
+switch.case.1:
+  br label %merge
+
+if.false:
+  br i1 %cond3, label %if.false.1, label %exit
+
+if.false.1:
+  br label %merge
+
+merge:
+  %s = select i1 %cond, i32 %x, i32 %y
+  ret i32 %s
+
+exit:
+  ret i32 0
+}
+
 ; Negative test: currently we take condition from IDom, but might be willing to expand it in the future.
 define i32 @select_not_imm_dominating_cond_neg(i1 %cond, i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_not_imm_dominating_cond_neg(
 ; 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_2]]
 ; CHECK:       merge.2:
 ; CHECK-NEXT:    br i1 [[COND]], label [[IF_TRUE_3:%.*]], label [[IF_FALSE_3:%.*]]
 ; CHECK:       if.true.3:
 ; CHECK-NEXT:    br label [[MERGE_3:%.*]]
 ; CHECK:       if.false.3:
 ; CHECK-NEXT:    br label [[MERGE_3]]
 ; CHECK:       merge.3:
-; CHECK-NEXT:    [[S_2:%.*]] = select i1 [[COND]], i32 [[X:%.*]], i32 [[Y:%.*]]
-; CHECK-NEXT:    [[S_1:%.*]] = select i1 [[COND]], i32 [[X]], i32 [[Y]]
-; CHECK-NEXT:    [[S_3:%.*]] = select i1 [[COND]], i32 [[X]], i32 [[Y]]
+; CHECK-NEXT:    [[S_3:%.*]] = phi i32 [ [[Y:%.*]], [[IF_FALSE_3]] ], [ [[X:%.*]], [[IF_TRUE_3]] ]
+; CHECK-NEXT:    [[S_2:%.*]] = phi i32 [ [[Y]], [[IF_FALSE_3]] ], [ [[X]], [[IF_TRUE_3]] ]
+; CHECK-NEXT:    [[S_1:%.*]] = phi i32 [ [[Y]], [[IF_FALSE_3]] ], [ [[X]], [[IF_TRUE_3]] ]
 ; CHECK-NEXT:    [[SUM_1:%.*]] = add i32 [[S_1]], [[S_2]]
 ; CHECK-NEXT:    [[SUM_2:%.*]] = add i32 [[SUM_1]], [[S_3]]
 ; CHECK-NEXT:    ret i32 [[SUM_2]]
 ;
 entry:
   br i1 %cond, label %if.true.1, label %if.false.1
 
 if.true.1:

 if.false:
   br label %merge
 
 merge:
   %phi = phi i32 [0, %if.true], [%b, %if.false]
   %s = select i1 %cond, i32 %a, i32 %phi
   ret i32 %s
 }
+
+declare i32 @__gxx_personality_v0(...)
+declare i1 @foo()
+
+define i32 @test_invoke_neg(i32 %x, i32 %y) nounwind uwtable ssp personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+; CHECK-LABEL: @test_invoke_neg(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[COND:%.*]] = invoke i1 @foo()
+; CHECK-NEXT:    to label [[INVOKE_CONT:%.*]] unwind label [[LPAD:%.*]]
+; CHECK:       invoke.cont:
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND]], i32 [[X:%.*]], i32 [[Y:%.*]]
+; CHECK-NEXT:    ret i32 [[SEL]]
+; CHECK:       lpad:
+; CHECK-NEXT:    [[LP:%.*]] = landingpad { i1, i32 }
+; CHECK-NEXT:    filter [0 x i1] zeroinitializer
+; CHECK-NEXT:    unreachable
+;
+entry:
+  %cond = invoke i1 @foo()
+  to label %invoke.cont unwind label %lpad
+
+invoke.cont:
+  %sel = select i1 %cond, i32 %x, i32 %y
+  ret i32 %sel
+
+lpad:
+  %lp = landingpad { i1, i32 }
+  filter [0 x i1] zeroinitializer
+  unreachable
+}