LPM: Simplify how passes mark loops for deletion. NFC

When a pass removes a loop it currently has to reach up into the
LPPassManager's internals to update the state of the iteration over
loops. This reverse dependency results in a pretty awkward interplay
of the LPPassManager and its Passes.

Here, we change this to instead keep track of when a loop has become
"unlooped" in the Loop objects themselves, then the LPPassManager can
check this and manipulate its own state directly. This opens the door
to allow most of the loop passes to work without a backreference to
the LPPassManager.

I've kept passes calling the LPPassManager::deleteLoopFromQueue API
now so I could put an assert in to prove that this is NFC, but a later
pass will update passes just to preserve the LoopInfo directly and
stop referencing the LPPassManager completely.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@255720 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index 57695b46d6400ba281bd30c4b9c7e14b192eb0c8..c219bd85a48abb0ba972c2e225f081fe20d68a86 100644 (file)
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -73,6 +73,10 @@ class LoopBase {
 
   SmallPtrSet<const BlockT*, 8> DenseBlockSet;
 
 
   SmallPtrSet<const BlockT*, 8> DenseBlockSet;
 

+  /// Indicator that this loops has been "unlooped", so there's no loop here
+  /// anymore.
+  bool IsUnloop = false;
+

   LoopBase(const LoopBase<BlockT, LoopT> &) = delete;
   const LoopBase<BlockT, LoopT>&
     operator=(const LoopBase<BlockT, LoopT> &) = delete;
   LoopBase(const LoopBase<BlockT, LoopT> &) = delete;
   const LoopBase<BlockT, LoopT>&
     operator=(const LoopBase<BlockT, LoopT> &) = delete;


@@ -150,6 +154,13 @@ public:
     return Blocks.size();
   }
 
     return Blocks.size();
   }
 

+  /// Mark this loop as having been unlooped - the last backedge was removed and
+  /// we no longer have a loop.
+  void markUnlooped() { IsUnloop = true; }
+
+  /// Return true if this no longer represents a loop.
+  bool isUnloop() const { return IsUnloop; }
+

   /// isLoopExiting - True if terminator in the block can branch to another
   /// block that is outside of the current loop.
   ///
   /// isLoopExiting - True if terminator in the block can branch to another
   /// block that is outside of the current loop.
   ///


@@ -661,8 +672,9 @@ public:
 
   /// updateUnloop - Update LoopInfo after removing the last backedge from a
   /// loop--now the "unloop". This updates the loop forest and parent loops for
 
   /// updateUnloop - Update LoopInfo after removing the last backedge from a
   /// loop--now the "unloop". This updates the loop forest and parent loops for

-  /// each block so that Unloop is no longer referenced, but the caller must
-  /// actually delete the Unloop object.
+  /// each block so that Unloop is no longer referenced, but does not actually
+  /// delete the Unloop object. Generally, the loop pass manager should manage
+  /// deleting the Unloop.

   void updateUnloop(Loop *Unloop);
 
   /// replacementPreservesLCSSAForm - Returns true if replacing From with To
   void updateUnloop(Loop *Unloop);
 
   /// replacementPreservesLCSSAForm - Returns true if replacing From with To

diff --git a/include/llvm/Analysis/LoopPass.h b/include/llvm/Analysis/LoopPass.h
index f2ead0963588e5aaddd7969dd864fe9ebcc699b6..cbc66b9c9a65eb23c3b9db7da9d87925ce02318a 100644 (file)
--- a/include/llvm/Analysis/LoopPass.h
+++ b/include/llvm/Analysis/LoopPass.h
@@ -155,7 +155,6 @@ public:
 
 private:
   std::deque<Loop *> LQ;
 
 private:
   std::deque<Loop *> LQ;

-  bool skipThisLoop;

   LoopInfo *LI;
   Loop *CurrentLoop;
 };
   LoopInfo *LI;
   Loop *CurrentLoop;
 };

diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp
index 07fd6a2ae7090b9c58a46e6183322cf8977badaa..ee311c50eee489e6d560518d83fa443e6831e908 100644 (file)
--- a/lib/Analysis/LoopInfo.cpp
+++ b/lib/Analysis/LoopInfo.cpp
@@ -630,14 +630,8 @@ LoopInfo::LoopInfo(const DominatorTreeBase<BasicBlock> &DomTree) {
   analyze(DomTree);
 }
 
   analyze(DomTree);
 }
 

-/// updateUnloop - The last backedge has been removed from a loop--now the
-/// "unloop". Find a new parent for the blocks contained within unloop and
-/// update the loop tree. We don't necessarily have valid dominators at this
-/// point, but LoopInfo is still valid except for the removal of this loop.
-///
-/// Note that Unloop may now be an empty loop. Calling Loop::getHeader without
-/// checking first is illegal.

 void LoopInfo::updateUnloop(Loop *Unloop) {
 void LoopInfo::updateUnloop(Loop *Unloop) {

+  Unloop->markAsUnloop();

 
   // First handle the special case of no parent loop to simplify the algorithm.
   if (!Unloop->getParentLoop()) {
 
   // First handle the special case of no parent loop to simplify the algorithm.
   if (!Unloop->getParentLoop()) {

diff --git a/lib/Analysis/LoopPass.cpp b/lib/Analysis/LoopPass.cpp
index 0cfc94c1434ca89fa3cb9c91bf7a47f34827b5a9..54b61256134cd6ced0a21062027818473df619af 100644 (file)
--- a/lib/Analysis/LoopPass.cpp
+++ b/lib/Analysis/LoopPass.cpp
@@ -58,37 +58,14 @@ char LPPassManager::ID = 0;
 
 LPPassManager::LPPassManager()
   : FunctionPass(ID), PMDataManager() {
 
 LPPassManager::LPPassManager()
   : FunctionPass(ID), PMDataManager() {

-  skipThisLoop = false;

   LI = nullptr;
   CurrentLoop = nullptr;
 }
 
 /// Delete loop from the loop queue and loop hierarchy (LoopInfo).
 void LPPassManager::deleteLoopFromQueue(Loop *L) {
   LI = nullptr;
   CurrentLoop = nullptr;
 }
 
 /// Delete loop from the loop queue and loop hierarchy (LoopInfo).
 void LPPassManager::deleteLoopFromQueue(Loop *L) {

-
+  assert(CurrentLoop == L && "deleting a loop that is not being operated on");

   LI->updateUnloop(L);
   LI->updateUnloop(L);

-
-  // Notify passes that the loop is being deleted.
-  deleteSimpleAnalysisLoop(L);
-
-  // If L is current loop then skip rest of the passes and let
-  // runOnFunction remove L from LQ. Otherwise, remove L from LQ now
-  // and continue applying other passes on CurrentLoop.
-  if (CurrentLoop == L)
-    skipThisLoop = true;
-
-  delete L;
-
-  if (skipThisLoop)
-    return;
-
-  for (std::deque<Loop *>::iterator I = LQ.begin(),
-         E = LQ.end(); I != E; ++I) {
-    if (*I == L) {
-      LQ.erase(I);
-      break;
-    }
-  }

 }
 
 // Inset loop into loop nest (LoopInfo) and loop queue (LQ).
 }
 
 // Inset loop into loop nest (LoopInfo) and loop queue (LQ).


@@ -204,9 +181,7 @@ bool LPPassManager::runOnFunction(Function &F) {
   // Walk Loops
   while (!LQ.empty()) {
 
   // Walk Loops
   while (!LQ.empty()) {
 

-    CurrentLoop  = LQ.back();
-    skipThisLoop = false;
-
+    CurrentLoop = LQ.back();

     // Run all passes on the current Loop.
     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
       LoopPass *P = getContainedPass(Index);
     // Run all passes on the current Loop.
     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
       LoopPass *P = getContainedPass(Index);


@@ -226,11 +201,15 @@ bool LPPassManager::runOnFunction(Function &F) {
 
       if (Changed)
         dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,
 
       if (Changed)
         dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,

-                     skipThisLoop ? "<deleted>" :
-                                    CurrentLoop->getHeader()->getName());
+                     CurrentLoop->isUnloop()
+                         ? "<deleted>"
+                         : CurrentLoop->getHeader()->getName());

       dumpPreservedSet(P);
 
       dumpPreservedSet(P);
 

-      if (!skipThisLoop) {
+      if (CurrentLoop->isUnloop()) {
+        // Notify passes that the loop is being deleted.
+        deleteSimpleAnalysisLoop(CurrentLoop);
+      } else {

         // Manually check that this loop is still healthy. This is done
         // instead of relying on LoopInfo::verifyLoop since LoopInfo
         // is a function pass and it's really expensive to verify every
         // Manually check that this loop is still healthy. This is done
         // instead of relying on LoopInfo::verifyLoop since LoopInfo
         // is a function pass and it's really expensive to verify every


@@ -249,12 +228,12 @@ bool LPPassManager::runOnFunction(Function &F) {
 
       removeNotPreservedAnalysis(P);
       recordAvailableAnalysis(P);
 
       removeNotPreservedAnalysis(P);
       recordAvailableAnalysis(P);

-      removeDeadPasses(P,
-                       skipThisLoop ? "<deleted>" :
-                                      CurrentLoop->getHeader()->getName(),
+      removeDeadPasses(P, CurrentLoop->isUnloop()
+                              ? "<deleted>"
+                              : CurrentLoop->getHeader()->getName(),

                        ON_LOOP_MSG);
 
                        ON_LOOP_MSG);
 

-      if (skipThisLoop)
+      if (CurrentLoop->isUnloop())

         // Do not run other passes on this loop.
         break;
     }
         // Do not run other passes on this loop.
         break;
     }


@@ -262,11 +241,13 @@ bool LPPassManager::runOnFunction(Function &F) {
     // If the loop was deleted, release all the loop passes. This frees up
     // some memory, and avoids trouble with the pass manager trying to call
     // verifyAnalysis on them.
     // If the loop was deleted, release all the loop passes. This frees up
     // some memory, and avoids trouble with the pass manager trying to call
     // verifyAnalysis on them.

-    if (skipThisLoop)
+    if (CurrentLoop->isUnloop()) {

       for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
         Pass *P = getContainedPass(Index);
         freePass(P, "<deleted>", ON_LOOP_MSG);
       }
       for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
         Pass *P = getContainedPass(Index);
         freePass(P, "<deleted>", ON_LOOP_MSG);
       }

+      delete CurrentLoop;
+    }

 
     // Pop the loop from queue after running all passes.
     LQ.pop_back();
 
     // Pop the loop from queue after running all passes.
     LQ.pop_back();