[Loop Deletion] Delete loops that are never executed

[anna]

Summary

Currently, loop deletion only supports deleting loops that have backedges that
are not-taken into the loop header (i.e. the values outside the loop are invariant
wrt each loop iteration).
This patch adds logic to delete loops where the loop is proven to be
semantically unreachable.
The basic purpose here is to support and test the loop deletion
logic for the usage in loop-simplifyCFG, where changing constant conditional
branches to unconditional can make loops dead. This is the first set of changes to
merge loop-deletion and loop-simplifyCFG [1].

The next steps are:

1. moving the loop deletion implementation to LoopUtils
2. Add logic in loop-simplifyCFG which will support changing conditional

constant branches to unconditional branches. If loops become unreachable in this
process, they can be removed using deleteDeadLoop function.

[1] https://reviews.llvm.org/D32353#734363

[sanjoy]

I made a few first pass comments. I think the term "semantically unreachable" sounds more complicated than it actually is. :) How about "never executed", as in isLoopNeverExecuted?

lib/Transforms/Scalar/LoopDeletion.cpp

48 ↗

(On Diff #96586)

Indent seems off - clang-format?

119 ↗

(On Diff #96586)

I think this distinction between predecessor and preheader is making the logic a bit more complex than it needs to be. I'd instead do:

auto *Pred = L->getLoopPredecessor();
auto *Succ = L->getHeader();
if (Pred && Pred->getTerminator() is not conditional branch) {
  Succ = Pred;
  Pred = Pred->getSinglePredecessor();
}
if (!Pred || Pred->getTerminator() is not conditional branch)
  return false;

134 ↗

(On Diff #96586)

Why is Loop-SimplifyCFG relevant here? Won't it only simplify control flow within a loop?

137 ↗

(On Diff #96586)

The T seems a bit superfluous here -- why not just auto *BI = dyn_cast<BranchInst>(HeaderPred->getTerminator())?

145 ↗

(On Diff #96586)

What if both the branches branch to the header?

146 ↗

(On Diff #96586)

This can be just return NotTaken == FirstLoopBlock;

189 ↗

(On Diff #96586)

I'm missing where you're checking for this second case?

279 ↗

(On Diff #96586)

How do dead phis make a block dead?

If you're talking about keeping the edge from SourceBB to ExitBlock even though it will never be taken, then I see what you mean, but that comment should be on SourceBB->getTerminator()->replaceUsesOfWith(L->getHeader(), ExitBlock);. Btw, what is the problem with deleting that edge? Is it with updating LoopInfo or something else?

[anna]

lib/Transforms/Scalar/LoopDeletion.cpp

134 ↗

(On Diff #96586)

Yes, that's right. The comment maybe confusing. My assumption is that these kind of constant conditional branches are generated by unswitch [1], i.e. branch is within a loop. At a later point, deleting unreachable loop will be handled by Loop-SimplifyCFG: It will *start* at a constant branch condition, iterating forward through the blocks that will never be executed, and in the process if we reach a loop header which will never be executed, that loop will be deleted.

So, loop-deletion will just be a subcase of loop-simplifyCFG. At some point, we should just be able to call loop-simplifyCFG in the pass pipeline instead of loop-deletion.

[1] If we have constant conditional branches outside of loops generated by some other non-loop passes, we could just use SimplifyCFG to eliminate the code? This brings me to the main reason for the patch: implementing the actual loop deletion, update dom tree etc for unreachable loops, and use that function for Loop-SimplifyCFG.

145 ↗

(On Diff #96586)

ah, thanks :)

189 ↗

(On Diff #96586)

That's the original and already existing case for loop deletion pass: see isLoopDead. I'll update this comment so that it does not look like this was an addition in the patch.

279 ↗

(On Diff #96586)

This comment is incorrect. There's no problem in deleting the edge. The only reason is to keep the code here similar in both cases: keep the edge from the source block to the exit block. If I special case the "loop never executes" scenario to delete the edge, we can remove the value from the phi as well.
For now, I'll keep the code the same, and leave the edge as-is.

[anna]

lib/Transforms/Scalar/LoopDeletion.cpp

134 ↗

(On Diff #96586)

Actually, with loop-unswitch, the branch can be outside the loop :) So, the merging of loop-simplifyCFG and this version of loop-deletion should fix cases handled by both.
I'll remove the comment about loop-simplifyCFG. I guess we could have something like this in the pipeline:

unswitch
loop-deletion + loop-simplifycfg which handles constant conditional branches (both outside and within loops) that make some loop dead.

[anna]

Addressed review comments. Added more tests with subloops and preserving loop structure.
Updated source code comments.

[anna]

lib/Transforms/Scalar/LoopDeletion.cpp

279 ↗

(On Diff #96586)

just FYI, it looks like there is a problem in deleting the edge. If this loop is within a parent loop, we may break the parent loop's structure.
Consider:

L1:
  br i1 true, label %exit, label %L2 
L2:
  br i1 %cond, label %L2, label %L1

Here we can delete L2. If we remove the edge from the sourceBlock L1 to the exit block (which will be L1.exit or L1), the loop structure of L1 is no longer preserved. I have added a test case (see test8) in the updated diff, and updated the comment as well.

In test8, both the loops are deleted through iterative calls to loop deletion starting from inner loop to outer loop.

[sanjoy]

Comments inline.

lib/Transforms/Scalar/LoopDeletion.cpp

34 ↗

(On Diff #96927)

80 chars line?

105 ↗

(On Diff #96927)

Is "not unreachable" == "i.e. it's header would always have atleast one predecessor" or == "its header must have a path from the entry block"?

107 ↗

(On Diff #96927)

I'd rephrase this a bit: However, if the loop header would never be executed at runtime, the loop is considered semantically unreachable.

But generally, I'd be in favor of not adding so much detail here, but instead just saying something brief like: "This function returns true if there is no viable path from the entry block to the header of \p L. Right now it only does a local search to save compile time(?)"

134 ↗

(On Diff #96927)

Perhaps this can be made more concise using PatternMatch?

BasicBlock *Taken, *NotTaken;
ConstantInst *Cond;
if (!match(Pred->getTerminator(), m_Br(m_ConstantInt(Cond), Taken, NotTaken)))
  return false;
if (!Cond->getZExtValue())
  std::swap(Taken, NotTaken);

edit: actually, I think this can be combined with the previous check too to make the entire function body be:

auto *Pred = L->getLoopPredecessor();
auto *FirstLoopBlock = L->getHeader();

for (int i = 0; i < 2 && Pred; i++) {
  BasicBlock *Taken, *NotTaken;
  ConstantInst *Cond;
  if (match(Pred->getTerminator(), m_Br(m_ConstantInt(Cond), Taken, NotTaken))) {
    if (!Cond->getZExtValue())
      std::swap(Taken, NotTaken);
    return NotTaken == FirstLoopBlock && Taken != FirstLoopBlock;
    // Alternatively:
    // if (NotTaken == FirstLoopBlock && Taken != FirstLoopBlock)
    //   return true;
  }
  FirstLoopBlock = Pred;
  Pred = Pred->getSinglePredecessor();
}

188 ↗

(On Diff #96927)

I didn't understand the "has no backedge" part -- if it does not have a backedge how is it a loop?

224 ↗

(On Diff #96927)

Why not insert a preheader if there wasn't one (by splitting the edge from the loop predecessor to the header), and keep the rest of the CFG modifying logic the same? IIUC, the only other place that needs to change is the P->setIncomingValue(j, UndefValue::get(P->getType())), and even that can be done as a pre-pass before deleteDeadLoop keeping the core logic here the same in both the situations.

235 ↗

(On Diff #96927)

I would just pass in the block that we decided was the last executed block instead of re-deriving it here. Otherwise we risk the logic here and isLoopNeverExecuted diverging.

[edit: the comment above about splitting the preheader supersedes this comment]

[anna]

lib/Transforms/Scalar/LoopDeletion.cpp

188 ↗

(On Diff #96927)

Actually, what I meant was it's "semantically not having a backedge": in isLoopDead, we check to see that only invariant values from the loop are used in the exit block. Then we hoist these invariant values *and their operands* to the preheader. I think this is equivalent to "semantically not having a backedge". I'm just going to remove these comments instead of going into all this detail :)

But just for my own clarification, do you think equivalent, or my statement is a stronger version of isLoopDead?

235 ↗

(On Diff #96927)

Actually, that's what I did initially (during local modification). However, it required passing that last executed block between 3 functions. I personally didnt like that design either.

I like your first comment on splitting the edge from the loop predecessor to the header. I'll try to get that working and keep the core logic as similar as possible.

[sanjoy]

lib/Transforms/Scalar/LoopDeletion.cpp

188 ↗

(On Diff #96927)

But just for my own clarification, do you think equivalent, or my statement is a stronger version of isLoopDead?

I believe the code is checking for loops like this:

int x = ..., y = ...;
int z;
for (int i = 0; i < 5; i++)
  z = x + y;
use(z);

I'd say the loop above does have a backedge but you're right in pointing out that the backedge is not "useful".

[anna]

Addressed review comments.
Main changes: Preheader is now a requirement for never executed loops.
We can also handle multiple immediate predecessors in the never executed loop.

[anna]

In this change, I've added the preheader requirement to never executed loops as well. The main reason for adding this requirement
is that in all testcases I've added, opt -loop-deletion always generates a preheader for the loop before running this pass.
Not sure how to test for non-preheader cases.
So, the core logic in deleteDeadLoop is now very similar to initial code before the patch.

lib/Transforms/Scalar/LoopDeletion.cpp

105 ↗

(On Diff #96927)

the latter. i've updated the comment.

134 ↗

(On Diff #96927)

I've changed this function to consider all immediate predecessors of the preheader. Preheader is now a requirement for this function. Pls see the updated function.

235 ↗

(On Diff #96927)

This logic is now removed because of the preheader requirement.

[sanjoy]

This looks pretty close to done.

One high level issue I have is that you've interchangeably used "semantically unreachable" and "never executed". I'd standardize to one or the other to reduce confusion. I'd lean towards "never executed" or "known never executed", but if you find "semantically unreachable" better, using that would also be better than using both.

lib/Transforms/Scalar/LoopDeletion.cpp

35 ↗

(On Diff #97295)

I thought we decided that backedges do exist in those cases?

37 ↗

(On Diff #97295)

Isn't the second kind of loop still a loop? It just is a loop that is provably not reachable.

39 ↗

(On Diff #97295)

Why not s/be more aggressive in removing the/always remove/ ?

40 ↗

(On Diff #97295)

s/program behaviour (observable or unobservable)/observable program behavior/

I don't think we care about changing unobservable program behavior. :)

I'd even drop the observable, btw, since "program behavior" means "observable program behavior".

135 ↗

(On Diff #97295)

Is the former ("the preheader has no predecessors") possible since we have an llvm::Loop? If not, I'd add an assert.

156 ↗

(On Diff #97295)

Any reason why you reordered the preheader and the empty loop checks? If not, I'd lean towards to keeping them the way they are to make the diff smaller.

254 ↗

(On Diff #97295)

Not directly relevant to this patch, but is this bit correct with multiple edges from an exiting block to an exit block?

336 ↗

(On Diff #97295)

Debugging code?

test/Transforms/LoopDeletion/unreachable-loops.ll

1 ↗

(On Diff #97295)

Why not just add -verify-dom-info to the first invocation (instead of having a separate one)?

[anna]

lib/Transforms/Scalar/LoopDeletion.cpp

35 ↗

(On Diff #97295)

oops, forgot to change the comment.

37 ↗

(On Diff #97295)

It is, but I think it's no longer a loop according to how llvm identifies loops. See LoopInfoImpl.h analyze: We always check that the backedges are reachable from entry (which auto implies the header that dominates these backedges are also reachable from entry). I've made the description of this function more concise though.

135 ↗

(On Diff #97295)

I think the only case is when the preheader is the function entry block. That's already been handled above. So, per llvm notion, the preheader should have predecessors at this point. Added the assert.

254 ↗

(On Diff #97295)

I think this is correct because the ExitingBlocks are generated by getExitingBlocks, so it handles multiple edges from an exiting block to an exit block. If it was getUniqueExitingBlocks, this would be incorrect.

336 ↗

(On Diff #97295)

thanks :)

[anna]

Main change: Updated comments to uniformly use terminology as loop is never executed
instead of semantically unreachable.
Addressed other review comments.

[sanjoy]

lgtm

llvm/trunk/lib/Transforms/Scalar/LoopDeletion.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/LoopDeletion.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-delete"
 
 STATISTIC(NumDeleted, "Number of loops deleted");
 
+/// This function deletes dead loops. The caller of this function needs to
+/// guarantee that the loop is infact dead.  Here we handle two kinds of dead
+/// loop. The first kind (\p isLoopDead) is where only invariant values from
+/// within the loop are used outside of it. The second kind (\p
+/// isLoopNeverExecuted) is where the loop is provably never executed. We can
+/// always remove never executed loops since they will not cause any
+/// difference to program behaviour.
+/// 
+/// This also updates the relevant analysis information in \p DT, \p SE, and \p
+/// LI. It also updates the loop PM if an updater struct is provided.
+// TODO: This function will be used by loop-simplifyCFG as well. So, move this
+// to LoopUtils.cpp
+static void deleteDeadLoop(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
+                           LoopInfo &LI, bool LoopIsNeverExecuted,
+                           LPMUpdater *Updater = nullptr);
 /// Determines if a loop is dead.
 ///
 /// This assumes that we've already checked for unique exit and exiting blocks,
 /// and that the code is in LCSSA form.
 static bool isLoopDead(Loop *L, ScalarEvolution &SE,
                        SmallVectorImpl<BasicBlock *> &ExitingBlocks,
                        BasicBlock *ExitBlock, bool &Changed,
                        BasicBlock *Preheader) {
static bool isLoopDead(Loop *L, ScalarEvolution &SE,
   // This includes instructions that could write to memory, and loads that are
   // marked volatile.
   for (auto &I : L->blocks())
     if (any_of(*I, [](Instruction &I) { return I.mayHaveSideEffects(); }))
       return false;
   return true;
 }
 
+/// This function returns true if there is no viable path from the
+/// entry block to the header of \p L. Right now, it only does
+/// a local search to save compile time.
+static bool isLoopNeverExecuted(Loop *L) {
+  using namespace PatternMatch;
+
+  auto *Preheader = L->getLoopPreheader();
+  // TODO: We can relax this constraint, since we just need a loop
+  // predecessor.
+  assert(Preheader && "Needs preheader!");
+
+  if (Preheader == &Preheader->getParent()->getEntryBlock())
+    return false;
+  // All predecessors of the preheader should have a constant conditional
+  // branch, with the loop's preheader as not-taken.
+  for (auto *Pred: predecessors(Preheader)) {
+    BasicBlock *Taken, *NotTaken;
+    ConstantInt *Cond;
+    if (!match(Pred->getTerminator(),
+               m_Br(m_ConstantInt(Cond), Taken, NotTaken)))
+      return false;
+    if (!Cond->getZExtValue())
+      std::swap(Taken, NotTaken);
+    if (Taken == Preheader)
+      return false;
+  }
+  assert(!pred_empty(Preheader) &&
+         "Preheader should have predecessors at this point!");
+  // All the predecessors have the loop preheader as not-taken target.
+  return true;
+}
+
 /// Remove a loop if it is dead.
 ///
 /// A loop is considered dead if it does not impact the observable behavior of
 /// the program other than finite running time. This never removes a loop that
-/// might be infinite, as doing so could change the halting/non-halting nature
-/// of a program.
+/// might be infinite (unless it is never executed), as doing so could change
+/// the halting/non-halting nature of a program.
 ///
 /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
 /// order to make various safety checks work.
 ///
 /// \returns true if any changes were made. This may mutate the loop even if it
 /// is unable to delete it due to hoisting trivially loop invariant
 /// instructions out of the loop.
-///
-/// This also updates the relevant analysis information in \p DT, \p SE, and \p
-/// LI. It also updates the loop PM if an updater struct is provided.
 static bool deleteLoopIfDead(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
                              LoopInfo &LI, LPMUpdater *Updater = nullptr) {
   assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
 
   // We can only remove the loop if there is a preheader that we can
   // branch from after removing it.
   BasicBlock *Preheader = L->getLoopPreheader();
   if (!Preheader)
     return false;
 
   // If LoopSimplify form is not available, stay out of trouble.
   if (!L->hasDedicatedExits())
     return false;
 
   // We can't remove loops that contain subloops.  If the subloops were dead,
   // they would already have been removed in earlier executions of this pass.
   if (L->begin() != L->end())
     return false;
 
+
+  BasicBlock *ExitBlock = L->getUniqueExitBlock();
+
+  if (ExitBlock && isLoopNeverExecuted(L)) {
+    deleteDeadLoop(L, DT, SE, LI, true /* LoopIsNeverExecuted */, Updater);
+    ++NumDeleted;
+    return true;
+  }
+
+  // The remaining checks below are for a loop being dead because all statements
+  // in the loop are invariant.
   SmallVector<BasicBlock *, 4> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
 
   // We require that the loop only have a single exit block.  Otherwise, we'd
   // be in the situation of needing to be able to solve statically which exit
   // block will be branched to, or trying to preserve the branching logic in
   // a loop invariant manner.
-  BasicBlock *ExitBlock = L->getUniqueExitBlock();
   if (!ExitBlock)
     return false;
 
   // Finally, we have to check that the loop really is dead.
   bool Changed = false;
   if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader))
     return Changed;
 
   // Don't remove loops for which we can't solve the trip count.
   // They could be infinite, in which case we'd be changing program behavior.
   const SCEV *S = SE.getMaxBackedgeTakenCount(L);
   if (isa<SCEVCouldNotCompute>(S))
     return Changed;
 
+  deleteDeadLoop(L, DT, SE, LI, false /* LoopIsNeverExecuted */, Updater);
+  ++NumDeleted;
+
+  return true;
+}
+
+static void deleteDeadLoop(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
+                           LoopInfo &LI, bool LoopIsNeverExecuted,
+                           LPMUpdater *Updater) {
+  assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
+  auto *Preheader = L->getLoopPreheader();
+  assert(Preheader && "Preheader should exist!");
+
   // Now that we know the removal is safe, remove the loop by changing the
   // branch from the preheader to go to the single exit block.
   //
   // Because we're deleting a large chunk of code at once, the sequence in which
   // we remove things is very important to avoid invalidation issues.
 
   // If we have an LPM updater, tell it about the loop being removed.
   if (Updater)
     Updater->markLoopAsDeleted(*L);
 
   // Tell ScalarEvolution that the loop is deleted. Do this before
   // deleting the loop so that ScalarEvolution can look at the loop
   // to determine what it needs to clean up.
   SE.forgetLoop(L);
 
+  auto *ExitBlock = L->getUniqueExitBlock();
+  assert(ExitBlock && "Should have a unique exit block!");
+
   // Connect the preheader directly to the exit block.
-  TerminatorInst *TI = Preheader->getTerminator();
-  TI->replaceUsesOfWith(L->getHeader(), ExitBlock);
+  // Even when the loop is never executed, we cannot remove the edge from the
+  // source block to the exit block. Consider the case where the unexecuted loop
+  // branches back to an outer loop. If we deleted the loop and removed the edge
+  // coming to this inner loop, this will break the outer loop structure (by
+  // deleting the backedge of the outer loop). If the outer loop is indeed a
+  // non-loop, it will be deleted in a future iteration of loop deletion pass.
+  Preheader->getTerminator()->replaceUsesOfWith(L->getHeader(), ExitBlock);
 
-  // Rewrite phis in the exit block to get their inputs from
-  // the preheader instead of the exiting block.
+  SmallVector<BasicBlock *, 4> ExitingBlocks;
+  L->getExitingBlocks(ExitingBlocks);
+  // Rewrite phis in the exit block to get their inputs from the Preheader
+  // instead of the exiting block.
   BasicBlock *ExitingBlock = ExitingBlocks[0];
   BasicBlock::iterator BI = ExitBlock->begin();
   while (PHINode *P = dyn_cast<PHINode>(BI)) {
     int j = P->getBasicBlockIndex(ExitingBlock);
     assert(j >= 0 && "Can't find exiting block in exit block's phi node!");
+    if (LoopIsNeverExecuted)
+      P->setIncomingValue(j, UndefValue::get(P->getType()));
     P->setIncomingBlock(j, Preheader);
     for (unsigned i = 1; i < ExitingBlocks.size(); ++i)
       P->removeIncomingValue(ExitingBlocks[i]);
     ++BI;
   }
 
   // Update the dominator tree and remove the instructions and blocks that will
   // be deleted from the reference counting scheme.
static void deleteDeadLoop(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
 
   SmallPtrSet<BasicBlock *, 8> blocks;
   blocks.insert(L->block_begin(), L->block_end());
   for (BasicBlock *BB : blocks)
     LI.removeBlock(BB);
 
   // The last step is to update LoopInfo now that we've eliminated this loop.
   LI.markAsRemoved(L);
-  ++NumDeleted;
-
-  return true;
 }
 
 PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM,
                                         LoopStandardAnalysisResults &AR,
                                         LPMUpdater &Updater) {
   if (!deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI, &Updater))
     return PreservedAnalyses::all();
 

 INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion",
                     "Delete dead loops", false, false)
 
 Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); }
 
 bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &) {
   if (skipLoop(L))
     return false;
-
   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 
   return deleteLoopIfDead(L, DT, SE, LI);
 }

llvm/trunk/test/Transforms/LoopDeletion/unreachable-loops.ll

+; RUN: opt < %s -loop-deletion -verify-dom-info -S | FileCheck %s
+
+; Checking that we can delete loops that are never executed.
+; We do not change the constant conditional branch statement (where the not-taken target
+; is the loop) to an unconditional one.
+
+; delete the infinite loop because it is never executed.
+define void @test1(i64 %n, i64 %m) nounwind {
+; CHECK-LABEL: test1
+; CHECK-LABEL: entry:
+; CHECK-NEXT: br i1 true, label %return, label %bb.preheader
+; CHECK-NOT: bb:
+entry:
+  br i1 true, label %return, label %bb
+
+bb:
+  %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb ]
+  %t0 = add i64 %x.0, 1
+  %t1 = icmp slt i64 %x.0, %n
+  %t3 = icmp sgt i64 %x.0, %m
+  %t4 = and i1 %t1, %t3
+  br i1 true, label %bb, label %return
+
+return:
+  ret void
+}
+
+; FIXME: We can delete this infinite loop. Currently we do not,
+; because the infinite loop has no exit block.
+define void @test2(i64 %n, i64 %m) nounwind {
+; CHECK-LABEL: test2
+; CHECK-LABEL: entry:
+; CHECK-NEXT: br i1 true, label %return, label %bb.preheader
+; CHECK-LABEL: bb:
+; CHECK: br label %bb
+entry:
+  br i1 true, label %return, label %bb
+
+bb:
+  %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb ]
+  %t0 = add i64 %x.0, 1
+  %t1 = icmp slt i64 %x.0, %n
+  %t3 = icmp sgt i64 %x.0, %m
+  %t4 = and i1 %t1, %t3
+  br label %bb
+
+return:
+  ret void
+}
+
+; There are multiple exiting blocks and a single exit block. 
+; Since it is a never executed loop, we do not care about the values
+; from different exiting paths and we can
+; delete the loop.
+define i64 @test3(i64 %n, i64 %m, i64 %maybe_zero) nounwind {
+
+; CHECK-NOT: bb:
+; CHECK-NOT: bb2:
+; CHECK-NOT: bb3:
+; CHECK-LABEL: return.loopexit:
+; CHECK-NEXT: %x.lcssa.ph = phi i64 [ undef, %bb.preheader ]
+; CHECK-NEXT: br label %return
+; CHECK-LABEL: return:
+; CHECK-NEXT: %x.lcssa = phi i64 [ 20, %entry ], [ %x.lcssa.ph, %return.loopexit ]
+; CHECK-NEXT: ret i64 %x.lcssa
+entry:
+  br i1 false, label %bb, label %return
+
+bb:
+  %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb3 ]
+  %t0 = add i64 %x.0, 1
+  %t1 = icmp slt i64 %x.0, %n
+  br i1 %t1, label %bb2, label %return
+
+bb2:
+  %t2 = icmp slt i64 %x.0, %m
+  %unused1 = udiv i64 42, %maybe_zero
+  br i1 %t2, label %bb3, label %return
+
+bb3:
+  %t3 = icmp slt i64 %x.0, %m
+  %unused2 = sdiv i64 42, %maybe_zero
+  br i1 %t3, label %bb, label %return
+
+return:
+; the only valid value fo x.lcssa is 20.
+  %x.lcssa = phi i64 [ 12, %bb ], [ 14, %bb2 ], [ 16, %bb3 ], [20, %entry ]
+  ret i64 %x.lcssa
+}
+
+; Cannot delete the loop, since it may be executed at runtime.
+define void @test4(i64 %n, i64 %m, i1 %cond) {
+; CHECK-LABEL: test4
+; CHECK-LABEL: bb:
+entry:
+  br i1 %cond, label %looppred1, label %looppred2
+
+looppred1:
+  br i1 true, label %return, label %bb
+
+looppred2:
+  br i1 false, label %return, label %bb
+
+bb:
+  %x.0 = phi i64 [ 0, %looppred1 ], [ 1, %looppred2 ], [ %t0, %bb ]
+  %t0 = add i64 %x.0, 1
+  %t1 = icmp slt i64 %x.0, %n
+  %t3 = icmp sgt i64 %x.0, %m
+  %t4 = and i1 %t1, %t3
+  br i1 true, label %bb, label %return
+
+return:
+  ret void
+}
+
+; multiple constant conditional branches with loop not-taken in all cases.
+define void @test5(i64 %n, i64 %m, i1 %cond) nounwind {
+; CHECK-LABEL: test5
+; CHECK-LABEL: looppred1:
+; CHECK-NEXT: br i1 true, label %return, label %bb.preheader
+; CHECK-LABEL: looppred2:
+; CHECK-NEXT: br i1 true, label %return, label %bb.preheader
+; CHECK-NOT: bb:
+entry:
+  br i1 %cond, label %looppred1, label %looppred2
+
+looppred1:
+  br i1 true, label %return, label %bb
+
+looppred2:
+  br i1 true, label %return, label %bb
+
+bb:
+  %x.0 = phi i64 [ 0, %looppred1 ], [ 1, %looppred2 ], [ %t0, %bb ]
+  %t0 = add i64 %x.0, 1
+  %t1 = icmp slt i64 %x.0, %n
+  %t3 = icmp sgt i64 %x.0, %m
+  %t4 = and i1 %t1, %t3
+  br i1 true, label %bb, label %return
+
+return:
+  ret void
+}
+
+; Don't delete this infinite loop because the loop 
+; is executable at runtime.
+define void @test6(i64 %n, i64 %m) nounwind {
+; CHECK-LABEL: test6
+; CHECK-LABEL: entry:
+; CHECK-NEXT: br i1 true, label %bb.preheader, label %bb.preheader
+; CHECK: bb:
+entry:
+  br i1 true, label %bb, label %bb
+
+bb:
+  %x.0 = phi i64 [ 0, %entry ], [ 0, %entry ], [ %t0, %bb ]
+  %t0 = add i64 %x.0, 1
+  %t1 = icmp slt i64 %x.0, %n
+  %t3 = icmp sgt i64 %x.0, %m
+  %t4 = and i1 %t1, %t3
+  br i1 true, label %bb, label %return
+
+return:
+  ret void
+}
+
+declare i64 @foo(i64)
+; The loop L2 is never executed and is a subloop, with an 
+; exit block that branches back to parent loop.
+; Here we can delete loop L2, while L1 still exists.
+define i64 @test7(i64 %n) {
+; CHECK-LABEL: test7
+; CHECK-LABEL: L1:
+; CHECK: br i1 true, label %L1Latch, label %L2.preheader
+; CHECK-LABEL: L2.preheader:
+; CHECK-NEXT: br label %L1Latch.loopexit
+; CHECK-LABEL: L1Latch.loopexit:
+; CHECK: br label %L1Latch
+; CHECK-LABEL: L1Latch:
+; CHECK-NEXT: %y = phi i64 [ %y.next, %L1 ], [ %y.L2.lcssa, %L1Latch.loopexit ]
+; CHECK: br i1 %cond2, label %exit, label %L1
+entry: 
+  br label %L1
+
+L1:
+  %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ]
+  br i1 true, label %L1Latch, label %L2
+
+L2:
+  %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ]
+  %x.next = add i64 %x, 1
+  %y.L2 = call i64 @foo(i64 %x.next)
+  %cond = icmp slt i64 %x.next, %n
+  br i1 %cond, label %L2, label %L1Latch
+
+L1Latch:
+ %y = phi i64 [ %y.next, %L1 ], [ %y.L2, %L2 ]
+ %y.add = add i64 %y, %n
+ %cond2 = icmp eq i64 %y.add, 42
+ br i1 %cond2, label %exit, label %L1
+
+exit:
+ ret i64 %y.add
+}
+
+
+; Show recursive deletion of loops. Since we start with subloops and progress outward 
+; to parent loop, we first delete the loop L2. Now loop L1 becomes a non-loop since it's backedge
+; from L2's preheader to L1's exit block is never taken. So, L1 gets deleted as well.
+define void @test8(i64 %n) {
+; CHECK-LABEL: test8
+; CHECK-LABEL: entry:
+; CHECK-NEXT: br label %exit
+; CHECK-LABEL: exit:
+; CHECK-NEXT: ret void
+entry: 
+  br label %L1
+
+L1:
+  br i1 true, label %exit, label %L2
+
+L2:
+  %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ]
+  %x.next = add i64 %x, 1
+  %y.L2 = call i64 @foo(i64 %x.next)
+  %cond = icmp slt i64 %x.next, %n
+  br i1 %cond, label %L2, label %L1
+
+exit:
+ ret void
+}
+
+
+; Delete a loop (L2) which has subloop (L3).
+; Here we delete loop L2, but leave L3 as is.
+; FIXME: Can delete L3 as well, by iteratively going backward through the single
+; predecessor of L3 until we reach L1's block that guarantees L3 is never
+; executed.
+define void @test9(i64 %n) {
+; CHECK-LABEL: test9
+; CHECK-LABEL: L2.preheader:
+; CHECK-NEXT: br label %L3.preheader
+; CHECK-NOT: L2:
+; CHECK-LABEL: L3.preheader:
+; CHECK-NEXT: %y.L2.lcssa = phi i64 [ undef, %L2.preheader ]
+; CHECK-NEXT: br label %L3
+; CHECK-LABEL: L3:
+; CHECK: br i1 %cond2, label %L3, label %L1.loopexit
+entry: 
+  br label %L1
+
+L1:
+  br i1 true, label %exit, label %L2
+
+L2:
+  %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ]
+  %x.next = add i64 %x, 1
+  %y.L2 = call i64 @foo(i64 %x.next)
+  %cond = icmp slt i64 %x.next, %n
+  br i1 %cond, label %L2, label %L3
+
+L3: 
+  %cond2 = icmp slt i64 %y.L2, %n
+  br i1 %cond2, label %L3, label %L1
+
+exit:
+ ret void
+}
+
+; We cannot delete L3 because of call within it.
+; Since L3 is not deleted, and entirely contained within L2, L2 is also not
+; deleted.
+; FIXME: We can delete unexecutable loops having
+; subloops contained entirely within them.
+define void @test10(i64 %n) {
+; CHECK-LABEL: test10
+; CHECK: L2:
+; CHECK: L3:
+entry: 
+  br label %L1
+
+L1:
+  br i1 true, label %exit, label %L2
+
+L2:
+  %x = phi i64 [ 0, %L1 ], [ %x.next, %L3 ]
+  %x.next = add i64 %x, 1
+  %y.L2 = call i64 @foo(i64 %x.next)
+  %cond = icmp slt i64 %x.next, %n
+  br i1 %cond, label %L1, label %L3
+
+L3:
+  %y.L3 = phi i64 [ %y.L2, %L2 ], [ %y.L3.next, %L3 ]
+  %y.L3.next = add i64 %y.L3, 1
+  %dummy = call i64 @foo(i64 %y.L3.next)
+  %cond2 = icmp slt i64 %y.L3, %n
+  br i1 %cond2, label %L3, label %L2
+
+exit:
+ ret void
+}
+
+; same as test10, but L3 does not contain call.
+; So, in the first iteration, all statements of L3 are made invariant, and L3 is
+; deleted.
+; In the next iteration, since L2 is never executed and has no subloops, we delete
+; L2 as well. Finally, the outermost loop L1 is deleted.
+define void @test11(i64 %n) {
+; CHECK-LABEL: test11
+; CHECK-LABEL: entry:
+; CHECK-NEXT: br label %exit
+; CHECK-LABEL: exit:
+; CHECK-NEXT: ret void
+entry: 
+  br label %L1
+
+L1:
+  br i1 true, label %exit, label %L2
+
+L2:
+  %x = phi i64 [ 0, %L1 ], [ %x.next, %L3 ]
+  %x.next = add i64 %x, 1
+  %y.L2 = call i64 @foo(i64 %x.next)
+  %cond = icmp slt i64 %x.next, %n
+  br i1 %cond, label %L1, label %L3
+
+L3: 
+  %y.L3 = phi i64 [ %y.L2, %L2 ], [ %y.L3.next, %L3 ]
+  %y.L3.next = add i64 %y.L3, 1
+  %cond2 = icmp slt i64 %y.L3, %n
+  br i1 %cond2, label %L3, label %L2
+
+exit:
+ ret void
+}
+