[PM] Port Dead Loop Deletion Pass to the new PM

[junbuml]

Summary

Port Dead Loop Deletion Pass to the new pass manager.

[silvas]

Hi Jun Bum,

First, thank you for taking the time to port this!

My understanding is that there is currently an issue with the new PM which causes it to not behave as expected in response to the loopInfo.markAsRemoved(L) call.
The core issue is that it is using this generic code for running a sequence of loop passes:
https://github.com/llvm-project/llvm/blob/master/include/llvm/Analysis/LoopPassManager.h#L30
https://github.com/llvm-project/llvm/blob/master/include/llvm/IR/PassManager.h#L244
Even though a loop may be marked as deleted, it will continue to run passes on it.

In the old PM, it will actually check if the loop was deleted and avoid running further passes on it:
https://github.com/llvm-project/llvm/blob/master/lib/Analysis/LoopPass.cpp#L204
https://github.com/llvm-project/llvm/blob/master/lib/Analysis/LoopPass.cpp#L238

So my suspicion is that if you run loop passes after loop-deletion deletes a loop then the pass manager will start running passes on loops that have been deleted. What happens in that case? Will we hit assertions?

(
also, the function to loop pass adaptor does not have any special handling for loop deletion; I'm not sure what that affects.
https://github.com/llvm-project/llvm/blob/master/include/llvm/Analysis/LoopPassManager.h#L84
)

I've added Davide as a reviewer. He has been looking more closely at the loop passes and will hopefully be able to provide some more information.

[davide]

In D21483#462155, @silvas wrote:

Hi Jun Bum,

First, thank you for taking the time to port this!

My understanding is that there is currently an issue with the new PM which causes it to not behave as expected in response to the loopInfo.markAsRemoved(L) call.
The core issue is that it is using this generic code for running a sequence of loop passes:
https://github.com/llvm-project/llvm/blob/master/include/llvm/Analysis/LoopPassManager.h#L30
https://github.com/llvm-project/llvm/blob/master/include/llvm/IR/PassManager.h#L244
Even though a loop may be marked as deleted, it will continue to run passes on it.

In the old PM, it will actually check if the loop was deleted and avoid running further passes on it:
https://github.com/llvm-project/llvm/blob/master/lib/Analysis/LoopPass.cpp#L204
https://github.com/llvm-project/llvm/blob/master/lib/Analysis/LoopPass.cpp#L238

So my suspicion is that if you run loop passes after loop-deletion deletes a loop then the pass manager will start running passes on loops that have been deleted. What happens in that case? Will we hit assertions?

(
also, the function to loop pass adaptor does not have any special handling for loop deletion; I'm not sure what that affects.
https://github.com/llvm-project/llvm/blob/master/include/llvm/Analysis/LoopPassManager.h#L84
)

I've added Davide as a reviewer. He has been looking more closely at the loop passes and will hopefully be able to provide some more information.

Sean is absolutely right, this pass is blocked on some missing functionality in the new LoopPM. We're still discussing on what are the correct semantics/interfaces for the CGSCCPassManager, and after that the plan is to add the missing functionality to LoopPM. Please hold on until this is unblocked. Sorry.

[junbuml]

Thanks Seen and Davide for the comment. I will hold it till the issue is resolved.

[silvas]

Hi Jun,

Feel free to rebase and commit this. I was testing it yesterday (my rebased patch is here: http://reviews.llvm.org/F2159016) and I think it is fine to go in.

If anything, having this committed will make the problems in the loop pass manager clearer / more obvious to fix.

• Sean Silva

[junbuml]

Thanks Sean. I will commit this soon.

include/llvm/InitializePasses.h

 void initializeLiveRegMatrixPass(PassRegistry&);
 void initializeLiveStacksPass(PassRegistry&);
 void initializeLiveVariablesPass(PassRegistry&);
 void initializeLoadCombinePass(PassRegistry&);
 void initializeLoaderPassPass(PassRegistry&);
 void initializeLocalStackSlotPassPass(PassRegistry&);
 void initializeLoopAccessAnalysisPass(PassRegistry&);
 void initializeLoopDataPrefetchPass(PassRegistry&);
-void initializeLoopDeletionPass(PassRegistry&);
+void initializeLoopDeletionLegacyPassPass(PassRegistry&);
 void initializeLoopDistributePass(PassRegistry&);
 void initializeLoopExtractorPass(PassRegistry&);
 void initializeLoopIdiomRecognizePass(PassRegistry&);
 void initializeLoopInfoWrapperPassPass(PassRegistry&);
 void initializeLoopInstSimplifyPass(PassRegistry&);
 void initializeLoopInterchangePass(PassRegistry &);
 void initializeLoopLoadEliminationPass(PassRegistry&);
 void initializeLoopPassPass(PassRegistry&);

include/llvm/Transforms/Scalar/LoopDeletion.h

+//===- LoopDeletion.h - Loop Deletion -------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides the interface for the Loop Deletion Pass.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_SCALAR_LOOPDELETION_H
+#define LLVM_TRANSFORMS_SCALAR_LOOPDELETION_H
+
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+class LoopDeletionPass : public PassInfoMixin<LoopDeletionPass> {
+public:
+  LoopDeletionPass() {}
+  PreservedAnalyses run(Loop &L, AnalysisManager<Loop> &AM);
+  bool runImpl(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
+               LoopInfo &loopInfo);
+
+private:
+  bool isLoopDead(Loop *L, ScalarEvolution &SE,
+                  SmallVectorImpl<BasicBlock *> &exitingBlocks,
+                  SmallVectorImpl<BasicBlock *> &exitBlocks, bool &Changed,
+                  BasicBlock *Preheader);
+};
+}
+
+#endif // LLVM_TRANSFORMS_SCALAR_LOOPDELETION_H

lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Scalar/BDCE.h"
 #include "llvm/Transforms/Scalar/DCE.h"
 #include "llvm/Transforms/Scalar/DeadStoreElimination.h"
 #include "llvm/Transforms/Scalar/EarlyCSE.h"
 #include "llvm/Transforms/Scalar/GVN.h"
 #include "llvm/Transforms/Scalar/GuardWidening.h"
 #include "llvm/Transforms/Scalar/IndVarSimplify.h"
 #include "llvm/Transforms/Scalar/JumpThreading.h"
+#include "llvm/Transforms/Scalar/LoopDeletion.h"
 #include "llvm/Transforms/Scalar/LoopRotation.h"
 #include "llvm/Transforms/Scalar/LoopSimplifyCFG.h"
 #include "llvm/Transforms/Scalar/LowerAtomic.h"
 #include "llvm/Transforms/Scalar/LowerExpectIntrinsic.h"
 #include "llvm/Transforms/Scalar/MemCpyOptimizer.h"
 #include "llvm/Transforms/Scalar/PartiallyInlineLibCalls.h"
 #include "llvm/Transforms/Scalar/Reassociate.h"
 #include "llvm/Transforms/Scalar/SCCP.h"

lib/Passes/PassRegistry.def

 #define LOOP_PASS(NAME, CREATE_PASS)
 #endif
 LOOP_PASS("invalidate<all>", InvalidateAllAnalysesPass())
 LOOP_PASS("rotate", LoopRotatePass())
 LOOP_PASS("no-op-loop", NoOpLoopPass())
 LOOP_PASS("print", PrintLoopPass(dbgs()))
 LOOP_PASS("simplify-cfg", LoopSimplifyCFGPass())
 LOOP_PASS("indvars", IndVarSimplifyPass())
+LOOP_PASS("loop-deletion", LoopDeletionPass())
 #undef LOOP_PASS

lib/Transforms/Scalar/LoopDeletion.cpp

 //===- LoopDeletion.cpp - Dead Loop Deletion Pass ---------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the Dead Loop Deletion Pass. This pass is responsible
 // for eliminating loops with non-infinite computable trip counts that have no
 // side effects or volatile instructions, and do not contribute to the
 // computation of the function's return value.
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Transforms/Scalar.h"
+#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/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/LoopPassManager.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-delete"
 
 STATISTIC(NumDeleted, "Number of loops deleted");
 
-namespace {
-  class LoopDeletion : public LoopPass {
-  public:
-    static char ID; // Pass ID, replacement for typeid
-    LoopDeletion() : LoopPass(ID) {
-      initializeLoopDeletionPass(*PassRegistry::getPassRegistry());
-    }
-
-    // Possibly eliminate loop L if it is dead.
-    bool runOnLoop(Loop *L, LPPassManager &) override;
-
-    void getAnalysisUsage(AnalysisUsage &AU) const override {
-      getLoopAnalysisUsage(AU);
-    }
-
-  private:
-    bool isLoopDead(Loop *L, ScalarEvolution &SE,
-                    SmallVectorImpl<BasicBlock *> &exitingBlocks,
-                    SmallVectorImpl<BasicBlock *> &exitBlocks, bool &Changed,
-                    BasicBlock *Preheader);
-  };
-}
-
-char LoopDeletion::ID = 0;
-INITIALIZE_PASS_BEGIN(LoopDeletion, "loop-deletion",
-                "Delete dead loops", false, false)
-INITIALIZE_PASS_DEPENDENCY(LoopPass)
-INITIALIZE_PASS_END(LoopDeletion, "loop-deletion",
-                "Delete dead loops", false, false)
-
-Pass *llvm::createLoopDeletionPass() {
-  return new LoopDeletion();
-}
-
 /// isLoopDead - Determined 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.
-bool LoopDeletion::isLoopDead(Loop *L, ScalarEvolution &SE,
+bool LoopDeletionPass::isLoopDead(Loop *L, ScalarEvolution &SE,
                                   SmallVectorImpl<BasicBlock *> &exitingBlocks,
                                   SmallVectorImpl<BasicBlock *> &exitBlocks,
                                   bool &Changed, BasicBlock *Preheader) {
   BasicBlock *exitBlock = exitBlocks[0];
 
   // Make sure that all PHI entries coming from the loop are loop invariant.
   // Because the code is in LCSSA form, any values used outside of the loop
   // must pass through a PHI in the exit block, meaning that this check is
   // sufficient to guarantee that no loop-variant values are used outside
   // of the loop.
   BasicBlock::iterator BI = exitBlock->begin();
if (!AllEntriesInvariant || !AllOutgoingValuesSame)
     return false;
 
   // Make sure that no instructions in the block have potential side-effects.
   // This includes instructions that could write to memory, and loads that are
   // marked volatile.  This could be made more aggressive by using aliasing
   // information to identify readonly and readnone calls.
   for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
        LI != LE; ++LI) {
-    for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end();
-         BI != BE; ++BI) {
+    for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); BI != BE;
+         ++BI) {
       if (BI->mayHaveSideEffects())
         return false;
     }
   }
-
   return true;
 }
 
-/// runOnLoop - Remove dead loops, by which we mean loops that do not impact the
-/// observable behavior of the program other than finite running time.  Note
-/// we do ensure that this never remove a loop that might be infinite, as doing
-/// so could change the halting/non-halting nature of a program.
-/// NOTE: This entire process relies pretty heavily on LoopSimplify and LCSSA
-/// in order to make various safety checks work.
-bool LoopDeletion::runOnLoop(Loop *L, LPPassManager &) {
-  if (skipLoop(L))
-    return false;
-
-  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+/// Remove dead loops, by which we mean loops that do not impact the observable
+/// behavior of the program other than finite running time.  Note we do ensure
+/// that this never remove a loop that might be infinite, as doing so could
+/// change the halting/non-halting nature of a program. NOTE: This entire
+/// process relies pretty heavily on LoopSimplify and LCSSA in order to make
+/// various safety checks work.
+bool LoopDeletionPass::runImpl(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
+                               LoopInfo &loopInfo) {
   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;
 
-  SmallVector<BasicBlock*, 4> exitingBlocks;
+  SmallVector<BasicBlock *, 4> exitingBlocks;
   L->getExitingBlocks(exitingBlocks);
 
-  SmallVector<BasicBlock*, 4> exitBlocks;
+  SmallVector<BasicBlock *, 4> exitBlocks;
   L->getUniqueExitBlocks(exitBlocks);
 
   // 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.
   if (exitBlocks.size() != 1)
     return false;
 
-  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
-
   // Finally, we have to check that the loop really is dead.
   bool Changed = false;
   if (!isLoopDead(L, SE, exitingBlocks, exitBlocks, 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);
while (PHINode *P = dyn_cast<PHINode>(BI)) {
     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.
-  SmallVector<DomTreeNode*, 8> ChildNodes;
+  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
     // allows us to remove the domtree entry for the block.
     ChildNodes.insert(ChildNodes.begin(), DT[*LI]->begin(), DT[*LI]->end());
     for (SmallVectorImpl<DomTreeNode *>::iterator DI = ChildNodes.begin(),
-         DE = ChildNodes.end(); DI != DE; ++DI) {
+                                                  DE = ChildNodes.end();
+         DI != DE; ++DI) {
       DT.changeImmediateDominator(*DI, DT[preheader]);
     }
 
     ChildNodes.clear();
     DT.eraseNode(*LI);
 
     // Remove the block from the reference counting scheme, so that we can
     // delete it freely later.
     (*LI)->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.
-  LoopInfo &loopInfo = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-  SmallPtrSet<BasicBlock*, 8> blocks;
+
+  SmallPtrSet<BasicBlock *, 8> blocks;
   blocks.insert(L->block_begin(), L->block_end());
   for (BasicBlock *BB : blocks)
     loopInfo.removeBlock(BB);
 
   // The last step is to update LoopInfo now that we've eliminated this loop.
   loopInfo.markAsRemoved(L);
   Changed = true;
 
   ++NumDeleted;
 
   return Changed;
 }
+
+PreservedAnalyses LoopDeletionPass::run(Loop &L, AnalysisManager<Loop> &AM) {
+  auto &FAM = AM.getResult<FunctionAnalysisManagerLoopProxy>(L).getManager();
+  Function *F = L.getHeader()->getParent();
+
+  auto &DT = *FAM.getCachedResult<DominatorTreeAnalysis>(*F);
+  auto &SE = *FAM.getCachedResult<ScalarEvolutionAnalysis>(*F);
+  auto &LI = *FAM.getCachedResult<LoopAnalysis>(*F);
+
+  bool Changed = runImpl(&L, DT, SE, LI);
+  if (!Changed)
+    return PreservedAnalyses::all();
+
+  return getLoopPassPreservedAnalyses();
+}
+
+namespace {
+class LoopDeletionLegacyPass : public LoopPass {
+public:
+  static char ID; // Pass ID, replacement for typeid
+  LoopDeletionLegacyPass() : LoopPass(ID) {
+    initializeLoopDeletionLegacyPassPass(*PassRegistry::getPassRegistry());
+  }
+
+  // Possibly eliminate loop L if it is dead.
+  bool runOnLoop(Loop *L, LPPassManager &) override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    getLoopAnalysisUsage(AU);
+  }
+};
+}
+
+char LoopDeletionLegacyPass::ID = 0;
+INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",
+                      "Delete dead loops", false, false)
+INITIALIZE_PASS_DEPENDENCY(LoopPass)
+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 &loopInfo = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+
+  LoopDeletionPass Impl;
+  return Impl.runImpl(L, DT, SE, loopInfo);
+}

lib/Transforms/Scalar/Scalar.cpp

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeGVNLegacyPassPass(Registry);
   initializeEarlyCSELegacyPassPass(Registry);
   initializeFlattenCFGPassPass(Registry);
   initializeInductiveRangeCheckEliminationPass(Registry);
   initializeIndVarSimplifyLegacyPassPass(Registry);
   initializeJumpThreadingPass(Registry);
   initializeLICMPass(Registry);
   initializeLoopDataPrefetchPass(Registry);
-  initializeLoopDeletionPass(Registry);
+  initializeLoopDeletionLegacyPassPass(Registry);
   initializeLoopAccessAnalysisPass(Registry);
   initializeLoopInstSimplifyPass(Registry);
   initializeLoopInterchangePass(Registry);
   initializeLoopRotateLegacyPassPass(Registry);
   initializeLoopStrengthReducePass(Registry);
   initializeLoopRerollPass(Registry);
   initializeLoopUnrollPass(Registry);
   initializeLoopUnswitchPass(Registry);

test/Transforms/LoopDeletion/multiple-exit-conditions.ll

 ; RUN: opt < %s -loop-deletion -S | FileCheck %s
+; RUN: opt < %s -passes='require<scalar-evolution>,loop(loop-deletion)' -S | FileCheck %s
 
 ; ScalarEvolution can prove the loop iteration is finite, even though
 ; it can't represent the exact trip count as an expression. That's
 ; good enough to let the loop be deleted.
 
 ; CHECK:      entry:
 ; CHECK-NEXT:   br label %return