[SimplifyCFG] `FoldBranchToCommonDest()`: deal with mismatched IV's in PHI's in common successor block

[lebedev.ri]

Summary

This tries to approach the problem noted by @arsenm:
terrible codegen for __builtin_fpclassify():
https://godbolt.org/z/388zqdE37

Just because the PHI in the common successor happens to have different
incoming values for these two blocks, doesn't mean we have to give up.
It's quite easy to deal with this, we just need to produce a select:
https://alive2.llvm.org/ce/z/000srb

Now, the cost model for this transform is rather overly strict,
so this will basically never fire. We tally all (over all preds)
the selects needed to the NumBonusInsts

[arsenm]

Thanks

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

3674

How can you be sure this won't constant fold to a ConstantExpr?

[lebedev.ri]

@arsenm thank you for taking a look!
I believe this addresses your concern.

I've tried to take even more cautious approach here,
because we *do* want this xform to happen,
but at the same time, if we produce something silly,
we won't undo it soon enough, so it seems like we should
pay extra care to canonicalize all the "selects" we "form".

[lebedev.ri]

Don't forget to remap just-created instruction,
and don't mishandle the case where we invert the cond via not.
I *think* this is it.

[lebedev.ri]

@arsenm apologies noise :)
Now(C) this should be non-miscompiling.
Forgot to add truly exhaustive test coverage, and thus
didn't deal with all combinations branch flow. All good now.

[lebedev.ri]

Actually you know what, let's keep this as simple as possible for the first step.
I've dropped all of InstSimplify stuff, and ensured that llvm test-suite (+one more thing) passes.

[arsenm]

I can't well which of these test changes is the new example. Is one of them literally what you get out of __builtin_fpclassify?

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

3570

Recepie?

[lebedev.ri]

In D139275#3975897, @arsenm wrote:

I can't well which of these test changes is the new example. Is one of them literally what you get out of __builtin_fpclassify?

Ctrl+F for test_builtin_fpclassify, it's at the end of the diff for llvm/test/Transforms/SimplifyCFG/fold-branch-to-common-dest.ll.
We don't quite manage to deal with it, but it's an improvement...

[lebedev.ri]

@arsenm thank you for taking a look!
Fix typo.

[arsenm]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

3575

Comment what a SelectCache is?

3677

Comment what this is trying to do

3679–3680

std::get_if?

3691–3692

dyn_cast instead of isa + cast

3801

I'm not really sure what this is doing; should there be a vector variant of the fpclassify test?

[lebedev.ri]

@arsenm thank you for taking a look!
Test added @incompatible_ivs_of_two_phis.vec, without SawVectorSelect |= PN.getType()->isVectorTy(); it would diverge into CHEAP and COSTLY variants.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

3801

These two lines are cost modelling.
We need to know how many selects we'll need,
and the cost model logic also rewards (allows bigger budget)
the cases where some of the instructions operate on vectors.

[nikic]

llvm/test/Transforms/SimplifyCFG/X86/SpeculativeExec.ll

15

Looks like this test, and many similar tests regress, where we go from two selects to three selects. And we never seem to recover from this in either the middle end or the back end: https://alive2.llvm.org/ce/z/GjCXkB

[nikic]

llvm/test/Transforms/SimplifyCFG/X86/SpeculativeExec.ll

15

Filed https://github.com/llvm/llvm-project/issues/59393. We should at least add an InstCombine fold, but ideally we'd avoid regressing this in SimplifyCFG.

[lebedev.ri]

llvm/test/Transforms/SimplifyCFG/X86/SpeculativeExec.ll

15

I'll deal with the InstCombine side of this.
I agree that this is a regression, that obviously affects further speculation,
but i'm not sure how much we can avoid it during speculation.
I can take a look, but not in this patch,
so i hope this patch isn't going to be blocked on that.

[lebedev.ri]

Thanks for taking a look!

Added requested instcombine fold (9ddff66d0c9c3e18d56e6b20aa26a2a8cdfb6d2b), rebased.
Does anyone else have any other comments here?

llvm/test/Transforms/SimplifyCFG/X86/SpeculativeExec.ll

15

Added InstCombine fold (9ddff66d0c9c3e18d56e6b20aa26a2a8cdfb6d2b), after which we get:

define i32 @test1(i32 %a, i32 %b, i32 %c) {
entry:
  %t1 = icmp eq i32 %b, 0
  %t2 = icmp sgt i32 %c, 1
  %t3 = zext i1 %t2 to i32
  %t4.sel = add i32 %t3, %a
  %t4 = select i1 %t1, i32 %t4.sel, i32 %b
  %t5 = add i32 %t4, -1
  ret i32 %t5
}

... so one of the two LHS selects was redundant also.
We may be able to improve this, but i really would prefer not to conflate things.

[lebedev.ri]

llvm/test/Transforms/SimplifyCFG/X86/SpeculativeExec.ll

15

I'm going to make a guess that if that feedback
was meant to be blocking, it would have been marked as such,
and proceed with the change, acknowledging the possible further improvements.

[nikic]

llvm/test/Transforms/SimplifyCFG/X86/SpeculativeExec.ll

15

This is not blocking, but I did not review the implementation and only glanced over test diffs. The patch looks pretty complicated for what it does (in the sense of a minimal baseline implementation on top of which incremental changes may be stacked).

[lebedev.ri]

llvm/test/Transforms/SimplifyCFG/X86/SpeculativeExec.ll

15

This is not blocking

but I did not review the implementation and only glanced over test diffs.

Right, i did not imply that you did.

The patch looks pretty complicated for what it does (in the sense of a minimal baseline implementation on top of which incremental changes may be stacked).

Right, the non-test side of things could be much smaller if not for the abstractons.
I'm hoping to make use of them in other places we speculate.

[nickdesaulniers]

@nathanchance is reporting that this is breaking PPC32 Linux kernel boots.
https://github.com/ClangBuiltLinux/linux/issues/1770
We'll work on trying to get a reproducer or more info, but "heads up."

[joanahalili]

In D139275#3993229, @nickdesaulniers wrote:

@nathanchance is reporting that this is breaking PPC32 Linux kernel boots.
https://github.com/ClangBuiltLinux/linux/issues/1770
We'll work on trying to get a reproducer or more info, but "heads up."

We are also experiencing some test failures that root cause to this commit. Here is a reproducer:
https://godbolt.org/z/aq6nYffxv

The function returns different results with the two different compiler versions.

[alexfh]

I will revert this patch. Please ensure the provided test case works fine before recommitting.

[lebedev.ri]

In D139275#4001601, @alexfh wrote:

I will revert this patch. Please ensure the provided test case works fine before recommitting.

Thanks for the reproducer. Will revert in a sec.

[alexfh]

In D139275#4001603, @lebedev.ri wrote:

In D139275#4001601, @alexfh wrote:

I will revert this patch. Please ensure the provided test case works fine before recommitting.

Thanks for the reproducer. Will revert in a sec.

I've done that already. I had a revert prepared with conflict resolutions for the opaque pointers migration.

[lebedev.ri]

In D139275#4001628, @alexfh wrote:

In D139275#4001603, @lebedev.ri wrote:

In D139275#4001601, @alexfh wrote:

I will revert this patch. Please ensure the provided test case works fine before recommitting.

Thanks for the reproducer. Will revert in a sec.

I've done that already. I had a revert prepared with conflict resolutions for the opaque pointers migration.

So. There is a problem.
Before the patch, this is what we got: https://alive2.llvm.org/ce/z/WMZXQu <-- good
With the patch, we'd get: https://alive2.llvm.org/ce/z/oBg872 <-- miscompile
BUT. If we just run simplifycfg on the old result, we get: https://alive2.llvm.org/ce/z/zb7bsb <-- good!
So the actual miscompile is elsewhere.

[lebedev.ri]

-- 49. InstCombinePass

----------------------------------------
define float @_Z1ff(float noundef %0) nofree noundef willreturn memory(none) {
%1:
  %2 = fcmp ugt float noundef %0, 0.000000
  %3 = fcmp ult float noundef %0, 1.000000
  %or.cond = and i1 %2, %3
  %4 = fcmp uge float noundef %0, 0.200000
  %5 = xor i1 %2, %or.cond
  %.0.sel6 = select i1 %5, float 0.100000, float 0.000000
  %or.cond7 = and i1 %4, %or.cond
  %6 = fadd float noundef %0, -0.100000
  %.0 = select i1 %or.cond7, float %6, float %.0.sel6
  ret float %.0
}
=>
define float @_Z1ff(float noundef %0) nofree noundef willreturn memory(none) {
%1:
  %2 = fcmp ugt float noundef %0, 0.000000
  %3 = fcmp ult float noundef %0, 1.000000
  %or.cond = and i1 %2, %3
  %4 = fcmp uge float noundef %0, 0.200000
  %5 = fadd float noundef %0, -0.100000
  %.0.sel6 = select i1 %4, float %5, float 0.100000
  %.0 = select i1 %or.cond, float %.0.sel6, float 0.000000
  ret float %.0
}
Transformation doesn't verify! (unsound)
ERROR: Value mismatch

Example:
float noundef %0 = #x7f800000 (+oo)

Source:
i1 %2 = #x1 (1)
i1 %3 = #x0 (0)
i1 %or.cond = #x0 (0)
i1 %4 = #x1 (1)
i1 %5 = #x1 (1)
float %.0.sel6 = #x3dcccccd (0.100000001490?)
i1 %or.cond7 = #x0 (0)
float %6 = #x7f800000 (+oo)
float %.0 = #x3dcccccd (0.100000001490?)

Target:
i1 %2 = #x1 (1)
i1 %3 = #x0 (0)
i1 %or.cond = #x0 (0)
i1 %4 = #x1 (1)
float %5 = #x7f800000 (+oo)
float %.0.sel6 = #x7f800000 (+oo)
float %.0 = #x00000000 (+0.0)
Source value: #x3dcccccd (0.100000001490?)
Target value: #x00000000 (+0.0)

Pass: InstCombinePass
Command line: '/builddirs/llvm-project/build-Clang15/bin/opt' '-load=/repositories/alive2/build-Clang-release/tv/tv.so' '-load-pass-plugin=/repositories/alive2/build-Clang-release/tv/tv.so' '-tv-exit-on-error' '-O1' '/tmp/test.ll' '-tv-smt-to=20000' '-tv-report-dir=/repositories/alive2/build-Clang-release/logs' '-tv-smt-stats'

[aeubanks]

just wanted to note that this did increase binary size in some places (https://bugs.chromium.org/p/chromium/issues/detail?id=1401820), even though the description claims it will basically never fire. (I'm not blocking anything on that, just a note)

separately, IMO this patch is non-trivial enough to deserve an lgtm before landing

[lebedev.ri]

In D139275#4009140, @aeubanks wrote:

just wanted to note that this did increase binary size in some places (https://bugs.chromium.org/p/chromium/issues/detail?id=1401820),

It's almost assuredly second-order effects.

even though the description claims it will basically never fire. (I'm not blocking anything on that, just a note)

That description is based off of it's current cost model, which is extremely, extremely, conservative.

separately, IMO this patch is non-trivial enough to deserve an lgtm before landing

There are several things to consider in this cases:

• Trivial-ness is different for everyone. I think, this is reasonably straight-forward.
• Review is useful to catch issues, BUT it is even more important to learn from previous issues to not repeat them, both to reduce review cycles, especially so when no adequate review can be requested/acquired.
• We seem to not have many active contributors in the areas i touch, so if i always just wait for review, i will be waiting a long while. And at the same time, not learn from mistakes, and not be able to review other's code.

[apilipenko]

FYI, this change caused widespread performance regressions in our testing. We haven't investigated further since the change was reverted.

I can re-run these tests and do some analysis on the next revision once you decide to reapply.

[lebedev.ri]

In D139275#4022015, @apilipenko wrote:

FYI, this change caused widespread performance regressions in our testing. We haven't investigated further since the change was reverted.

I can re-run these tests and do some analysis on the next revision once you decide to reapply.

At this point this is waiting on @alexfh's reproducer mostly.
I'm not sure what sequence of events you have in mind,
but presumably it may be good to have an idea
about at least some of those regressions before this is relanded?

[samtebbs]

We've also seen lots of large regressions for a variety of ARM CPUs with the original patch and that weren't fixed by any updates. At the moment it's not clear if downstream changes are to blame so I'll sort out a reproducer as soon as I can.

[alexfh]

In D139275#4022050, @lebedev.ri wrote:

In D139275#4022015, @apilipenko wrote:

FYI, this change caused widespread performance regressions in our testing. We haven't investigated further since the change was reverted.

I can re-run these tests and do some analysis on the next revision once you decide to reapply.

At this point this is waiting on @alexfh's reproducer mostly.

IIUC, the reproducer you mentioned is the one here: https://reviews.llvm.org/rG9ddff66d0c9c3e18d56e6b20aa26a2a8cdfb6d2b#1158810. Given that there was a bit of confusion and the problem had been fixed in ToT before the issue was reported, there's no concerns on our side about relanding this commit.

Just fyi, our performance testing shows around 20% improvements of the mediabench-g721 benchmark from the LLVM's MultiSource test-suite associated with the reland of this patch (428f36401b1b695fd501ebfdc8773bed8ced8d4e) and no regressions on any other benchmarks we run.

[lebedev.ri]

@apilipenko @samtebbs please, can you clarify, do you wish to block relanding of this patch until those issues you saw are addressed, or at least reduced and reported?

In D139275#4046383, @alexfh wrote:

In D139275#4022050, @lebedev.ri wrote:

In D139275#4022015, @apilipenko wrote:

FYI, this change caused widespread performance regressions in our testing. We haven't investigated further since the change was reverted.

I can re-run these tests and do some analysis on the next revision once you decide to reapply.

At this point this is waiting on @alexfh's reproducer mostly.

IIUC, the reproducer you mentioned is the one here: https://reviews.llvm.org/rG9ddff66d0c9c3e18d56e6b20aa26a2a8cdfb6d2b#1158810. Given that there was a bit of confusion and the problem had been fixed in ToT before the issue was reported, there's no concerns on our side about relanding this commit.

Just fyi, our performance testing shows around 20% improvements of the mediabench-g721 benchmark from the LLVM's MultiSource test-suite associated with the reland of this patch (428f36401b1b695fd501ebfdc8773bed8ced8d4e) and no regressions on any other benchmarks we run.

Thank you!

[samtebbs]

After investigating it looks like the regressions are due to something downstream so I don't want to block this relanding based on that. Thank you for waiting.

[lebedev.ri]

In D139275#4059264, @samtebbs wrote:

After investigating it looks like the regressions are due to something downstream so I don't want to block this relanding based on that. Thank you for waiting.

Thanks! @apilipenko ?

[samtebbs]

Hi @lebedev.ri , after some more investigation it looks like the regressions are due to this patch breaking canonical loop form and therefore preventing optimisations later on in the pipeline. I don't think that the additional comparisons and selects that come from this transformation are ideal in all cases, either. I've attached a reproducer.

reprod.ll1 KBDownload

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

 }
 
 static bool performBranchToCommonDestFolding(BranchInst *BI, BranchInst *PBI,
                                              DomTreeUpdater *DTU,
                                              MemorySSAUpdater *MSSAU,
                                              const TargetTransformInfo *TTI) {
   BasicBlock *BB = BI->getParent();
   BasicBlock *PredBlock = PBI->getParent();
 
   // Determine if the two branches share a common destination.
   BasicBlock *CommonSucc;
   Instruction::BinaryOps Opc;
   bool InvertPredCond;
   std::tie(CommonSucc, Opc, InvertPredCond) =
       *shouldFoldCondBranchesToCommonDestination(BI, PBI, TTI);
 
   LLVM_DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
 
   IRBuilder<> Builder(PBI);
   // The builder is used to create instructions to eliminate the branch in BB.
   // If BB's terminator has !annotation metadata, add it to the new
   // instructions.
static bool performBranchToCommonDestFolding(BranchInst *BI, BranchInst *PBI,
   // If BI was a loop latch, it may have had associated loop metadata.
   // We need to copy it to the new latch, that is, PBI.
   if (MDNode *LoopMD = BI->getMetadata(LLVMContext::MD_loop))
     PBI->setMetadata(LLVMContext::MD_loop, LoopMD);
 
   ValueToValueMapTy VMap; // maps original values to cloned values
   CloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BB, PredBlock, VMap);
 
+  SmallDenseMap<std::pair<Value *, Value *>, SelectInst *, 2> UniqueSelects;
+  for (PHINode &PN : CommonSucc->phis()) {
+    Value *BBIV = PN.getIncomingValueForBlock(BB);
+    Value *PBBIV = PN.getIncomingValueForBlock(PredBlock);
+    if (BBIV == PBBIV)
+      continue;
+    SelectInst *&SI =
+        UniqueSelects.insert({{BBIV, PBBIV}, nullptr}).first->getSecond();
+    if (!SI)
+      SI = cast<SelectInst>(Builder.CreateSelect(PBI->getCondition(), BBIV,
+                                                 PBBIV, PN.getName() + ".sel"));
+    PN.setIncomingValueForBlock(PredBlock, SI);
+  }
+
   // Now that the Cond was cloned into the predecessor basic block,
   // or/and the two conditions together.
   Value *BICond = VMap[BI->getCondition()];
   PBI->setCondition(
       createLogicalOp(Builder, Opc, PBI->getCondition(), BICond, "or.cond"));
 
   // Copy any debug value intrinsics into the end of PredBlock.
   for (Instruction &I : *BB) {
     if (isa<DbgInfoIntrinsic>(I)) {
       Instruction *NewI = I.clone();
       RemapInstruction(NewI, VMap,
                        RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
       NewI->insertBefore(PBI);
     }
   }
 
   ++NumFoldBranchToCommonDest;
   return true;
 }
 
 /// Return if an instruction's type or any of its operands' types are a vector
 /// type.
if (!Cond ||
        !isa<SelectInst>(Cond)) ||
       Cond->getParent() != BB || !Cond->hasOneUse())
     return false;
 
   // Finally, don't infinitely unroll conditional loops.
   if (is_contained(successors(BB), BB))
     return false;
 
+  unsigned NumSelectsNeeded = 0;
+  bool SawVectorSelect = false;
+
   // With which predecessors will we want to deal with?
   SmallVector<BasicBlock *, 8> Preds;
   for (BasicBlock *PredBlock : predecessors(BB)) {
     BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
 
     // Check that we have two conditional branches.  If there is a PHI node in
     // the common successor, verify that the same value flows in from both
     // blocks.
-    if (!PBI || PBI->isUnconditional() || !SafeToMergeTerminators(BI, PBI))
+    if (!PBI || PBI->isUnconditional())
       continue;
 
     // Determine if the two branches share a common destination.
     BasicBlock *CommonSucc;
     Instruction::BinaryOps Opc;
     bool InvertPredCond;
     if (auto Recipe = shouldFoldCondBranchesToCommonDestination(BI, PBI, TTI))
       std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
     else
       continue;
 
     // Check the cost of inserting the necessary logic before performing the
     // transformation.
     if (TTI) {
       Type *Ty = BI->getCondition()->getType();
       InstructionCost Cost = TTI->getArithmeticInstrCost(Opc, Ty, CostKind);
       if (InvertPredCond && (!PBI->getCondition()->hasOneUse() ||
           !isa<CmpInst>(PBI->getCondition())))
         Cost += TTI->getArithmeticInstrCost(Instruction::Xor, Ty, CostKind);
 
       if (Cost > BranchFoldThreshold)
         continue;
     }
 
+    SmallSet<std::pair<Value *, Value *>, 2> UniqueSelectsInPred;
+    for (PHINode &PN : CommonSucc->phis()) {
+      Value *BBIV = PN.getIncomingValueForBlock(BB);
+      Value *PBBIV = PN.getIncomingValueForBlock(PredBlock);
+      if (BBIV == PBBIV || !UniqueSelectsInPred.insert({BBIV, PBBIV}).second)
+        continue;
+      ++NumSelectsNeeded;
+      SawVectorSelect |= PN.getType()->isVectorTy();
+    }
+
     // Ok, we do want to deal with this predecessor. Record it.
     Preds.emplace_back(PredBlock);
   }
 
   // If there aren't any predecessors into which we can fold,
   // don't bother checking the cost.
   if (Preds.empty())
     return false;
 
   // Only allow this transformation if computing the condition doesn't involve
   // too many instructions and these involved instructions can be executed
   // unconditionally. We denote all involved instructions except the condition
   // as "bonus instructions", and only allow this transformation when the
   // number of the bonus instructions we'll need to create when cloning into
   // each predecessor does not exceed a certain threshold.
-  unsigned NumBonusInsts = 0;
-  bool SawVectorOp = false;
+  unsigned NumBonusInsts = NumSelectsNeeded;
+  bool SawVectorOp = SawVectorSelect;
   const unsigned PredCount = Preds.size();
   for (Instruction &I : *BB) {
     // Don't check the branch condition comparison itself.
     if (&I == Cond)
       continue;
     // Ignore dbg intrinsics, and the terminator.
     if (isa<DbgInfoIntrinsic>(I) || isa<BranchInst>(I))
       continue;
     // I must be safe to execute unconditionally.
     if (!isSafeToSpeculativelyExecute(&I))
       return false;

llvm/test/Transforms/InstCombine/unused-nonnull.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature
 ; RUN: opt -S -O3 -o - %s | FileCheck %s
 
 ; PR44154: LLVM c3b06d0c393e caused the body of @main to be replaced with
 ; unreachable. Check that we perform the expected calls and optimizations.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define i32 @main(i32 %argc, ptr %argv) #0 {
 ; CHECK-LABEL: define {{[^@]+}}@main
 ; CHECK-SAME: (i32 [[ARGC:%.*]], ptr nocapture readonly [[ARGV:%.*]]) local_unnamed_addr #[[ATTR0:[0-9]+]] {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp slt i32 [[ARGC]], 2
-; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[TMP0]], i32 0, i32 [[ARGC]]
-; CHECK-NEXT:    ret i32 [[SPEC_SELECT]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[ARGC]], 1
+; CHECK-NEXT:    [[RETVAL_SEL:%.*]] = select i1 [[TMP0]], i32 [[ARGC]], i32 0
+; CHECK-NEXT:    ret i32 [[RETVAL_SEL]]
 ;
 entry:
   %ptr = load ptr, ptr %argv
   %0 = call i32 @compute(ptr %ptr, i32 %argc)
   %1 = icmp slt i32 %argc, 2
   br i1 %1, label %done, label %do_work
 
 do_work:

llvm/test/Transforms/LICM/hoist-phi.ll

 end:
   ret void
 }
 
 ; We can hoist blocks that contain an edge that exits the loop by ignoring that
 ; edge in the hoisted block.
 ; CHECK-LABEL: @triangle_phi_loopexit
 define void @triangle_phi_loopexit(i32 %x, ptr %p) {
-; CHECK-LABEL: entry:
-; CHECK-DAG: %add = add i32 %x, 1
-; CHECK-DAG: %cmp1 = icmp sgt i32 %x, 0
-; CHECK-DAG: %cmp2 = icmp sgt i32 10, %add
-; CHECK-ENABLED: br i1 %cmp1, label %[[IF_LICM:.*]], label %[[THEN_LICM:.*]]
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[X:%.*]], 1
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp sle i32 [[X]], 0
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 10, [[ADD]]
+; CHECK-NEXT:    [[PHI_SEL:%.*]] = select i1 [[CMP1]], i32 [[ADD]], i32 [[X]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    [[CMP3:%.*]] = icmp ne i32 [[PHI_SEL]], 0
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[THEN:%.*]], label [[END:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    store i32 [[PHI_SEL]], ptr [[P:%.*]], align 4
+; CHECK-NEXT:    br i1 [[CMP3]], label [[LOOP]], label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
 entry:
   br label %loop
 
-; CHECK-ENABLED: [[IF_LICM]]:
-; CHECK-ENABLED: br label %[[THEN_LICM]]
-
-; CHECK-ENABLED: [[THEN_LICM]]:
-; CHECK-ENABLED: %phi = phi i32 [ %add, %[[IF_LICM]] ], [ %x, %entry ]
-; CHECK: br label %loop
-
 loop:
   %cmp1 = icmp sgt i32 %x, 0
   br i1 %cmp1, label %if, label %then
 
 if:
   %add = add i32 %x, 1
   %cmp2 = icmp sgt i32 10, %add
   br i1 %cmp2, label %then, label %end
 
-; CHECK-LABEL: then:
-; CHECK-DISABLED: %phi = phi i32 [ %add, %if ], [ %x, %loop ]
 then:
   %phi = phi i32 [ %add, %if ], [ %x, %loop ]
   store i32 %phi, ptr %p
   %cmp3 = icmp ne i32 %phi, 0
   br i1 %cmp3, label %loop, label %end
 
 end:
   ret void

llvm/test/Transforms/LICM/sinking.ll

 
 ; Check if LICM can sink a sinkable instruction the exit blocks through
 ; a non-trivially replacable PHI node.
 define i32 @test14(i32 %N, i32 %N2, i1 %C) {
 ; CHECK-LABEL: @test14(
 ; CHECK-NEXT:  Entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       Loop:
-; CHECK-NEXT:    [[N_ADDR_0_PN:%.*]] = phi i32 [ [[DEC:%.*]], [[CONTLOOP:%.*]] ], [ [[N:%.*]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[N_ADDR_0_PN:%.*]] = phi i32 [ [[N:%.*]], [[ENTRY:%.*]] ], [ [[DEC:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[DEC]] = add i32 [[N_ADDR_0_PN]], -1
-; CHECK-NEXT:    br i1 [[C:%.*]], label [[CONTLOOP]], label [[OUT12_SPLIT_LOOP_EXIT1:%.*]]
-; CHECK:       ContLoop:
 ; CHECK-NEXT:    [[TMP_1:%.*]] = icmp ne i32 [[N_ADDR_0_PN]], 1
-; CHECK-NEXT:    br i1 [[TMP_1]], label [[LOOP]], label [[OUT12_SPLIT_LOOP_EXIT:%.*]]
-; CHECK:       Out12.split.loop.exit:
-; CHECK-NEXT:    [[N_ADDR_0_PN_LCSSA4:%.*]] = phi i32 [ [[N_ADDR_0_PN]], [[CONTLOOP]] ]
-; CHECK-NEXT:    [[SINK_MUL_LE3:%.*]] = mul i32 [[N]], [[N_ADDR_0_PN_LCSSA4]]
-; CHECK-NEXT:    br label [[OUT12:%.*]]
-; CHECK:       Out12.split.loop.exit1:
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C:%.*]], i1 [[TMP_1]], i1 false
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[LOOP]], label [[OUT12:%.*]]
+; CHECK:       Out12:
 ; CHECK-NEXT:    [[N_ADDR_0_PN_LCSSA:%.*]] = phi i32 [ [[N_ADDR_0_PN]], [[LOOP]] ]
 ; CHECK-NEXT:    [[SINK_MUL_LE:%.*]] = mul i32 [[N]], [[N_ADDR_0_PN_LCSSA]]
 ; CHECK-NEXT:    [[SINK_SUB_LE:%.*]] = sub i32 [[SINK_MUL_LE]], [[N]]
-; CHECK-NEXT:    br label [[OUT12]]
-; CHECK:       Out12:
-; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ [[SINK_MUL_LE3]], [[OUT12_SPLIT_LOOP_EXIT]] ], [ [[SINK_SUB_LE]], [[OUT12_SPLIT_LOOP_EXIT1]] ]
-; CHECK-NEXT:    ret i32 [[TMP]]
+; CHECK-NEXT:    [[TMP_SEL_LE:%.*]] = select i1 [[C]], i32 [[SINK_MUL_LE]], i32 [[SINK_SUB_LE]]
+; CHECK-NEXT:    ret i32 [[TMP_SEL_LE]]
 ;
 Entry:
   br label %Loop
 Loop:
   %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
   %sink.mul = mul i32 %N, %N_addr.0.pn
   %sink.sub = sub i32 %sink.mul, %N
   %dec = add i32 %N_addr.0.pn, -1

 ; to the shared operations. As of now, we split predecessors of non-trivially
 ; replicalbe PHIs by default in LICM because all incoming edges of a
 ; non-trivially replacable PHI in LCSSA is critical.
 define i32 @test15(i32 %N, i32 %N2, i1 %C) {
 ; CHECK-LABEL: @test15(
 ; CHECK-NEXT:  Entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       Loop:
-; CHECK-NEXT:    [[N_ADDR_0_PN:%.*]] = phi i32 [ [[DEC:%.*]], [[CONTLOOP:%.*]] ], [ [[N:%.*]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[N_ADDR_0_PN:%.*]] = phi i32 [ [[N:%.*]], [[ENTRY:%.*]] ], [ [[DEC:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[DEC]] = add i32 [[N_ADDR_0_PN]], -1
-; CHECK-NEXT:    br i1 [[C:%.*]], label [[CONTLOOP]], label [[OUT12_SPLIT_LOOP_EXIT1:%.*]]
-; CHECK:       ContLoop:
 ; CHECK-NEXT:    [[TMP_1:%.*]] = icmp ne i32 [[N_ADDR_0_PN]], 1
-; CHECK-NEXT:    br i1 [[TMP_1]], label [[LOOP]], label [[OUT12_SPLIT_LOOP_EXIT:%.*]]
-; CHECK:       Out12.split.loop.exit:
-; CHECK-NEXT:    [[N_ADDR_0_PN_LCSSA5:%.*]] = phi i32 [ [[N_ADDR_0_PN]], [[CONTLOOP]] ]
-; CHECK-NEXT:    [[SINK_MUL_LE4:%.*]] = mul i32 [[N]], [[N_ADDR_0_PN_LCSSA5]]
-; CHECK-NEXT:    [[SINK_SUB2_LE:%.*]] = sub i32 [[SINK_MUL_LE4]], [[N2:%.*]]
-; CHECK-NEXT:    br label [[OUT12:%.*]]
-; CHECK:       Out12.split.loop.exit1:
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C:%.*]], i1 [[TMP_1]], i1 false
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[LOOP]], label [[OUT12:%.*]]
+; CHECK:       Out12:
 ; CHECK-NEXT:    [[N_ADDR_0_PN_LCSSA:%.*]] = phi i32 [ [[N_ADDR_0_PN]], [[LOOP]] ]
 ; CHECK-NEXT:    [[SINK_MUL_LE:%.*]] = mul i32 [[N]], [[N_ADDR_0_PN_LCSSA]]
 ; CHECK-NEXT:    [[SINK_SUB_LE:%.*]] = sub i32 [[SINK_MUL_LE]], [[N]]
-; CHECK-NEXT:    br label [[OUT12]]
-; CHECK:       Out12:
-; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ [[SINK_SUB2_LE]], [[OUT12_SPLIT_LOOP_EXIT]] ], [ [[SINK_SUB_LE]], [[OUT12_SPLIT_LOOP_EXIT1]] ]
-; CHECK-NEXT:    ret i32 [[TMP]]
+; CHECK-NEXT:    [[SINK_SUB2_LE:%.*]] = sub i32 [[SINK_MUL_LE]], [[N2:%.*]]
+; CHECK-NEXT:    [[TMP_SEL_LE:%.*]] = select i1 [[C]], i32 [[SINK_SUB2_LE]], i32 [[SINK_SUB_LE]]
+; CHECK-NEXT:    ret i32 [[TMP_SEL_LE]]
 ;
 Entry:
   br label %Loop
 Loop:
   %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
   %sink.mul = mul i32 %N, %N_addr.0.pn
   %sink.sub = sub i32 %sink.mul, %N
   %sink.sub2 = sub i32 %sink.mul, %N2

llvm/test/Transforms/LoopUnroll/runtime-loop-multiple-exits.ll

 define void @non_loop(i32 %arg) {
 ; CHECK-LABEL: @non_loop(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    %i = icmp sgt i32 undef, %arg
 ; CHECK-NEXT:    br i1 %i, label %preheader, label %returnblock
 ; CHECK:       preheader:
 ; CHECK-NEXT:    br label %header
 ; CHECK:       header:
-; CHECK-NEXT:    br i1 true, label %latchExit, label %latch
-; CHECK:       latch:
-; CHECK-NEXT:    br label %latchExit
-; CHECK:       latchExit:
-; CHECK-NEXT:    %i2.ph = phi i32 [ %arg, %header ], [ -1, %latch ]
 ; CHECK-NEXT:    br label %returnblock
 ; CHECK:       returnblock:
-; CHECK-NEXT:    %i2 = phi i32 [ -1, %entry ], [ %i2.ph, %latchExit ]
+; CHECK-NEXT:    %i2 = phi i32 [ -1, %entry ], [ %arg, %header ]
 ; CHECK-NEXT:    ret void
 ;
 
 entry:
   %i = icmp sgt i32 undef, %arg
   br i1 %i, label %preheader, label %returnblock
 
 preheader:                                 ; preds = %entry
returnblock:                                         ; preds = %latchExit, %entry
   %i2 = phi i32 [ -1, %entry ], [ %i2.ph, %latchExit ]
   ret void
 }
 
 ; Latch exit is shared by all exiting blocks
 define void @unique_exit(i32 %N, i32 %M) {
 ; EPILOG-LABEL: @unique_exit(
 ; EPILOG-NEXT:  preheader:
-; EPILOG-NEXT:    %M.shifted = shl i32 %M, 3
-; EPILOG-NEXT:    %umax = call i32 @llvm.umax.i32(i32 %M.shifted, i32 1)
-; EPILOG-NEXT:    %0 = freeze i32 %umax
-; EPILOG-NEXT:    %1 = add i32 %0, -1
-; EPILOG-NEXT:    %xtraiter = and i32 %0, 7
-; EPILOG-NEXT:    %2 = icmp ult i32 %1, 7
-; EPILOG-NEXT:    br i1 %2, label %latchExit.unr-lcssa, label %preheader.new
-; EPILOG:       preheader.new:
-; EPILOG-NEXT:    %unroll_iter = sub i32 %0, %xtraiter
+; EPILOG-NEXT:    %M.shifted = shl nuw i32 %M, 3
 ; EPILOG-NEXT:    br label %header
 ; EPILOG:       header:
-; EPILOG-NEXT:    %i4 = phi i32 [ 0, %preheader.new ], [ %inc.7, %latch.7 ]
-; EPILOG-NEXT:    %niter = phi i32 [ 0, %preheader.new ], [ %niter.next.7, %latch.7 ]
-; EPILOG-NEXT:    %inc = add nuw nsw i32 %i4, 1
+; EPILOG-NEXT:    %i4 = phi i32 [ 0, %preheader ], [ %inc, %header ]
+; EPILOG-NEXT:    %inc = add nuw i32 %i4, 1
 ; EPILOG-NEXT:    %cmp1 = icmp ult i32 %inc, %N
-; EPILOG-NEXT:    br i1 %cmp1, label %latch, label %latchExit.epilog-lcssa.loopexit
-; EPILOG:       latch:
-; EPILOG-NEXT:    %niter.next = add nuw nsw i32 %niter, 1
-; EPILOG-NEXT:    %inc.1 = add nuw nsw i32 %inc, 1
-; EPILOG-NEXT:    %cmp1.1 = icmp ult i32 %inc.1, %N
-; EPILOG-NEXT:    br i1 %cmp1.1, label %latch.1, label %latchExit.epilog-lcssa.loopexit
-; EPILOG:       latch.1:
-; EPILOG-NEXT:    %niter.next.1 = add nuw nsw i32 %niter.next, 1
-; EPILOG-NEXT:    %inc.2 = add nuw nsw i32 %inc.1, 1
-; EPILOG-NEXT:    %cmp1.2 = icmp ult i32 %inc.2, %N
-; EPILOG-NEXT:    br i1 %cmp1.2, label %latch.2, label %latchExit.epilog-lcssa.loopexit
-; EPILOG:       latch.2:
-; EPILOG-NEXT:    %niter.next.2 = add nuw nsw i32 %niter.next.1, 1
-; EPILOG-NEXT:    %inc.3 = add nuw nsw i32 %inc.2, 1
-; EPILOG-NEXT:    %cmp1.3 = icmp ult i32 %inc.3, %N
-; EPILOG-NEXT:    br i1 %cmp1.3, label %latch.3, label %latchExit.epilog-lcssa.loopexit
-; EPILOG:       latch.3:
-; EPILOG-NEXT:    %niter.next.3 = add nuw nsw i32 %niter.next.2, 1
-; EPILOG-NEXT:    %inc.4 = add nuw nsw i32 %inc.3, 1
-; EPILOG-NEXT:    %cmp1.4 = icmp ult i32 %inc.4, %N
-; EPILOG-NEXT:    br i1 %cmp1.4, label %latch.4, label %latchExit.epilog-lcssa.loopexit
-; EPILOG:       latch.4:
-; EPILOG-NEXT:    %niter.next.4 = add nuw nsw i32 %niter.next.3, 1
-; EPILOG-NEXT:    %inc.5 = add nuw nsw i32 %inc.4, 1
-; EPILOG-NEXT:    %cmp1.5 = icmp ult i32 %inc.5, %N
-; EPILOG-NEXT:    br i1 %cmp1.5, label %latch.5, label %latchExit.epilog-lcssa.loopexit
-; EPILOG:       latch.5:
-; EPILOG-NEXT:    %niter.next.5 = add nuw nsw i32 %niter.next.4, 1
-; EPILOG-NEXT:    %inc.6 = add nuw nsw i32 %inc.5, 1
-; EPILOG-NEXT:    %cmp1.6 = icmp ult i32 %inc.6, %N
-; EPILOG-NEXT:    br i1 %cmp1.6, label %latch.6, label %latchExit.epilog-lcssa.loopexit
-; EPILOG:       latch.6:
-; EPILOG-NEXT:    %niter.next.6 = add nuw nsw i32 %niter.next.5, 1
-; EPILOG-NEXT:    %inc.7 = add nuw i32 %inc.6, 1
-; EPILOG-NEXT:    %cmp1.7 = icmp ult i32 %inc.7, %N
-; EPILOG-NEXT:    br i1 %cmp1.7, label %latch.7, label %latchExit.epilog-lcssa.loopexit
-; EPILOG:       latch.7:
-; EPILOG-NEXT:    %niter.next.7 = add nuw i32 %niter.next.6, 1
-; EPILOG-NEXT:    %niter.ncmp.7 = icmp ne i32 %niter.next.7, %unroll_iter
-; EPILOG-NEXT:    br i1 %niter.ncmp.7, label %header, label %latchExit.unr-lcssa.loopexit
-; EPILOG:       latchExit.unr-lcssa.loopexit:
-; EPILOG-NEXT:    %i2.ph.ph.ph = phi i32 [ -1, %latch.7 ]
-; EPILOG-NEXT:    %i4.unr.ph = phi i32 [ %inc.7, %latch.7 ]
-; EPILOG-NEXT:    br label %latchExit.unr-lcssa
-; EPILOG:       latchExit.unr-lcssa:
-; EPILOG-NEXT:    %i2.ph.ph = phi i32 [ undef, %preheader ], [ %i2.ph.ph.ph, %latchExit.unr-lcssa.loopexit ]
-; EPILOG-NEXT:    %i4.unr = phi i32 [ 0, %preheader ], [ %i4.unr.ph, %latchExit.unr-lcssa.loopexit ]
-; EPILOG-NEXT:    %lcmp.mod = icmp ne i32 %xtraiter, 0
-; EPILOG-NEXT:    br i1 %lcmp.mod, label %header.epil.preheader, label %latchExit
-; EPILOG:       header.epil.preheader:
-; EPILOG-NEXT:    br label %header.epil
-; EPILOG:       header.epil:
-; EPILOG-NEXT:    %i4.epil = phi i32 [ %inc.epil, %latch.epil ], [ %i4.unr, %header.epil.preheader ]
-; EPILOG-NEXT:    %epil.iter = phi i32 [ 0, %header.epil.preheader ], [ %epil.iter.next, %latch.epil ]
-; EPILOG-NEXT:    %inc.epil = add nuw i32 %i4.epil, 1
-; EPILOG-NEXT:    %cmp1.epil = icmp ult i32 %inc.epil, %N
-; EPILOG-NEXT:    br i1 %cmp1.epil, label %latch.epil, label %latchExit.epilog-lcssa.loopexit2
-; EPILOG:       latch.epil:
-; EPILOG-NEXT:    %cmp.epil = icmp ult i32 %inc.epil, %M.shifted
-; EPILOG-NEXT:    %epil.iter.next = add i32 %epil.iter, 1
-; EPILOG-NEXT:    %epil.iter.cmp = icmp ne i32 %epil.iter.next, %xtraiter
-; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %header.epil, label %latchExit.epilog-lcssa.loopexit2, !llvm.loop !8
-; EPILOG:       latchExit.epilog-lcssa.loopexit:
-; EPILOG-NEXT:    %i2.ph.ph1.ph = phi i32 [ %i4, %header ], [ %inc, %latch ], [ %inc.1, %latch.1 ], [ %inc.2, %latch.2 ], [ %inc.3, %latch.3 ], [ %inc.4, %latch.4 ], [ %inc.5, %latch.5 ], [ %inc.6, %latch.6 ]
-; EPILOG-NEXT:    br label %latchExit.epilog-lcssa
-; EPILOG:       latchExit.epilog-lcssa.loopexit2:
-; EPILOG-NEXT:    %i2.ph.ph1.ph3 = phi i32 [ %i4.epil, %header.epil ], [ -1, %latch.epil ]
-; EPILOG-NEXT:    br label %latchExit.epilog-lcssa
-; EPILOG:       latchExit.epilog-lcssa:
-; EPILOG-NEXT:    %i2.ph.ph1 = phi i32 [ %i2.ph.ph1.ph, %latchExit.epilog-lcssa.loopexit ], [ %i2.ph.ph1.ph3, %latchExit.epilog-lcssa.loopexit2 ]
-; EPILOG-NEXT:    br label %latchExit
+; EPILOG-NEXT:    %cmp = icmp ult i32 %inc, %M.shifted
+; EPILOG-NEXT:    %i2.ph.sel = select i1 %cmp1, i32 -1, i32 %i4
+; EPILOG-NEXT:    %or.cond = select i1 %cmp1, i1 %cmp, i1 false
+; EPILOG-NEXT:    br i1 %or.cond, label %header, label %latchExit
 ; EPILOG:       latchExit:
-; EPILOG-NEXT:    %i2.ph = phi i32 [ %i2.ph.ph, %latchExit.unr-lcssa ], [ %i2.ph.ph1, %latchExit.epilog-lcssa ]
 ; EPILOG-NEXT:    ret void
 ;
 ; EPILOG-BLOCK-LABEL: @unique_exit(
 ; EPILOG-BLOCK-NEXT:  preheader:
 ; EPILOG-BLOCK-NEXT:    %M.shifted = shl i32 %M, 3
 ; EPILOG-BLOCK-NEXT:    %umax = call i32 @llvm.umax.i32(i32 %M.shifted, i32 1)
-; EPILOG-BLOCK-NEXT:    %0 = freeze i32 %umax
-; EPILOG-BLOCK-NEXT:    %1 = add i32 %0, -1
-; EPILOG-BLOCK-NEXT:    %xtraiter = and i32 %0, 1
-; EPILOG-BLOCK-NEXT:    %2 = icmp ult i32 %1, 1
-; EPILOG-BLOCK-NEXT:    br i1 %2, label %latchExit.unr-lcssa, label %preheader.new
+; EPILOG-BLOCK-NEXT:    %0 = add i32 %umax, -1
+; EPILOG-BLOCK-NEXT:    %1 = freeze i32 %0
+; EPILOG-BLOCK-NEXT:    %umax1 = call i32 @llvm.umax.i32(i32 %N, i32 1)
+; EPILOG-BLOCK-NEXT:    %2 = add i32 %umax1, -1
+; EPILOG-BLOCK-NEXT:    %umin = call i32 @llvm.umin.i32(i32 %1, i32 %2)
+; EPILOG-BLOCK-NEXT:    %3 = add nuw i32 %umin, 1
+; EPILOG-BLOCK-NEXT:    %xtraiter = and i32 %3, 1
+; EPILOG-BLOCK-NEXT:    %4 = icmp ult i32 %umin, 1
+; EPILOG-BLOCK-NEXT:    br i1 %4, label %latchExit.unr-lcssa, label %preheader.new
 ; EPILOG-BLOCK:       preheader.new:
-; EPILOG-BLOCK-NEXT:    %unroll_iter = sub i32 %0, %xtraiter
+; EPILOG-BLOCK-NEXT:    %unroll_iter = sub i32 %3, %xtraiter
 ; EPILOG-BLOCK-NEXT:    br label %header
 ; EPILOG-BLOCK:       header:
-; EPILOG-BLOCK-NEXT:    %i4 = phi i32 [ 0, %preheader.new ], [ %inc.1, %latch.1 ]
-; EPILOG-BLOCK-NEXT:    %niter = phi i32 [ 0, %preheader.new ], [ %niter.next.1, %latch.1 ]
+; EPILOG-BLOCK-NEXT:    %i4 = phi i32 [ 0, %preheader.new ], [ %inc.1, %header ]
+; EPILOG-BLOCK-NEXT:    %niter = phi i32 [ 0, %preheader.new ], [ %niter.next.1, %header ]
 ; EPILOG-BLOCK-NEXT:    %inc = add nuw nsw i32 %i4, 1
-; EPILOG-BLOCK-NEXT:    %cmp1 = icmp ult i32 %inc, %N
-; EPILOG-BLOCK-NEXT:    br i1 %cmp1, label %latch, label %latchExit.epilog-lcssa.loopexit
-; EPILOG-BLOCK:       latch:
 ; EPILOG-BLOCK-NEXT:    %niter.next = add nuw nsw i32 %niter, 1
 ; EPILOG-BLOCK-NEXT:    %inc.1 = add nuw i32 %inc, 1
-; EPILOG-BLOCK-NEXT:    %cmp1.1 = icmp ult i32 %inc.1, %N
-; EPILOG-BLOCK-NEXT:    br i1 %cmp1.1, label %latch.1, label %latchExit.epilog-lcssa.loopexit
-; EPILOG-BLOCK:       latch.1:
-; EPILOG-BLOCK-NEXT:    %niter.next.1 = add nuw i32 %niter.next, 1
+; EPILOG-BLOCK-NEXT:    %niter.next.1 = add i32 %niter.next, 1
 ; EPILOG-BLOCK-NEXT:    %niter.ncmp.1 = icmp ne i32 %niter.next.1, %unroll_iter
 ; EPILOG-BLOCK-NEXT:    br i1 %niter.ncmp.1, label %header, label %latchExit.unr-lcssa.loopexit, !llvm.loop !8
 ; EPILOG-BLOCK:       latchExit.unr-lcssa.loopexit:
-; EPILOG-BLOCK-NEXT:    %i2.ph.ph.ph = phi i32 [ -1, %latch.1 ]
-; EPILOG-BLOCK-NEXT:    %i4.unr.ph = phi i32 [ %inc.1, %latch.1 ]
 ; EPILOG-BLOCK-NEXT:    br label %latchExit.unr-lcssa
 ; EPILOG-BLOCK:       latchExit.unr-lcssa:
-; EPILOG-BLOCK-NEXT:    %i2.ph.ph = phi i32 [ undef, %preheader ], [ %i2.ph.ph.ph, %latchExit.unr-lcssa.loopexit ]
-; EPILOG-BLOCK-NEXT:    %i4.unr = phi i32 [ 0, %preheader ], [ %i4.unr.ph, %latchExit.unr-lcssa.loopexit ]
 ; EPILOG-BLOCK-NEXT:    %lcmp.mod = icmp ne i32 %xtraiter, 0
 ; EPILOG-BLOCK-NEXT:    br i1 %lcmp.mod, label %header.epil.preheader, label %latchExit
 ; EPILOG-BLOCK:       header.epil.preheader:
 ; EPILOG-BLOCK-NEXT:    br label %header.epil
 ; EPILOG-BLOCK:       header.epil:
-; EPILOG-BLOCK-NEXT:    %inc.epil = add nuw i32 %i4.unr, 1
-; EPILOG-BLOCK-NEXT:    %cmp1.epil = icmp ult i32 %inc.epil, %N
-; EPILOG-BLOCK-NEXT:    br i1 %cmp1.epil, label %latch.epil, label %latchExit.epilog-lcssa
-; EPILOG-BLOCK:       latch.epil:
-; EPILOG-BLOCK-NEXT:    br label %latchExit.epilog-lcssa
-; EPILOG-BLOCK:       latchExit.epilog-lcssa.loopexit:
-; EPILOG-BLOCK-NEXT:    %i2.ph.ph1.ph = phi i32 [ %i4, %header ], [ %inc, %latch ]
-; EPILOG-BLOCK-NEXT:    br label %latchExit.epilog-lcssa
-; EPILOG-BLOCK:       latchExit.epilog-lcssa:
-; EPILOG-BLOCK-NEXT:    %i2.ph.ph1 = phi i32 [ -1, %latch.epil ], [ %i4.unr, %header.epil ], [ %i2.ph.ph1.ph, %latchExit.epilog-lcssa.loopexit ]
 ; EPILOG-BLOCK-NEXT:    br label %latchExit
 ; EPILOG-BLOCK:       latchExit:
-; EPILOG-BLOCK-NEXT:    %i2.ph = phi i32 [ %i2.ph.ph, %latchExit.unr-lcssa ], [ %i2.ph.ph1, %latchExit.epilog-lcssa ]
 ; EPILOG-BLOCK-NEXT:    ret void
 ;
 ; PROLOG-LABEL: @unique_exit(
 ; PROLOG-NEXT:  preheader:
-; PROLOG-NEXT:    %M.shifted = shl i32 %M, 3
-; PROLOG-NEXT:    %umax = call i32 @llvm.umax.i32(i32 %M.shifted, i32 1)
-; PROLOG-NEXT:    %0 = freeze i32 %umax
-; PROLOG-NEXT:    %1 = add i32 %0, -1
-; PROLOG-NEXT:    %xtraiter = and i32 %0, 7
-; PROLOG-NEXT:    %lcmp.mod = icmp ne i32 %xtraiter, 0
-; PROLOG-NEXT:    br i1 %lcmp.mod, label %header.prol.preheader, label %header.prol.loopexit
-; PROLOG:       header.prol.preheader:
-; PROLOG-NEXT:    br label %header.prol
-; PROLOG:       header.prol:
-; PROLOG-NEXT:    %i4.prol = phi i32 [ %inc.prol, %latch.prol ], [ 0, %header.prol.preheader ]
-; PROLOG-NEXT:    %prol.iter = phi i32 [ 0, %header.prol.preheader ], [ %prol.iter.next, %latch.prol ]
-; PROLOG-NEXT:    %inc.prol = add nuw i32 %i4.prol, 1
-; PROLOG-NEXT:    %cmp1.prol = icmp ult i32 %inc.prol, %N
-; PROLOG-NEXT:    br i1 %cmp1.prol, label %latch.prol, label %latchExit.unr-lcssa.loopexit1
-; PROLOG:       latch.prol:
-; PROLOG-NEXT:    %cmp.prol = icmp ult i32 %inc.prol, %M.shifted
-; PROLOG-NEXT:    %prol.iter.next = add i32 %prol.iter, 1
-; PROLOG-NEXT:    %prol.iter.cmp = icmp ne i32 %prol.iter.next, %xtraiter
-; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %header.prol, label %header.prol.loopexit.unr-lcssa, !llvm.loop !8
-; PROLOG:       header.prol.loopexit.unr-lcssa:
-; PROLOG-NEXT:    %i4.unr.ph = phi i32 [ %inc.prol, %latch.prol ]
-; PROLOG-NEXT:    %i2.ph.unr.ph = phi i32 [ -1, %latch.prol ]
-; PROLOG-NEXT:    br label %header.prol.loopexit
-; PROLOG:       header.prol.loopexit:
-; PROLOG-NEXT:    %i4.unr = phi i32 [ 0, %preheader ], [ %i4.unr.ph, %header.prol.loopexit.unr-lcssa ]
-; PROLOG-NEXT:    %i2.ph.unr = phi i32 [ undef, %preheader ], [ %i2.ph.unr.ph, %header.prol.loopexit.unr-lcssa ]
-; PROLOG-NEXT:    %2 = icmp ult i32 %1, 7
-; PROLOG-NEXT:    br i1 %2, label %latchExit, label %preheader.new
-; PROLOG:       preheader.new:
+; PROLOG-NEXT:    %M.shifted = shl nuw i32 %M, 3
 ; PROLOG-NEXT:    br label %header
 ; PROLOG:       header:
-; PROLOG-NEXT:    %i4 = phi i32 [ %i4.unr, %preheader.new ], [ %inc.7, %latch.7 ]
+; PROLOG-NEXT:    %i4 = phi i32 [ 0, %preheader ], [ %inc, %header ]
 ; PROLOG-NEXT:    %inc = add nuw i32 %i4, 1
 ; PROLOG-NEXT:    %cmp1 = icmp ult i32 %inc, %N
-; PROLOG-NEXT:    br i1 %cmp1, label %latch, label %latchExit.unr-lcssa.loopexit
-; PROLOG:       latch:
-; PROLOG-NEXT:    %inc.1 = add nuw i32 %inc, 1
-; PROLOG-NEXT:    %cmp1.1 = icmp ult i32 %inc.1, %N
-; PROLOG-NEXT:    br i1 %cmp1.1, label %latch.1, label %latchExit.unr-lcssa.loopexit
-; PROLOG:       latch.1:
-; PROLOG-NEXT:    %inc.2 = add nuw i32 %inc.1, 1
-; PROLOG-NEXT:    %cmp1.2 = icmp ult i32 %inc.2, %N
-; PROLOG-NEXT:    br i1 %cmp1.2, label %latch.2, label %latchExit.unr-lcssa.loopexit
-; PROLOG:       latch.2:
-; PROLOG-NEXT:    %inc.3 = add nuw i32 %inc.2, 1
-; PROLOG-NEXT:    %cmp1.3 = icmp ult i32 %inc.3, %N
-; PROLOG-NEXT:    br i1 %cmp1.3, label %latch.3, label %latchExit.unr-lcssa.loopexit
-; PROLOG:       latch.3:
-; PROLOG-NEXT:    %inc.4 = add nuw i32 %inc.3, 1
-; PROLOG-NEXT:    %cmp1.4 = icmp ult i32 %inc.4, %N
-; PROLOG-NEXT:    br i1 %cmp1.4, label %latch.4, label %latchExit.unr-lcssa.loopexit
-; PROLOG:       latch.4:
-; PROLOG-NEXT:    %inc.5 = add nuw i32 %inc.4, 1
-; PROLOG-NEXT:    %cmp1.5 = icmp ult i32 %inc.5, %N
-; PROLOG-NEXT:    br i1 %cmp1.5, label %latch.5, label %latchExit.unr-lcssa.loopexit
-; PROLOG:       latch.5:
-; PROLOG-NEXT:    %inc.6 = add nuw i32 %inc.5, 1
-; PROLOG-NEXT:    %cmp1.6 = icmp ult i32 %inc.6, %N
-; PROLOG-NEXT:    br i1 %cmp1.6, label %latch.6, label %latchExit.unr-lcssa.loopexit
-; PROLOG:       latch.6:
-; PROLOG-NEXT:    %inc.7 = add nuw i32 %inc.6, 1
-; PROLOG-NEXT:    %cmp1.7 = icmp ult i32 %inc.7, %N
-; PROLOG-NEXT:    br i1 %cmp1.7, label %latch.7, label %latchExit.unr-lcssa.loopexit
-; PROLOG:       latch.7:
-; PROLOG-NEXT:    %cmp.7 = icmp ult i32 %inc.7, %M.shifted
-; PROLOG-NEXT:    br i1 %cmp.7, label %header, label %latchExit.unr-lcssa.loopexit
-; PROLOG:       latchExit.unr-lcssa.loopexit:
-; PROLOG-NEXT:    %i2.ph.ph.ph = phi i32 [ %i4, %header ], [ %inc, %latch ], [ %inc.1, %latch.1 ], [ %inc.2, %latch.2 ], [ %inc.3, %latch.3 ], [ %inc.4, %latch.4 ], [ %inc.5, %latch.5 ], [ %inc.6, %latch.6 ], [ -1, %latch.7 ]
-; PROLOG-NEXT:    br label %latchExit.unr-lcssa
-; PROLOG:       latchExit.unr-lcssa.loopexit1:
-; PROLOG-NEXT:    %i2.ph.ph.ph2 = phi i32 [ %i4.prol, %header.prol ]
-; PROLOG-NEXT:    br label %latchExit.unr-lcssa
-; PROLOG:       latchExit.unr-lcssa:
-; PROLOG-NEXT:    %i2.ph.ph = phi i32 [ %i2.ph.ph.ph, %latchExit.unr-lcssa.loopexit ], [ %i2.ph.ph.ph2, %latchExit.unr-lcssa.loopexit1 ]
-; PROLOG-NEXT:    br label %latchExit
+; PROLOG-NEXT:    %cmp = icmp ult i32 %inc, %M.shifted
+; PROLOG-NEXT:    %i2.ph.sel = select i1 %cmp1, i32 -1, i32 %i4
+; PROLOG-NEXT:    %or.cond = select i1 %cmp1, i1 %cmp, i1 false
+; PROLOG-NEXT:    br i1 %or.cond, label %header, label %latchExit
 ; PROLOG:       latchExit:
-; PROLOG-NEXT:    %i2.ph = phi i32 [ %i2.ph.unr, %header.prol.loopexit ], [ %i2.ph.ph, %latchExit.unr-lcssa ]
 ; PROLOG-NEXT:    ret void
 ;
 ; PROLOG-BLOCK-LABEL: @unique_exit(
 ; PROLOG-BLOCK-NEXT:  preheader:
 ; PROLOG-BLOCK-NEXT:    %M.shifted = shl i32 %M, 3
 ; PROLOG-BLOCK-NEXT:    %umax = call i32 @llvm.umax.i32(i32 %M.shifted, i32 1)
-; PROLOG-BLOCK-NEXT:    %0 = freeze i32 %umax
-; PROLOG-BLOCK-NEXT:    %1 = add i32 %0, -1
-; PROLOG-BLOCK-NEXT:    %xtraiter = and i32 %0, 1
+; PROLOG-BLOCK-NEXT:    %0 = add i32 %umax, -1
+; PROLOG-BLOCK-NEXT:    %1 = freeze i32 %0
+; PROLOG-BLOCK-NEXT:    %umax1 = call i32 @llvm.umax.i32(i32 %N, i32 1)
+; PROLOG-BLOCK-NEXT:    %2 = add i32 %umax1, -1
+; PROLOG-BLOCK-NEXT:    %umin = call i32 @llvm.umin.i32(i32 %1, i32 %2)
+; PROLOG-BLOCK-NEXT:    %3 = add nuw i32 %umin, 1
+; PROLOG-BLOCK-NEXT:    %xtraiter = and i32 %3, 1
 ; PROLOG-BLOCK-NEXT:    %lcmp.mod = icmp ne i32 %xtraiter, 0
 ; PROLOG-BLOCK-NEXT:    br i1 %lcmp.mod, label %header.prol.preheader, label %header.prol.loopexit
 ; PROLOG-BLOCK:       header.prol.preheader:
 ; PROLOG-BLOCK-NEXT:    br label %header.prol
 ; PROLOG-BLOCK:       header.prol:
-; PROLOG-BLOCK-NEXT:    %cmp1.prol = icmp ult i32 1, %N
-; PROLOG-BLOCK-NEXT:    br i1 %cmp1.prol, label %latch.prol, label %latchExit.unr-lcssa
-; PROLOG-BLOCK:       latch.prol:
 ; PROLOG-BLOCK-NEXT:    br label %header.prol.loopexit
 ; PROLOG-BLOCK:       header.prol.loopexit:
-; PROLOG-BLOCK-NEXT:    %i4.unr = phi i32 [ 0, %preheader ], [ 1, %latch.prol ]
-; PROLOG-BLOCK-NEXT:    %i2.ph.unr = phi i32 [ undef, %preheader ], [ -1, %latch.prol ]
-; PROLOG-BLOCK-NEXT:    %2 = icmp ult i32 %1, 1
-; PROLOG-BLOCK-NEXT:    br i1 %2, label %latchExit, label %preheader.new
+; PROLOG-BLOCK-NEXT:    %i4.unr = phi i32 [ 0, %preheader ], [ 1, %header.prol ]
+; PROLOG-BLOCK-NEXT:    %4 = icmp ult i32 %umin, 1
+; PROLOG-BLOCK-NEXT:    br i1 %4, label %latchExit, label %preheader.new
 ; PROLOG-BLOCK:       preheader.new:
 ; PROLOG-BLOCK-NEXT:    br label %header
 ; PROLOG-BLOCK:       header:
-; PROLOG-BLOCK-NEXT:    %i4 = phi i32 [ %i4.unr, %preheader.new ], [ %inc.1, %latch.1 ]
+; PROLOG-BLOCK-NEXT:    %i4 = phi i32 [ %i4.unr, %preheader.new ], [ %inc.1, %header ]
 ; PROLOG-BLOCK-NEXT:    %inc = add nuw i32 %i4, 1
-; PROLOG-BLOCK-NEXT:    %cmp1 = icmp ult i32 %inc, %N
-; PROLOG-BLOCK-NEXT:    br i1 %cmp1, label %latch, label %latchExit.unr-lcssa.loopexit
-; PROLOG-BLOCK:       latch:
 ; PROLOG-BLOCK-NEXT:    %inc.1 = add nuw i32 %inc, 1
 ; PROLOG-BLOCK-NEXT:    %cmp1.1 = icmp ult i32 %inc.1, %N
-; PROLOG-BLOCK-NEXT:    br i1 %cmp1.1, label %latch.1, label %latchExit.unr-lcssa.loopexit
-; PROLOG-BLOCK:       latch.1:
 ; PROLOG-BLOCK-NEXT:    %cmp.1 = icmp ult i32 %inc.1, %M.shifted
-; PROLOG-BLOCK-NEXT:    br i1 %cmp.1, label %header, label %latchExit.unr-lcssa.loopexit, !llvm.loop !8
-; PROLOG-BLOCK:       latchExit.unr-lcssa.loopexit:
-; PROLOG-BLOCK-NEXT:    %i2.ph.ph.ph = phi i32 [ %i4, %header ], [ %inc, %latch ], [ -1, %latch.1 ]
-; PROLOG-BLOCK-NEXT:    br label %latchExit.unr-lcssa
+; PROLOG-BLOCK-NEXT:    %or.cond.1 = select i1 %cmp1.1, i1 %cmp.1, i1 false
+; PROLOG-BLOCK-NEXT:    br i1 %or.cond.1, label %header, label %latchExit.unr-lcssa, !llvm.loop !8
 ; PROLOG-BLOCK:       latchExit.unr-lcssa:
-; PROLOG-BLOCK-NEXT:    %i2.ph.ph = phi i32 [ 0, %header.prol ], [ %i2.ph.ph.ph, %latchExit.unr-lcssa.loopexit ]
 ; PROLOG-BLOCK-NEXT:    br label %latchExit
 ; PROLOG-BLOCK:       latchExit:
-; PROLOG-BLOCK-NEXT:    %i2.ph = phi i32 [ %i2.ph.unr, %header.prol.loopexit ], [ %i2.ph.ph, %latchExit.unr-lcssa ]
 ; PROLOG-BLOCK-NEXT:    ret void
 ;
 
 preheader:
   %M.shifted = shl nuw i32 %M, 3
   br label %header
 
 header:                                           ; preds = %preheader, %latch

 ; EPILOG-NEXT:    i64 42, label %exit1.loopexit2
 ; EPILOG-NEXT:    ]
 ; EPILOG:       loop_latch.epil:
 ; EPILOG-NEXT:    %iv_next.epil = add nuw nsw i64 %iv.epil, 1
 ; EPILOG-NEXT:    %sum.next.epil = add i64 %sum.epil, %add
 ; EPILOG-NEXT:    %cmp.epil = icmp ne i64 %iv_next.epil, %trip
 ; EPILOG-NEXT:    %epil.iter.next = add i64 %epil.iter, 1
 ; EPILOG-NEXT:    %epil.iter.cmp = icmp ne i64 %epil.iter.next, %xtraiter
-; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %loop_header.epil, label %latchexit.epilog-lcssa, !llvm.loop !9
+; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %loop_header.epil, label %latchexit.epilog-lcssa, !llvm.loop !8
 ; EPILOG:       latchexit.epilog-lcssa:
 ; EPILOG-NEXT:    %sum.next.lcssa.ph1 = phi i64 [ %sum.next.epil, %loop_latch.epil ]
 ; EPILOG-NEXT:    br label %latchexit
 ; EPILOG:       latchexit:
 ; EPILOG-NEXT:    %sum.next.lcssa = phi i64 [ %sum.next.lcssa.ph, %latchexit.unr-lcssa ], [ %sum.next.lcssa.ph1, %latchexit.epilog-lcssa ]
 ; EPILOG-NEXT:    ret i64 %sum.next.lcssa
 ;
 ; EPILOG-BLOCK-LABEL: @test5(

 ; PROLOG-NEXT:    i64 42, label %exit1.loopexit1
 ; PROLOG-NEXT:    ]
 ; PROLOG:       loop_latch.prol:
 ; PROLOG-NEXT:    %iv_next.prol = add nuw nsw i64 %iv.prol, 1
 ; PROLOG-NEXT:    %sum.next.prol = add i64 %sum.prol, %add
 ; PROLOG-NEXT:    %cmp.prol = icmp ne i64 %iv_next.prol, %trip
 ; PROLOG-NEXT:    %prol.iter.next = add i64 %prol.iter, 1
 ; PROLOG-NEXT:    %prol.iter.cmp = icmp ne i64 %prol.iter.next, %xtraiter
-; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %loop_header.prol, label %loop_header.prol.loopexit.unr-lcssa, !llvm.loop !9
+; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %loop_header.prol, label %loop_header.prol.loopexit.unr-lcssa, !llvm.loop !8
 ; PROLOG:       loop_header.prol.loopexit.unr-lcssa:
 ; PROLOG-NEXT:    %iv.unr.ph = phi i64 [ %iv_next.prol, %loop_latch.prol ]
 ; PROLOG-NEXT:    %sum.unr.ph = phi i64 [ %sum.next.prol, %loop_latch.prol ]
 ; PROLOG-NEXT:    %sum.next.lcssa.unr.ph = phi i64 [ %sum.next.prol, %loop_latch.prol ]
 ; PROLOG-NEXT:    br label %loop_header.prol.loopexit
 ; PROLOG:       loop_header.prol.loopexit:
 ; PROLOG-NEXT:    %iv.unr = phi i64 [ 0, %entry ], [ %iv.unr.ph, %loop_header.prol.loopexit.unr-lcssa ]
 ; PROLOG-NEXT:    %sum.unr = phi i64 [ 0, %entry ], [ %sum.unr.ph, %loop_header.prol.loopexit.unr-lcssa ]

 ; EPILOG:       latch.epil:
 ; EPILOG-NEXT:    %arrayidx.epil = getelementptr inbounds i32, i32* %a, i64 %indvars.iv.epil
 ; EPILOG-NEXT:    %load.epil = load i32, i32* %arrayidx.epil, align 4
 ; EPILOG-NEXT:    %add.epil = add nsw i32 %load.epil, %sum.02.epil
 ; EPILOG-NEXT:    %indvars.iv.next.epil = add i64 %indvars.iv.epil, 1
 ; EPILOG-NEXT:    %exitcond.epil = icmp eq i64 %indvars.iv.next.epil, %n
 ; EPILOG-NEXT:    %epil.iter.next = add i64 %epil.iter, 1
 ; EPILOG-NEXT:    %epil.iter.cmp = icmp ne i64 %epil.iter.next, %xtraiter
-; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %header.epil, label %latch_exit.epilog-lcssa, !llvm.loop !10
+; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %header.epil, label %latch_exit.epilog-lcssa, !llvm.loop !9
 ; EPILOG:       latch_exit.epilog-lcssa:
 ; EPILOG-NEXT:    %sum.0.lcssa.ph1 = phi i32 [ %add.epil, %latch.epil ]
 ; EPILOG-NEXT:    br label %latch_exit
 ; EPILOG:       latch_exit:
 ; EPILOG-NEXT:    %sum.0.lcssa = phi i32 [ %sum.0.lcssa.ph, %latch_exit.unr-lcssa ], [ %sum.0.lcssa.ph1, %latch_exit.epilog-lcssa ]
 ; EPILOG-NEXT:    ret i32 %sum.0.lcssa
 ; EPILOG:       for.exit2.loopexit:
 ; EPILOG-NEXT:    %retval.ph = phi i32 [ 42, %for.exiting_block ], [ %sum.02, %header ], [ %add, %latch ], [ 42, %for.exiting_block.1 ], [ %add.1, %latch.1 ], [ 42, %for.exiting_block.2 ], [ %add.2, %latch.2 ], [ 42, %for.exiting_block.3 ], [ %add.3, %latch.3 ], [ 42, %for.exiting_block.4 ], [ %add.4, %latch.4 ], [ 42, %for.exiting_block.5 ], [ %add.5, %latch.5 ], [ 42, %for.exiting_block.6 ], [ %add.6, %latch.6 ], [ 42, %for.exiting_block.7 ]

 ; PROLOG:       latch.prol:
 ; PROLOG-NEXT:    %arrayidx.prol = getelementptr inbounds i32, i32* %a, i64 %indvars.iv.prol
 ; PROLOG-NEXT:    %load.prol = load i32, i32* %arrayidx.prol, align 4
 ; PROLOG-NEXT:    %add.prol = add nsw i32 %load.prol, %sum.02.prol
 ; PROLOG-NEXT:    %indvars.iv.next.prol = add i64 %indvars.iv.prol, 1
 ; PROLOG-NEXT:    %exitcond.prol = icmp eq i64 %indvars.iv.next.prol, %n
 ; PROLOG-NEXT:    %prol.iter.next = add i64 %prol.iter, 1
 ; PROLOG-NEXT:    %prol.iter.cmp = icmp ne i64 %prol.iter.next, %xtraiter
-; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %header.prol, label %header.prol.loopexit.unr-lcssa, !llvm.loop !10
+; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %header.prol, label %header.prol.loopexit.unr-lcssa, !llvm.loop !9
 ; PROLOG:       header.prol.loopexit.unr-lcssa:
 ; PROLOG-NEXT:    %sum.0.lcssa.unr.ph = phi i32 [ %add.prol, %latch.prol ]
 ; PROLOG-NEXT:    %indvars.iv.unr.ph = phi i64 [ %indvars.iv.next.prol, %latch.prol ]
 ; PROLOG-NEXT:    %sum.02.unr.ph = phi i32 [ %add.prol, %latch.prol ]
 ; PROLOG-NEXT:    br label %header.prol.loopexit
 ; PROLOG:       header.prol.loopexit:
 ; PROLOG-NEXT:    %sum.0.lcssa.unr = phi i32 [ undef, %entry ], [ %sum.0.lcssa.unr.ph, %header.prol.loopexit.unr-lcssa ]
 ; PROLOG-NEXT:    %indvars.iv.unr = phi i64 [ 0, %entry ], [ %indvars.iv.unr.ph, %header.prol.loopexit.unr-lcssa ]

 ; EPILOG-NEXT:    %i6.epil = phi i64 [ %i6.unr, %header.epil.preheader ], [ %add.epil, %latch.epil ]
 ; EPILOG-NEXT:    %epil.iter = phi i64 [ 0, %header.epil.preheader ], [ %epil.iter.next, %latch.epil ]
 ; EPILOG-NEXT:    br i1 false, label %loopexit1.loopexit1, label %latch.epil
 ; EPILOG:       latch.epil:
 ; EPILOG-NEXT:    %add.epil = add nuw nsw i64 %i6.epil, 1
 ; EPILOG-NEXT:    %i9.epil = icmp slt i64 %add.epil, %sext
 ; EPILOG-NEXT:    %epil.iter.next = add i64 %epil.iter, 1
 ; EPILOG-NEXT:    %epil.iter.cmp = icmp ne i64 %epil.iter.next, %xtraiter
-; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %header.epil, label %latchexit.epilog-lcssa, !llvm.loop !11
+; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %header.epil, label %latchexit.epilog-lcssa, !llvm.loop !10
 ; EPILOG:       latchexit.epilog-lcssa:
 ; EPILOG-NEXT:    br label %latchexit
 ; EPILOG:       latchexit:
 ; EPILOG-NEXT:    unreachable
 ; EPILOG:       loopexit2:
 ; EPILOG-NEXT:    ret i32 %shft
 ; EPILOG:       loopexit1.loopexit:
 ; EPILOG-NEXT:    %sext3.ph = phi i32 [ %shft, %header ], [ %shft, %latch ], [ %shft, %latch.1 ], [ %shft, %latch.2 ], [ %shft, %latch.3 ], [ %shft, %latch.4 ], [ %shft, %latch.5 ], [ %shft, %latch.6 ]

 ; PROLOG-NEXT:    %i6.prol = phi i64 [ 1, %header.prol.preheader ], [ %add.prol, %latch.prol ]
 ; PROLOG-NEXT:    %prol.iter = phi i64 [ 0, %header.prol.preheader ], [ %prol.iter.next, %latch.prol ]
 ; PROLOG-NEXT:    br i1 false, label %loopexit1.loopexit1, label %latch.prol
 ; PROLOG:       latch.prol:
 ; PROLOG-NEXT:    %add.prol = add nuw nsw i64 %i6.prol, 1
 ; PROLOG-NEXT:    %i9.prol = icmp slt i64 %add.prol, %sext
 ; PROLOG-NEXT:    %prol.iter.next = add i64 %prol.iter, 1
 ; PROLOG-NEXT:    %prol.iter.cmp = icmp ne i64 %prol.iter.next, %xtraiter
-; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %header.prol, label %header.prol.loopexit.unr-lcssa, !llvm.loop !11
+; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %header.prol, label %header.prol.loopexit.unr-lcssa, !llvm.loop !10
 ; PROLOG:       header.prol.loopexit.unr-lcssa:
 ; PROLOG-NEXT:    %i6.unr.ph = phi i64 [ %add.prol, %latch.prol ]
 ; PROLOG-NEXT:    br label %header.prol.loopexit
 ; PROLOG:       header.prol.loopexit:
 ; PROLOG-NEXT:    %i6.unr = phi i64 [ 1, %preheader ], [ %i6.unr.ph, %header.prol.loopexit.unr-lcssa ]
 ; PROLOG-NEXT:    %3 = icmp ult i64 %2, 7
 ; PROLOG-NEXT:    br i1 %3, label %latchexit, label %preheader.new
 ; PROLOG:       preheader.new:

 ; EPILOG-NEXT:    %i3.epil = phi i64 [ %i4.epil, %latch.epil ], [ %i3.unr, %innerH.epil.preheader ]
 ; EPILOG-NEXT:    %epil.iter = phi i64 [ 0, %innerH.epil.preheader ], [ %epil.iter.next, %latch.epil ]
 ; EPILOG-NEXT:    %i4.epil = add nuw nsw i64 %i3.epil, 1
 ; EPILOG-NEXT:    br i1 false, label %outerloop.loopexit.loopexit1, label %latch.epil
 ; EPILOG:       latch.epil:
 ; EPILOG-NEXT:    %i6.epil = icmp ult i64 %i4.epil, 100
 ; EPILOG-NEXT:    %epil.iter.next = add i64 %epil.iter, 1
 ; EPILOG-NEXT:    %epil.iter.cmp = icmp ne i64 %epil.iter.next, %xtraiter
-; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %innerH.epil, label %exit.epilog-lcssa, !llvm.loop !12
+; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %innerH.epil, label %exit.epilog-lcssa, !llvm.loop !11
 ; EPILOG:       exit.epilog-lcssa:
 ; EPILOG-NEXT:    br label %exit
 ; EPILOG:       exit.loopexit:
 ; EPILOG-NEXT:    br label %exit
 ; EPILOG:       exit:
 ; EPILOG-NEXT:    ret void
 ;
 ; EPILOG-BLOCK-LABEL: @test8(

 ; PROLOG-NEXT:    %i3.prol = phi i64 [ %i4.prol, %latch.prol ], [ %i, %innerH.prol.preheader ]
 ; PROLOG-NEXT:    %prol.iter = phi i64 [ 0, %innerH.prol.preheader ], [ %prol.iter.next, %latch.prol ]
 ; PROLOG-NEXT:    %i4.prol = add nuw nsw i64 %i3.prol, 1
 ; PROLOG-NEXT:    br i1 false, label %outerloop.loopexit.loopexit1, label %latch.prol
 ; PROLOG:       latch.prol:
 ; PROLOG-NEXT:    %i6.prol = icmp ult i64 %i4.prol, 100
 ; PROLOG-NEXT:    %prol.iter.next = add i64 %prol.iter, 1
 ; PROLOG-NEXT:    %prol.iter.cmp = icmp ne i64 %prol.iter.next, %xtraiter
-; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %innerH.prol, label %innerH.prol.loopexit.unr-lcssa, !llvm.loop !12
+; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %innerH.prol, label %innerH.prol.loopexit.unr-lcssa, !llvm.loop !11
 ; PROLOG:       innerH.prol.loopexit.unr-lcssa:
 ; PROLOG-NEXT:    %i3.unr.ph = phi i64 [ %i4.prol, %latch.prol ]
 ; PROLOG-NEXT:    br label %innerH.prol.loopexit
 ; PROLOG:       innerH.prol.loopexit:
 ; PROLOG-NEXT:    %i3.unr = phi i64 [ %i, %outerloop ], [ %i3.unr.ph, %innerH.prol.loopexit.unr-lcssa ]
 ; PROLOG-NEXT:    %2 = icmp ult i64 %1, 7
 ; PROLOG-NEXT:    br i1 %2, label %exit.loopexit, label %outerloop.new
 ; PROLOG:       outerloop.new:

 ; EPILOG-NEXT:    %i7.epil = trunc i64 %phi.epil to i32
 ; EPILOG-NEXT:    br i1 true, label %latch.epil, label %innerexit.loopexit1
 ; EPILOG:       latch.epil:
 ; EPILOG-NEXT:    %i11.epil = add nsw i32 %i7.epil, 1
 ; EPILOG-NEXT:    %innercnd.epil = icmp slt i32 %i11.epil, %trip
 ; EPILOG-NEXT:    %iv.next.epil = add nuw nsw i64 %phi.epil, 1
 ; EPILOG-NEXT:    %epil.iter.next = add i32 %epil.iter, 1
 ; EPILOG-NEXT:    %epil.iter.cmp = icmp ne i32 %epil.iter.next, %xtraiter
-; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %header.epil, label %outerLatch.loopexit.epilog-lcssa, !llvm.loop !13
+; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %header.epil, label %outerLatch.loopexit.epilog-lcssa, !llvm.loop !12
 ; EPILOG:       outerLatch.loopexit.epilog-lcssa:
 ; EPILOG-NEXT:    br label %outerLatch.loopexit
 ; EPILOG:       outerLatch.loopexit:
 ; EPILOG-NEXT:    br label %outerLatch
 ; EPILOG:       outerLatch:
 ; EPILOG-NEXT:    br label %outerloopHdr
 ;
 ; EPILOG-BLOCK-LABEL: @test9(

 ; PROLOG-NEXT:    %i7.prol = trunc i64 %phi.prol to i32
 ; PROLOG-NEXT:    br i1 true, label %latch.prol, label %innerexit.loopexit1
 ; PROLOG:       latch.prol:
 ; PROLOG-NEXT:    %i11.prol = add nsw i32 %i7.prol, 1
 ; PROLOG-NEXT:    %innercnd.prol = icmp slt i32 %i11.prol, %trip
 ; PROLOG-NEXT:    %iv.next.prol = add nuw nsw i64 %phi.prol, 1
 ; PROLOG-NEXT:    %prol.iter.next = add i32 %prol.iter, 1
 ; PROLOG-NEXT:    %prol.iter.cmp = icmp ne i32 %prol.iter.next, %xtraiter
-; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %header.prol, label %header.prol.loopexit.unr-lcssa, !llvm.loop !13
+; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %header.prol, label %header.prol.loopexit.unr-lcssa, !llvm.loop !12
 ; PROLOG:       header.prol.loopexit.unr-lcssa:
 ; PROLOG-NEXT:    %phi.unr.ph = phi i64 [ %iv.next.prol, %latch.prol ]
 ; PROLOG-NEXT:    br label %header.prol.loopexit
 ; PROLOG:       header.prol.loopexit:
 ; PROLOG-NEXT:    %phi.unr = phi i64 [ %i4, %preheader ], [ %phi.unr.ph, %header.prol.loopexit.unr-lcssa ]
 ; PROLOG-NEXT:    %3 = icmp ult i32 %2, 7
 ; PROLOG-NEXT:    br i1 %3, label %outerLatch.loopexit, label %preheader.new
 ; PROLOG:       preheader.new:

 ; EPILOG-NEXT:    call void @bar()
 ; EPILOG-NEXT:    %cmp_early.epil = icmp ne i64 %iv.epil, %trip2
 ; EPILOG-NEXT:    br i1 %cmp_early.epil, label %loop_latch.epil, label %exit1.loopexit1
 ; EPILOG:       loop_latch.epil:
 ; EPILOG-NEXT:    %iv_next.epil = add i64 %iv.epil, 1
 ; EPILOG-NEXT:    %cmp.epil = icmp ne i64 %iv_next.epil, %trip
 ; EPILOG-NEXT:    %epil.iter.next = add i64 %epil.iter, 1
 ; EPILOG-NEXT:    %epil.iter.cmp = icmp ne i64 %epil.iter.next, %xtraiter
-; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %loop_header.epil, label %exit2.epilog-lcssa, !llvm.loop !14
+; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %loop_header.epil, label %exit2.epilog-lcssa, !llvm.loop !13
 ; EPILOG:       exit2.epilog-lcssa:
 ; EPILOG-NEXT:    br label %exit2
 ; EPILOG:       exit2:
 ; EPILOG-NEXT:    ret void
 ;
 ; EPILOG-BLOCK-LABEL: @test10(
 ; EPILOG-BLOCK-NEXT:  entry:
 ; EPILOG-BLOCK-NEXT:    %0 = freeze i64 %trip

 ; PROLOG-NEXT:    call void @bar()
 ; PROLOG-NEXT:    %cmp_early.prol = icmp ne i64 %iv.prol, %trip2
 ; PROLOG-NEXT:    br i1 %cmp_early.prol, label %loop_latch.prol, label %exit1.loopexit1
 ; PROLOG:       loop_latch.prol:
 ; PROLOG-NEXT:    %iv_next.prol = add i64 %iv.prol, 1
 ; PROLOG-NEXT:    %cmp.prol = icmp ne i64 %iv_next.prol, %trip
 ; PROLOG-NEXT:    %prol.iter.next = add i64 %prol.iter, 1
 ; PROLOG-NEXT:    %prol.iter.cmp = icmp ne i64 %prol.iter.next, %xtraiter
-; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %loop_header.prol, label %loop_header.prol.loopexit.unr-lcssa, !llvm.loop !14
+; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %loop_header.prol, label %loop_header.prol.loopexit.unr-lcssa, !llvm.loop !13
 ; PROLOG:       loop_header.prol.loopexit.unr-lcssa:
 ; PROLOG-NEXT:    %iv.unr.ph = phi i64 [ %iv_next.prol, %loop_latch.prol ]
 ; PROLOG-NEXT:    br label %loop_header.prol.loopexit
 ; PROLOG:       loop_header.prol.loopexit:
 ; PROLOG-NEXT:    %iv.unr = phi i64 [ 0, %entry ], [ %iv.unr.ph, %loop_header.prol.loopexit.unr-lcssa ]
 ; PROLOG-NEXT:    %2 = icmp ult i64 %1, 7
 ; PROLOG-NEXT:    br i1 %2, label %exit2, label %entry.new
 ; PROLOG:       entry.new:

 ; EPILOG-NEXT:    %epil.iter = phi i64 [ 0, %loop_header.epil.preheader ], [ %epil.iter.next, %loop_latch.epil ]
 ; EPILOG-NEXT:    call void @bar()
 ; EPILOG-NEXT:    br i1 %cond, label %loop_latch.epil, label %exit1.loopexit1
 ; EPILOG:       loop_latch.epil:
 ; EPILOG-NEXT:    %iv_next.epil = add i64 %iv.epil, 1
 ; EPILOG-NEXT:    %cmp.epil = icmp ne i64 %iv_next.epil, %trip
 ; EPILOG-NEXT:    %epil.iter.next = add i64 %epil.iter, 1
 ; EPILOG-NEXT:    %epil.iter.cmp = icmp ne i64 %epil.iter.next, %xtraiter
-; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %loop_header.epil, label %exit2.epilog-lcssa, !llvm.loop !15
+; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %loop_header.epil, label %exit2.epilog-lcssa, !llvm.loop !14
 ; EPILOG:       exit2.epilog-lcssa:
 ; EPILOG-NEXT:    br label %exit2
 ; EPILOG:       exit2:
 ; EPILOG-NEXT:    ret void
 ;
 ; EPILOG-BLOCK-LABEL: @test11(
 ; EPILOG-BLOCK-NEXT:  entry:
 ; EPILOG-BLOCK-NEXT:    %0 = freeze i64 %trip

 ; PROLOG-NEXT:    %prol.iter = phi i64 [ 0, %loop_header.prol.preheader ], [ %prol.iter.next, %loop_latch.prol ]
 ; PROLOG-NEXT:    call void @bar()
 ; PROLOG-NEXT:    br i1 %cond, label %loop_latch.prol, label %exit1.loopexit1
 ; PROLOG:       loop_latch.prol:
 ; PROLOG-NEXT:    %iv_next.prol = add i64 %iv.prol, 1
 ; PROLOG-NEXT:    %cmp.prol = icmp ne i64 %iv_next.prol, %trip
 ; PROLOG-NEXT:    %prol.iter.next = add i64 %prol.iter, 1
 ; PROLOG-NEXT:    %prol.iter.cmp = icmp ne i64 %prol.iter.next, %xtraiter
-; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %loop_header.prol, label %loop_header.prol.loopexit.unr-lcssa, !llvm.loop !15
+; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %loop_header.prol, label %loop_header.prol.loopexit.unr-lcssa, !llvm.loop !14
 ; PROLOG:       loop_header.prol.loopexit.unr-lcssa:
 ; PROLOG-NEXT:    %iv.unr.ph = phi i64 [ %iv_next.prol, %loop_latch.prol ]
 ; PROLOG-NEXT:    br label %loop_header.prol.loopexit
 ; PROLOG:       loop_header.prol.loopexit:
 ; PROLOG-NEXT:    %iv.unr = phi i64 [ 0, %entry ], [ %iv.unr.ph, %loop_header.prol.loopexit.unr-lcssa ]
 ; PROLOG-NEXT:    %2 = icmp ult i64 %1, 7
 ; PROLOG-NEXT:    br i1 %2, label %exit2, label %entry.new
 ; PROLOG:       entry.new:

 ; EPILOG-NEXT:    br i1 %cmp_early.epil, label %loop_exiting_bb2.epil, label %exit1.epilog-lcssa.loopexit1
 ; EPILOG:       loop_exiting_bb2.epil:
 ; EPILOG-NEXT:    br i1 %cond, label %loop_latch.epil, label %exit1.epilog-lcssa.loopexit1
 ; EPILOG:       loop_latch.epil:
 ; EPILOG-NEXT:    %iv_next.epil = add i64 %iv.epil, 1
 ; EPILOG-NEXT:    %cmp.epil = icmp ne i64 %iv_next.epil, %trip
 ; EPILOG-NEXT:    %epil.iter.next = add i64 %epil.iter, 1
 ; EPILOG-NEXT:    %epil.iter.cmp = icmp ne i64 %epil.iter.next, %xtraiter
-; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %loop_header.epil, label %exit1.epilog-lcssa.loopexit1, !llvm.loop !16
+; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %loop_header.epil, label %exit1.epilog-lcssa.loopexit1, !llvm.loop !15
 ; EPILOG:       exit1.epilog-lcssa.loopexit:
 ; EPILOG-NEXT:    br label %exit1.epilog-lcssa
 ; EPILOG:       exit1.epilog-lcssa.loopexit1:
 ; EPILOG-NEXT:    br label %exit1.epilog-lcssa
 ; EPILOG:       exit1.epilog-lcssa:
 ; EPILOG-NEXT:    br label %exit1
 ; EPILOG:       exit1:
 ; EPILOG-NEXT:    ret void

 ; PROLOG-NEXT:    br i1 %cmp_early.prol, label %loop_exiting_bb2.prol, label %exit1.unr-lcssa.loopexit1
 ; PROLOG:       loop_exiting_bb2.prol:
 ; PROLOG-NEXT:    br i1 %cond, label %loop_latch.prol, label %exit1.unr-lcssa.loopexit1
 ; PROLOG:       loop_latch.prol:
 ; PROLOG-NEXT:    %iv_next.prol = add i64 %iv.prol, 1
 ; PROLOG-NEXT:    %cmp.prol = icmp ne i64 %iv_next.prol, %trip
 ; PROLOG-NEXT:    %prol.iter.next = add i64 %prol.iter, 1
 ; PROLOG-NEXT:    %prol.iter.cmp = icmp ne i64 %prol.iter.next, %xtraiter
-; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %loop_header.prol, label %loop_header.prol.loopexit.unr-lcssa, !llvm.loop !16
+; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %loop_header.prol, label %loop_header.prol.loopexit.unr-lcssa, !llvm.loop !15
 ; PROLOG:       loop_header.prol.loopexit.unr-lcssa:
 ; PROLOG-NEXT:    %iv.unr.ph = phi i64 [ %iv_next.prol, %loop_latch.prol ]
 ; PROLOG-NEXT:    br label %loop_header.prol.loopexit
 ; PROLOG:       loop_header.prol.loopexit:
 ; PROLOG-NEXT:    %iv.unr = phi i64 [ 0, %entry ], [ %iv.unr.ph, %loop_header.prol.loopexit.unr-lcssa ]
 ; PROLOG-NEXT:    %2 = icmp ult i64 %1, 7
 ; PROLOG-NEXT:    br i1 %2, label %exit1, label %entry.new
 ; PROLOG:       entry.new:

 ; EPILOG:       loop_exiting_bb2.epil:
 ; EPILOG-NEXT:    %unknown.epil = call i1 @unknown_cond()
 ; EPILOG-NEXT:    br i1 %unknown.epil, label %loop_latch.epil, label %exit1.epilog-lcssa.loopexit1
 ; EPILOG:       loop_latch.epil:
 ; EPILOG-NEXT:    %iv_next.epil = add i64 %iv.epil, 1
 ; EPILOG-NEXT:    %cmp.epil = icmp ne i64 %iv_next.epil, %trip
 ; EPILOG-NEXT:    %epil.iter.next = add i64 %epil.iter, 1
 ; EPILOG-NEXT:    %epil.iter.cmp = icmp ne i64 %epil.iter.next, %xtraiter
-; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %loop_header.epil, label %exit1.epilog-lcssa.loopexit1, !llvm.loop !17
+; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %loop_header.epil, label %exit1.epilog-lcssa.loopexit1, !llvm.loop !16
 ; EPILOG:       exit1.epilog-lcssa.loopexit:
 ; EPILOG-NEXT:    br label %exit1.epilog-lcssa
 ; EPILOG:       exit1.epilog-lcssa.loopexit1:
 ; EPILOG-NEXT:    br label %exit1.epilog-lcssa
 ; EPILOG:       exit1.epilog-lcssa:
 ; EPILOG-NEXT:    br label %exit1
 ; EPILOG:       exit1:
 ; EPILOG-NEXT:    ret void

 ; PROLOG:       loop_exiting_bb2.prol:
 ; PROLOG-NEXT:    %unknown.prol = call i1 @unknown_cond()
 ; PROLOG-NEXT:    br i1 %unknown.prol, label %loop_latch.prol, label %exit1.unr-lcssa.loopexit1
 ; PROLOG:       loop_latch.prol:
 ; PROLOG-NEXT:    %iv_next.prol = add i64 %iv.prol, 1
 ; PROLOG-NEXT:    %cmp.prol = icmp ne i64 %iv_next.prol, %trip
 ; PROLOG-NEXT:    %prol.iter.next = add i64 %prol.iter, 1
 ; PROLOG-NEXT:    %prol.iter.cmp = icmp ne i64 %prol.iter.next, %xtraiter
-; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %loop_header.prol, label %loop_header.prol.loopexit.unr-lcssa, !llvm.loop !17
+; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %loop_header.prol, label %loop_header.prol.loopexit.unr-lcssa, !llvm.loop !16
 ; PROLOG:       loop_header.prol.loopexit.unr-lcssa:
 ; PROLOG-NEXT:    %iv.unr.ph = phi i64 [ %iv_next.prol, %loop_latch.prol ]
 ; PROLOG-NEXT:    br label %loop_header.prol.loopexit
 ; PROLOG:       loop_header.prol.loopexit:
 ; PROLOG-NEXT:    %iv.unr = phi i64 [ 0, %entry ], [ %iv.unr.ph, %loop_header.prol.loopexit.unr-lcssa ]
 ; PROLOG-NEXT:    %2 = icmp ult i64 %1, 7
 ; PROLOG-NEXT:    br i1 %2, label %exit1, label %entry.new
 ; PROLOG:       entry.new:

 ; EPILOG:       loop_exiting_bb2.epil:
 ; EPILOG-NEXT:    %unknown.epil = call i1 @unknown_cond()
 ; EPILOG-NEXT:    br i1 %unknown.epil, label %loop_latch.epil, label %exit1.epilog-lcssa.loopexit1
 ; EPILOG:       loop_latch.epil:
 ; EPILOG-NEXT:    %iv_next.epil = add i64 %iv.epil, 1
 ; EPILOG-NEXT:    %cmp.epil = icmp ne i64 %iv_next.epil, %trip
 ; EPILOG-NEXT:    %epil.iter.next = add i64 %epil.iter, 1
 ; EPILOG-NEXT:    %epil.iter.cmp = icmp ne i64 %epil.iter.next, %xtraiter
-; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %loop_header.epil, label %exit1.epilog-lcssa.loopexit1, !llvm.loop !18
+; EPILOG-NEXT:    br i1 %epil.iter.cmp, label %loop_header.epil, label %exit1.epilog-lcssa.loopexit1, !llvm.loop !17
 ; EPILOG:       exit1.epilog-lcssa.loopexit:
 ; EPILOG-NEXT:    br label %exit1.epilog-lcssa
 ; EPILOG:       exit1.epilog-lcssa.loopexit1:
 ; EPILOG-NEXT:    br label %exit1.epilog-lcssa
 ; EPILOG:       exit1.epilog-lcssa:
 ; EPILOG-NEXT:    br label %exit1
 ; EPILOG:       exit1:
 ; EPILOG-NEXT:    ret void

 ; PROLOG:       loop_exiting_bb2.prol:
 ; PROLOG-NEXT:    %unknown.prol = call i1 @unknown_cond()
 ; PROLOG-NEXT:    br i1 %unknown.prol, label %loop_latch.prol, label %exit1.unr-lcssa.loopexit1
 ; PROLOG:       loop_latch.prol:
 ; PROLOG-NEXT:    %iv_next.prol = add i64 %iv.prol, 1
 ; PROLOG-NEXT:    %cmp.prol = icmp ne i64 %iv_next.prol, %trip
 ; PROLOG-NEXT:    %prol.iter.next = add i64 %prol.iter, 1
 ; PROLOG-NEXT:    %prol.iter.cmp = icmp ne i64 %prol.iter.next, %xtraiter
-; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %loop_header.prol, label %loop_header.prol.loopexit.unr-lcssa, !llvm.loop !18
+; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %loop_header.prol, label %loop_header.prol.loopexit.unr-lcssa, !llvm.loop !17
 ; PROLOG:       loop_header.prol.loopexit.unr-lcssa:
 ; PROLOG-NEXT:    %iv.unr.ph = phi i64 [ %iv_next.prol, %loop_latch.prol ]
 ; PROLOG-NEXT:    br label %loop_header.prol.loopexit
 ; PROLOG:       loop_header.prol.loopexit:
 ; PROLOG-NEXT:    %iv.unr = phi i64 [ 0, %entry ], [ %iv.unr.ph, %loop_header.prol.loopexit.unr-lcssa ]
 ; PROLOG-NEXT:    %2 = icmp ult i64 %1, 7
 ; PROLOG-NEXT:    br i1 %2, label %exit1, label %entry.new
 ; PROLOG:       entry.new:

llvm/test/Transforms/LoopUnroll/scevunroll.ll

 ; iteration via the early exit. So loop unrolling cannot assume that
 ; the loop latch's exit count of zero is an upper bound on the number
 ; of iterations.
 define void @nsw_latch(i32* %a) nounwind {
 ; CHECK-LABEL: @nsw_latch(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    br label [[FOR_COND:%.*]]
-; CHECK:       for.cond:
-; CHECK-NEXT:    br i1 false, label [[RETURN:%.*]], label [[FOR_BODY_1:%.*]]
-; CHECK:       for.body.1:
-; CHECK-NEXT:    br i1 false, label [[FOR_COND_1:%.*]], label [[RETURN]]
-; CHECK:       for.cond.1:
-; CHECK-NEXT:    br label [[RETURN]]
+; CHECK-NEXT:    [[B_03:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 [[B_03]], 0
+; CHECK-NEXT:    [[ADD]] = add nuw nsw i32 [[B_03]], 8
+; CHECK-NEXT:    [[RETVAL_0_SEL:%.*]] = select i1 [[TOBOOL]], i32 0, i32 1
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[TOBOOL]], i1 true, i1 false
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[RETURN:%.*]], label [[FOR_BODY]]
 ; CHECK:       return:
-; CHECK-NEXT:    [[B_03_LCSSA:%.*]] = phi i32 [ 0, [[FOR_COND]] ], [ 8, [[FOR_BODY_1]] ], [ 0, [[FOR_COND_1]] ]
-; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ 0, [[FOR_COND]] ], [ 1, [[FOR_BODY_1]] ], [ 0, [[FOR_COND_1]] ]
+; CHECK-NEXT:    [[B_03_LCSSA:%.*]] = phi i32 [ [[B_03]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    store i32 [[B_03_LCSSA]], i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.cond, %entry
   %b.03 = phi i32 [ 0, %entry ], [ %add, %for.cond ]

llvm/test/Transforms/LoopUnroll/unroll-after-peel.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=loop-unroll -S | FileCheck %s
 
 define i64 @hoge(i1 %c) {
 ; CHECK-LABEL: @hoge(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    br label [[BB1_PEEL_BEGIN:%.*]]
 ; CHECK:       bb1.peel.begin:
 ; CHECK-NEXT:    br label [[BB1_PEEL:%.*]]
 ; CHECK:       bb1.peel:
-; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB2_PEEL:%.*]], label [[BB4:%.*]]
-; CHECK:       bb2.peel:
 ; CHECK-NEXT:    [[TMP3_PEEL:%.*]] = icmp slt i32 0, 9
-; CHECK-NEXT:    br i1 [[TMP3_PEEL]], label [[BB1_PEEL_NEXT:%.*]], label [[BB4]]
+; CHECK-NEXT:    [[TMP5_SEL_PEEL:%.*]] = select i1 [[C:%.*]], i32 8, i32 0
+; CHECK-NEXT:    [[OR_COND_PEEL:%.*]] = and i1 [[C]], [[TMP3_PEEL]]
+; CHECK-NEXT:    br i1 [[OR_COND_PEEL]], label [[BB1_PEEL_NEXT:%.*]], label [[BB4:%.*]]
 ; CHECK:       bb1.peel.next:
 ; CHECK-NEXT:    br label [[BB1_PEEL_NEXT1:%.*]]
 ; CHECK:       bb1.peel.next1:
 ; CHECK-NEXT:    br label [[BB_PEEL_NEWPH:%.*]]
 ; CHECK:       bb.peel.newph:
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br i1 [[C]], label [[BB1]], label [[BB4_LOOPEXIT:%.*]], !llvm.loop [[LOOP0:![0-9]+]]
 ; CHECK:       bb4.loopexit:
-; CHECK-NEXT:    [[TMP5_PH:%.*]] = phi i32 [ 8, [[BB1]] ]
 ; CHECK-NEXT:    br label [[BB4]]
 ; CHECK:       bb4:
-; CHECK-NEXT:    [[TMP5:%.*]] = phi i32 [ 0, [[BB1_PEEL]] ], [ 8, [[BB2_PEEL]] ], [ [[TMP5_PH]], [[BB4_LOOPEXIT]] ]
 ; CHECK-NEXT:    [[TMP6:%.*]] = call i64 (...) @llvm.experimental.deoptimize.i64(i32 10) [ "deopt"() ]
 ; CHECK-NEXT:    ret i64 [[TMP6]]
 ;
 bb:
   br label %bb1
 
 bb1:                                              ; preds = %bb2, %bb
   %tmp = phi i32 [ 8, %bb2 ], [ 0, %bb ]

llvm/test/Transforms/LoopUnroll/unroll-header-exiting-with-phis-multiple-exiting-blocks.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -loop-unroll -S %s | FileCheck %s
 
 ; Loop with multiple exiting blocks, where the header exits but not the latch,
 ; e.g. because it has not been rotated.
 define i16 @full_unroll_multiple_exiting_blocks(i16* %A, i16 %x, i16 %y) {
 ; CHECK-LABEL: @full_unroll_multiple_exiting_blocks(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[LV:%.*]] = load i16, i16* [[A:%.*]], align 2
-; CHECK-NEXT:    [[RES_NEXT:%.*]] = add i16 123, [[LV]]
-; CHECK-NEXT:    br label [[EXITING_1:%.*]]
-; CHECK:       exiting.1:
+; CHECK-NEXT:    [[RES:%.*]] = phi i16 [ 123, [[ENTRY:%.*]] ], [ [[RES_NEXT:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    [[I_0:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[INC9:%.*]], [[LATCH]] ]
+; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds i16, i16* [[A:%.*]], i64 [[I_0]]
+; CHECK-NEXT:    [[LV:%.*]] = load i16, i16* [[PTR]], align 2
+; CHECK-NEXT:    [[RES_NEXT]] = add i16 [[RES]], [[LV]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i64 [[I_0]], 3
 ; CHECK-NEXT:    [[EC_1:%.*]] = icmp eq i16 [[LV]], [[X:%.*]]
-; CHECK-NEXT:    br i1 [[EC_1]], label [[EXIT:%.*]], label [[EXITING_2:%.*]]
-; CHECK:       exiting.2:
+; CHECK-NEXT:    [[RES_LCSSA_SEL:%.*]] = select i1 [[CMP]], i16 0, i16 [[RES_NEXT]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP]], i1 true, i1 [[EC_1]]
 ; CHECK-NEXT:    [[EC_2:%.*]] = icmp eq i16 [[LV]], [[Y:%.*]]
-; CHECK-NEXT:    br i1 [[EC_2]], label [[EXIT]], label [[LATCH:%.*]]
+; CHECK-NEXT:    [[RES_LCSSA_SEL1:%.*]] = select i1 [[OR_COND]], i16 1, i16 [[RES_LCSSA_SEL]]
+; CHECK-NEXT:    [[OR_COND2:%.*]] = select i1 [[OR_COND]], i1 true, i1 [[EC_2]]
+; CHECK-NEXT:    br i1 [[OR_COND2]], label [[EXIT:%.*]], label [[LATCH]]
 ; CHECK:       latch:
-; CHECK-NEXT:    [[PTR_1:%.*]] = getelementptr inbounds i16, i16* [[A]], i64 1
-; CHECK-NEXT:    [[LV_1:%.*]] = load i16, i16* [[PTR_1]], align 2
-; CHECK-NEXT:    [[RES_NEXT_1:%.*]] = add i16 [[RES_NEXT]], [[LV_1]]
-; CHECK-NEXT:    br label [[EXITING_1_1:%.*]]
-; CHECK:       exiting.1.1:
-; CHECK-NEXT:    [[EC_1_1:%.*]] = icmp eq i16 [[LV_1]], [[X]]
-; CHECK-NEXT:    br i1 [[EC_1_1]], label [[EXIT]], label [[EXITING_2_1:%.*]]
-; CHECK:       exiting.2.1:
-; CHECK-NEXT:    [[EC_2_1:%.*]] = icmp eq i16 [[LV_1]], [[Y]]
-; CHECK-NEXT:    br i1 [[EC_2_1]], label [[EXIT]], label [[LATCH_1:%.*]]
-; CHECK:       latch.1:
-; CHECK-NEXT:    [[PTR_2:%.*]] = getelementptr inbounds i16, i16* [[A]], i64 2
-; CHECK-NEXT:    [[LV_2:%.*]] = load i16, i16* [[PTR_2]], align 2
-; CHECK-NEXT:    [[RES_NEXT_2:%.*]] = add i16 [[RES_NEXT_1]], [[LV_2]]
-; CHECK-NEXT:    br label [[EXITING_1_2:%.*]]
-; CHECK:       exiting.1.2:
-; CHECK-NEXT:    [[EC_1_2:%.*]] = icmp eq i16 [[LV_2]], [[X]]
-; CHECK-NEXT:    br i1 [[EC_1_2]], label [[EXIT]], label [[EXITING_2_2:%.*]]
-; CHECK:       exiting.2.2:
-; CHECK-NEXT:    [[EC_2_2:%.*]] = icmp eq i16 [[LV_2]], [[Y]]
-; CHECK-NEXT:    br i1 [[EC_2_2]], label [[EXIT]], label [[LATCH_2:%.*]]
-; CHECK:       latch.2:
-; CHECK-NEXT:    [[PTR_3:%.*]] = getelementptr inbounds i16, i16* [[A]], i64 3
-; CHECK-NEXT:    [[LV_3:%.*]] = load i16, i16* [[PTR_3]], align 2
-; CHECK-NEXT:    [[RES_NEXT_3:%.*]] = add i16 [[RES_NEXT_2]], [[LV_3]]
-; CHECK-NEXT:    br i1 false, label [[EXITING_1_3:%.*]], label [[EXIT]]
-; CHECK:       exiting.1.3:
-; CHECK-NEXT:    [[EC_1_3:%.*]] = icmp eq i16 [[LV_3]], [[X]]
-; CHECK-NEXT:    br i1 [[EC_1_3]], label [[EXIT]], label [[EXITING_2_3:%.*]]
-; CHECK:       exiting.2.3:
-; CHECK-NEXT:    [[EC_2_3:%.*]] = icmp eq i16 [[LV_3]], [[Y]]
-; CHECK-NEXT:    br i1 [[EC_2_3]], label [[EXIT]], label [[LATCH_3:%.*]]
-; CHECK:       latch.3:
-; CHECK-NEXT:    unreachable
+; CHECK-NEXT:    [[INC9]] = add i64 [[I_0]], 1
+; CHECK-NEXT:    br label [[HEADER]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES_LCSSA:%.*]] = phi i16 [ 0, [[EXITING_1]] ], [ 1, [[EXITING_2]] ], [ 0, [[EXITING_1_1]] ], [ 1, [[EXITING_2_1]] ], [ 0, [[EXITING_1_2]] ], [ 1, [[EXITING_2_2]] ], [ [[RES_NEXT_3]], [[LATCH_2]] ], [ 0, [[EXITING_1_3]] ], [ 1, [[EXITING_2_3]] ]
-; CHECK-NEXT:    ret i16 [[RES_LCSSA]]
+; CHECK-NEXT:    [[RES_LCSSA_SEL1_LCSSA:%.*]] = phi i16 [ [[RES_LCSSA_SEL1]], [[HEADER]] ]
+; CHECK-NEXT:    ret i16 [[RES_LCSSA_SEL1_LCSSA]]
 ;
 entry:
   br label %header
 
 header:
   %res = phi i16 [ 123, %entry ], [ %res.next, %latch ]
   %i.0 = phi i64 [ 0, %entry ], [ %inc9, %latch ]
   %ptr = getelementptr inbounds i16, i16* %A, i64 %i.0

llvm/test/Transforms/SimplifyCFG/2008-07-13-InfLoopMiscompile.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s
 ; PR2540
 ; Outval should end up with a select from 0/2, not all constants.
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32"
 target triple = "i386-pc-linux-gnu"
 @g_37 = common global i32 0   ; <i32*> [#uses=1]
 @.str = internal constant [4 x i8] c"%d\0A\00"    ; <[4 x i8]*> [#uses=1]
 
 define i32 @main() nounwind  {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[L:%.*]] = load i32, i32* @g_37, align 4
 ; CHECK-NEXT:    [[CMPA:%.*]] = icmp ne i32 [[L]], 0
-; CHECK-NEXT:    br i1 [[CMPA]], label [[FUNC_1_EXIT:%.*]], label [[MOOSEBLOCK:%.*]]
-; CHECK:       mooseblock:
 ; CHECK-NEXT:    [[CMPB:%.*]] = icmp eq i1 [[CMPA]], false
-; CHECK-NEXT:    [[BRMERGE:%.*]] = or i1 [[CMPB]], [[CMPA]]
-; CHECK-NEXT:    [[DOTMUX:%.*]] = select i1 [[CMPB]], i32 0, i32 2
-; CHECK-NEXT:    br i1 [[BRMERGE]], label [[FUNC_1_EXIT]], label [[INFLOOP:%.*]]
+; CHECK-NEXT:    [[OUTVAL_SEL:%.*]] = select i1 [[CMPA]], i32 0, i32 1
+; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[CMPA]], [[CMPB]]
+; CHECK-NEXT:    [[BRMERGE:%.*]] = or i1 [[OR_COND]], [[CMPA]]
+; CHECK-NEXT:    [[OUTVAL_SEL_MUX:%.*]] = select i1 [[OR_COND]], i32 [[OUTVAL_SEL]], i32 2
+; CHECK-NEXT:    br i1 [[BRMERGE]], label [[FUNC_1_EXIT:%.*]], label [[INFLOOP:%.*]]
 ; CHECK:       func_1.exit:
-; CHECK-NEXT:    [[OUTVAL:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ [[DOTMUX]], [[MOOSEBLOCK]] ]
-; CHECK-NEXT:    [[POUT:%.*]] = tail call i32 (i8*, ...) @printf(i8* noalias getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0), i32 [[OUTVAL]]) #[[ATTR0:[0-9]+]]
+; CHECK-NEXT:    [[POUT:%.*]] = tail call i32 (i8*, ...) @printf(i8* noalias getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0), i32 [[OUTVAL_SEL_MUX]]) #[[ATTR0:[0-9]+]]
 ; CHECK-NEXT:    ret i32 0
 ; CHECK:       infloop:
 ; CHECK-NEXT:    br label [[INFLOOP]]
 ;
 entry:
   %l = load i32, i32* @g_37, align 4    ; <i32> [#uses=1]
   %cmpa = icmp ne i32 %l, 0    ; <i1> [#uses=3]
   br i1 %cmpa, label %func_1.exit, label %mooseblock

llvm/test/Transforms/SimplifyCFG/X86/SpeculativeExec.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -phi-node-folding-threshold=2 -S | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define i32 @test1(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[T1:%.*]] = icmp eq i32 [[B:%.*]], 0
 ; CHECK-NEXT:    [[T2:%.*]] = icmp sgt i32 [[C:%.*]], 1
-; CHECK-NEXT:    [[T3:%.*]] = add i32 [[A:%.*]], 1
-; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[T2]], i32 [[T3]], i32 [[A]]
-; CHECK-NEXT:    [[T4:%.*]] = select i1 [[T1]], i32 [[SPEC_SELECT]], i32 [[B]]
+; CHECK-NEXT:    [[T4_SEL:%.*]] = select i1 [[T1]], i32 [[A:%.*]], i32 [[B]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[T1]], i1 [[T2]], i1 false
+; CHECK-NEXT:    [[T3:%.*]] = add i32 [[A]], 1
+; CHECK-NEXT:    [[T4:%.*]] = select i1 [[OR_COND]], i32 [[T3]], i32 [[T4_SEL]]
 ; CHECK-NEXT:    [[T5:%.*]] = sub i32 [[T4]], 1
 ; CHECK-NEXT:    ret i32 [[T5]]
 ;
 entry:
   %t1 = icmp eq i32 %b, 0
   br i1 %t1, label %bb1, label %bb3
 
 bb1:
bb3:
   %t5 = sub i32 %t4, 1
   ret i32 %t5
 }
 
 define float @spec_select_fp1(float %a, float %b, float %c) {
 ; CHECK-LABEL: @spec_select_fp1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[T1:%.*]] = fcmp oeq float [[B:%.*]], 0.000000e+00
-; CHECK-NEXT:    br i1 [[T1]], label [[BB1:%.*]], label [[BB3:%.*]]
-; CHECK:       bb1:
 ; CHECK-NEXT:    [[T2:%.*]] = fcmp ogt float [[C:%.*]], 1.000000e+00
-; CHECK-NEXT:    br i1 [[T2]], label [[BB2:%.*]], label [[BB3]]
-; CHECK:       bb2:
-; CHECK-NEXT:    [[T3:%.*]] = fadd float [[A:%.*]], 1.000000e+00
-; CHECK-NEXT:    br label [[BB3]]
-; CHECK:       bb3:
-; CHECK-NEXT:    [[T4:%.*]] = phi ninf float [ [[B]], [[ENTRY:%.*]] ], [ [[A]], [[BB1]] ], [ [[T3]], [[BB2]] ]
+; CHECK-NEXT:    [[T4_SEL:%.*]] = select i1 [[T1]], float [[A:%.*]], float [[B]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[T1]], i1 [[T2]], i1 false
+; CHECK-NEXT:    [[T3:%.*]] = fadd float [[A]], 1.000000e+00
+; CHECK-NEXT:    [[T4:%.*]] = select ninf i1 [[OR_COND]], float [[T3]], float [[T4_SEL]]
 ; CHECK-NEXT:    [[T5:%.*]] = fsub float [[T4]], 1.000000e+00
 ; CHECK-NEXT:    ret float [[T5]]
 ;
 entry:
   %t1 = fcmp oeq float %b, 0.0
   br i1 %t1, label %bb1, label %bb3
 
 bb1:
end:
   ret i8* %x10
 }
 
 define i32* @test5(i32 %a, i32 %b, i32 %c, i32* dereferenceable(10) %ptr1, i32* dereferenceable(10) %ptr2, i32** dereferenceable(10) align 8 %ptr3) nofree nosync {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[T1:%.*]] = icmp eq i32 [[B:%.*]], 0
 ; CHECK-NEXT:    [[T2:%.*]] = icmp sgt i32 [[C:%.*]], 1
+; CHECK-NEXT:    [[T4_SEL:%.*]] = select i1 [[T1]], i32* [[PTR2:%.*]], i32* [[PTR1:%.*]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[T1]], i1 [[T2]], i1 false
 ; CHECK-NEXT:    [[T3:%.*]] = load i32*, i32** [[PTR3:%.*]], align 8
-; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[T2]], i32* [[T3]], i32* [[PTR2:%.*]]
-; CHECK-NEXT:    [[T4:%.*]] = select i1 [[T1]], i32* [[SPEC_SELECT]], i32* [[PTR1:%.*]]
+; CHECK-NEXT:    [[T4:%.*]] = select i1 [[OR_COND]], i32* [[T3]], i32* [[T4_SEL]]
 ; CHECK-NEXT:    ret i32* [[T4]]
 ;
 entry:
   %t1 = icmp eq i32 %b, 0
   br i1 %t1, label %bb1, label %bb3
 
 bb1:
   %t2 = icmp sgt i32 %c, 1
   br i1 %t2, label %bb2, label %bb3
 
 bb2:
   %t3 = load i32*, i32** %ptr3, !dereferenceable !{i64 10}
   br label %bb3
 
 bb3:
   %t4 = phi i32* [ %ptr1, %entry ], [ %ptr2, %bb1 ], [ %t3, %bb2 ]
   ret i32* %t4
 }
 
 define float @spec_select_fp5(float %a, float %b, float %c) {
 ; CHECK-LABEL: @spec_select_fp5(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[T1:%.*]] = fcmp oeq float [[B:%.*]], 0.000000e+00
-; CHECK-NEXT:    br i1 [[T1]], label [[BB1:%.*]], label [[BB3:%.*]]
-; CHECK:       bb1:
 ; CHECK-NEXT:    [[T2:%.*]] = fcmp ogt float [[C:%.*]], 1.000000e+00
-; CHECK-NEXT:    br i1 [[T2]], label [[BB2:%.*]], label [[BB3]]
-; CHECK:       bb2:
-; CHECK-NEXT:    br label [[BB3]]
-; CHECK:       bb3:
-; CHECK-NEXT:    [[T4:%.*]] = phi nsz float [ [[A:%.*]], [[ENTRY:%.*]] ], [ [[B]], [[BB1]] ], [ [[C]], [[BB2]] ]
+; CHECK-NEXT:    [[T4_SEL:%.*]] = select i1 [[T1]], float [[B]], float [[A:%.*]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[T1]], i1 [[T2]], i1 false
+; CHECK-NEXT:    [[T4:%.*]] = select nsz i1 [[OR_COND]], float [[C]], float [[T4_SEL]]
 ; CHECK-NEXT:    ret float [[T4]]
 ;
 entry:
   %t1 = fcmp oeq float %b, 0.0
   br i1 %t1, label %bb1, label %bb3
 
 bb1:
   %t2 = fcmp ogt float %c, 1.0

llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll

 
 ; Cannot reuse the table range compare, because the phi at the switch merge
 ; point is not dominated by the switch.
 define i32 @no_reuse_cmp2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @no_reuse_cmp2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[EC:%.*]] = icmp ne i32 [[Y:%.*]], 0
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 4
+; CHECK-NEXT:    [[R_0_SEL:%.*]] = select i1 [[EC]], i32 0, i32 100
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[EC]], i1 [[TMP0]], i1 false
 ; CHECK-NEXT:    [[SWITCH_OFFSET:%.*]] = add i32 [[X]], 10
-; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[TMP0]], i32 [[SWITCH_OFFSET]], i32 0
-; CHECK-NEXT:    [[R_0:%.*]] = select i1 [[EC]], i32 [[SPEC_SELECT]], i32 100
+; CHECK-NEXT:    [[R_0:%.*]] = select i1 [[OR_COND]], i32 [[SWITCH_OFFSET]], i32 [[R_0_SEL]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[R_0]], 0
 ; CHECK-NEXT:    [[DOTR_0:%.*]] = select i1 [[CMP]], i32 100, i32 [[R_0]]
 ; CHECK-NEXT:    ret i32 [[DOTR_0]]
 ;
 entry:
   %ec = icmp ne i32 %y, 0
   br i1 %ec, label %switch.entry, label %sw.epilog
 switch.entry:

llvm/test/Transforms/SimplifyCFG/fold-branch-to-common-dest-phis.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -S -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -bonus-inst-threshold=1 | FileCheck %s --check-prefixes=ALL
+; RUN: opt < %s -S -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -bonus-inst-threshold=1 | FileCheck %s --check-prefixes=ALL,CHEAP
+; RUN: opt < %s -S -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -bonus-inst-threshold=10 | FileCheck %s --check-prefixes=ALL,COSTLY
 
 declare void @sideeffect0(i8)
 declare void @sideeffect1(i8)
 declare void @sideeffect2(i8)
 declare i8 @gen8() speculatable
 
 define void @incompatible_ivs_of_single_phi(i8 %v0, i8 %v1, i8 %iv.of.final_left.from.dispatch, i8 %iv.of.final_right.from.pred, i8 %iv.of.final_right.from.dispatch) {
 ; ALL-LABEL: @incompatible_ivs_of_single_phi(
 ; ALL-NEXT:  pred:
 ; ALL-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
-; ALL-NEXT:    br i1 [[C0]], label [[DISPATCH:%.*]], label [[FINAL_RIGHT:%.*]]
-; ALL:       dispatch:
 ; ALL-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
-; ALL-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT]]
+; ALL-NEXT:    [[FINAL_RIGHT_PHI_SEL:%.*]] = select i1 [[C0]], i8 [[IV_OF_FINAL_RIGHT_FROM_DISPATCH:%.*]], i8 [[IV_OF_FINAL_RIGHT_FROM_PRED:%.*]]
+; ALL-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
+; ALL-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; ALL:       common.ret:
 ; ALL-NEXT:    ret void
 ; ALL:       final_left:
-; ALL-NEXT:    [[FINAL_LEFT_PHI:%.*]] = phi i8 [ [[IV_OF_FINAL_LEFT_FROM_DISPATCH:%.*]], [[DISPATCH]] ]
-; ALL-NEXT:    call void @sideeffect0(i8 [[FINAL_LEFT_PHI]])
+; ALL-NEXT:    call void @sideeffect0(i8 [[IV_OF_FINAL_LEFT_FROM_DISPATCH:%.*]])
 ; ALL-NEXT:    br label [[COMMON_RET:%.*]]
 ; ALL:       final_right:
-; ALL-NEXT:    [[FINAL_RIGHT_PHI:%.*]] = phi i8 [ [[IV_OF_FINAL_RIGHT_FROM_PRED:%.*]], [[PRED:%.*]] ], [ [[IV_OF_FINAL_RIGHT_FROM_DISPATCH:%.*]], [[DISPATCH]] ]
-; ALL-NEXT:    call void @sideeffect1(i8 [[FINAL_RIGHT_PHI]])
+; ALL-NEXT:    call void @sideeffect1(i8 [[FINAL_RIGHT_PHI_SEL]])
 ; ALL-NEXT:    br label [[COMMON_RET]]
 ;
 pred:
   %c0 = icmp eq i8 %v0, 0
   br i1 %c0, label %dispatch, label %final_right
 dispatch:
   %c1 = icmp eq i8 %v1, 0
   br i1 %c1, label %final_left, label %final_right
 final_left:
   %final_left.phi = phi i8 [ %iv.of.final_left.from.dispatch, %dispatch ]
   call void @sideeffect0(i8 %final_left.phi)
   ret void
 final_right:
   %final_right.phi = phi i8 [ %iv.of.final_right.from.pred, %pred ], [ %iv.of.final_right.from.dispatch, %dispatch ]
   call void @sideeffect1(i8 %final_right.phi)
   ret void
 }
 
 define void @incompatible_ivs_of_single_phi.invert_pred_cond(i8 %v0, i8 %v1, i8 %iv.of.final_left.from.dispatch, i8 %iv.of.final_right.from.pred, i8 %iv.of.final_right.from.dispatch) {
 ; ALL-LABEL: @incompatible_ivs_of_single_phi.invert_pred_cond(
 ; ALL-NEXT:  pred:
-; ALL-NEXT:    [[C0:%.*]] = icmp ne i8 [[V0:%.*]], 0
-; ALL-NEXT:    br i1 [[C0]], label [[FINAL_RIGHT:%.*]], label [[DISPATCH:%.*]]
-; ALL:       dispatch:
+; ALL-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; ALL-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
-; ALL-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT]]
+; ALL-NEXT:    [[FINAL_RIGHT_PHI_SEL:%.*]] = select i1 [[C0]], i8 [[IV_OF_FINAL_RIGHT_FROM_DISPATCH:%.*]], i8 [[IV_OF_FINAL_RIGHT_FROM_PRED:%.*]]
+; ALL-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
+; ALL-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; ALL:       common.ret:
 ; ALL-NEXT:    ret void
 ; ALL:       final_left:
-; ALL-NEXT:    [[FINAL_LEFT_PHI:%.*]] = phi i8 [ [[IV_OF_FINAL_LEFT_FROM_DISPATCH:%.*]], [[DISPATCH]] ]
-; ALL-NEXT:    call void @sideeffect0(i8 [[FINAL_LEFT_PHI]])
+; ALL-NEXT:    call void @sideeffect0(i8 [[IV_OF_FINAL_LEFT_FROM_DISPATCH:%.*]])
 ; ALL-NEXT:    br label [[COMMON_RET:%.*]]
 ; ALL:       final_right:
-; ALL-NEXT:    [[FINAL_RIGHT_PHI:%.*]] = phi i8 [ [[IV_OF_FINAL_RIGHT_FROM_PRED:%.*]], [[PRED:%.*]] ], [ [[IV_OF_FINAL_RIGHT_FROM_DISPATCH:%.*]], [[DISPATCH]] ]
-; ALL-NEXT:    call void @sideeffect1(i8 [[FINAL_RIGHT_PHI]])
+; ALL-NEXT:    call void @sideeffect1(i8 [[FINAL_RIGHT_PHI_SEL]])
 ; ALL-NEXT:    br label [[COMMON_RET]]
 ;
 pred:
   %c0 = icmp ne i8 %v0, 0
   br i1 %c0, label %final_right, label %dispatch
 dispatch:
   %c1 = icmp eq i8 %v1, 0
   br i1 %c1, label %final_left, label %final_right
 final_left:
   %final_left.phi = phi i8 [ %iv.of.final_left.from.dispatch, %dispatch ]
   call void @sideeffect0(i8 %final_left.phi)
   ret void
 final_right:
   %final_right.phi = phi i8 [ %iv.of.final_right.from.pred, %pred ], [ %iv.of.final_right.from.dispatch, %dispatch ]
   call void @sideeffect1(i8 %final_right.phi)
   ret void
 }
 
 define void @incompatible_ivs_of_single_phi.insertpos(i8 %v0, i8 %v1, i8 %iv.of.final_left.from.dispatch) {
-; ALL-LABEL: @incompatible_ivs_of_single_phi.insertpos(
-; ALL-NEXT:  pred:
-; ALL-NEXT:    [[IV_OF_FINAL_RIGHT_FROM_PRED:%.*]] = call i8 @gen8()
-; ALL-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
-; ALL-NEXT:    br i1 [[C0]], label [[DISPATCH:%.*]], label [[FINAL_RIGHT:%.*]]
-; ALL:       dispatch:
-; ALL-NEXT:    [[IV_OF_FINAL_RIGHT_FROM_DISPATCH:%.*]] = call i8 @gen8()
-; ALL-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
-; ALL-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT]]
-; ALL:       common.ret:
-; ALL-NEXT:    ret void
-; ALL:       final_left:
-; ALL-NEXT:    [[FINAL_LEFT_PHI:%.*]] = phi i8 [ [[IV_OF_FINAL_LEFT_FROM_DISPATCH:%.*]], [[DISPATCH]] ]
-; ALL-NEXT:    call void @sideeffect0(i8 [[FINAL_LEFT_PHI]])
-; ALL-NEXT:    br label [[COMMON_RET:%.*]]
-; ALL:       final_right:
-; ALL-NEXT:    [[FINAL_RIGHT_PHI:%.*]] = phi i8 [ [[IV_OF_FINAL_RIGHT_FROM_PRED]], [[PRED:%.*]] ], [ [[IV_OF_FINAL_RIGHT_FROM_DISPATCH]], [[DISPATCH]] ]
-; ALL-NEXT:    call void @sideeffect1(i8 [[FINAL_RIGHT_PHI]])
-; ALL-NEXT:    br label [[COMMON_RET]]
+; CHEAP-LABEL: @incompatible_ivs_of_single_phi.insertpos(
+; CHEAP-NEXT:  pred:
+; CHEAP-NEXT:    [[IV_OF_FINAL_RIGHT_FROM_PRED:%.*]] = call i8 @gen8()
+; CHEAP-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
+; CHEAP-NEXT:    br i1 [[C0]], label [[DISPATCH:%.*]], label [[FINAL_RIGHT:%.*]]
+; CHEAP:       dispatch:
+; CHEAP-NEXT:    [[IV_OF_FINAL_RIGHT_FROM_DISPATCH:%.*]] = call i8 @gen8()
+; CHEAP-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
+; CHEAP-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT]]
+; CHEAP:       common.ret:
+; CHEAP-NEXT:    ret void
+; CHEAP:       final_left:
+; CHEAP-NEXT:    [[FINAL_LEFT_PHI:%.*]] = phi i8 [ [[IV_OF_FINAL_LEFT_FROM_DISPATCH:%.*]], [[DISPATCH]] ]
+; CHEAP-NEXT:    call void @sideeffect0(i8 [[FINAL_LEFT_PHI]])
+; CHEAP-NEXT:    br label [[COMMON_RET:%.*]]
+; CHEAP:       final_right:
+; CHEAP-NEXT:    [[FINAL_RIGHT_PHI:%.*]] = phi i8 [ [[IV_OF_FINAL_RIGHT_FROM_PRED]], [[PRED:%.*]] ], [ [[IV_OF_FINAL_RIGHT_FROM_DISPATCH]], [[DISPATCH]] ]
+; CHEAP-NEXT:    call void @sideeffect1(i8 [[FINAL_RIGHT_PHI]])
+; CHEAP-NEXT:    br label [[COMMON_RET]]
+;
+; COSTLY-LABEL: @incompatible_ivs_of_single_phi.insertpos(
+; COSTLY-NEXT:  pred:
+; COSTLY-NEXT:    [[IV_OF_FINAL_RIGHT_FROM_PRED:%.*]] = call i8 @gen8()
+; COSTLY-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
+; COSTLY-NEXT:    [[IV_OF_FINAL_RIGHT_FROM_DISPATCH:%.*]] = call i8 @gen8()
+; COSTLY-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
+; COSTLY-NEXT:    [[FINAL_RIGHT_PHI_SEL:%.*]] = select i1 [[C0]], i8 poison, i8 [[IV_OF_FINAL_RIGHT_FROM_PRED]]
+; COSTLY-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
+; COSTLY-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
+; COSTLY:       common.ret:
+; COSTLY-NEXT:    ret void
+; COSTLY:       final_left:
+; COSTLY-NEXT:    call void @sideeffect0(i8 [[IV_OF_FINAL_LEFT_FROM_DISPATCH:%.*]])
+; COSTLY-NEXT:    br label [[COMMON_RET:%.*]]
+; COSTLY:       final_right:
+; COSTLY-NEXT:    call void @sideeffect1(i8 [[FINAL_RIGHT_PHI_SEL]])
+; COSTLY-NEXT:    br label [[COMMON_RET]]
 ;
 pred:
   %iv.of.final_right.from.pred = call i8 @gen8()
   %c0 = icmp eq i8 %v0, 0
   br i1 %c0, label %dispatch, label %final_right
 dispatch:
   %iv.of.final_right.from.dispatch = call i8 @gen8()
   %c1 = icmp eq i8 %v1, 0
   br i1 %c1, label %final_left, label %final_right
 final_left:
   %final_left.phi = phi i8 [ %iv.of.final_left.from.dispatch, %dispatch ]
   call void @sideeffect0(i8 %final_left.phi)
   ret void
 final_right:
   %final_right.phi = phi i8 [ %iv.of.final_right.from.pred, %pred ], [ %iv.of.final_right.from.dispatch, %dispatch ]
   call void @sideeffect1(i8 %final_right.phi)
   ret void
 }
 
 define void @incompatible_ivs_of_one_of_two_phis(i8 %v0, i8 %v1, i8 %iv.of.final_left.from.dispatch, i8 %iv.of.final_right.from.pred, i8 %iv.of.final_right.from.dispatch) {
 ; ALL-LABEL: @incompatible_ivs_of_one_of_two_phis(
 ; ALL-NEXT:  pred:
 ; ALL-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
-; ALL-NEXT:    br i1 [[C0]], label [[DISPATCH:%.*]], label [[FINAL_RIGHT:%.*]]
-; ALL:       dispatch:
 ; ALL-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
-; ALL-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT]]
+; ALL-NEXT:    [[FINAL_RIGHT_PHI_0_SEL:%.*]] = select i1 [[C0]], i8 [[IV_OF_FINAL_RIGHT_FROM_DISPATCH:%.*]], i8 [[IV_OF_FINAL_RIGHT_FROM_PRED:%.*]]
+; ALL-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
+; ALL-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; ALL:       common.ret:
 ; ALL-NEXT:    ret void
 ; ALL:       final_left:
-; ALL-NEXT:    [[FINAL_LEFT_PHI:%.*]] = phi i8 [ [[IV_OF_FINAL_LEFT_FROM_DISPATCH:%.*]], [[DISPATCH]] ]
-; ALL-NEXT:    call void @sideeffect0(i8 [[FINAL_LEFT_PHI]])
+; ALL-NEXT:    call void @sideeffect0(i8 [[IV_OF_FINAL_LEFT_FROM_DISPATCH:%.*]])
 ; ALL-NEXT:    br label [[COMMON_RET:%.*]]
 ; ALL:       final_right:
-; ALL-NEXT:    [[FINAL_RIGHT_PHI_0:%.*]] = phi i8 [ [[IV_OF_FINAL_RIGHT_FROM_PRED:%.*]], [[PRED:%.*]] ], [ [[IV_OF_FINAL_RIGHT_FROM_DISPATCH:%.*]], [[DISPATCH]] ]
-; ALL-NEXT:    [[FINAL_RIGHT_PHI_1:%.*]] = phi i8 [ 42, [[PRED]] ], [ 42, [[DISPATCH]] ]
-; ALL-NEXT:    call void @sideeffect1(i8 [[FINAL_RIGHT_PHI_0]])
-; ALL-NEXT:    call void @sideeffect1(i8 [[FINAL_RIGHT_PHI_1]])
+; ALL-NEXT:    call void @sideeffect1(i8 [[FINAL_RIGHT_PHI_0_SEL]])
+; ALL-NEXT:    call void @sideeffect1(i8 42)
 ; ALL-NEXT:    br label [[COMMON_RET]]
 ;
 pred:
   %c0 = icmp eq i8 %v0, 0
   br i1 %c0, label %dispatch, label %final_right
 dispatch:
   %c1 = icmp eq i8 %v1, 0
   br i1 %c1, label %final_left, label %final_right
 final_left:
   %final_left.phi = phi i8 [ %iv.of.final_left.from.dispatch, %dispatch ]
   call void @sideeffect0(i8 %final_left.phi)
   ret void
 final_right:
   %final_right.phi.0 = phi i8 [ %iv.of.final_right.from.pred, %pred ], [ %iv.of.final_right.from.dispatch, %dispatch ]
   %final_right.phi.1 = phi i8 [ 42, %pred ], [ 42, %dispatch ]
   call void @sideeffect1(i8 %final_right.phi.0)
   call void @sideeffect1(i8 %final_right.phi.1)
   ret void
 }
 
 define void @incompatible_ivs_of_two_phis(i8 %v0, i8 %v1, i8 %iv.of.final_left.from.dispatch, i8 %iv0.of.final_right.from.pred, i8 %iv0.of.final_right.from.dispatch, i8 %iv1.of.final_right.from.pred, i8 %iv1.of.final_right.from.dispatch) {
-; ALL-LABEL: @incompatible_ivs_of_two_phis(
-; ALL-NEXT:  pred:
-; ALL-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
-; ALL-NEXT:    br i1 [[C0]], label [[DISPATCH:%.*]], label [[FINAL_RIGHT:%.*]]
-; ALL:       dispatch:
-; ALL-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
-; ALL-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT]]
-; ALL:       common.ret:
-; ALL-NEXT:    ret void
-; ALL:       final_left:
-; ALL-NEXT:    [[FINAL_LEFT_PHI:%.*]] = phi i8 [ [[IV_OF_FINAL_LEFT_FROM_DISPATCH:%.*]], [[DISPATCH]] ]
-; ALL-NEXT:    call void @sideeffect0(i8 [[FINAL_LEFT_PHI]])
-; ALL-NEXT:    br label [[COMMON_RET:%.*]]
-; ALL:       final_right:
-; ALL-NEXT:    [[FINAL_RIGHT_PHI_0:%.*]] = phi i8 [ [[IV0_OF_FINAL_RIGHT_FROM_PRED:%.*]], [[PRED:%.*]] ], [ [[IV0_OF_FINAL_RIGHT_FROM_DISPATCH:%.*]], [[DISPATCH]] ]
-; ALL-NEXT:    [[FINAL_RIGHT_PHI_1:%.*]] = phi i8 [ [[IV1_OF_FINAL_RIGHT_FROM_PRED:%.*]], [[PRED]] ], [ [[IV1_OF_FINAL_RIGHT_FROM_DISPATCH:%.*]], [[DISPATCH]] ]
-; ALL-NEXT:    call void @sideeffect1(i8 [[FINAL_RIGHT_PHI_0]])
-; ALL-NEXT:    call void @sideeffect1(i8 [[FINAL_RIGHT_PHI_1]])
-; ALL-NEXT:    br label [[COMMON_RET]]
+; CHEAP-LABEL: @incompatible_ivs_of_two_phis(
+; CHEAP-NEXT:  pred:
+; CHEAP-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
+; CHEAP-NEXT:    br i1 [[C0]], label [[DISPATCH:%.*]], label [[FINAL_RIGHT:%.*]]
+; CHEAP:       dispatch:
+; CHEAP-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
+; CHEAP-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT]]
+; CHEAP:       common.ret:
+; CHEAP-NEXT:    ret void
+; CHEAP:       final_left:
+; CHEAP-NEXT:    [[FINAL_LEFT_PHI:%.*]] = phi i8 [ [[IV_OF_FINAL_LEFT_FROM_DISPATCH:%.*]], [[DISPATCH]] ]
+; CHEAP-NEXT:    call void @sideeffect0(i8 [[FINAL_LEFT_PHI]])
+; CHEAP-NEXT:    br label [[COMMON_RET:%.*]]
+; CHEAP:       final_right:
+; CHEAP-NEXT:    [[FINAL_RIGHT_PHI_0:%.*]] = phi i8 [ [[IV0_OF_FINAL_RIGHT_FROM_PRED:%.*]], [[PRED:%.*]] ], [ [[IV0_OF_FINAL_RIGHT_FROM_DISPATCH:%.*]], [[DISPATCH]] ]
+; CHEAP-NEXT:    [[FINAL_RIGHT_PHI_1:%.*]] = phi i8 [ [[IV1_OF_FINAL_RIGHT_FROM_PRED:%.*]], [[PRED]] ], [ [[IV1_OF_FINAL_RIGHT_FROM_DISPATCH:%.*]], [[DISPATCH]] ]
+; CHEAP-NEXT:    call void @sideeffect1(i8 [[FINAL_RIGHT_PHI_0]])
+; CHEAP-NEXT:    call void @sideeffect1(i8 [[FINAL_RIGHT_PHI_1]])
+; CHEAP-NEXT:    br label [[COMMON_RET]]
+;
+; COSTLY-LABEL: @incompatible_ivs_of_two_phis(
+; COSTLY-NEXT:  pred:
+; COSTLY-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
+; COSTLY-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
+; COSTLY-NEXT:    [[FINAL_RIGHT_PHI_0_SEL:%.*]] = select i1 [[C0]], i8 [[IV0_OF_FINAL_RIGHT_FROM_DISPATCH:%.*]], i8 [[IV0_OF_FINAL_RIGHT_FROM_PRED:%.*]]
+; COSTLY-NEXT:    [[FINAL_RIGHT_PHI_1_SEL:%.*]] = select i1 [[C0]], i8 [[IV1_OF_FINAL_RIGHT_FROM_DISPATCH:%.*]], i8 [[IV1_OF_FINAL_RIGHT_FROM_PRED:%.*]]
+; COSTLY-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
+; COSTLY-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
+; COSTLY:       common.ret:
+; COSTLY-NEXT:    ret void
+; COSTLY:       final_left:
+; COSTLY-NEXT:    call void @sideeffect0(i8 [[IV_OF_FINAL_LEFT_FROM_DISPATCH:%.*]])
+; COSTLY-NEXT:    br label [[COMMON_RET:%.*]]
+; COSTLY:       final_right:
+; COSTLY-NEXT:    call void @sideeffect1(i8 [[FINAL_RIGHT_PHI_0_SEL]])
+; COSTLY-NEXT:    call void @sideeffect1(i8 [[FINAL_RIGHT_PHI_1_SEL]])
+; COSTLY-NEXT:    br label [[COMMON_RET]]
 ;
 pred:
   %c0 = icmp eq i8 %v0, 0
   br i1 %c0, label %dispatch, label %final_right
 dispatch:
   %c1 = icmp eq i8 %v1, 0
   br i1 %c1, label %final_left, label %final_right
 final_left:

llvm/test/Transforms/SimplifyCFG/fold-branch-to-common-dest.ll

 
 define void @two_preds_with_extra_op_liveout(i8 %v0, i8 %v1, i8 %v2, i8 %v3) {
 ; CHECK-LABEL: @two_preds_with_extra_op_liveout(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 ; CHECK:       pred0:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
-; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[DISPATCH:%.*]]
+; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2:%.*]]
+; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3_ADJ_OLD]], 0
+; CHECK-NEXT:    [[MERGE_LEFT_SEL:%.*]] = select i1 [[C1]], i8 poison, i8 0
+; CHECK-NEXT:    [[OR_COND1:%.*]] = select i1 [[C1]], i1 true, i1 [[C3_OLD]]
+; CHECK-NEXT:    br i1 [[OR_COND1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       pred1:
-; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
+; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2]], 0
 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V1]], [[V2]]
 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3_ADJ]], 0
 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
-; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT:%.*]]
-; CHECK:       dispatch:
-; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2]]
-; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3_ADJ_OLD]], 0
-; CHECK-NEXT:    br i1 [[C3_OLD]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 ; CHECK:       common.ret:
 ; CHECK-NEXT:    ret void
 ; CHECK:       final_left:
-; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 0, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
+; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[MERGE_LEFT_SEL]], [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT]])
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 ; CHECK:       final_right:
 ; CHECK-NEXT:    call void @sideeffect1()
 ; CHECK-NEXT:    br label [[COMMON_RET]]
 ;
 entry:

 
 define void @two_preds_with_extra_op_liveout_multiuse(i8 %v0, i8 %v1, i8 %v2, i8 %v3) {
 ; CHECK-LABEL: @two_preds_with_extra_op_liveout_multiuse(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 ; CHECK:       pred0:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
-; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[DISPATCH:%.*]]
+; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2:%.*]]
+; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3_ADJ_OLD]], 0
+; CHECK-NEXT:    [[MERGE_LEFT_SEL:%.*]] = select i1 [[C1]], i8 poison, i8 0
+; CHECK-NEXT:    [[MERGE_LEFT_2_SEL:%.*]] = select i1 [[C1]], i8 poison, i8 42
+; CHECK-NEXT:    [[OR_COND1:%.*]] = select i1 [[C1]], i1 true, i1 [[C3_OLD]]
+; CHECK-NEXT:    br i1 [[OR_COND1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       pred1:
-; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
+; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2]], 0
 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V1]], [[V2]]
 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3_ADJ]], 0
 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
-; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT:%.*]]
-; CHECK:       dispatch:
-; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2]]
-; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3_ADJ_OLD]], 0
-; CHECK-NEXT:    br i1 [[C3_OLD]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 ; CHECK:       common.ret:
 ; CHECK-NEXT:    ret void
 ; CHECK:       final_left:
-; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 0, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
-; CHECK-NEXT:    [[MERGE_LEFT_2:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 42, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
+; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[MERGE_LEFT_SEL]], [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
+; CHECK-NEXT:    [[MERGE_LEFT_2:%.*]] = phi i8 [ [[MERGE_LEFT_2_SEL]], [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT]])
 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT_2]])
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 ; CHECK:       final_right:
 ; CHECK-NEXT:    call void @sideeffect1()
 ; CHECK-NEXT:    br label [[COMMON_RET]]
 ;

 
 define void @two_preds_with_extra_op_externally_used_only(i8 %v0, i8 %v1, i8 %v2, i8 %v3) {
 ; CHECK-LABEL: @two_preds_with_extra_op_externally_used_only(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 ; CHECK:       pred0:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
-; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[DISPATCH:%.*]]
+; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2:%.*]]
+; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3:%.*]], 0
+; CHECK-NEXT:    [[MERGE_LEFT_SEL:%.*]] = select i1 [[C1]], i8 poison, i8 0
+; CHECK-NEXT:    [[OR_COND1:%.*]] = select i1 [[C1]], i1 true, i1 [[C3_OLD]]
+; CHECK-NEXT:    br i1 [[OR_COND1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       pred1:
-; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
+; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2]], 0
 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V1]], [[V2]]
-; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3:%.*]], 0
+; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3]], 0
 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
-; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT:%.*]]
-; CHECK:       dispatch:
-; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2]]
-; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3]], 0
-; CHECK-NEXT:    br i1 [[C3_OLD]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 ; CHECK:       common.ret:
 ; CHECK-NEXT:    ret void
 ; CHECK:       final_left:
-; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 0, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
+; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[MERGE_LEFT_SEL]], [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT]])
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 ; CHECK:       final_right:
 ; CHECK-NEXT:    call void @sideeffect1()
 ; CHECK-NEXT:    br label [[COMMON_RET]]
 ;
 entry:

 
 define void @two_preds_with_extra_op_externally_used_only_multiuse(i8 %v0, i8 %v1, i8 %v2, i8 %v3) {
 ; CHECK-LABEL: @two_preds_with_extra_op_externally_used_only_multiuse(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 ; CHECK:       pred0:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
-; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[DISPATCH:%.*]]
+; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2:%.*]]
+; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3:%.*]], 0
+; CHECK-NEXT:    [[MERGE_LEFT_SEL:%.*]] = select i1 [[C1]], i8 poison, i8 0
+; CHECK-NEXT:    [[MERGE_LEFT_2_SEL:%.*]] = select i1 [[C1]], i8 poison, i8 42
+; CHECK-NEXT:    [[OR_COND1:%.*]] = select i1 [[C1]], i1 true, i1 [[C3_OLD]]
+; CHECK-NEXT:    br i1 [[OR_COND1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       pred1:
-; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
+; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2]], 0
 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V1]], [[V2]]
-; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3:%.*]], 0
+; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3]], 0
 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
-; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT:%.*]]
-; CHECK:       dispatch:
-; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2]]
-; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3]], 0
-; CHECK-NEXT:    br i1 [[C3_OLD]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 ; CHECK:       common.ret:
 ; CHECK-NEXT:    ret void
 ; CHECK:       final_left:
-; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 0, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
-; CHECK-NEXT:    [[MERGE_LEFT_2:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 42, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
+; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[MERGE_LEFT_SEL]], [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
+; CHECK-NEXT:    [[MERGE_LEFT_2:%.*]] = phi i8 [ [[MERGE_LEFT_2_SEL]], [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT]])
 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT_2]])
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 ; CHECK:       final_right:
 ; CHECK-NEXT:    call void @sideeffect1()
 ; CHECK-NEXT:    br label [[COMMON_RET]]
 ;

 }
 define void @two_preds_with_extra_op_externally_used_only_after_cond(i8 %v0, i8 %v1, i8 %v2, i8 %v3, i8 %v4, i8 %v5) {
 ; CHECK-LABEL: @two_preds_with_extra_op_externally_used_only_after_cond(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 ; CHECK:       pred0:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
-; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[DISPATCH:%.*]]
+; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3:%.*]], 0
+; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V4:%.*]], [[V5:%.*]]
+; CHECK-NEXT:    [[MERGE_LEFT_SEL:%.*]] = select i1 [[C1]], i8 poison, i8 0
+; CHECK-NEXT:    [[OR_COND1:%.*]] = select i1 [[C1]], i1 true, i1 [[C3_OLD]]
+; CHECK-NEXT:    br i1 [[OR_COND1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       pred1:
 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
-; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3:%.*]], 0
-; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V4:%.*]], [[V5:%.*]]
+; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3]], 0
+; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V4]], [[V5]]
 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
-; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT:%.*]]
-; CHECK:       dispatch:
-; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3]], 0
-; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V4]], [[V5]]
-; CHECK-NEXT:    br i1 [[C3_OLD]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 ; CHECK:       common.ret:
 ; CHECK-NEXT:    ret void
 ; CHECK:       final_left:
-; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 0, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
+; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[MERGE_LEFT_SEL]], [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT]])
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 ; CHECK:       final_right:
 ; CHECK-NEXT:    call void @sideeffect1()
 ; CHECK-NEXT:    br label [[COMMON_RET]]
 ;
 entry:
cleanup:
   %retval.0 = phi i32 [ 1, %entry ], [ 1, %if.end ], [ 1, %if.end13 ], [ %., %if.end22 ]
   ret i32 %retval.0
 }
 
 define i32 @test_builtin_fpclassify(float %x) {
 ; CHECK-LABEL: @test_builtin_fpclassify(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[ISZERO:%.*]] = fcmp oeq float [[X:%.*]], 0.000000e+00
-; CHECK-NEXT:    br i1 [[ISZERO]], label [[FPCLASSIFY_END:%.*]], label [[FPCLASSIFY_NOT_ZERO:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = fcmp uno float [[X]], 0.000000e+00
+; CHECK-NEXT:    [[FPCLASSIFY_RESULT_SEL:%.*]] = select i1 [[ISZERO]], i32 0, i32 2
+; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[ISZERO]], [[CMP]]
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[FPCLASSIFY_END:%.*]], label [[FPCLASSIFY_NOT_NAN:%.*]]
 ; CHECK:       fpclassify_end:
-; CHECK-NEXT:    [[FPCLASSIFY_RESULT:%.*]] = phi i32 [ 2, [[ENTRY:%.*]] ], [ 0, [[FPCLASSIFY_NOT_ZERO]] ], [ 1, [[FPCLASSIFY_NOT_NAN:%.*]] ], [ [[NORMAL_OR_SUBNORMAL:%.*]], [[FPCLASSIFY_NOT_INF:%.*]] ]
+; CHECK-NEXT:    [[FPCLASSIFY_RESULT:%.*]] = phi i32 [ [[FPCLASSIFY_RESULT_SEL]], [[ENTRY:%.*]] ], [ 1, [[FPCLASSIFY_NOT_NAN]] ], [ [[NORMAL_OR_SUBNORMAL:%.*]], [[FPCLASSIFY_NOT_INF:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[FPCLASSIFY_RESULT]]
-; CHECK:       fpclassify_not_zero:
-; CHECK-NEXT:    [[CMP:%.*]] = fcmp uno float [[X]], 0.000000e+00
-; CHECK-NEXT:    br i1 [[CMP]], label [[FPCLASSIFY_END]], label [[FPCLASSIFY_NOT_NAN]]
 ; CHECK:       fpclassify_not_nan:
 ; CHECK-NEXT:    [[X_ABS:%.*]] = tail call float @llvm.fabs.f32(float [[X]])
 ; CHECK-NEXT:    [[ISINF:%.*]] = fcmp oeq float [[X_ABS]], 0x7FF0000000000000
 ; CHECK-NEXT:    br i1 [[ISINF]], label [[FPCLASSIFY_END]], label [[FPCLASSIFY_NOT_INF]]
 ; CHECK:       fpclassify_not_inf:
 ; CHECK-NEXT:    [[ISNORMAL:%.*]] = fcmp uge float [[X_ABS]], 0x3810000000000000
 ; CHECK-NEXT:    [[NORMAL_OR_SUBNORMAL]] = select i1 [[ISNORMAL]], i32 4, i32 3
 ; CHECK-NEXT:    br label [[FPCLASSIFY_END]]

llvm/test/Transforms/SimplifyCFG/hoist-dbgvalue.ll

exit:
   %p = phi i1 [ true, %cond.end.thread19 ], [ false, %cond.end.thread ]
   ret i1 %p
 }
 
 ; Test case for PR49982.
 define i16 @hoist_with_debug3_pr49982(i32 %x, i1 %c.2) !dbg !26 {
 ; CHECK-LABEL: @hoist_with_debug3_pr49982(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[FOR_COND:%.*]]
-; CHECK:       for.cond:
-; CHECK-NEXT:    [[C_0:%.*]] = icmp sgt i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[BRMERGE:%.*]] = select i1 [[C_0]], i1 true, i1 [[C_2:%.*]]
-; CHECK-NEXT:    [[DOTMUX:%.*]] = select i1 [[C_0]], i16 0, i16 20
-; CHECK-NEXT:    br i1 [[BRMERGE]], label [[COMMON_RET:%.*]], label [[FOR_COND]]
+; CHECK-NEXT:    [[C_0_OLD:%.*]] = icmp sgt i32 [[X:%.*]], 0
+; CHECK-NEXT:    br i1 [[C_0_OLD]], label [[COMMON_RET:%.*]], label [[LATCH:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[C_0:%.*]] = icmp sgt i32 [[X]], 0
+; CHECK-NEXT:    [[COMMON_RET_OP_SEL:%.*]] = select i1 [[C_2:%.*]], i16 0, i16 20
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C_2]], i1 true, i1 [[C_0]]
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[COMMON_RET]], label [[LATCH]]
 ; CHECK:       common.ret:
-; CHECK-NEXT:    ret i16 [[DOTMUX]]
+; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i16 [ [[COMMON_RET_OP_SEL]], [[LATCH]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i16 [[COMMON_RET_OP]]
 ;
 entry:
   br label %for.cond
 
 for.cond:
   %c.0 = icmp sgt i32 %x, 0
   br i1 %c.0, label %check, label %latch
 

llvm/test/Transforms/SimplifyCFG/switch-on-const-select.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s
 
 ; Test basic folding to a conditional branch.
 define i32 @foo(i64 %x, i64 %y) nounwind {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[EQ:%.*]] = icmp eq i64 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    br i1 [[EQ]], label [[B:%.*]], label [[SWITCH:%.*]]
-; CHECK:       switch:
+; CHECK-NEXT:    [[EQ:%.*]] = icmp ne i64 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[LT:%.*]] = icmp slt i64 [[X]], [[Y]]
-; CHECK-NEXT:    br i1 [[LT]], label [[A:%.*]], label [[B]]
+; CHECK-NEXT:    [[RETVAL_SEL:%.*]] = select i1 [[EQ]], i32 0, i32 2
+; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[EQ]], [[LT]]
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[A:%.*]], label [[B:%.*]]
 ; CHECK:       common.ret:
-; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 1, [[A]] ], [ [[RETVAL:%.*]], [[B]] ]
+; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 1, [[A]] ], [ [[RETVAL_SEL]], [[B]] ]
 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
 ; CHECK:       a:
 ; CHECK-NEXT:    tail call void @bees.a() #[[ATTR0:[0-9]+]]
 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 ; CHECK:       b:
-; CHECK-NEXT:    [[RETVAL]] = phi i32 [ 0, [[SWITCH]] ], [ 2, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    tail call void @bees.b() #[[ATTR0]]
 ; CHECK-NEXT:    br label [[COMMON_RET]]
 ;
 entry:
   %eq = icmp eq i64 %x, %y
   br i1 %eq, label %b, label %switch
 switch:
   %lt = icmp slt i64 %x, %y
bees:
   tail call void @llvm.trap()
   unreachable
 }
 
 ; A final test, for phi node munging.
 define i32 @xyzzy(i64 %x, i64 %y) {
 ; CHECK-LABEL: @xyzzy(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[EQ:%.*]] = icmp eq i64 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[EQ:%.*]] = icmp ne i64 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[LT:%.*]] = icmp slt i64 [[X]], [[Y]]
-; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[LT]], i32 -1, i32 1
-; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = select i1 [[EQ]], i32 0, i32 [[SPEC_SELECT]]
+; CHECK-NEXT:    [[VAL_SEL:%.*]] = select i1 [[EQ]], i32 1, i32 0
+; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[EQ]], [[LT]]
+; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = select i1 [[OR_COND]], i32 -1, i32 [[VAL_SEL]]
 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
 ;
 entry:
   %eq = icmp eq i64 %x, %y
   br i1 %eq, label %r, label %cont
 cont:
   %lt = icmp slt i64 %x, %y
   %qux = select i1 %lt, i32 0, i32 2