diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index d4e2cbb..c986c57 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -78,6 +78,7 @@
 	compiler/oat_test.cc \
 	compiler/optimizing/codegen_test.cc \
 	compiler/optimizing/dominator_test.cc \
+	compiler/optimizing/find_loops_test.cc \
 	compiler/optimizing/liveness_test.cc \
 	compiler/optimizing/pretty_printer_test.cc \
 	compiler/optimizing/ssa_test.cc \
diff --git a/compiler/optimizing/dominator_test.cc b/compiler/optimizing/dominator_test.cc
index 0417050..3062e37 100644
--- a/compiler/optimizing/dominator_test.cc
+++ b/compiler/optimizing/dominator_test.cc
@@ -167,7 +167,8 @@
     0,
     1,
     1,
-    3
+    3,
+    1,  // Synthesized block to avoid critical edge.
   };
 
   TestCode(data, dominators, sizeof(dominators) / sizeof(int));
@@ -185,7 +186,9 @@
     0,
     1,
     1,
-    -1  // exit block is not dominated by any block due to the spin loop.
+    -1,  // exit block is not dominated by any block due to the spin loop.
+    1,   // block to avoid critical edge.
+    1    // block to avoid critical edge.
   };
 
   TestCode(data, dominators, sizeof(dominators) / sizeof(int));
@@ -205,7 +208,8 @@
     1,
     1,
     1,
-    -1  // exit block is not dominated by any block due to the spin loop.
+    -1,  // exit block is not dominated by any block due to the spin loop.
+    1    // block to avoid critical edge.
   };
 
   TestCode(data, dominators, sizeof(dominators) / sizeof(int));
@@ -225,7 +229,8 @@
     1,
     1,
     1,
-    -1  // exit block is not dominated by any block due to the spin loop.
+    -1,  // exit block is not dominated by any block due to the spin loop.
+    1    // block to avoid critical edge.
   };
 
   TestCode(data, dominators, sizeof(dominators) / sizeof(int));
@@ -247,7 +252,9 @@
     2,
     2,
     1,
-    5  // Block number 5 dominates exit block
+    5,    // Block number 5 dominates exit block
+    1,    // block to avoid critical edge.
+    2     // block to avoid critical edge.
   };
 
   TestCode(data, dominators, sizeof(dominators) / sizeof(int));
diff --git a/compiler/optimizing/find_loops_test.cc b/compiler/optimizing/find_loops_test.cc
new file mode 100644
index 0000000..fab9f7a
--- /dev/null
+++ b/compiler/optimizing/find_loops_test.cc
@@ -0,0 +1,362 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "builder.h"
+#include "dex_file.h"
+#include "dex_instruction.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "ssa_liveness_analysis.h"
+#include "utils/arena_allocator.h"
+#include "pretty_printer.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+static HGraph* TestCode(const uint16_t* data, ArenaPool* pool) {
+  ArenaAllocator allocator(pool);
+  HGraphBuilder builder(&allocator);
+  const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
+  HGraph* graph = builder.BuildGraph(*item);
+  graph->BuildDominatorTree();
+  graph->FindNaturalLoops();
+  return graph;
+}
+
+TEST(FindLoopsTest, CFG1) {
+  // Constant is not used.
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::RETURN_VOID);
+
+  ArenaPool arena;
+  HGraph* graph = TestCode(data, &arena);
+  for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
+    ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
+  }
+}
+
+TEST(FindLoopsTest, CFG2) {
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::RETURN);
+
+  ArenaPool arena;
+  HGraph* graph = TestCode(data, &arena);
+  for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
+    ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
+  }
+}
+
+TEST(FindLoopsTest, CFG3) {
+  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 3 << 12 | 0,
+    Instruction::CONST_4 | 4 << 12 | 1 << 8,
+    Instruction::ADD_INT_2ADDR | 1 << 12,
+    Instruction::GOTO | 0x100,
+    Instruction::RETURN);
+
+  ArenaPool arena;
+  HGraph* graph = TestCode(data, &arena);
+  for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
+    ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
+  }
+}
+
+TEST(FindLoopsTest, CFG4) {
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::GOTO | 0x200,
+    Instruction::CONST_4 | 5 << 12 | 0,
+    Instruction::RETURN | 0 << 8);
+
+  ArenaPool arena;
+  HGraph* graph = TestCode(data, &arena);
+  for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
+    ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
+  }
+}
+
+TEST(FindLoopsTest, CFG5) {
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::RETURN | 0 << 8);
+
+  ArenaPool arena;
+  HGraph* graph = TestCode(data, &arena);
+  for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
+    ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
+  }
+}
+
+static void TestBlock(HGraph* graph,
+                      int block_id,
+                      bool is_loop_header,
+                      int parent_loop_header_id,
+                      const int* blocks_in_loop = nullptr,
+                      size_t number_of_blocks = 0) {
+  HBasicBlock* block = graph->GetBlocks().Get(block_id);
+  ASSERT_EQ(block->IsLoopHeader(), is_loop_header);
+  if (parent_loop_header_id == -1) {
+    ASSERT_EQ(block->GetLoopInformation(), nullptr);
+  } else {
+    ASSERT_EQ(block->GetLoopInformation()->GetHeader()->GetBlockId(), parent_loop_header_id);
+  }
+
+  if (blocks_in_loop != nullptr) {
+    HLoopInformation* info = block->GetLoopInformation();
+    const BitVector& blocks = info->GetBlocks();
+    ASSERT_EQ(blocks.NumSetBits(), number_of_blocks);
+    for (size_t i = 0; i < number_of_blocks; ++i) {
+      ASSERT_TRUE(blocks.IsBitSet(blocks_in_loop[i]));
+    }
+  } else {
+    ASSERT_FALSE(block->IsLoopHeader());
+  }
+}
+
+TEST(FindLoopsTest, Loop1) {
+  // Simple loop with one preheader and one back edge.
+  // var a = 0;
+  // while (a == a) {
+  // }
+  // return;
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0xFE00,
+    Instruction::RETURN_VOID);
+
+  ArenaPool arena;
+  HGraph* graph = TestCode(data, &arena);
+
+  TestBlock(graph, 0, false, -1);            // entry block
+  TestBlock(graph, 1, false, -1);            // pre header
+  const int blocks2[] = {2, 3};
+  TestBlock(graph, 2, true, 2, blocks2, 2);  // loop header
+  TestBlock(graph, 3, false, 2);             // block in loop
+  TestBlock(graph, 4, false, -1);            // return block
+  TestBlock(graph, 5, false, -1);            // exit block
+}
+
+TEST(FindLoopsTest, Loop2) {
+  // Make sure we support a preheader of a loop not being the first predecessor
+  // in the predecessor list of the header.
+  // var a = 0;
+  // while (a == a) {
+  // }
+  // return a;
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::GOTO | 0x400,
+    Instruction::IF_EQ, 4,
+    Instruction::GOTO | 0xFE00,
+    Instruction::GOTO | 0xFD00,
+    Instruction::RETURN | 0 << 8);
+
+  ArenaPool arena;
+  HGraph* graph = TestCode(data, &arena);
+
+  TestBlock(graph, 0, false, -1);            // entry block
+  TestBlock(graph, 1, false, -1);            // goto block
+  const int blocks2[] = {2, 3};
+  TestBlock(graph, 2, true, 2, blocks2, 2);  // loop header
+  TestBlock(graph, 3, false, 2);             // block in loop
+  TestBlock(graph, 4, false, -1);            // pre header
+  TestBlock(graph, 5, false, -1);            // return block
+  TestBlock(graph, 6, false, -1);            // exit block
+}
+
+TEST(FindLoopsTest, Loop3) {
+  // Make sure we create a preheader of a loop when a header originally has two
+  // incoming blocks and one back edge.
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0x100,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0xFE00,
+    Instruction::RETURN | 0 << 8);
+
+  ArenaPool arena;
+  HGraph* graph = TestCode(data, &arena);
+
+  TestBlock(graph, 0, false, -1);            // entry block
+  TestBlock(graph, 1, false, -1);            // goto block
+  TestBlock(graph, 2, false, -1);
+  const int blocks2[] = {3, 4};
+  TestBlock(graph, 3, true, 3, blocks2, 2);  // loop header
+  TestBlock(graph, 4, false, 3);             // block in loop
+  TestBlock(graph, 5, false, -1);            // pre header
+  TestBlock(graph, 6, false, -1);            // return block
+  TestBlock(graph, 7, false, -1);            // exit block
+  TestBlock(graph, 8, false, -1);            // synthesized pre header
+}
+
+TEST(FindLoopsTest, Loop4) {
+  // Test loop with originally two back edges.
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 6,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0xFC00,
+    Instruction::GOTO | 0xFB00,
+    Instruction::RETURN | 0 << 8);
+
+  ArenaPool arena;
+  HGraph* graph = TestCode(data, &arena);
+
+  TestBlock(graph, 0, false, -1);            // entry block
+  TestBlock(graph, 1, false, -1);            // pre header
+  const int blocks2[] = {2, 3, 4, 5, 8};
+  TestBlock(graph, 2, true, 2, blocks2, 5);  // loop header
+  TestBlock(graph, 3, false, 2);             // block in loop
+  TestBlock(graph, 4, false, 2);             // original back edge
+  TestBlock(graph, 5, false, 2);             // original back edge
+  TestBlock(graph, 6, false, -1);            // return block
+  TestBlock(graph, 7, false, -1);            // exit block
+  TestBlock(graph, 8, false, 2);             // synthesized back edge
+}
+
+
+TEST(FindLoopsTest, Loop5) {
+  // Test loop with two exit edges.
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 6,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0x0200,
+    Instruction::GOTO | 0xFB00,
+    Instruction::RETURN | 0 << 8);
+
+  ArenaPool arena;
+  HGraph* graph = TestCode(data, &arena);
+
+  TestBlock(graph, 0, false, -1);            // entry block
+  TestBlock(graph, 1, false, -1);            // pre header
+  const int blocks2[] = {2, 3, 5};
+  TestBlock(graph, 2, true, 2, blocks2, 3);  // loop header
+  TestBlock(graph, 3, false, 2);             // block in loop
+  TestBlock(graph, 4, false, -1);            // loop exit
+  TestBlock(graph, 5, false, 2);             // back edge
+  TestBlock(graph, 6, false, -1);            // return block
+  TestBlock(graph, 7, false, -1);            // exit block
+  TestBlock(graph, 8, false, -1);            // synthesized block at the loop exit
+}
+
+TEST(FindLoopsTest, InnerLoop) {
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 6,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0xFE00,  // inner loop
+    Instruction::GOTO | 0xFB00,
+    Instruction::RETURN | 0 << 8);
+
+
+  ArenaPool arena;
+  HGraph* graph = TestCode(data, &arena);
+
+  TestBlock(graph, 0, false, -1);            // entry block
+  TestBlock(graph, 1, false, -1);            // pre header of outer loop
+  const int blocks2[] = {2, 3, 4, 5, 8};
+  TestBlock(graph, 2, true, 2, blocks2, 5);  // outer loop header
+  const int blocks3[] = {3, 4};
+  TestBlock(graph, 3, true, 3, blocks3, 2);  // inner loop header
+  TestBlock(graph, 4, false, 3);             // back edge on inner loop
+  TestBlock(graph, 5, false, 2);             // back edge on outer loop
+  TestBlock(graph, 6, false, -1);            // return block
+  TestBlock(graph, 7, false, -1);            // exit block
+  TestBlock(graph, 8, false, 2);             // synthesized block as pre header of inner loop
+
+  ASSERT_TRUE(graph->GetBlocks().Get(3)->GetLoopInformation()->IsIn(
+                    *graph->GetBlocks().Get(2)->GetLoopInformation()));
+  ASSERT_FALSE(graph->GetBlocks().Get(2)->GetLoopInformation()->IsIn(
+                    *graph->GetBlocks().Get(3)->GetLoopInformation()));
+}
+
+TEST(FindLoopsTest, TwoLoops) {
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0xFE00,  // first loop
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0xFE00,  // second loop
+    Instruction::RETURN | 0 << 8);
+
+
+  ArenaPool arena;
+  HGraph* graph = TestCode(data, &arena);
+
+  TestBlock(graph, 0, false, -1);            // entry block
+  TestBlock(graph, 1, false, -1);            // pre header of first loop
+  const int blocks2[] = {2, 3};
+  TestBlock(graph, 2, true, 2, blocks2, 2);  // first loop header
+  TestBlock(graph, 3, false, 2);             // back edge of first loop
+  const int blocks4[] = {4, 5};
+  TestBlock(graph, 4, true, 4, blocks4, 2);  // second loop header
+  TestBlock(graph, 5, false, 4);             // back edge of second loop
+  TestBlock(graph, 6, false, -1);            // return block
+  TestBlock(graph, 7, false, -1);            // exit block
+
+  ASSERT_FALSE(graph->GetBlocks().Get(4)->GetLoopInformation()->IsIn(
+                    *graph->GetBlocks().Get(2)->GetLoopInformation()));
+  ASSERT_FALSE(graph->GetBlocks().Get(2)->GetLoopInformation()->IsIn(
+                    *graph->GetBlocks().Get(4)->GetLoopInformation()));
+}
+
+TEST(FindLoopsTest, NonNaturalLoop) {
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0x0100,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0xFD00,
+    Instruction::RETURN | 0 << 8);
+
+  ArenaPool arena;
+  HGraph* graph = TestCode(data, &arena);
+  ASSERT_TRUE(graph->GetBlocks().Get(3)->IsLoopHeader());
+  HLoopInformation* info = graph->GetBlocks().Get(3)->GetLoopInformation();
+  ASSERT_FALSE(info->GetHeader()->Dominates(info->GetBackEdges().Get(0)));
+}
+
+TEST(FindLoopsTest, DoWhileLoop) {
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::GOTO | 0x0100,
+    Instruction::IF_EQ, 0xFFFF,
+    Instruction::RETURN | 0 << 8);
+
+  ArenaPool arena;
+  HGraph* graph = TestCode(data, &arena);
+
+  TestBlock(graph, 0, false, -1);            // entry block
+  TestBlock(graph, 1, false, -1);            // pre header of first loop
+  const int blocks2[] = {2, 3, 6};
+  TestBlock(graph, 2, true, 2, blocks2, 3);  // loop header
+  TestBlock(graph, 3, false, 2);             // back edge of first loop
+  TestBlock(graph, 4, false, -1);            // return block
+  TestBlock(graph, 5, false, -1);            // exit block
+  TestBlock(graph, 6, false, 2);             // synthesized block to avoid a critical edge
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc
index aa4d35e..d665ab9 100644
--- a/compiler/optimizing/liveness_test.cc
+++ b/compiler/optimizing/liveness_test.cc
@@ -188,7 +188,7 @@
     "  kill: (1100)\n"
     "Block 1\n"  // block with if
     "  live in: (1100)\n"
-    "  live out: (0100)\n"
+    "  live out: (1100)\n"
     "  kill: (0010)\n"
     "Block 2\n"  // else block
     "  live in: (0100)\n"
@@ -201,6 +201,10 @@
     "Block 4\n"  // exit block
     "  live in: (0000)\n"
     "  live out: (0000)\n"
+    "  kill: (0000)\n"
+    "Block 5\n"  // block to avoid critical edge. Predecessor is 1, successor is 3.
+    "  live in: (1000)\n"
+    "  live out: (0000)\n"
     "  kill: (0000)\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
@@ -412,40 +416,45 @@
 
 TEST(LivenessTest, Loop6) {
   // Bitsets are made of:
-  // (constant0, constant4, constant5, phi in block 2, equal in block 2, equal in block 3)
+  // (constant0, constant4, constant5, phi in block 2, equal in block 2, equal in block 3,
+  //  phi in block 8)
   const char* expected =
     "Block 0\n"
-    "  live in: (000000)\n"
-    "  live out: (111000)\n"
-    "  kill: (111000)\n"
+    "  live in: (0000000)\n"
+    "  live out: (1110000)\n"
+    "  kill: (1110000)\n"
     "Block 1\n"
-    "  live in: (111000)\n"
-    "  live out: (011000)\n"
-    "  kill: (000000)\n"
+    "  live in: (1110000)\n"
+    "  live out: (0110000)\n"
+    "  kill: (0000000)\n"
     "Block 2\n"  // loop header
-    "  live in: (011000)\n"
-    "  live out: (011100)\n"
-    "  kill: (000110)\n"
+    "  live in: (0110000)\n"
+    "  live out: (0111000)\n"
+    "  kill: (0001100)\n"
     "Block 3\n"
-    "  live in: (011000)\n"
-    "  live out: (011000)\n"
-    "  kill: (000001)\n"
-    "Block 4\n"  // back edge
-    "  live in: (011000)\n"
-    "  live out: (011000)\n"
-    "  kill: (000000)\n"
-    "Block 5\n"  // back edge
-    "  live in: (011000)\n"
-    "  live out: (011000)\n"
-    "  kill: (000000)\n"
+    "  live in: (0110000)\n"
+    "  live out: (0110000)\n"
+    "  kill: (0000010)\n"
+    "Block 4\n"  // original back edge
+    "  live in: (0110000)\n"
+    "  live out: (0110000)\n"
+    "  kill: (0000000)\n"
+    "Block 5\n"  // original back edge
+    "  live in: (0110000)\n"
+    "  live out: (0110000)\n"
+    "  kill: (0000000)\n"
     "Block 6\n"  // return block
-    "  live in: (000100)\n"
-    "  live out: (000000)\n"
-    "  kill: (000000)\n"
+    "  live in: (0001000)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000000)\n"
     "Block 7\n"  // exit block
-    "  live in: (000000)\n"
-    "  live out: (000000)\n"
-    "  kill: (000000)\n";
+    "  live in: (0000000)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000000)\n"
+    "Block 8\n"  // synthesized back edge
+    "  live in: (0110000)\n"
+    "  live out: (0110000)\n"
+    "  kill: (0000001)\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
@@ -476,7 +485,7 @@
     "  kill: (0000000)\n"
     "Block 2\n"  // loop header
     "  live in: (0110000)\n"
-    "  live out: (0110000)\n"
+    "  live out: (0111000)\n"
     "  kill: (0001100)\n"
     "Block 3\n"
     "  live in: (0110000)\n"
@@ -497,6 +506,10 @@
     "Block 7\n"  // exit block
     "  live in: (0000000)\n"
     "  live out: (0000000)\n"
+    "  kill: (0000000)\n"
+    "Block 8\n"  // synthesized block to avoid critical edge.
+    "  live in: (0001000)\n"
+    "  live out: (0000000)\n"
     "  kill: (0000000)\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index d153bf7..cf2d1ee 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -31,11 +31,11 @@
 }
 
 void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const {
-  for (size_t i = 0; i < blocks_.Size(); i++) {
+  for (size_t i = 0; i < blocks_.Size(); ++i) {
     if (!visited.IsBitSet(i)) {
       HBasicBlock* block = blocks_.Get(i);
-      for (size_t j = 0; j < block->GetSuccessors()->Size(); j++) {
-        block->GetSuccessors()->Get(j)->RemovePredecessor(block, false);
+      for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
+        block->GetSuccessors().Get(j)->RemovePredecessor(block, false);
       }
       for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
         block->RemovePhi(it.Current()->AsPhi());
@@ -55,15 +55,14 @@
 
   visited->SetBit(id);
   visiting->SetBit(id);
-  for (size_t i = 0; i < block->GetSuccessors()->Size(); i++) {
-    HBasicBlock* successor = block->GetSuccessors()->Get(i);
+  for (size_t i = 0; i < block->GetSuccessors().Size(); i++) {
+    HBasicBlock* successor = block->GetSuccessors().Get(i);
     if (visiting->IsBitSet(successor->GetBlockId())) {
       successor->AddBackEdge(block);
     } else {
       VisitBlockForBackEdges(successor, visited, visiting);
     }
   }
-  post_order_.Add(block);
   visiting->ClearBit(id);
 }
 
@@ -78,13 +77,18 @@
   //     predecessors list of live blocks.
   RemoveDeadBlocks(visited);
 
-  // (3) Compute the immediate dominator of each block. We visit
+  // (3) Simplify the CFG now, so that we don't need to recompute
+  //     dominators and the reverse post order.
+  SimplifyCFG();
+
+  // (4) Compute the immediate dominator of each block. We visit
   //     the successors of a block only when all its forward branches
   //     have been processed.
   GrowableArray<size_t> visits(arena_, blocks_.Size());
   visits.SetSize(blocks_.Size());
-  for (size_t i = 0; i < entry_block_->GetSuccessors()->Size(); i++) {
-    VisitBlockForDominatorTree(entry_block_->GetSuccessors()->Get(i), entry_block_, &visits);
+  reverse_post_order_.Add(entry_block_);
+  for (size_t i = 0; i < entry_block_->GetSuccessors().Size(); i++) {
+    VisitBlockForDominatorTree(entry_block_->GetSuccessors().Get(i), entry_block_, &visits);
   }
 }
 
@@ -119,59 +123,172 @@
   // Once all the forward edges have been visited, we know the immediate
   // dominator of the block. We can then start visiting its successors.
   if (visits->Get(block->GetBlockId()) ==
-      block->GetPredecessors()->Size() - block->NumberOfBackEdges()) {
-    for (size_t i = 0; i < block->GetSuccessors()->Size(); i++) {
-      VisitBlockForDominatorTree(block->GetSuccessors()->Get(i), block, visits);
+      block->GetPredecessors().Size() - block->NumberOfBackEdges()) {
+    reverse_post_order_.Add(block);
+    for (size_t i = 0; i < block->GetSuccessors().Size(); i++) {
+      VisitBlockForDominatorTree(block->GetSuccessors().Get(i), block, visits);
     }
   }
 }
 
 void HGraph::TransformToSSA() {
-  DCHECK(!post_order_.IsEmpty());
-  SimplifyCFG();
+  DCHECK(!reverse_post_order_.IsEmpty());
   SsaBuilder ssa_builder(this);
   ssa_builder.BuildSsa();
 }
 
-void HGraph::SimplifyCFG() {
-  for (size_t i = post_order_.Size(); i > 0; --i) {
-    HBasicBlock* current = post_order_.Get(i - 1);
-    if (current->IsLoopHeader()) {
-      // Make sure the loop has only one pre header. This simplifies SSA building by having
-      // to just look at the pre header to know which locals are initialized at entry of the
-      // loop.
-      HLoopInformation* info = current->GetLoopInformation();
-      size_t number_of_incomings = current->GetPredecessors()->Size() - info->NumberOfBackEdges();
-      if (number_of_incomings != 1) {
-        HBasicBlock* pre_header = new (arena_) HBasicBlock(this);
-        AddBlock(pre_header);
-        pre_header->AddInstruction(new (arena_) HGoto());
-        pre_header->SetDominator(current->GetDominator());
-        current->SetDominator(pre_header);
-        post_order_.InsertAt(i, pre_header);
-
-        ArenaBitVector back_edges(arena_, GetBlocks().Size(), false);
-        for (size_t pred = 0; pred < info->GetBackEdges()->Size(); pred++) {
-          back_edges.SetBit(info->GetBackEdges()->Get(pred)->GetBlockId());
-        }
-        for (size_t pred = 0; pred < current->GetPredecessors()->Size(); pred++) {
-          HBasicBlock* predecessor = current->GetPredecessors()->Get(pred);
-          if (!back_edges.IsBitSet(predecessor->GetBlockId())) {
-            current->RemovePredecessor(predecessor);
-            pred--;
-            predecessor->AddSuccessor(pre_header);
-          }
-        }
-        pre_header->AddSuccessor(current);
-      }
-      info->SetPreHeader(current->GetDominator());
+void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) {
+  // Insert a new node between `block` and `successor` to split the
+  // critical edge.
+  HBasicBlock* new_block = new (arena_) HBasicBlock(this);
+  AddBlock(new_block);
+  new_block->AddInstruction(new (arena_) HGoto());
+  block->RemoveSuccessor(successor);
+  block->AddSuccessor(new_block);
+  new_block->AddSuccessor(successor);
+  if (successor->IsLoopHeader()) {
+    // If we split at a back edge boundary, make the new block the back edge.
+    HLoopInformation* info = successor->GetLoopInformation();
+    if (info->IsBackEdge(block)) {
+      info->RemoveBackEdge(block);
+      info->AddBackEdge(new_block);
     }
   }
 }
 
-void HLoopInformation::SetPreHeader(HBasicBlock* block) {
-  DCHECK_EQ(header_->GetDominator(), block);
-  pre_header_ = block;
+void HGraph::SimplifyLoop(HBasicBlock* header) {
+  HLoopInformation* info = header->GetLoopInformation();
+
+  // If there are more than one back edge, make them branch to the same block that
+  // will become the only back edge. This simplifies finding natural loops in the
+  // graph.
+  if (info->NumberOfBackEdges() > 1) {
+    HBasicBlock* new_back_edge = new (arena_) HBasicBlock(this);
+    AddBlock(new_back_edge);
+    new_back_edge->AddInstruction(new (arena_) HGoto());
+    for (size_t pred = 0, e = info->GetBackEdges().Size(); pred < e; ++pred) {
+      HBasicBlock* back_edge = info->GetBackEdges().Get(pred);
+      header->RemovePredecessor(back_edge);
+      back_edge->AddSuccessor(new_back_edge);
+    }
+    info->ClearBackEdges();
+    info->AddBackEdge(new_back_edge);
+    new_back_edge->AddSuccessor(header);
+  }
+
+  // Make sure the loop has only one pre header. This simplifies SSA building by having
+  // to just look at the pre header to know which locals are initialized at entry of the
+  // loop.
+  size_t number_of_incomings = header->GetPredecessors().Size() - info->NumberOfBackEdges();
+  if (number_of_incomings != 1) {
+    HBasicBlock* pre_header = new (arena_) HBasicBlock(this);
+    AddBlock(pre_header);
+    pre_header->AddInstruction(new (arena_) HGoto());
+
+    ArenaBitVector back_edges(arena_, GetBlocks().Size(), false);
+    HBasicBlock* back_edge = info->GetBackEdges().Get(0);
+    for (size_t pred = 0; pred < header->GetPredecessors().Size(); ++pred) {
+      HBasicBlock* predecessor = header->GetPredecessors().Get(pred);
+      if (predecessor != back_edge) {
+        header->RemovePredecessor(predecessor);
+        pred--;
+        predecessor->AddSuccessor(pre_header);
+      }
+    }
+    pre_header->AddSuccessor(header);
+  }
+}
+
+void HGraph::SimplifyCFG() {
+  // Simplify the CFG for future analysis, and code generation:
+  // (1): Split critical edges.
+  // (2): Simplify loops by having only one back edge, and one preheader.
+  for (size_t i = 0; i < blocks_.Size(); ++i) {
+    HBasicBlock* block = blocks_.Get(i);
+    if (block->GetSuccessors().Size() > 1) {
+      for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
+        HBasicBlock* successor = block->GetSuccessors().Get(j);
+        if (successor->GetPredecessors().Size() > 1) {
+          SplitCriticalEdge(block, successor);
+          --j;
+        }
+      }
+    }
+    if (block->IsLoopHeader()) {
+      SimplifyLoop(block);
+    }
+  }
+}
+
+bool HGraph::FindNaturalLoops() const {
+  for (size_t i = 0; i < blocks_.Size(); ++i) {
+    HBasicBlock* block = blocks_.Get(i);
+    if (block->IsLoopHeader()) {
+      HLoopInformation* info = block->GetLoopInformation();
+      if (!info->Populate()) {
+        // Abort if the loop is non natural. We currently bailout in such cases.
+        return false;
+      }
+    }
+  }
+  return true;
+}
+
+void HLoopInformation::PopulateRecursive(HBasicBlock* block) {
+  if (blocks_.IsBitSet(block->GetBlockId())) {
+    return;
+  }
+
+  blocks_.SetBit(block->GetBlockId());
+  block->SetInLoop(this);
+  for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) {
+    PopulateRecursive(block->GetPredecessors().Get(i));
+  }
+}
+
+bool HLoopInformation::Populate() {
+  DCHECK_EQ(GetBackEdges().Size(), 1u);
+  HBasicBlock* back_edge = GetBackEdges().Get(0);
+  DCHECK(back_edge->GetDominator() != nullptr);
+  if (!header_->Dominates(back_edge)) {
+    // This loop is not natural. Do not bother going further.
+    return false;
+  }
+
+  // Populate this loop: starting with the back edge, recursively add predecessors
+  // that are not already part of that loop. Set the header as part of the loop
+  // to end the recursion.
+  // This is a recursive implementation of the algorithm described in
+  // "Advanced Compiler Design & Implementation" (Muchnick) p192.
+  blocks_.SetBit(header_->GetBlockId());
+  PopulateRecursive(back_edge);
+  return true;
+}
+
+HBasicBlock* HLoopInformation::GetPreHeader() const {
+  DCHECK_EQ(header_->GetPredecessors().Size(), 2u);
+  return header_->GetDominator();
+}
+
+bool HLoopInformation::Contains(const HBasicBlock& block) const {
+  return blocks_.IsBitSet(block.GetBlockId());
+}
+
+bool HLoopInformation::IsIn(const HLoopInformation& other) const {
+  return other.blocks_.IsBitSet(header_->GetBlockId());
+}
+
+bool HBasicBlock::Dominates(HBasicBlock* other) const {
+  // Walk up the dominator tree from `other`, to find out if `this`
+  // is an ancestor.
+  HBasicBlock* current = other;
+  while (current != nullptr) {
+    if (current == this) {
+      return true;
+    }
+    current = current->GetDominator();
+  }
+  return false;
 }
 
 static void Add(HInstructionList* instruction_list,
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index bd3d703..081c2bd 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -60,7 +60,7 @@
   explicit HGraph(ArenaAllocator* arena)
       : arena_(arena),
         blocks_(arena, kDefaultNumberOfBlocks),
-        post_order_(arena, kDefaultNumberOfBlocks),
+        reverse_post_order_(arena, kDefaultNumberOfBlocks),
         maximum_number_of_out_vregs_(0),
         number_of_vregs_(0),
         number_of_in_vregs_(0),
@@ -81,6 +81,14 @@
   void TransformToSSA();
   void SimplifyCFG();
 
+  // Find all natural loops in this graph. Aborts computation and returns false
+  // if one loop is not natural, that is the header does not dominated the back
+  // edge.
+  bool FindNaturalLoops() const;
+
+  void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor);
+  void SimplifyLoop(HBasicBlock* header);
+
   int GetNextInstructionId() {
     return current_instruction_id_++;
   }
@@ -109,8 +117,8 @@
     return number_of_in_vregs_;
   }
 
-  const GrowableArray<HBasicBlock*>& GetPostOrder() const {
-    return post_order_;
+  const GrowableArray<HBasicBlock*>& GetReversePostOrder() const {
+    return reverse_post_order_;
   }
 
  private:
@@ -129,8 +137,8 @@
   // List of blocks in insertion order.
   GrowableArray<HBasicBlock*> blocks_;
 
-  // List of blocks to perform a post order tree traversal.
-  GrowableArray<HBasicBlock*> post_order_;
+  // List of blocks to perform a reverse post order tree traversal.
+  GrowableArray<HBasicBlock*> reverse_post_order_;
 
   HBasicBlock* entry_block_;
   HBasicBlock* exit_block_;
@@ -154,30 +162,63 @@
  public:
   HLoopInformation(HBasicBlock* header, HGraph* graph)
       : header_(header),
-        back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges) { }
+        back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges),
+        blocks_(graph->GetArena(), graph->GetBlocks().Size(), false) {}
+
+  HBasicBlock* GetHeader() const {
+    return header_;
+  }
 
   void AddBackEdge(HBasicBlock* back_edge) {
     back_edges_.Add(back_edge);
   }
 
+  void RemoveBackEdge(HBasicBlock* back_edge) {
+    back_edges_.Delete(back_edge);
+  }
+
+  bool IsBackEdge(HBasicBlock* block) {
+    for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) {
+      if (back_edges_.Get(i) == block) return true;
+    }
+    return false;
+  }
+
   int NumberOfBackEdges() const {
     return back_edges_.Size();
   }
 
-  void SetPreHeader(HBasicBlock* block);
+  HBasicBlock* GetPreHeader() const;
 
-  HBasicBlock* GetPreHeader() const {
-    return pre_header_;
+  const GrowableArray<HBasicBlock*>& GetBackEdges() const {
+    return back_edges_;
   }
 
-  const GrowableArray<HBasicBlock*>* GetBackEdges() const {
-    return &back_edges_;
+  void ClearBackEdges() {
+    back_edges_.Reset();
   }
 
+  // Find blocks that are part of this loop. Returns whether the loop is a natural loop,
+  // that is the header dominates the back edge.
+  bool Populate();
+
+  // Returns whether this loop information contains `block`.
+  // Note that this loop information *must* be populated before entering this function.
+  bool Contains(const HBasicBlock& block) const;
+
+  // Returns whether this loop information is an inner loop of `other`.
+  // Note that `other` *must* be populated before entering this function.
+  bool IsIn(const HLoopInformation& other) const;
+
+  const ArenaBitVector& GetBlocks() const { return blocks_; }
+
  private:
-  HBasicBlock* pre_header_;
+  // Internal recursive implementation of `Populate`.
+  void PopulateRecursive(HBasicBlock* block);
+
   HBasicBlock* header_;
   GrowableArray<HBasicBlock*> back_edges_;
+  ArenaBitVector blocks_;
 
   DISALLOW_COPY_AND_ASSIGN(HLoopInformation);
 };
@@ -195,18 +236,19 @@
         dominator_(nullptr),
         block_id_(-1) { }
 
-  const GrowableArray<HBasicBlock*>* GetPredecessors() const {
-    return &predecessors_;
+  const GrowableArray<HBasicBlock*>& GetPredecessors() const {
+    return predecessors_;
   }
 
-  const GrowableArray<HBasicBlock*>* GetSuccessors() const {
-    return &successors_;
+  const GrowableArray<HBasicBlock*>& GetSuccessors() const {
+    return successors_;
   }
 
   void AddBackEdge(HBasicBlock* back_edge) {
     if (loop_information_ == nullptr) {
       loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_);
     }
+    DCHECK_EQ(loop_information_->GetHeader(), this);
     loop_information_->AddBackEdge(back_edge);
   }
 
@@ -241,19 +283,57 @@
     }
   }
 
+  void RemoveSuccessor(HBasicBlock* block, bool remove_in_predecessor = true) {
+    successors_.Delete(block);
+    if (remove_in_predecessor) {
+      block->predecessors_.Delete(this);
+    }
+  }
+
+  void ClearAllPredecessors() {
+    predecessors_.Reset();
+  }
+
+  void AddPredecessor(HBasicBlock* block) {
+    predecessors_.Add(block);
+    block->successors_.Add(this);
+  }
+
   void AddInstruction(HInstruction* instruction);
   void RemoveInstruction(HInstruction* instruction);
   void AddPhi(HPhi* phi);
   void RemovePhi(HPhi* phi);
 
   bool IsLoopHeader() const {
-    return loop_information_ != nullptr;
+    return (loop_information_ != nullptr) && (loop_information_->GetHeader() == this);
   }
 
   HLoopInformation* GetLoopInformation() const {
     return loop_information_;
   }
 
+  // Set the loop_information_ on this block. This method overrides the current
+  // loop_information if it is an outer loop of the passed loop information.
+  void SetInLoop(HLoopInformation* info) {
+    if (IsLoopHeader()) {
+      // Nothing to do. This just means `info` is an outer loop.
+    } else if (loop_information_ == nullptr) {
+      loop_information_ = info;
+    } else if (loop_information_->Contains(*info->GetHeader())) {
+      // Block is currently part of an outer loop. Make it part of this inner loop.
+      // Note that a non loop header having a loop information means this loop information
+      // has already been populated
+      loop_information_ = info;
+    } else {
+      // Block is part of an inner loop. Do not update the loop information.
+      // Note that we cannot do the check `info->Contains(loop_information_)->GetHeader()`
+      // at this point, because this method is being called while populating `info`.
+    }
+  }
+
+  // Returns wheter this block dominates the blocked passed as parameter.
+  bool Dominates(HBasicBlock* block) const;
+
  private:
   HGraph* const graph_;
   GrowableArray<HBasicBlock*> predecessors_;
@@ -638,7 +718,7 @@
   HGoto() { }
 
   HBasicBlock* GetSuccessor() const {
-    return GetBlock()->GetSuccessors()->Get(0);
+    return GetBlock()->GetSuccessors().Get(0);
   }
 
   DECLARE_INSTRUCTION(Goto)
@@ -656,11 +736,11 @@
   }
 
   HBasicBlock* IfTrueSuccessor() const {
-    return GetBlock()->GetSuccessors()->Get(0);
+    return GetBlock()->GetSuccessors().Get(0);
   }
 
   HBasicBlock* IfFalseSuccessor() const {
-    return GetBlock()->GetSuccessors()->Get(1);
+    return GetBlock()->GetSuccessors().Get(1);
   }
 
   DECLARE_INSTRUCTION(If)
@@ -1011,35 +1091,35 @@
   DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator);
 };
 
-class HPostOrderIterator : public ValueObject {
+class HReversePostOrderIterator : public ValueObject {
  public:
-  explicit HPostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {}
+  explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {}
 
-  bool Done() const { return index_ == graph_.GetPostOrder().Size(); }
-  HBasicBlock* Current() const { return graph_.GetPostOrder().Get(index_); }
+  bool Done() const { return index_ == graph_.GetReversePostOrder().Size(); }
+  HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_); }
   void Advance() { ++index_; }
 
  private:
   const HGraph& graph_;
   size_t index_;
 
-  DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator);
+  DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator);
 };
 
-class HReversePostOrderIterator : public ValueObject {
+class HPostOrderIterator : public ValueObject {
  public:
-  explicit HReversePostOrderIterator(const HGraph& graph)
-      : graph_(graph), index_(graph_.GetPostOrder().Size()) {}
+  explicit HPostOrderIterator(const HGraph& graph)
+      : graph_(graph), index_(graph_.GetReversePostOrder().Size()) {}
 
   bool Done() const { return index_ == 0; }
-  HBasicBlock* Current() const { return graph_.GetPostOrder().Get(index_ - 1); }
+  HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_ - 1); }
   void Advance() { --index_; }
 
  private:
   const HGraph& graph_;
   size_t index_;
 
-  DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator);
+  DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator);
 };
 
 }  // namespace art
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 8594c69..a5031e0 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -104,6 +104,7 @@
   // Run these phases to get some test coverage.
   graph->BuildDominatorTree();
   graph->TransformToSSA();
+  graph->FindNaturalLoops();
   SsaLivenessAnalysis(*graph).Analyze();
 
   return new CompiledMethod(GetCompilerDriver(),
diff --git a/compiler/optimizing/pretty_printer.h b/compiler/optimizing/pretty_printer.h
index c82d0cc..dfeafe7 100644
--- a/compiler/optimizing/pretty_printer.h
+++ b/compiler/optimizing/pretty_printer.h
@@ -70,23 +70,23 @@
   virtual void VisitBasicBlock(HBasicBlock* block) {
     PrintString("BasicBlock ");
     PrintInt(block->GetBlockId());
-    const GrowableArray<HBasicBlock*>* blocks = block->GetPredecessors();
-    if (!blocks->IsEmpty()) {
+    const GrowableArray<HBasicBlock*>& predecessors = block->GetPredecessors();
+    if (!predecessors.IsEmpty()) {
       PrintString(", pred: ");
-      for (size_t i = 0; i < blocks->Size() -1; i++) {
-        PrintInt(blocks->Get(i)->GetBlockId());
+      for (size_t i = 0; i < predecessors.Size() -1; i++) {
+        PrintInt(predecessors.Get(i)->GetBlockId());
         PrintString(", ");
       }
-      PrintInt(blocks->Peek()->GetBlockId());
+      PrintInt(predecessors.Peek()->GetBlockId());
     }
-    blocks = block->GetSuccessors();
-    if (!blocks->IsEmpty()) {
+    const GrowableArray<HBasicBlock*>& successors = block->GetSuccessors();
+    if (!successors.IsEmpty()) {
       PrintString(", succ: ");
-      for (size_t i = 0; i < blocks->Size() - 1; i++) {
-        PrintInt(blocks->Get(i)->GetBlockId());
+      for (size_t i = 0; i < successors.Size() - 1; i++) {
+        PrintInt(successors.Get(i)->GetBlockId());
         PrintString(", ");
       }
-      PrintInt(blocks->Peek()->GetBlockId());
+      PrintInt(successors.Peek()->GetBlockId());
     }
     PrintNewLine();
     HGraphVisitor::VisitBasicBlock(block);
diff --git a/compiler/optimizing/pretty_printer_test.cc b/compiler/optimizing/pretty_printer_test.cc
index 04db7a6..006349c 100644
--- a/compiler/optimizing/pretty_printer_test.cc
+++ b/compiler/optimizing/pretty_printer_test.cc
@@ -57,7 +57,7 @@
     PrintString("  ");
     PrintInt(gota->GetId());
     PrintString(": Goto ");
-    PrintInt(current_block_->GetSuccessors()->Get(0)->GetBlockId());
+    PrintInt(current_block_->GetSuccessors().Get(0)->GetBlockId());
     PrintNewLine();
   }
 
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index ee1e1e4..1fc041c 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -32,8 +32,8 @@
     HBasicBlock* block = loop_headers_.Get(i);
     for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
       HPhi* phi = it.Current()->AsPhi();
-      for (size_t pred = 0; pred < block->GetPredecessors()->Size(); pred++) {
-        phi->AddInput(ValueOfLocal(block->GetPredecessors()->Get(pred), phi->GetRegNumber()));
+      for (size_t pred = 0; pred < block->GetPredecessors().Size(); pred++) {
+        phi->AddInput(ValueOfLocal(block->GetPredecessors().Get(pred), phi->GetRegNumber()));
       }
     }
   }
@@ -75,14 +75,14 @@
     // Save the loop header so that the last phase of the analysis knows which
     // blocks need to be updated.
     loop_headers_.Add(block);
-  } else if (block->GetPredecessors()->Size() > 0) {
+  } else if (block->GetPredecessors().Size() > 0) {
     // All predecessors have already been visited because we are visiting in reverse post order.
     // We merge the values of all locals, creating phis if those values differ.
     for (size_t local = 0; local < current_locals_->Size(); local++) {
       bool is_different = false;
-      HInstruction* value = ValueOfLocal(block->GetPredecessors()->Get(0), local);
-      for (size_t i = 1; i < block->GetPredecessors()->Size(); i++) {
-        if (ValueOfLocal(block->GetPredecessors()->Get(i), local) != value) {
+      HInstruction* value = ValueOfLocal(block->GetPredecessors().Get(0), local);
+      for (size_t i = 1; i < block->GetPredecessors().Size(); i++) {
+        if (ValueOfLocal(block->GetPredecessors().Get(i), local) != value) {
           is_different = true;
           break;
         }
@@ -90,9 +90,9 @@
       if (is_different) {
         // TODO: Compute union type.
         HPhi* phi = new (GetGraph()->GetArena()) HPhi(
-            GetGraph()->GetArena(), local, block->GetPredecessors()->Size(), Primitive::kPrimVoid);
-        for (size_t i = 0; i < block->GetPredecessors()->Size(); i++) {
-          phi->SetRawInputAt(i, ValueOfLocal(block->GetPredecessors()->Get(i), local));
+            GetGraph()->GetArena(), local, block->GetPredecessors().Size(), Primitive::kPrimVoid);
+        for (size_t i = 0; i < block->GetPredecessors().Size(); i++) {
+          phi->SetRawInputAt(i, ValueOfLocal(block->GetPredecessors().Get(i), local));
         }
         block->AddPhi(phi);
         value = phi;
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 838597d..0ab77ca 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -110,7 +110,7 @@
       for (size_t i = 0, e = current->InputCount(); i < e; ++i) {
         HInstruction* input = current->InputAt(i);
 
-        HBasicBlock* predecessor = block->GetPredecessors()->Get(i);
+        HBasicBlock* predecessor = block->GetPredecessors().Get(i);
         size_t ssa_index = input->GetSsaIndex();
         BitVector* predecessor_kill = GetKillSet(*predecessor);
         BitVector* predecessor_live_in = GetLiveInSet(*predecessor);
@@ -147,8 +147,8 @@
   BitVector* live_out = GetLiveOutSet(block);
   bool changed = false;
   // The live_out set of a block is the union of live_in sets of its successors.
-  for (size_t i = 0, e = block.GetSuccessors()->Size(); i < e; ++i) {
-    HBasicBlock* successor = block.GetSuccessors()->Get(i);
+  for (size_t i = 0, e = block.GetSuccessors().Size(); i < e; ++i) {
+    HBasicBlock* successor = block.GetSuccessors().Get(i);
     if (live_out->Union(GetLiveInSet(*successor))) {
       changed = true;
     }
diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc
index e4aafb7..9be2197 100644
--- a/compiler/optimizing/ssa_test.cc
+++ b/compiler/optimizing/ssa_test.cc
@@ -98,15 +98,18 @@
     "BasicBlock 0, succ: 1\n"
     "  0: IntConstant 0 [2, 2]\n"
     "  1: Goto\n"
-    "BasicBlock 1, pred: 0, succ: 3, 2\n"
+    "BasicBlock 1, pred: 0, succ: 2, 5\n"
     "  2: Equal(0, 0) [3]\n"
     "  3: If(2)\n"
     "BasicBlock 2, pred: 1, succ: 3\n"
     "  4: Goto\n"
-    "BasicBlock 3, pred: 1, 2, succ: 4\n"
+    "BasicBlock 3, pred: 2, 5, succ: 4\n"
     "  5: ReturnVoid\n"
     "BasicBlock 4, pred: 3\n"
-    "  6: Exit\n";
+    "  6: Exit\n"
+    // Synthesized block to avoid critical edge.
+    "BasicBlock 5, pred: 1, succ: 3\n"
+    "  7: Goto\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
@@ -125,16 +128,19 @@
     "  0: IntConstant 0 [6, 3, 3]\n"
     "  1: IntConstant 4 [6]\n"
     "  2: Goto\n"
-    "BasicBlock 1, pred: 0, succ: 3, 2\n"
+    "BasicBlock 1, pred: 0, succ: 2, 5\n"
     "  3: Equal(0, 0) [4]\n"
     "  4: If(3)\n"
     "BasicBlock 2, pred: 1, succ: 3\n"
     "  5: Goto\n"
-    "BasicBlock 3, pred: 1, 2, succ: 4\n"
-    "  6: Phi(0, 1) [7]\n"
+    "BasicBlock 3, pred: 2, 5, succ: 4\n"
+    "  6: Phi(1, 0) [7]\n"
     "  7: Return(6)\n"
     "BasicBlock 4, pred: 3\n"
-    "  8: Exit\n";
+    "  8: Exit\n"
+    // Synthesized block to avoid critical edge.
+    "BasicBlock 5, pred: 1, succ: 3\n"
+    "  9: Goto\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
@@ -184,16 +190,21 @@
     "BasicBlock 0, succ: 1\n"
     "  0: IntConstant 0 [6, 4, 2, 2]\n"
     "  1: Goto\n"
-    "BasicBlock 1, pred: 0, succ: 3, 2\n"
+    "BasicBlock 1, pred: 0, succ: 5, 6\n"
     "  2: Equal(0, 0) [3]\n"
     "  3: If(2)\n"
-    "BasicBlock 2, pred: 1, 3, succ: 3\n"
-    "  4: Phi(0, 6) [6]\n"
+    "BasicBlock 2, pred: 3, 6, succ: 3\n"
+    "  4: Phi(6, 0) [6]\n"
     "  5: Goto\n"
-    "BasicBlock 3, pred: 1, 2, succ: 2\n"
-    "  6: Phi(0, 4) [4]\n"
+    "BasicBlock 3, pred: 2, 5, succ: 2\n"
+    "  6: Phi(4, 0) [4]\n"
     "  7: Goto\n"
-    "BasicBlock 4\n";
+    "BasicBlock 4\n"
+    // Synthesized blocks to avoid critical edge.
+    "BasicBlock 5, pred: 1, succ: 3\n"
+    "  8: Goto\n"
+    "BasicBlock 6, pred: 1, succ: 2\n"
+    "  9: Goto\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
@@ -349,26 +360,30 @@
   const char* expected =
     "BasicBlock 0, succ: 1\n"
     "  0: IntConstant 0 [5]\n"
-    "  1: IntConstant 4 [5, 8, 8]\n"
-    "  2: IntConstant 5 [5]\n"
+    "  1: IntConstant 4 [14, 8, 8]\n"
+    "  2: IntConstant 5 [14]\n"
     "  3: Goto\n"
     "BasicBlock 1, pred: 0, succ: 2\n"
     "  4: Goto\n"
-    "BasicBlock 2, pred: 1, 4, 5, succ: 6, 3\n"
-    "  5: Phi(0, 2, 1) [12, 6, 6]\n"
+    "BasicBlock 2, pred: 1, 8, succ: 6, 3\n"
+    "  5: Phi(0, 14) [12, 6, 6]\n"
     "  6: Equal(5, 5) [7]\n"
     "  7: If(6)\n"
     "BasicBlock 3, pred: 2, succ: 5, 4\n"
     "  8: Equal(1, 1) [9]\n"
     "  9: If(8)\n"
-    "BasicBlock 4, pred: 3, succ: 2\n"
+    "BasicBlock 4, pred: 3, succ: 8\n"
     "  10: Goto\n"
-    "BasicBlock 5, pred: 3, succ: 2\n"
+    "BasicBlock 5, pred: 3, succ: 8\n"
     "  11: Goto\n"
     "BasicBlock 6, pred: 2, succ: 7\n"
     "  12: Return(5)\n"
     "BasicBlock 7, pred: 6\n"
-    "  13: Exit\n";
+    "  13: Exit\n"
+    // Synthesized single back edge of loop.
+    "BasicBlock 8, pred: 5, 4, succ: 2\n"
+    "  14: Phi(1, 2) [5]\n"
+    "  15: Goto\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
@@ -393,7 +408,7 @@
     "  3: Goto\n"
     "BasicBlock 1, pred: 0, succ: 2\n"
     "  4: Goto\n"
-    "BasicBlock 2, pred: 1, 5, succ: 6, 3\n"
+    "BasicBlock 2, pred: 1, 5, succ: 3, 8\n"
     "  5: Phi(0, 1) [12, 6, 6]\n"
     "  6: Equal(5, 5) [7]\n"
     "  7: If(6)\n"
@@ -404,11 +419,13 @@
     "  10: Goto\n"
     "BasicBlock 5, pred: 3, succ: 2\n"
     "  11: Goto\n"
-    "BasicBlock 6, pred: 2, 4, succ: 7\n"
-    "  12: Phi(5, 2) [13]\n"
+    "BasicBlock 6, pred: 4, 8, succ: 7\n"
+    "  12: Phi(2, 5) [13]\n"
     "  13: Return(12)\n"
     "BasicBlock 7, pred: 6\n"
-    "  14: Exit\n";
+    "  14: Exit\n"
+    "BasicBlock 8, pred: 2, succ: 6\n"
+    "  15: Goto\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
diff --git a/runtime/base/bit_vector.cc b/runtime/base/bit_vector.cc
index 0e01dc2..a3e2b15 100644
--- a/runtime/base/bit_vector.cc
+++ b/runtime/base/bit_vector.cc
@@ -399,13 +399,13 @@
   return count;
 }
 
-void BitVector::Dump(std::ostream& os, const char *prefix) {
+void BitVector::Dump(std::ostream& os, const char *prefix) const {
   std::ostringstream buffer;
   DumpHelper(buffer, prefix);
   os << buffer.str() << std::endl;
 }
 
-void BitVector::DumpDot(FILE* file, const char* prefix, bool last_entry) {
+void BitVector::DumpDot(FILE* file, const char* prefix, bool last_entry) const {
   std::ostringstream buffer;
   Dump(buffer, prefix);
 
@@ -421,7 +421,7 @@
   fprintf(file, "\\\n");
 }
 
-void BitVector::DumpHelper(std::ostringstream& buffer, const char* prefix) {
+void BitVector::DumpHelper(std::ostringstream& buffer, const char* prefix) const {
   // Initialize it.
   if (prefix != nullptr) {
     buffer << prefix;
diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h
index 6ee6b00..2a68396 100644
--- a/runtime/base/bit_vector.h
+++ b/runtime/base/bit_vector.h
@@ -148,11 +148,11 @@
 
     bool EnsureSizeAndClear(unsigned int num);
 
-    void Dump(std::ostream& os, const char* prefix);
-    void DumpDot(FILE* file, const char* prefix, bool last_entry = false);
+    void Dump(std::ostream& os, const char* prefix) const;
+    void DumpDot(FILE* file, const char* prefix, bool last_entry = false) const;
 
   protected:
-    void DumpHelper(std::ostringstream& buffer, const char* prefix);
+    void DumpHelper(std::ostringstream& buffer, const char* prefix) const;
 
   private:
     Allocator* const allocator_;