[LoopUnswitch] Do not freeze condition if hoisted branch is guaranteed to be reachable

[aqjune]

Summary

If the branch is hoisted to the loop header, and we know that it was originally
reachable, then no freeze instruction is needed since we are not introducing
a new branch in the dynamic control-flow.

For example:

while (D) {
  I1
  I2
  if (C) { A }
  else   { B }
}

If we know that I1 and I2 always transfer execution to the successor, then we
know that branch on C is reachable if D is true at least once.
Therefore, transforming the code above to the following is correct:

if (D) {
  if (C) {
    do { I1 I2 A } while (D)
  } else {
    do { I1 I2 B } while (D)
  }
}

[efriedma]

lib/Transforms/Scalar/LoopUnswitch.cpp

722

Maybe we should be a little more aggressive here? LoopUnswitch::TryTrivialLoopUnswitch has a branch-following loop which special-cases conditional branches with a constant condition.

Can we compute this once for the whole loop, rather than iterating over the whole loop for each basic block?

[aqjune]

lib/Transforms/Scalar/LoopUnswitch.cpp

722

@efriedma Hello. I couldn't understand your comment. Do you mean we can cache the necessity of freeze when LoopUnswitch::TryTrivialLoopUnswitch is called (which is called at line 545), and then reuse the cached info here?

[efriedma]

lib/Transforms/Scalar/LoopUnswitch.cpp

722

The two paragraphs are sort of separate issues: you should share the branch-following code, and you should compute this property outside of the loop. I don't think you can reuse the result from TryTrivialLoopUnswitch because it isn't computing the same property.

[aqjune]

• Compute reachable terminators in advance so it does not traverse same basic block multiple times
• Let branchs with constant condition be treated well

[aqjune]

lib/Transforms/Scalar/LoopUnswitch.cpp

722

@efriedma I lifted out the loop to line 610 so it calculates reachable terminators in advance. Also I added code snippet which deals with constant branch condition.

[efriedma]

(I don't feel comfortable approving changes to loop-unswitch, so someone else should probably look over this.)

lib/Transforms/Scalar/LoopUnswitch.cpp

708

Refactor the identical "find the next successor" code into a helper?

[filcab]

lib/Transforms/Scalar/LoopUnswitch.cpp

679

break;
No need to keep going if we're just going to break the outer loop.

735

This comment seems to make more sense in line 681 (which already has a similar comment), since that's where you decide if you need to freeze the condition (and set NeedFreeze).

1058

(2) I guess :-)

1080

Minor nit: Maybe this instead of if + |=?
NeedFreeze = NeedFreeze || !isGuaranteedToTransferExecutionToSuccessor(&I);

[aqjune]

lib/Transforms/Scalar/LoopUnswitch.cpp

708

@efriedma What do you mean by a helper?

[aqjune]

• Add FindNextSuccessorBlock
• Minor modifications

[efriedma]

What do you mean by a helper?

Exactly what you did by adding FindNextSuccessorBlock.

[aqjune]

Rebased to svn commit 308173

[reames]

lib/Transforms/Scalar/LoopUnswitch.cpp

699

Please see Analysis/MustExecute.h. We already have a tested implementation of this, please use it. It looks like you probably want ICFLoopSafetyInfo

[aqjune]

Addressed via https://reviews.llvm.org/D29015

[jdoerfert]

lib/Transforms/Scalar/LoopUnswitch.cpp

699

You can also use MustBeExecutedContextExplorer (with or without LI, DT, PDT).

lib/Transforms/Scalar/LoopUnswitch.cpp

static std::pair<Value *, OperatorChain> FindLIVLoopCondition(Value *Cond,
 
   // In case we do find a LIV, it can not be obtained by walking up a mixed
   // operator chain.
   assert((!FCond || OpChain != OC_OpChainMixed) &&
         "Do not expect a partial LIV with mixed operator chain");
   return {FCond, OpChain};
 }
 
+static BasicBlock *FindNextSuccessorBlock(TerminatorInst *TI) {
+  BasicBlock *BB = nullptr;
+  LLVMContext &Context = TI->getContext();
+
+  if (TI->getNumSuccessors() == 1)
+    BB = TI->getSuccessor(0);
+  else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
+    if (BI->getCondition() == ConstantInt::getTrue(Context))
+      BB = BI->getSuccessor(0);
+    else if (BI->getCondition() == ConstantInt::getFalse(Context))
+      BB = BI->getSuccessor(1);
+  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition())) {
+      SwitchInst::CaseIt CItr = SI->findCaseValue(CI);
+      BB = CItr->getCaseSuccessor();
+    }
+  }
+
+  return BB;
+}
+
 bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
   if (skipLoop(L))
     return false;
 
   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
       *L->getHeader()->getParent());
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   LPM = &LPM_Ref;
if (LoopCond &&
       // NB! Unswitching (if successful) could have erased some of the
       // instructions in Guards leaving dangling pointers there.  This is fine
       // because we're returning now, and won't look at Guards again.
       ++NumGuards;
       return true;
     }
   }
 
+  // Given a terminator TI, if TI is in header, and all instructions
+  // between the beginning of the loop header and TI are guaranteed to
+  // execute, then no freeze is needed in unswitching it.
+  // ReachableTI is a set of terminator instructions which does not
+  // require freeze when being unswitched.
+  DenseSet<TerminatorInst *> ReachableTIs;
+  {
+    BasicBlock *BB = currentLoop->getHeader();
+    while (BB) {
+      TerminatorInst *BBTI = BB->getTerminator();
+      bool AlwaysReachableTI = true;
+
+      // Check whether all instructions in BB transfers execution
+      // to successors.
+      for (auto &I : *BB) {
+        Instruction *Inst = &I;
+        if (!isGuaranteedToTransferExecutionToSuccessor(Inst)) {
+          AlwaysReachableTI = false;
+          break;
+        }
+      }
+
+      if (!AlwaysReachableTI)
+        break;
+
+      // BBTI is always reachable from the header of the loop.
+      ReachableTIs.insert(BBTI);
+
+      // Now proceed to the next basic block, or stop here?
+      BB = FindNextSuccessorBlock(BBTI);
+      if (BB == nullptr)
+        break;
+
+      // Check whether the block is already visited.
+      if (ReachableTIs.count(BB->getTerminator()) > 0)
+        break;
+    }
+  }
+
   // Loop over all of the basic blocks in the loop.  If we find an interior
   // block that is branching on a loop-invariant condition, we can unswitch this
   // loop.
   for (Loop::block_iterator I = currentLoop->block_begin(),
          E = currentLoop->block_end(); I != E; ++I) {
     TerminatorInst *TI = (*I)->getTerminator();
 
     // Unswitching on a potentially uninitialized predicate is not
     // MSan-friendly. Limit this to the cases when the original predicate is
     // guaranteed to execute, to avoid creating a use-of-uninitialized-value
     // in the code that did not have one.
     // This is a workaround for the discrepancy between LLVM IR and MSan
     // semantics. See PR28054 for more details.
     if (SanitizeMemory &&
         !isGuaranteedToExecute(*TI, DT, currentLoop, &SafetyInfo))
       continue;
 
+    // Is freeze needed when unswitching this branch?
+    bool NeedFreeze = ReachableTIs.count(TI) == 0;
+
     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
       // Some branches may be rendered unreachable because of previous
       // unswitching.
       // Unswitch only those branches that are reachable.
       if (isUnreachableDueToPreviousUnswitching(*I))
         continue;
  
       // If this isn't branching on an invariant condition, we can't unswitch
       // it.
       if (BI->isConditional()) {
         // See if this, or some part of it, is loop invariant.  If so, we can
         // unswitch on it if we desire.
         Value *LoopCond = FindLIVLoopCondition(BI->getCondition(),
                                                currentLoop, Changed).first;
+        // Determine whether we should freeze the condition.
         if (LoopCond &&
-            UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context), true, TI)) {
+            UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context),
+                                 NeedFreeze, TI)) {
           ++NumBranches;
           return true;
         }
       }
     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
       Value *SC = SI->getCondition();
       Value *LoopCond;
       OperatorChain OpChain;
if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
               break;
             }
           }
         }
 
         if (!UnswitchVal)
           continue;
 
-        if (UnswitchIfProfitable(LoopCond, UnswitchVal, true)) {
+        if (UnswitchIfProfitable(LoopCond, UnswitchVal, NeedFreeze)) {
           ++NumSwitches;
           // In case of a full LIV, UnswitchVal is the value we unswitched out.
           // In case of a partial LIV, we only unswitch when its an AND-chain
           // or OR-chain. In both cases switch input value simplifies to
           // UnswitchVal.
           BranchesInfo.setUnswitched(SI, UnswitchVal);
           return true;
         }
bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) {
   // branches could either eliminate the current loop or make other loops
   // unreachable. LCSSA form might also not be preserved after deleting
   // branches. The following code keeps traversing loop header's successors
   // until it finds the trivial condition candidate (condition that is not a
   // constant). Since unswitching generates branches with constant conditions,
   // this scenario could be very common in practice.
   SmallSet<BasicBlock*, 8> Visited;
 
+  // If there exists an instruction I which is (1) between the beginning of
+  // the loop preheader and the branch to unswitch, and (2) not guaranteed to 
+  // transfer execution to successor, then we need to freeze the condition.
+  bool NeedFreeze = false;
+
   while (true) {
     // If we exit loop or reach a previous visited block, then
     // we can not reach any trivial condition candidates (unfoldable
     // branch instructions or switch instructions) and no unswitch
     // can happen. Exit and return false.
     if (!currentLoop->contains(CurrentBB) || !Visited.insert(CurrentBB).second)
       return false;
 
     // Check if this loop will execute any side-effecting instructions (e.g.
     // stores, calls, volatile loads) in the part of the loop that the code
     // *would* execute. Check the header first.
-    for (Instruction &I : *CurrentBB)
+    for (Instruction &I : *CurrentBB) {
       if (I.mayHaveSideEffects())
         return false;
 
-    if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
-      if (BI->isUnconditional()) {
-        CurrentBB = BI->getSuccessor(0);
-      } else if (BI->getCondition() == ConstantInt::getTrue(Context)) {
-        CurrentBB = BI->getSuccessor(0);
-      } else if (BI->getCondition() == ConstantInt::getFalse(Context)) {
-        CurrentBB = BI->getSuccessor(1);
-      } else {
-        // Found a trivial condition candidate: non-foldable conditional branch.
-        break;
+      if (!NeedFreeze) {
+        // There exists an instruction which can exit from the loop.
+        // Hoisting branch must not have undef/poison value as its condition.
+        NeedFreeze |= !isGuaranteedToTransferExecutionToSuccessor(&I);
       }
-    } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
-      // At this point, any constant-foldable instructions should have probably
-      // been folded.
-      ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
-      if (!Cond)
-        break;
-      // Find the target block we are definitely going to.
-      CurrentBB = SI->findCaseValue(Cond)->getCaseSuccessor();
-    } else {
-      // We do not understand these terminator instructions.
-      break;
     }
 
+    CurrentBB = FindNextSuccessorBlock(CurrentTerm);
+    if (CurrentBB == nullptr)
+      // Found a trivial condition candidate: non-foldable conditional branch.
+      break;
+
     CurrentTerm = CurrentBB->getTerminator();
   }
 
   // CondVal is the condition that controls the trivial condition.
   // LoopExitBB is the BasicBlock that loop exits when meets trivial condition.
   Constant *CondVal = nullptr;
   BasicBlock *LoopExitBB = nullptr;
 
if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
     }
 
     // If we didn't find a single unique LoopExit block, or if the loop exit
     // block contains phi nodes, this isn't trivial.
     if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
       return false;   // Can't handle this.
 
     UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB,
-                             true, CurrentTerm);
+                             NeedFreeze, CurrentTerm);
     ++NumBranches;
     return true;
   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
     // If this isn't switching on an invariant condition, we can't unswitch it.
     Value *LoopCond = FindLIVLoopCondition(SI->getCondition(),
                                            currentLoop, Changed).first;
 
     // Unswitch only if the trivial condition itself is an LIV (not
if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
     }
 
     // If we didn't find a single unique LoopExit block, or if the loop exit
     // block contains phi nodes, this isn't trivial.
     if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
       return false;   // Can't handle this.
 
     UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB,
-                             true, nullptr);
+                             NeedFreeze, nullptr);
 
     // We are only unswitching full LIV.
     BranchesInfo.setUnswitched(SI, CondVal);
     ++NumSwitches;
     return true;
   }
   return false;
 }

test/Transforms/LoopUnswitch/2011-11-18-SimpleSwitch.ll

 ; REQUIRES: asserts
 ; RUN: opt -loop-unswitch -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s
 ; RUN: opt -S -loop-unswitch -verify-loop-info -verify-dom-info < %s | FileCheck %s
 
 ; STATS: 2 loop-unswitch - Number of switches unswitched
 
-; CHECK:      %c.fr = freeze i32 %c
-; CHECK-NEXT: %1 = icmp eq i32 %c.fr, 1
+; CHECK:      %1 = icmp eq i32 %c, 1
 ; CHECK-NEXT: br i1 %1, label %.split.us, label %..split_crit_edge
 
 ; CHECK:      ..split_crit_edge:                                ; preds = %0
 ; CHECK-NEXT:   br label %.split
 
 ; CHECK:      .split.us:                                        ; preds = %0
 ; CHECK-NEXT:   br label %loop_begin.us
 
 ; CHECK:      loop_begin.us:                                    ; preds = %loop_begin.backedge.us, %.split.us
 ; CHECK-NEXT:   %var_val.us = load i32, i32* %var
 ; CHECK-NEXT:   switch i32 1, label %default.us-lcssa.us [
 ; CHECK-NEXT:     i32 1, label %inc.us
 
 ; CHECK:      inc.us:                                           ; preds = %loop_begin.us
 ; CHECK-NEXT:   call void @incf() [[NOR_NUW:#[0-9]+]]
 ; CHECK-NEXT:   br label %loop_begin.backedge.us
 
 ; CHECK:      .split:                                           ; preds = %..split_crit_edge
-; CHECK-NEXT:   %2 = icmp eq i32 %c.fr, 2
+; CHECK-NEXT:   %2 = icmp eq i32 %c, 2
 ; CHECK-NEXT:   br i1 %2, label %.split.split.us, label %.split..split.split_crit_edge
 
 ; CHECK:      .split..split.split_crit_edge:                    ; preds = %.split
 ; CHECK-NEXT:   br label %.split.split
 
 ; CHECK:      .split.split.us:                                  ; preds = %.split
 ; CHECK-NEXT:   br label %loop_begin.us1
 
 ; CHECK:      loop_begin.us1:                                   ; preds = %loop_begin.backedge.us5, %.split.split.us
 ; CHECK-NEXT:   %var_val.us2 = load i32, i32* %var
 ; CHECK-NEXT:   switch i32 2, label %default.us-lcssa.us-lcssa.us [
 ; CHECK-NEXT:     i32 1, label %inc.us4
 ; CHECK-NEXT:     i32 2, label %dec.us3
 ; CHECK-NEXT:   ]
 
 ; CHECK:      dec.us3:                                          ; preds = %loop_begin.us1
 ; CHECK-NEXT:   call void @decf() [[NOR_NUW]]
 ; CHECK-NEXT:   br label %loop_begin.backedge.us5
 
 ; CHECK:      .split.split:                                     ; preds = %.split..split.split_crit_edge
 ; CHECK-NEXT:   br label %loop_begin
 
 ; CHECK:      loop_begin:                                       ; preds = %loop_begin.backedge, %.split.split
 ; CHECK-NEXT:   %var_val = load i32, i32* %var
-; CHECK-NEXT:   switch i32 %c.fr, label %default.us-lcssa.us-lcssa [
+; CHECK-NEXT:   switch i32 %c, label %default.us-lcssa.us-lcssa [
 ; CHECK-NEXT:     i32 1, label %inc
 ; CHECK-NEXT:     i32 2, label %dec
 ; CHECK-NEXT:   ]
 
 ; CHECK:      inc:                                              ; preds = %loop_begin
 ; CHECK-NEXT:   br i1 true, label %us-unreachable.us-lcssa, label %inc.split
 
 ; CHECK:      dec:                                              ; preds = %loop_begin

test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches-Threshold.ll

 ; REQUIRES: asserts
 ; RUN: opt -loop-unswitch -loop-unswitch-threshold 13 -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s
 ; RUN: opt -S -loop-unswitch -loop-unswitch-threshold 13 -verify-loop-info -verify-dom-info < %s | FileCheck %s
 
 ; STATS: 1 loop-unswitch - Number of switches unswitched
 
 ; ModuleID = '../llvm/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches.ll'
 
-; CHECK:        %c.fr = freeze i32 %c
-
-; CHECK:        %1 = icmp eq i32 %c.fr, 1
+; CHECK:        %1 = icmp eq i32 %c, 1
 ; CHECK-NEXT:   br i1 %1, label %.split.us, label %..split_crit_edge
 
 ; CHECK:      ..split_crit_edge:                                ; preds = %0
 ; CHECK-NEXT:   br label %.split
 
 ; CHECK:      .split.us:                                        ; preds = %0
 ; CHECK-NEXT:   br label %loop_begin.us
 

 ; CHECK:      inc.us:                                           ; preds = %second_switch.us, %loop_begin.us
 ; CHECK-NEXT:   call void @incf() [[NOR_NUW:#[0-9]+]]
 ; CHECK-NEXT:   br label %loop_begin.backedge.us
 
 ; CHECK:      .split:                                           ; preds = %..split_crit_edge
 ; CHECK-NEXT:   br label %loop_begin
 
 ; CHECK:      loop_begin:                                       ; preds = %loop_begin.backedge, %.split
-; CHECK:        switch i32 %c.fr, label %second_switch [
+; CHECK:        switch i32 %c, label %second_switch [
 ; CHECK-NEXT:     i32 1, label %loop_begin.inc_crit_edge
 ; CHECK-NEXT:   ]
 
 ; CHECK:      loop_begin.inc_crit_edge:                         ; preds = %loop_begin
 ; CHECK-NEXT:   br i1 true, label %us-unreachable, label %inc
 
 ; CHECK:      second_switch:                                    ; preds = %loop_begin
 ; CHECK-NEXT:   switch i32 %d, label %default [

test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches.ll

 ; REQUIRES: asserts
 ; RUN: opt -loop-unswitch -loop-unswitch-threshold 1000 -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s
 ; RUN: opt -S -loop-unswitch -loop-unswitch-threshold 1000 -verify-loop-info -verify-dom-info < %s | FileCheck %s
 
 ; STATS: 3 loop-unswitch - Number of switches unswitched
 
-; CHECK:        %c.fr = freeze i32 %c
-
 ; CHECK:        %d.fr = freeze i32 %d
-; CHECK-NEXT:   %1 = icmp eq i32 %c.fr, 1
+; CHECK-NEXT:   %1 = icmp eq i32 %c, 1
 ; CHECK-NEXT:   br i1 %1, label %.split.us, label %..split_crit_edge
 
 ; CHECK:      ..split_crit_edge:                                ; preds = %0
 ; CHECK-NEXT:   br label %.split
 
 ; CHECK:      .split.us:                                        ; preds = %0
 ; CHECK-NEXT:   %2 = icmp eq i32 %d.fr, 1
 ; CHECK-NEXT:   br i1 %2, label %.split.us.split.us, label %.split.us..split.us.split_crit_edge

 ; CHECK:      .split..split.split_crit_edge:                    ; preds = %.split
 ; CHECK-NEXT:   br label %.split.split
 
 ; CHECK:      .split.split.us:                                  ; preds = %.split
 ; CHECK-NEXT:   br label %loop_begin.us1
 
 ; CHECK:      loop_begin.us1:                                   ; preds = %loop_begin.backedge.us6, %.split.split.us
 ; CHECK-NEXT:   %var_val.us2 = load i32, i32* %var
-; CHECK-NEXT:   switch i32 %c.fr, label %second_switch.us3 [
+; CHECK-NEXT:   switch i32 %c, label %second_switch.us3 [
 ; CHECK-NEXT:     i32 1, label %loop_begin.inc_crit_edge.us
 ; CHECK-NEXT:   ]
 
 ; CHECK:      second_switch.us3:                                ; preds = %loop_begin.us1
 ; CHECK-NEXT:   switch i32 1, label %default.us5 [
 ; CHECK-NEXT:     i32 1, label %inc.us4
 ; CHECK-NEXT:   ]
 
 ; CHECK:      inc.us4:                                          ; preds = %loop_begin.inc_crit_edge.us, %second_switch.us3
 ; CHECK-NEXT:   call void @incf() [[NOR_NUW]]
 ; CHECK-NEXT:   br label %loop_begin.backedge.us6
 
 ; CHECK:      loop_begin.inc_crit_edge.us:                      ; preds = %loop_begin.us1
 ; CHECK-NEXT:   br i1 true, label %us-unreachable.us-lcssa.us, label %inc.us4
 
 ; CHECK:      .split.split:                                     ; preds = %.split..split.split_crit_edge
 ; CHECK-NEXT:   br label %loop_begin
 
 ; CHECK:      loop_begin:                                       ; preds = %loop_begin.backedge, %.split.split
 ; CHECK-NEXT:   %var_val = load i32, i32* %var
-; CHECK-NEXT:   switch i32 %c.fr, label %second_switch [
+; CHECK-NEXT:   switch i32 %c, label %second_switch [
 ; CHECK-NEXT:     i32 1, label %loop_begin.inc_crit_edge
 ; CHECK-NEXT:   ]
 
 ; CHECK:      loop_begin.inc_crit_edge:                         ; preds = %loop_begin
 ; CHECK-NEXT:   br i1 true, label %us-unreachable.us-lcssa, label %inc
 
 ; CHECK:      second_switch:                                    ; preds = %loop_begin
 ; CHECK-NEXT:   switch i32 %d.fr, label %default [

test/Transforms/LoopUnswitch/2015-06-17-Metadata.ll

 
 for.body:                                         ; preds = %for.inc, %for.body.lr.ph
   %inc.i = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
   %mul.i = phi i32 [ 3, %for.body.lr.ph ], [ %mul.p, %for.inc ]
   %add.i = phi i32 [ %a, %for.body.lr.ph ], [ %add.p, %for.inc ]
   %cmp1 = icmp eq i32 %a, 12345
   br i1 %cmp1, label %if.then, label %if.else, !prof !0
 ; CHECK: %cmp1 = icmp eq i32 %a, 12345
-; CHECK-NEXT: %cmp1.fr = freeze i1 %cmp1
-; CHECK-NEXT: br i1 %cmp1.fr, label %for.body.us, label %for.body, !prof !0
+; CHECK-NEXT: br i1 %cmp1, label %for.body.us, label %for.body, !prof !0
 if.then:                                          ; preds = %for.body
 ; CHECK: for.body.us:
 ; CHECK: add nsw i32 %{{.*}}, 123
 ; CHECK: %exitcond.us = icmp eq i32 %inc.us, %b
 ; CHECK: br i1 %exitcond.us, label %for.cond.cleanup, label %for.body.us
   %add = add nsw i32 %add.i, 123
   br label %for.inc
 

 }
 
 define void @foo_swapped(i32 %a, i32 %b) {
 ;CHECK-LABEL: foo_swapped
 entry:
   br label %for.body
 ;CHECK: entry:
 ;CHECK-NEXT: %cmp1 = icmp eq i32 1, 2
-;CHECK-NEXT: %cmp1.fr = freeze i1 %cmp1
-;CHECK-NEXT: br i1 %cmp1.fr, label %for.body, label %for.cond.cleanup.split, !prof !1
+;CHECK-NEXT: br i1 %cmp1, label %for.body, label %for.cond.cleanup.split, !prof !1
 ;CHECK: for.body:
 for.body:                                         ; preds = %for.inc, %entry
   %inc.i = phi i32 [ 0, %entry ], [ %inc, %if.then ]
   %add.i = phi i32 [ 100, %entry ], [ %add, %if.then ]
   %inc = add nuw nsw i32 %inc.i, 1
   %cmp1 = icmp eq i32 1, 2
   br i1 %cmp1, label %if.then, label  %for.cond.cleanup, !prof !0
 

test/Transforms/LoopUnswitch/AMDGPU/divergent-unswitch.ll

 ; RUN: opt -mtriple=amdgcn-- -O3 -S %s | FileCheck %s
 
 ; Check that loop unswitch happened and condition hoisted out of the loop.
 ; Condition is uniform so all targets should perform unswitching.
 
 ; CHECK-LABEL: {{^}}define amdgpu_kernel void @uniform_unswitch
 ; CHECK: entry:
 ; CHECK-NEXT: [[LOOP_COND:%[a-z0-9]+]] = icmp
-; CHECK-NEXT: br i1 [[LOOP_COND]]
-; CHECK: for.body.lr.ph:
 ; CHECK-NEXT: [[IF_COND:%[a-z0-9]+]] = icmp eq i32 %x, 123456
-; CHECK-NEXT: [[IF_COND]].fr = freeze i1 [[IF_COND]]
-; CHECK-NEXT: br i1 [[IF_COND]]
+; CHECK-NEXT: and i1 [[LOOP_COND]], [[IF_COND]]
+; CHECK-NEXT: br i1
 
 define amdgpu_kernel void @uniform_unswitch(i32 * nocapture %out, i32 %n, i32 %x) {
 entry:
   %cmp6 = icmp sgt i32 %n, 0
   br i1 %cmp6, label %for.body.lr.ph, label %for.cond.cleanup
 
 for.body.lr.ph:                                   ; preds = %entry
   %cmp1 = icmp eq i32 %x, 123456

test/Transforms/LoopUnswitch/basictest.ll

 ; CHECK: }
 }
 
 ; Make sure we unswitch %a == 0 out of the loop.
 ;
 ; CHECK: define void @and_i2_as_switch_input(i2
 ; CHECK: entry:
 ; This is an indication that the loop has been unswitched.
-; CHECK: freeze i2 %a
-; CHECK: icmp eq i2 %a.fr, 0
+; CHECK: icmp eq i2 %a, 0
 ; CHECK: br
 ; There should be no more unswitching after the 1st unswitch.
 ; CHECK-NOT: icmp eq
 ; CHECK: ret
 define void @and_i2_as_switch_input(i2 %a) {
 entry:
   br label %for.body
 
for.end:
   ret void
 }
 
 ; Make sure we unswitch %a == !0 out of the loop.
 ;
 ; CHECK: define void @or_i2_as_switch_input(i2
 ; CHECK: entry:
 ; This is an indication that the loop has been unswitched.
-; CHECK: freeze i2 %a
-; CHECK: icmp eq i2 %a.fr, -1
+; CHECK: icmp eq i2 %a, -1
 ; CHECK: br
 ; There should be no more unswitching after the 1st unswitch.
 ; CHECK-NOT: icmp eq
 ; CHECK: ret
 define void @or_i2_as_switch_input(i2 %a) {
 entry:
   br label %for.body
 

 
 ; Make sure we unswitch %a == !0 out of the loop. Even we do not
 ; have it as a case value. Unswitching it out allows us to simplify
 ; the or operator chain.
 ;
 ; CHECK: define void @or_i2_as_switch_input_unswitch_default(i2
 ; CHECK: entry:
 ; This is an indication that the loop has been unswitched.
-; CHECK: freeze i2 %a
-; CHECK: icmp eq i2 %a.fr, -1
+; CHECK: icmp eq i2 %a, -1
 ; CHECK: br
 ; There should be no more unswitching after the 1st unswitch.
 ; CHECK-NOT: icmp eq
 ; CHECK: ret
 define void @or_i2_as_switch_input_unswitch_default(i2 %a) {
 entry:
   br label %for.body
 

test/Transforms/LoopUnswitch/copy-metadata.ll

 ; RUN: opt < %s -loop-unswitch -S < %s 2>&1 | FileCheck %s
 
 ; This test checks if unswitched condition preserve make.implicit metadata.
 
 define i32 @test(i1 %cond) {
 ; CHECK-LABEL: @test(
-; CHECK: %cond.fr = freeze i1 %cond
-; CHECK: br i1 %cond.fr, label %..split_crit_edge, label %.loop_exit.split_crit_edge, !make.implicit !0
+; CHECK: br i1 %cond, label %..split_crit_edge, label %.loop_exit.split_crit_edge, !make.implicit !0
   br label %loop_begin
 
 loop_begin:
   br i1 %cond, label %continue, label %loop_exit, !make.implicit !0
 
 continue:
   call void @some_func()
   br label %loop_begin
 
 loop_exit:
   ret i32 0
 }
 
 declare void @some_func()
 
 !0 = !{}

test/Transforms/LoopUnswitch/freeze.ll

-; 6 test cases which must introduce a freeze instruction after loop unswitch
+; 4 Test cases which must introduce a freeze instruction after loop unswitch
+; , and 2 test cases which must not introduce a freeze instruction
 ; RUN: opt < %s -loop-simplify -loop-rotate -loop-unswitch -S | FileCheck %s
 
 @x = common global i32 0, align 4
 define i32 @emptyf()  {
 entry:
   ret i32 0
 }
 declare i32 @g(i32) 

 ; }
 
 ; CHECK: define i32 @f_freeze5(i32 %a, i32 %b) {
 define i32 @f_freeze5(i32 %a, i32 %b)  {
 entry:
   br label %for.cond
 
 ; CHECK: %cmp1 = icmp eq i32 %b, 0
-; CHECK-NEXT: %cmp1.fr = freeze i1 %cmp1
-; CHECK-NEXT: br i1 %cmp1.fr, label %for.body.lr.ph.split.us, label %for.body.lr.ph.for.body.lr.ph.split_crit_edge
+; CHECK-NEXT: br i1 %cmp1, label %for.body.lr.ph.split.us, label %for.body.lr.ph.for.body.lr.ph.split_crit_edge
 
 for.cond:                                         ; preds = %for.inc, %entry
   %sum.0 = phi i32 [ 0, %entry ], [ %sum.1, %for.inc ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc2, %for.inc ]
   %cmp = icmp slt i32 %i.0, %a
   br i1 %cmp, label %for.body, label %for.end
 
 for.body:                                         ; preds = %for.cond

 ; }
 
 ; CHECK: define i32 @f_freeze6(i32 %a, i32 %b) {
 define i32 @f_freeze6(i32 %a, i32 %b)  {
 entry:
   br label %for.cond
 
 ; CHECK: %cmp1 = icmp eq i32 %b, 0
-; CHECK-NEXT: %cmp1.fr = freeze i1 %cmp1
-; CHECK-NEXT: br i1 %cmp1.fr, label %for.body.lr.ph.split.us, label %for.body.lr.ph.for.body.lr.ph.split_crit_edge
+; CHECK-NEXT: br i1 %cmp1, label %for.body.lr.ph.split.us, label %for.body.lr.ph.for.body.lr.ph.split_crit_edge
 
 for.cond:                                         ; preds = %for.inc, %entry
   %sum.0 = phi i32 [ 0, %entry ], [ %sum.1, %for.inc ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc4, %for.inc ]
   %cmp = icmp slt i32 %i.0, %a
   br i1 %cmp, label %for.body, label %for.end
 
 for.body:                                         ; preds = %for.cond

test/Transforms/LoopUnswitch/infinite-loop.ll

 ; REQUIRES: asserts
 ; RUN: opt -loop-unswitch -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s
 ; RUN: opt -loop-unswitch -simplifycfg -S < %s | FileCheck %s
 ; PR5373
 
 ; Loop unswitching shouldn't trivially unswitch the true case of condition %a
 ; in the code here because it leads to an infinite loop. While this doesn't
 ; contain any instructions with side effects, it's still a kind of side effect.
 ; It can trivially unswitch on the false cas of condition %a though.
 
 ; STATS: 2 loop-unswitch - Number of branches unswitched
 ; STATS: 2 loop-unswitch - Number of unswitches that are trivial
 
 ; CHECK-LABEL: @func_16(
 ; CHECK-NEXT: entry:
-; CHECK-NEXT: %b.fr = freeze i1 %b
-; CHECK-NEXT: %a.fr = freeze i1 %a
-; CHECK-NEXT: br i1 %a.fr, label %entry.split, label %abort0.split
+; CHECK-NEXT: br i1 %a, label %entry.split, label %abort0.split
 
 ; CHECK: entry.split:
-; CHECK-NEXT: br i1 %b.fr, label %for.body, label %abort1.split
+; CHECK-NEXT: br i1 %b, label %for.body, label %abort1.split
 
 ; CHECK: for.body:
 ; CHECK-NEXT: br label %for.body
 
 ; CHECK: abort0.split:
 ; CHECK-NEXT: call void @end0() [[NOR_NUW:#[0-9]+]]
 ; CHECK-NEXT: unreachable
 

test/Transforms/LoopUnswitch/msan.ll

 ; }
 ; "if (y)" is guaranteed to execute; the loop can be unswitched.
 
 define void @must_execute(i1 zeroext %x, i32 %p, i32 %q) sanitize_memory {
 ; CHECK-LABEL: @must_execute(
 entry:
 ; CHECK:       %[[Y:.*]] = load i64, i64* @y, align 8
 ; CHECK-NEXT:  %[[YB:.*]] = icmp eq i64 %[[Y]], 0
-; CHECK-NEXT:  %[[YB]].fr = freeze i1 %[[YB]]
-; CHECK-NEXT:  br i1 %[[YB]].fr,
+; CHECK-NEXT:  br i1 %[[YB]],
 
   %x2 = alloca i8, align 1
   %frombool1 = zext i1 %x to i8
   store volatile i8 %frombool1, i8* %x2, align 1
   %0 = load i64, i64* @y, align 8
   %tobool2 = icmp eq i64 %0, 0
   br label %for.body
 

test/Transforms/LoopUnswitch/trivial-unswitch.ll

 ; RUN: opt < %s -loop-unswitch -loop-unswitch-threshold=0 -verify-loop-info -S < %s 2>&1 | FileCheck %s
 
 ; This test contains two trivial unswitch condition in one loop. 
 ; LoopUnswitch pass should be able to unswitch the second one 
 ; after unswitching the first one.
 
 
-; CHECK:  %cond2.fr = freeze i1 %cond2
-; CHECK:  %cond1.fr = freeze i1 %cond1
-; CHECK:  br i1 %cond1.fr, label %..split_crit_edge, label %.loop_exit.split_crit_edge
+; CHECK:  br i1 %cond1, label %..split_crit_edge, label %.loop_exit.split_crit_edge
 
 ; CHECK:  ..split_crit_edge:                                ; preds = %0
 ; CHECK:    br label %.split
 
 ; CHECK:  .split:                                           ; preds = %..split_crit_edge
-; CHECK:    br i1 %cond2.fr, label %.split..split.split_crit_edge, label %.split.loop_exit.split1_crit_edge
+; CHECK:    br i1 %cond2, label %.split..split.split_crit_edge, label %.split.loop_exit.split1_crit_edge
 
 ; CHECK:  .split..split.split_crit_edge:                    ; preds = %.split
 ; CHECK:    br label %.split.split
 
 ; CHECK:  .split.split:                                     ; preds = %.split..split.split_crit_edge
 ; CHECK:    br label %loop_begin
 
 ; CHECK:  loop_begin:                                       ; preds = %do_something, %.split.split

 
 ; We will not be able trivially unswitch on the SwitchInst, as its input
 ; is a constant. However, since its a constant we should be able to figure
 ; out that the switch can be folded into a unconditional branch to %continue.
 ; Then we unswitch on the br inst in %continue.
 ;
 ; CHECK: define i32 @test2(
 ; This is an indication that the loop has been unswitched on %cond1.
-; CHECK:  %cond1.fr = freeze i1 %cond
-; CHECK:  br i1 %cond1.fr, label %..split_crit_edge, label %.loop_exit.split_crit_edge
+; CHECK:  br i1 %cond1, label %..split_crit_edge, label %.loop_exit.split_crit_edge
 
 ; CHECK:  ..split_crit_edge:                                ; preds = %0
 ; CHECK:    br label %.split
 
 ; CHECK:  .split:                                           ; preds = %..split_crit_edge
 ; CHECK:    br label %loop_begin
 
 ; CHECK:  loop_begin:                                       ; preds = %do_something, %.split