diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index fbcbe36..a689f35 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -58,6 +58,30 @@
          !boundary->IsEntry();
 }
 
+
+size_t GraphChecker::Run(bool pass_change, size_t last_size) {
+  size_t current_size = GetGraph()->GetReversePostOrder().size();
+  if (!pass_change) {
+    // Nothing changed for certain. Do a quick sanity check on that assertion
+    // for anything other than the first call (when last size was still 0).
+    if (last_size != 0) {
+      if (current_size != last_size) {
+        AddError(StringPrintf("Incorrect no-change assertion, "
+                              "last graph size %zu vs current graph size %zu",
+                              last_size, current_size));
+      }
+    }
+    // TODO: if we would trust the "false" value of the flag completely, we
+    // could skip checking the graph at this point.
+  }
+
+  // VisitReversePostOrder is used instead of VisitInsertionOrder,
+  // as the latter might visit dead blocks removed by the dominator
+  // computation.
+  VisitReversePostOrder();
+  return current_size;
+}
+
 void GraphChecker::VisitBasicBlock(HBasicBlock* block) {
   current_block_ = block;
 
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index dbedc40..3a2bb7a 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -38,13 +38,11 @@
     seen_ids_.ClearAllBits();
   }
 
-  // Check the whole graph (in reverse post-order).
-  void Run() {
-    // VisitReversePostOrder is used instead of VisitInsertionOrder,
-    // as the latter might visit dead blocks removed by the dominator
-    // computation.
-    VisitReversePostOrder();
-  }
+  // Check the whole graph. The pass_change parameter indicates whether changes
+  // may have occurred during the just executed pass. The default value is
+  // conservatively "true" (something may have changed). The last_size parameter
+  // and return value pass along the observed graph sizes.
+  size_t Run(bool pass_change = true, size_t last_size = 0);
 
   void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
 
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 0d85c2f..1ce3524 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -589,6 +589,7 @@
     // loop if the induction of any inner loop has changed.
     if (TraverseLoopsInnerToOuter(node->inner)) {
       induction_range_.ReVisit(node->loop_info);
+      changed = true;
     }
     // Repeat simplifications in the loop-body until no more changes occur.
     // Note that since each simplification consists of eliminating code (without
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index a6163a7..6e2c994 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -107,6 +107,7 @@
                CompilerDriver* compiler_driver,
                Mutex& dump_mutex)
       : graph_(graph),
+        last_seen_graph_size_(0),
         cached_method_name_(),
         timing_logger_enabled_(compiler_driver->GetCompilerOptions().GetDumpTimings()),
         timing_logger_(timing_logger_enabled_ ? GetMethodName() : "", true, true),
@@ -174,7 +175,7 @@
     visualizer_oss_.clear();
   }
 
-  void EndPass(const char* pass_name) REQUIRES(!visualizer_dump_mutex_) {
+  void EndPass(const char* pass_name, bool pass_change) REQUIRES(!visualizer_dump_mutex_) {
     // Pause timer first, then dump graph.
     if (timing_logger_enabled_) {
       timing_logger_.EndTiming();
@@ -188,7 +189,7 @@
     if (kIsDebugBuild) {
       if (!graph_in_bad_state_) {
         GraphChecker checker(graph_);
-        checker.Run();
+        last_seen_graph_size_ = checker.Run(pass_change, last_seen_graph_size_);
         if (!checker.IsValid()) {
           LOG(FATAL) << "Error after " << pass_name << ": " << Dumpable<GraphChecker>(checker);
         }
@@ -214,6 +215,7 @@
   }
 
   HGraph* const graph_;
+  size_t last_seen_graph_size_;
 
   std::string cached_method_name_;
 
@@ -241,16 +243,22 @@
  public:
   PassScope(const char *pass_name, PassObserver* pass_observer)
       : pass_name_(pass_name),
+        pass_change_(true),  // assume change
         pass_observer_(pass_observer) {
     pass_observer_->StartPass(pass_name_);
   }
 
+  void SetPassNotChanged() {
+    pass_change_ = false;
+  }
+
   ~PassScope() {
-    pass_observer_->EndPass(pass_name_);
+    pass_observer_->EndPass(pass_name_, pass_change_);
   }
 
  private:
   const char* const pass_name_;
+  bool pass_change_;
   PassObserver* const pass_observer_;
 };
 
@@ -324,7 +332,11 @@
         PassScope scope(optimizations[i]->GetPassName(), pass_observer);
         bool pass_change = optimizations[i]->Run();
         pass_changes[static_cast<size_t>(definitions[i].pass)] = pass_change;
-        change |= pass_change;
+        if (pass_change) {
+          change = true;
+        } else {
+          scope.SetPassNotChanged();
+        }
       } else {
         // Skip the pass and record that nothing changed.
         pass_changes[static_cast<size_t>(definitions[i].pass)] = false;