Merge "Type MoveOperands."
diff --git a/compiler/optimizing/boolean_simplifier.cc b/compiler/optimizing/boolean_simplifier.cc
index be432c5..06328f2 100644
--- a/compiler/optimizing/boolean_simplifier.cc
+++ b/compiler/optimizing/boolean_simplifier.cc
@@ -73,8 +73,8 @@
     }
   } else {
     // General case when 'cond' is another instruction of type boolean.
-    // Negate with 'cond == 0'.
-    return new (allocator) HEqual(cond, graph->GetIntConstant(0));
+    DCHECK_EQ(cond->GetType(), Primitive::Type::kPrimBoolean);
+    return new (allocator) HBooleanNot(cond);
   }
 }
 
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index ab025a8..507b3cd 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -2665,6 +2665,21 @@
   }
 }
 
+void LocationsBuilderARM::VisitBooleanNot(HBooleanNot* bool_not) {
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(bool_not, LocationSummary::kNoCall);
+  locations->SetInAt(0, Location::RequiresRegister());
+  locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
+}
+
+void InstructionCodeGeneratorARM::VisitBooleanNot(HBooleanNot* bool_not) {
+  DCHECK_EQ(bool_not->InputAt(0)->GetType(), Primitive::kPrimBoolean);
+  LocationSummary* locations = bool_not->GetLocations();
+  Location out = locations->Out();
+  Location in = locations->InAt(0);
+  __ eor(out.AsRegister<Register>(), in.AsRegister<Register>(), ShifterOperand(1));
+}
+
 void LocationsBuilderARM::VisitCompare(HCompare* compare) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(compare, LocationSummary::kNoCall);
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index e9f9d1a..f6ec729 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -2279,6 +2279,17 @@
   }
 }
 
+void LocationsBuilderARM64::VisitBooleanNot(HBooleanNot* instruction) {
+  LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction);
+  locations->SetInAt(0, Location::RequiresRegister());
+  locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
+}
+
+void InstructionCodeGeneratorARM64::VisitBooleanNot(HBooleanNot* instruction) {
+  DCHECK_EQ(instruction->InputAt(0)->GetType(), Primitive::kPrimBoolean);
+  __ Eor(OutputRegister(instruction), InputRegisterAt(instruction, 0), vixl::Operand(1));
+}
+
 void LocationsBuilderARM64::VisitNullCheck(HNullCheck* instruction) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall);
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index f6b0cf3..6c75f34 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -2923,6 +2923,22 @@
   }
 }
 
+void LocationsBuilderX86::VisitBooleanNot(HBooleanNot* bool_not) {
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(bool_not, LocationSummary::kNoCall);
+  locations->SetInAt(0, Location::RequiresRegister());
+  locations->SetOut(Location::SameAsFirstInput());
+}
+
+void InstructionCodeGeneratorX86::VisitBooleanNot(HBooleanNot* bool_not) {
+  DCHECK_EQ(bool_not->InputAt(0)->GetType(), Primitive::kPrimBoolean);
+  LocationSummary* locations = bool_not->GetLocations();
+  Location in = locations->InAt(0);
+  Location out = locations->Out();
+  DCHECK(in.Equals(out));
+  __ xorl(out.AsRegister<Register>(), Immediate(1));
+}
+
 void LocationsBuilderX86::VisitCompare(HCompare* compare) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(compare, LocationSummary::kNoCall);
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 652cca4..aa4d7c6 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -2978,6 +2978,22 @@
   }
 }
 
+void LocationsBuilderX86_64::VisitBooleanNot(HBooleanNot* bool_not) {
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(bool_not, LocationSummary::kNoCall);
+  locations->SetInAt(0, Location::RequiresRegister());
+  locations->SetOut(Location::SameAsFirstInput());
+}
+
+void InstructionCodeGeneratorX86_64::VisitBooleanNot(HBooleanNot* bool_not) {
+  DCHECK_EQ(bool_not->InputAt(0)->GetType(), Primitive::kPrimBoolean);
+  LocationSummary* locations = bool_not->GetLocations();
+  DCHECK_EQ(locations->InAt(0).AsRegister<CpuRegister>().AsRegister(),
+            locations->Out().AsRegister<CpuRegister>().AsRegister());
+  Location out = locations->Out();
+  __ xorl(out.AsRegister<CpuRegister>(), Immediate(1));
+}
+
 void LocationsBuilderX86_64::VisitPhi(HPhi* instruction) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall);
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 @@
                              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 @@
   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 @@
   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 @@
   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 @@
   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 @@
   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 @@
   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 @@
   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 @@
   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 a2179fa..6fb34da 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -112,6 +112,7 @@
       : 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 @@
     return reverse_post_order_;
   }
 
+  const GrowableArray<HBasicBlock*>& GetLinearOrder() const {
+    return linear_order_;
+  }
+
   bool HasArrayAccesses() const {
     return has_array_accesses_;
   }
@@ -262,6 +267,9 @@
   // 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 @@
   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);
 };
@@ -676,6 +685,7 @@
   M(ArrayGet, Instruction)                                              \
   M(ArrayLength, Instruction)                                           \
   M(ArraySet, Instruction)                                              \
+  M(BooleanNot, UnaryOperation)                                         \
   M(BoundsCheck, Instruction)                                           \
   M(BoundType, Instruction)                                             \
   M(CheckCast, Instruction)                                             \
@@ -2643,6 +2653,33 @@
   DISALLOW_COPY_AND_ASSIGN(HNot);
 };
 
+class HBooleanNot : public HUnaryOperation {
+ public:
+  explicit HBooleanNot(HInstruction* input)
+      : HUnaryOperation(Primitive::Type::kPrimBoolean, input) {}
+
+  bool CanBeMoved() const OVERRIDE { return true; }
+  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
+    UNUSED(other);
+    return true;
+  }
+
+  int32_t Evaluate(int32_t x) const OVERRIDE {
+    DCHECK(IsUint<1>(x));
+    return !x;
+  }
+
+  int64_t Evaluate(int64_t x ATTRIBUTE_UNUSED) const OVERRIDE {
+    LOG(FATAL) << DebugName() << " cannot be used with 64-bit values";
+    UNREACHABLE();
+  }
+
+  DECLARE_INSTRUCTION(BooleanNot);
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HBooleanNot);
+};
+
 class HTypeConversion : public HExpression<1> {
  public:
   // Instantiate a type conversion of `input` to `result_type`.
@@ -3640,6 +3677,43 @@
   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 @@
                               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 e03f5c3..2fbd051 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -103,7 +103,7 @@
     // 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::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 @@
                                      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 @@
   }
 
   // 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 @@
   }
 
   // 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 @@
   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 @@
   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 @@
   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 @@
   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 @@
   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 @@
     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 @@
     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 @@
     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 @@
     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 @@
     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 @@
     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 @@
     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 @@
     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 @@
     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 @@
   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 @@
   //      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 @@
   //      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 @@
   // 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 @@
         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 @@
         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::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::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 @@
   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 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 @@
     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 @@
     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 @@
   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_
diff --git a/test/468-bool-simplifier-regression/expected.txt b/test/468-checker-bool-simplifier-regression/expected.txt
similarity index 100%
rename from test/468-bool-simplifier-regression/expected.txt
rename to test/468-checker-bool-simplifier-regression/expected.txt
diff --git a/test/468-bool-simplifier-regression/info.txt b/test/468-checker-bool-simplifier-regression/info.txt
similarity index 100%
rename from test/468-bool-simplifier-regression/info.txt
rename to test/468-checker-bool-simplifier-regression/info.txt
diff --git a/test/468-bool-simplifier-regression/smali/TestCase.smali b/test/468-checker-bool-simplifier-regression/smali/TestCase.smali
similarity index 100%
rename from test/468-bool-simplifier-regression/smali/TestCase.smali
rename to test/468-checker-bool-simplifier-regression/smali/TestCase.smali
diff --git a/test/468-bool-simplifier-regression/src/Main.java b/test/468-checker-bool-simplifier-regression/src/Main.java
similarity index 64%
rename from test/468-bool-simplifier-regression/src/Main.java
rename to test/468-checker-bool-simplifier-regression/src/Main.java
index 1dd27c9..65f20b3 100644
--- a/test/468-bool-simplifier-regression/src/Main.java
+++ b/test/468-checker-bool-simplifier-regression/src/Main.java
@@ -17,6 +17,20 @@
 import java.lang.reflect.*;
 
 public class Main {
+  
+  // CHECK-START: boolean TestCase.testCase() boolean_simplifier (before)
+  // CHECK-DAG:     [[Const0:i\d+]]   IntConstant 0
+  // CHECK-DAG:     [[Const1:i\d+]]   IntConstant 1
+  // CHECK-DAG:     [[Value:z\d+]]    StaticFieldGet
+  // CHECK-DAG:                       If [ [[Value]] ]
+  // CHECK-DAG:     [[Phi:i\d+]]      Phi [ [[Const1]] [[Const0]] ]
+  // CHECK-DAG:                       Return [ [[Phi]] ]
+
+  // CHECK-START: boolean TestCase.testCase() boolean_simplifier (after)
+  // CHECK-DAG:     [[Value:z\d+]]    StaticFieldGet
+  // CHECK-DAG:     [[Not:z\d+]]      BooleanNot [ [[Value]] ]
+  // CHECK-DAG:                       Return [ [[Not]] ]
+  
   public static boolean runTest(boolean input) throws Exception {
     Class<?> c = Class.forName("TestCase");
     Method m = c.getMethod("testCase");