Move the linear order to the HGraph.

Bug found by Zheng Xu: SsaLivenessAnalysis being a stack allocated
object, we should not refer to it in later phases of the compiler.
Specifically, the code generator was using the linear order, which
was stored in the liveness analysis object.

Change-Id: I574641f522b7b86fc43f3914166108efc72edb3b

10 files changed, 97 insertions, 94 deletions

diff --git a/compiler/optimizing/codegen_test.cc b/compiler/optimizing/codegen_test.cc
index 2be117b..afcff1e 100644
--- a/compiler/optimizing/codegen_test.cc
+++ b/compiler/optimizing/codegen_test.cc
@@ -152,7 +152,7 @@ static void RunCodeOptimized(CodeGenerator* codegen,
                              bool has_result,
                              Expected expected) {
   graph->BuildDominatorTree();
-  SsaLivenessAnalysis liveness(*graph, codegen);
+  SsaLivenessAnalysis liveness(graph, codegen);
   liveness.Analyze();
 
   RegisterAllocator register_allocator(graph->GetArena(), codegen, liveness);
diff --git a/compiler/optimizing/linearize_test.cc b/compiler/optimizing/linearize_test.cc
index 28c5555..7818c60 100644
--- a/compiler/optimizing/linearize_test.cc
+++ b/compiler/optimizing/linearize_test.cc
@@ -50,12 +50,12 @@ static void TestCode(const uint16_t* data, const int* expected_order, size_t num
   std::unique_ptr<const X86InstructionSetFeatures> features_x86(
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-  SsaLivenessAnalysis liveness(*graph, &codegen);
+  SsaLivenessAnalysis liveness(graph, &codegen);
   liveness.Analyze();
 
-  ASSERT_EQ(liveness.GetLinearOrder().Size(), number_of_blocks);
+  ASSERT_EQ(graph->GetLinearOrder().Size(), number_of_blocks);
   for (size_t i = 0; i < number_of_blocks; ++i) {
-    ASSERT_EQ(liveness.GetLinearOrder().Get(i)->GetBlockId(), expected_order[i]);
+    ASSERT_EQ(graph->GetLinearOrder().Get(i)->GetBlockId(), expected_order[i]);
   }
 }
 
diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc
index 61d6593..5236773 100644
--- a/compiler/optimizing/live_ranges_test.cc
+++ b/compiler/optimizing/live_ranges_test.cc
@@ -69,7 +69,7 @@ TEST(LiveRangesTest, CFG1) {
   std::unique_ptr<const X86InstructionSetFeatures> features_x86(
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-  SsaLivenessAnalysis liveness(*graph, &codegen);
+  SsaLivenessAnalysis liveness(graph, &codegen);
   liveness.Analyze();
 
   LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
@@ -117,7 +117,7 @@ TEST(LiveRangesTest, CFG2) {
   std::unique_ptr<const X86InstructionSetFeatures> features_x86(
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-  SsaLivenessAnalysis liveness(*graph, &codegen);
+  SsaLivenessAnalysis liveness(graph, &codegen);
   liveness.Analyze();
 
   LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
@@ -168,7 +168,7 @@ TEST(LiveRangesTest, CFG3) {
   std::unique_ptr<const X86InstructionSetFeatures> features_x86(
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-  SsaLivenessAnalysis liveness(*graph, &codegen);
+  SsaLivenessAnalysis liveness(graph, &codegen);
   liveness.Analyze();
 
   // Test for the 4 constant.
@@ -247,7 +247,7 @@ TEST(LiveRangesTest, Loop1) {
   std::unique_ptr<const X86InstructionSetFeatures> features_x86(
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-  SsaLivenessAnalysis liveness(*graph, &codegen);
+  SsaLivenessAnalysis liveness(graph, &codegen);
   liveness.Analyze();
 
   // Test for the 0 constant.
@@ -327,7 +327,7 @@ TEST(LiveRangesTest, Loop2) {
   std::unique_ptr<const X86InstructionSetFeatures> features_x86(
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-  SsaLivenessAnalysis liveness(*graph, &codegen);
+  SsaLivenessAnalysis liveness(graph, &codegen);
   liveness.Analyze();
 
   // Test for the 0 constant.
@@ -405,7 +405,7 @@ TEST(LiveRangesTest, CFG4) {
   std::unique_ptr<const X86InstructionSetFeatures> features_x86(
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-  SsaLivenessAnalysis liveness(*graph, &codegen);
+  SsaLivenessAnalysis liveness(graph, &codegen);
   liveness.Analyze();
 
   // Test for the 0 constant.
diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc
index 81250ca..8a96ee9 100644
--- a/compiler/optimizing/liveness_test.cc
+++ b/compiler/optimizing/liveness_test.cc
@@ -57,7 +57,7 @@ static void TestCode(const uint16_t* data, const char* expected) {
   std::unique_ptr<const X86InstructionSetFeatures> features_x86(
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-  SsaLivenessAnalysis liveness(*graph, &codegen);
+  SsaLivenessAnalysis liveness(graph, &codegen);
   liveness.Analyze();
 
   std::ostringstream buffer;
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 5f50494..b406cbb 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -112,6 +112,7 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
       : arena_(arena),
         blocks_(arena, kDefaultNumberOfBlocks),
         reverse_post_order_(arena, kDefaultNumberOfBlocks),
+        linear_order_(arena, kDefaultNumberOfBlocks),
         entry_block_(nullptr),
         exit_block_(nullptr),
         maximum_number_of_out_vregs_(0),
@@ -216,6 +217,10 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
     return reverse_post_order_;
   }
 
+  const GrowableArray<HBasicBlock*>& GetLinearOrder() const {
+    return linear_order_;
+  }
+
   bool HasArrayAccesses() const {
     return has_array_accesses_;
   }
@@ -262,6 +267,9 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
   // List of blocks to perform a reverse post order tree traversal.
   GrowableArray<HBasicBlock*> reverse_post_order_;
 
+  // List of blocks to perform a linear order tree traversal.
+  GrowableArray<HBasicBlock*> linear_order_;
+
   HBasicBlock* entry_block_;
   HBasicBlock* exit_block_;
 
@@ -293,6 +301,7 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
   ArenaSafeMap<int32_t, HIntConstant*> cached_int_constants_;
   ArenaSafeMap<int64_t, HLongConstant*> cached_long_constants_;
 
+  friend class SsaLivenessAnalysis;  // For the linear order.
   ART_FRIEND_TEST(GraphTest, IfSuccessorSimpleJoinBlock1);
   DISALLOW_COPY_AND_ASSIGN(HGraph);
 };
@@ -3628,6 +3637,43 @@ class HPostOrderIterator : public ValueObject {
   DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator);
 };
 
+class HLinearPostOrderIterator : public ValueObject {
+ public:
+  explicit HLinearPostOrderIterator(const HGraph& graph)
+      : order_(graph.GetLinearOrder()), index_(graph.GetLinearOrder().Size()) {}
+
+  bool Done() const { return index_ == 0; }
+
+  HBasicBlock* Current() const { return order_.Get(index_ -1); }
+
+  void Advance() {
+    --index_;
+    DCHECK_GE(index_, 0U);
+  }
+
+ private:
+  const GrowableArray<HBasicBlock*>& order_;
+  size_t index_;
+
+  DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator);
+};
+
+class HLinearOrderIterator : public ValueObject {
+ public:
+  explicit HLinearOrderIterator(const HGraph& graph)
+      : order_(graph.GetLinearOrder()), index_(0) {}
+
+  bool Done() const { return index_ == order_.Size(); }
+  HBasicBlock* Current() const { return order_.Get(index_); }
+  void Advance() { ++index_; }
+
+ private:
+  const GrowableArray<HBasicBlock*>& order_;
+  size_t index_;
+
+  DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator);
+};
+
 // Iterator over the blocks that art part of the loop. Includes blocks part
 // of an inner loop. The order in which the blocks are iterated is on their
 // block id.
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 56cea8a..efca1a5 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -361,7 +361,7 @@ static void AllocateRegisters(HGraph* graph,
                               CodeGenerator* codegen,
                               PassInfoPrinter* pass_info_printer) {
   PrepareForRegisterAllocation(graph).Run();
-  SsaLivenessAnalysis liveness(*graph, codegen);
+  SsaLivenessAnalysis liveness(graph, codegen);
   {
     PassInfo pass_info(SsaLivenessAnalysis::kLivenessPassName, pass_info_printer);
     liveness.Analyze();
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 8f26328..5e28343 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -103,7 +103,7 @@ void RegisterAllocator::AllocateRegisters() {
     // Since only parallel moves have been inserted during the register allocation,
     // these checks are mostly for making sure these moves have been added correctly.
     size_t current_liveness = 0;
-    for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) {
+    for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) {
       HBasicBlock* block = it.Current();
       for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
         HInstruction* instruction = inst_it.Current();
@@ -147,7 +147,7 @@ void RegisterAllocator::BlockRegister(Location location,
 void RegisterAllocator::AllocateRegistersInternal() {
   // Iterate post-order, to ensure the list is sorted, and the last added interval
   // is the one with the lowest start position.
-  for (HLinearPostOrderIterator it(liveness_); !it.Done(); it.Advance()) {
+  for (HLinearPostOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
     for (HBackwardInstructionIterator back_it(block->GetInstructions()); !back_it.Done();
          back_it.Advance()) {
@@ -1598,7 +1598,7 @@ void RegisterAllocator::Resolve() {
                                      maximum_number_of_live_core_registers_,
                                      maximum_number_of_live_fp_registers_,
                                      reserved_out_slots_,
-                                     liveness_.GetLinearOrder());
+                                     codegen_->GetGraph()->GetLinearOrder());
 
   // Adjust the Out Location of instructions.
   // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration.
@@ -1678,7 +1678,7 @@ void RegisterAllocator::Resolve() {
   }
 
   // Resolve non-linear control flow across branches. Order does not matter.
-  for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) {
+  for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
     BitVector* live = liveness_.GetLiveInSet(*block);
     for (uint32_t idx : live->Indexes()) {
@@ -1691,7 +1691,7 @@ void RegisterAllocator::Resolve() {
   }
 
   // Resolve phi inputs. Order does not matter.
-  for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) {
+  for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) {
     HBasicBlock* current = it.Current();
     for (HInstructionIterator inst_it(current->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
       HInstruction* phi = inst_it.Current();
diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc
index 3951439..c307d98 100644
--- a/compiler/optimizing/register_allocator_test.cc
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -46,7 +46,7 @@ static bool Check(const uint16_t* data) {
   std::unique_ptr<const X86InstructionSetFeatures> features_x86(
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-  SsaLivenessAnalysis liveness(*graph, &codegen);
+  SsaLivenessAnalysis liveness(graph, &codegen);
   liveness.Analyze();
   RegisterAllocator register_allocator(&allocator, &codegen, liveness);
   register_allocator.AllocateRegisters();
@@ -306,7 +306,7 @@ TEST(RegisterAllocatorTest, Loop3) {
   std::unique_ptr<const X86InstructionSetFeatures> features_x86(
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-  SsaLivenessAnalysis liveness(*graph, &codegen);
+  SsaLivenessAnalysis liveness(graph, &codegen);
   liveness.Analyze();
   RegisterAllocator register_allocator(&allocator, &codegen, liveness);
   register_allocator.AllocateRegisters();
@@ -340,7 +340,7 @@ TEST(RegisterAllocatorTest, FirstRegisterUse) {
   std::unique_ptr<const X86InstructionSetFeatures> features_x86(
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-  SsaLivenessAnalysis liveness(*graph, &codegen);
+  SsaLivenessAnalysis liveness(graph, &codegen);
   liveness.Analyze();
 
   HXor* first_xor = graph->GetBlocks().Get(1)->GetFirstInstruction()->AsXor();
@@ -395,7 +395,7 @@ TEST(RegisterAllocatorTest, DeadPhi) {
   std::unique_ptr<const X86InstructionSetFeatures> features_x86(
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-  SsaLivenessAnalysis liveness(*graph, &codegen);
+  SsaLivenessAnalysis liveness(graph, &codegen);
   liveness.Analyze();
   RegisterAllocator register_allocator(&allocator, &codegen, liveness);
   register_allocator.AllocateRegisters();
@@ -419,7 +419,7 @@ TEST(RegisterAllocatorTest, FreeUntil) {
   std::unique_ptr<const X86InstructionSetFeatures> features_x86(
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-  SsaLivenessAnalysis liveness(*graph, &codegen);
+  SsaLivenessAnalysis liveness(graph, &codegen);
   liveness.Analyze();
   RegisterAllocator register_allocator(&allocator, &codegen, liveness);
 
@@ -523,7 +523,7 @@ TEST(RegisterAllocatorTest, PhiHint) {
     std::unique_ptr<const X86InstructionSetFeatures> features_x86(
         X86InstructionSetFeatures::FromCppDefines());
     x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-    SsaLivenessAnalysis liveness(*graph, &codegen);
+    SsaLivenessAnalysis liveness(graph, &codegen);
     liveness.Analyze();
 
     // Check that the register allocator is deterministic.
@@ -540,7 +540,7 @@ TEST(RegisterAllocatorTest, PhiHint) {
     std::unique_ptr<const X86InstructionSetFeatures> features_x86(
         X86InstructionSetFeatures::FromCppDefines());
     x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-    SsaLivenessAnalysis liveness(*graph, &codegen);
+    SsaLivenessAnalysis liveness(graph, &codegen);
     liveness.Analyze();
 
     // Set the phi to a specific register, and check that the inputs get allocated
@@ -559,7 +559,7 @@ TEST(RegisterAllocatorTest, PhiHint) {
     std::unique_ptr<const X86InstructionSetFeatures> features_x86(
         X86InstructionSetFeatures::FromCppDefines());
     x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-    SsaLivenessAnalysis liveness(*graph, &codegen);
+    SsaLivenessAnalysis liveness(graph, &codegen);
     liveness.Analyze();
 
     // Set input1 to a specific register, and check that the phi and other input get allocated
@@ -578,7 +578,7 @@ TEST(RegisterAllocatorTest, PhiHint) {
     std::unique_ptr<const X86InstructionSetFeatures> features_x86(
         X86InstructionSetFeatures::FromCppDefines());
     x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-    SsaLivenessAnalysis liveness(*graph, &codegen);
+    SsaLivenessAnalysis liveness(graph, &codegen);
     liveness.Analyze();
 
     // Set input2 to a specific register, and check that the phi and other input get allocated
@@ -632,7 +632,7 @@ TEST(RegisterAllocatorTest, ExpectedInRegisterHint) {
     std::unique_ptr<const X86InstructionSetFeatures> features_x86(
         X86InstructionSetFeatures::FromCppDefines());
     x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-    SsaLivenessAnalysis liveness(*graph, &codegen);
+    SsaLivenessAnalysis liveness(graph, &codegen);
     liveness.Analyze();
 
     RegisterAllocator register_allocator(&allocator, &codegen, liveness);
@@ -647,7 +647,7 @@ TEST(RegisterAllocatorTest, ExpectedInRegisterHint) {
     std::unique_ptr<const X86InstructionSetFeatures> features_x86(
         X86InstructionSetFeatures::FromCppDefines());
     x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-    SsaLivenessAnalysis liveness(*graph, &codegen);
+    SsaLivenessAnalysis liveness(graph, &codegen);
     liveness.Analyze();
 
     // Check that the field gets put in the register expected by its use.
@@ -699,7 +699,7 @@ TEST(RegisterAllocatorTest, SameAsFirstInputHint) {
     std::unique_ptr<const X86InstructionSetFeatures> features_x86(
         X86InstructionSetFeatures::FromCppDefines());
     x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-    SsaLivenessAnalysis liveness(*graph, &codegen);
+    SsaLivenessAnalysis liveness(graph, &codegen);
     liveness.Analyze();
 
     RegisterAllocator register_allocator(&allocator, &codegen, liveness);
@@ -715,7 +715,7 @@ TEST(RegisterAllocatorTest, SameAsFirstInputHint) {
     std::unique_ptr<const X86InstructionSetFeatures> features_x86(
         X86InstructionSetFeatures::FromCppDefines());
     x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-    SsaLivenessAnalysis liveness(*graph, &codegen);
+    SsaLivenessAnalysis liveness(graph, &codegen);
     liveness.Analyze();
 
     // check that both adds get the same register.
@@ -766,7 +766,7 @@ TEST(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) {
     std::unique_ptr<const X86InstructionSetFeatures> features_x86(
         X86InstructionSetFeatures::FromCppDefines());
     x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-    SsaLivenessAnalysis liveness(*graph, &codegen);
+    SsaLivenessAnalysis liveness(graph, &codegen);
     liveness.Analyze();
 
     RegisterAllocator register_allocator(&allocator, &codegen, liveness);
@@ -856,7 +856,7 @@ TEST(RegisterAllocatorTest, SpillInactive) {
   std::unique_ptr<const X86InstructionSetFeatures> features_x86(
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
-  SsaLivenessAnalysis liveness(*graph, &codegen);
+  SsaLivenessAnalysis liveness(graph, &codegen);
 
   RegisterAllocator register_allocator(&allocator, &codegen, liveness);
   register_allocator.unhandled_core_intervals_.Add(fourth);
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 95da6ef..302df2a 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -69,9 +69,9 @@ void SsaLivenessAnalysis::LinearizeGraph() {
   //      current reverse post order in the graph, but it would require making
   //      order queries to a GrowableArray, which is not the best data structure
   //      for it.
-  GrowableArray<uint32_t> forward_predecessors(graph_.GetArena(), graph_.GetBlocks().Size());
-  forward_predecessors.SetSize(graph_.GetBlocks().Size());
-  for (HReversePostOrderIterator it(graph_); !it.Done(); it.Advance()) {
+  GrowableArray<uint32_t> forward_predecessors(graph_->GetArena(), graph_->GetBlocks().Size());
+  forward_predecessors.SetSize(graph_->GetBlocks().Size());
+  for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
     size_t number_of_forward_predecessors = block->GetPredecessors().Size();
     if (block->IsLoopHeader()) {
@@ -86,11 +86,11 @@ void SsaLivenessAnalysis::LinearizeGraph() {
   //      iterate over the successors. When all non-back edge predecessors of a
   //      successor block are visited, the successor block is added in the worklist
   //      following an order that satisfies the requirements to build our linear graph.
-  GrowableArray<HBasicBlock*> worklist(graph_.GetArena(), 1);
-  worklist.Add(graph_.GetEntryBlock());
+  GrowableArray<HBasicBlock*> worklist(graph_->GetArena(), 1);
+  worklist.Add(graph_->GetEntryBlock());
   do {
     HBasicBlock* current = worklist.Pop();
-    linear_order_.Add(current);
+    graph_->linear_order_.Add(current);
     for (size_t i = 0, e = current->GetSuccessors().Size(); i < e; ++i) {
       HBasicBlock* successor = current->GetSuccessors().Get(i);
       int block_id = successor->GetBlockId();
@@ -115,7 +115,7 @@ void SsaLivenessAnalysis::NumberInstructions() {
   // to differentiate between the start and end of an instruction. Adding 2 to
   // the lifetime position for each instruction ensures the start of an
   // instruction is different than the end of the previous instruction.
-  for (HLinearOrderIterator it(*this); !it.Done(); it.Advance()) {
+  for (HLinearOrderIterator it(*graph_); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
     block->SetLifetimeStart(lifetime_position);
 
@@ -127,7 +127,7 @@ void SsaLivenessAnalysis::NumberInstructions() {
         instructions_from_ssa_index_.Add(current);
         current->SetSsaIndex(ssa_index++);
         current->SetLiveInterval(
-            LiveInterval::MakeInterval(graph_.GetArena(), current->GetType(), current));
+            LiveInterval::MakeInterval(graph_->GetArena(), current->GetType(), current));
       }
       current->SetLifetimePosition(lifetime_position);
     }
@@ -145,7 +145,7 @@ void SsaLivenessAnalysis::NumberInstructions() {
         instructions_from_ssa_index_.Add(current);
         current->SetSsaIndex(ssa_index++);
         current->SetLiveInterval(
-            LiveInterval::MakeInterval(graph_.GetArena(), current->GetType(), current));
+            LiveInterval::MakeInterval(graph_->GetArena(), current->GetType(), current));
       }
       instructions_from_lifetime_position_.Add(current);
       current->SetLifetimePosition(lifetime_position);
@@ -158,11 +158,11 @@ void SsaLivenessAnalysis::NumberInstructions() {
 }
 
 void SsaLivenessAnalysis::ComputeLiveness() {
-  for (HLinearOrderIterator it(*this); !it.Done(); it.Advance()) {
+  for (HLinearOrderIterator 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_));
+        new (graph_->GetArena()) BlockInfo(graph_->GetArena(), *block, number_of_ssa_values_));
   }
 
   // Compute the live ranges, as well as the initial live_in, live_out, and kill sets.
@@ -179,7 +179,7 @@ void SsaLivenessAnalysis::ComputeLiveness() {
 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 (HLinearPostOrderIterator it(*this); !it.Done(); it.Advance()) {
+  for (HLinearPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
 
     BitVector* kill = GetKillSet(*block);
@@ -281,7 +281,7 @@ void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() {
   do {
     changed = false;
 
-    for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) {
+    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
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index b6e4028..2b51f94 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -893,15 +893,14 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
  */
 class SsaLivenessAnalysis : public ValueObject {
  public:
-  SsaLivenessAnalysis(const HGraph& graph, CodeGenerator* codegen)
+  SsaLivenessAnalysis(HGraph* graph, CodeGenerator* codegen)
       : graph_(graph),
         codegen_(codegen),
-        linear_order_(graph.GetArena(), graph.GetBlocks().Size()),
-        block_infos_(graph.GetArena(), graph.GetBlocks().Size()),
-        instructions_from_ssa_index_(graph.GetArena(), 0),
-        instructions_from_lifetime_position_(graph.GetArena(), 0),
+        block_infos_(graph->GetArena(), graph->GetBlocks().Size()),
+        instructions_from_ssa_index_(graph->GetArena(), 0),
+        instructions_from_lifetime_position_(graph->GetArena(), 0),
         number_of_ssa_values_(0) {
-    block_infos_.SetSize(graph.GetBlocks().Size());
+    block_infos_.SetSize(graph->GetBlocks().Size());
   }
 
   void Analyze();
@@ -918,10 +917,6 @@ class SsaLivenessAnalysis : public ValueObject {
     return &block_infos_.Get(block.GetBlockId())->kill_;
   }
 
-  const GrowableArray<HBasicBlock*>& GetLinearOrder() const {
-    return linear_order_;
-  }
-
   HInstruction* GetInstructionFromSsaIndex(size_t index) const {
     return instructions_from_ssa_index_.Get(index);
   }
@@ -989,9 +984,8 @@ class SsaLivenessAnalysis : public ValueObject {
     return instruction->GetType() == Primitive::kPrimNot;
   }
 
-  const HGraph& graph_;
+  HGraph* const graph_;
   CodeGenerator* const codegen_;
-  GrowableArray<HBasicBlock*> linear_order_;
   GrowableArray<BlockInfo*> block_infos_;
 
   // Temporary array used when computing live_in, live_out, and kill sets.
@@ -1004,43 +998,6 @@ class SsaLivenessAnalysis : public ValueObject {
   DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis);
 };
 
-class HLinearPostOrderIterator : public ValueObject {
- public:
-  explicit HLinearPostOrderIterator(const SsaLivenessAnalysis& liveness)
-      : order_(liveness.GetLinearOrder()), index_(liveness.GetLinearOrder().Size()) {}
-
-  bool Done() const { return index_ == 0; }
-
-  HBasicBlock* Current() const { return order_.Get(index_ -1); }
-
-  void Advance() {
-    --index_;
-    DCHECK_GE(index_, 0U);
-  }
-
- private:
-  const GrowableArray<HBasicBlock*>& order_;
-  size_t index_;
-
-  DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator);
-};
-
-class HLinearOrderIterator : public ValueObject {
- public:
-  explicit HLinearOrderIterator(const SsaLivenessAnalysis& liveness)
-      : order_(liveness.GetLinearOrder()), index_(0) {}
-
-  bool Done() const { return index_ == order_.Size(); }
-  HBasicBlock* Current() const { return order_.Get(index_); }
-  void Advance() { ++index_; }
-
- private:
-  const GrowableArray<HBasicBlock*>& order_;
-  size_t index_;
-
-  DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator);
-};
-
 }  // namespace art
 
 #endif  // ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_