diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index d4498a6..0ef174d 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -133,8 +133,13 @@
   // recognition. Returns whether it was successful in doing all these steps.
   bool TryBuildingSsa() {
     BuildDominatorTree();
+    // The SSA builder requires loops to all be natural. Specifically, the dead phi
+    // elimination phase checks the consistency of the graph when doing a post-order
+    // visit for eliminating dead phis: a dead phi can only have loop header phi
+    // users remaining when being visited.
+    if (!AnalyzeNaturalLoops()) return false;
     TransformToSsa();
-    return AnalyzeNaturalLoops();
+    return true;
   }
 
   void BuildDominatorTree();