[LoopPeel] Peel loops with exits followed by an unreachable or deopt block

[dmakogon]

Summary

Added support for peeling loops with exits that are followed either by an unreachable-terminated block or block that has a terminatnig deoptimize call. All blocks in the sequence must have an unique successor, maybe except for the last one.

[lebedev.ri]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

504

Nice, i was about to ask for that.
But doesn't this lead to the issues with branch weights discussed in D108108?

[mkazantsev]

llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h

132

This comment doesn't correspond to what you really want. Imagine that a block has 2 successors, one being deoptimizing and another is just a regular block. It falls into category "any of its children is deoptimizing", but it's definitely not what you are looking for.

What I suggest is to rewrite it like "Check if we can prove that all paths starting from this block will converge to a block that is terminated by unreachable".

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

490

What DeoptimizingBlocks is used for? To me it looks like a complete doubler of VisitedBlocks. Also no good reason for it to be a parameter.

493

Use SmallPtrSet. contains checks in vector are expensive.

494

Looks like it may be done much easier.

while(BB && VisitedBlocks.insert(BB).second) {
  if ([terminates with unreachable](BB))
    return true;
   BB = BB->getSingleSuccessor();
 }
return false;

Please check if it's what you meant here, and simplify the code.

[mkazantsev]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

504

Well, it doesn't introduce a new bug, it just expands the scope of the existing problem. I'm pretty sure it's relatively safe to always set "many:1" metadata for unreached blocks, but need more digging to understand the impact of this.

512

Compile time-wise, I'd prefer to have traversal limit set by an option. In worst case, you'll need to walk dozens blocks for each exit, and here is where things may go astray.

[dmakogon]

Rewritten IsBlockDeoptimizing in a simpler way with the use of SmallPtrSet.
Added an option to limit the maximum traversed block chain depth.

[mkazantsev]

llvm/lib/Transforms/Utils/LoopPeel.cpp

758

Instead of this, please fill a SmallVector with DomTreeUpdates and then DT->applyUpdates once. It's a more canonical way of doing this.

[mkazantsev]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

488

This name is misleading. It's not always deoptimizing (if it ends with unreachable), and neither *this* block is deoptimizing. Maybe smth like IsBlockFollowedByDeoptOrUnreached?

496

There is one thing that bugs me. Imagine a sutiation:

loop_exit:
  call foo() // will not return, but is not a deopt
  unreachable

I'm not sure if it's bad actually. But maybe we should consider checking all other (non deopt) instruction with isGuaranteedToTransferExecutionToSuccessor. Opinions?

[lebedev.ri]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

496

This is actually exactly the situation would have wanted to ask to be supported.

[dmakogon]

Renamed IsBlockDeoptimizing to IsBlockFollowedByDeoptOrUnreachable
DT is now updated using applyUpdates

[mkazantsev]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

496

Do you mean "supported" as "let's peel it" or "let's NOT peel it unless we know unreachable WILL execute"? :)

[lebedev.ri]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

496

"let's peel it"

[mkazantsev]

In that case everything since done; @dmakogon pls add one more test with single-exit non-throwing unreachable exit and I think we can go with it, unless someone has cons.

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

496

Ok, we peel it now. :)

[lebedev.ri]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

496

:)

[foad]

This causes lots of lit test failures in an LLVM_ENABLE_EXPENSIVE_CHECKS build. Can you please fix or revert?

Failed Tests (26):
  LLVM :: ThinLTO/X86/function_entry_count.ll
  LLVM :: Transforms/LoopFusion/guarded_peel.ll
  LLVM :: Transforms/LoopFusion/peel.ll
  LLVM :: Transforms/LoopUnroll/Hexagon/peel-small-loop.ll
  LLVM :: Transforms/LoopUnroll/dce.ll
  LLVM :: Transforms/LoopUnroll/peel-loop-conditions-pgo-1.ll
  LLVM :: Transforms/LoopUnroll/peel-loop-conditions-pgo-2.ll
  LLVM :: Transforms/LoopUnroll/peel-loop-conditions.ll
  LLVM :: Transforms/LoopUnroll/peel-loop-inner.ll
  LLVM :: Transforms/LoopUnroll/peel-loop-nests.ll
  LLVM :: Transforms/LoopUnroll/peel-loop-noalias-scope-decl.ll
  LLVM :: Transforms/LoopUnroll/peel-loop-not-forced.ll
  LLVM :: Transforms/LoopUnroll/peel-loop-pgo-deopt-idom-2.ll
  LLVM :: Transforms/LoopUnroll/peel-loop-pgo-deopt-idom.ll
  LLVM :: Transforms/LoopUnroll/peel-loop-pgo-deopt.ll
  LLVM :: Transforms/LoopUnroll/peel-loop-pgo.ll
  LLVM :: Transforms/LoopUnroll/peel-loop-scev-invalidate.ll
  LLVM :: Transforms/LoopUnroll/peel-loop.ll
  LLVM :: Transforms/LoopUnroll/peel-loop2.ll
  LLVM :: Transforms/LoopUnroll/peel-multiple-unreachable-exits.ll
  LLVM :: Transforms/LoopUnroll/pr33437.ll
  LLVM :: Transforms/LoopUnroll/pr45939-peel-count-and-complete-unroll.ll
  LLVM :: Transforms/LoopUnroll/unroll-after-peel.ll
  LLVM :: Transforms/LoopUnroll/unroll-heuristics-pgo.ll
  LLVM :: Transforms/LoopUnroll/wrong_assert_in_peeling.ll
  LLVM :: Transforms/PhaseOrdering/X86/peel-before-lv-to-enable-vectorization.ll

[mkazantsev]

Reverted, Dima pls investigate.

[dmakogon]

Fixed failing tests with expensive checks enabled. Forgot to remove the DT->verify check that happened every iteration after all needed DT updates which were applied immediately, but with the patch we store some updates to apply them all later at once.

[aeubanks]

This causes crashes, reverting

$ ./build/rel/bin/opt -passes=loop-unroll-full /tmp/b.ll -disable-output
opt: ../../llvm/include/llvm/Support/CFGUpdate.h:87: void llvm::cfg::LegalizeUpdates(ArrayRef<Update<NodePtr>>, SmallVectorImpl<Update<NodePtr>> &, bool, bool) [NodePtr = llvm::BasicBlock *]: Assertion `std::abs(NumInsertions) <= 1 && "Unbalanced operations!"' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace.
Stack dump:
0.      Program arguments: ./build/rel/bin/opt -passes=loop-unroll-full /tmp/b.ll -disable-output
 #0 0x0000000001f01953 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /usr/local/google/home/aeubanks/repos/llvm-project/build/rel/../../llvm/lib/Support/Unix/Signals.inc:565:13
 #1 0x0000000001eff7ce llvm::sys::RunSignalHandlers() /usr/local/google/home/aeubanks/repos/llvm-project/build/rel/../../llvm/lib/Support/Signals.cpp:98:18
 #2 0x0000000001f01cbf SignalHandler(int) /usr/local/google/home/aeubanks/repos/llvm-project/build/rel/../../llvm/lib/Support/Unix/Signals.inc:407:1
 #3 0x00007f998f9e7140 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x14140)
 #4 0x00007f998f4c6ce1 raise ./signal/../sysdeps/unix/sysv/linux/raise.c:51:1
 #5 0x00007f998f4b0537 abort ./stdlib/abort.c:81:7
 #6 0x00007f998f4b040f get_sysdep_segment_value ./intl/loadmsgcat.c:509:8
 #7 0x00007f998f4b040f _nl_load_domain ./intl/loadmsgcat.c:970:34
 #8 0x00007f998f4bf662 (/lib/x86_64-linux-gnu/libc.so.6+0x34662)
 #9 0x0000000001539fd3 AdvancePastEmptyBuckets /usr/local/google/home/aeubanks/repos/llvm-project/build/rel/../../llvm/include/llvm/ADT/DenseMap.h:1281:5
#10 0x0000000001539fd3 operator++ /usr/local/google/home/aeubanks/repos/llvm-project/build/rel/../../llvm/include/llvm/ADT/DenseMap.h:1271:5
#11 0x0000000001539fd3 void llvm::cfg::LegalizeUpdates<llvm::BasicBlock*>(llvm::ArrayRef<llvm::cfg::Update<llvm::BasicBlock*> >, llvm::SmallVectorImpl<llvm::cfg::Update<llvm::BasicBlock*> >&, bool, bool) /usr/local/google/home/aeubanks/repos/llvm-project/build/rel/../../llvm/include/llvm/Support/CFGUpdate.h:85:17
#12 0x0000000001537265 llvm::GraphDiff<llvm::BasicBlock*, false>::GraphDiff(llvm::ArrayRef<llvm::cfg::Update<llvm::BasicBlock*> >, bool) /usr/local/google/home/aeubanks/repos/llvm-project/build/rel/../../llvm/include/llvm/Support/CFGDiff.h:0:5
#13 0x00000000025a0809 applyUpdates /usr/local/google/home/aeubanks/repos/llvm-project/build/rel/../../llvm/include/llvm/Support/GenericDomTree.h:547:5
#14 0x00000000025a0809 llvm::peelLoop(llvm::Loop*, unsigned int, llvm::LoopInfo*, llvm::ScalarEvolution*, llvm::DominatorTree*, llvm::AssumptionCache*, bool) /usr/local/google/home/aeubanks/repos/llvm-project/build/rel/../../llvm/lib/Transforms/Utils/LoopPeel.cpp:803:7

b.ll3 KBDownload

[mkazantsev]

Thanks @aeubanks! I've checked in your test as test/Transforms/LoopUnroll/revert-D110922.ll to not skip this again. @dmakogon pls investigate.

[dmakogon]

Fixed crash on test/Transforms/LoopUnroll/revert-D110922.ll. It happened due to adding the same edges to DomTree due to the fact that one of the loop exiting blocks had a switch terminator and there were multiple edges from that exiting block to an exit. Now we construct a set from the loop exiting edges and then add edge insertion updates only for edges from the set.

[reames]

Two drive by comments.

One the surface, this seems like it should be two changes. One to do an NFC restructuring of the domtree updates. One to actually enable the broader scope.

The description of the change also needs updated. An exit reaching an unreachable is *not* a "deoptimizing" exit.

[mkazantsev]

+1 to spliting off dom tree update, especially since it was causing troubles.

[dmakogon]

Split the patch into 2:

1. D111611 changes the way DT is updated,
2. This patch adds support for peeling loops with exits followed by unreachable or deopt blocks.

Also changed this patch's title and description to address Philip's comment.

[mkazantsev]

Do I understand correctly that the reason of crash was duplicating exiting edges, which caused duplicating DT, and this is now fixed in D111611?

[mkazantsev]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

56

Please rename the option and change description, taking Philip's comment into account. Unreachable-terminated block is not a deopt block.

[dmakogon]

Rebase.

Updated name of the option which limits the maximum path length when checking whether a BB is followed by an unreachable or deoptimizing block.

[mkazantsev]

LGTM

llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h

 /// instruction.
 void ReplaceInstWithInst(BasicBlock::InstListType &BIL,
                          BasicBlock::iterator &BI, Instruction *I);
 
 /// Replace the instruction specified by From with the instruction specified by
 /// To. Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc.
 void ReplaceInstWithInst(Instruction *From, Instruction *To);
 
+/// Checks if the block or any of its children (or any of their children, etc)
+/// is "deoptimizing", i.e. either has a @llvm.experimental.deoptimize call
+/// prior to the terminating return instruction of this basic block or is
+/// terminated with unreachable. All blocks in the traversed sequence must have
+/// a single predecessor, maybe except for the last one.
+bool IsBlockDeoptimizing(
+    const BasicBlock *BB,
+    SmallVector<const BasicBlock *, 8> &DeoptimizingBlocks);
+
 /// Option class for critical edge splitting.
 ///
 /// This provides a builder interface for overriding the default options used
 /// during critical edge splitting.
 struct CriticalEdgeSplittingOptions {
   DominatorTree *DT;
   PostDominatorTree *PDT;
   LoopInfo *LI;

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "basicblock-utils"
 
 void llvm::DetatchDeadBlocks(
     ArrayRef<BasicBlock *> BBs,
     SmallVectorImpl<DominatorTree::UpdateType> *Updates,
     bool KeepOneInputPHIs) {
   for (auto *BB : BBs) {
     // Loop through all of our successors and make sure they know that one
     // of their predecessors is going away.
     SmallPtrSet<BasicBlock *, 4> UniqueSuccessors;
     for (BasicBlock *Succ : successors(BB)) {
       Succ->removePredecessor(BB, KeepOneInputPHIs);
void llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL,
 
   // Replace all uses of the old instruction, and delete it.
   ReplaceInstWithValue(BIL, BI, I);
 
   // Move BI back to point to the newly inserted instruction
   BI = New;
 }
 
+bool llvm::IsBlockDeoptimizing(
+    const BasicBlock *BB,
+    SmallVector<const BasicBlock *, 8> &DeoptimizingBlocks) {
+  const BasicBlock *Succ = BB;
+  // Remember visited blocks to avoid infinite loop
+  SmallVector<const BasicBlock *, 8> VisitedBlocks;
+  while (Succ) {
+    // Already proved this block is deoptimizing
+    if (find(DeoptimizingBlocks, Succ) != DeoptimizingBlocks.end())
+      return true;
+    // Already visited this block
+    if (find(VisitedBlocks, Succ) != VisitedBlocks.end())
+      return false;
+    const BasicBlock *NextSucc = Succ->getSingleSuccessor();
+    if (!NextSucc) {
+      if (Succ->getTerminatingDeoptimizeCall() ||
+          isa<UnreachableInst>(Succ->getTerminator())) {
+        DeoptimizingBlocks.push_back(Succ);
+        return true;
+      }
+      return false;
+    }
+    VisitedBlocks.push_back(Succ);
+    Succ = NextSucc;
+  }
+  return false;
+}
+
 void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) {
   BasicBlock::iterator BI(From);
   ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
 }
 
 BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT,
                             LoopInfo *LI, MemorySSAUpdater *MSSAU,
                             const Twine &BBName) {

llvm/lib/Transforms/Utils/LoopPeel.cpp

bool llvm::canPeel(Loop *L) {
 
   // Peeling is only supported if the latch is a branch.
   if (!isa<BranchInst>(Latch->getTerminator()))
     return false;
 
   SmallVector<BasicBlock *, 4> Exits;
   L->getUniqueNonLatchExitBlocks(Exits);
   // The latch must either be the only exiting block or all non-latch exit
-  // blocks have either a deopt or unreachable terminator. Both deopt and
-  // unreachable terminators are a strong indication they are not taken. Note
-  // that this is a profitability check, not a legality check. Also note that
-  // LoopPeeling currently can only update the branch weights of latch blocks
-  // and branch weights to blocks with deopt or unreachable do not need
+  // blocks have either a deopt or unreachable terminator or compose a chain of
+  // blocks where the last one is either deopt or unreachable terminated. Both
+  // deopt and unreachable terminators are a strong indication they are not
+  // taken. Note that this is a profitability check, not a legality check. Also
+  // note that LoopPeeling currently can only update the branch weights of latch
+  // blocks and branch weights to blocks with deopt or unreachable do not need
   // updating.
-  return all_of(Exits, [](const BasicBlock *BB) {
-    return BB->getTerminatingDeoptimizeCall() ||
-           isa<UnreachableInst>(BB->getTerminator());
+  SmallVector<const BasicBlock *, 8> DeoptimizingBlocks;
+  return all_of(Exits, [&](const BasicBlock *BB) {
+    return IsBlockDeoptimizing(BB, DeoptimizingBlocks);
   });
 }
 
 // This function calculates the number of iterations after which the given Phi
 // becomes an invariant. The pre-calculated values are memorized in the map. The
 // function (shortcut is I) is calculated according to the following definition:
 // Given %x = phi <Inputs from above the loop>, ..., [%y, %back.edge].
 //   If %y is a loop invariant, then I(%x) = 1.
bool llvm::peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI,
   LoopBlocks.perform(LI);
 
   BasicBlock *Header = L->getHeader();
   BasicBlock *PreHeader = L->getLoopPreheader();
   BasicBlock *Latch = L->getLoopLatch();
   SmallVector<std::pair<BasicBlock *, BasicBlock *>, 4> ExitEdges;
   L->getExitEdges(ExitEdges);
 
-  DenseMap<BasicBlock *, BasicBlock *> ExitIDom;
-  if (DT) {
-    // We'd like to determine the idom of exit block after peeling one
-    // iteration.
-    // Let Exit is exit block.
-    // Let ExitingSet - is a set of predecessors of Exit block. They are exiting
-    // blocks.
-    // Let Latch' and ExitingSet' are copies after a peeling.
-    // We'd like to find an idom'(Exit) - idom of Exit after peeling.
-    // It is an evident that idom'(Exit) will be the nearest common dominator
-    // of ExitingSet and ExitingSet'.
-    // idom(Exit) is a nearest common dominator of ExitingSet.
-    // idom(Exit)' is a nearest common dominator of ExitingSet'.
-    // Taking into account that we have a single Latch, Latch' will dominate
-    // Header and idom(Exit).
-    // So the idom'(Exit) is nearest common dominator of idom(Exit)' and Latch'.
-    // All these basic blocks are in the same loop, so what we find is
-    // (nearest common dominator of idom(Exit) and Latch)'.
-    // In the loop below we remember nearest common dominator of idom(Exit) and
-    // Latch to update idom of Exit later.
-    assert(L->hasDedicatedExits() && "No dedicated exits?");
-    for (auto Edge : ExitEdges) {
-      if (ExitIDom.count(Edge.second))
-        continue;
-      BasicBlock *BB = DT->findNearestCommonDominator(
-          DT->getNode(Edge.second)->getIDom()->getBlock(), Latch);
-      assert(L->contains(BB) && "IDom is not in a loop");
-      ExitIDom[Edge.second] = BB;
-    }
-  }
-
   Function *F = Header->getParent();
 
   // Set up all the necessary basic blocks. It is convenient to split the
   // preheader into 3 parts - two blocks to anchor the peeled copy of the loop
   // body, and a new preheader for the "real" loop.
 
   // Peeling the first iteration transforms.
   //
for (unsigned Iter = 0; Iter < PeelCount; ++Iter) {
     cloneLoopBlocks(L, Iter, InsertTop, InsertBot, ExitEdges, NewBlocks,
                     LoopBlocks, VMap, LVMap, DT, LI,
                     LoopLocalNoAliasDeclScopes);
 
     // Remap to use values from the current iteration instead of the
     // previous one.
     remapInstructionsInBlocks(NewBlocks, VMap);
 
+    // If DT is available, insert edges from cloned exiting blocks to the exits
     if (DT) {
-      // Latches of the cloned loops dominate over the loop exit, so idom of the
-      // latter is the first cloned loop body, as original PreHeader dominates
-      // the original loop body.
-      if (Iter == 0)
-        for (auto Exit : ExitIDom)
-          DT->changeImmediateDominator(Exit.first,
-                                       cast<BasicBlock>(LVMap[Exit.second]));
+      for (auto Exit : ExitEdges)
+        DT->insertEdge(cast<BasicBlock>(LVMap[Exit.first]), Exit.second);
 #ifdef EXPENSIVE_CHECKS
       assert(DT->verify(DominatorTree::VerificationLevel::Fast));
 #endif
     }
 
     auto *LatchBRCopy = cast<BranchInst>(VMap[LatchBR]);
     updateBranchWeights(InsertBot, LatchBRCopy, ExitWeight, FallThroughWeight);
     // Remove Loop metadata from the latch branch instruction

llvm/test/Transforms/LoopUnroll/peel-multiple-unreachable-exits.ll

 unreachable.exit:
   call void @foo()
   unreachable
 }
 
 define void @peel_exits_to_blocks_branch_to_unreachable_block(i32* %ptr, i32 %N, i32 %x, i1 %c.1) {
 ; CHECK-LABEL: @peel_exits_to_blocks_branch_to_unreachable_block(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP_HEADER_PEEL_BEGIN:%.*]]
+; CHECK:       loop.header.peel.begin:
+; CHECK-NEXT:    br label [[LOOP_HEADER_PEEL:%.*]]
+; CHECK:       loop.header.peel:
+; CHECK-NEXT:    [[C_PEEL:%.*]] = icmp ult i32 1, 2
+; CHECK-NEXT:    br i1 [[C_PEEL]], label [[THEN_PEEL:%.*]], label [[ELSE_PEEL:%.*]]
+; CHECK:       else.peel:
+; CHECK-NEXT:    [[C_2_PEEL:%.*]] = icmp eq i32 1, [[X:%.*]]
+; CHECK-NEXT:    br i1 [[C_2_PEEL]], label [[EXIT_2:%.*]], label [[LOOP_LATCH_PEEL:%.*]]
+; CHECK:       then.peel:
+; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[EXIT_1:%.*]], label [[LOOP_LATCH_PEEL]]
+; CHECK:       loop.latch.peel:
+; CHECK-NEXT:    [[M_PEEL:%.*]] = phi i32 [ 0, [[THEN_PEEL]] ], [ [[X]], [[ELSE_PEEL]] ]
+; CHECK-NEXT:    [[GEP_PEEL:%.*]] = getelementptr i32, i32* [[PTR:%.*]], i32 1
+; CHECK-NEXT:    store i32 [[M_PEEL]], i32* [[GEP_PEEL]], align 4
+; CHECK-NEXT:    [[IV_NEXT_PEEL:%.*]] = add nuw nsw i32 1, 1
+; CHECK-NEXT:    [[C_3_PEEL:%.*]] = icmp ult i32 1, 1000
+; CHECK-NEXT:    br i1 [[C_3_PEEL]], label [[LOOP_HEADER_PEEL_NEXT:%.*]], label [[EXIT:%.*]]
+; CHECK:       loop.header.peel.next:
+; CHECK-NEXT:    br label [[LOOP_HEADER_PEEL_NEXT1:%.*]]
+; CHECK:       loop.header.peel.next1:
+; CHECK-NEXT:    br label [[ENTRY_PEEL_NEWPH:%.*]]
+; CHECK:       entry.peel.newph:
 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; CHECK:       loop.header:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
-; CHECK-NEXT:    [[C:%.*]] = icmp ult i32 [[IV]], 2
-; CHECK-NEXT:    br i1 [[C]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT_PEEL]], [[ENTRY_PEEL_NEWPH]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
+; CHECK-NEXT:    br i1 false, label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
-; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[EXIT_1:%.*]], label [[LOOP_LATCH]]
+; CHECK-NEXT:    br i1 [[C_1]], label [[EXIT_1_LOOPEXIT:%.*]], label [[LOOP_LATCH]]
 ; CHECK:       else:
-; CHECK-NEXT:    [[C_2:%.*]] = icmp eq i32 [[IV]], [[X:%.*]]
-; CHECK-NEXT:    br i1 [[C_2]], label [[EXIT_2:%.*]], label [[LOOP_LATCH]]
+; CHECK-NEXT:    [[C_2:%.*]] = icmp eq i32 [[IV]], [[X]]
+; CHECK-NEXT:    br i1 [[C_2]], label [[EXIT_2_LOOPEXIT:%.*]], label [[LOOP_LATCH]]
 ; CHECK:       loop.latch:
 ; CHECK-NEXT:    [[M:%.*]] = phi i32 [ 0, [[THEN]] ], [ [[X]], [[ELSE]] ]
-; CHECK-NEXT:    [[GEP:%.*]] = getelementptr i32, i32* [[PTR:%.*]], i32 [[IV]]
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr i32, i32* [[PTR]], i32 [[IV]]
 ; CHECK-NEXT:    store i32 [[M]], i32* [[GEP]], align 4
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ult i32 [[IV]], 1000
-; CHECK-NEXT:    br i1 [[C_3]], label [[LOOP_HEADER]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[C_3]], label [[LOOP_HEADER]], label [[EXIT_LOOPEXIT:%.*]], !llvm.loop [[LOOP2:![0-9]+]]
+; CHECK:       exit.loopexit:
+; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
+; CHECK:       exit.1.loopexit:
+; CHECK-NEXT:    br label [[EXIT_1]]
 ; CHECK:       exit.1:
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[UNREACHABLE_TERM:%.*]]
+; CHECK:       exit.2.loopexit:
+; CHECK-NEXT:    br label [[EXIT_2]]
 ; CHECK:       exit.2:
 ; CHECK-NEXT:    call void @bar()
 ; CHECK-NEXT:    br label [[UNREACHABLE_TERM]]
 ; CHECK:       unreachable.term:
 ; CHECK-NEXT:    call void @baz()
 ; CHECK-NEXT:    unreachable
 ;
 entry: