Add a DominatorTree argument to isLCSSA so that it doesn't have to

compute a set of reachable blocks for itself each time it is called, which
is fairly frequently.

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

diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index f792a7fae3ee0ca5f6bc246ea9c8bce096eb1962..2babc25cb140a517c89dd315e4835f52342de387 100644 (file)
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -571,7 +571,7 @@ public:
   unsigned getSmallConstantTripMultiple() const;
 
   /// isLCSSAForm - Return true if the Loop is in LCSSA form
-  bool isLCSSAForm() const;
+  bool isLCSSAForm(DominatorTree &DT) const;
 
   /// isLoopSimplifyForm - Return true if the Loop is in the form that
   /// the LoopSimplify form transforms loops to, which is sometimes called

diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp
index 2139c29cc1f860097bb6a74b0fc7af3175351d5c..1001d2b5460395f56ad0ff594b1da6cf5f35d06b 100644 (file)
--- a/lib/Analysis/LoopInfo.cpp
+++ b/lib/Analysis/LoopInfo.cpp
@@ -263,14 +263,7 @@ unsigned Loop::getSmallConstantTripMultiple() const {
 }
 
 /// isLCSSAForm - Return true if the Loop is in LCSSA form
-bool Loop::isLCSSAForm() const {
-  // Collect all the reachable blocks in the function, for fast lookups.
-  SmallPtrSet<BasicBlock *, 32> ReachableBBs;
-  BasicBlock *EntryBB = getHeader()->getParent()->begin();
-  for (df_iterator<BasicBlock *> NI = df_begin(EntryBB),
-       NE = df_end(EntryBB); NI != NE; ++NI)
-    ReachableBBs.insert(*NI);
-
+bool Loop::isLCSSAForm(DominatorTree &DT) const {
   // Sort the blocks vector so that we can use binary search to do quick
   // lookups.
   SmallPtrSet<BasicBlock *, 16> LoopBBs(block_begin(), block_end());
@@ -290,7 +283,7 @@ bool Loop::isLCSSAForm() const {
         // entry are special; uses in them don't need to go through PHIs.
         if (UserBB != BB &&
             !LoopBBs.count(UserBB) &&
-            ReachableBBs.count(UserBB))
+            DT.isReachableFromEntry(UserBB))
           return false;
       }
   }

diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index cb563c3a7d03536560b3026220f40e4b6a5b31c4..838a3e74875cd9d69f3f696aab2c428126772fa5 100644 (file)
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -215,7 +215,7 @@ ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
 void IndVarSimplify::RewriteLoopExitValues(Loop *L,
                                            SCEVExpander &Rewriter) {
   // Verify the input to the pass in already in LCSSA form.
-  assert(L->isLCSSAForm());
+  assert(L->isLCSSAForm(*DT));
 
   SmallVector<BasicBlock*, 8> ExitBlocks;
   L->getUniqueExitBlocks(ExitBlocks);
@@ -445,7 +445,7 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
   // Clean up dead instructions.
   Changed |= DeleteDeadPHIs(L->getHeader());
   // Check a post-condition.
-  assert(L->isLCSSAForm() && "Indvars did not leave the loop in lcssa form!");
+  assert(L->isLCSSAForm(*DT) && "Indvars did not leave the loop in lcssa form!");
   return Changed;
 }
 

diff --git a/lib/Transforms/Scalar/LoopUnrollPass.cpp b/lib/Transforms/Scalar/LoopUnrollPass.cpp
index a355ec3a7e68ff0245db1407887cf86b2d00dde6..4ad41ae4b59f7572ed1370ee19ab43b4ec1c6394 100644 (file)
--- a/lib/Transforms/Scalar/LoopUnrollPass.cpp
+++ b/lib/Transforms/Scalar/LoopUnrollPass.cpp
@@ -86,7 +86,6 @@ static unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls) {
 }
 
 bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) {
-  assert(L->isLCSSAForm());
   LoopInfo *LI = &getAnalysis<LoopInfo>();
 
   BasicBlock *Header = L->getHeader();

diff --git a/lib/Transforms/Scalar/LoopUnswitch.cpp b/lib/Transforms/Scalar/LoopUnswitch.cpp
index 071e9b7c9e97ac8537e84bd611ee8b6837afca54..e3b809e35d4cc578ddcd461b24edc2cb95794055 100644 (file)
--- a/lib/Transforms/Scalar/LoopUnswitch.cpp
+++ b/lib/Transforms/Scalar/LoopUnswitch.cpp
@@ -206,7 +206,7 @@ bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
   Function *F = currentLoop->getHeader()->getParent();
   bool Changed = false;
   do {
-    assert(currentLoop->isLCSSAForm());
+    assert(currentLoop->isLCSSAForm(*DT));
     redoLoop = false;
     Changed |= processCurrentLoop();
   } while(redoLoop);

diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp
index 590d667a1aa317689e5a687378a8e238ec463c51..df6e603c0ba271b02f85daedcd3f14ebe7d4969b 100644 (file)
--- a/lib/Transforms/Utils/LCSSA.cpp
+++ b/lib/Transforms/Utils/LCSSA.cpp
@@ -88,7 +88,7 @@ namespace {
     /// verifyAnalysis() - Verify loop nest.
     virtual void verifyAnalysis() const {
       // Check the special guarantees that LCSSA makes.
-      assert(L->isLCSSAForm() && "LCSSA form not preserved!");
+      assert(L->isLCSSAForm(*DT) && "LCSSA form not preserved!");
     }
 
     /// inLoop - returns true if the given block is within the current loop
@@ -164,7 +164,7 @@ bool LCSSA::runOnLoop(Loop *TheLoop, LPPassManager &LPM) {
     }
   }
   
-  assert(L->isLCSSAForm());
+  assert(L->isLCSSAForm(*DT));
   PredCache.clear();
 
   return MadeChange;

diff --git a/lib/Transforms/Utils/LoopUnroll.cpp b/lib/Transforms/Utils/LoopUnroll.cpp
index e47c86d23b3d0123581f8279759b59d84f4bf480..ac59b4d7b3e8ec18dfcb9ffe7e86049424db5e0d 100644 (file)
--- a/lib/Transforms/Utils/LoopUnroll.cpp
+++ b/lib/Transforms/Utils/LoopUnroll.cpp
@@ -105,8 +105,6 @@ static BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI) {
 /// If a LoopPassManager is passed in, and the loop is fully removed, it will be
 /// removed from the LoopPassManager as well. LPM can also be NULL.
 bool llvm::UnrollLoop(Loop *L, unsigned Count, LoopInfo* LI, LPPassManager* LPM) {
-  assert(L->isLCSSAForm());
-
   BasicBlock *Preheader = L->getLoopPreheader();
   if (!Preheader) {
     DEBUG(dbgs() << "  Can't unroll; loop preheader-insertion failed.\n");
@@ -370,9 +368,5 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, LoopInfo* LI, LPPassManager* LPM)
   if (CompletelyUnroll && LPM != NULL)
     LPM->deleteLoopFromQueue(L);
 
-  // If we didn't completely unroll the loop, it should still be in LCSSA form.
-  if (!CompletelyUnroll)
-    assert(L->isLCSSAForm());
-
   return true;
 }