Re-apply r80926, with fixes: keep the domtree informed of new blocks

that get created during loop unswitching, and fix SplitBlockPredecessors'
LCSSA updating code to create new PHIs instead of trying to just move
existing ones.

Also, optimize Loop::verifyLoop, since it gets called a lot. Use
searches on a sorted list of blocks instead of calling the "contains"
function, as is done in other places in the Loop class, since "contains"
does a linear search. Also, don't call verifyLoop from LoopSimplify or
LCSSA, as the PassManager is already calling verifyLoop as part of
LoopInfo's verifyAnalysis.

llvm-svn: 81221

1 files changed, 14 insertions, 3 deletions

diff --git a/llvm/lib/Transforms/Utils/LCSSA.cpp b/llvm/lib/Transforms/Utils/LCSSA.cpp
index 84fcc643bfb..b510262c05c 100644
--- a/llvm/lib/Transforms/Utils/LCSSA.cpp
+++ b/llvm/lib/Transforms/Utils/LCSSA.cpp
@@ -58,6 +58,7 @@ namespace {
     DominatorTree *DT;
     std::vector<BasicBlock*> LoopBlocks;
     PredIteratorCache PredCache;
+    Loop *L;
     
     virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
 
@@ -72,9 +73,9 @@ namespace {
       AU.setPreservesCFG();
       AU.addRequiredID(LoopSimplifyID);
       AU.addPreservedID(LoopSimplifyID);
-      AU.addRequired<LoopInfo>();
+      AU.addRequiredTransitive<LoopInfo>();
       AU.addPreserved<LoopInfo>();
-      AU.addRequired<DominatorTree>();
+      AU.addRequiredTransitive<DominatorTree>();
       AU.addPreserved<ScalarEvolution>();
       AU.addPreserved<DominatorTree>();
 
@@ -86,6 +87,15 @@ namespace {
       AU.addPreserved<DominanceFrontier>();
     }
   private:
+
+    /// verifyAnalysis() - Verify loop nest.
+    virtual void verifyAnalysis() const {
+#ifndef NDEBUG
+      // Check the special guarantees that LCSSA makes.
+      assert(L->isLCSSAForm());
+#endif
+    }
+
     void getLoopValuesUsedOutsideLoop(Loop *L,
                                       SetVector<Instruction*> &AffectedValues,
                                  const SmallVector<BasicBlock*, 8>& exitBlocks);
@@ -107,7 +117,8 @@ Pass *llvm::createLCSSAPass() { return new LCSSA(); }
 const PassInfo *const llvm::LCSSAID = &X;
 
 /// runOnFunction - Process all loops in the function, inner-most out.
-bool LCSSA::runOnLoop(Loop *L, LPPassManager &LPM) {
+bool LCSSA::runOnLoop(Loop *l, LPPassManager &LPM) {
+  L = l;
   PredCache.clear();
   
   LI = &LPM.getAnalysis<LoopInfo>();