[SimpleLoopUnswitch] Create SimpleLoopNestUnswitch pass

[uint256_t]

Summary

This patch adds a new LoopNest pass called SimpleLoopNestUnswitch. This pass is similar to SimpleLoopUnswitch, but only unswitches branches out of a whole loop nest. In other words, this pass doesn't make branches in-between loops. This helps create/maintain a perfect loop nest.
See also https://reviews.llvm.org/D104180 for another example of creating a new LoopNest pass of existing passes.

[uint256_t]

This patch is not ready for review. I'll update the diff soon.

[uint256_t]

Ready for review

[uint256_t]

Small change

[uint256_t]

Follow clang-tidy

[jaykang10]

If possible, can you let us know what kinds of improvement this patch achieve please? like performance, code size, compile time and etc.

If we remove conditional branch inside loop, it could help loop vectorization. I am not sure the improvement from the perfect loop nest is better than that...

Maybe, other people could give you more good comments.

[uint256_t]

For example, we may have an opportunity to perform loop-interchange (or some other transformations that require a perfect loop nest) after performing simple-loop-nest-unswitch.
We can perform simple-loop-unswitch after that, so there should be no problem for loop vectorization.
What order we put passes including simple-loop-nest-unswitch in a pass pipeline is still a problem though...

[Whitney]

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2973

When given BestUnswitchTIForLoopNest, why do we want to findBestUnswitchTI?

When given BestUnswitchTIForLoopNest, this code only unswitch if BestUnswitchTIForLoopNest == findBestUnswitchTI. Is it possible that BestUnswitchTIForLoopNest != findBestUnswitchTI only have some loop level?

2976

2982

[uint256_t]

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2973

We want to findBestUnswitchTI to obtain PartialIVInfo, ExitBlocks, and BestUnswitchInvariants. However it seems we can remove some code.
I'll change the code soon.

[uint256_t]

• No longer do findBestUnswitchTI every time we call unswitchBestCondition given BestUnswitchTIForLoopNest.
• Remove the condition BestUnswitchTIForLoopNest == findBestUnswitchTI, which was confusing.

llvm/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h

 public:
   SimpleLoopUnswitchPass(bool NonTrivial = false, bool Trivial = true)
       : NonTrivial(NonTrivial), Trivial(Trivial) {}
 
   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
                         LoopStandardAnalysisResults &AR, LPMUpdater &U);
 };
 
+class SimpleLoopNestUnswitchPass
+    : public PassInfoMixin<SimpleLoopNestUnswitchPass> {
+  bool NonTrivial;
+  bool Trivial;
+
+public:
+  SimpleLoopNestUnswitchPass(bool NonTrivial = false, bool Trivial = true)
+      : NonTrivial(NonTrivial), Trivial(Trivial) {}
+
+  PreservedAnalyses run(LoopNest &LN, LoopAnalysisManager &AM,
+                        LoopStandardAnalysisResults &AR, LPMUpdater &U);
+};
+
 /// Create the legacy pass object for the simple loop unswitcher.
 ///
 /// See the documentaion for `SimpleLoopUnswitchPass` for details.
 Pass *createSimpleLoopUnswitchLegacyPass(bool NonTrivial = false);
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H

llvm/lib/Passes/PassRegistry.def

 #endif
 LOOP_PASS_WITH_PARAMS("simple-loop-unswitch",
                       "SimpleLoopUnswitchPass",
                       [](std::pair<bool, bool> Params) {
                         return SimpleLoopUnswitchPass(Params.first, Params.second);
                       },
                       parseLoopUnswitchOptions,
                       "nontrivial;no-nontrivial;trivial;no-trivial")
+LOOP_PASS_WITH_PARAMS("simple-loop-nest-unswitch",
+                      "SimpleLoopNestUnswitchPass",
+                      [](std::pair<bool, bool> Params) {
+                        return SimpleLoopNestUnswitchPass(Params.first, Params.second);
+                      },
+                      parseLoopUnswitchOptions,
+                      "nontrivial;no-nontrivial;trivial;no-trivial")
 #undef LOOP_PASS_WITH_PARAMS

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

static int CalculateUnswitchCostMultiplier(
 
   LLVM_DEBUG(dbgs() << "  Computed multiplier  " << CostMultiplier
                     << " (siblings " << SiblingsMultiplier << " * clones "
                     << (1 << ClonesPower) << ")"
                     << " for unswitch candidate: " << TI << "\n");
   return CostMultiplier;
 }
 
-static bool unswitchBestCondition(
+static Instruction *findBestUnswitchTI(
     Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC,
-    AAResults &AA, TargetTransformInfo &TTI,
-    function_ref<void(bool, bool, ArrayRef<Loop *>)> UnswitchCB,
-    ScalarEvolution *SE, MemorySSAUpdater *MSSAU) {
+    AAResults &AA, TargetTransformInfo &TTI, ScalarEvolution *SE,
+    MemorySSAUpdater *MSSAU, IVConditionInfo &PartialIVInfo,
+    SmallVector<BasicBlock *, 4> &ExitBlocks,
+    TinyPtrVector<Value *> &BestUnswitchInvariants, bool LoopNestMode = false) {
+
   // Collect all invariant conditions within this loop (as opposed to an inner
   // loop which would be handled when visiting that inner loop).
   SmallVector<std::pair<Instruction *, TinyPtrVector<Value *>>, 4>
       UnswitchCandidates;
 
   // Whether or not we should also collect guards in the loop.
   bool CollectGuards = false;
   if (UnswitchGuards) {
     auto *GuardDecl = L.getHeader()->getParent()->getParent()->getFunction(
         Intrinsic::getName(Intrinsic::experimental_guard));
     if (GuardDecl && !GuardDecl->use_empty())
       CollectGuards = true;
   }
 
-  IVConditionInfo PartialIVInfo;
   for (auto *BB : L.blocks()) {
-    if (LI.getLoopFor(BB) != &L)
+    if (!LoopNestMode && LI.getLoopFor(BB) != &L)
       continue;
 
     if (CollectGuards)
       for (auto &I : *BB)
         if (isGuard(&I)) {
           auto *Cond = cast<IntrinsicInst>(&I)->getArgOperand(0);
           // TODO: Support AND, OR conditions and partial unswitching.
           if (!isa<Constant>(Cond) && L.isLoopInvariant(Cond))
if (auto Info = hasPartialIVCondition(L, MSSAThreshold, *MSSA, AA)) {
         ValsToDuplicate.push_back(Inst);
       UnswitchCandidates.push_back(
           {L.getHeader()->getTerminator(), std::move(ValsToDuplicate)});
     }
   }
 
   // If we didn't find any candidates, we're done.
   if (UnswitchCandidates.empty())
-    return false;
+    return nullptr;
 
   // Check if there are irreducible CFG cycles in this loop. If so, we cannot
   // easily unswitch non-trivial edges out of the loop. Doing so might turn the
   // irreducible control flow into reducible control flow and introduce new
   // loops "out of thin air". If we ever discover important use cases for doing
   // this, we can add support to loop unswitch, but it is a lot of complexity
   // for what seems little or no real world benefit.
   LoopBlocksRPO RPOT(&L);
   RPOT.perform(&LI);
   if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
-    return false;
+    return nullptr;
 
-  SmallVector<BasicBlock *, 4> ExitBlocks;
   L.getUniqueExitBlocks(ExitBlocks);
 
   // We cannot unswitch if exit blocks contain a cleanuppad/catchswitch
   // instruction as we don't know how to split those exit blocks.
   // FIXME: We should teach SplitBlock to handle this and remove this
   // restriction.
   for (auto *ExitBB : ExitBlocks) {
     auto *I = ExitBB->getFirstNonPHI();
     if (isa<CleanupPadInst>(I) || isa<CatchSwitchInst>(I)) {
       LLVM_DEBUG(dbgs() << "Cannot unswitch because of cleanuppad/catchswitch "
                            "in exit block\n");
-      return false;
+      return nullptr;
     }
   }
 
   LLVM_DEBUG(
       dbgs() << "Considering " << UnswitchCandidates.size()
              << " non-trivial loop invariant conditions for unswitching.\n");
 
   // Given that unswitching these terminators will require duplicating parts of
static Instruction *findBestUnswitchTI(
   InstructionCost LoopCost = 0;
   for (auto *BB : L.blocks()) {
     InstructionCost Cost = 0;
     for (auto &I : *BB) {
       if (EphValues.count(&I))
         continue;
 
       if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB))
-        return false;
+        return nullptr;
       if (auto *CB = dyn_cast<CallBase>(&I))
         if (CB->isConvergent() || CB->cannotDuplicate())
-          return false;
+          return nullptr;
 
       Cost += TTI.getUserCost(&I, CostKind);
     }
     assert(Cost >= 0 && "Must not have negative costs!");
     LoopCost += Cost;
     assert(LoopCost >= 0 && "Must not have negative loop costs!");
     BBCostMap[BB] = Cost;
   }
auto ComputeUnswitchedCost = [&](Instruction &TI,
     // will be materialized if we decide to unswitch it.
     int SuccessorsCount = isGuard(&TI) ? 2 : Visited.size();
     assert(SuccessorsCount > 1 &&
            "Cannot unswitch a condition without multiple distinct successors!");
     return (LoopCost - Cost) * (SuccessorsCount - 1);
   };
   Instruction *BestUnswitchTI = nullptr;
   InstructionCost BestUnswitchCost = 0;
-  ArrayRef<Value *> BestUnswitchInvariants;
   for (auto &TerminatorAndInvariants : UnswitchCandidates) {
     Instruction &TI = *TerminatorAndInvariants.first;
-    ArrayRef<Value *> Invariants = TerminatorAndInvariants.second;
+    TinyPtrVector<Value *> Invariants = TerminatorAndInvariants.second;
     BranchInst *BI = dyn_cast<BranchInst>(&TI);
     InstructionCost CandidateCost = ComputeUnswitchedCost(
         TI, /*FullUnswitch*/ !BI || (Invariants.size() == 1 &&
                                      Invariants[0] == BI->getCondition()));
     // Calculate cost multiplier which is a tool to limit potentially
     // exponential behavior of loop-unswitch.
     if (EnableUnswitchCostMultiplier) {
       int CostMultiplier =
if (!BestUnswitchTI || CandidateCost < BestUnswitchCost) {
       BestUnswitchInvariants = Invariants;
     }
   }
   assert(BestUnswitchTI && "Failed to find loop unswitch candidate");
 
   if (BestUnswitchCost >= UnswitchThreshold) {
     LLVM_DEBUG(dbgs() << "Cannot unswitch, lowest cost found: "
                       << BestUnswitchCost << "\n");
-    return false;
+    return nullptr;
   }
 
   if (BestUnswitchTI != PartialIVCondBranch)
     PartialIVInfo.InstToDuplicate.clear();
 
   // If the best candidate is a guard, turn it into a branch.
   if (isGuard(BestUnswitchTI))
     BestUnswitchTI = turnGuardIntoBranch(cast<IntrinsicInst>(BestUnswitchTI), L,
                                          ExitBlocks, DT, LI, MSSAU);
 
   LLVM_DEBUG(dbgs() << "  Unswitching non-trivial (cost = "
                     << BestUnswitchCost << ") terminator: " << *BestUnswitchTI
                     << "\n");
+
+  return BestUnswitchTI;
+}
+
+static bool unswitchBestCondition(
+    Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC,
+    AAResults &AA, TargetTransformInfo &TTI,
+    function_ref<void(bool, bool, ArrayRef<Loop *>)> UnswitchCB,
+    ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
+    Instruction *BestUnswitchTIForLoopNest = nullptr,
+    TinyPtrVector<Value *> *BestUnswitchInvariantsForLoopNest = nullptr) {
+  IVConditionInfo PartialIVInfo;
+  SmallVector<BasicBlock *, 4> ExitBlocks;
+
+  if (BestUnswitchTIForLoopNest && BestUnswitchInvariantsForLoopNest) {
+    L.getUniqueExitBlocks(ExitBlocks);
+
+    if (MSSAU &&
+        !findOptionMDForLoop(&L, "llvm.loop.unswitch.partial.disable") &&
+        BestUnswitchTIForLoopNest != L.getHeader()->getTerminator()) {
+      MemorySSA *MSSA = MSSAU->getMemorySSA();
+      if (auto Info = hasPartialIVCondition(L, MSSAThreshold, *MSSA, AA)) {
+        PartialIVInfo = *Info;
+      }
+    }
+
+    unswitchNontrivialInvariants(
+        L, *BestUnswitchTIForLoopNest, *BestUnswitchInvariantsForLoopNest,
+        ExitBlocks, PartialIVInfo, DT, LI, AC, UnswitchCB, SE, MSSAU);
+
+    return true;
+  }
+
+  TinyPtrVector<Value *> BestUnswitchInvariants;
+
+  Instruction *BestUnswitchTI =
+      findBestUnswitchTI(L, DT, LI, AC, AA, TTI, SE, MSSAU, PartialIVInfo,
+                         ExitBlocks, BestUnswitchInvariants);
+
+  if (!BestUnswitchTI)
+    return false;
+
   unswitchNontrivialInvariants(L, *BestUnswitchTI, BestUnswitchInvariants,
                                ExitBlocks, PartialIVInfo, DT, LI, AC,
                                UnswitchCB, SE, MSSAU);
+
   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
 /// well by cloning the loop if the result is small enough.
 ///
 /// The `DT`, `LI`, `AC`, `AA`, `TTI` parameters are required analyses that are
 /// also updated based on the unswitch. The `MSSA` analysis is also updated if
 /// valid (i.e. its use is enabled).
 ///
 /// If either `NonTrivial` is true or the flag `EnableNonTrivialUnswitch` is
 /// true, we will attempt to do non-trivial unswitching as well as trivial
 /// unswitching.
 ///
 /// The `UnswitchCB` callback provided will be run after unswitching is
 /// complete, with the first parameter set to `true` if the provided loop
 /// remains a loop, and a list of new sibling loops created.
 ///
 /// If `SE` is non-null, we will update that analysis based on the unswitching
 /// done.
-static bool
-unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC,
-             AAResults &AA, TargetTransformInfo &TTI, bool Trivial,
-             bool NonTrivial,
-             function_ref<void(bool, bool, ArrayRef<Loop *>)> UnswitchCB,
-             ScalarEvolution *SE, MemorySSAUpdater *MSSAU) {
+static bool unswitchLoop(
+    Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC,
+    AAResults &AA, TargetTransformInfo &TTI, bool Trivial, bool NonTrivial,
+    ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
+    Instruction *BestUnswitchTIForLoopNest = nullptr,
+    TinyPtrVector<Value *> *BestUnswitchInvariantsForLoopNest = nullptr) {
   assert(L.isRecursivelyLCSSAForm(DT, LI) &&
          "Loops must be in LCSSA form before unswitching.");
 
   // Must be in loop simplified form: we need a preheader and dedicated exits.
   if (!L.isLoopSimplifyForm())
     return false;
 
   // Try trivial unswitch first before loop over other basic blocks in the loop.
static bool unswitchLoop(
   // For non-trivial unswitching, because it often creates new loops, we rely on
   // the pass manager to iterate on the loops rather than trying to immediately
   // reach a fixed point. There is no substantial advantage to iterating
   // internally, and if any of the new loops are simplified enough to contain
   // trivial unswitching we want to prefer those.
 
   // Try to unswitch the best invariant condition. We prefer this full unswitch to
   // a partial unswitch when possible below the threshold.
-  if (unswitchBestCondition(L, DT, LI, AC, AA, TTI, UnswitchCB, SE, MSSAU))
+  if (unswitchBestCondition(L, DT, LI, AC, AA, TTI, UnswitchCB, SE, MSSAU,
+                            BestUnswitchTIForLoopNest,
+                            BestUnswitchInvariantsForLoopNest))
     return true;
 
   // No other opportunities to unswitch.
   return false;
 }
 
 PreservedAnalyses SimpleLoopUnswitchPass::run(Loop &L, LoopAnalysisManager &AM,
                                               LoopStandardAnalysisResults &AR,
PreservedAnalyses SimpleLoopUnswitchPass::run(Loop &L, LoopAnalysisManager &AM,
   assert(AR.DT.verify(DominatorTree::VerificationLevel::Fast));
 
   auto PA = getLoopPassPreservedAnalyses();
   if (AR.MSSA)
     PA.preserve<MemorySSAAnalysis>();
   return PA;
 }
 
+PreservedAnalyses
+SimpleLoopNestUnswitchPass::run(LoopNest &LN, LoopAnalysisManager &AM,
+                                LoopStandardAnalysisResults &AR,
+                                LPMUpdater &U) {
+  bool DidSomething = false;
+  ArrayRef<Loop *> Loops = LN.getLoops();
+  Loop *OutermostLoop = &LN.getOutermostLoop();
+
+  SmallPriorityWorklist<Loop *, 4> Worklist;
+  appendLoopsToWorklist(Loops, Worklist);
+
+  IVConditionInfo PartialIVInfo;
+  SmallVector<BasicBlock *, 4> ExitBlocks;
+  TinyPtrVector<Value *> BestUnswitchInvariantsForLoopNest;
+
+  Optional<MemorySSAUpdater> MSSAU;
+  if (AR.MSSA) {
+    MSSAU = MemorySSAUpdater(AR.MSSA);
+    if (VerifyMemorySSA)
+      AR.MSSA->verifyMemorySSA();
+  }
+
+  Instruction *BestUnswitchTIForLoopNest = findBestUnswitchTI(
+      *OutermostLoop, AR.DT, AR.LI, AR.AC, AR.AA, AR.TTI, &AR.SE,
+      MSSAU.hasValue() ? MSSAU.getPointer() : nullptr, PartialIVInfo,
+      ExitBlocks, BestUnswitchInvariantsForLoopNest, true);
+
+  if (!BestUnswitchTIForLoopNest)
+    return PreservedAnalyses::all();
+
+  while (!Worklist.empty()) {
+    Loop *L = Worklist.pop_back_val();
+
+    Function &F = *L->getHeader()->getParent();
+    (void)F;
+
+    LLVM_DEBUG(dbgs() << "Unswitching loop in " << F.getName() << ": " << *L
+                      << "\n");
+
+    // Save the current loop name in a variable so that we can report it even
+    // after it has been deleted.
+    std::string LoopName = std::string(L->getName());
+
+    auto UnswitchCB = [&L, &U, &LoopName, &OutermostLoop](
+                          bool CurrentLoopValid, bool PartiallyInvariant,
+                          ArrayRef<Loop *> NewLoops) {
+      // If we did a non-trivial unswitch, we have added new (cloned) loops.
+      if (OutermostLoop == L && !NewLoops.empty())
+        U.addSiblingLoops(NewLoops);
+
+      // If the current loop remains valid, we should revisit it to catch any
+      // other unswitch opportunities. Otherwise, we need to mark it as deleted.
+      if (CurrentLoopValid) {
+        if (PartiallyInvariant) {
+          // Mark the new loop as partially unswitched, to avoid unswitching on
+          // the same condition again.
+          auto &Context = L->getHeader()->getContext();
+          MDNode *DisableUnswitchMD = MDNode::get(
+              Context,
+              MDString::get(Context, "llvm.loop.unswitch.partial.disable"));
+          MDNode *NewLoopID = makePostTransformationMetadata(
+              Context, L->getLoopID(), {"llvm.loop.unswitch.partial"},
+              {DisableUnswitchMD});
+          L->setLoopID(NewLoopID);
+        } else
+          U.revisitCurrentLoop();
+      } else
+        U.markLoopAsDeleted(*L, LoopName);
+    };
+
+    DidSomething |= unswitchLoop(
+        *L, AR.DT, AR.LI, AR.AC, AR.AA, AR.TTI, Trivial, NonTrivial, UnswitchCB,
+        &AR.SE, MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
+        BestUnswitchTIForLoopNest, &BestUnswitchInvariantsForLoopNest);
+
+    assert(DidSomething && "L must be unswitched");
+
+    if (AR.MSSA && VerifyMemorySSA)
+      AR.MSSA->verifyMemorySSA();
+
+    // Historically this pass has had issues with the dominator tree so verify
+    // it in asserts builds.
+    assert(AR.DT.verify(DominatorTree::VerificationLevel::Fast));
+  }
+
+  auto PA = getLoopPassPreservedAnalyses();
+  if (AR.MSSA)
+    PA.preserve<MemorySSAAnalysis>();
+  return PA;
+}
+
 namespace {
 
 class SimpleLoopUnswitchLegacyPass : public LoopPass {
   bool NonTrivial;
 
 public:
   static char ID; // Pass ID, replacement for typeid
 

llvm/test/Transforms/SimpleLoopUnswitch/loop-nest-unswitch.ll

+; RUN: opt -passes='simple-loop-nest-unswitch<nontrivial>' -S < %s | FileCheck %s --check-prefixes CHECK,SLNU
+; RUN: opt -passes='simple-loop-unswitch<nontrivial>' -S < %s | FileCheck %s --check-prefixes CHECK,SLU
+
+; This test represents the following code:
+;
+; int test(bool flag, int n) {
+;   int sum = 0;
+;   for (int i = 0; i < n; i++) {
+;     for (int k = 0; k < n; k++) {
+;       sum++;
+;       if (flag)
+;         sum++;
+;     }
+;   }
+;   return sum;
+; }
+;
+; Both SimpleLoopUnswitch and SimpleLoopNestUnswitch do unswitching.
+
+define dso_local i32 @test(i1 zeroext %flag, i32 %n) {
+; CHECK-LABEL: test
+entry:
+  %frombool = zext i1 %flag to i8
+  %tobool = trunc i8 %frombool to i1
+  br label %for.cond
+
+; Check if SimpleLoopNestUnswitch creates new blocks for unswitching
+; CHECK: entry.split.us
+; CHECK: for.cond.us
+; CHECK: for.body.us
+; CHECK: for.inc6.us
+; CHECK: for.end.us
+; CHECK: for.body.split.us.us
+; CHECK: for.cond1.us.us
+; CHECK: for.body3.us.us
+; CHECK: if.then.us.us
+; CHECK: if.end.us.us
+; CHECK: for.inc.us.us
+; CHECK: for.end.split.us.us
+; CHECK: for.end8.split.us
+
+for.cond:                                         ; preds = %for.inc6, %entry
+  %sum.0 = phi i32 [ 0, %entry ], [ %sum.1.lcssa, %for.inc6 ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc7, %for.inc6 ]
+  %cmp = icmp slt i32 %i.0, %n
+  br i1 %cmp, label %for.body, label %for.end8
+
+for.body:                                         ; preds = %for.cond
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc, %for.body
+  %sum.1 = phi i32 [ %sum.0, %for.body ], [ %sum.2, %for.inc ]
+  %k.0 = phi i32 [ 0, %for.body ], [ %inc5, %for.inc ]
+  %cmp2 = icmp slt i32 %k.0, %n
+  br i1 %cmp2, label %for.body3, label %for.end
+
+for.body3:                                        ; preds = %for.cond1
+  %inc = add nsw i32 %sum.1, 1
+  br i1 %tobool, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.body3
+  %inc4 = add nsw i32 %inc, 1
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %for.body3
+  %sum.2 = phi i32 [ %inc4, %if.then ], [ %inc, %for.body3 ]
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %inc5 = add nsw i32 %k.0, 1
+  br label %for.cond1, !llvm.loop !0
+
+for.end:                                          ; preds = %for.cond1
+  %sum.1.lcssa = phi i32 [ %sum.1, %for.cond1 ]
+  br label %for.inc6
+
+for.inc6:                                         ; preds = %for.end
+  %inc7 = add nsw i32 %i.0, 1
+  br label %for.cond, !llvm.loop !2
+
+for.end8:                                         ; preds = %for.cond
+  %sum.0.lcssa = phi i32 [ %sum.0, %for.cond ]
+  ret i32 %sum.0.lcssa
+}
+
+; This test represents the following code:
+;
+; int test2(int n) {
+;   int sum = 0;
+;   for (int i = 0; i < n; i++) {
+;     for (int k = 0; k < n; k++) {
+;       sum++;
+;       if (i == 10)
+;         sum++;
+;     }
+;   }
+;   return sum;
+; }
+;
+; We don't want to unswitch the branch `if (i == 10)` out of for-k because
+; it prevents the loop nest from being a perfect loop nest. This test shows
+; that SimpleLoopUnswitch unswitches the branch, but SimpleLoopNestUnswitch doesn't.
+
+define dso_local i32 @test2(i32 %n) {
+; CHECK-LABEL: test2
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc7, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc8, %for.inc7 ]
+  %sum.0 = phi i32 [ 0, %entry ], [ %sum.1.lcssa, %for.inc7 ]
+  %cmp = icmp slt i32 %i.0, %n
+  br i1 %cmp, label %for.body, label %for.end9
+
+for.body:                                         ; preds = %for.cond
+  %cmp4 = icmp eq i32 %i.0, 10
+  br label %for.cond1
+
+; SLU: for.body.split.us:
+; SLU: for.cond1.us:
+; SLU: for.body3.us:
+; SLU: if.then.us:
+; SLU: if.end.us:
+; SLU: for.inc.us:
+; SLU: for.end.split.us:
+; SLU: for.body.split:
+; SLNU-NOT: for.body.split.us:
+; SLNU-NOT: for.cond1.us:
+; SLNU-NOT: for.body3.us:
+; SLNU-NOT: if.then.us:
+; SLNU-NOT: if.end.us:
+; SLNU-NOT: for.inc.us:
+; SLNU-NOT: for.end.split.us:
+; SLNU-NOT: for.body.split:
+
+for.cond1:                                        ; preds = %for.inc, %for.body
+  %sum.1 = phi i32 [ %sum.0, %for.body ], [ %sum.2, %for.inc ]
+  %k.0 = phi i32 [ 0, %for.body ], [ %inc6, %for.inc ]
+  %cmp2 = icmp slt i32 %k.0, %n
+  br i1 %cmp2, label %for.body3, label %for.end
+
+for.body3:                                        ; preds = %for.cond1
+  %inc = add nsw i32 %sum.1, 1
+  br i1 %cmp4, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.body3
+  %inc5 = add nsw i32 %inc, 1
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %for.body3
+  %sum.2 = phi i32 [ %inc5, %if.then ], [ %inc, %for.body3 ]
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %inc6 = add nsw i32 %k.0, 1
+  br label %for.cond1, !llvm.loop !0
+
+for.end:                                          ; preds = %for.cond1
+  %sum.1.lcssa = phi i32 [ %sum.1, %for.cond1 ]
+  br label %for.inc7
+
+for.inc7:                                         ; preds = %for.end
+  %inc8 = add nsw i32 %i.0, 1
+  br label %for.cond, !llvm.loop !2
+
+for.end9:                                         ; preds = %for.cond
+  %sum.0.lcssa = phi i32 [ %sum.0, %for.cond ]
+  ret i32 %sum.0.lcssa
+}
+
+!0 = distinct !{!0, !1}
+!1 = !{!"llvm.loop.mustprogress"}
+!2 = distinct !{!2, !1}
+