Index: polly/trunk/include/polly/ScopInfo.h
===================================================================
--- polly/trunk/include/polly/ScopInfo.h
+++ polly/trunk/include/polly/ScopInfo.h
@@ -3044,6 +3044,13 @@
   /// A map of Region to its Scop object containing
   ///        Polly IR of static control part.
   RegionToScopMapTy RegionToScopMap;
+  const DataLayout &DL;
+  ScopDetection &SD;
+  ScalarEvolution &SE;
+  LoopInfo &LI;
+  AliasAnalysis &AA;
+  DominatorTree &DT;
+  AssumptionCache ∾
 
 public:
   ScopInfo(const DataLayout &DL, ScopDetection &SD, ScalarEvolution &SE,
@@ -3063,6 +3070,15 @@
     return nullptr;
   }
 
+  /// Recompute the Scop-Information for a function.
+  ///
+  /// This invalidates any iterators.
+  void recompute();
+
+  /// Handle invalidation explicitly
+  bool invalidate(Function &F, const PreservedAnalyses &PA,
+                  FunctionAnalysisManager::Invalidator &Inv);
+
   iterator begin() { return RegionToScopMap.begin(); }
   iterator end() { return RegionToScopMap.end(); }
   const_iterator begin() const { return RegionToScopMap.begin(); }
Index: polly/trunk/include/polly/ScopPass.h
===================================================================
--- polly/trunk/include/polly/ScopPass.h
+++ polly/trunk/include/polly/ScopPass.h
@@ -180,18 +180,26 @@
 
 class SPMUpdater {
 public:
-  SPMUpdater(SmallPriorityWorklist<Scop *, 4> &Worklist,
+  SPMUpdater(SmallPriorityWorklist<Region *, 4> &Worklist,
              ScopAnalysisManager &SAM)
-      : Worklist(Worklist), SAM(SAM) {}
+      : Worklist(Worklist), SAM(SAM), InvalidateCurrentScop(false) {}
 
-  void SkipScop(Scop &S) {
-    if (Worklist.erase(&S))
-      SAM.clear(S);
+  bool invalidateCurrentScop() const { return InvalidateCurrentScop; }
+
+  void invalidateScop(Scop &S) {
+    if (&S == CurrentScop)
+      InvalidateCurrentScop = true;
+
+    Worklist.erase(&S.getRegion());
+    SAM.clear(S);
   }
 
 private:
-  SmallPriorityWorklist<Scop *, 4> &Worklist;
+  Scop *CurrentScop;
+  bool InvalidateCurrentScop;
+  SmallPriorityWorklist<Region *, 4> &Worklist;
   ScopAnalysisManager &SAM;
+  template <typename ScopPassT> friend class FunctionToScopPassAdaptor;
 };
 
 template <typename ScopPassT>
@@ -202,10 +210,16 @@
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
     PreservedAnalyses PA = PreservedAnalyses::all();
-    auto &Scops = AM.getResult<ScopInfoAnalysis>(F);
-    if (Scops.empty())
+    auto &SD = AM.getResult<ScopAnalysis>(F);
+    auto &SI = AM.getResult<ScopInfoAnalysis>(F);
+    if (SI.empty())
       return PA;
 
+    SmallPriorityWorklist<Region *, 4> Worklist;
+    for (auto &S : SI)
+      if (S.second)
+        Worklist.insert(S.first);
+
     ScopStandardAnalysisResults AR = {AM.getResult<DominatorTreeAnalysis>(F),
                                       AM.getResult<ScopInfoAnalysis>(F),
                                       AM.getResult<ScalarEvolutionAnalysis>(F),
@@ -215,19 +229,23 @@
     ScopAnalysisManager &SAM =
         AM.getResult<ScopAnalysisManagerFunctionProxy>(F).getManager();
 
-    SmallPriorityWorklist<Scop *, 4> Worklist;
     SPMUpdater Updater{Worklist, SAM};
 
-    for (auto &S : Scops)
-      if (auto *scop = S.second.get())
-        Worklist.insert(scop);
-
     while (!Worklist.empty()) {
-      Scop *scop = Worklist.pop_back_val();
+      Region *R = Worklist.pop_back_val();
+      if (!SD.isMaxRegionInScop(*R))
+        continue;
+      Scop *scop = SI.getScop(R);
+      if (!scop)
+        continue;
+      Updater.CurrentScop = scop;
+      Updater.InvalidateCurrentScop = false;
       PreservedAnalyses PassPA = Pass.run(*scop, SAM, AR, Updater);
 
       SAM.invalidate(*scop, PassPA);
       PA.intersect(std::move(PassPA));
+      if (Updater.invalidateCurrentScop())
+        SI.recompute();
     };
 
     PA.preserveSet<AllAnalysesOn<Scop>>();
Index: polly/trunk/lib/Analysis/ScopInfo.cpp
===================================================================
--- polly/trunk/lib/Analysis/ScopInfo.cpp
+++ polly/trunk/lib/Analysis/ScopInfo.cpp
@@ -5227,7 +5227,13 @@
 //===----------------------------------------------------------------------===//
 ScopInfo::ScopInfo(const DataLayout &DL, ScopDetection &SD, ScalarEvolution &SE,
                    LoopInfo &LI, AliasAnalysis &AA, DominatorTree &DT,
-                   AssumptionCache &AC) {
+                   AssumptionCache &AC)
+    : DL(DL), SD(SD), SE(SE), LI(LI), AA(AA), DT(DT), AC(AC) {
+  recompute();
+}
+
+void ScopInfo::recompute() {
+  RegionToScopMap.clear();
   /// Create polyhedral description of scops for all the valid regions of a
   /// function.
   for (auto &It : SD) {
@@ -5248,6 +5254,20 @@
   }
 }
 
+bool ScopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
+                          FunctionAnalysisManager::Invalidator &Inv) {
+  // Check whether the analysis, all analyses on functions have been preserved
+  // or anything we're holding references to is being invalidated
+  auto PAC = PA.getChecker<ScopInfoAnalysis>();
+  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
+         Inv.invalidate<ScopAnalysis>(F, PA) ||
+         Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
+         Inv.invalidate<LoopAnalysis>(F, PA) ||
+         Inv.invalidate<AAManager>(F, PA) ||
+         Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||
+         Inv.invalidate<AssumptionAnalysis>(F, PA);
+}
+
 AnalysisKey ScopInfoAnalysis::Key;
 
 ScopInfoAnalysis::Result ScopInfoAnalysis::run(Function &F,
Index: polly/trunk/lib/Analysis/ScopPass.cpp
===================================================================
--- polly/trunk/lib/Analysis/ScopPass.cpp
+++ polly/trunk/lib/Analysis/ScopPass.cpp
@@ -79,11 +79,11 @@
 
   // First, check whether our ScopInfo is about to be invalidated
   auto PAC = PA.getChecker<ScopAnalysisManagerFunctionProxy>();
-  if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
-        Inv.invalidate<ScopInfoAnalysis>(F, PA) ||
-        Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
-        Inv.invalidate<LoopAnalysis>(F, PA) ||
-        Inv.invalidate<DominatorTreeAnalysis>(F, PA))) {
+  if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
+      Inv.invalidate<ScopInfoAnalysis>(F, PA) ||
+      Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
+      Inv.invalidate<LoopAnalysis>(F, PA) ||
+      Inv.invalidate<DominatorTreeAnalysis>(F, PA)) {
 
     // As everything depends on ScopInfo, we must drop all existing results
     for (auto &S : *SI)
Index: polly/trunk/lib/CodeGen/CodeGeneration.cpp
===================================================================
--- polly/trunk/lib/CodeGen/CodeGeneration.cpp
+++ polly/trunk/lib/CodeGen/CodeGeneration.cpp
@@ -328,8 +328,10 @@
 polly::CodeGenerationPass::run(Scop &S, ScopAnalysisManager &SAM,
                                ScopStandardAnalysisResults &AR, SPMUpdater &U) {
   auto &AI = SAM.getResult<IslAstAnalysis>(S, AR);
-  if (CodeGen(S, AI, AR.LI, AR.DT, AR.SE, AR.RI))
+  if (CodeGen(S, AI, AR.LI, AR.DT, AR.SE, AR.RI)) {
+    U.invalidateScop(S);
     return PreservedAnalyses::none();
+  }
 
   return PreservedAnalyses::all();
 }