Index: llvm/trunk/include/llvm/Analysis/ScalarEvolution.h
===================================================================
--- llvm/trunk/include/llvm/Analysis/ScalarEvolution.h
+++ llvm/trunk/include/llvm/Analysis/ScalarEvolution.h
@@ -764,6 +764,12 @@
   /// loop bodies.
   void forgetLoop(const Loop *L);
 
+  // This method invokes forgetLoop for the outermost loop of the given loop
+  // \p L, making ScalarEvolution forget about all this subtree. This needs to
+  // be done whenever we make a transform that may affect the parameters of the
+  // outer loop, such as exit counts for branches.
+  void forgetTopmostLoop(const Loop *L);
+
   /// This method should be called by the client when it has changed a value
   /// in a way that may effect its value, or which may disconnect it from a
   /// def-use chain linking it to a loop.
Index: llvm/trunk/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/trunk/lib/Analysis/ScalarEvolution.cpp
+++ llvm/trunk/lib/Analysis/ScalarEvolution.cpp
@@ -6620,6 +6620,12 @@
   }
 }
 
+void ScalarEvolution::forgetTopmostLoop(const Loop *L) {
+  while (Loop *Parent = L->getParentLoop())
+    L = Parent;
+  forgetLoop(L);
+}
+
 void ScalarEvolution::forgetValue(Value *V) {
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I) return;
Index: llvm/trunk/lib/Transforms/Utils/LoopSimplify.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Utils/LoopSimplify.cpp
+++ llvm/trunk/lib/Transforms/Utils/LoopSimplify.cpp
@@ -510,10 +510,6 @@
           BI->setCondition(ConstantInt::get(Cond->getType(),
                                             !L->contains(BI->getSuccessor(0))));
 
-          // This may make the loop analyzable, force SCEV recomputation.
-          if (SE)
-            SE->forgetLoop(L);
-
           Changed = true;
         }
       }
@@ -651,13 +647,6 @@
       DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block "
                    << ExitingBlock->getName() << "\n");
 
-      // Notify ScalarEvolution before deleting this block. Currently assume the
-      // parent loop doesn't change (spliting edges doesn't count). If blocks,
-      // CFG edges, or other values in the parent loop change, then we need call
-      // to forgetLoop() for the parent instead.
-      if (SE)
-        SE->forgetLoop(L);
-
       assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock));
       Changed = true;
       LI->removeBlock(ExitingBlock);
@@ -679,6 +668,18 @@
     }
   }
 
+  // Changing exit conditions for blocks may affect exit counts of this loop and
+  // any of its paretns, so we must invalidate the entire subtree if we've made
+  // any changes.
+  if (Changed && SE)
+    SE->forgetTopmostLoop(L);
+
+#ifndef NDEBUG
+  // Make sure that after all our transforms SE is correct.
+  if (SE)
+    SE->verify();
+#endif
+
   return Changed;
 }
 
Index: llvm/trunk/test/Transforms/LoopSimplify/preserve-scev.ll
===================================================================
--- llvm/trunk/test/Transforms/LoopSimplify/preserve-scev.ll
+++ llvm/trunk/test/Transforms/LoopSimplify/preserve-scev.ll
@@ -95,7 +95,7 @@
 ; CHECK: Loop %while.cond191: max backedge-taken count is 0
 ; CHECK: Loop %while.cond191: Predicated backedge-taken count is 0
 ; CHECK: Loop %while.cond191.outer: <multiple exits> Unpredictable backedge-taken count.
-; CHECK: Loop %while.cond191.outer: Unpredictable max backedge-taken count.
+; CHECK: Loop %while.cond191.outer: max backedge-taken count is false
 ; CHECK: Loop %while.cond191.outer: Unpredictable predicated backedge-taken count.
 define void @mergeExit(i32 %MapAttrCount) nounwind uwtable ssp {
 entry: