diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index 8b85d71..bbebd3a 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -30,12 +30,12 @@
 namespace art {
 
 void CodeGenerator::Compile(CodeAllocator* allocator) {
-  const GrowableArray<HBasicBlock*>* blocks = GetGraph()->GetBlocks();
-  DCHECK(blocks->Get(0) == GetGraph()->GetEntryBlock());
-  DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks->Get(1)));
+  const GrowableArray<HBasicBlock*>& blocks = GetGraph()->GetBlocks();
+  DCHECK(blocks.Get(0) == GetGraph()->GetEntryBlock());
+  DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks.Get(1)));
   GenerateFrameEntry();
-  for (size_t i = 0; i < blocks->Size(); i++) {
-    CompileBlock(blocks->Get(i));
+  for (size_t i = 0, e = blocks.Size(); i < e; ++i) {
+    CompileBlock(blocks.Get(i));
   }
   size_t code_size = GetAssembler()->CodeSize();
   uint8_t* buffer = allocator->Allocate(code_size);
diff --git a/compiler/optimizing/code_generator.h b/compiler/optimizing/code_generator.h
index 74cbccc..aafd801 100644
--- a/compiler/optimizing/code_generator.h
+++ b/compiler/optimizing/code_generator.h
@@ -354,7 +354,7 @@
         pc_infos_(graph->GetArena(), 32),
         blocked_registers_(static_cast<bool*>(
             graph->GetArena()->Alloc(number_of_registers * sizeof(bool), kArenaAllocData))) {
-    block_labels_.SetSize(graph->GetBlocks()->Size());
+    block_labels_.SetSize(graph->GetBlocks().Size());
   }
   ~CodeGenerator() { }
 
diff --git a/compiler/optimizing/dominator_test.cc b/compiler/optimizing/dominator_test.cc
index 1c30b79..0417050 100644
--- a/compiler/optimizing/dominator_test.cc
+++ b/compiler/optimizing/dominator_test.cc
@@ -32,13 +32,13 @@
   HGraph* graph = builder.BuildGraph(*item);
   ASSERT_NE(graph, nullptr);
   graph->BuildDominatorTree();
-  ASSERT_EQ(graph->GetBlocks()->Size(), blocks_length);
-  for (size_t i = 0; i < blocks_length; i++) {
+  ASSERT_EQ(graph->GetBlocks().Size(), blocks_length);
+  for (size_t i = 0, e = blocks_length; i < e; ++i) {
     if (blocks[i] == -1) {
-      ASSERT_EQ(nullptr, graph->GetBlocks()->Get(i)->GetDominator());
+      ASSERT_EQ(nullptr, graph->GetBlocks().Get(i)->GetDominator());
     } else {
-      ASSERT_NE(nullptr, graph->GetBlocks()->Get(i)->GetDominator());
-      ASSERT_EQ(blocks[i], graph->GetBlocks()->Get(i)->GetDominator()->GetBlockId());
+      ASSERT_NE(nullptr, graph->GetBlocks().Get(i)->GetDominator());
+      ASSERT_EQ(blocks[i], graph->GetBlocks().Get(i)->GetDominator()->GetBlockId());
     }
   }
 }
diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc
new file mode 100644
index 0000000..aa4d35e
--- /dev/null
+++ b/compiler/optimizing/liveness_test.cc
@@ -0,0 +1,515 @@
+/*
+ * 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 "gtest/gtest.h"
+
+namespace art {
+
+static void TestCode(const uint16_t* data, const char* expected) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraphBuilder builder(&allocator);
+  const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
+  HGraph* graph = builder.BuildGraph(*item);
+  ASSERT_NE(graph, nullptr);
+  graph->BuildDominatorTree();
+  graph->TransformToSSA();
+  SsaLivenessAnalysis liveness(*graph);
+  liveness.Analyze();
+
+  std::ostringstream buffer;
+  for (HInsertionOrderIterator it(*graph); !it.Done(); it.Advance()) {
+    HBasicBlock* block = it.Current();
+    buffer << "Block " << block->GetBlockId() << std::endl;
+    BitVector* live_in = liveness.GetLiveInSet(*block);
+    live_in->Dump(buffer, "  live in: ");
+    BitVector* live_out = liveness.GetLiveOutSet(*block);
+    live_out->Dump(buffer, "  live out: ");
+    BitVector* kill = liveness.GetKillSet(*block);
+    kill->Dump(buffer, "  kill: ");
+  }
+  ASSERT_STREQ(expected, buffer.str().c_str());
+}
+
+TEST(LivenessTest, CFG1) {
+  const char* expected =
+    "Block 0\n"
+    "  live in: ()\n"
+    "  live out: ()\n"
+    "  kill: ()\n"
+    "Block 1\n"
+    "  live in: ()\n"
+    "  live out: ()\n"
+    "  kill: ()\n"
+    "Block 2\n"
+    "  live in: ()\n"
+    "  live out: ()\n"
+    "  kill: ()\n";
+
+  // Constant is not used.
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::RETURN_VOID);
+
+  TestCode(data, expected);
+}
+
+TEST(LivenessTest, CFG2) {
+  const char* expected =
+    "Block 0\n"
+    "  live in: (0)\n"
+    "  live out: (1)\n"
+    "  kill: (1)\n"
+    "Block 1\n"
+    "  live in: (1)\n"
+    "  live out: (0)\n"
+    "  kill: (0)\n"
+    "Block 2\n"
+    "  live in: (0)\n"
+    "  live out: (0)\n"
+    "  kill: (0)\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::RETURN);
+
+  TestCode(data, expected);
+}
+
+TEST(LivenessTest, CFG3) {
+  const char* expected =
+    "Block 0\n"  // entry block
+    "  live in: (000)\n"
+    "  live out: (110)\n"
+    "  kill: (110)\n"
+    "Block 1\n"  // block with add
+    "  live in: (110)\n"
+    "  live out: (001)\n"
+    "  kill: (001)\n"
+    "Block 2\n"  // block with return
+    "  live in: (001)\n"
+    "  live out: (000)\n"
+    "  kill: (000)\n"
+    "Block 3\n"  // exit block
+    "  live in: (000)\n"
+    "  live out: (000)\n"
+    "  kill: (000)\n";
+
+  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);
+
+  TestCode(data, expected);
+}
+
+TEST(LivenessTest, CFG4) {
+  // var a;
+  // if (0 == 0) {
+  //   a = 5;
+  // } else {
+  //   a = 4;
+  // }
+  // return a;
+  //
+  // Bitsets are made of:
+  // (constant0, constant4, constant5, phi, equal test)
+  const char* expected =
+    "Block 0\n"  // entry block
+    "  live in: (00000)\n"
+    "  live out: (11100)\n"
+    "  kill: (11100)\n"
+    "Block 1\n"  // block with if
+    "  live in: (11100)\n"
+    "  live out: (01100)\n"
+    "  kill: (00010)\n"
+    "Block 2\n"  // else block
+    "  live in: (01000)\n"
+    "  live out: (00000)\n"
+    "  kill: (00000)\n"
+    "Block 3\n"  // then block
+    "  live in: (00100)\n"
+    "  live out: (00000)\n"
+    "  kill: (00000)\n"
+    "Block 4\n"  // return block
+    "  live in: (00000)\n"
+    "  live out: (00000)\n"
+    "  kill: (00001)\n"
+    "Block 5\n"  // exit block
+    "  live in: (00000)\n"
+    "  live out: (00000)\n"
+    "  kill: (00000)\n";
+
+  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);
+
+  TestCode(data, expected);
+}
+
+TEST(LivenessTest, CFG5) {
+  // var a = 0;
+  // if (0 == 0) {
+  // } else {
+  //   a = 4;
+  // }
+  // return a;
+  const char* expected =
+    "Block 0\n"  // entry block
+    "  live in: (0000)\n"
+    "  live out: (1100)\n"
+    "  kill: (1100)\n"
+    "Block 1\n"  // block with if
+    "  live in: (1100)\n"
+    "  live out: (0100)\n"
+    "  kill: (0010)\n"
+    "Block 2\n"  // else block
+    "  live in: (0100)\n"
+    "  live out: (0000)\n"
+    "  kill: (0000)\n"
+    "Block 3\n"  // return block
+    "  live in: (0000)\n"
+    "  live out: (0000)\n"
+    "  kill: (0001)\n"
+    "Block 4\n"  // exit block
+    "  live in: (0000)\n"
+    "  live out: (0000)\n"
+    "  kill: (0000)\n";
+
+  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);
+
+  TestCode(data, expected);
+}
+
+TEST(LivenessTest, Loop1) {
+  // Simple loop with one preheader and one back edge.
+  // var a = 0;
+  // while (a == a) {
+  //   a = 4;
+  // }
+  // return;
+  const char* expected =
+    "Block 0\n"  // entry block
+    "  live in: (0000)\n"
+    "  live out: (1100)\n"
+    "  kill: (1100)\n"
+    "Block 1\n"  // pre header
+    "  live in: (1100)\n"
+    "  live out: (0100)\n"
+    "  kill: (0000)\n"
+    "Block 2\n"  // loop header
+    "  live in: (0100)\n"
+    "  live out: (0100)\n"
+    "  kill: (0011)\n"
+    "Block 3\n"  // back edge
+    "  live in: (0100)\n"
+    "  live out: (0100)\n"
+    "  kill: (0000)\n"
+    "Block 4\n"  // return block
+    "  live in: (0000)\n"
+    "  live out: (0000)\n"
+    "  kill: (0000)\n"
+    "Block 5\n"  // exit block
+    "  live in: (0000)\n"
+    "  live out: (0000)\n"
+    "  kill: (0000)\n";
+
+
+  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 | 0xFD00,
+    Instruction::RETURN_VOID);
+
+  TestCode(data, expected);
+}
+
+TEST(LivenessTest, Loop3) {
+  // Test that the returned value stays live in a preceding loop.
+  // var a = 0;
+  // while (a == a) {
+  //   a = 4;
+  // }
+  // return 5;
+  const char* expected =
+    "Block 0\n"
+    "  live in: (00000)\n"
+    "  live out: (11100)\n"
+    "  kill: (11100)\n"
+    "Block 1\n"
+    "  live in: (11100)\n"
+    "  live out: (01100)\n"
+    "  kill: (00000)\n"
+    "Block 2\n"  // loop header
+    "  live in: (01100)\n"
+    "  live out: (01100)\n"
+    "  kill: (00011)\n"
+    "Block 3\n"  // back edge
+    "  live in: (01100)\n"
+    "  live out: (01100)\n"
+    "  kill: (00000)\n"
+    "Block 4\n"  // return block
+    "  live in: (00100)\n"
+    "  live out: (00000)\n"
+    "  kill: (00000)\n"
+    "Block 5\n"  // exit block
+    "  live in: (00000)\n"
+    "  live out: (00000)\n"
+    "  kill: (00000)\n";
+
+  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::GOTO | 0xFD00,
+    Instruction::CONST_4 | 5 << 12 | 1 << 8,
+    Instruction::RETURN | 1 << 8);
+
+  TestCode(data, expected);
+}
+
+
+TEST(LivenessTest, Loop4) {
+  // 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) {
+  //   a = 4;
+  // }
+  // return a;
+  // Bitsets are made of:
+  // (constant0, constant4, phi, equal test)
+  const char* expected =
+    "Block 0\n"
+    "  live in: (0000)\n"
+    "  live out: (1100)\n"
+    "  kill: (1100)\n"
+    "Block 1\n"
+    "  live in: (1100)\n"
+    "  live out: (1100)\n"
+    "  kill: (0000)\n"
+    "Block 2\n"  // loop header
+    "  live in: (0100)\n"
+    "  live out: (0110)\n"
+    "  kill: (0011)\n"
+    "Block 3\n"  // back edge
+    "  live in: (0100)\n"
+    "  live out: (0100)\n"
+    "  kill: (0000)\n"
+    "Block 4\n"  // pre loop header
+    "  live in: (1100)\n"
+    "  live out: (0100)\n"
+    "  kill: (0000)\n"
+    "Block 5\n"  // return block
+    "  live in: (0010)\n"
+    "  live out: (0000)\n"
+    "  kill: (0000)\n"
+    "Block 6\n"  // exit block
+    "  live in: (0000)\n"
+    "  live out: (0000)\n"
+    "  kill: (0000)\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::GOTO | 0x500,
+    Instruction::IF_EQ, 5,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::GOTO | 0xFD00,
+    Instruction::GOTO | 0xFC00,
+    Instruction::RETURN | 0 << 8);
+
+  TestCode(data, expected);
+}
+
+TEST(LivenessTest, Loop5) {
+  // Make sure we create a preheader of a loop when a header originally has two
+  // incoming blocks and one back edge.
+  // Bitsets are made of:
+  // (constant0, constant4, constant5, equal in block 1, phi in block 8, phi in block 4,
+  //  equal in block 4)
+  const char* expected =
+    "Block 0\n"
+    "  live in: (0000000)\n"
+    "  live out: (1110000)\n"
+    "  kill: (1110000)\n"
+    "Block 1\n"
+    "  live in: (1110000)\n"
+    "  live out: (0110000)\n"
+    "  kill: (0001000)\n"
+    "Block 2\n"
+    "  live in: (0100000)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000000)\n"
+    "Block 3\n"
+    "  live in: (0010000)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000000)\n"
+    "Block 4\n"  // loop header
+    "  live in: (0000000)\n"
+    "  live out: (0000010)\n"
+    "  kill: (0000011)\n"
+    "Block 5\n"  // back edge
+    "  live in: (0000010)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000000)\n"
+    "Block 6\n"  // return block
+    "  live in: (0000010)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000000)\n"
+    "Block 7\n"  // exit block
+    "  live in: (0000000)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000000)\n"
+    "Block 8\n"  // synthesized pre header
+    "  live in: (0000000)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000100)\n";
+
+  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::IF_EQ, 3,
+    Instruction::GOTO | 0xFE00,
+    Instruction::RETURN | 0 << 8);
+
+  TestCode(data, expected);
+}
+
+TEST(LivenessTest, Loop6) {
+  // Bitsets are made of:
+  // (constant0, constant4, constant5, phi in block 2, equal in block 2, equal in block 3)
+  const char* expected =
+    "Block 0\n"
+    "  live in: (000000)\n"
+    "  live out: (111000)\n"
+    "  kill: (111000)\n"
+    "Block 1\n"
+    "  live in: (111000)\n"
+    "  live out: (011000)\n"
+    "  kill: (000000)\n"
+    "Block 2\n"  // loop header
+    "  live in: (011000)\n"
+    "  live out: (011100)\n"
+    "  kill: (000110)\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"
+    "Block 6\n"  // return block
+    "  live in: (000100)\n"
+    "  live out: (000000)\n"
+    "  kill: (000000)\n"
+    "Block 7\n"  // exit block
+    "  live in: (000000)\n"
+    "  live out: (000000)\n"
+    "  kill: (000000)\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 8,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::CONST_4 | 5 << 12 | 0,
+    Instruction::GOTO | 0xFA00,
+    Instruction::GOTO | 0xF900,
+    Instruction::RETURN | 0 << 8);
+
+  TestCode(data, expected);
+}
+
+
+TEST(LivenessTest, Loop7) {
+  // Bitsets are made of:
+  // (constant0, constant4, constant5, phi in block 2, equal in block 2, equal in block 3,
+  //  phi in block 6)
+  const char* expected =
+    "Block 0\n"
+    "  live in: (0000000)\n"
+    "  live out: (1110000)\n"
+    "  kill: (1110000)\n"
+    "Block 1\n"
+    "  live in: (1110000)\n"
+    "  live out: (0110000)\n"
+    "  kill: (0000000)\n"
+    "Block 2\n"  // loop header
+    "  live in: (0110000)\n"
+    "  live out: (0110000)\n"
+    "  kill: (0001100)\n"
+    "Block 3\n"
+    "  live in: (0110000)\n"
+    "  live out: (0110000)\n"
+    "  kill: (0000010)\n"
+    "Block 4\n"  // loop exit
+    "  live in: (0010000)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000000)\n"
+    "Block 5\n"  // back edge
+    "  live in: (0110000)\n"
+    "  live out: (0110000)\n"
+    "  kill: (0000000)\n"
+    "Block 6\n"  // return block
+    "  live in: (0000000)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000001)\n"
+    "Block 7\n"  // exit block
+    "  live in: (0000000)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000000)\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 8,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::CONST_4 | 5 << 12 | 0,
+    Instruction::GOTO | 0x0200,
+    Instruction::GOTO | 0xF900,
+    Instruction::RETURN | 0 << 8);
+
+  TestCode(data, expected);
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 3d6aeb7..d153bf7 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -25,7 +25,7 @@
   blocks_.Add(block);
 }
 
-void HGraph::FindBackEdges(ArenaBitVector* visited) const {
+void HGraph::FindBackEdges(ArenaBitVector* visited) {
   ArenaBitVector visiting(arena_, blocks_.Size(), false);
   VisitBlockForBackEdges(entry_block_, visited, &visiting);
 }
@@ -49,7 +49,7 @@
 
 void HGraph::VisitBlockForBackEdges(HBasicBlock* block,
                                     ArenaBitVector* visited,
-                                    ArenaBitVector* visiting) const {
+                                    ArenaBitVector* visiting) {
   int id = block->GetBlockId();
   if (visited->IsBitSet(id)) return;
 
@@ -63,6 +63,7 @@
       VisitBlockForBackEdges(successor, visited, visiting);
     }
   }
+  post_order_.Add(block);
   visiting->ClearBit(id);
 }
 
@@ -82,7 +83,6 @@
   //     have been processed.
   GrowableArray<size_t> visits(arena_, blocks_.Size());
   visits.SetSize(blocks_.Size());
-  dominator_order_.Add(entry_block_);
   for (size_t i = 0; i < entry_block_->GetSuccessors()->Size(); i++) {
     VisitBlockForDominatorTree(entry_block_->GetSuccessors()->Get(i), entry_block_, &visits);
   }
@@ -120,7 +120,6 @@
   // dominator of the block. We can then start visiting its successors.
   if (visits->Get(block->GetBlockId()) ==
       block->GetPredecessors()->Size() - block->NumberOfBackEdges()) {
-    dominator_order_.Add(block);
     for (size_t i = 0; i < block->GetSuccessors()->Size(); i++) {
       VisitBlockForDominatorTree(block->GetSuccessors()->Get(i), block, visits);
     }
@@ -128,15 +127,15 @@
 }
 
 void HGraph::TransformToSSA() {
-  DCHECK(!dominator_order_.IsEmpty());
+  DCHECK(!post_order_.IsEmpty());
   SimplifyCFG();
   SsaBuilder ssa_builder(this);
   ssa_builder.BuildSsa();
 }
 
 void HGraph::SimplifyCFG() {
-  for (size_t i = 0; i < dominator_order_.Size(); i++) {
-    HBasicBlock* current = dominator_order_.Get(i);
+  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
@@ -149,10 +148,9 @@
         pre_header->AddInstruction(new (arena_) HGoto());
         pre_header->SetDominator(current->GetDominator());
         current->SetDominator(pre_header);
-        dominator_order_.InsertAt(i, pre_header);
-        i++;
+        post_order_.InsertAt(i, pre_header);
 
-        ArenaBitVector back_edges(arena_, GetBlocks()->Size(), false);
+        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());
         }
@@ -298,9 +296,9 @@
 #undef DEFINE_ACCEPT
 
 void HGraphVisitor::VisitInsertionOrder() {
-  const GrowableArray<HBasicBlock*>* blocks = graph_->GetBlocks();
-  for (size_t i = 0 ; i < blocks->Size(); i++) {
-    VisitBasicBlock(blocks->Get(i));
+  const GrowableArray<HBasicBlock*>& blocks = graph_->GetBlocks();
+  for (size_t i = 0 ; i < blocks.Size(); i++) {
+    VisitBasicBlock(blocks.Get(i));
   }
 }
 
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 581c1d5..bd3d703 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -49,6 +49,7 @@
 
   friend class HBasicBlock;
   friend class HInstructionIterator;
+  friend class HBackwardInstructionIterator;
 
   DISALLOW_COPY_AND_ASSIGN(HInstructionList);
 };
@@ -59,14 +60,14 @@
   explicit HGraph(ArenaAllocator* arena)
       : arena_(arena),
         blocks_(arena, kDefaultNumberOfBlocks),
-        dominator_order_(arena, kDefaultNumberOfBlocks),
+        post_order_(arena, kDefaultNumberOfBlocks),
         maximum_number_of_out_vregs_(0),
         number_of_vregs_(0),
         number_of_in_vregs_(0),
         current_instruction_id_(0) { }
 
   ArenaAllocator* GetArena() const { return arena_; }
-  const GrowableArray<HBasicBlock*>* GetBlocks() const { return &blocks_; }
+  const GrowableArray<HBasicBlock*>& GetBlocks() const { return blocks_; }
 
   HBasicBlock* GetEntryBlock() const { return entry_block_; }
   HBasicBlock* GetExitBlock() const { return exit_block_; }
@@ -108,8 +109,8 @@
     return number_of_in_vregs_;
   }
 
-  GrowableArray<HBasicBlock*>* GetDominatorOrder() {
-    return &dominator_order_;
+  const GrowableArray<HBasicBlock*>& GetPostOrder() const {
+    return post_order_;
   }
 
  private:
@@ -117,10 +118,10 @@
   void VisitBlockForDominatorTree(HBasicBlock* block,
                                   HBasicBlock* predecessor,
                                   GrowableArray<size_t>* visits);
-  void FindBackEdges(ArenaBitVector* visited) const;
+  void FindBackEdges(ArenaBitVector* visited);
   void VisitBlockForBackEdges(HBasicBlock* block,
                               ArenaBitVector* visited,
-                              ArenaBitVector* visiting) const;
+                              ArenaBitVector* visiting);
   void RemoveDeadBlocks(const ArenaBitVector& visited) const;
 
   ArenaAllocator* const arena_;
@@ -128,8 +129,8 @@
   // List of blocks in insertion order.
   GrowableArray<HBasicBlock*> blocks_;
 
-  // List of blocks to perform a pre-order dominator tree traversal.
-  GrowableArray<HBasicBlock*> dominator_order_;
+  // List of blocks to perform a post order tree traversal.
+  GrowableArray<HBasicBlock*> post_order_;
 
   HBasicBlock* entry_block_;
   HBasicBlock* exit_block_;
@@ -322,6 +323,7 @@
         next_(nullptr),
         block_(nullptr),
         id_(-1),
+        ssa_index_(-1),
         uses_(nullptr),
         env_uses_(nullptr),
         environment_(nullptr),
@@ -360,11 +362,17 @@
   HUseListNode<HInstruction>* GetUses() const { return uses_; }
   HUseListNode<HEnvironment>* GetEnvUses() const { return env_uses_; }
 
-  bool HasUses() const { return uses_ != nullptr; }
+  bool HasUses() const { return uses_ != nullptr || env_uses_ != nullptr; }
 
   int GetId() const { return id_; }
   void SetId(int id) { id_ = id; }
 
+  int GetSsaIndex() const { return ssa_index_; }
+  void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; }
+  bool HasSsaIndex() const { return ssa_index_ != -1; }
+
+  bool HasEnvironment() const { return environment_ != nullptr; }
+  HEnvironment* GetEnvironment() const { return environment_; }
   void SetEnvironment(HEnvironment* environment) { environment_ = environment; }
 
   LocationSummary* GetLocations() const { return locations_; }
@@ -388,6 +396,9 @@
   // has not beed added to the graph.
   int id_;
 
+  // When doing liveness analysis, instructions that have uses get an SSA index.
+  int ssa_index_;
+
   // List of instructions that have this instruction as input.
   HUseListNode<HInstruction>* uses_;
 
@@ -496,6 +507,25 @@
   HInstruction* next_;
 };
 
+class HBackwardInstructionIterator : public ValueObject {
+ public:
+  explicit HBackwardInstructionIterator(const HInstructionList& instructions)
+      : instruction_(instructions.last_instruction_) {
+    next_ = Done() ? nullptr : instruction_->GetPrevious();
+  }
+
+  bool Done() const { return instruction_ == nullptr; }
+  HInstruction* Current() const { return instruction_; }
+  void Advance() {
+    instruction_ = next_;
+    next_ = Done() ? nullptr : instruction_->GetPrevious();
+  }
+
+ private:
+  HInstruction* instruction_;
+  HInstruction* next_;
+};
+
 // An embedded container with N elements of type T.  Used (with partial
 // specialization for N=0) because embedded arrays cannot have size 0.
 template<typename T, intptr_t N>
@@ -966,6 +996,52 @@
   DISALLOW_COPY_AND_ASSIGN(HGraphVisitor);
 };
 
+class HInsertionOrderIterator : public ValueObject {
+ public:
+  explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {}
+
+  bool Done() const { return index_ == graph_.GetBlocks().Size(); }
+  HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); }
+  void Advance() { ++index_; }
+
+ private:
+  const HGraph& graph_;
+  size_t index_;
+
+  DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator);
+};
+
+class HPostOrderIterator : public ValueObject {
+ public:
+  explicit HPostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {}
+
+  bool Done() const { return index_ == graph_.GetPostOrder().Size(); }
+  HBasicBlock* Current() const { return graph_.GetPostOrder().Get(index_); }
+  void Advance() { ++index_; }
+
+ private:
+  const HGraph& graph_;
+  size_t index_;
+
+  DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator);
+};
+
+class HReversePostOrderIterator : public ValueObject {
+ public:
+  explicit HReversePostOrderIterator(const HGraph& graph)
+      : graph_(graph), index_(graph_.GetPostOrder().Size()) {}
+
+  bool Done() const { return index_ == 0; }
+  HBasicBlock* Current() const { return graph_.GetPostOrder().Get(index_ - 1); }
+  void Advance() { --index_; }
+
+ private:
+  const HGraph& graph_;
+  size_t index_;
+
+  DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator);
+};
+
 }  // namespace art
 
 #endif  // ART_COMPILER_OPTIMIZING_NODES_H_
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 9438890..4c75cd4 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -22,6 +22,7 @@
 #include "driver/compiler_driver.h"
 #include "driver/dex_compilation_unit.h"
 #include "nodes.h"
+#include "ssa_liveness_analysis.h"
 #include "utils/arena_allocator.h"
 
 namespace art {
@@ -103,6 +104,7 @@
   // Run these phases to get some test coverage.
   graph->BuildDominatorTree();
   graph->TransformToSSA();
+  SsaLivenessAnalysis(*graph).Analyze();
 
   return new CompiledMethod(driver,
                             instruction_set,
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index bfb4f38..ee1e1e4 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -20,11 +20,11 @@
 namespace art {
 
 void SsaBuilder::BuildSsa() {
-  // 1) Visit in dominator order. We need to have all predecessors of a block visited
+  // 1) Visit in reverse post order. We need to have all predecessors of a block visited
   // (with the exception of loops) in order to create the right environment for that
   // block. For loops, we create phis whose inputs will be set in 2).
-  for (size_t i = 0; i < GetGraph()->GetDominatorOrder()->Size(); i++) {
-    VisitBasicBlock(GetGraph()->GetDominatorOrder()->Get(i));
+  for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
+    VisitBasicBlock(it.Current());
   }
 
   // 2) Set inputs of loop phis.
@@ -59,7 +59,7 @@
 
   if (block->IsLoopHeader()) {
     // If the block is a loop header, we know we only have visited the pre header
-    // because we are visiting in dominator order. We create phis for all initialized
+    // because we are visiting in reverse post order. We create phis for all initialized
     // locals from the pre header. Their inputs will be populated at the end of
     // the analysis.
     for (size_t local = 0; local < current_locals_->Size(); local++) {
@@ -76,7 +76,7 @@
     // blocks need to be updated.
     loop_headers_.Add(block);
   } else if (block->GetPredecessors()->Size() > 0) {
-    // All predecessors have already been visited because we are visiting in dominator order.
+    // 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;
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index b6c6c0b..9d8c072 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -29,8 +29,8 @@
       : HGraphVisitor(graph),
         current_locals_(nullptr),
         loop_headers_(graph->GetArena(), kDefaultNumberOfLoops),
-        locals_for_(graph->GetArena(), graph->GetBlocks()->Size()) {
-    locals_for_.SetSize(graph->GetBlocks()->Size());
+        locals_for_(graph->GetArena(), graph->GetBlocks().Size()) {
+    locals_for_.SetSize(graph->GetBlocks().Size());
   }
 
   void BuildSsa();
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
new file mode 100644
index 0000000..838597d
--- /dev/null
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -0,0 +1,170 @@
+/*
+ * 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 "ssa_liveness_analysis.h"
+#include "nodes.h"
+
+namespace art {
+
+void SsaLivenessAnalysis::Analyze() {
+  NumberInstructions();
+  ComputeSets();
+}
+
+void SsaLivenessAnalysis::NumberInstructions() {
+  int ssa_index = 0;
+  for (HReversePostOrderIterator it(graph_); !it.Done(); it.Advance()) {
+    HBasicBlock* block = it.Current();
+
+    for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
+      HInstruction* current = it.Current();
+      if (current->HasUses()) {
+        current->SetSsaIndex(ssa_index++);
+      }
+    }
+
+    for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
+      HInstruction* current = it.Current();
+      if (current->HasUses()) {
+        current->SetSsaIndex(ssa_index++);
+      }
+    }
+  }
+  number_of_ssa_values_ = ssa_index;
+}
+
+void SsaLivenessAnalysis::ComputeSets() {
+  for (HReversePostOrderIterator it(graph_); !it.Done(); it.Advance()) {
+    HBasicBlock* block = it.Current();
+    block_infos_.Put(
+        block->GetBlockId(),
+        new (graph_.GetArena()) BlockInfo(graph_.GetArena(), *block, number_of_ssa_values_));
+  }
+
+  // Compute the initial live_in, live_out, and kill sets. This method does not handle
+  // backward branches, therefore live_in and live_out sets are not yet correct.
+  ComputeInitialSets();
+
+  // Do a fixed point calculation to take into account backward branches,
+  // that will update live_in of loop headers, and therefore live_out and live_in
+  // of blocks in the loop.
+  ComputeLiveInAndLiveOutSets();
+}
+
+void SsaLivenessAnalysis::ComputeInitialSets() {
+  // Do a post orderr visit, adding inputs of instructions live in the block where
+  // that instruction is defined, and killing instructions that are being visited.
+  for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) {
+    HBasicBlock* block = it.Current();
+
+    BitVector* kill = GetKillSet(*block);
+    BitVector* live_in = GetLiveInSet(*block);
+
+    for (HBackwardInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
+      HInstruction* current = it.Current();
+      if (current->HasSsaIndex()) {
+        kill->SetBit(current->GetSsaIndex());
+        live_in->ClearBit(current->GetSsaIndex());
+      }
+
+      // All inputs of an instruction must be live.
+      for (size_t i = 0, e = current->InputCount(); i < e; ++i) {
+        DCHECK(current->InputAt(i)->HasSsaIndex());
+        live_in->SetBit(current->InputAt(i)->GetSsaIndex());
+      }
+
+      if (current->HasEnvironment()) {
+        // All instructions in the environment must be live.
+        GrowableArray<HInstruction*>* environment = current->GetEnvironment()->GetVRegs();
+        for (size_t i = 0, e = environment->Size(); i < e; ++i) {
+          HInstruction* instruction = environment->Get(i);
+          if (instruction != nullptr) {
+            DCHECK(instruction->HasSsaIndex());
+            live_in->SetBit(instruction->GetSsaIndex());
+          }
+        }
+      }
+    }
+
+    for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
+      HInstruction* current = it.Current();
+      if (current->HasSsaIndex()) {
+        kill->SetBit(current->GetSsaIndex());
+        live_in->ClearBit(current->GetSsaIndex());
+      }
+
+      // Mark a phi input live_in for its corresponding predecessor.
+      for (size_t i = 0, e = current->InputCount(); i < e; ++i) {
+        HInstruction* input = current->InputAt(i);
+
+        HBasicBlock* predecessor = block->GetPredecessors()->Get(i);
+        size_t ssa_index = input->GetSsaIndex();
+        BitVector* predecessor_kill = GetKillSet(*predecessor);
+        BitVector* predecessor_live_in = GetLiveInSet(*predecessor);
+
+        // Phi inputs from a back edge have already been visited. If the back edge
+        // block defines that input, we should not add it to its live_in.
+        if (!predecessor_kill->IsBitSet(ssa_index)) {
+          predecessor_live_in->SetBit(ssa_index);
+        }
+      }
+    }
+  }
+}
+
+void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() {
+  bool changed;
+  do {
+    changed = false;
+
+    for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) {
+      const HBasicBlock& block = *it.Current();
+
+      // The live_in set depends on the kill set (which does not
+      // change in this loop), and the live_out set.  If the live_out
+      // set does not change, there is no need to update the live_in set.
+      if (UpdateLiveOut(block) && UpdateLiveIn(block)) {
+        changed = true;
+      }
+    }
+  } while (changed);
+}
+
+bool SsaLivenessAnalysis::UpdateLiveOut(const HBasicBlock& block) {
+  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);
+    if (live_out->Union(GetLiveInSet(*successor))) {
+      changed = true;
+    }
+  }
+  return changed;
+}
+
+
+bool SsaLivenessAnalysis::UpdateLiveIn(const HBasicBlock& block) {
+  BitVector* live_out = GetLiveOutSet(block);
+  BitVector* kill = GetKillSet(block);
+  BitVector* live_in = GetLiveInSet(block);
+  // If live_out is updated (because of backward branches), we need to make
+  // sure instructions in live_out are also in live_in, unless they are killed
+  // by this block.
+  return live_in->UnionIfNotIn(live_out, kill);
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
new file mode 100644
index 0000000..6a901d1
--- /dev/null
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -0,0 +1,101 @@
+/*
+ * 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.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_
+#define ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_
+
+#include "nodes.h"
+
+namespace art {
+
+class BlockInfo : public ArenaObject {
+ public:
+  BlockInfo(ArenaAllocator* allocator, const HBasicBlock& block, size_t number_of_ssa_values)
+      : block_(block),
+        live_in_(allocator, number_of_ssa_values, false),
+        live_out_(allocator, number_of_ssa_values, false),
+        kill_(allocator, number_of_ssa_values, false) {
+    live_in_.ClearAllBits();
+    live_out_.ClearAllBits();
+    kill_.ClearAllBits();
+  }
+
+ private:
+  const HBasicBlock& block_;
+  ArenaBitVector live_in_;
+  ArenaBitVector live_out_;
+  ArenaBitVector kill_;
+
+  friend class SsaLivenessAnalysis;
+
+  DISALLOW_COPY_AND_ASSIGN(BlockInfo);
+};
+
+class SsaLivenessAnalysis : public ValueObject {
+ public:
+  explicit SsaLivenessAnalysis(const HGraph& graph)
+      : graph_(graph),
+        block_infos_(graph.GetArena(), graph.GetBlocks().Size()),
+        number_of_ssa_values_(0) {
+    block_infos_.SetSize(graph.GetBlocks().Size());
+  }
+
+  void Analyze();
+
+  BitVector* GetLiveInSet(const HBasicBlock& block) const {
+    return &block_infos_.Get(block.GetBlockId())->live_in_;
+  }
+
+  BitVector* GetLiveOutSet(const HBasicBlock& block) const {
+    return &block_infos_.Get(block.GetBlockId())->live_out_;
+  }
+
+  BitVector* GetKillSet(const HBasicBlock& block) const {
+    return &block_infos_.Get(block.GetBlockId())->kill_;
+  }
+
+ private:
+  // Give an SSA number to each instruction that defines a value used by another instruction.
+  void NumberInstructions();
+
+  // Compute live_in, live_out and kill sets.
+  void ComputeSets();
+
+  // Compute the initial live_in, live_out and kill sets, without analyzing
+  // backward branches.
+  void ComputeInitialSets();
+
+  // After computing the initial sets, this method does a fixed point
+  // calculation over the live_in and live_out set to take into account
+  // backwards branches.
+  void ComputeLiveInAndLiveOutSets();
+
+  // Update the live_in set of the block and returns whether it has changed.
+  bool UpdateLiveIn(const HBasicBlock& block);
+
+  // Update the live_out set of the block and returns whether it has changed.
+  bool UpdateLiveOut(const HBasicBlock& block);
+
+  const HGraph& graph_;
+  GrowableArray<BlockInfo*> block_infos_;
+  size_t number_of_ssa_values_;
+
+  DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_
diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc
index 7c3633b..e4aafb7 100644
--- a/compiler/optimizing/ssa_test.cc
+++ b/compiler/optimizing/ssa_test.cc
@@ -64,8 +64,8 @@
 
 static void ReNumberInstructions(HGraph* graph) {
   int id = 0;
-  for (size_t i = 0; i < graph->GetBlocks()->Size(); i++) {
-    HBasicBlock* block = graph->GetBlocks()->Get(i);
+  for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
+    HBasicBlock* block = graph->GetBlocks().Get(i);
     for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
       it.Current()->SetId(id++);
     }
@@ -147,7 +147,7 @@
 
 TEST(SsaTest, CFG3) {
   // Test that we create a phi for the join block of an if control flow instruction
-  // when there both branches update a local.
+  // when both branches update a local.
   const char* expected =
     "BasicBlock 0, succ: 1\n"
     "  0: IntConstant 0 [4, 4]\n"