diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 207c605..1d7e678 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -194,6 +194,11 @@
     }
     pre_header->AddSuccessor(header);
   }
+
+  // Make sure the second predecessor of a loop header is the back edge.
+  if (header->GetPredecessors().Get(1) != info->GetBackEdges().Get(0)) {
+    header->SwapPredecessors();
+  }
 }
 
 void HGraph::SimplifyCFG() {
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index d6dfeae..142b517 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -331,6 +331,13 @@
     block->successors_.Add(this);
   }
 
+  void SwapPredecessors() {
+    DCHECK(predecessors_.Size() == 2);
+    HBasicBlock* temp = predecessors_.Get(0);
+    predecessors_.Put(0, predecessors_.Get(1));
+    predecessors_.Put(1, temp);
+  }
+
   size_t GetPredecessorIndexOf(HBasicBlock* predecessor) {
     for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) {
       if (predecessors_.Get(i) == predecessor) {
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 65675dc..d541a62 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -83,6 +83,10 @@
   }
 }
 
+static bool LoopPreHeaderIsFirstPredecessor(HBasicBlock* block) {
+  return block->GetPredecessors().Get(0) == block->GetLoopInformation()->GetPreHeader();
+}
+
 void SsaRedundantPhiElimination::Run() {
   // Add all phis in the worklist.
   for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
@@ -102,7 +106,10 @@
 
     // Find if the inputs of the phi are the same instruction.
     HInstruction* candidate = phi->InputAt(0);
-    // A loop phi cannot have itself as the first phi.
+    // A loop phi cannot have itself as the first phi. Note that this
+    // check relies on our simplification pass ensuring the pre-header
+    // block is first in the list of predecessors of the loop header.
+    DCHECK(!phi->IsLoopHeaderPhi() || LoopPreHeaderIsFirstPredecessor(phi->GetBlock()));
     DCHECK_NE(phi, candidate);
 
     for (size_t i = 1; i < phi->InputCount(); ++i) {