[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

Indent seems off - clang-format?

118

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;

133

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

136

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

144

What if both the branches branch to the header?

145

This can be just return NotTaken == FirstLoopBlock;

187

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

281

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

133

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.

144

ah, thanks :)

187

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.

281

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

133

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

281

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

80 chars line?

105

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

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

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

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

224

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

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

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

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

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

the latter. i've updated the comment.

134

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

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

34

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

36

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

38

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

39

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

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

165

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.

284

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

366

Debugging code?

test/Transforms/LoopDeletion/unreachable-loops.ll

2

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

[anna]

lib/Transforms/Scalar/LoopDeletion.cpp

34

oops, forgot to change the comment.

36

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

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.

284

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.

366

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

lib/Transforms/Scalar/LoopDeletion.cpp

 #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 is where no backedges exist, and
+/// the loop variant statements are made invariant by moving to the preheader.
+/// The second kind is where the loop is no longer a loop in LLVM notion, since
+/// the loop is semantically unreachable (see `IsLoopNeverExecuted`).
+/// We can be more aggressive in removing the semantically unreachable loops
+/// since they will not cause any difference to program behaviour (observable or
+/// unobservable).
+///
+/// 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;
 }
 
+/// In LLVM, a loop can never be unreachable i.e. it's header would
+/// always have atleast one predecessor. However, in cases where the loop
+/// header would never be executed at runtime, we consider such loops as
+/// semantically unreachable. This function returns true when loop `L` is
+/// semantically unreachable. For example, loop L2 is unreachable in 
+/// the following IR:
+/// L1: ... 
+///     br i1 true, label L1, label L2
+/// L2: ...  ; predecessors: L1, B3
+///     br label B3
+/// B3: ...  ; predecessors: L2
+///      br label L2
+static bool isLoopNeverExecuted(Loop *L) {
+
+  auto *Pred = L->getLoopPredecessor();
+  auto *FirstLoopBlock = L->getHeader();
+
+  // Pred can be the preheader that branches unconditionally to the loop header.
+  // We want the block that has a constant conditional branch, with the loop's
+  // first block as not-taken.
+  if (Pred && Pred->getTerminator()->getNumSuccessors() == 1) {
+    FirstLoopBlock = Pred;
+    Pred = Pred->getSinglePredecessor();
+  }
+
+  if (!Pred)
+    return false;
+  // Note: We could keep iterating backwards over the singlePredecessors
+  // (straight line code) until we reach a block that satisfies the constraint
+  // of constant conditional branch.
+  auto *BI = dyn_cast<BranchInst>(Pred->getTerminator());
+  if (!BI || BI->isUnconditional())
+    return false;
+  ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
+  if (!Cond)
+    return false;
+  BasicBlock *NotTaken =
+      Cond->getZExtValue() ? BI->getSuccessor(1) : BI->getSuccessor(0);
+  BasicBlock *Taken =
+      Cond->getZExtValue() ? BI->getSuccessor(0) : BI->getSuccessor(1);
+  return NotTaken == FirstLoopBlock && Taken != FirstLoopBlock;
+}
+
 /// 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 semantically unreachable), 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)
+
+  // 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;
 
   // 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())
+  BasicBlock *ExitBlock = L->getUniqueExitBlock();
+
+  // When the loop is never executed, we do not care if it is an
+  // infinite loop, has multiple exits, or subloops (entirely contained in this
+  // loop). For now, we handle possibly infinite loops and loops with single exit.
+  if (ExitBlock && isLoopNeverExecuted(L)) {
+    deleteDeadLoop(L, DT, SE, LI,
+                   /*LoopIsNeverExecuted*/ true, Updater);
+    ++NumDeleted;
+    return true;
+  }
+
+  // The remaining checks below are for a loop being dead because it has no
+  // backedge, and all statements in the loop are invariant. This is a non-loop
+  // if we can move all statements within the loop to the preheader.
+  // 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;
 
+
   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 || LoopIsNeverExecuted) &&
+         "Preheader should exist if loop is reachable!");
+  BasicBlock *BlockCausingLoopUnreachable = nullptr;
+  // We already proved that the loop is never executed. Get the block that makes
+  // the loop unreachable. If the preheader does not exist, this will be the
+  // source block which will be directly connected to the exit block of the
+  // loop.
+  if (LoopIsNeverExecuted)
+    BlockCausingLoopUnreachable =
+        Preheader ? Preheader->getSinglePredecessor() : L->getLoopPredecessor();
+
   // 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);
 
-  // Connect the preheader directly to the exit block.
-  TerminatorInst *TI = Preheader->getTerminator();
-  TI->replaceUsesOfWith(L->getHeader(), ExitBlock);
+  auto *ExitBlock = L->getUniqueExitBlock();
+  assert(ExitBlock && "Should have a unique exit block!");
+  // All the branch changes, phi node updates at the exit block and dom tree
+  // updates should be done with this node as the source.
+  auto *SourceBB = Preheader ? Preheader : BlockCausingLoopUnreachable;
+  assert(SourceBB && "the source basic block into the loop should exist!");
+
+  // Connect the source block that exists outside the loop, directly to
+  // the exit block.
+  // 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.
+  SourceBB->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 SourceBB
+  // 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!");
-    P->setIncomingBlock(j, Preheader);
+    if (LoopIsNeverExecuted)
+      P->setIncomingValue(j, UndefValue::get(P->getType()));
+    P->setIncomingBlock(j, SourceBB);
     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.
   SmallVector<DomTreeNode*, 8> ChildNodes;
   for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
        LI != LE; ++LI) {
-    // Move all of the block's children to be children of the Preheader, which
+    // Move all of the block's children to be children of the SourceBB, which
     // allows us to remove the domtree entry for the block.
     ChildNodes.insert(ChildNodes.begin(), DT[*LI]->begin(), DT[*LI]->end());
     for (DomTreeNode *ChildNode : ChildNodes) {
-      DT.changeImmediateDominator(ChildNode, DT[Preheader]);
+      DT.changeImmediateDominator(ChildNode, DT[SourceBB]);
     }
 
     ChildNodes.clear();
     DT.eraseNode(*LI);
 
     // Remove the block from the reference counting scheme, so that we can
     // delete it freely later.
     (*LI)->dropAllReferences();
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);
 }

test/Transforms/LoopDeletion/unreachable-loops.ll

+; RUN: opt < %s -loop-deletion -S | FileCheck %s
+; RUN: opt < %s -loop-deletion -verify-dom-info -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
+}
+
+; FIXME: multiple constant conditional branches with loop not-taken in test1.
+; Currently, we do not delete the loop.
+define void @test5(i64 %n, i64 %m, i1 %cond) nounwind {
+; CHECK-LABEL: test5
+; CHECK-LABEL: 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 makes L3 unreachable.
+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 unreachable 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
+}
+