diff --git a/compiler/optimizing/constant_propagation_test.cc b/compiler/optimizing/constant_propagation_test.cc
index 342777a..ff44805 100644
--- a/compiler/optimizing/constant_propagation_test.cc
+++ b/compiler/optimizing/constant_propagation_test.cc
@@ -62,7 +62,7 @@
   ASSERT_EQ(expected_after_dce, actual_after_dce);
 
   SSAChecker ssa_checker(&allocator, graph);
-  ssa_checker.VisitInsertionOrder();
+  ssa_checker.Run();
   ASSERT_TRUE(ssa_checker.IsValid());
 }
 
diff --git a/compiler/optimizing/dead_code_elimination_test.cc b/compiler/optimizing/dead_code_elimination_test.cc
index 245bcb2..3e0ba3a 100644
--- a/compiler/optimizing/dead_code_elimination_test.cc
+++ b/compiler/optimizing/dead_code_elimination_test.cc
@@ -47,7 +47,7 @@
   ASSERT_EQ(actual_after, expected_after);
 
   SSAChecker ssa_checker(&allocator, graph);
-  ssa_checker.VisitInsertionOrder();
+  ssa_checker.Run();
   ASSERT_TRUE(ssa_checker.IsValid());
 }
 
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index 34a770b..862f1b6 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -29,6 +29,9 @@
       allocator_(allocator),
       errors_(allocator, 0) {}
 
+  // Check the whole graph (in insertion order).
+  virtual void Run() { VisitInsertionOrder(); }
+
   // Check `block`.
   virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
 
@@ -65,6 +68,14 @@
   SSAChecker(ArenaAllocator* allocator, HGraph* graph)
     : GraphChecker(allocator, graph) {}
 
+  // Check the whole graph (in reverse post-order).
+  virtual void Run() {
+    // VisitReversePostOrder is used instead of VisitInsertionOrder,
+    // as the latter might visit dead blocks removed by the dominator
+    // computation.
+    VisitReversePostOrder();
+  }
+
   // Perform SSA form checks on `block`.
   virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
   // Loop-related checks from block `loop_header`.
diff --git a/compiler/optimizing/graph_checker_test.cc b/compiler/optimizing/graph_checker_test.cc
index ea06920..39def82 100644
--- a/compiler/optimizing/graph_checker_test.cc
+++ b/compiler/optimizing/graph_checker_test.cc
@@ -51,7 +51,7 @@
   ASSERT_NE(graph, nullptr);
 
   GraphChecker graph_checker(&allocator, graph);
-  graph_checker.VisitInsertionOrder();
+  graph_checker.Run();
   ASSERT_TRUE(graph_checker.IsValid());
 }
 
@@ -65,7 +65,7 @@
   graph->TransformToSSA();
 
   SSAChecker ssa_checker(&allocator, graph);
-  ssa_checker.VisitInsertionOrder();
+  ssa_checker.Run();
   ASSERT_TRUE(ssa_checker.IsValid());
 }
 
@@ -113,13 +113,13 @@
 
   HGraph* graph = CreateSimpleCFG(&allocator);
   GraphChecker graph_checker(&allocator, graph);
-  graph_checker.VisitInsertionOrder();
+  graph_checker.Run();
   ASSERT_TRUE(graph_checker.IsValid());
 
   // Remove the entry block from the exit block's predecessors, to create an
   // inconsistent successor/predecessor relation.
   graph->GetExitBlock()->RemovePredecessor(graph->GetEntryBlock());
-  graph_checker.VisitInsertionOrder();
+  graph_checker.Run();
   ASSERT_FALSE(graph_checker.IsValid());
 }
 
@@ -131,7 +131,7 @@
 
   HGraph* graph = CreateSimpleCFG(&allocator);
   GraphChecker graph_checker(&allocator, graph);
-  graph_checker.VisitInsertionOrder();
+  graph_checker.Run();
   ASSERT_TRUE(graph_checker.IsValid());
 
   // Remove the sole instruction of the exit block (composed of a
@@ -141,7 +141,7 @@
   HInstruction* last_inst = exit_block->GetLastInstruction();
   exit_block->RemoveInstruction(last_inst);
 
-  graph_checker.VisitInsertionOrder();
+  graph_checker.Run();
   ASSERT_FALSE(graph_checker.IsValid());
 }
 
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index a058dea..aee2177 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -553,6 +553,12 @@
   }
 }
 
+void HGraphVisitor::VisitReversePostOrder() {
+  for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+    VisitBasicBlock(it.Current());
+  }
+}
+
 void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) {
   for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
     it.Current()->Accept(this);
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index c6eb806..e60a7e6 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1961,8 +1961,12 @@
   virtual void VisitInstruction(HInstruction* instruction) {}
   virtual void VisitBasicBlock(HBasicBlock* block);
 
+  // Visit the graph following basic block insertion order.
   void VisitInsertionOrder();
 
+  // Visit the graph following dominator tree reverse post-order.
+  void VisitReversePostOrder();
+
   HGraph* GetGraph() const { return graph_; }
 
   // Visit functions for instruction classes.