Revert r80926. It causes loop unswitch assertion and slow down some JIT tests significantly.

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

11 files changed, 195 insertions, 287 deletions

diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index 1892bc7..b803176 100644
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -376,73 +376,11 @@ public:
   /// verifyLoop - Verify loop structure
   void verifyLoop() const {
 #ifndef NDEBUG
-    assert(!Blocks.empty() && "Loop header is missing");
-    assert(getHeader() && "Loop header is missing");
-
-    // Verify the individual blocks.
-    for (block_iterator I = block_begin(), E = block_end(); I != E; ++I) {
-      BlockT *BB = *I;
-      bool HasInsideLoopSuccs = false;
-      bool HasInsideLoopPreds = false;
-      SmallVector<BlockT *, 2> OutsideLoopPreds;
-
-      typedef GraphTraits<BlockT*> BlockTraits;
-      for (typename BlockTraits::ChildIteratorType SI =
-           BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB);
-           SI != SE; ++SI)
-        if (contains(*SI))
-          HasInsideLoopSuccs = true;
-      typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
-      for (typename InvBlockTraits::ChildIteratorType PI =
-           InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB);
-           PI != PE; ++PI) {
-        if (contains(*PI))
-          HasInsideLoopPreds = true;
-        else
-          OutsideLoopPreds.push_back(*PI);
-      }
-
-      if (BB == getHeader()) {
-        assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
-      } else if (!OutsideLoopPreds.empty()) {
-        // A non-header loop shouldn't be reachable from outside the loop,
-        // though it is permitted if the predecessor is not itself actually
-        // reachable.
-        BlockT *EntryBB = BB->getParent()->begin();
-        for (df_iterator<BlockT *> NI = df_begin(EntryBB),
-             NE = df_end(EntryBB); NI != NE; ++NI)
-          for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
-            assert(*NI != OutsideLoopPreds[i] &&
-                   "Loop has multiple entry points!");
-      }
-      assert(HasInsideLoopPreds && "Loop block has no in-loop predecessors!");
-      assert(HasInsideLoopSuccs && "Loop block has no in-loop successors!");
-      assert(BB != getHeader()->getParent()->begin() &&
-             "Loop contains function entry block!");
-    }
-
-    // Verify the subloops.
-    for (iterator I = begin(), E = end(); I != E; ++I) {
-      // Each block in each subloop should be contained within this loop.
-      for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
-           BI != BE; ++BI) {
-        assert(contains(*BI) &&
-               "Loop does not contain all the blocks of a subloop!");
-      }
-      // Recursively check the subloop.
+    assert (getHeader() && "Loop header is missing");
+    assert (getLoopPreheader() && "Loop preheader is missing");
+    assert (getLoopLatch() && "Loop latch is missing");
+    for (iterator I = SubLoops.begin(), E = SubLoops.end(); I != E; ++I)
       (*I)->verifyLoop();
-    }
-
-    // Verify the parent loop.
-    if (ParentLoop) {
-      bool FoundSelf = false;
-      for (iterator I = ParentLoop->begin(), E = ParentLoop->end(); I != E; ++I)
-        if (*I == this) {
-          FoundSelf = true;
-          break;
-        }
-      assert(FoundSelf && "Loop is not a subloop of its parent!");
-    }
 #endif
   }
 
@@ -935,8 +873,6 @@ public:
   ///
   virtual bool runOnFunction(Function &F);
 
-  virtual void verifyAnalysis() const;
-
   virtual void releaseMemory() { LI.releaseMemory(); }
 
   virtual void print(raw_ostream &O, const Module* M = 0) const;
diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h
index e766d72..95ffa46 100644
--- a/include/llvm/Transforms/Utils/BasicBlockUtils.h
+++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h
@@ -126,10 +126,10 @@ bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
 /// dest go to one block instead of each going to a different block, but isn't 
 /// the standard definition of a "critical edge".
 ///
-BasicBlock *SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
-                              Pass *P = 0, bool MergeIdenticalEdges = false);
+bool SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P = 0,
+                       bool MergeIdenticalEdges = false);
 
-inline BasicBlock *SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, Pass *P = 0) {
+inline bool SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, Pass *P = 0) {
   return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(), P);
 }
 
@@ -143,7 +143,7 @@ inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, Pass *P = 0) {
   TerminatorInst *TI = (*PI)->getTerminator();
   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
     if (TI->getSuccessor(i) == Succ)
-      MadeChange |= !!SplitCriticalEdge(TI, i, P);
+      MadeChange |= SplitCriticalEdge(TI, i, P);
   return MadeChange;
 }
 
@@ -151,9 +151,8 @@ inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, Pass *P = 0) {
 /// and return true, otherwise return false.  This method requires that there be
 /// an edge between the two blocks.  If P is specified, it updates the analyses
 /// described above.
-inline BasicBlock *SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst,
-                                     Pass *P = 0,
-                                     bool MergeIdenticalEdges = false) {
+inline bool SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, Pass *P = 0,
+                              bool MergeIdenticalEdges = false) {
   TerminatorInst *TI = Src->getTerminator();
   unsigned i = 0;
   while (1) {
@@ -181,12 +180,8 @@ BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P);
 /// Preds array, which has NumPreds elements in it.  The new block is given a
 /// suffix of 'Suffix'.  This function returns the new block.
 ///
-/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
-/// DominanceFrontier, LoopInfo, and LCCSA but no other analyses.
-/// In particular, it does not preserve LoopSimplify (because it's
-/// complicated to handle the case where one of the edges being split
-/// is an exit of a loop with other exits).
-///
+/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree and
+/// DominanceFrontier, but no other analyses.
 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, BasicBlock *const *Preds,
                                    unsigned NumPreds, const char *Suffix,
                                    Pass *P = 0);
diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp
index 10806eb..b240579 100644
--- a/lib/Analysis/LoopInfo.cpp
+++ b/lib/Analysis/LoopInfo.cpp
@@ -300,9 +300,6 @@ bool Loop::isLoopSimplifyForm() const {
 ///
 void
 Loop::getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const {
-  assert(isLoopSimplifyForm() &&
-         "getUniqueExitBlocks assumes the loop is in canonical form!");
-
   // Sort the blocks vector so that we can use binary search to do quick
   // lookups.
   SmallVector<BasicBlock *, 128> LoopBBs(block_begin(), block_end());
@@ -374,13 +371,6 @@ bool LoopInfo::runOnFunction(Function &) {
   return false;
 }
 
-void LoopInfo::verifyAnalysis() const {
-  for (iterator I = begin(), E = end(); I != E; ++I) {
-    assert(!(*I)->getParentLoop() && "Top-level loop has a parent!");
-    (*I)->verifyLoop();
-  }
-}
-
 void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequired<DominatorTree>();
diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp
index 1c29878..15bb9c7 100644
--- a/lib/Transforms/Scalar/LICM.cpp
+++ b/lib/Transforms/Scalar/LICM.cpp
@@ -91,7 +91,6 @@ namespace {
       AU.addRequired<AliasAnalysis>();
       AU.addPreserved<ScalarEvolution>();
       AU.addPreserved<DominanceFrontier>();
-      AU.addPreservedID(LoopSimplifyID);
     }
 
     bool doFinalization() {
diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
index 82eb14f..0bf62ec 100644
--- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -484,37 +484,36 @@ void BasedUser::RewriteInstructionToUseNewBase(const SCEV *const &NewBase,
       // loop because multiple copies sometimes do useful sinking of code in
       // that case(?).
       Instruction *OldLoc = dyn_cast<Instruction>(OperandValToReplace);
-      BasicBlock *PHIPred = PN->getIncomingBlock(i);
       if (L->contains(OldLoc->getParent())) {
         // If this is a critical edge, split the edge so that we do not insert
         // the code on all predecessor/successor paths.  We do this unless this
         // is the canonical backedge for this loop, as this can make some
         // inserted code be in an illegal position.
+        BasicBlock *PHIPred = PN->getIncomingBlock(i);
         if (e != 1 && PHIPred->getTerminator()->getNumSuccessors() > 1 &&
             (PN->getParent() != L->getHeader() || !L->contains(PHIPred))) {
 
           // First step, split the critical edge.
-          BasicBlock *NewBB = SplitCriticalEdge(PHIPred, PN->getParent(),
-                                                P, false);
+          SplitCriticalEdge(PHIPred, PN->getParent(), P, false);
 
           // Next step: move the basic block.  In particular, if the PHI node
           // is outside of the loop, and PredTI is in the loop, we want to
           // move the block to be immediately before the PHI block, not
           // immediately after PredTI.
-          if (L->contains(PHIPred) && !L->contains(PN->getParent()))
+          if (L->contains(PHIPred) && !L->contains(PN->getParent())) {
+            BasicBlock *NewBB = PN->getIncomingBlock(i);
             NewBB->moveBefore(PN->getParent());
+          }
 
           // Splitting the edge can reduce the number of PHI entries we have.
           e = PN->getNumIncomingValues();
-          PHIPred = NewBB;
-          i = PN->getBasicBlockIndex(PHIPred);
         }
       }
-      Value *&Code = InsertedCode[PHIPred];
+      Value *&Code = InsertedCode[PN->getIncomingBlock(i)];
       if (!Code) {
         // Insert the code into the end of the predecessor block.
         Instruction *InsertPt = (L->contains(OldLoc->getParent())) ?
-                                PHIPred->getTerminator() :
+                                PN->getIncomingBlock(i)->getTerminator() :
                                 OldLoc->getParent()->getTerminator();
         Code = InsertCodeForBaseAtPosition(NewBase, PN->getType(),
                                            Rewriter, InsertPt, L, LI);
diff --git a/lib/Transforms/Scalar/LoopUnswitch.cpp b/lib/Transforms/Scalar/LoopUnswitch.cpp
index b49e14a..8e7c91a 100644
--- a/lib/Transforms/Scalar/LoopUnswitch.cpp
+++ b/lib/Transforms/Scalar/LoopUnswitch.cpp
@@ -518,12 +518,7 @@ void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
     std::swap(TrueDest, FalseDest);
 
   // Insert the new branch.
-  BranchInst *BI = BranchInst::Create(TrueDest, FalseDest, BranchVal, InsertPt);
-
-  // If either edge is critical, split it. This helps preserve LoopSimplify
-  // form for enclosing loops.
-  SplitCriticalEdge(BI, 0, this);
-  SplitCriticalEdge(BI, 1, this);
+  BranchInst::Create(TrueDest, FalseDest, BranchVal, InsertPt);
 }
 
 /// UnswitchTrivialCondition - Given a loop that has a trivial unswitchable
@@ -580,11 +575,47 @@ void LoopUnswitch::SplitExitEdges(Loop *L,
 
   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
     BasicBlock *ExitBlock = ExitBlocks[i];
-    SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock),
-                                       pred_end(ExitBlock));
-    SplitBlockPredecessors(ExitBlock, Preds.data(), Preds.size(),
-                           ".us-lcssa", this);
+    std::vector<BasicBlock*> Preds(pred_begin(ExitBlock), pred_end(ExitBlock));
+
+    for (unsigned j = 0, e = Preds.size(); j != e; ++j) {
+      BasicBlock* NewExitBlock = SplitEdge(Preds[j], ExitBlock, this);
+      BasicBlock* StartBlock = Preds[j];
+      BasicBlock* EndBlock;
+      if (NewExitBlock->getSinglePredecessor() == ExitBlock) {
+        EndBlock = NewExitBlock;
+        NewExitBlock = EndBlock->getSinglePredecessor();
+      } else {
+        EndBlock = ExitBlock;
+      }
+      
+      std::set<PHINode*> InsertedPHIs;
+      PHINode* OldLCSSA = 0;
+      for (BasicBlock::iterator I = EndBlock->begin();
+           (OldLCSSA = dyn_cast<PHINode>(I)); ++I) {
+        Value* OldValue = OldLCSSA->getIncomingValueForBlock(NewExitBlock);
+        PHINode* NewLCSSA = PHINode::Create(OldLCSSA->getType(),
+                                            OldLCSSA->getName() + ".us-lcssa",
+                                            NewExitBlock->getTerminator());
+        NewLCSSA->addIncoming(OldValue, StartBlock);
+        OldLCSSA->setIncomingValue(OldLCSSA->getBasicBlockIndex(NewExitBlock),
+                                   NewLCSSA);
+        InsertedPHIs.insert(NewLCSSA);
+      }
+
+      BasicBlock::iterator InsertPt = EndBlock->getFirstNonPHI();
+      for (BasicBlock::iterator I = NewExitBlock->begin();
+         (OldLCSSA = dyn_cast<PHINode>(I)) && InsertedPHIs.count(OldLCSSA) == 0;
+         ++I) {
+        PHINode *NewLCSSA = PHINode::Create(OldLCSSA->getType(),
+                                            OldLCSSA->getName() + ".us-lcssa",
+                                            InsertPt);
+        OldLCSSA->replaceAllUsesWith(NewLCSSA);
+        NewLCSSA->addIncoming(OldLCSSA, NewExitBlock);
+      }
+
+    }    
   }
+
 }
 
 /// UnswitchNontrivialCondition - We determined that the loop is profitable 
@@ -914,29 +945,27 @@ void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
               // FIXME: This is a hack.  We need to keep the successor around
               // and hooked up so as to preserve the loop structure, because
               // trying to update it is complicated.  So instead we preserve the
-              // loop structure and put the block on a dead code path.
-              BasicBlock *Switch = SI->getParent();
-              SplitEdge(Switch, SI->getSuccessor(i), this);
-              // Compute the successors instead of relying on the return value
-              // of SplitEdge, since it may have split the switch successor
-              // after PHI nodes.
-              BasicBlock *NewSISucc = SI->getSuccessor(i);
-              BasicBlock *OldSISucc = *succ_begin(NewSISucc);
-              // Create an "unreachable" destination.
-              BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable",
-                                                     Switch->getParent(),
-                                                     OldSISucc);
-              new UnreachableInst(Context, Abort);
-              // Force the new case destination to branch to the "unreachable"
-              // block while maintaining a (dead) CFG edge to the old block.
-              NewSISucc->getTerminator()->eraseFromParent();
-              BranchInst::Create(Abort, OldSISucc,
-                                 ConstantInt::getTrue(Context), NewSISucc);
-              // Release the PHI operands for this edge.
-              for (BasicBlock::iterator II = NewSISucc->begin();
-                   PHINode *PN = dyn_cast<PHINode>(II); ++II)
-                PN->setIncomingValue(PN->getBasicBlockIndex(Switch),
-                                     UndefValue::get(PN->getType()));
+              // loop structure and put the block on an dead code path.
+              
+              BasicBlock *SISucc = SI->getSuccessor(i);
+              BasicBlock* Old = SI->getParent();
+              BasicBlock* Split = SplitBlock(Old, SI, this);
+              
+              Instruction* OldTerm = Old->getTerminator();
+              BranchInst::Create(Split, SISucc,
+                                 ConstantInt::getTrue(Context), OldTerm);
+
+              LPM->deleteSimpleAnalysisValue(Old->getTerminator(), L);
+              Old->getTerminator()->eraseFromParent();
+              
+              PHINode *PN;
+              for (BasicBlock::iterator II = SISucc->begin();
+                   (PN = dyn_cast<PHINode>(II)); ++II) {
+                Value *InVal = PN->removeIncomingValue(Split, false);
+                PN->addIncoming(InVal, Old);
+              }
+
+              SI->removeCase(i);
               break;
             }
           }
diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp
index 736d26e..c165e04 100644
--- a/lib/Transforms/Utils/BasicBlockUtils.cpp
+++ b/lib/Transforms/Utils/BasicBlockUtils.cpp
@@ -24,7 +24,6 @@
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Target/TargetData.h"
 #include "llvm/Transforms/Utils/Local.h"
-#include "llvm/Transforms/Scalar.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/ValueHandle.h"
 #include <algorithm>
@@ -320,8 +319,7 @@ BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) {
     ++SplitIt;
   BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split");
 
-  // The new block lives in whichever loop the old one did. This preserves
-  // LCSSA as well, because we force the split point to be after any PHI nodes.
+  // The new block lives in whichever loop the old one did.
   if (LoopInfo* LI = P->getAnalysisIfAvailable<LoopInfo>())
     if (Loop *L = LI->getLoopFor(Old))
       L->addBasicBlockToLoop(New, LI->getBase());
@@ -355,12 +353,8 @@ BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) {
 /// Preds array, which has NumPreds elements in it.  The new block is given a
 /// suffix of 'Suffix'.
 ///
-/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
-/// DominanceFrontier, LoopInfo, and LCCSA but no other analyses.
-/// In particular, it does not preserve LoopSimplify (because it's
-/// complicated to handle the case where one of the edges being split
-/// is an exit of a loop with other exits).
-///
+/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree and
+/// DominanceFrontier, but no other analyses.
 BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, 
                                          BasicBlock *const *Preds,
                                          unsigned NumPreds, const char *Suffix,
@@ -372,44 +366,19 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
   // The new block unconditionally branches to the old block.
   BranchInst *BI = BranchInst::Create(BB, NewBB);
   
-  LoopInfo *LI = P ? P->getAnalysisIfAvailable<LoopInfo>() : 0;
-  Loop *L = LI ? LI->getLoopFor(BB) : 0;
-  bool PreserveLCSSA = P->mustPreserveAnalysisID(LCSSAID);
-
   // Move the edges from Preds to point to NewBB instead of BB.
-  // While here, if we need to preserve loop analyses, collect
-  // some information about how this split will affect loops.
-  bool HasLoopExit = false;
-  bool IsLoopEntry = !!L;
-  bool SplitMakesNewLoopHeader = false;
-  for (unsigned i = 0; i != NumPreds; ++i) {
+  for (unsigned i = 0; i != NumPreds; ++i)
     Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB);
-
-    if (LI) {
-      // If we need to preserve LCSSA, determine if any of
-      // the preds is a loop exit.
-      if (PreserveLCSSA)
-        if (Loop *PL = LI->getLoopFor(Preds[i]))
-          if (!PL->contains(BB))
-            HasLoopExit = true;
-      // If we need to preserve LoopInfo, note whether any of the
-      // preds crosses an interesting loop boundary.
-      if (L) {
-        if (L->contains(Preds[i]))
-          IsLoopEntry = false;
-        else
-          SplitMakesNewLoopHeader = true;
-      }
-    }
-  }
-
+  
   // Update dominator tree and dominator frontier if available.
   DominatorTree *DT = P ? P->getAnalysisIfAvailable<DominatorTree>() : 0;
   if (DT)
     DT->splitBlock(NewBB);
   if (DominanceFrontier *DF = P ? P->getAnalysisIfAvailable<DominanceFrontier>():0)
     DF->splitBlock(NewBB);
-
+  AliasAnalysis *AA = P ? P->getAnalysisIfAvailable<AliasAnalysis>() : 0;
+  
+  
   // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
   // node becomes an incoming value for BB's phi node.  However, if the Preds
   // list is empty, we need to insert dummy entries into the PHI nodes in BB to
@@ -420,42 +389,20 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
       cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
     return NewBB;
   }
-
-  AliasAnalysis *AA = P ? P->getAnalysisIfAvailable<AliasAnalysis>() : 0;
-
-  if (L) {
-    if (IsLoopEntry) {
-      if (Loop *PredLoop = LI->getLoopFor(Preds[0])) {
-        // Add the new block to the nearest enclosing loop (and not an
-        // adjacent loop).
-        while (PredLoop && !PredLoop->contains(BB))
-          PredLoop = PredLoop->getParentLoop();
-        if (PredLoop)
-          PredLoop->addBasicBlockToLoop(NewBB, LI->getBase());
-      }
-    } else {
-      L->addBasicBlockToLoop(NewBB, LI->getBase());
-      if (SplitMakesNewLoopHeader)
-        L->moveToHeader(NewBB);
-    }
-  }
   
   // Otherwise, create a new PHI node in NewBB for each PHI node in BB.
   for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ) {
     PHINode *PN = cast<PHINode>(I++);
     
     // Check to see if all of the values coming in are the same.  If so, we
-    // don't need to create a new PHI node, unless it's needed for LCSSA.
-    Value *InVal = 0;
-    if (!HasLoopExit) {
-      InVal = PN->getIncomingValueForBlock(Preds[0]);
-      for (unsigned i = 1; i != NumPreds; ++i)
-        if (InVal != PN->getIncomingValueForBlock(Preds[i])) {
-          InVal = 0;
-          break;
-        }
-    }
-
+    // don't need to create a new PHI node.
+    Value *InVal = PN->getIncomingValueForBlock(Preds[0]);
+    for (unsigned i = 1; i != NumPreds; ++i)
+      if (InVal != PN->getIncomingValueForBlock(Preds[i])) {
+        InVal = 0;
+        break;
+      }
+    
     if (InVal) {
       // If all incoming values for the new PHI would be the same, just don't
       // make a new PHI.  Instead, just remove the incoming values from the old
@@ -480,6 +427,13 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
     // Add an incoming value to the PHI node in the loop for the preheader
     // edge.
     PN->addIncoming(InVal, NewBB);
+    
+    // Check to see if we can eliminate this phi node.
+    if (Value *V = PN->hasConstantValue(DT)) {
+      PN->replaceAllUsesWith(V);
+      if (AA) AA->deleteValue(PN);
+      PN->eraseFromParent();
+    }
   }
   
   return NewBB;
diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp
index f5a1366..632aa2b 100644
--- a/lib/Transforms/Utils/BreakCriticalEdges.cpp
+++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp
@@ -122,9 +122,9 @@ bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
 /// false otherwise.  This ensures that all edges to that dest go to one block
 /// instead of each going to a different block.
 //
-BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
-                                    Pass *P, bool MergeIdenticalEdges) {
-  if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return 0;
+bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P,
+                             bool MergeIdenticalEdges) {
+  if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return false;
   BasicBlock *TIBB = TI->getParent();
   BasicBlock *DestBB = TI->getSuccessor(SuccNum);
 
@@ -172,7 +172,7 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
   
 
   // If we don't have a pass object, we can't update anything...
-  if (P == 0) return NewBB;
+  if (P == 0) return true;
 
   // Now update analysis information.  Since the only predecessor of NewBB is
   // the TIBB, TIBB clearly dominates NewBB.  TIBB usually doesn't dominate
@@ -254,9 +254,9 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
   
   // Update LoopInfo if it is around.
   if (LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>()) {
-    if (Loop *TIL = LI->getLoopFor(TIBB)) {
-      // If one or the other blocks were not in a loop, the new block is not
-      // either, and thus LI doesn't need to be updated.
+    // If one or the other blocks were not in a loop, the new block is not
+    // either, and thus LI doesn't need to be updated.
+    if (Loop *TIL = LI->getLoopFor(TIBB))
       if (Loop *DestLoop = LI->getLoopFor(DestBB)) {
         if (TIL == DestLoop) {
           // Both in the same loop, the NewBB joins loop.
@@ -278,55 +278,6 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
             P->addBasicBlockToLoop(NewBB, LI->getBase());
         }
       }
-      // If TIBB is in a loop and DestBB is outside of that loop, split the
-      // other exit blocks of the loop that also have predecessors outside
-      // the loop, to maintain a LoopSimplify guarantee.
-      if (!TIL->contains(DestBB) &&
-          P->mustPreserveAnalysisID(LoopSimplifyID)) {
-        // For each unique exit block...
-        SmallVector<BasicBlock *, 4> ExitBlocks;
-        TIL->getExitBlocks(ExitBlocks);
-        for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
-          // Collect all the preds that are inside the loop, and note
-          // whether there are any preds outside the loop.
-          SmallVector<BasicBlock *, 4> Preds;
-          bool AllPredsInLoop = false;
-          BasicBlock *Exit = ExitBlocks[i];
-          for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit);
-               I != E; ++I)
-            if (TIL->contains(*I))
-              Preds.push_back(*I);
-            else
-              AllPredsInLoop = true;
-          // If there are any preds not in the loop, we'll need to split
-          // the edges. The Preds.empty() check is needed because a block
-          // may appear multiple times in the list. We can't use
-          // getUniqueExitBlocks above because that depends on LoopSimplify
-          // form, which we're in the process of restoring!
-          if (Preds.empty() || !AllPredsInLoop) continue;
-          BasicBlock *NewBB = SplitBlockPredecessors(Exit,
-                                                     Preds.data(), Preds.size(),
-                                                     "split", P);
-          // Update LCSSA form. This is fairly simple in LoopSimplify form:
-          // just move the existing LCSSA-mandated PHI nodes from the old exit
-          // block to the new one.
-          if (P->mustPreserveAnalysisID(LCSSAID))
-            for (BasicBlock::iterator I = Exit->begin();
-                 PHINode *PN = dyn_cast<PHINode>(I); ++I)
-              PN->moveBefore(NewBB->getTerminator());
-        }
-      }
-      // LCSSA form was updated above for the case where LoopSimplify is
-      // available, which means that all predecessors of loop exit blocks
-      // are within the loop. Without LoopSimplify form, it would be
-      // necessary to insert a new phi.
-      assert((!P->mustPreserveAnalysisID(LCSSAID) ||
-              P->mustPreserveAnalysisID(LoopSimplifyID)) &&
-             "SplitCriticalEdge doesn't know how to update LCCSA form "
-             "without LoopSimplify!");
-    }
-
   }
-
-  return NewBB;
+  return true;
 }
diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp
index e0251f8..84fcc64 100644
--- a/lib/Transforms/Utils/LCSSA.cpp
+++ b/lib/Transforms/Utils/LCSSA.cpp
@@ -58,7 +58,6 @@ namespace {
     DominatorTree *DT;
     std::vector<BasicBlock*> LoopBlocks;
     PredIteratorCache PredCache;
-    Loop *L;
     
     virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
 
@@ -73,9 +72,9 @@ namespace {
       AU.setPreservesCFG();
       AU.addRequiredID(LoopSimplifyID);
       AU.addPreservedID(LoopSimplifyID);
-      AU.addRequiredTransitive<LoopInfo>();
+      AU.addRequired<LoopInfo>();
       AU.addPreserved<LoopInfo>();
-      AU.addRequiredTransitive<DominatorTree>();
+      AU.addRequired<DominatorTree>();
       AU.addPreserved<ScalarEvolution>();
       AU.addPreserved<DominatorTree>();
 
@@ -87,17 +86,6 @@ namespace {
       AU.addPreserved<DominanceFrontier>();
     }
   private:
-
-    /// verifyAnalysis() - Verify loop nest.
-    virtual void verifyAnalysis() const {
-#ifndef NDEBUG
-      // Sanity check: Check basic loop invariants.
-      L->verifyLoop();
-      // Check the special guarantees that LCSSA makes.
-      assert(L->isLCSSAForm());
-#endif
-    }
-
     void getLoopValuesUsedOutsideLoop(Loop *L,
                                       SetVector<Instruction*> &AffectedValues,
                                  const SmallVector<BasicBlock*, 8>& exitBlocks);
@@ -119,8 +107,7 @@ 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) {
-  L = l;
+bool LCSSA::runOnLoop(Loop *L, LPPassManager &LPM) {
   PredCache.clear();
   
   LI = &LPM.getAnalysis<LoopInfo>();
diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index 36709f7..56e5a46 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -69,8 +69,8 @@ namespace {
 
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       // We need loop information to identify the loops...
-      AU.addRequiredTransitive<LoopInfo>();
-      AU.addRequiredTransitive<DominatorTree>();
+      AU.addRequired<LoopInfo>();
+      AU.addRequired<DominatorTree>();
 
       AU.addPreserved<LoopInfo>();
       AU.addPreserved<DominatorTree>();
@@ -83,13 +83,9 @@ namespace {
     void verifyAnalysis() const {
 #ifndef NDEBUG
       LoopInfo *NLI = &getAnalysis<LoopInfo>();
-      for (LoopInfo::iterator I = NLI->begin(), E = NLI->end(); I != E; ++I) {
-        // Sanity check: Check basic loop invariants.
+      for (LoopInfo::iterator I = NLI->begin(), E = NLI->end(); I != E; ++I) 
         (*I)->verifyLoop();
-        // Check the special guarantees that LoopSimplify makes.
-        assert((*I)->isLoopSimplifyForm());
-      }
-#endif
+#endif  
     }
 
   private:
@@ -350,6 +346,15 @@ BasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) {
   BasicBlock *NewBB =
     SplitBlockPredecessors(Header, &OutsideBlocks[0], OutsideBlocks.size(),
                            ".preheader", this);
+  
+
+  //===--------------------------------------------------------------------===//
+  //  Update analysis results now that we have performed the transformation
+  //
+
+  // We know that we have loop information to update... update it now.
+  if (Loop *Parent = L->getParentLoop())
+    Parent->addBasicBlockToLoop(NewBB, LI->getBase());
 
   // Make sure that NewBB is put someplace intelligent, which doesn't mess up
   // code layout too horribly.
@@ -372,6 +377,17 @@ BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) {
                                              LoopBlocks.size(), ".loopexit",
                                              this);
 
+  // Update Loop Information - we know that the new block will be in whichever
+  // loop the Exit block is in.  Note that it may not be in that immediate loop,
+  // if the successor is some other loop header.  In that case, we continue 
+  // walking up the loop tree to find a loop that contains both the successor
+  // block and the predecessor block.
+  Loop *SuccLoop = LI->getLoopFor(Exit);
+  while (SuccLoop && !SuccLoop->contains(L->getHeader()))
+    SuccLoop = SuccLoop->getParentLoop();
+  if (SuccLoop)
+    SuccLoop->addBasicBlockToLoop(NewBB, LI->getBase());
+
   return NewBB;
 }
 
@@ -505,6 +521,10 @@ Loop *LoopSimplify::SeparateNestedLoop(Loop *L) {
   else
     LI->changeTopLevelLoop(L, NewOuter);
 
+  // This block is going to be our new header block: add it to this loop and all
+  // parent loops.
+  NewOuter->addBasicBlockToLoop(NewBB, LI->getBase());
+
   // L is now a subloop of our outer loop.
   NewOuter->addChildLoop(L);
 
@@ -512,10 +532,6 @@ Loop *LoopSimplify::SeparateNestedLoop(Loop *L) {
        I != E; ++I)
     NewOuter->addBlockEntry(*I);
 
-  // Now reset the header in L, which had been moved by
-  // SplitBlockPredecessors for the outer loop.
-  L->moveToHeader(Header);
-
   // Determine which blocks should stay in L and which should be moved out to
   // the Outer loop now.
   std::set<BasicBlock*> BlocksInL;
diff --git a/test/Transforms/LoopUnswitch/2009-09-05-DomAssert.ll b/test/Transforms/LoopUnswitch/2009-09-05-DomAssert.ll
new file mode 100644
index 0000000..0258085
--- /dev/null
+++ b/test/Transforms/LoopUnswitch/2009-09-05-DomAssert.ll
@@ -0,0 +1,52 @@
+; RUN: llvm-as < %s | opt -loop-unswitch -disable-output 
+; rdar://7197574
+
+target datalayout = "e-p:32:32:32-i1:8:32-i8:8:32-i16:16:32-i32:32:32-i64:32:32-f32:32:32-f64:32:32-v64:64:64-v128:128:128-a0:0:32"
+target triple = "thumbv7-apple-darwin9"
+	%struct.frame = type { i16*, i16*, i16* }
+
+declare arm_apcscc i32 @ercCollect8PredBlocks(i32* nocapture, i32, i32, i32* nocapture, i32, i32, i32, i8 zeroext) nounwind
+
+define arm_apcscc void @concealBlocks(i32 %lastColumn, i32 %lastRow, i32 %comp, %struct.frame* nocapture %recfr, i32 %picSizeX, i32* nocapture %condition) nounwind {
+entry:
+	br i1 undef, label %bb.nph12, label %return
+
+bb28:		; preds = %bb.nph12
+	unreachable
+
+bb42:		; preds = %bb.nph12
+	br label %bb43
+
+bb43:		; preds = %bb61, %bb42
+	%0 = call arm_apcscc  i32 @ercCollect8PredBlocks(i32* undef, i32 undef, i32 0, i32* %condition, i32 %lastRow, i32 %lastColumn, i32 undef, i8 zeroext 1) nounwind		; <i32> [#uses=0]
+	switch i32 %comp, label %bb58 [
+		i32 0, label %bb52
+		i32 1, label %bb54
+		i32 2, label %bb56
+	]
+
+bb52:		; preds = %bb43
+	br label %bb58
+
+bb54:		; preds = %bb43
+	br label %bb58
+
+bb56:		; preds = %bb43
+	unreachable
+
+bb58:		; preds = %bb54, %bb52, %bb43
+	br i1 %1, label %bb59, label %bb61
+
+bb59:		; preds = %bb58
+	br label %bb61
+
+bb61:		; preds = %bb59, %bb58
+	br label %bb43
+
+bb.nph12:		; preds = %entry
+	%1 = icmp eq i32 %comp, 0		; <i1> [#uses=1]
+	br i1 undef, label %bb28, label %bb42
+
+return:		; preds = %entry
+	ret void
+}