[SimpleLoopUnswitch] Fix introduction of UB when hoisted condition may be undef or poison

[aqjune]

Summary

Loop unswitch hoists branches on loop-invariant conditions. However, if this
condition is poison/undef and the branch wasn't originally reachable, loop
unswitch introduces UB (since the optimized code will branch on poison/undef and
the original one didn't)).
We fix this problem by freezing the condition to ensure we don't introduce UB.

We will now transform the following:

while (...) {
  if (C) { A }
  else   { B }
}

Into:

C' = freeze(C)
if (C') {
  while (...) { A }
} else {
  while (...) { B }
}

This patch fixes the root cause of the following bug reports (which use the old loop unswitch, but can be reproduced with minor changes in the code and -enable-nontrivial-unswitch):

• https://llvm.org/bugs/show_bug.cgi?id=27506
• https://llvm.org/bugs/show_bug.cgi?id=31652

[aqjune]

• Move IRBuilder::CreateFreezeAtDef from https://reviews.llvm.org/D29011

[filcab]

Is NeedFreeze always true? If so, why have the parameter?
If not, when is it not?

include/llvm/IR/IRBuilder.h

1718 ↗

(On Diff #86252)

Maybe add

if (isa<FreezeInst>(Arg))
  return Arg;

so we don't need to create a FreezeInst that will be immediately simplified in the next run of instsimplify (and avoids ReplaceAllUsesWith)?
Unless I missed something.

1734 ↗

(On Diff #86252)

What happens if we try to Freeze a non-Instruction, non-Argument Value subclass (any type of Constant?)?
From the name and location, I'm assuming this function should be fairly generic.

lib/Transforms/Scalar/LoopUnswitch.cpp

243 ↗

(On Diff #86252)

Why is it a default parameter here?

[aqjune]

include/llvm/IR/IRBuilder.h

1718 ↗

(On Diff #86252)

@filcab I think it is caller's job to check whether the value is simple enough and creating a new freeze is unnecessary. A function FreezeBranchCondition in this patch (which is in LoopUnswitch.cpp) does similar thing : first of all it checks whether the new freeze instruction is needed (by calling isGuaranteedNotToBeUndefOrPoison), and then calls this function (CreateFreezeAtDef).

[aqjune]

NeedFreeze is set to true in this patch, but it can have different value in upcoming patch (https://reviews.llvm.org/D29016).

[aqjune]

Rebased to svn commit 308173

[reames]

p.s. You know you're changing the old pass which isn't used in the new pass manager right? You may instead wish to focus on SimpleLoopUnswitch which is the new version.

include/llvm/IR/IRBuilder.h

1795 ↗

(On Diff #106917)

This is really not idiomatic for an IRBuilder function. The standard idioms is to just insert the requested instruction sequence at the specified insertion point. Please refactor to match that idiom and move other logic to caller or utility outside of IRBuilder.

lib/Transforms/Scalar/LoopUnswitch.cpp

229 ↗

(On Diff #106917)

Please leave this out of the current patch. It belongs in the one using the must execute logic.

I'd be open to combining them if you thought that was needed.

897 ↗

(On Diff #106917)

I think this can and should be simpler. If we need a freeze, just insert it into the end of the preheader. The complexity of hoisting to def doesn't seem warranted.

[aqjune]

• Target SimpleLoopUnswitch to fix introduction of UB
• Use ICFLoopSafetyInfo::isGuaranteedToExecute to not freeze condition if hoisted branch is guaranteed to be reachable

The second change was necessary to minimize the updates at unit tests.
(which was https://reviews.llvm.org/D29016 , but it needed only small amount of change so I moved it to here)

[reames]

LGTM

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2179

As a further enhancement (separate change), I think you can improve the logic for this case slightly. If you can prove that the original condition would have triggered UB if any of the invariant components had been poison, then you can avoid the freeze on the partially unswitched condition.

[aqjune]

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2179

IIUC, it is addressed by this patch because we could exploit that branching on poison is UB:

// want to partial unswitch cond2
for (..)
  if (cond1 && cond2) { A } else { B } // if cond2 is poison, cond1 && cond2 is also poison, so this is UB
=>
if (cond2) // freeze is not needed here
  for (..) { if (cond1) { A } }
else
  for (..) { B }

[aqjune]

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2179

(to clarify, it is assumed in the example that if(cond1 && cond2) is guaranteed to execute, meaning that there is no intervening branch or function call that may not return between the if statement and loop preheader )

[jdoerfert]

Thx for the patch!

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

186

Nit: InsertFreze

[aqjune]

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

186

Fixed via https://github.com/llvm/llvm-project/commit/1cb7ec870dc5c6b3900bfc832b910010dfac772b

[aqjune]

Reverted due to performance reason (https://github.com/llvm/llvm-project/commit/2b5a8976514de326bb84f0913d9d451089c11d22 ) ; LICM/CSE support for freeze is needed

[aqjune]

Now we have a pass for removing freezes in a loop (D77524). I can check whether the existing slowdowns can be addressed with it. I'll be a bit busy for a month, so it may proceed a bit slowly.
BTW, having an attribute for function arguments that states the value is already frozen will be really helpful for reducing the amount of introduced freezes (not only for loop unswitch, but also for other transformations that need freeze operations). I remember that it was called nonpoison in the previous llvm-dev discussion.
According to C/C++ standard, if indeterminate value is produced by an evaluation, the behavior is undefined except when the value was a family of char type:
C++14: https://timsong-cpp.github.io/cppwp/n4140/dcl.init#12
C++17: https://timsong-cpp.github.io/cppwp/n4659/dcl.init#12
C++11: https://timsong-cpp.github.io/cppwp/n3337/conv.lval#1 (wording is a bit different)
C11: https://port70.net/~nsz/c/c11/n1570.html#6.3.2.1p2
This means that it is valid to put the attribute unless the type is char or an aggregate with char when translating C/C++ to IR.
What do you think? @jdoerfert @reames This will help support other optimizations, such as supporting hoisting divisions from a loop when its divisor is a non-zero value derived from a function argument.

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

 #include "llvm/Analysis/GuardUtils.h"
 #include "llvm/Analysis/InstructionSimplify.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 "llvm/Analysis/Utils/Local.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"

 }
 
 /// Insert code to test a set of loop invariant values, and conditionally branch
 /// on them.
 static void buildPartialUnswitchConditionalBranch(BasicBlock &BB,
                                                   ArrayRef<Value *> Invariants,
                                                   bool Direction,
                                                   BasicBlock &UnswitchedSucc,
-                                                  BasicBlock &NormalSucc) {
+                                                  BasicBlock &NormalSucc,
+                                                  bool insertFreeze) {
   IRBuilder<> IRB(&BB);
-  
   Value *Cond = Direction ? IRB.CreateOr(Invariants) :
     IRB.CreateAnd(Invariants);
+  if (insertFreeze)
+    Cond = IRB.CreateFreeze(Cond, Cond->getName() + ".fr");
   IRB.CreateCondBr(Cond, Direction ? &UnswitchedSucc : &NormalSucc,
                    Direction ? &NormalSucc : &UnswitchedSucc);
 }
 
 /// Rewrite the PHI nodes in an unswitched loop exit basic block.
 ///
 /// Requires that the loop exit and unswitched basic block are the same, and
 /// that the exiting block was a unique predecessor of that block. Rewrites the
if (ExitDirection)
       assert(cast<Instruction>(BI.getCondition())->getOpcode() ==
                  Instruction::Or &&
              "Must have an `or` of `i1`s for the condition!");
     else
       assert(cast<Instruction>(BI.getCondition())->getOpcode() ==
                  Instruction::And &&
              "Must have an `and` of `i1`s for the condition!");
     buildPartialUnswitchConditionalBranch(*OldPH, Invariants, ExitDirection,
-                                          *UnswitchedBB, *NewPH);
+                                          *UnswitchedBB, *NewPH, false);
   }
 
   // Update the dominator tree with the added edge.
   DT.insertEdge(OldPH, UnswitchedBB);
 
   // After the dominator tree was updated with the added edge, update MemorySSA
   // if available.
   if (MSSAU) {
static void unswitchNontrivialInvariants(
   // containing an exit block and all nested loops.
   if (SE) {
     if (OuterExitL)
       SE->forgetLoop(OuterExitL);
     else
       SE->forgetTopmostLoop(&L);
   }
 
+  ICFLoopSafetyInfo SafetyInfo(&DT);
+  SafetyInfo.computeLoopSafetyInfo(&L);
+  bool 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.
   SmallDenseMap<BasicBlock *, BasicBlock *, 16> DominatingSucc;
   for (auto *SuccBB : llvm::concat<BasicBlock *const>(
            makeArrayRef(RetainedSuccBB), UnswitchedSuccBBs))
if (FullUnswitch) {
     Instruction *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);
+      if (insertFreeze) {
+        auto Cond = BI->getCondition();
+        if (!isGuaranteedNotToBeUndefOrPoison(Cond))
+          BI->setCondition(new FreezeInst(Cond, Cond->getName() + ".fr", BI));
+      }
+
       DTUpdates.push_back({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 &&
              "Not retaining default successor!");
       SI->setDefaultDest(LoopPH);
       for (auto &Case : SI->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))
+          SI->setCondition(new FreezeInst(Cond, Cond->getName() + ".fr", SI));
+      }
+
       // 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});
     }
 
if (FullUnswitch) {
     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.
     buildPartialUnswitchConditionalBranch(*SplitBB, Invariants, Direction,
-                                          *ClonedPH, *LoopPH);
+                                          *ClonedPH, *LoopPH, insertFreeze);
     DTUpdates.push_back({DominatorTree::Insert, SplitBB, ClonedPH});
 
     if (MSSAU) {
       DT.applyUpdates(DTUpdates);
       DTUpdates.clear();
 
       // Perform MSSA cloning updates.
       for (auto &VMap : VMaps)

llvm/test/Transforms/SimpleLoopUnswitch/exponential-nontrivial-unswitch-nested.ll

 ; 32 loop nests, fully unswitched
 ; LOOP32-COUNT-32: Loop at depth 1 containing:
 ; LOOP32-COUNT-32: Loop at depth 2 containing:
 ; LOOP32-COUNT-32: Loop at depth 3 containing:
 ; LOOP32-NOT:      Loop at depth {{[0-9]+}} containing:
 
 declare void @bar()
 
-define void @loop_nested3_conds5(i32* %addr, i1 %c1, i1 %c2, i1 %c3, i1 %c4, i1 %c5) {
+define void @loop_nested3_conds5(i32* %addr, i1 %c1i, i1 %c2i, i1 %c3i, i1 %c4i, i1 %c5i) {
 entry:
+  ; c1 ~ c5 are guaranteed to be never undef or poison.
+  %c1 = freeze i1 %c1i
+  %c2 = freeze i1 %c2i
+  %c3 = freeze i1 %c3i
+  %c4 = freeze i1 %c4i
+  %c5 = freeze i1 %c5i
   %addr1 = getelementptr i32, i32* %addr, i64 0
   %addr2 = getelementptr i32, i32* %addr, i64 1
   %addr3 = getelementptr i32, i32* %addr, i64 2
   br label %outer
 outer:
   %iv1 = phi i32 [0, %entry], [%iv1.next, %outer_latch]
   %iv1.next = add i32 %iv1, 1
   ;; skip nontrivial unswitch

llvm/test/Transforms/SimpleLoopUnswitch/exponential-nontrivial-unswitch-nested2.ll

 ; LOOP-MAX-NOT:      Loop at depth 1 containing:
 ; LOOP-MAX-COUNT-1: Loop at depth 2 containing:
 ; LOOP-MAX-NOT:      Loop at depth 2 containing:
 ; LOOP-MAX-COUNT-1: Loop at depth 3 containing:
 ; LOOP-MAX-NOT:      Loop at depth 3 containing:
 
 declare void @bar()
 
-define void @loop_nested3_conds5(i32* %addr, i1 %c1, i1 %c2, i1 %c3, i1 %c4, i1 %c5) {
+define void @loop_nested3_conds5(i32* %addr, i1 %c1i, i1 %c2i, i1 %c3i, i1 %c4i, i1 %c5i) {
 entry:
+  ; c1 ~ c5 are guaranteed to be never undef or poison.
+  %c1 = freeze i1 %c1i
+  %c2 = freeze i1 %c2i
+  %c3 = freeze i1 %c3i
+  %c4 = freeze i1 %c4i
+  %c5 = freeze i1 %c5i
   %addr1 = getelementptr i32, i32* %addr, i64 0
   %addr2 = getelementptr i32, i32* %addr, i64 1
   %addr3 = getelementptr i32, i32* %addr, i64 2
   br label %outer
 outer:
   %iv1 = phi i32 [0, %entry], [%iv1.next, %outer_latch]
   %iv1.next = add i32 %iv1, 1
   ;; skip nontrivial unswitch

llvm/test/Transforms/SimpleLoopUnswitch/exponential-switch-unswitch.ll

 ; LOOP-RELAX-NOT: Loop at depth 2 containing:
 ;
 ; Unswitched as much as it could (with multiplier disabled).
 ; LOOP-MAX-COUNT-56:     Loop at depth 1 containing:
 ; LOOP-MAX-NOT: Loop at depth 1 containing:
 ; LOOP-MAX-COUNT-111:     Loop at depth 2 containing:
 ; LOOP-MAX-NOT: Loop at depth 2 containing:
 
-define i32 @loop_switch(i32* %addr, i32 %c1, i32 %c2) {
+define i32 @loop_switch(i32* %addr, i32 %c1i, i32 %c2i) {
 entry:
+  ; c1, c2 are guaranteed to be never undef or poison.
+  %c1 = freeze i32 %c1i
+  %c2 = freeze i32 %c2i
   %addr1 = getelementptr i32, i32* %addr, i64 0
   %addr2 = getelementptr i32, i32* %addr, i64 1
   %check0 = icmp eq i32 %c2, 0
   %check1 = icmp eq i32 %c2, 31
   %check2 = icmp eq i32 %c2, 32
   %check3 = icmp eq i32 %c2, 33
   %check4 = icmp eq i32 %c2, 34
   br label %outer_loop

llvm/test/Transforms/SimpleLoopUnswitch/guards.ll

 
 exit:
   ret void
 }
 
 define void @test_conditional_guards(i1 %cond, i32 %N) {
 ; CHECK-LABEL: @test_conditional_guards(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[ENTRY_SPLIT_US:%.*]], label [[ENTRY_SPLIT:%.*]]
+; CHECK-NEXT:    [[COND_FR:%.*]] = freeze i1 [[COND:%.*]]
+; CHECK-NEXT:    br i1 [[COND_FR]], label [[ENTRY_SPLIT_US:%.*]], label [[ENTRY_SPLIT:%.*]]
 ; CHECK:       entry.split.us:
 ; CHECK-NEXT:    br label [[LOOP_US:%.*]]
 ; CHECK:       loop.us:
 ; CHECK-NEXT:    [[IV_US:%.*]] = phi i32 [ 0, [[ENTRY_SPLIT_US]] ], [ [[IV_NEXT_US:%.*]], [[BACKEDGE_US:%.*]] ]
 ; CHECK-NEXT:    [[CONDITION_US:%.*]] = icmp eq i32 [[IV_US]], 123
 ; CHECK-NEXT:    br i1 [[CONDITION_US]], label [[GUARD_US:%.*]], label [[BACKEDGE_US]]
 ; CHECK:       guard.us:
 ; CHECK-NEXT:    br label [[GUARDED_US:%.*]]

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

 
 ; Now check that the smaller formulation of 'loop_begin' does in fact unswitch
 ; with our low threshold.
 define void @test_unswitch(i1* %ptr, i1 %cond) {
 ; CHECK-LABEL: @test_unswitch(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %cond
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %entry.split.us, label %entry.split
 
 loop_begin:
   call void @x()
   br i1 %cond, label %loop_a, label %loop_b
 
 loop_a:
   call void @a()
   br label %loop_latch

 ; Check that even with large amounts of code on either side of the unswitched
 ; branch, if that code would be kept in only one of the unswitched clones it
 ; doesn't contribute to the cost.
 define void @test_unswitch_non_dup_code(i1* %ptr, i1 %cond) {
 ; CHECK-LABEL: @test_unswitch_non_dup_code(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %cond
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %entry.split.us, label %entry.split
 
 loop_begin:
   call void @x()
   br i1 %cond, label %loop_a, label %loop_b
 
 loop_a:
   call void @a()
   call void @a()

 
 ; Much like with non-duplicated code directly in the successor, we also won't
 ; duplicate even interesting CFGs.
 define void @test_unswitch_non_dup_code_in_cfg(i1* %ptr, i1 %cond) {
 ; CHECK-LABEL: @test_unswitch_non_dup_code_in_cfg(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %cond
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %entry.split.us, label %entry.split
 
 loop_begin:
   call void @x()
   br i1 %cond, label %loop_a, label %loop_b
 
 loop_a:
   %v1 = load i1, i1* %ptr
   br i1 %v1, label %loop_a_a, label %loop_a_b

 ; Check that we still unswitch when the exit block contains lots of code, even
 ; though we do clone the exit block as part of unswitching. This should work
 ; because we should split the exit block before anything inside it.
 define void @test_unswitch_large_exit(i1* %ptr, i1 %cond) {
 ; CHECK-LABEL: @test_unswitch_large_exit(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %cond
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %entry.split.us, label %entry.split
 
 loop_begin:
   call void @x()
   br i1 %cond, label %loop_a, label %loop_b
 
 loop_a:
   call void @a()
   br label %loop_latch

 
 ; Check that we handle a dedicated exit edge unswitch which is still
 ; non-trivial and has lots of code in the exit.
 define void @test_unswitch_dedicated_exiting(i1* %ptr, i1 %cond) {
 ; CHECK-LABEL: @test_unswitch_dedicated_exiting(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %cond
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %entry.split.us, label %entry.split
 
 loop_begin:
   call void @x()
   br i1 %cond, label %loop_a, label %loop_b_exit
 
 loop_a:
   call void @a()
   br label %loop_latch

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

inner_loop_begin:
   %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ]
   %cond = load i1, i1* %cond.ptr
   %b = load i32, i32* %b.ptr
   br label %inner_inner_loop_begin
 ; CHECK:       inner_loop_begin:
 ; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ]
 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
-; CHECK-NEXT:    br i1 %[[COND]], label %inner_loop_begin.split.us, label %inner_loop_begin.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %[[COND]]
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %inner_loop_begin.split.us, label %inner_loop_begin.split
 
 inner_inner_loop_begin:
   %v1 = load i1, i1* %ptr
   br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b
 
 inner_inner_loop_a:
   %v2 = load i1, i1* %ptr
   br i1 %v2, label %loop_exit, label %inner_inner_loop_c
inner_loop_begin:
   %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ]
   %cond = load i1, i1* %cond.ptr
   %b = load i32, i32* %b.ptr
   br label %inner_inner_loop_begin
 ; CHECK:       inner_loop_begin:
 ; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ]
 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
-; CHECK-NEXT:    br i1 %[[COND]], label %inner_loop_begin.split.us, label %inner_loop_begin.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %[[COND]]
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %inner_loop_begin.split.us, label %inner_loop_begin.split
 
 inner_inner_loop_begin:
   %v1 = load i1, i1* %ptr
   br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b
 
 inner_inner_loop_a:
   %v2 = load i1, i1* %ptr
   br i1 %v2, label %loop_exit, label %inner_inner_loop_c
inner_loop_begin:
   %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ]
   %cond = load i1, i1* %cond.ptr
   %b = load i32, i32* %b.ptr
   br label %inner_inner_loop_begin
 ; CHECK:       inner_loop_begin:
 ; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ]
 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
-; CHECK-NEXT:    br i1 %[[COND]], label %inner_loop_begin.split.us, label %inner_loop_begin.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %[[COND]]
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %inner_loop_begin.split.us, label %inner_loop_begin.split
 
 inner_inner_loop_begin:
   %v1 = load i1, i1* %ptr
   br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b
 
 inner_inner_loop_a:
   %v2 = load i1, i1* %ptr
   br i1 %v2, label %inner_inner_loop_latch, label %inner_loop_exit
inner_loop_begin:
   %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ]
   %cond = load i1, i1* %cond.ptr
   %b = load i32, i32* %b.ptr
   br label %inner_inner_loop_begin
 ; CHECK:       inner_loop_begin:
 ; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ]
 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
-; CHECK-NEXT:    br i1 %[[COND]], label %inner_loop_begin.split.us, label %inner_loop_begin.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %[[COND]]
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %inner_loop_begin.split.us, label %inner_loop_begin.split
 
 inner_inner_loop_begin:
   %v1 = load i1, i1* %ptr
   br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b
 
 inner_inner_loop_a:
   %v2 = load i1, i1* %ptr
   br i1 %v2, label %inner_inner_loop_latch, label %inner_loop_exit

 }
 
 ; Test that requires re-forming dedicated exits for the cloned loop.
 define i32 @test10a(i1* %ptr, i1 %cond, i32* %a.ptr) {
 ; CHECK-LABEL: @test10a(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %cond
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %entry.split.us, label %entry.split
 
 loop_begin:
   %a = load i32, i32* %a.ptr
   %v1 = load i1, i1* %ptr
   br i1 %v1, label %loop_a, label %loop_b
 
 loop_a:
   %v2 = load i1, i1* %ptr

 }
 
 ; Test that requires re-forming dedicated exits for the original loop.
 define i32 @test10b(i1* %ptr, i1 %cond, i32* %a.ptr) {
 ; CHECK-LABEL: @test10b(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %cond
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %entry.split.us, label %entry.split
 
 loop_begin:
   %a = load i32, i32* %a.ptr
   %v1 = load i1, i1* %ptr
   br i1 %v1, label %loop_a, label %loop_b
 
 loop_a:
   %v2 = load i1, i1* %ptr

 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 ; CHECK-NEXT:    br i1 %[[V]], label %loop_latch, label %inner_loop_ph
 
 inner_loop_ph:
   %cond = load i1, i1* %cond.ptr
   br label %inner_loop_begin
 ; CHECK:       inner_loop_ph:
 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
-; CHECK-NEXT:    br i1 %[[COND]], label %inner_loop_ph.split.us, label %inner_loop_ph.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %[[COND]]
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %inner_loop_ph.split.us, label %inner_loop_ph.split
 
 inner_loop_begin:
   call void @sink1(i32 %b)
   %a = load i32, i32* %a.ptr
   br i1 %cond, label %loop_exit, label %inner_loop_a
 
 inner_loop_a:
   %v2 = load i1, i1* %ptr

 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 ; CHECK-NEXT:    br i1 %[[V]], label %loop_latch, label %inner_loop_ph
 
 inner_loop_ph:
   %cond = load i1, i1* %cond.ptr
   br label %inner_loop_begin
 ; CHECK:       inner_loop_ph:
 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
-; CHECK-NEXT:    br i1 %[[COND]], label %inner_loop_ph.split.us, label %inner_loop_ph.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %[[COND]]
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %inner_loop_ph.split.us, label %inner_loop_ph.split
 
 inner_loop_begin:
   call void @sink1(i32 %b)
   %a = load i32, i32* %a.ptr
   br i1 %cond, label %inner_loop_a, label %loop_exit
 
 inner_loop_a:
   %v2 = load i1, i1* %ptr

 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_latch, label %inner_inner_loop_ph
 
 inner_inner_loop_ph:
   %cond = load i1, i1* %cond.ptr
   br label %inner_inner_loop_begin
 ; CHECK:       inner_inner_loop_ph:
 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
-; CHECK-NEXT:    br i1 %[[COND]], label %inner_inner_loop_ph.split.us, label %inner_inner_loop_ph.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %[[COND]]
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %inner_inner_loop_ph.split.us, label %inner_inner_loop_ph.split
 
 inner_inner_loop_begin:
   call void @sink1(i32 %b)
   %a = load i32, i32* %a.ptr
   br i1 %cond, label %inner_loop_exit, label %inner_inner_loop_a
 
 inner_inner_loop_a:
   %v2 = load i1, i1* %ptr

 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_latch, label %inner_inner_loop_ph
 
 inner_inner_loop_ph:
   %cond = load i1, i1* %cond.ptr
   br label %inner_inner_loop_begin
 ; CHECK:       inner_inner_loop_ph:
 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
-; CHECK-NEXT:    br i1 %[[COND]], label %inner_inner_loop_ph.split.us, label %inner_inner_loop_ph.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %[[COND]]
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %inner_inner_loop_ph.split.us, label %inner_inner_loop_ph.split
 
 inner_inner_loop_begin:
   call void @sink1(i32 %b)
   %a = load i32, i32* %a.ptr
   br i1 %cond, label %inner_inner_loop_a, label %inner_loop_exit
 
 inner_inner_loop_a:
   %v2 = load i1, i1* %ptr

 ; exiting block that connects the inner loop to the cloned loop is not the header
 ; block. This ensures that we correctly handle interesting corner cases of
 ; traversing back to the header when establishing the cloned loop.
 define i32 @test13a(i1* %ptr, i1 %cond, i32* %a.ptr, i32* %b.ptr) {
 ; CHECK-LABEL: @test13a(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %cond
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %entry.split.us, label %entry.split
 
 loop_begin:
   %a = load i32, i32* %a.ptr
   %v1 = load i1, i1* %ptr
   br i1 %v1, label %loop_a, label %loop_b
 
 loop_a:
   %v2 = load i1, i1* %ptr

 ; the header block. This ensures that we correctly handle interesting corner
 ; cases of traversing back to the header when re-establishing the original loop
 ; still exists after unswitching.
 define i32 @test13b(i1* %ptr, i1 %cond, i32* %a.ptr, i32* %b.ptr) {
 ; CHECK-LABEL: @test13b(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
+; CHECK-NEXT:    %[[COND_FR:.*]] = freeze i1 %cond
+; CHECK-NEXT:    br i1 %[[COND_FR]], label %entry.split.us, label %entry.split
 
 loop_begin:
   %a = load i32, i32* %a.ptr
   %v1 = load i1, i1* %ptr
   br i1 %v1, label %loop_a, label %loop_b
 
 loop_a:
   %v2 = load i1, i1* %ptr
loop_exit:
   ret void
 }
 
 ; A test reduced out of 403.gcc with interesting nested loops that trigger
 ; multiple unswitches. A key component of this test is that there are multiple
 ; paths to reach an inner loop after unswitching, and one of them is via the
 ; predecessors of the unswitched loop header. That can allow us to find the loop
 ; through multiple different paths.
-define void @test21(i1 %a, i1 %b) {
+define void @test21(i1 %a0, i1 %b) {
 ; CHECK-LABEL: @test21(
 bb:
+  %a = freeze i1 %a0
   br label %bb3
 ; CHECK-NOT:     br i1 %a
 ;
 ; CHECK:         br i1 %a, label %[[BB_SPLIT_US:.*]], label %[[BB_SPLIT:.*]]
 ;
 ; CHECK-NOT:     br i1 %a
 ; CHECK-NOT:     br i1 %b
 ;

 ; skip whole subregions of the outer loop blocks but just because the header of
 ; the outer loop is also the preheader of an inner loop shouldn't confuse this
 ; walk.
 define void @test23(i1 %arg, i1* %ptr) {
 ; CHECK-LABEL: define void @test23(
 entry:
   br label %outer.header
 ; CHECK:       entry:
-; CHECK-NEXT:    br i1 %arg,
+; CHECK-NEXT:    %[[ARG_FR:.*]] = freeze i1 %arg
+; CHECK-NEXT:    br i1 %[[ARG_FR]],
 ;
 ; Just verify that we unswitched the correct bits. We should call `@f` twice in
 ; one unswitch and `@f` and then `@g` in the other.
 ; CHECK:         call void
 ; CHECK-SAME:              @f
 ; CHECK:         call void
 ; CHECK-SAME:              @f
 ;

 ; can introduce multiple edges to successors. These need lots of special case
 ; handling as they get collapsed in many cases (domtree, the unswitch itself)
 ; but not in all cases (the PHI node operands).
 define i32 @test29(i32 %arg) {
 ; CHECK-LABEL: @test29(
 entry:
   br label %header
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    switch i32 %arg, label %[[ENTRY_SPLIT_C:.*]] [
+; CHECK-NEXT:    %arg.fr = freeze i32 %arg
+; CHECK-NEXT:    switch i32 %arg.fr, label %[[ENTRY_SPLIT_C:.*]] [
 ; CHECK-NEXT:      i32 0, label %[[ENTRY_SPLIT_A:.*]]
 ; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_A]]
 ; CHECK-NEXT:      i32 2, label %[[ENTRY_SPLIT_B:.*]]
 ; CHECK-NEXT:      i32 3, label %[[ENTRY_SPLIT_C]]
 ; CHECK-NEXT:    ]
 
 header:
   %tmp = call i32 @d()

 ; CHECK-NEXT:    %[[EXIT_PHI2:.*]] = phi i32 [ %[[EXIT_PHI1]], %[[EXIT_SPLIT]] ], [ %[[LCSSA_A]], %[[LOOP_EXIT_A]] ]
 ; CHECK-NEXT:    ret i32 %[[EXIT_PHI2]]
 }
 
 ; Similar to @test29 but designed to have one of the duplicate edges be
 ; a loop exit edge as those can in some cases be special. Among other things,
 ; this includes an LCSSA phi with multiple entries despite being a dedicated
 ; exit block.
-define i32 @test30(i32 %arg) {
+define i32 @test30(i32 %arg0) {
 ; CHECK-LABEL: define i32 @test30(
 entry:
+  %arg = freeze i32 %arg0
   br label %header
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    %arg = freeze i32 %arg0
 ; CHECK-NEXT:    switch i32 %arg, label %[[ENTRY_SPLIT_EXIT:.*]] [
 ; CHECK-NEXT:      i32 -1, label %[[ENTRY_SPLIT_EXIT]]
 ; CHECK-NEXT:      i32 0, label %[[ENTRY_SPLIT_A:.*]]
 ; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_B:.*]]
 ; CHECK-NEXT:      i32 2, label %[[ENTRY_SPLIT_B]]
 ; CHECK-NEXT:    ]
 
 header:

 ; CHECK:       a.header:
 ; CHECK-NEXT:    br label %b.header
 
 b.header:
   %v1 = call i1 @cond()
   br label %c.header
 ; CHECK:       b.header:
 ; CHECK-NEXT:    %v1 = call i1 @cond()
-; CHECK-NEXT:    br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
+; CHECK-NEXT:    %[[V1_FR:.*]] = freeze i1 %v1
+; CHECK-NEXT:    br i1 %[[V1_FR]], label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
 ;
 ; CHECK:       [[B_HEADER_SPLIT_US]]:
 ; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
 ;
 ; CHECK:       [[C_HEADER_US]]:
 ; CHECK-NEXT:    call i32 @c()
 ; CHECK-NEXT:    br label %[[B_LATCH_SPLIT_US:.*]]
 ;

 
 b.header:
   %x.b = load i32, i32* %ptr
   %v1 = call i1 @cond()
   br label %c.header
 ; CHECK:       b.header:
 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
 ; CHECK-NEXT:    %v1 = call i1 @cond()
-; CHECK-NEXT:    br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
+; CHECK-NEXT:    %[[V1_FR:.*]] = freeze i1 %v1
+; CHECK-NEXT:    br i1 %[[V1_FR]], label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
 ;
 ; CHECK:       [[B_HEADER_SPLIT_US]]:
 ; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
 ;
 ; CHECK:       [[C_HEADER_US]]:
 ; CHECK-NEXT:    call i32 @c()
 ; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
 ;

 
 b.header:
   %x.b = load i32, i32* %ptr
   %v1 = call i1 @cond()
   br label %c.header
 ; CHECK:       b.header:
 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
 ; CHECK-NEXT:    %v1 = call i1 @cond()
-; CHECK-NEXT:    br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
+; CHECK-NEXT:    %[[V1_FR:.*]] = freeze i1 %v1
+; CHECK-NEXT:    br i1 %[[V1_FR]], label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
 ;
 ; CHECK:       [[B_HEADER_SPLIT_US]]:
 ; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
 ;
 ; CHECK:       [[C_HEADER_US]]:
 ; CHECK-NEXT:    call i32 @c()
 ; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
 ;

 
 b.header:
   %x.b = load i32, i32* %ptr
   %v1 = call i1 @cond()
   br label %c.header
 ; CHECK:       b.header:
 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
 ; CHECK-NEXT:    %v1 = call i1 @cond()
-; CHECK-NEXT:    br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
+; CHECK-NEXT:    %[[V1_FR:.*]] = freeze i1 %v1
+; CHECK-NEXT:    br i1 %[[V1_FR]], label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
 ;
 ; CHECK:       [[B_HEADER_SPLIT_US]]:
 ; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
 ;
 ; CHECK:       [[C_HEADER_US]]:
 ; CHECK-NEXT:    call i32 @c()
 ; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
 ;

 ; CHECK:       b.header:
 ; CHECK-NEXT:    br label %c.header
 
 c.header:
   %v1 = call i1 @cond()
   br label %d.header
 ; CHECK:       c.header:
 ; CHECK-NEXT:    %v1 = call i1 @cond()
-; CHECK-NEXT:    br i1 %v1, label %[[C_HEADER_SPLIT_US:.*]], label %[[C_HEADER_SPLIT:.*]]
+; CHECK-NEXT:    %[[V1_FR:.*]] = freeze i1 %v1
+; CHECK-NEXT:    br i1 %[[V1_FR]], label %[[C_HEADER_SPLIT_US:.*]], label %[[C_HEADER_SPLIT:.*]]
 ;
 ; CHECK:       [[C_HEADER_SPLIT_US]]:
 ; CHECK-NEXT:    br label %[[D_HEADER_US:.*]]
 ;
 ; CHECK:       [[D_HEADER_US]]:
 ; CHECK-NEXT:    call i32 @d()
 ; CHECK-NEXT:    br label %[[C_LATCH_US:.*]]
 ;

 
 c.header:
   %x.c = load i32, i32* %ptr
   %v1 = call i1 @cond()
   br label %d.header
 ; CHECK:       c.header:
 ; CHECK-NEXT:    %x.c = load i32, i32* %ptr
 ; CHECK-NEXT:    %v1 = call i1 @cond()
-; CHECK-NEXT:    br i1 %v1, label %[[C_HEADER_SPLIT_US:.*]], label %[[C_HEADER_SPLIT:.*]]
+; CHECK-NEXT:    %[[V1_FR:.*]] = freeze i1 %v1
+; CHECK-NEXT:    br i1 %[[V1_FR]], label %[[C_HEADER_SPLIT_US:.*]], label %[[C_HEADER_SPLIT:.*]]
 ;
 ; CHECK:       [[C_HEADER_SPLIT_US]]:
 ; CHECK-NEXT:    br label %[[D_HEADER_US:.*]]
 ;
 ; CHECK:       [[D_HEADER_US]]:
 ; CHECK-NEXT:    call i32 @d()
 ; CHECK-NEXT:    br label %[[C_LATCH_US:.*]]
 ;

 
 b.header:
   %x.b = load i32, i32* %ptr
   %v1 = call i32 @cond.i32()
   br label %c.header
 ; CHECK:       b.header:
 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
 ; CHECK-NEXT:    %v1 = call i32 @cond.i32()
-; CHECK-NEXT:    switch i32 %v1, label %[[B_HEADER_SPLIT:.*]] [
+; CHECK-NEXT:    %[[V1_FR]] = freeze i32 %v1
+; CHECK-NEXT:    switch i32 %[[V1_FR]], label %[[B_HEADER_SPLIT:.*]] [
 ; CHECK-NEXT:      i32 1, label %[[B_HEADER_SPLIT_US:.*]]
 ; CHECK-NEXT:      i32 2, label %[[B_HEADER_SPLIT_US]]
 ; CHECK-NEXT:      i32 3, label %[[B_HEADER_SPLIT_US]]
 ; CHECK-NEXT:    ]
 ;
 ; CHECK:       [[B_HEADER_SPLIT_US]]:
 ; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
 ;