Move deleteDeadLoop to LoopUtils. NFC

[kariddi]

Summary

Moving deleteDeadLoop in LoopUtils like the FIXME in the comments is asking to be done.

I made it such that can update various analysis conditionally in case we are running it in a pass that doesn't preserve those analysis anyway

[anna]

include/llvm/Transforms/Utils/LoopUtils.h

444

These comments are stale now. Please update.

lib/Transforms/Utils/LoopUtils.cpp

1142

These comments are stale now. The 2 kinds of "dead" loops were specific to loop deletion.

1147

Please state as a comment that we also have certain requirements on the structure of the loop and the deletion works by connecting the preheader directly to the exit. (these conditions have been specified as asserts below: preheader has exactly one successors, we have exactly one exit block etc).

[kariddi]

Thanks Anna for the review.

I modified the comments

[anna]

lib/Transforms/Utils/LoopUtils.cpp

1145

This second part is incorrect. We can have any number of predecessors to the exit block, we just remove all the predecessors (because these are from the dead loop) and set the preheader as the only predecessor of the exit block.

Pls rmove the second part of the statement.

[kariddi]

lib/Transforms/Utils/LoopUtils.cpp

1145

What I meant with that is that the predecessors of the exit need to be only blocks from the loop (aka. The loop has dedicated exits).

That should be a requirement for the function (There's an assert for that). I'll reword it by just saying that the exit needs to be dedicated.
I agree that how it is right now is confusing

[kariddi]

Updated confusing comment after Anna's suggestion.

[anna]

LGTM with nits.

lib/Transforms/Utils/LoopUtils.cpp

1145

Could you phrase it as "a unique dedicated exit block must exist".

Btw, please keep this explanation in the LoopUtils header. We don't need to repeat it here. I think that's the convention we follow in llvm header and cpp files, to avoid repetition.

[kariddi]

Thanks Anna.
Addressed your nitpicks.

Forgot to add the Differential revision in the commit message, so I'll close this manually as it will not do it by itself.

include/llvm/Transforms/Utils/LoopUtils.h

 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
 /// loop and loop safety information as arguments. Diagnostics is emitted via \p
 /// ORE. It returns changed status.
 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
                  LoopSafetyInfo *, OptimizationRemarkEmitter *ORE);
 
+/// This function deletes dead loops. The caller of this function needs to
+/// guarantee that the loop is infact dead.
+/// The function requires a bunch or prerequisites to be present:
+///   - The loop needs to be in LCSSA form
+///   - The loop needs to have a Preheader
+///   - A unique exit block must exist and the loop should be the only
+///     predecessor of the exit
+///
+/// This also updates the relevant analysis information in \p DT, \p SE, and \p
+/// LI if pointers to those are provided.
+/// It also updates the loop PM if an updater struct is provided.
+
+void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE,
+                    LoopInfo *LI);
+
 /// \brief Try to promote memory values to scalars by sinking stores out of
 /// the loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
 /// loop invariant. It takes a set of must-alias values, Loop exit blocks
 /// vector, loop exit blocks insertion point vector, PredIteratorCache,
 /// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions
 /// of the loop and loop safety information as arguments.
 /// Diagnostics is emitted via \p ORE. It returns changed status.

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 (\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);
-
 enum class LoopDeletionResult {
   Unmodified,
   Modified,
   Deleted,
 };
 
 /// Determines if a loop is dead.
 ///
if (ExitBlock && isLoopNeverExecuted(L)) {
     DEBUG(dbgs() << "Loop is proven to never execute, delete it!");
     // Set incoming value to undef for phi nodes in the exit block.
     BasicBlock::iterator BI = ExitBlock->begin();
     while (PHINode *P = dyn_cast<PHINode>(BI)) {
       for (unsigned i = 0; i < P->getNumIncomingValues(); i++)
         P->setIncomingValue(i, UndefValue::get(P->getType()));
       BI++;
     }
-    deleteDeadLoop(L, DT, SE, LI);
+    deleteDeadLoop(L, &DT, &SE, &LI);
     ++NumDeleted;
     return LoopDeletionResult::Deleted;
   }
 
   // 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);
static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
   const SCEV *S = SE.getMaxBackedgeTakenCount(L);
   if (isa<SCEVCouldNotCompute>(S)) {
     DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n");
     return Changed ? LoopDeletionResult::Modified
                    : LoopDeletionResult::Unmodified;
   }
 
   DEBUG(dbgs() << "Loop is invariant, delete it!");
-  deleteDeadLoop(L, DT, SE, LI);
+  deleteDeadLoop(L, &DT, &SE, &LI);
   ++NumDeleted;
 
   return LoopDeletionResult::Deleted;
 }
 
-static void deleteDeadLoop(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
-                           LoopInfo &LI) {
-  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.
-
-  // 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!");
-  assert(L->hasDedicatedExits() && "Loop should have dedicated exits!");
-
-  auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator());
-  assert(OldBr && "Preheader must end with a branch");
-  assert(OldBr->isUnconditional() && "Preheader must have a single successor");
-  // Connect the preheader to the exit block. Keep the old edge to the header
-  // around to perform the dominator tree update in two separate steps
-  // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
-  // preheader -> header.
-  //
-  //
-  // 0.  Preheader          1.  Preheader           2.  Preheader
-  //        |                    |   |                   |
-  //        V                    |   V                   |
-  //      Header <--\            | Header <--\           | Header <--\
-  //       |  |     |            |  |  |     |           |  |  |     |
-  //       |  V     |            |  |  V     |           |  |  V     |
-  //       | Body --/            |  | Body --/           |  | Body --/
-  //       V                     V  V                    V  V
-  //      Exit                   Exit                    Exit
-  //
-  // By doing this is two separate steps we can perform the dominator tree
-  // update without using the batch update API.
-  //
-  // 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.
-  IRBuilder<> Builder(OldBr);
-  Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock);
-  // Remove the old branch. The conditional branch becomes a new terminator.
-  OldBr->eraseFromParent();
-
-  // Update the dominator tree by informing it about the new edge from the
-  // preheader to the exit.
-  DT.insertEdge(Preheader, ExitBlock);
-
-  // Rewrite phis in the exit block to get their inputs from the Preheader
-  // instead of the exiting block.
-  BasicBlock::iterator BI = ExitBlock->begin();
-  while (PHINode *P = dyn_cast<PHINode>(BI)) {
-    // Set the zero'th element of Phi to be from the preheader and remove all
-    // other incoming values. Given the loop has dedicated exits, all other
-    // incoming values must be from the exiting blocks.
-    int PredIndex = 0;
-    P->setIncomingBlock(PredIndex, Preheader);
-    // Removes all incoming values from all other exiting blocks (including
-    // duplicate values from an exiting block).
-    // Nuke all entries except the zero'th entry which is the preheader entry.
-    // NOTE! We need to remove Incoming Values in the reverse order as done
-    // below, to keep the indices valid for deletion (removeIncomingValues
-    // updates getNumIncomingValues and shifts all values down into the operand
-    // being deleted).
-    for (unsigned i = 0, e = P->getNumIncomingValues() - 1; i != e; ++i)
-      P->removeIncomingValue(e-i, false);
-
-    assert((P->getNumIncomingValues() == 1 &&
-            P->getIncomingBlock(PredIndex) == Preheader) &&
-           "Should have exactly one value and that's from the preheader!");
-    ++BI;
-  }
-
-  // Disconnect the loop body by branching directly to its exit.
-  Builder.SetInsertPoint(Preheader->getTerminator());
-  Builder.CreateBr(ExitBlock);
-  // Remove the old branch.
-  Preheader->getTerminator()->eraseFromParent();
-
-  // Inform the dominator tree about the removed edge.
-  DT.deleteEdge(Preheader, L->getHeader());
-
-  // Remove the block from the reference counting scheme, so that we can
-  // delete it freely later.
-  for (auto *Block : L->blocks())
-    Block->dropAllReferences();
-
-  // Erase the instructions and the blocks without having to worry
-  // about ordering because we already dropped the references.
-  // NOTE: This iteration is safe because erasing the block does not remove its
-  // entry from the loop's block list.  We do that in the next section.
-  for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
-       LI != LE; ++LI)
-    (*LI)->eraseFromParent();
-
-  // Finally, the blocks from loopinfo.  This has to happen late because
-  // otherwise our loop iterators won't work.
-
-  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.erase(L);
-}
-
 PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM,
                                         LoopStandardAnalysisResults &AR,
                                         LPMUpdater &Updater) {
 
   DEBUG(dbgs() << "Analyzing Loop for deletion: ");
   DEBUG(L.dump());
   std::string LoopName = L.getName();
   auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI);

lib/Transforms/Utils/LoopUtils.cpp

llvm::collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop) {
 
   for (size_t I = 0; I < Worklist.size(); I++)
     for (DomTreeNode *Child : Worklist[I]->getChildren())
       AddRegionToWorklist(Child);
 
   return Worklist;
 }
 
+/// This function deletes dead loops. The caller of this function needs to
+/// guarantee that the loop is infact dead.
+/// The function requires a bunch or prerequisites to be present:
+///   - The loop needs to be in LCSSA form
+///   - The loop needs to have a Preheader
+///   - A unique exit block must exist and the loop should be the only
+///     predecessor of the exit
+///
+/// This also updates the relevant analysis information in \p DT, \p SE, and \p
+/// LI if pointers to those are provided.
+/// It also updates the loop PM if an updater struct is provided.
+
+void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT = nullptr,
+                          ScalarEvolution *SE = nullptr,
+                          LoopInfo *LI = nullptr) {
+  assert(!DT || 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.
+
+  // 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.
+  if (SE)
+    SE->forgetLoop(L);
+
+  auto *ExitBlock = L->getUniqueExitBlock();
+  assert(ExitBlock && "Should have a unique exit block!");
+  assert(L->hasDedicatedExits() && "Loop should have dedicated exits!");
+
+  auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator());
+  assert(OldBr && "Preheader must end with a branch");
+  assert(OldBr->isUnconditional() && "Preheader must have a single successor");
+  // Connect the preheader to the exit block. Keep the old edge to the header
+  // around to perform the dominator tree update in two separate steps
+  // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
+  // preheader -> header.
+  //
+  //
+  // 0.  Preheader          1.  Preheader           2.  Preheader
+  //        |                    |   |                   |
+  //        V                    |   V                   |
+  //      Header <--\            | Header <--\           | Header <--\
+  //       |  |     |            |  |  |     |           |  |  |     |
+  //       |  V     |            |  |  V     |           |  |  V     |
+  //       | Body --/            |  | Body --/           |  | Body --/
+  //       V                     V  V                    V  V
+  //      Exit                   Exit                    Exit
+  //
+  // By doing this is two separate steps we can perform the dominator tree
+  // update without using the batch update API.
+  //
+  // 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.
+  IRBuilder<> Builder(OldBr);
+  Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock);
+  // Remove the old branch. The conditional branch becomes a new terminator.
+  OldBr->eraseFromParent();
+
+  // Rewrite phis in the exit block to get their inputs from the Preheader
+  // instead of the exiting block.
+  BasicBlock::iterator BI = ExitBlock->begin();
+  while (PHINode *P = dyn_cast<PHINode>(BI)) {
+    // Set the zero'th element of Phi to be from the preheader and remove all
+    // other incoming values. Given the loop has dedicated exits, all other
+    // incoming values must be from the exiting blocks.
+    int PredIndex = 0;
+    P->setIncomingBlock(PredIndex, Preheader);
+    // Removes all incoming values from all other exiting blocks (including
+    // duplicate values from an exiting block).
+    // Nuke all entries except the zero'th entry which is the preheader entry.
+    // NOTE! We need to remove Incoming Values in the reverse order as done
+    // below, to keep the indices valid for deletion (removeIncomingValues
+    // updates getNumIncomingValues and shifts all values down into the operand
+    // being deleted).
+    for (unsigned i = 0, e = P->getNumIncomingValues() - 1; i != e; ++i)
+      P->removeIncomingValue(e - i, false);
+
+    assert((P->getNumIncomingValues() == 1 &&
+            P->getIncomingBlock(PredIndex) == Preheader) &&
+           "Should have exactly one value and that's from the preheader!");
+    ++BI;
+  }
+
+  // Disconnect the loop body by branching directly to its exit.
+  Builder.SetInsertPoint(Preheader->getTerminator());
+  Builder.CreateBr(ExitBlock);
+  // Remove the old branch.
+  Preheader->getTerminator()->eraseFromParent();
+
+  if (DT) {
+    // Update the dominator tree by informing it about the new edge from the
+    // preheader to the exit.
+    DT->insertEdge(Preheader, ExitBlock);
+    // Inform the dominator tree about the removed edge.
+    DT->deleteEdge(Preheader, L->getHeader());
+  }
+
+  // Remove the block from the reference counting scheme, so that we can
+  // delete it freely later.
+  for (auto *Block : L->blocks())
+    Block->dropAllReferences();
+
+  if (LI) {
+    // Erase the instructions and the blocks without having to worry
+    // about ordering because we already dropped the references.
+    // NOTE: This iteration is safe because erasing the block does not remove
+    // its entry from the loop's block list.  We do that in the next section.
+    for (Loop::block_iterator LpI = L->block_begin(), LpE = L->block_end();
+         LpI != LpE; ++LpI)
+      (*LpI)->eraseFromParent();
+
+    // Finally, the blocks from loopinfo.  This has to happen late because
+    // otherwise our loop iterators won't work.
+
+    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->erase(L);
+  }
+}
+
 /// Returns true if the instruction in a loop is guaranteed to execute at least
 /// once.
 bool llvm::isGuaranteedToExecute(const Instruction &Inst,
                                  const DominatorTree *DT, const Loop *CurLoop,
                                  const LoopSafetyInfo *SafetyInfo) {
   // We have to check to make sure that the instruction dominates all
   // of the exit blocks.  If it doesn't, then there is a path out of the loop
   // which does not execute this instruction, so we can't hoist it.