diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index b157d8e..7369928 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -81,6 +81,7 @@
 	compiler/optimizing/find_loops_test.cc \
 	compiler/optimizing/linearize_test.cc \
 	compiler/optimizing/liveness_test.cc \
+	compiler/optimizing/live_ranges_test.cc \
 	compiler/optimizing/pretty_printer_test.cc \
 	compiler/optimizing/ssa_test.cc \
 	compiler/output_stream_test.cc \
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index 2c2564d..521992a 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -499,6 +499,7 @@
       break;
     }
 
+    case Instruction::MOVE_RESULT:
     case Instruction::MOVE_RESULT_WIDE: {
       UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction());
       break;
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index b9c1164..52e3e37 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -18,6 +18,7 @@
 
 #include "driver/dex_compilation_unit.h"
 #include "nodes.h"
+#include "ssa_liveness_analysis.h"
 
 namespace art {
 
@@ -102,6 +103,24 @@
       }
       output_ << "]";
     }
+    if (instruction->GetLifetimePosition() != kNoLifetime) {
+      output_ << " (liveness: " << instruction->GetLifetimePosition();
+      if (instruction->HasLiveInterval()) {
+        output_ << " ";
+        const GrowableArray<LiveRange>& ranges = instruction->GetLiveInterval()->GetRanges();
+        size_t i = ranges.Size() - 1;
+        do {
+          output_ << "[" << ranges.Get(i).GetStart() << "," << ranges.Get(i).GetEnd() << "[";
+          if (i == 0) {
+            break;
+          } else {
+            --i;
+            output_ << ",";
+          }
+        } while (true);
+      }
+      output_ << ")";
+    }
   }
 
   void PrintInstructions(const HInstructionList& list) {
@@ -126,8 +145,14 @@
   void VisitBasicBlock(HBasicBlock* block) {
     StartTag("block");
     PrintProperty("name", "B", block->GetBlockId());
-    PrintInt("from_bci", -1);
-    PrintInt("to_bci", -1);
+    if (block->GetLifetimeStart() != kNoLifetime) {
+      // Piggy back on these fields to show the lifetime of the block.
+      PrintInt("from_bci", block->GetLifetimeStart());
+      PrintInt("to_bci", block->GetLifetimeEnd());
+    } else {
+      PrintInt("from_bci", -1);
+      PrintInt("to_bci", -1);
+    }
     PrintPredecessors(block);
     PrintSuccessors(block);
     PrintEmptyProperty("xhandlers");
diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc
new file mode 100644
index 0000000..9849388
--- /dev/null
+++ b/compiler/optimizing/live_ranges_test.cc
@@ -0,0 +1,263 @@
+/*
+ * 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 HGraph* BuildGraph(const uint16_t* data, ArenaAllocator* allocator) {
+  HGraphBuilder builder(allocator);
+  const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
+  HGraph* graph = builder.BuildGraph(*item);
+  graph->BuildDominatorTree();
+  graph->TransformToSSA();
+  graph->FindNaturalLoops();
+  return graph;
+}
+
+TEST(LiveRangesTest, CFG1) {
+  /*
+   * Test the following snippet:
+   *  return 0;
+   *
+   * Which becomes the following graph (numbered by lifetime position):
+   *       2: constant0
+   *       3: goto
+   *           |
+   *       6: return
+   *           |
+   *       9: exit
+   */
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::RETURN);
+
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = BuildGraph(data, &allocator);
+  SsaLivenessAnalysis liveness(*graph);
+  liveness.Analyze();
+
+  LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
+  ASSERT_EQ(1u, interval->GetRanges().Size());
+  LiveRange range = interval->GetRanges().Get(0);
+  ASSERT_EQ(2u, range.GetStart());
+  // Last use is the return instruction.
+  ASSERT_EQ(6u, range.GetEnd());
+  HBasicBlock* block = graph->GetBlocks().Get(1);
+  ASSERT_TRUE(block->GetLastInstruction()->AsReturn() != nullptr);
+  ASSERT_EQ(6u, block->GetLastInstruction()->GetLifetimePosition());
+}
+
+TEST(LiveRangesTest, CFG2) {
+  /*
+   * Test the following snippet:
+   *  var a = 0;
+   *  if (0 == 0) {
+   *  } else {
+   *  }
+   *  return a;
+   *
+   * Which becomes the following graph (numbered by lifetime position):
+   *       2: constant0
+   *       3: goto
+   *           |
+   *       6: equal
+   *       7: if
+   *       /       \
+   *   10: goto   13: goto
+   *       \       /
+   *       16: return
+   *         |
+   *       19: exit
+   */
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0x100,
+    Instruction::RETURN | 0 << 8);
+
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = BuildGraph(data, &allocator);
+  SsaLivenessAnalysis liveness(*graph);
+  liveness.Analyze();
+
+  LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
+  ASSERT_EQ(1u, interval->GetRanges().Size());
+  LiveRange range = interval->GetRanges().Get(0);
+  ASSERT_EQ(2u, range.GetStart());
+  // Last use is the return instruction.
+  ASSERT_EQ(16u, range.GetEnd());
+  HBasicBlock* block = graph->GetBlocks().Get(3);
+  ASSERT_TRUE(block->GetLastInstruction()->AsReturn() != nullptr);
+  ASSERT_EQ(16u, block->GetLastInstruction()->GetLifetimePosition());
+}
+
+TEST(LiveRangesTest, CFG3) {
+  /*
+   * Test the following snippet:
+   *  var a = 0;
+   *  if (0 == 0) {
+   *  } else {
+   *    a = 4;
+   *  }
+   *  return a;
+   *
+   * Which becomes the following graph (numbered by lifetime position):
+   *       2: constant0
+   *       3: constant4
+   *       4: goto
+   *           |
+   *       7: equal
+   *       8: if
+   *       /       \
+   *   11: goto   14: goto
+   *       \       /
+   *       16: phi
+   *       17: return
+   *         |
+   *       20: exit
+   */
+  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 pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = BuildGraph(data, &allocator);
+  SsaLivenessAnalysis liveness(*graph);
+  liveness.Analyze();
+
+  // Test for the 0 constant.
+  LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
+  ASSERT_EQ(1u, interval->GetRanges().Size());
+  LiveRange range = interval->GetRanges().Get(0);
+  ASSERT_EQ(2u, range.GetStart());
+  // Last use is the phi at the return block so instruction is live until
+  // the end of the then block.
+  ASSERT_EQ(12u, range.GetEnd());
+
+  // Test for the 4 constant.
+  interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
+  // The then branch is a hole for this constant, therefore its interval has 2 ranges.
+  ASSERT_EQ(2u, interval->GetRanges().Size());
+  // First range is the else block.
+  range = interval->GetRanges().Get(0);
+  ASSERT_EQ(13u, range.GetStart());
+  // Last use is the phi at the return block.
+  ASSERT_EQ(15u, range.GetEnd());
+  // Second range starts from the definition and ends at the if block.
+  range = interval->GetRanges().Get(1);
+  ASSERT_EQ(3u, range.GetStart());
+  // 9 is the end of the if block.
+  ASSERT_EQ(9u, range.GetEnd());
+
+  // Test for the phi.
+  interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval();
+  ASSERT_EQ(1u, interval->GetRanges().Size());
+  range = interval->GetRanges().Get(0);
+  ASSERT_EQ(16u, range.GetStart());
+  ASSERT_EQ(17u, range.GetEnd());
+}
+
+TEST(LiveRangesTest, Loop) {
+  /*
+   * Test the following snippet:
+   *  var a = 0;
+   *  while (a == a) {
+   *    a = 4;
+   *  }
+   *  return 5;
+   *
+   * Which becomes the following graph (numbered by lifetime position):
+   *       2: constant0
+   *       3: constant4
+   *       4: constant5
+   *       5: goto
+   *           |
+   *       8: goto
+   *           |
+   *       10: phi
+   *       11: equal
+   *       12: if +++++
+   *        |       \ +
+   *        |     15: goto
+   *        |
+   *       18: return
+   *         |
+   *       21: exit
+   */
+
+  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);
+
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = BuildGraph(data, &allocator);
+  SsaLivenessAnalysis liveness(*graph);
+  liveness.Analyze();
+
+  // Test for the 0 constant.
+  LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
+  ASSERT_EQ(1u, interval->GetRanges().Size());
+  LiveRange range = interval->GetRanges().Get(0);
+  ASSERT_EQ(2u, range.GetStart());
+  // Last use is the loop phi so instruction is live until
+  // the end of the pre loop header.
+  ASSERT_EQ(9u, range.GetEnd());
+
+  // Test for the 4 constant.
+  interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
+  // The instruction is live until the end of the loop.
+  ASSERT_EQ(1u, interval->GetRanges().Size());
+  range = interval->GetRanges().Get(0);
+  ASSERT_EQ(3u, range.GetStart());
+  ASSERT_EQ(16u, range.GetEnd());
+
+  // Test for the 5 constant.
+  interval = liveness.GetInstructionFromSsaIndex(2)->GetLiveInterval();
+  // The instruction is live until the return instruction of the loop.
+  ASSERT_EQ(1u, interval->GetRanges().Size());
+  range = interval->GetRanges().Get(0);
+  ASSERT_EQ(4u, range.GetStart());
+  ASSERT_EQ(18u, range.GetEnd());
+
+  // Test for the phi.
+  interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval();
+  ASSERT_EQ(1u, interval->GetRanges().Size());
+  range = interval->GetRanges().Get(0);
+  // Instruction is consumed by the if.
+  ASSERT_EQ(10u, range.GetStart());
+  ASSERT_EQ(11u, range.GetEnd());
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 1085c10..a2cb1c4 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -29,6 +29,7 @@
 class HIntConstant;
 class HGraphVisitor;
 class HPhi;
+class LiveInterval;
 class LocationSummary;
 
 static const int kDefaultNumberOfBlocks = 8;
@@ -223,6 +224,8 @@
   DISALLOW_COPY_AND_ASSIGN(HLoopInformation);
 };
 
+static constexpr size_t kNoLifetime = -1;
+
 // A block in a method. Contains the list of instructions represented
 // as a double linked list. Each block knows its predecessors and
 // successors.
@@ -234,7 +237,9 @@
         successors_(graph->GetArena(), kDefaultNumberOfSuccessors),
         loop_information_(nullptr),
         dominator_(nullptr),
-        block_id_(-1) { }
+        block_id_(-1),
+        lifetime_start_(kNoLifetime),
+        lifetime_end_(kNoLifetime) {}
 
   const GrowableArray<HBasicBlock*>& GetPredecessors() const {
     return predecessors_;
@@ -299,6 +304,15 @@
     block->successors_.Add(this);
   }
 
+  size_t GetPredecessorIndexOf(HBasicBlock* predecessor) {
+    for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) {
+      if (predecessors_.Get(i) == predecessor) {
+        return i;
+      }
+    }
+    return -1;
+  }
+
   void AddInstruction(HInstruction* instruction);
   void RemoveInstruction(HInstruction* instruction);
   void AddPhi(HPhi* phi);
@@ -334,6 +348,12 @@
   // Returns wheter this block dominates the blocked passed as parameter.
   bool Dominates(HBasicBlock* block) const;
 
+  size_t GetLifetimeStart() const { return lifetime_start_; }
+  size_t GetLifetimeEnd() const { return lifetime_end_; }
+
+  void SetLifetimeStart(size_t start) { lifetime_start_ = start; }
+  void SetLifetimeEnd(size_t end) { lifetime_end_ = end; }
+
  private:
   HGraph* const graph_;
   GrowableArray<HBasicBlock*> predecessors_;
@@ -343,6 +363,8 @@
   HLoopInformation* loop_information_;
   HBasicBlock* dominator_;
   int block_id_;
+  size_t lifetime_start_;
+  size_t lifetime_end_;
 
   DISALLOW_COPY_AND_ASSIGN(HBasicBlock);
 };
@@ -407,7 +429,9 @@
         uses_(nullptr),
         env_uses_(nullptr),
         environment_(nullptr),
-        locations_(nullptr) { }
+        locations_(nullptr),
+        live_interval_(nullptr),
+        lifetime_position_(kNoLifetime) {}
 
   virtual ~HInstruction() { }
 
@@ -477,6 +501,12 @@
   FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
 #undef INSTRUCTION_TYPE_CHECK
 
+  size_t GetLifetimePosition() const { return lifetime_position_; }
+  void SetLifetimePosition(size_t position) { lifetime_position_ = position; }
+  LiveInterval* GetLiveInterval() const { return live_interval_; }
+  void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; }
+  bool HasLiveInterval() const { return live_interval_ != nullptr; }
+
  private:
   HInstruction* previous_;
   HInstruction* next_;
@@ -501,6 +531,13 @@
   // Set by the code generator.
   LocationSummary* locations_;
 
+  // Set by the liveness analysis.
+  LiveInterval* live_interval_;
+
+  // Set by the liveness analysis, this is the position in a linear
+  // order of blocks where this instruction's live interval start.
+  size_t lifetime_position_;
+
   friend class HBasicBlock;
   friend class HInstructionList;
 
@@ -596,6 +633,8 @@
  private:
   HInstruction* instruction_;
   HInstruction* next_;
+
+  DISALLOW_COPY_AND_ASSIGN(HInstructionIterator);
 };
 
 class HBackwardInstructionIterator : public ValueObject {
@@ -615,6 +654,8 @@
  private:
   HInstruction* instruction_;
   HInstruction* next_;
+
+  DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator);
 };
 
 // An embedded container with N elements of type T.  Used (with partial
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index f435cb0..286f48a 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -129,6 +129,7 @@
 
   graph->FindNaturalLoops();
   SsaLivenessAnalysis(*graph).Analyze();
+  visualizer.DumpGraph("liveness");
 
   return new CompiledMethod(GetCompilerDriver(),
                             instruction_set,
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 85171aa..0f16ad2 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -22,7 +22,7 @@
 void SsaLivenessAnalysis::Analyze() {
   LinearizeGraph();
   NumberInstructions();
-  ComputeSets();
+  ComputeLiveness();
 }
 
 static bool IsLoopExit(HLoopInformation* current, HLoopInformation* to) {
@@ -96,6 +96,22 @@
   DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator);
 };
 
+class HLinearPostOrderIterator : public ValueObject {
+ public:
+  explicit HLinearPostOrderIterator(const GrowableArray<HBasicBlock*>& post_order)
+      : post_order_(post_order), index_(0) {}
+
+  bool Done() const { return index_ == post_order_.Size(); }
+  HBasicBlock* Current() const { return post_order_.Get(index_); }
+  void Advance() { ++index_; }
+
+ private:
+  const GrowableArray<HBasicBlock*>& post_order_;
+  size_t index_;
+
+  DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator);
+};
+
 void SsaLivenessAnalysis::LinearizeGraph() {
   // For simplicity of the implementation, we create post linear order. The order for
   // computing live ranges is the reverse of that order.
@@ -105,27 +121,41 @@
 
 void SsaLivenessAnalysis::NumberInstructions() {
   int ssa_index = 0;
+  size_t lifetime_position = 0;
+  // Each instruction gets an individual lifetime position, and a block gets a lifetime
+  // start and end position. Non-phi instructions have a distinct lifetime position than
+  // the block they are in. Phi instructions have the lifetime start of their block as
+  // lifetime position
   for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
+    block->SetLifetimeStart(++lifetime_position);
 
     for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
       HInstruction* current = it.Current();
       if (current->HasUses()) {
+        instructions_from_ssa_index_.Add(current);
         current->SetSsaIndex(ssa_index++);
+        current->SetLiveInterval(new (graph_.GetArena()) LiveInterval(graph_.GetArena()));
       }
+      current->SetLifetimePosition(lifetime_position);
     }
 
     for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
       HInstruction* current = it.Current();
       if (current->HasUses()) {
+        instructions_from_ssa_index_.Add(current);
         current->SetSsaIndex(ssa_index++);
+        current->SetLiveInterval(new (graph_.GetArena()) LiveInterval(graph_.GetArena()));
       }
+      current->SetLifetimePosition(++lifetime_position);
     }
+
+    block->SetLifetimeEnd(++lifetime_position);
   }
   number_of_ssa_values_ = ssa_index;
 }
 
-void SsaLivenessAnalysis::ComputeSets() {
+void SsaLivenessAnalysis::ComputeLiveness() {
   for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
     block_infos_.Put(
@@ -133,9 +163,10 @@
         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();
+  // Compute the live ranges, as well as the initial live_in, live_out, and kill sets.
+  // This method does not handle backward branches for the sets, therefore live_in
+  // and live_out sets are not yet correct.
+  ComputeLiveRanges();
 
   // 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
@@ -143,26 +174,71 @@
   ComputeLiveInAndLiveOutSets();
 }
 
-void SsaLivenessAnalysis::ComputeInitialSets() {
-  // Do a post orderr visit, adding inputs of instructions live in the block where
+class InstructionBitVectorIterator : public ValueObject {
+ public:
+  InstructionBitVectorIterator(const BitVector& vector,
+                               const GrowableArray<HInstruction*>& instructions)
+        : instructions_(instructions),
+          iterator_(BitVector::Iterator(&vector)),
+          current_bit_index_(iterator_.Next()) {}
+
+  bool Done() const { return current_bit_index_ == -1; }
+  HInstruction* Current() const { return instructions_.Get(current_bit_index_); }
+  void Advance() {
+    current_bit_index_ = iterator_.Next();
+  }
+
+ private:
+  const GrowableArray<HInstruction*> instructions_;
+  BitVector::Iterator iterator_;
+  int32_t current_bit_index_;
+
+  DISALLOW_COPY_AND_ASSIGN(InstructionBitVectorIterator);
+};
+
+void SsaLivenessAnalysis::ComputeLiveRanges() {
+  // Do a post order 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()) {
+  for (HLinearPostOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
 
     BitVector* kill = GetKillSet(*block);
     BitVector* live_in = GetLiveInSet(*block);
 
+    // Set phi inputs of successors of this block corresponding to this block
+    // as live_in.
+    for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) {
+      HBasicBlock* successor = block->GetSuccessors().Get(i);
+      live_in->Union(GetLiveInSet(*successor));
+      size_t phi_input_index = successor->GetPredecessorIndexOf(block);
+      for (HInstructionIterator it(successor->GetPhis()); !it.Done(); it.Advance()) {
+        HInstruction* input = it.Current()->InputAt(phi_input_index);
+        live_in->SetBit(input->GetSsaIndex());
+      }
+    }
+
+    // Add a range that covers this block to all instructions live_in because of successors.
+    for (InstructionBitVectorIterator it(*live_in, instructions_from_ssa_index_);
+         !it.Done();
+         it.Advance()) {
+      it.Current()->GetLiveInterval()->AddRange(block->GetLifetimeStart(), block->GetLifetimeEnd());
+    }
+
     for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
       HInstruction* current = it.Current();
       if (current->HasSsaIndex()) {
+        // Kill the instruction and shorten its interval.
         kill->SetBit(current->GetSsaIndex());
         live_in->ClearBit(current->GetSsaIndex());
+        current->GetLiveInterval()->SetFrom(current->GetLifetimePosition());
       }
 
       // 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());
+        HInstruction* input = current->InputAt(i);
+        DCHECK(input->HasSsaIndex());
+        live_in->SetBit(input->GetSsaIndex());
+        input->GetLiveInterval()->AddUse(current);
       }
 
       if (current->HasEnvironment()) {
@@ -173,32 +249,30 @@
           if (instruction != nullptr) {
             DCHECK(instruction->HasSsaIndex());
             live_in->SetBit(instruction->GetSsaIndex());
+            instruction->GetLiveInterval()->AddUse(current);
           }
         }
       }
     }
 
+    // Kill phis defined in this block.
     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);
-        }
+    if (block->IsLoopHeader()) {
+      HBasicBlock* back_edge = block->GetLoopInformation()->GetBackEdges().Get(0);
+      // For all live_in instructions at the loop header, we need to create a range
+      // that covers the full loop.
+      for (InstructionBitVectorIterator it(*live_in, instructions_from_ssa_index_);
+           !it.Done();
+           it.Advance()) {
+        it.Current()->GetLiveInterval()->AddLoopRange(block->GetLifetimeStart(),
+                                                      back_edge->GetLifetimeEnd());
       }
     }
   }
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index b8695ba..2d91436 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -44,12 +44,104 @@
   DISALLOW_COPY_AND_ASSIGN(BlockInfo);
 };
 
+/**
+ * A live range contains the start and end of a range where an instruction
+ * is live.
+ */
+class LiveRange : public ValueObject {
+ public:
+  LiveRange(size_t start, size_t end) : start_(start), end_(end) {
+    DCHECK_LT(start, end);
+  }
+
+  size_t GetStart() const { return start_; }
+  size_t GetEnd() const { return end_; }
+
+ private:
+  size_t start_;
+  size_t end_;
+};
+
+static constexpr int kDefaultNumberOfRanges = 3;
+
+/**
+ * An interval is a list of disjoint live ranges where an instruction is live.
+ * Each instruction that has uses gets an interval.
+ */
+class LiveInterval : public ArenaObject {
+ public:
+  explicit LiveInterval(ArenaAllocator* allocator) : ranges_(allocator, kDefaultNumberOfRanges) {}
+
+  void AddUse(HInstruction* instruction) {
+    size_t position = instruction->GetLifetimePosition();
+    size_t start_block_position = instruction->GetBlock()->GetLifetimeStart();
+    size_t end_block_position = instruction->GetBlock()->GetLifetimeEnd();
+    if (ranges_.IsEmpty()) {
+      // First time we see a use of that interval.
+      ranges_.Add(LiveRange(start_block_position, position));
+    } else if (ranges_.Peek().GetStart() == start_block_position) {
+      // There is a use later in the same block.
+      DCHECK_LE(position, ranges_.Peek().GetEnd());
+    } else if (ranges_.Peek().GetStart() == end_block_position + 1) {
+      // Last use is in a following block.
+      LiveRange existing = ranges_.Pop();
+      ranges_.Add(LiveRange(start_block_position, existing.GetEnd()));
+    } else {
+      // There is a hole in the interval. Create a new range.
+      ranges_.Add(LiveRange(start_block_position, position));
+    }
+  }
+
+  void AddRange(size_t start, size_t end) {
+    if (ranges_.IsEmpty()) {
+      ranges_.Add(LiveRange(start, end));
+    } else if (ranges_.Peek().GetStart() == end + 1) {
+      // There is a use in the following block.
+      LiveRange existing = ranges_.Pop();
+      ranges_.Add(LiveRange(start, existing.GetEnd()));
+    } else {
+      // There is a hole in the interval. Create a new range.
+      ranges_.Add(LiveRange(start, end));
+    }
+  }
+
+  void AddLoopRange(size_t start, size_t end) {
+    DCHECK(!ranges_.IsEmpty());
+    while (!ranges_.IsEmpty() && ranges_.Peek().GetEnd() < end) {
+      DCHECK_LE(start, ranges_.Peek().GetStart());
+      ranges_.Pop();
+    }
+    if (ranges_.IsEmpty()) {
+      // Uses are only in the loop.
+      ranges_.Add(LiveRange(start, end));
+    } else {
+      // There are uses after the loop.
+      LiveRange range = ranges_.Pop();
+      ranges_.Add(LiveRange(start, range.GetEnd()));
+    }
+  }
+
+  void SetFrom(size_t from) {
+    DCHECK(!ranges_.IsEmpty());
+    LiveRange existing = ranges_.Pop();
+    ranges_.Add(LiveRange(from, existing.GetEnd()));
+  }
+
+  const GrowableArray<LiveRange>& GetRanges() const { return ranges_; }
+
+ private:
+  GrowableArray<LiveRange> ranges_;
+
+  DISALLOW_COPY_AND_ASSIGN(LiveInterval);
+};
+
 class SsaLivenessAnalysis : public ValueObject {
  public:
   explicit SsaLivenessAnalysis(const HGraph& graph)
       : graph_(graph),
         linear_post_order_(graph.GetArena(), graph.GetBlocks().Size()),
         block_infos_(graph.GetArena(), graph.GetBlocks().Size()),
+        instructions_from_ssa_index_(graph.GetArena(), 0),
         number_of_ssa_values_(0) {
     block_infos_.SetSize(graph.GetBlocks().Size());
   }
@@ -72,6 +164,10 @@
     return linear_post_order_;
   }
 
+  HInstruction* GetInstructionFromSsaIndex(size_t index) {
+    return instructions_from_ssa_index_.Get(index);
+  }
+
  private:
   // Linearize the graph so that:
   // (1): a block is always after its dominator,
@@ -79,15 +175,16 @@
   // This creates a natural and efficient ordering when visualizing live ranges.
   void LinearizeGraph();
 
-  // Give an SSA number to each instruction that defines a value used by another instruction.
+  // Give an SSA number to each instruction that defines a value used by another instruction,
+  // and setup the lifetime information of each instruction and block.
   void NumberInstructions();
 
-  // Compute live_in, live_out and kill sets.
-  void ComputeSets();
+  // Compute live ranges of instructions, as well as live_in, live_out and kill sets.
+  void ComputeLiveness();
 
-  // Compute the initial live_in, live_out and kill sets, without analyzing
-  // backward branches.
-  void ComputeInitialSets();
+  // Compute the live ranges of instructions, as well as the initial live_in, live_out and
+  // kill sets, that do not take into account backward branches.
+  void ComputeLiveRanges();
 
   // After computing the initial sets, this method does a fixed point
   // calculation over the live_in and live_out set to take into account
@@ -103,6 +200,7 @@
   const HGraph& graph_;
   GrowableArray<HBasicBlock*> linear_post_order_;
   GrowableArray<BlockInfo*> block_infos_;
+  GrowableArray<HInstruction*> instructions_from_ssa_index_;
   size_t number_of_ssa_values_;
 
   DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis);