diff --git a/compiler/optimizing/loop_optimization_test.cc b/compiler/optimizing/loop_optimization_test.cc
index 4e1857d..db83689 100644
--- a/compiler/optimizing/loop_optimization_test.cc
+++ b/compiler/optimizing/loop_optimization_test.cc
@@ -194,7 +194,9 @@
 
 // Check that SimplifyLoop() doesn't invalidate data flow when ordering loop headers'
 // predecessors.
-TEST_F(LoopOptimizationTest, SimplifyLoop) {
+//
+// This is a test for nodes.cc functionality - HGraph::SimplifyLoop.
+TEST_F(LoopOptimizationTest, SimplifyLoopReoderPredecessors) {
   // Can't use AddLoop as we want special order for blocks predecessors.
   HBasicBlock* header = new (GetAllocator()) HBasicBlock(graph_);
   HBasicBlock* body = new (GetAllocator()) HBasicBlock(graph_);
@@ -232,4 +234,83 @@
     ASSERT_TRUE(input->GetBlock()->Dominates(header->GetPredecessors()[i]));
   }
 }
+
+// Test that SimplifyLoop() processes the multiple-preheaders loops correctly.
+//
+// This is a test for nodes.cc functionality - HGraph::SimplifyLoop.
+TEST_F(LoopOptimizationTest, SimplifyLoopSinglePreheader) {
+  HBasicBlock* header = AddLoop(entry_block_, return_block_);
+
+  header->InsertInstructionBefore(
+      new (GetAllocator()) HSuspendCheck(), header->GetLastInstruction());
+
+  // Insert an if construct before the loop so it will have two preheaders.
+  HBasicBlock* if_block = new (GetAllocator()) HBasicBlock(graph_);
+  HBasicBlock* preheader0 = new (GetAllocator()) HBasicBlock(graph_);
+  HBasicBlock* preheader1 = new (GetAllocator()) HBasicBlock(graph_);
+
+  graph_->AddBlock(if_block);
+  graph_->AddBlock(preheader0);
+  graph_->AddBlock(preheader1);
+
+  // Fix successors/predecessors.
+  entry_block_->ReplaceSuccessor(header, if_block);
+  if_block->AddSuccessor(preheader0);
+  if_block->AddSuccessor(preheader1);
+  preheader0->AddSuccessor(header);
+  preheader1->AddSuccessor(header);
+
+  if_block->AddInstruction(new (GetAllocator()) HIf(parameter_));
+  preheader0->AddInstruction(new (GetAllocator()) HGoto());
+  preheader1->AddInstruction(new (GetAllocator()) HGoto());
+
+  HBasicBlock* body = header->GetSuccessors()[0];
+  DCHECK(body != return_block_);
+
+  // Add some data flow.
+  HIntConstant* const_0 = graph_->GetIntConstant(0);
+  HIntConstant* const_1 = graph_->GetIntConstant(1);
+  HIntConstant* const_2 = graph_->GetIntConstant(2);
+
+  HAdd* preheader0_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, parameter_, const_0);
+  preheader0->AddInstruction(preheader0_add);
+  HAdd* preheader1_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, parameter_, const_1);
+  preheader1->AddInstruction(preheader1_add);
+
+  HPhi* header_phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
+  header->AddPhi(header_phi);
+
+  HAdd* body_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, parameter_, const_2);
+  body->AddInstruction(body_add);
+
+  DCHECK(header->GetPredecessors()[0] == body);
+  DCHECK(header->GetPredecessors()[1] == preheader0);
+  DCHECK(header->GetPredecessors()[2] == preheader1);
+
+  header_phi->AddInput(body_add);
+  header_phi->AddInput(preheader0_add);
+  header_phi->AddInput(preheader1_add);
+
+  graph_->ClearLoopInformation();
+  graph_->ClearDominanceInformation();
+  graph_->BuildDominatorTree();
+
+  EXPECT_EQ(header->GetPredecessors().size(), 2u);
+  EXPECT_EQ(header->GetPredecessors()[1], body);
+
+  HBasicBlock* new_preheader = header->GetLoopInformation()->GetPreHeader();
+  EXPECT_EQ(preheader0->GetSingleSuccessor(), new_preheader);
+  EXPECT_EQ(preheader1->GetSingleSuccessor(), new_preheader);
+
+  EXPECT_EQ(new_preheader->GetPhis().CountSize(), 1u);
+  HPhi* new_preheader_phi = new_preheader->GetFirstPhi()->AsPhi();
+  EXPECT_EQ(new_preheader_phi->InputCount(), 2u);
+  EXPECT_EQ(new_preheader_phi->InputAt(0), preheader0_add);
+  EXPECT_EQ(new_preheader_phi->InputAt(1), preheader1_add);
+
+  EXPECT_EQ(header_phi->InputCount(), 2u);
+  EXPECT_EQ(header_phi->InputAt(0), new_preheader_phi);
+  EXPECT_EQ(header_phi->InputAt(1), body_add);
+}
+
 }  // namespace art
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index d39c2ad..099e6cc 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -397,6 +397,117 @@
   }
 }
 
+// Transform control flow of the loop to a single preheader format (don't touch the data flow).
+// New_preheader can be already among the header predecessors - this situation will be correctly
+// processed.
+static void FixControlForNewSinglePreheader(HBasicBlock* header, HBasicBlock* new_preheader) {
+  HLoopInformation* loop_info = header->GetLoopInformation();
+  for (size_t pred = 0; pred < header->GetPredecessors().size(); ++pred) {
+    HBasicBlock* predecessor = header->GetPredecessors()[pred];
+    if (!loop_info->IsBackEdge(*predecessor) && predecessor != new_preheader) {
+      predecessor->ReplaceSuccessor(header, new_preheader);
+      pred--;
+    }
+  }
+}
+
+//             == Before ==                                               == After ==
+//      _________         _________                               _________         _________
+//     | B0      |       | B1      |      (old preheaders)       | B0      |       | B1      |
+//     |=========|       |=========|                             |=========|       |=========|
+//     | i0 = .. |       | i1 = .. |                             | i0 = .. |       | i1 = .. |
+//     |_________|       |_________|                             |_________|       |_________|
+//           \               /                                         \              /
+//            \             /                                        ___v____________v___
+//             \           /               (new preheader)          | B20 <- B0, B1      |
+//              |         |                                         |====================|
+//              |         |                                         | i20 = phi(i0, i1)  |
+//              |         |                                         |____________________|
+//              |         |                                                   |
+//    /\        |         |        /\                           /\            |              /\
+//   /  v_______v_________v_______v  \                         /  v___________v_____________v  \
+//  |  | B10 <- B0, B1, B2, B3     |  |                       |  | B10 <- B20, B2, B3        |  |
+//  |  |===========================|  |       (header)        |  |===========================|  |
+//  |  | i10 = phi(i0, i1, i2, i3) |  |                       |  | i10 = phi(i20, i2, i3)    |  |
+//  |  |___________________________|  |                       |  |___________________________|  |
+//  |        /               \        |                       |        /               \        |
+//  |      ...              ...       |                       |      ...              ...       |
+//  |   _________         _________   |                       |   _________         _________   |
+//  |  | B2      |       | B3      |  |                       |  | B2      |       | B3      |  |
+//  |  |=========|       |=========|  |     (back edges)      |  |=========|       |=========|  |
+//  |  | i2 = .. |       | i3 = .. |  |                       |  | i2 = .. |       | i3 = .. |  |
+//  |  |_________|       |_________|  |                       |  |_________|       |_________|  |
+//   \     /                   \     /                         \     /                   \     /
+//    \___/                     \___/                           \___/                     \___/
+//
+void HGraph::TransformLoopToSinglePreheaderFormat(HBasicBlock* header) {
+  HLoopInformation* loop_info = header->GetLoopInformation();
+
+  HBasicBlock* preheader = new (allocator_) HBasicBlock(this, header->GetDexPc());
+  AddBlock(preheader);
+  preheader->AddInstruction(new (allocator_) HGoto(header->GetDexPc()));
+
+  // If the old header has no Phis then we only need to fix the control flow.
+  if (header->GetPhis().IsEmpty()) {
+    FixControlForNewSinglePreheader(header, preheader);
+    preheader->AddSuccessor(header);
+    return;
+  }
+
+  // Find the first non-back edge block in the header's predecessors list.
+  size_t first_nonbackedge_pred_pos = 0;
+  bool found = false;
+  for (size_t pred = 0; pred < header->GetPredecessors().size(); ++pred) {
+    HBasicBlock* predecessor = header->GetPredecessors()[pred];
+    if (!loop_info->IsBackEdge(*predecessor)) {
+      first_nonbackedge_pred_pos = pred;
+      found = true;
+      break;
+    }
+  }
+
+  DCHECK(found);
+
+  // Fix the data-flow.
+  for (HInstructionIterator it(header->GetPhis()); !it.Done(); it.Advance()) {
+    HPhi* header_phi = it.Current()->AsPhi();
+
+    HPhi* preheader_phi = new (GetAllocator()) HPhi(GetAllocator(),
+                                                    header_phi->GetRegNumber(),
+                                                    0,
+                                                    header_phi->GetType());
+    if (header_phi->GetType() == DataType::Type::kReference) {
+      preheader_phi->SetReferenceTypeInfo(header_phi->GetReferenceTypeInfo());
+    }
+    preheader->AddPhi(preheader_phi);
+
+    HInstruction* orig_input = header_phi->InputAt(first_nonbackedge_pred_pos);
+    header_phi->ReplaceInput(preheader_phi, first_nonbackedge_pred_pos);
+    preheader_phi->AddInput(orig_input);
+
+    for (size_t input_pos = first_nonbackedge_pred_pos + 1;
+         input_pos < header_phi->InputCount();
+         input_pos++) {
+      HInstruction* input = header_phi->InputAt(input_pos);
+      HBasicBlock* pred_block = header->GetPredecessors()[input_pos];
+
+      if (loop_info->Contains(*pred_block)) {
+        DCHECK(loop_info->IsBackEdge(*pred_block));
+      } else {
+        preheader_phi->AddInput(input);
+        header_phi->RemoveInputAt(input_pos);
+        input_pos--;
+      }
+    }
+  }
+
+  // Fix the control-flow.
+  HBasicBlock* first_pred = header->GetPredecessors()[first_nonbackedge_pred_pos];
+  preheader->InsertBetween(first_pred, header);
+
+  FixControlForNewSinglePreheader(header, preheader);
+}
+
 void HGraph::SimplifyLoop(HBasicBlock* header) {
   HLoopInformation* info = header->GetLoopInformation();
 
@@ -406,18 +517,7 @@
   // this graph.
   size_t number_of_incomings = header->GetPredecessors().size() - info->NumberOfBackEdges();
   if (number_of_incomings != 1 || (GetEntryBlock()->GetSingleSuccessor() == header)) {
-    HBasicBlock* pre_header = new (allocator_) HBasicBlock(this, header->GetDexPc());
-    AddBlock(pre_header);
-    pre_header->AddInstruction(new (allocator_) HGoto(header->GetDexPc()));
-
-    for (size_t pred = 0; pred < header->GetPredecessors().size(); ++pred) {
-      HBasicBlock* predecessor = header->GetPredecessors()[pred];
-      if (!info->IsBackEdge(*predecessor)) {
-        predecessor->ReplaceSuccessor(header, pre_header);
-        pred--;
-      }
-    }
-    pre_header->AddSuccessor(header);
+    TransformLoopToSinglePreheaderFormat(header);
   }
 
   OrderLoopHeaderPredecessors(header);
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index affd54e..f83abd7 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -423,6 +423,17 @@
 
   void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor);
   void OrderLoopHeaderPredecessors(HBasicBlock* header);
+
+  // Transform a loop into a format with a single preheader.
+  //
+  // Each phi in the header should be split: original one in the header should only hold
+  // inputs reachable from the back edges and a single input from the preheader. The newly created
+  // phi in the preheader should collate the inputs from the original multiple incoming blocks.
+  //
+  // Loops in the graph typically have a single preheader, so this method is used to "repair" loops
+  // that no longer have this property.
+  void TransformLoopToSinglePreheaderFormat(HBasicBlock* header);
+
   void SimplifyLoop(HBasicBlock* header);
 
   int32_t GetNextInstructionId() {