Build live-in, live-out and kill sets for each block.

This information will be used when computing live ranges of
instructions.

Change-Id: I345ee833c1ccb4a8e725c7976453f6d58d350d74

16 files changed, 981 insertions, 55 deletions

diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 429c523..d4e2cbb 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -78,6 +78,7 @@ COMPILER_GTEST_COMMON_SRC_FILES := \
 	compiler/oat_test.cc \
 	compiler/optimizing/codegen_test.cc \
 	compiler/optimizing/dominator_test.cc \
+	compiler/optimizing/liveness_test.cc \
 	compiler/optimizing/pretty_printer_test.cc \
 	compiler/optimizing/ssa_test.cc \
 	compiler/output_stream_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index e3201e7..a993251 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -79,6 +79,7 @@ LIBART_COMPILER_SRC_FILES := \
 	optimizing/nodes.cc \
 	optimizing/optimizing_compiler.cc \
 	optimizing/ssa_builder.cc \
+	optimizing/ssa_liveness_analysis.cc \
 	trampolines/trampoline_compiler.cc \
 	utils/arena_allocator.cc \
 	utils/arena_bit_vector.cc \
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 @@ class CodeGenerator : public ArenaObject {
         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 @@ static void TestCode(const uint16_t* data, const int* blocks, size_t blocks_leng
   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 @@ void HGraph::AddBlock(HBasicBlock* block) {
   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::RemoveDeadBlocks(const ArenaBitVector& visited) const {
 
 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 @@ void HGraph::VisitBlockForBackEdges(HBasicBlock* block,
       VisitBlockForBackEdges(successor, visited, visiting);
     }
   }
+  post_order_.Add(block);
   visiting->ClearBit(id);
 }
 
@@ -82,7 +83,6 @@ void HGraph::BuildDominatorTree() {
   //     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 @@ void HGraph::VisitBlockForDominatorTree(HBasicBlock* block,
   // 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::VisitBlockForDominatorTree(HBasicBlock* block,
 }
 
 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 @@ void HGraph::SimplifyCFG() {
         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 @@ FOR_EACH_INSTRUCTION(DEFINE_ACCEPT)
 #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 @@ class HInstructionList {
 
   friend class HBasicBlock;
   friend class HInstructionIterator;
+  friend class HBackwardInstructionIterator;
 
   DISALLOW_COPY_AND_ASSIGN(HInstructionList);
 };
@@ -59,14 +60,14 @@ class HGraph : public ArenaObject {
   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 @@ class HGraph : public ArenaObject {
     return number_of_in_vregs_;
   }
 
-  GrowableArray<HBasicBlock*>* GetDominatorOrder() {
-    return &dominator_order_;
+  const GrowableArray<HBasicBlock*>& GetPostOrder() const {
+    return post_order_;
   }
 
  private:
@@ -117,10 +118,10 @@ class HGraph : public ArenaObject {
   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 @@ class HGraph : public ArenaObject {
   // 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 @@ class HInstruction : public ArenaObject {
         next_(nullptr),
         block_(nullptr),
         id_(-1),
+        ssa_index_(-1),
         uses_(nullptr),
         env_uses_(nullptr),
         environment_(nullptr),
@@ -360,11 +362,17 @@ class HInstruction : public ArenaObject {
   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 @@ class HInstruction : public ArenaObject {
   // 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 @@ class HInstructionIterator : public ValueObject {
   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 @@ class HGraphVisitor : public ValueObject {
   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 @@ CompiledMethod* OptimizingCompiler::TryCompile(CompilerDriver& driver,
   // 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 @@ void SsaBuilder::VisitBasicBlock(HBasicBlock* block) {
 
   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 @@ void SsaBuilder::VisitBasicBlock(HBasicBlock* block) {
     // 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 @@ class SsaBuilder : public HGraphVisitor {
       : 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 @@ class StringPrettyPrinter : public HPrettyPrinter {
 
 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, CFG2) {
 
 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"
diff --git a/runtime/base/bit_vector.cc b/runtime/base/bit_vector.cc
index 3df5101..47e85a3 100644
--- a/runtime/base/bit_vector.cc
+++ b/runtime/base/bit_vector.cc
@@ -43,7 +43,8 @@ BitVector::BitVector(uint32_t start_bits,
   : allocator_(allocator),
     expandable_(expandable),
     storage_size_(storage_size),
-    storage_(storage) {
+    storage_(storage),
+    number_of_bits_(start_bits) {
   DCHECK_EQ(sizeof(*storage_), 4U);  // Assuming 32-bit units.
   if (storage_ == nullptr) {
     storage_size_ = BitsToWords(start_bits);
@@ -93,6 +94,7 @@ void BitVector::SetBit(uint32_t num) {
     // TOTO: collect stats on space wasted because of resize.
     storage_ = new_storage;
     storage_size_ = new_size;
+    number_of_bits_ = num;
   }
 
   storage_[num >> 5] |= check_masks[num & 0x1f];
@@ -156,13 +158,14 @@ void BitVector::Intersect(const BitVector* src) {
 /*
  * Union with another bit vector.
  */
-void BitVector::Union(const BitVector* src) {
+bool BitVector::Union(const BitVector* src) {
   // Get the highest bit to determine how much we need to expand.
   int highest_bit = src->GetHighestBitSet();
+  bool changed = false;
 
   // If src has no bit set, we are done: there is no need for a union with src.
   if (highest_bit == -1) {
-    return;
+    return changed;
   }
 
   // Update src_size to how many cells we actually care about: where the bit is + 1.
@@ -170,6 +173,8 @@ void BitVector::Union(const BitVector* src) {
 
   // Is the storage size smaller than src's?
   if (storage_size_ < src_size) {
+    changed = true;
+
     // Set it to reallocate.
     SetBit(highest_bit);
 
@@ -178,8 +183,62 @@ void BitVector::Union(const BitVector* src) {
   }
 
   for (uint32_t idx = 0; idx < src_size; idx++) {
-    storage_[idx] |= src->GetRawStorageWord(idx);
+    uint32_t existing = storage_[idx];
+    uint32_t update = existing | src->GetRawStorageWord(idx);
+    if (existing != update) {
+      changed = true;
+      storage_[idx] = update;
+    }
   }
+  return changed;
+}
+
+bool BitVector::UnionIfNotIn(const BitVector* union_with, const BitVector* not_in) {
+  // Get the highest bit to determine how much we need to expand.
+  int highest_bit = union_with->GetHighestBitSet();
+  bool changed = false;
+
+  // If src has no bit set, we are done: there is no need for a union with src.
+  if (highest_bit == -1) {
+    return changed;
+  }
+
+  // Update union_with_size to how many cells we actually care about: where the bit is + 1.
+  uint32_t union_with_size = BitsToWords(highest_bit + 1);
+
+  // Is the storage size smaller than src's?
+  if (storage_size_ < union_with_size) {
+    changed = true;
+
+    // Set it to reallocate.
+    SetBit(highest_bit);
+
+    // Paranoid: storage size should be big enough to hold this bit now.
+    DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * sizeof(*(storage_)) * 8);
+  }
+
+  uint32_t not_in_size = not_in->GetStorageSize();
+
+  uint32_t idx = 0;
+  for (; idx < std::min(not_in_size, union_with_size); idx++) {
+    uint32_t existing = storage_[idx];
+    uint32_t update = existing |
+        (union_with->GetRawStorageWord(idx) & ~not_in->GetRawStorageWord(idx));
+    if (existing != update) {
+      changed = true;
+      storage_[idx] = update;
+    }
+  }
+
+  for (; idx < union_with_size; idx++) {
+    uint32_t existing = storage_[idx];
+    uint32_t update = existing | union_with->GetRawStorageWord(idx);
+    if (existing != update) {
+      changed = true;
+      storage_[idx] = update;
+    }
+  }
+  return changed;
 }
 
 void BitVector::Subtract(const BitVector *src) {
@@ -342,7 +401,7 @@ uint32_t BitVector::NumSetBits(const uint32_t* storage, uint32_t end) {
 void BitVector::Dump(std::ostream& os, const char *prefix) {
   std::ostringstream buffer;
   DumpHelper(buffer, prefix);
-  os << buffer << std::endl;
+  os << buffer.str() << std::endl;
 }
 
 void BitVector::DumpDot(FILE* file, const char* prefix, bool last_entry) {
@@ -367,13 +426,11 @@ void BitVector::DumpHelper(std::ostringstream& buffer, const char* prefix) {
     buffer << prefix;
   }
 
-  int max = GetHighestBitSet();
-
-  for (int i = 0; i <= max; i++) {
-    if (IsBitSet(i)) {
-      buffer << i << " ";
-    }
+  buffer << '(';
+  for (size_t i = 0; i < number_of_bits_; i++) {
+    buffer << IsBitSet(i);
   }
+  buffer << ')';
 }
 
 }  // namespace art
diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h
index db29c49..6ee6b00 100644
--- a/runtime/base/bit_vector.h
+++ b/runtime/base/bit_vector.h
@@ -103,7 +103,11 @@ class BitVector {
 
     void Copy(const BitVector* src);
     void Intersect(const BitVector* src2);
-    void Union(const BitVector* src);
+    bool Union(const BitVector* src);
+
+    // Set bits of union_with that are not in not_in.
+    bool UnionIfNotIn(const BitVector* union_with, const BitVector* not_in);
+
     void Subtract(const BitVector* src);
     // Are we equal to another bit vector?  Note: expandability attributes must also match.
     bool Equal(const BitVector* src) {
@@ -155,6 +159,7 @@ class BitVector {
     const bool expandable_;         // expand bitmap if we run out?
     uint32_t   storage_size_;       // current size, in 32-bit words.
     uint32_t*  storage_;
+    uint32_t number_of_bits_;
 };