[SimpleLoopUnswitch][reland 2] unswitch selects

[caojoshua]

Summary

The old LoopUnswitch pass unswitched selects, but the changes were
never ported to the new SimpleLoopUnswitch.

We unswitch by turning:

S = select %cond, %a, %b

into:

 head: br %cond, label %then, label %tail

then: br label %tail

tail: S = phi [ %a, %then ], [ %b, %head ]

Unswitch selects are always nontrivial, since the successors do not
exit the loop and the loop body always needs to be cloned.

Unswitch selects always need to freeze the conditional if the
conditional could be poison or undef. Selects don't propagate
poison/undef, and branches on poison/undef causes UB.

Reland 1 - Fix the insertion of freeze instructions. The original
implementation inserts a dead freeze instruction that is not used by the
unswitched branch.

Reland 2 - Include https://reviews.llvm.org/D149560 in the same patch,
which was originally reverted along with this patch. The patch prevents
unswitching of selects with a vector conditional. This could have been
caught in SimpleLoopUnswitch/crash.ll if it included tests for
nontrivial unswitching. This reland also adds a run for the test file
with nontrivial unswitching.

[caojoshua]

This comment was removed by caojoshua.

[caojoshua]

update commit message

[caojoshua]

Fix typo in commit message

[caojoshua]

More changes before sending for review

[caojoshua]

ping

[fhahn]

This seems to try to unswitch every select, but https://github.com/llvm/llvm-project/issues/58122 would only require unswitching conditions that are fed by selects with (some) constant values. Would it be possible to just unswitch such branches, rather than all selects?

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2413

Please submit an NFC patch for review that just changes that so it can be discussed separately.

llvm/test/Transforms/SimpleLoopUnswitch/unswitch-equality-undef.ll

4

Do the tests need to be so big to just check for that? Seems like it should be possible to simplify this more. Also, please limit the test to just simple-loop-unsiwtch, if possible. And use the new PM syntax -passes=...

llvm/test/Transforms/SimpleLoopUnswitch/unswitch-select.ll

8

I think we definitely need to check the full generates structure of the IR. Also, this is could do with a few more test cases, .e.g including bottom tested loops, select not fed by phi, chained selects and so on.

[caojoshua]

In D138526#3962885, @fhahn wrote:

This seems to try to unswitch every select, but https://github.com/llvm/llvm-project/issues/58122 would only require unswitching conditions that are fed by selects with (some) constant values. Would it be possible to just unswitch such branches, rather than all selects?

Yes, we could, but I think its better to unswitch all selects, like the previous LoopUnswitch did. Should I provide some evidence for this? Maybe through benchmarks?

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2413

This is not a separate patch because we are calling ConstantFoldTerminator(), which only accepts the DomTreeUpdater. I don't think we can motivate this change outside of this patch.

llvm/test/Transforms/SimpleLoopUnswitch/unswitch-equality-undef.ll

4

Do the tests need to be so big to just check for that?

Probably not. This test is directly copied from the old LoopUnswitch. I chose not to modify copied tests.

Also, please limit the test to just simple-loop-unsiwtch, if possible. And use the new PM syntax -passes=...

sounds good. I'll change that.

llvm/test/Transforms/SimpleLoopUnswitch/unswitch-select.ll

8

Thank you. I'll work on this.

[caojoshua]

Threw away original implementation and took it from https://reviews.llvm.org/D139109. Thanks to @kachkov98 for his work on this, who is listed as a co-author in the commit.

The implementation is mostly copied with small changes and incorporates feedback from reviewers. Took out NFC's for unswitching guards.

Added a bunch of tests.

[caojoshua]

update commit message in review

[vchuravy]

This revision seems to fix one of the largest regression we found when going to SimpleLoopUnswitch in Julia, we will likely carry this patch going forward.

[kachkov98]

If there is a critical regression that this patch solves, I don't see any objections to merge it (just for note, I didn't observe any noticeable performance improvements from this on SPEC2006/2017 + some internal benchmarks)

[caojoshua]

I'll let this sit for a bit in case anyone else comes and reviews.

I ran this through non-SPEC llvm-test-suite and did not observe increase in compile time.

[caojoshua]

Use DomTreeUpdater for SplitAndInsertIfThen

[mstorsjo]

This triggers failed asserts for aarch64. To repro:

$ cat repro.c
typedef __attribute__((neon_vector_type(8))) unsigned char a;
a c, d, f;
char e;
void b();
void g() {
  a h;
  if (e) {
    a i = {255};
    h = i;
  } else {
    a i = {};
    h = i;
  }
  for (;;) {
    b();
    a i = __builtin_neon_vbsl_v(h, c, d, 16);
    f = i;
  }
}
$ clang -target aarch64-linux-gnu -c repro.c -O3
clang: ../lib/IR/Instructions.cpp:1383: void llvm::BranchInst::AssertOK(): Assertion `getCondition()->getType()->isIntegerTy(1) && "May only branch on boolean predicates!"' failed.

[caojoshua]

Should be fixed by https://reviews.llvm.org/D149560, which does not unswitch vector selects.

[vitalybuka]

In D138526#4309363, @caojoshua wrote:

Should be fixed by https://reviews.llvm.org/D149560, which does not unswitch vector selects.

Could this be caused by this patch?
https://lab.llvm.org/buildbot/#/builders/74/builds/18906

[mstorsjo]

In D138526#4309363, @caojoshua wrote:

Should be fixed by https://reviews.llvm.org/D149560, which does not unswitch vector selects.

Indeed it is, thanks, and sorry for not checking the latest git main before posting.

[caojoshua]

In D138526#4309373, @vitalybuka wrote:

In D138526#4309363, @caojoshua wrote:

Should be fixed by https://reviews.llvm.org/D149560, which does not unswitch vector selects.

Could this be caused by this patch?
https://lab.llvm.org/buildbot/#/builders/74/builds/18906

It first started failing in https://lab.llvm.org/buildbot/#/builders/237/builds/2419, which this patch is on the blamelist for. There are 11 patches on the blamelist, and this patch is the most disruptive. Looking at the error message, msan has found use-of-initialized error. Its not obvious to me how this patch can cause this.

I will try reproducing this locally.

[vitalybuka]

In D138526#4310137, @caojoshua wrote:

In D138526#4309373, @vitalybuka wrote:

In D138526#4309363, @caojoshua wrote:

Should be fixed by https://reviews.llvm.org/D149560, which does not unswitch vector selects.

Could this be caused by this patch?
https://lab.llvm.org/buildbot/#/builders/74/builds/18906

It first started failing in https://lab.llvm.org/buildbot/#/builders/237/builds/2419, which this patch is on the blamelist for. There are 11 patches on the blamelist, and this patch is the most disruptive. Looking at the error message, msan has found use-of-initialized error. Its not obvious to me how this patch can cause this.

I will try reproducing this locally.

My nightly bisect failed. So still guesses.
instcombine cold be related too, but this one is more likely. Msan is about branches. In case of select, it only propagates shadow, but branch reports uninitialized stuff immediatly.
So either a bug in the Interval code, this patch breaks msan.

[caojoshua]

Its too hard to reproduce this locally on my personal machine. @vitalybuka I see you submitted a build for this patch. Lets see how that goes.

msan is reporting using unitialized end iterator. The end_iterator should be initialized with the default constructor, and I'm not sure yet how my change could break that.

[vitalybuka]

In D138526#4311286, @caojoshua wrote:

Its too hard to reproduce this locally on my personal machine. @vitalybuka I see you submitted a build for this patch. Lets see how that goes.

msan is reporting using unitialized end iterator. The end_iterator should be initialized with the default constructor, and I'm not sure yet how my change could break that.

Yes, it passed on the parent. Also I bisected locally and this is the patch.
Easy way to reproduce is https://github.com/google/sanitizers/wiki/SanitizerBotReproduceBuild
We need to revert as it breaks existing feature. Unless there is a prove that C++ code is invalid (I can't see that).

[vitalybuka]

As reverted, with D149560 fixes.

[caojoshua]

I think this patch's transformations are correct, and that the affected test has a true case of use-of-uninitialized-value. I posted a review in https://reviews.llvm.org/D149698. If that patch is merged, I would like to reland this patch.

[vitalybuka]

In D138526#4313843, @caojoshua wrote:

I think this patch's transformations are correct, and that the affected test has a true case of use-of-uninitialized-value. I posted a review in https://reviews.llvm.org/D149698. If that patch is merged, I would like to reland this patch.

This could be correct if you ignore other features of compiler, like msan.
Msan goal is to detects UB issues in C/C++ code. So before Msan we can't run transformation which eliminate information about the program. This patch does, so it can't detect UBs correctly.
So I am strongly against landing this patch as-is.

So what can we do about the issue?
It would be nice to change the patch to preserve structure so msan works correctly.
E.g. in order of preference:

1. if possible avoid branching on uninitalized variables, select is fine.
2. If it's hard, the do not run such transformations before msan. Ideally for report quality sanitizers should run as earliest passes in pipeline, but it greatly reduces performance of sanitizers (times). So they benefit from the most simplification passes. But then time to time we get into situation like this. Note that early optimizations hide some bug from sanitizers. We trade false-negatives for performance. However false-positive very undesirable.
3. If there is a reason to run the pass in exactly that point of pipeline, then don't run transformation if function has "sanitize_memory" attribute. (I don't see implication for other sanitizers from this patch).

[nikic]

@vitalybuka This transform introduces a freeze on the select condition. msan assumes clean shadow for freeze. So I think by itself this shouldn't cause false positives in msan (at worst only false negatives, which are okay). Something more must be going on here.

[caojoshua]

if possible avoid branching on uninitalized variables, select is fine.

I might be ok with this, would be an easy change. I would not like suggestion 2, because we want passes to work correctly regardless of where its run in the pipeline. I also would avoid suggestion 3, because we want our sanitizers to validate after the transformations.

As nikic pointed out, we are inserting a freeze. Looking at the final IR, the freeze generated by loop unswitch is gone, so I agree that something else is going on. I suspect something is happening further down the optimization pipeline. I'm going to investigate further before I make a decision on where I want to take this patch.

As an exercise, I came up with an example with branch unswitching that could cause msan warnings. The freeze instruction there prevents msan warnings. However, if I manually remove the freeze instruction and run it with msan, I do see the use-of-uninitialized-value warning. This showed me its ok to hoist the invariant branch outside of the loop, as long as we insert the freeze instruction.

[caojoshua]

I found that the previous implementation was completely broken on inserting freeze instructions. We were creating freeze instructions, but not inserting it as the condition for the branch instruction. In other words, we were creating a dead freeze instruction. This issue was not caught earlier because existing logic to insert freeze on branch instructions covered most cases.

I factored out the freeze logic from unswitchNontrivialInvariants to shouldInsertFreeze. This will allow the select-converted-branch get a freeze inserted just like other branches. I added some comments here which I'm not 100% sure is accurate. Would appreciate review on wording for these.

[vitalybuka]

Thanks.
Freeze is going to be false negatives, which are bad for msan, but better then false positives. Taking that this is -O3 only the patch is LGTM.

I played with existing version of compiler, looks like freeze from this pass can hide a lot of bugs.
So please consider just make this patch NOOP if function has sanitize_memory attribute. Do you see disadvantages in this?

BTW. Also this probably means that we need to switch our msan bots to -O2 or below, to catch more uninit bugs in LLVM.

Would appreciate review on wording for these.

This is beyond my expertise. I'll accept, but please set a blocking reviewer to catch attention of particular person.

[nikic]

freeze comments looks fine.

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2658–2659

[caojoshua]

Freeze is going to be false negatives, which are bad for msan, but better then false positives. Taking that this is -O3 only the patch is LGTM.
I played with existing version of compiler, looks like freeze from this pass can hide a lot of bugs.
So please consider just make this patch NOOP if function has sanitize_memory attribute. Do you see disadvantages in this?

Could you share an example of a case where LoopUnswitch could hide a bug? I'm guessing its where we hoist a branch that could be undef. We insert a freeze that hides the use of undef, but maybe its actually a true undef and we get a false negative. I'm having some trouble producing this case atm.

Not sure what examples you were able to produce, but "trivial" loop unswitching is enabled in O1. It is possible that even if we switch msan builders to a lower optimization level, some bugs could still be hidden.

From my understanding, you found the pass as a whole, and not just this patch, can hide bugs. If we filter by sanitize_memory, we should probably turn it on for the entire pass, and not just this patch. I would be OK to add this change in a separate patch.

This is beyond my expertise. I'll accept, but please set a blocking reviewer to catch attention of particular person.

I added @nikic as a blocking reviewer.

[vitalybuka]

In D138526#4327672, @caojoshua wrote:

Freeze is going to be false negatives, which are bad for msan, but better then false positives. Taking that this is -O3 only the patch is LGTM.
I played with existing version of compiler, looks like freeze from this pass can hide a lot of bugs.
So please consider just make this patch NOOP if function has sanitize_memory attribute. Do you see disadvantages in this?

Could you share an example of a case where LoopUnswitch could hide a bug? I'm guessing its where we hoist a branch that could be undef. We insert a freeze that hides the use of undef, but maybe its actually a true undef and we get a false negative. I'm having some trouble producing this case atm.

I mean your and similar to https://godbolt.org/z/fvP1h164s when foo (%myB.coerce) is uninitialized, freezes eliminated all checks for shadow.

[nikic]

LGTM

[xbolva00]

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

3125

on on -> on

3126

condtional -> conditional

[caojoshua]

@vitalybuka I created https://github.com/llvm/llvm-project/issues/62633 to track the fact that LoopUnswitch can make msan miss bugs.

I think that your idea to turn off loop unswitching for functions with sanitize_memory makes the most sense.

[bkramer]

Reverted this in a414db1d8e3173faca024d4532a4c655a1fe02c0. Test case in the commit message.

[caojoshua]

I forgot to reland together with https://reviews.llvm.org/D149560, which will fix the broken case. I'll apply that patch and do some more testing later.

[caojoshua]

reland 2

Include https://reviews.llvm.org/D149560 together with the patch.

I also noticed this could have been caught if SimpleLoopUnswitch/crash.ll
@test2 had nontrivial loop unswitch testing. I also added a run with nontrivial
unswitching turned on.

[caojoshua]

Update commit message to make it clear its a reland

[nikic]

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2829

I think this also needs a check that !SI->getType()->isInteger(1). We don't want to unswitch logical and/or through this code path, we have separate handling for unswitching of complex conditions.

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CodeMetrics.h"
+#include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GuardUtils.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/MustExecute.h"

 #include <utility>
 
 #define DEBUG_TYPE "simple-loop-unswitch"
 
 using namespace llvm;
 using namespace llvm::PatternMatch;
 
 STATISTIC(NumBranches, "Number of branches unswitched");
+STATISTIC(NumSelects, "Number of selects unswitched");
 STATISTIC(NumSwitches, "Number of switches unswitched");
 STATISTIC(NumGuards, "Number of guards turned into branches for unswitching");
 STATISTIC(NumTrivial, "Number of unswitches that are trivial");
 STATISTIC(
     NumCostMultiplierSkipped,
     "Number of unswitch candidates that had their cost multiplier skipped");
 
 static cl::opt<bool> EnableNonTrivialUnswitch(

 /// blocks to them but doesn't create the cloned `DominatorTree` structure and
 /// instead the caller must recompute an accurate DT. It *does* correctly
 /// update the `AssumptionCache` provided in `AC`.
 static BasicBlock *buildClonedLoopBlocks(
     Loop &L, BasicBlock *LoopPH, BasicBlock *SplitBB,
     ArrayRef<BasicBlock *> ExitBlocks, BasicBlock *ParentBB,
     BasicBlock *UnswitchedSuccBB, BasicBlock *ContinueSuccBB,
     const SmallDenseMap<BasicBlock *, BasicBlock *, 16> &DominatingSucc,
-    ValueToValueMapTy &VMap,
-    SmallVectorImpl<DominatorTree::UpdateType> &DTUpdates, AssumptionCache &AC,
+    SelectInst *SLI, ValueToValueMapTy &VMap,
+    DomTreeUpdater &DTU,  AssumptionCache &AC,
     DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU,
     ScalarEvolution *SE) {
   SmallVector<BasicBlock *, 4> NewBlocks;
   NewBlocks.reserve(L.getNumBlocks() + ExitBlocks.size());
 
   // We will need to clone a bunch of blocks, wrap up the clone operation in
   // a helper.
   auto CloneBlock = [&](BasicBlock *OldBB) {
if (SkipBlock(LoopBB))
       for (auto *SuccBB : successors(LoopBB))
         if (auto *ClonedSuccBB = cast_or_null<BasicBlock>(VMap.lookup(SuccBB)))
           for (PHINode &PN : ClonedSuccBB->phis())
             PN.removeIncomingValue(LoopBB, /*DeletePHIIfEmpty*/ false);
 
   // Remove the cloned parent as a predecessor of any successor we ended up
   // cloning other than the unswitched one.
   auto *ClonedParentBB = cast<BasicBlock>(VMap.lookup(ParentBB));
+  if (!SLI) {
     for (auto *SuccBB : successors(ParentBB)) {
       if (SuccBB == UnswitchedSuccBB)
         continue;
 
       auto *ClonedSuccBB = cast_or_null<BasicBlock>(VMap.lookup(SuccBB));
       if (!ClonedSuccBB)
         continue;
 
       ClonedSuccBB->removePredecessor(ClonedParentBB,
                                       /*KeepOneInputPHIs*/ true);
     }
+  }
 
+  auto *ClonedSuccBB = cast<BasicBlock>(VMap.lookup(UnswitchedSuccBB));
+  if (SLI) {
+    // Replace the cloned select with the true operand
+    SelectInst *ClonedSLI = cast<SelectInst>(VMap.lookup(SLI));
+    ClonedSLI->replaceAllUsesWith(ClonedSLI->getOperand(1));
+    ClonedSLI->eraseFromParent();
+  } else {
     // Replace the cloned branch with an unconditional branch to the cloned
     // unswitched successor.
-  auto *ClonedSuccBB = cast<BasicBlock>(VMap.lookup(UnswitchedSuccBB));
     Instruction *ClonedTerminator = ClonedParentBB->getTerminator();
     // Trivial Simplification. If Terminator is a conditional branch and
     // condition becomes dead - erase it.
     Value *ClonedConditionToErase = nullptr;
     if (auto *BI = dyn_cast<BranchInst>(ClonedTerminator))
       ClonedConditionToErase = BI->getCondition();
     else if (auto *SI = dyn_cast<SwitchInst>(ClonedTerminator))
       ClonedConditionToErase = SI->getCondition();
 
     ClonedTerminator->eraseFromParent();
     BranchInst::Create(ClonedSuccBB, ClonedParentBB);
 
     if (ClonedConditionToErase)
       RecursivelyDeleteTriviallyDeadInstructions(ClonedConditionToErase, nullptr,
                                                  MSSAU);
+  }
 
   // If there are duplicate entries in the PHI nodes because of multiple edges
   // to the unswitched successor, we need to nuke all but one as we replaced it
   // with a direct branch.
   for (PHINode &PN : ClonedSuccBB->phis()) {
     bool Found = false;
     // Loop over the incoming operands backwards so we can easily delete as we
     // go without invalidating the index.
     for (int i = PN.getNumOperands() - 1; i >= 0; --i) {
       if (PN.getIncomingBlock(i) != ClonedParentBB)
         continue;
       if (!Found) {
         Found = true;
         continue;
       }
       PN.removeIncomingValue(i, /*DeletePHIIfEmpty*/ false);
     }
   }
 
   // Record the domtree updates for the new blocks.
   SmallPtrSet<BasicBlock *, 4> SuccSet;
   for (auto *ClonedBB : NewBlocks) {
     for (auto *SuccBB : successors(ClonedBB))
       if (SuccSet.insert(SuccBB).second)
-        DTUpdates.push_back({DominatorTree::Insert, ClonedBB, SuccBB});
+        DTU.applyUpdates({{DominatorTree::Insert, ClonedBB, SuccBB}});
     SuccSet.clear();
   }
 
   return ClonedPH;
 }
 
 /// Recursively clone the specified loop and all of its children.
 ///
static void unswitchNontrivialInvariants(
     Loop &L, Instruction &TI, ArrayRef<Value *> Invariants,
     IVConditionInfo &PartialIVInfo, DominatorTree &DT, LoopInfo &LI,
     AssumptionCache &AC,
     function_ref<void(bool, bool, ArrayRef<Loop *>)> UnswitchCB,
     ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
     function_ref<void(Loop &, StringRef)> DestroyLoopCB) {
   auto *ParentBB = TI.getParent();
   BranchInst *BI = dyn_cast<BranchInst>(&TI);
-  SwitchInst *SI = BI ? nullptr : cast<SwitchInst>(&TI);
+  SwitchInst *SWI = dyn_cast<SwitchInst>(&TI);
+  SelectInst *SLI = dyn_cast<SelectInst>(&TI);
 
   // We can only unswitch switches, conditional branches with an invariant
   // condition, or combining invariant conditions with an instruction or
   // partially invariant instructions.
-  assert((SI || (BI && BI->isConditional())) &&
-         "Can only unswitch switches and conditional branch!");
+  assert((SWI || SLI || (BI && BI->isConditional())) &&
+         "Can only unswitch switches, selects and conditional branch!");
   bool PartiallyInvariant = !PartialIVInfo.InstToDuplicate.empty();
   bool FullUnswitch =
-      SI || (skipTrivialSelect(BI->getCondition()) == Invariants[0] &&
+      SWI || SLI || (skipTrivialSelect(BI->getCondition()) == Invariants[0] &&
              !PartiallyInvariant);
   if (FullUnswitch)
     assert(Invariants.size() == 1 &&
            "Cannot have other invariants with full unswitching!");
   else
     assert(isa<Instruction>(skipTrivialSelect(BI->getCondition())) &&
            "Partial unswitching requires an instruction as the condition!");
 
   if (MSSAU && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();
 
   // Constant and BBs tracking the cloned and continuing successor. When we are
   // unswitching the entire condition, this can just be trivially chosen to
   // unswitch towards `true`. However, when we are unswitching a set of
   // invariants combined with `and` or `or` or partially invariant instructions,
   // the combining operation determines the best direction to unswitch: we want
   // to unswitch the direction that will collapse the branch.
   bool Direction = true;
   int ClonedSucc = 0;
   if (!FullUnswitch) {
     Value *Cond = skipTrivialSelect(BI->getCondition());
     (void)Cond;
     assert(((match(Cond, m_LogicalAnd()) ^ match(Cond, m_LogicalOr())) ||
             PartiallyInvariant) &&
-           "Only `or`, `and`, an `select`, partially invariant instructions "
+           "Only `or`, `and` and partially invariant instructions "
            "can combine invariants being unswitched.");
     if (!match(Cond, m_LogicalOr())) {
       if (match(Cond, m_LogicalAnd()) ||
           (PartiallyInvariant && !PartialIVInfo.KnownValue->isOneValue())) {
         Direction = false;
         ClonedSucc = 1;
       }
     }
   }
 
   BasicBlock *RetainedSuccBB =
-      BI ? BI->getSuccessor(1 - ClonedSucc) : SI->getDefaultDest();
+      BI ? BI->getSuccessor(1 - ClonedSucc) : SLI ? SLI->getParent() : SWI->getDefaultDest();
   SmallSetVector<BasicBlock *, 4> UnswitchedSuccBBs;
   if (BI)
     UnswitchedSuccBBs.insert(BI->getSuccessor(ClonedSucc));
+  else if (SLI)
+    UnswitchedSuccBBs.insert(ParentBB);
   else
-    for (auto Case : SI->cases())
+    for (auto Case : SWI->cases())
       if (Case.getCaseSuccessor() != RetainedSuccBB)
         UnswitchedSuccBBs.insert(Case.getCaseSuccessor());
 
-  assert(!UnswitchedSuccBBs.count(RetainedSuccBB) &&
-         "Should not unswitch the same successor we are retaining!");
-
   // The branch should be in this exact loop. Any inner loop's invariant branch
   // should be handled by unswitching that inner loop. The caller of this
   // routine should filter out any candidates that remain (but were skipped for
   // whatever reason).
   assert(LI.getLoopFor(ParentBB) == &L && "Branch in an inner loop!");
 
   // Compute the parent loop now before we start hacking on things.
   Loop *ParentL = L.getParentLoop();
if (FreezeLoopUnswitchCond) {
     SafetyInfo.computeLoopSafetyInfo(&L);
     InsertFreeze = !SafetyInfo.isGuaranteedToExecute(TI, &DT, &L);
   }
 
   // If the edge from this terminator to a successor dominates that successor,
   // store a map from each block in its dominator subtree to it. This lets us
   // tell when cloning for a particular successor if a block is dominated by
   // some *other* successor with a single data structure. We use this to
-  // significantly reduce cloning.
+  // significantly reduce cloning. We must clone everything when unswitching
+  // a select instruction.
   SmallDenseMap<BasicBlock *, BasicBlock *, 16> DominatingSucc;
+  if (!SLI)
     for (auto *SuccBB : llvm::concat<BasicBlock *const>(
              makeArrayRef(RetainedSuccBB), UnswitchedSuccBBs))
       if (SuccBB->getUniquePredecessor() ||
           llvm::all_of(predecessors(SuccBB), [&](BasicBlock *PredBB) {
             return PredBB == ParentBB || DT.dominates(SuccBB, PredBB);
           }))
         visitDomSubTree(DT, SuccBB, [&](BasicBlock *BB) {
           DominatingSucc[BB] = SuccBB;
           return true;
         });
 
   // Split the preheader, so that we know that there is a safe place to insert
   // the conditional branch. We will change the preheader to have a conditional
   // branch on LoopCond. The original preheader will become the split point
   // between the unswitched versions, and we will have a new preheader for the
   // original loop.
   BasicBlock *SplitBB = L.getLoopPreheader();
   BasicBlock *LoopPH = SplitEdge(SplitBB, L.getHeader(), &DT, &LI, MSSAU);
 
   // Keep track of the dominator tree updates needed.
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
   SmallVector<DominatorTree::UpdateType, 4> DTUpdates;
 
   // Clone the loop for each unswitched successor.
   SmallVector<std::unique_ptr<ValueToValueMapTy>, 4> VMaps;
   VMaps.reserve(UnswitchedSuccBBs.size());
   SmallDenseMap<BasicBlock *, BasicBlock *, 4> ClonedPHs;
   for (auto *SuccBB : UnswitchedSuccBBs) {
     VMaps.emplace_back(new ValueToValueMapTy());
     ClonedPHs[SuccBB] = buildClonedLoopBlocks(
         L, LoopPH, SplitBB, ExitBlocks, ParentBB, SuccBB, RetainedSuccBB,
-        DominatingSucc, *VMaps.back(), DTUpdates, AC, DT, LI, MSSAU, SE);
+        DominatingSucc, SLI, *VMaps.back(), DTU, AC, DT, LI, MSSAU, SE);
   }
 
   // Drop metadata if we may break its semantics by moving this instr into the
   // split block.
   if (TI.getMetadata(LLVMContext::MD_make_implicit)) {
     if (DropNonTrivialImplicitNullChecks)
       // Do not spend time trying to understand if we can keep it, just drop it
       // to save compile time.
       TI.setMetadata(LLVMContext::MD_make_implicit, nullptr);
     else {
       // It is only legal to preserve make.implicit metadata if we are
       // guaranteed no reach implicit null check after following this branch.
       ICFLoopSafetyInfo SafetyInfo;
       SafetyInfo.computeLoopSafetyInfo(&L);
       if (!SafetyInfo.isGuaranteedToExecute(TI, &DT, &L))
         TI.setMetadata(LLVMContext::MD_make_implicit, nullptr);
     }
   }
 
   // The stitching of the branched code back together depends on whether we're
   // doing full unswitching or not with the exception that we always want to
   // nuke the initial terminator placed in the split block.
   SplitBB->getTerminator()->eraseFromParent();
   if (FullUnswitch) {
+    Instruction *NewTI;
+
+    if (SLI) {
+      BasicBlock *ClonedPH = ClonedPHs.begin()->second;
+      NewTI = BranchInst::Create(ClonedPH, LoopPH, SLI->getCondition());
+      SplitBB->getInstList().push_back(NewTI);
+
+      Value *Cond = SLI->getCondition();
+      if (InsertFreeze) {
+        if (!isGuaranteedNotToBeUndefOrPoison(Cond, &AC, BI, &DT))
+          Cond = new FreezeInst(Cond, Cond->getName() + ".fr", BI);
+      }
+      DTU.applyUpdates({{DominatorTree::Insert, SplitBB, ClonedPH}});
+
+      // Replace the retained select with the false operand
+      SLI->replaceAllUsesWith(SLI->getOperand(2));
+      SLI->eraseFromParent();
+
+      // Fold terminators that used the select instruction and now have a
+      // constant condition. This can reduce the size of the CFG and make
+      // further unswitching cheaper. Terminators in the new unswitched
+      // loop will be folded in LoopSimplifyCFG.
+      for (BasicBlock *BB : L.getBlocks())
+        ConstantFoldTerminator(BB, false, nullptr, &DTU);
+    } else {
+      assert((BI || SWI) && "Must either be a branch, select or switch!");
+
       // Splice the terminator from the original loop and rewrite its
       // successors.
       SplitBB->getInstList().splice(SplitBB->end(), ParentBB->getInstList(), TI);
 
       // Keep a clone of the terminator for MSSA updates.
-    Instruction *NewTI = TI.clone();
+      NewTI = TI.clone();
       ParentBB->getInstList().push_back(NewTI);
 
       // First wire up the moved terminator to the preheaders.
       if (BI) {
         BasicBlock *ClonedPH = ClonedPHs.begin()->second;
         BI->setSuccessor(ClonedSucc, ClonedPH);
         BI->setSuccessor(1 - ClonedSucc, LoopPH);
         Value *Cond = skipTrivialSelect(BI->getCondition());
         if (InsertFreeze) {
           if (!isGuaranteedNotToBeUndefOrPoison(Cond, &AC, BI, &DT))
             Cond = new FreezeInst(Cond, Cond->getName() + ".fr", BI);
         }
         BI->setCondition(Cond);
-      DTUpdates.push_back({DominatorTree::Insert, SplitBB, ClonedPH});
+        DTU.applyUpdates({{DominatorTree::Insert, SplitBB, ClonedPH}});
       } else {
-      assert(SI && "Must either be a branch or switch!");
-
         // Walk the cases and directly update their successors.
-      assert(SI->getDefaultDest() == RetainedSuccBB &&
+        assert(SWI->getDefaultDest() == RetainedSuccBB &&
                "Not retaining default successor!");
-      SI->setDefaultDest(LoopPH);
-      for (const auto &Case : SI->cases())
+        SWI->setDefaultDest(LoopPH);
+        for (const auto &Case : SWI->cases())
           if (Case.getCaseSuccessor() == RetainedSuccBB)
             Case.setSuccessor(LoopPH);
           else
             Case.setSuccessor(ClonedPHs.find(Case.getCaseSuccessor())->second);
 
         if (InsertFreeze) {
-        auto Cond = SI->getCondition();
-        if (!isGuaranteedNotToBeUndefOrPoison(Cond, &AC, SI, &DT))
-          SI->setCondition(new FreezeInst(Cond, Cond->getName() + ".fr", SI));
+          auto Cond = SWI->getCondition();
+          if (!isGuaranteedNotToBeUndefOrPoison(Cond, &AC, SWI, &DT))
+            SWI->setCondition(new FreezeInst(Cond, Cond->getName() + ".fr", SWI));
         }
         // We need to use the set to populate domtree updates as even when there
         // are multiple cases pointing at the same successor we only want to
         // remove and insert one edge in the domtree.
         for (BasicBlock *SuccBB : UnswitchedSuccBBs)
-        DTUpdates.push_back(
-            {DominatorTree::Insert, SplitBB, ClonedPHs.find(SuccBB)->second});
+          DTU.applyUpdates(
+              {{DominatorTree::Insert, SplitBB, ClonedPHs.find(SuccBB)->second}});
+      }
     }
 
     if (MSSAU) {
-      DT.applyUpdates(DTUpdates);
-      DTUpdates.clear();
+      DTU.flush();
 
       // Remove all but one edge to the retained block and all unswitched
       // blocks. This is to avoid having duplicate entries in the cloned Phis,
       // when we know we only keep a single edge for each case.
       MSSAU->removeDuplicatePhiEdgesBetween(ParentBB, RetainedSuccBB);
       for (BasicBlock *SuccBB : UnswitchedSuccBBs)
         MSSAU->removeDuplicatePhiEdgesBetween(ParentBB, SuccBB);
 
       for (auto &VMap : VMaps)
         MSSAU->updateForClonedLoop(LBRPO, ExitBlocks, *VMap,
                                    /*IgnoreIncomingWithNoClones=*/true);
       MSSAU->updateExitBlocksForClonedLoop(ExitBlocks, VMaps, DT);
 
       // Remove all edges to unswitched blocks.
       for (BasicBlock *SuccBB : UnswitchedSuccBBs)
         MSSAU->removeEdge(ParentBB, SuccBB);
     }
 
     // Now unhook the successor relationship as we'll be replacing
     // the terminator with a direct branch. This is much simpler for branches
-    // than switches so we handle those first.
+    // than switches so we handle those first. No work required for selects.
     if (BI) {
       // Remove the parent as a predecessor of the unswitched successor.
       assert(UnswitchedSuccBBs.size() == 1 &&
              "Only one possible unswitched block for a branch!");
       BasicBlock *UnswitchedSuccBB = *UnswitchedSuccBBs.begin();
       UnswitchedSuccBB->removePredecessor(ParentBB,
                                           /*KeepOneInputPHIs*/ true);
-      DTUpdates.push_back({DominatorTree::Delete, ParentBB, UnswitchedSuccBB});
-    } else {
+      DTU.applyUpdates({{DominatorTree::Delete, ParentBB, UnswitchedSuccBB}});
+    } else if (SWI) {
       // Note that we actually want to remove the parent block as a predecessor
       // of *every* case successor. The case successor is either unswitched,
       // completely eliminating an edge from the parent to that successor, or it
       // is a duplicate edge to the retained successor as the retained successor
       // is always the default successor and as we'll replace this with a direct
       // branch we no longer need the duplicate entries in the PHI nodes.
-      SwitchInst *NewSI = cast<SwitchInst>(NewTI);
-      assert(NewSI->getDefaultDest() == RetainedSuccBB &&
+      SwitchInst *NewSWI = cast<SwitchInst>(NewTI);
+      assert(NewSWI->getDefaultDest() == RetainedSuccBB &&
              "Not retaining default successor!");
-      for (const auto &Case : NewSI->cases())
+      for (const auto &Case : NewSWI->cases())
         Case.getCaseSuccessor()->removePredecessor(
             ParentBB,
             /*KeepOneInputPHIs*/ true);
 
       // We need to use the set to populate domtree updates as even when there
       // are multiple cases pointing at the same successor we only want to
       // remove and insert one edge in the domtree.
       for (BasicBlock *SuccBB : UnswitchedSuccBBs)
-        DTUpdates.push_back({DominatorTree::Delete, ParentBB, SuccBB});
+        DTU.applyUpdates({{DominatorTree::Delete, ParentBB, SuccBB}});
     }
 
+    if (!SLI) {
       // After MSSAU update, remove the cloned terminator instruction NewTI.
       ParentBB->getTerminator()->eraseFromParent();
 
       // Create a new unconditional branch to the continuing block (as opposed to
       // the one cloned).
       BranchInst::Create(RetainedSuccBB, ParentBB);
+    }
   } else {
     assert(BI && "Only branches have partial unswitching.");
     assert(UnswitchedSuccBBs.size() == 1 &&
            "Only one possible unswitched block for a branch!");
     BasicBlock *ClonedPH = ClonedPHs.begin()->second;
     // When doing a partial unswitch, we have to do a bit more work to build up
     // the branch in the split block.
     if (PartiallyInvariant)
       buildPartialInvariantUnswitchConditionalBranch(
           *SplitBB, Invariants, Direction, *ClonedPH, *LoopPH, L, MSSAU);
     else {
       buildPartialUnswitchConditionalBranch(
           *SplitBB, Invariants, Direction, *ClonedPH, *LoopPH,
           FreezeLoopUnswitchCond, BI, &AC, DT);
     }
-    DTUpdates.push_back({DominatorTree::Insert, SplitBB, ClonedPH});
+    DTU.applyUpdates({{DominatorTree::Insert, SplitBB, ClonedPH}});
 
     if (MSSAU) {
-      DT.applyUpdates(DTUpdates);
-      DTUpdates.clear();
+      DTU.flush();
 
       // Perform MSSA cloning updates.
       for (auto &VMap : VMaps)
         MSSAU->updateForClonedLoop(LBRPO, ExitBlocks, *VMap,
                                    /*IgnoreIncomingWithNoClones=*/true);
       MSSAU->updateExitBlocksForClonedLoop(ExitBlocks, VMaps, DT);
     }
   }
 
   // Apply the updates accumulated above to get an up-to-date dominator tree.
-  DT.applyUpdates(DTUpdates);
+  DTU.flush();
 
   // Now that we have an accurate dominator tree, first delete the dead cloned
   // blocks so that we can accurately build any cloned loops. It is important to
   // not delete the blocks from the original loop yet because we still want to
   // reference the original loop to understand the cloned loop's structure.
   deleteDeadClonedBlocks(L, ExitBlocks, VMaps, DT, MSSAU);
 
   // Build the cloned loop structure itself. This may be substantially
if (UpdatedL->getParentLoop() == ParentL)
       SibLoops.push_back(UpdatedL);
   UnswitchCB(IsStillLoop, PartiallyInvariant, SibLoops);
 
   if (MSSAU && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();
 
   if (BI)
     ++NumBranches;
+  else if (SLI)
+    ++NumSelects;
   else
     ++NumSwitches;
+
 }
 
 /// Recursively compute the cost of a dominator subtree based on the per-block
 /// cost map provided.
 ///
-/// The recursive computation is memozied into the provided DT-indexed cost map
+/// The recursive computation is memoized into the provided DT-indexed cost map
 /// to allow querying it for most nodes in the domtree without it becoming
 /// quadratic.
 static InstructionCost computeDomSubtreeCost(
     DomTreeNode &N,
     const SmallDenseMap<BasicBlock *, InstructionCost, 4> &BBCostMap,
     SmallDenseMap<DomTreeNode *, InstructionCost, 4> &DTCostMap) {
   // Don't accumulate cost (or recurse through) blocks not in our block cost
   // map and thus not part of the duplication cost being considered.

 static BranchInst *turnGuardIntoBranch(IntrinsicInst *GI, Loop &L,
                                        DominatorTree &DT, LoopInfo &LI,
                                        MemorySSAUpdater *MSSAU) {
   SmallVector<DominatorTree::UpdateType, 4> DTUpdates;
   LLVM_DEBUG(dbgs() << "Turning " << *GI << " into a branch.\n");
   BasicBlock *CheckBB = GI->getParent();
 
   if (MSSAU && VerifyMemorySSA)
      MSSAU->getMemorySSA()->verifyMemorySSA();
 
   // Remove all CheckBB's successors from DomTree. A block can be seen among
   // successors more than once, but for DomTree it should be added only once.
   SmallPtrSet<BasicBlock *, 4> Successors;
   for (auto *Succ : successors(CheckBB))
     if (Successors.insert(Succ).second)
       DTUpdates.push_back({DominatorTree::Delete, CheckBB, Succ});
 
   Instruction *DeoptBlockTerm =
static int CalculateUnswitchCostMultiplier(
     const DominatorTree &DT,
     ArrayRef<NonTrivialUnswitchCandidate> UnswitchCandidates) {
 
   // Guards and other exiting conditions do not contribute to exponential
   // explosion as soon as they dominate the latch (otherwise there might be
   // another path to the latch remaining that does not allow to eliminate the
   // loop copy on unswitch).
   const BasicBlock *Latch = L.getLoopLatch();
+  if (TI.isTerminator()) {
     const BasicBlock *CondBlock = TI.getParent();
     if (DT.dominates(CondBlock, Latch) &&
         (isGuard(&TI) ||
          llvm::count_if(successors(&TI), [&L](const BasicBlock *SuccBB) {
            return L.contains(SuccBB);
          }) <= 1)) {
       NumCostMultiplierSkipped++;
       return 1;
     }
+  }
 
   auto *ParentL = L.getParentLoop();
   int SiblingsCount = (ParentL ? ParentL->getSubLoopsVector().size()
                                : std::distance(LI.begin(), LI.end()));
   // Count amount of clones that all the candidates might cause during
   // unswitching. Branch/guard counts as 1, switch counts as log2 of its cases.
   int UnswitchedClones = 0;
   for (auto Candidate : UnswitchCandidates) {
if (CollectGuards)
         if (isGuard(&I)) {
           auto *Cond =
               skipTrivialSelect(cast<IntrinsicInst>(&I)->getArgOperand(0));
           // TODO: Support AND, OR conditions and partial unswitching.
           if (!isa<Constant>(Cond) && L.isLoopInvariant(Cond))
             UnswitchCandidates.push_back({&I, {Cond}});
         }
 
+    for (Instruction &I : *BB) {
+      if (auto *SI = dyn_cast<SelectInst>(&I)) {
+        if (L.isLoopInvariant(SI->getCondition()) && !isa<Constant>(SI->getCondition()))
+          UnswitchCandidates.push_back({SI, {SI->getCondition()}});
+      }
+    }
+
     if (auto *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
       // We can only consider fully loop-invariant switch conditions as we need
       // to completely eliminate the switch after unswitching.
       if (!isa<Constant>(SI->getCondition()) &&
           L.isLoopInvariant(SI->getCondition()) && !BB->getUniqueSuccessor())
         UnswitchCandidates.push_back({SI, {SI->getCondition()}});
       continue;
     }
static NonTrivialUnswitchCandidate findBestNonTrivialUnswitchCandidate(
   // This requires memoizing each dominator subtree to avoid redundant work.
   //
   // FIXME: Need to actually do the number of candidates part above.
   SmallDenseMap<DomTreeNode *, InstructionCost, 4> DTCostMap;
   // Given a terminator which might be unswitched, computes the non-duplicated
   // cost for that terminator.
   auto ComputeUnswitchedCost = [&](Instruction &TI,
                                    bool FullUnswitch) -> InstructionCost {
+    // Unswitching selects require copying the entire loop.
+    if (isa<SelectInst>(&TI)) {
+      return LoopCost;
+    }
+
     BasicBlock &BB = *TI.getParent();
     SmallPtrSet<BasicBlock *, 4> Visited;
 
     InstructionCost Cost = 0;
     for (BasicBlock *SuccBB : successors(&BB)) {
       // Don't count successors more than once.
       if (!Visited.insert(SuccBB).second)
         continue;
static bool unswitchBestCondition(
 
   // If the best candidate is a guard, turn it into a branch.
   if (isGuard(Best.TI))
     Best.TI =
         turnGuardIntoBranch(cast<IntrinsicInst>(Best.TI), L, DT, LI, MSSAU);
 
   LLVM_DEBUG(dbgs() << "  Unswitching non-trivial (cost = " << Best.Cost
                     << ") terminator: " << *Best.TI << "\n");
   unswitchNontrivialInvariants(L, *Best.TI, Best.Invariants, PartialIVInfo, DT,
                                LI, AC, UnswitchCB, SE, MSSAU, DestroyLoopCB);
   return true;
 }
 
 /// Unswitch control flow predicated on loop invariant conditions.
 ///
 /// This first hoists all branches or switches which are trivial (IE, do not
 /// require duplicating any part of the loop) out of the loop body. It then
 /// looks at other loop invariant control flows and tries to unswitch those as

llvm/test/Transforms/SimpleLoopUnswitch/2010-11-18-LCSSA.ll

 ; RUN: opt < %s -simple-loop-unswitch -verify-memoryssa
 ; PR8622
+
+; Can't unswitch `%call1 = select` because `%tobool.i` is defined in the loop. `tobool.i` could
+; have been hoisted in the LICM pass, but LoopUnswitching pass does not do LICM.
+
 @g_38 = external global i32, align 4
 
 define void @func_67(i32 %p_68.coerce) nounwind {
+; CHECK-LABEL: @func_67
+; CHECK: select
+
 entry:
   br i1 true, label %for.end12, label %bb.nph
 
 bb.nph:                                           ; preds = %entry
   %g_38.promoted = load i32, i32* @g_38
   br label %for.body
 
 for.body:                                         ; preds = %for.cond, %bb.nph

llvm/test/Transforms/SimpleLoopUnswitch/2012-05-20-Phi.ll

 ; RUN: opt < %s -simple-loop-unswitch -verify-memoryssa -disable-output
 ; PR12887
 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"
 
 @a = common global i32 0, align 4
 @c = common global i32 0, align 4
 @b = common global i32 0, align 4
 
 define void @func() noreturn nounwind uwtable {
+; CHECK-LABEL: @func
+; CHECK-NOT: select
+; CHECK: br i1 %tobool
+
 entry:
   %0 = load i32, i32* @a, align 4
   %tobool = icmp eq i32 %0, 0
   %1 = load i32, i32* @b, align 4
   br label %while.body
 
 while.body:                                       ; preds = %while.body, %entry
   %d.0 = phi i8 [ undef, %entry ], [ %conv2, %while.body ]
   %conv = sext i8 %d.0 to i32
   %cond = select i1 %tobool, i32 0, i32 %conv
   %conv11 = zext i8 %d.0 to i32
   %add = add i32 %1, %conv11
   %conv2 = trunc i32 %add to i8
   br label %while.body
 }

llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch-freeze.ll

a.latch:
   br label %a.header
 
 exit:
   ret void
 }
 
 define i32 @test_partial_unswitch_all_conds_guaranteed_non_poison(i1 noundef %c.1, i1 noundef %c.2) {
 ; CHECK-LABEL: @test_partial_unswitch_all_conds_guaranteed_non_poison(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = and i1 [[C_1:%.*]], [[C_2:%.*]]
-; CHECK-NEXT:    br i1 [[TMP0]], label [[ENTRY_SPLIT:%.*]], label [[ENTRY_SPLIT_US:%.*]]
-; CHECK:       entry.split.us:
-; CHECK-NEXT:    br label [[LOOP_US:%.*]]
-; CHECK:       loop.us:
-; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @a()
-; CHECK-NEXT:    br label [[EXIT_SPLIT_US:%.*]]
-; CHECK:       exit.split.us:
-; CHECK-NEXT:    br label [[EXIT:%.*]]
-; CHECK:       entry.split:
-; CHECK-NEXT:    br label [[LOOP:%.*]]
-; CHECK:       loop:
-; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @a()
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 true, i1 true, i1 false
-; CHECK-NEXT:    br i1 [[SEL]], label [[LOOP]], label [[EXIT_SPLIT:%.*]]
-; CHECK:       exit.split:
-; CHECK-NEXT:    br label [[EXIT]]
-; CHECK:       exit:
-; CHECK-NEXT:    ret i32 0
-;
+; CHECK-NEXT: entry:
+; CHECK-NEXT: br i1 %c.1, label [[ENTRY_SPLIT_US:%.*]], label [[ENTRY_SPLIT:%.*]]
+; CHECK: entry.split.us:
+; CHECK-NEXT; br i1 %c.2, label [[ENTRY_SPLIT_US_SPLIT_US:%.*]], label [[ENTRY_SPLIT_US_SPLIT:%.*]]
+; CHECK: entry.split.us.split.us:
+; CHECK-NEXT: br label [[LOOP_US_US:%.*]]
+; CHECK: loop.us.us:
+; CHECK-NEXT: [[TMP1:%.*]] = call i32 @a()
+; CHECK-NEXT: br label [[LOOP_US_US]]
+; CHECK: entry.split.us.split:
+; CHECK-NEXT: br label [[LOOP_US:%.*]]
+; CHECK: loop.us:
+; CHECK-NEXT: [[TMP2:%.*]] = call i32 @a()
+; CHECK-NEXT: br label [[EXIT_SPLIT_US:%.*]]
+; CHECK: exit.split.us:
+; CHECK-NEXT: br label [[EXIT:%.*]]
+; CHECK: entry.split:
+; CHECK-NEXT: br label [[LOOP:%.*]]
+; CHECK: loop:
+; CHECK-NEXT: [[TMP3:%.*]] = call i32 @a()
+; CHECK-NEXT: br label [[EXIT_SPLIT:%.*]]
+; CHECK: exit.split:
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: exit:
+; CHECK-NEXT: ret i32 0
+
 entry:
   br label %loop
 
 loop:
   call i32 @a()
   %sel = select i1 %c.1, i1 %c.2, i1 false
   br i1 %sel, label %loop, label %exit
 
 exit:
   ret i32 0
 }

llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch-trivial-select.ll

 ; CHECK-LABEL: @unswitch_trivial_select_cmp_outside(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C:%.*]] = icmp ult i32 [[X:%.*]], 100
 ; CHECK-NEXT:    br i1 [[C]], label [[ENTRY_SPLIT_US:%.*]], label [[ENTRY_SPLIT:%.*]]
 ; CHECK:       entry.split.us:
 ; CHECK-NEXT:    br label [[LOOP_US:%.*]]
 ; CHECK:       loop.us:
 ; CHECK-NEXT:    [[P_US:%.*]] = phi i32 [ 0, [[ENTRY_SPLIT_US]] ], [ 35, [[LOOP_US]] ]
-; CHECK-NEXT:    br label [[LOOP_US]]
+; CHECK-NEXT:    br i1 true, label [[LOOP_US]], label [[EXIT_SPLIT_US:%.*]]
+; CHECK:       exit.split.us:
+; CHECK-NEXT:    [[LCSSA_US:%.*]] = phi i32 [ [[P_US]], [[LOOP_US]] ]
+; CHECK-NEXT:    br label %exit
 ; CHECK:       entry.split:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 0, [[ENTRY_SPLIT]] ]
-; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 false, i1 true, i1 false
+; CHECK-NEXT:    br label [[EXIT_SPLIT:%.*]]
+; CHECK:       exit.split:
+; CHECK-NEXT:    [[LCSSA:%.*]] = phi i32 [ 0, %loop ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[LCSSA:%.*]] = phi i32 [ [[P]], [[LOOP]] ]
-; CHECK-NEXT:    ret i32 [[LCSSA]]
+; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[LCSSA]], [[EXIT_SPLIT]] ], [ [[LCSSA_US]], [[EXIT_SPLIT_US]] ]
+; CHECK-NEXT:    ret i32 [[RET]]
 ;
 entry:
   %c = icmp ult i32 %x, 100
   br label %loop
 
 loop:
   %p = phi i32 [ 0, %entry ], [ 35, %loop ]
   %spec.select = select i1 %c, i1 true, i1 false
   br i1 %spec.select, label %loop, label %exit
 
 exit:
   %lcssa = phi i32 [ %p, %loop ]
   ret i32 %lcssa
 }

llvm/test/Transforms/SimpleLoopUnswitch/pr32818.ll

+; Check that the call doesn't get removed even if
+; it has no uses. It could have side-effects.
+; RUN: opt -passes='loop(simple-loop-unswitch<nontrivial>),verify<loops>' -S < %s | FileCheck %s
+; RUN: opt -passes='loop-mssa(simple-loop-unswitch<nontrivial>),verify<loops>' -S < %s | FileCheck %s
+; RUN: opt -simple-loop-unswitch -enable-nontrivial-unswitch -verify-memoryssa -S < %s | FileCheck %s
+
+define i32 @tinkywinky(i8 %patatino) {
+; CHECK-LABEL: @tinky
+; CHECK-NOT: select
+; CHECK: br i1 %cmp1
+
+  %cmp1 = icmp slt i8 %patatino, 5
+  br label %body
+body:
+  %i = select i1 %cmp1, i8 6, i8 undef
+  br i1 true, label %body, label %end
+end:
+  %split = phi i8 [ %i, %body ]
+  %conv4 = sext i8 %split to i32
+; CHECK: tail call fastcc i32 @fn5(
+  %call = tail call fastcc i32 @fn5(i32 %conv4)
+  ret i32 0
+}
+declare fastcc i32 @fn5(i32 returned) unnamed_addr

llvm/test/Transforms/SimpleLoopUnswitch/unswitch-equality-undef.ll

+; REQUIRES: asserts
+; RUN: opt < %s -instcombine -licm -simple-loop-unswitch -enable-new-pm=0 -verify-memoryssa -disable-output -stats 2>&1| FileCheck %s
+; Check no loop unswitch is done because unswitching of equality expr with
+; undef is unsafe before the freeze patch is committed.
+; CHECK-NOT: Number of branches unswitched
+
+define void @ham(i64 %arg) local_unnamed_addr {
+bb:
+  %tmp = icmp eq i64 %arg, 0
+  br i1 %tmp, label %bb3, label %bb1
+
+bb1:                                              ; preds = %bb
+  %tmp2 = load volatile i64, i64* @global, align 8
+  br label %bb3
+
+bb3:                                              ; preds = %bb1, %bb
+  %tmp4 = phi i64 [ %tmp2, %bb1 ], [ undef, %bb ]
+  %tmp5 = load i64, i64* @global.1, align 8
+  br label %bb6
+
+bb6:                                              ; preds = %bb21, %bb3
+  %tmp7 = phi i64 [ 3, %bb21 ], [ %tmp5, %bb3 ]
+  %tmp8 = phi i64 [ %tmp25, %bb21 ], [ 0, %bb3 ]
+  %tmp9 = icmp eq i64 %tmp7, %arg
+  br i1 %tmp9, label %bb10, label %bb28
+
+bb10:                                             ; preds = %bb6
+  %tmp11 = icmp eq i64 %tmp7, 0
+  br i1 %tmp11, label %bb21, label %bb12
+
+bb12:                                             ; preds = %bb10
+  %tmp13 = load i64, i64* @global.2, align 8
+  %tmp14 = add nsw i64 %tmp13, 1
+  store i64 %tmp14, i64* @global.2, align 8
+  %tmp15 = load i64, i64* @global.3, align 8
+  %tmp16 = icmp eq i64 %tmp15, %tmp4
+  br i1 %tmp16, label %bb17, label %bb21
+
+bb17:                                             ; preds = %bb12
+  %tmp18 = phi i64 [ %tmp15, %bb12 ]
+  %tmp19 = load i64, i64* @global.4, align 8
+  %tmp20 = add nsw i64 %tmp19, %tmp18
+  store i64 %tmp20, i64* @global.5, align 8
+  br label %bb29
+
+bb21:                                             ; preds = %bb12, %bb10
+  %tmp22 = load i64, i64* @global.3, align 8
+  %tmp23 = load volatile i64, i64* @global, align 8
+  %tmp24 = add nsw i64 %tmp23, %tmp22
+  store i64 %tmp24, i64* @global.5, align 8
+  store i64 3, i64* @global.1, align 8
+  %tmp25 = add nsw i64 %tmp8, 1
+  %tmp26 = load i64, i64* @global.6, align 8
+  %tmp27 = icmp slt i64 %tmp25, %tmp26
+  br i1 %tmp27, label %bb6, label %bb28
+
+bb28:                                             ; preds = %bb21, %bb6
+  br label %bb29
+
+bb29:                                             ; preds = %bb28, %bb17
+  ret void
+}
+
+define void @zot(i64 %arg, i64 %arg1) local_unnamed_addr {
+bb:
+  %tmp = icmp eq i64 %arg, 0
+  %tmp2 = select i1 %tmp, i64 %arg1, i64 undef
+  %tmp3 = load i64, i64* @global.1, align 8
+  br label %bb4
+
+bb4:                                              ; preds = %bb19, %bb
+  %tmp5 = phi i64 [ 3, %bb19 ], [ %tmp3, %bb ]
+  %tmp6 = phi i64 [ %tmp23, %bb19 ], [ 0, %bb ]
+  %tmp7 = icmp eq i64 %tmp5, %arg
+  br i1 %tmp7, label %bb8, label %bb26
+
+bb8:                                              ; preds = %bb4
+  %tmp9 = icmp eq i64 %tmp5, 0
+  br i1 %tmp9, label %bb19, label %bb10
+
+bb10:                                             ; preds = %bb8
+  %tmp11 = load i64, i64* @global.2, align 8
+  %tmp12 = add nsw i64 %tmp11, 1
+  store i64 %tmp12, i64* @global.2, align 8
+  %tmp13 = load i64, i64* @global.3, align 8
+  %tmp14 = icmp eq i64 %tmp13, %tmp2
+  br i1 %tmp14, label %bb15, label %bb19
+
+bb15:                                             ; preds = %bb10
+  %tmp16 = phi i64 [ %tmp13, %bb10 ]
+  %tmp17 = load i64, i64* @global.4, align 8
+  %tmp18 = add nsw i64 %tmp17, %tmp16
+  store i64 %tmp18, i64* @global.5, align 8
+  br label %bb27
+
+bb19:                                             ; preds = %bb10, %bb8
+  %tmp20 = load i64, i64* @global.3, align 8
+  %tmp21 = load volatile i64, i64* @global, align 8
+  %tmp22 = add nsw i64 %tmp21, %tmp20
+  store i64 %tmp22, i64* @global.5, align 8
+  store i64 3, i64* @global.1, align 8
+  %tmp23 = add nsw i64 %tmp6, 1
+  %tmp24 = load i64, i64* @global.6, align 8
+  %tmp25 = icmp slt i64 %tmp23, %tmp24
+  br i1 %tmp25, label %bb4, label %bb26
+
+bb26:                                             ; preds = %bb19, %bb4
+  br label %bb27
+
+bb27:                                             ; preds = %bb26, %bb15
+  ret void
+}
+
+@global = common global i64 0, align 8
+@global.1 = common global i64 0, align 8
+@global.2 = common global i64 0, align 8
+@global.3 = common global i64 0, align 8
+@global.4 = common global i64 0, align 8
+@global.5 = common global i64 0, align 8
+@global.6 = common global i64 0, align 8
+
+

llvm/test/Transforms/SimpleLoopUnswitch/unswitch-select.ll

+; RUN: opt -passes='loop(simple-loop-unswitch<nontrivial>),verify<loops>' -S < %s | FileCheck %s
+; RUN: opt -passes='loop-mssa(simple-loop-unswitch<nontrivial>),verify<loops>' -S < %s | FileCheck %s
+; RUN: opt -simple-loop-unswitch -enable-nontrivial-unswitch -verify-memoryssa -S < %s | FileCheck %s
+
+define i32 @test(i1 zeroext %x, i32 %a) local_unnamed_addr {
+; CHECK-LABEL: define i32 @test(i1 zeroext %x, i32 %a) local_unnamed_addr {
+; CHECK-NOT: select
+; CHECK: br i1 %x
+
+entry:
+  br label %while.cond
+
+while.cond:                                       ; preds = %while.body, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.body ]
+  %s.0 = phi i32 [ %a, %entry ], [ %add, %while.body ]
+  %cmp = icmp slt i32 %i.0, 10000
+  br i1 %cmp, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.cond
+  %cond = select i1 %x, i32 %a, i32 %i.0
+  %add = add nsw i32 %s.0, %cond
+  %inc = add nsw i32 %i.0, 1
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  %s.0.lcssa = phi i32 [ %s.0, %while.cond ]
+  ret i32 %s.0.lcssa
+}
+
+define i32 @cant_unswitch(i32 %a) local_unnamed_addr {
+; CHECK-LABEL: @cant_unswitch
+; CHECK: select i1 %invariant_cmp
+
+entry:
+  br label %while.cond
+
+while.cond:                                       ; preds = %while.body, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.body ]
+  %s.0 = phi i32 [ %a, %entry ], [ %add, %while.body ]
+  %cmp = icmp slt i32 %i.0, 10000
+  br i1 %cmp, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.cond
+  %invariant_cmp = icmp ugt i32 %s.0, 100
+  %cond = select i1 %invariant_cmp, i32 %a, i32 %i.0
+  %add = add nsw i32 %s.0, %cond
+  %inc = add nsw i32 %i.0, 1
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  %s.0.lcssa = phi i32 [ %s.0, %while.cond ]
+  ret i32 %s.0.lcssa
+}
+