Use ScopedArenaAllocator in BCE, DCE, LSE, ...

... ReferenceTypePropagation and GraphChecker.

Define and use a new allocation kind for LoadStoreAnalysis.

Memory needed to compile the two most expensive methods for
aosp_angler-userdebug boot image:
  BatteryStats.dumpCheckinLocked() : 19.7MiB -> 19.6MiB (-79KiB)
  BatteryStats.dumpLocked(): 39.4MiB -> 39.3MiB (-120KiB)

Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Bug: 64312607
Change-Id: Ib0cf074ac21ab67d8f8f2efabbdfb84cce9cae8e
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 0255e73..9c2068e 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -18,7 +18,8 @@
 
 #include <limits>
 
-#include "base/arena_containers.h"
+#include "base/scoped_arena_allocator.h"
+#include "base/scoped_arena_containers.h"
 #include "induction_var_range.h"
 #include "nodes.h"
 #include "side_effects_analysis.h"
@@ -287,7 +288,7 @@
  */
 class ValueRange : public ArenaObject<kArenaAllocBoundsCheckElimination> {
  public:
-  ValueRange(ArenaAllocator* allocator, ValueBound lower, ValueBound upper)
+  ValueRange(ScopedArenaAllocator* allocator, ValueBound lower, ValueBound upper)
       : allocator_(allocator), lower_(lower), upper_(upper) {}
 
   virtual ~ValueRange() {}
@@ -297,7 +298,7 @@
     return AsMonotonicValueRange() != nullptr;
   }
 
-  ArenaAllocator* GetAllocator() const { return allocator_; }
+  ScopedArenaAllocator* GetAllocator() const { return allocator_; }
   ValueBound GetLower() const { return lower_; }
   ValueBound GetUpper() const { return upper_; }
 
@@ -350,7 +351,7 @@
   }
 
  private:
-  ArenaAllocator* const allocator_;
+  ScopedArenaAllocator* const allocator_;
   const ValueBound lower_;  // inclusive
   const ValueBound upper_;  // inclusive
 
@@ -365,7 +366,7 @@
  */
 class MonotonicValueRange : public ValueRange {
  public:
-  MonotonicValueRange(ArenaAllocator* allocator,
+  MonotonicValueRange(ScopedArenaAllocator* allocator,
                       HPhi* induction_variable,
                       HInstruction* initial,
                       int32_t increment,
@@ -510,21 +511,19 @@
              const SideEffectsAnalysis& side_effects,
              HInductionVarAnalysis* induction_analysis)
       : HGraphVisitor(graph),
+        allocator_(graph->GetArenaStack()),
         maps_(graph->GetBlocks().size(),
-              ArenaSafeMap<int, ValueRange*>(
+              ScopedArenaSafeMap<int, ValueRange*>(
                   std::less<int>(),
-                  graph->GetAllocator()->Adapter(kArenaAllocBoundsCheckElimination)),
-              graph->GetAllocator()->Adapter(kArenaAllocBoundsCheckElimination)),
-        first_index_bounds_check_map_(
-            std::less<int>(),
-            graph->GetAllocator()->Adapter(kArenaAllocBoundsCheckElimination)),
-        early_exit_loop_(
-            std::less<uint32_t>(),
-            graph->GetAllocator()->Adapter(kArenaAllocBoundsCheckElimination)),
-        taken_test_loop_(
-            std::less<uint32_t>(),
-            graph->GetAllocator()->Adapter(kArenaAllocBoundsCheckElimination)),
-        finite_loop_(graph->GetAllocator()->Adapter(kArenaAllocBoundsCheckElimination)),
+                  allocator_.Adapter(kArenaAllocBoundsCheckElimination)),
+              allocator_.Adapter(kArenaAllocBoundsCheckElimination)),
+        first_index_bounds_check_map_(std::less<int>(),
+                                      allocator_.Adapter(kArenaAllocBoundsCheckElimination)),
+        early_exit_loop_(std::less<uint32_t>(),
+                         allocator_.Adapter(kArenaAllocBoundsCheckElimination)),
+        taken_test_loop_(std::less<uint32_t>(),
+                         allocator_.Adapter(kArenaAllocBoundsCheckElimination)),
+        finite_loop_(allocator_.Adapter(kArenaAllocBoundsCheckElimination)),
         has_dom_based_dynamic_bce_(false),
         initial_block_size_(graph->GetBlocks().size()),
         side_effects_(side_effects),
@@ -569,7 +568,7 @@
 
  private:
   // Return the map of proven value ranges at the beginning of a basic block.
-  ArenaSafeMap<int, ValueRange*>* GetValueRangeMap(HBasicBlock* basic_block) {
+  ScopedArenaSafeMap<int, ValueRange*>* GetValueRangeMap(HBasicBlock* basic_block) {
     if (IsAddedBlock(basic_block)) {
       // Added blocks don't keep value ranges.
       return nullptr;
@@ -580,7 +579,7 @@
   // Traverse up the dominator tree to look for value range info.
   ValueRange* LookupValueRange(HInstruction* instruction, HBasicBlock* basic_block) {
     while (basic_block != nullptr) {
-      ArenaSafeMap<int, ValueRange*>* map = GetValueRangeMap(basic_block);
+      ScopedArenaSafeMap<int, ValueRange*>* map = GetValueRangeMap(basic_block);
       if (map != nullptr) {
         if (map->find(instruction->GetId()) != map->end()) {
           return map->Get(instruction->GetId());
@@ -668,8 +667,8 @@
       if (successor != nullptr) {
         bool overflow;
         bool underflow;
-        ValueRange* new_left_range = new (GetGraph()->GetAllocator()) ValueRange(
-            GetGraph()->GetAllocator(),
+        ValueRange* new_left_range = new (&allocator_) ValueRange(
+            &allocator_,
             left_range->GetBound(),
             right_range->GetBound().Add(left_compensation, &overflow, &underflow));
         if (!overflow && !underflow) {
@@ -677,8 +676,8 @@
                                    new_left_range);
         }
 
-        ValueRange* new_right_range = new (GetGraph()->GetAllocator()) ValueRange(
-            GetGraph()->GetAllocator(),
+        ValueRange* new_right_range = new (&allocator_) ValueRange(
+            &allocator_,
             left_range->GetBound().Add(right_compensation, &overflow, &underflow),
             right_range->GetBound());
         if (!overflow && !underflow) {
@@ -750,8 +749,8 @@
         if (overflow || underflow) {
           return;
         }
-        ValueRange* new_range = new (GetGraph()->GetAllocator())
-            ValueRange(GetGraph()->GetAllocator(), ValueBound::Min(), new_upper);
+        ValueRange* new_range = new (&allocator_) ValueRange(
+            &allocator_, ValueBound::Min(), new_upper);
         ApplyRangeFromComparison(left, block, true_successor, new_range);
       }
 
@@ -762,8 +761,8 @@
         if (overflow || underflow) {
           return;
         }
-        ValueRange* new_range = new (GetGraph()->GetAllocator())
-            ValueRange(GetGraph()->GetAllocator(), new_lower, ValueBound::Max());
+        ValueRange* new_range = new (&allocator_) ValueRange(
+            &allocator_, new_lower, ValueBound::Max());
         ApplyRangeFromComparison(left, block, false_successor, new_range);
       }
     } else if (cond == kCondGT || cond == kCondGE) {
@@ -774,8 +773,8 @@
         if (overflow || underflow) {
           return;
         }
-        ValueRange* new_range = new (GetGraph()->GetAllocator())
-            ValueRange(GetGraph()->GetAllocator(), new_lower, ValueBound::Max());
+        ValueRange* new_range = new (&allocator_) ValueRange(
+            &allocator_, new_lower, ValueBound::Max());
         ApplyRangeFromComparison(left, block, true_successor, new_range);
       }
 
@@ -785,8 +784,8 @@
         if (overflow || underflow) {
           return;
         }
-        ValueRange* new_range = new (GetGraph()->GetAllocator())
-            ValueRange(GetGraph()->GetAllocator(), ValueBound::Min(), new_upper);
+        ValueRange* new_range = new (&allocator_) ValueRange(
+            &allocator_, ValueBound::Min(), new_upper);
         ApplyRangeFromComparison(left, block, false_successor, new_range);
       }
     } else if (cond == kCondNE || cond == kCondEQ) {
@@ -795,8 +794,7 @@
         //   length == [c,d] yields [c, d] along true
         //   length != [c,d] yields [c, d] along false
         if (!lower.Equals(ValueBound::Min()) || !upper.Equals(ValueBound::Max())) {
-          ValueRange* new_range = new (GetGraph()->GetAllocator())
-              ValueRange(GetGraph()->GetAllocator(), lower, upper);
+          ValueRange* new_range = new (&allocator_) ValueRange(&allocator_, lower, upper);
           ApplyRangeFromComparison(
               left, block, cond == kCondEQ ? true_successor : false_successor, new_range);
         }
@@ -804,8 +802,8 @@
         //   length == 0 yields [1, max] along false
         //   length != 0 yields [1, max] along true
         if (lower.GetConstant() == 0 && upper.GetConstant() == 0) {
-          ValueRange* new_range = new (GetGraph()->GetAllocator())
-              ValueRange(GetGraph()->GetAllocator(), ValueBound(nullptr, 1), ValueBound::Max());
+          ValueRange* new_range = new (&allocator_) ValueRange(
+              &allocator_, ValueBound(nullptr, 1), ValueBound::Max());
           ApplyRangeFromComparison(
               left, block, cond == kCondEQ ? false_successor : true_successor, new_range);
         }
@@ -826,7 +824,7 @@
       // Non-constant index.
       ValueBound lower = ValueBound(nullptr, 0);        // constant 0
       ValueBound upper = ValueBound(array_length, -1);  // array_length - 1
-      ValueRange array_range(GetGraph()->GetAllocator(), lower, upper);
+      ValueRange array_range(&allocator_, lower, upper);
       // Try index range obtained by dominator-based analysis.
       ValueRange* index_range = LookupValueRange(index, block);
       if (index_range != nullptr && index_range->FitsIn(&array_range)) {
@@ -875,8 +873,7 @@
       } else {
         ValueBound lower = ValueBound(nullptr, constant + 1);
         ValueBound upper = ValueBound::Max();
-        ValueRange* range = new (GetGraph()->GetAllocator())
-            ValueRange(GetGraph()->GetAllocator(), lower, upper);
+        ValueRange* range = new (&allocator_) ValueRange(&allocator_, lower, upper);
         AssignRange(block, array_length, range);
       }
     }
@@ -938,8 +935,8 @@
           ValueRange* range = nullptr;
           if (increment == 0) {
             // Add constant 0. It's really a fixed value.
-            range = new (GetGraph()->GetAllocator()) ValueRange(
-                GetGraph()->GetAllocator(),
+            range = new (&allocator_) ValueRange(
+                &allocator_,
                 ValueBound(initial_value, 0),
                 ValueBound(initial_value, 0));
           } else {
@@ -959,8 +956,8 @@
                 bound = increment > 0 ? ValueBound::Min() : ValueBound::Max();
               }
             }
-            range = new (GetGraph()->GetAllocator()) MonotonicValueRange(
-                GetGraph()->GetAllocator(),
+            range = new (&allocator_) MonotonicValueRange(
+                &allocator_,
                 phi,
                 initial_value,
                 increment,
@@ -1039,8 +1036,8 @@
                 !ValueBound::WouldAddOverflowOrUnderflow(c0, -c1)) {
               if ((c0 - c1) <= 0) {
                 // array.length + (c0 - c1) won't overflow/underflow.
-                ValueRange* range = new (GetGraph()->GetAllocator()) ValueRange(
-                    GetGraph()->GetAllocator(),
+                ValueRange* range = new (&allocator_) ValueRange(
+                    &allocator_,
                     ValueBound(nullptr, right_const - upper.GetConstant()),
                     ValueBound(array_length, right_const - lower.GetConstant()));
                 AssignRange(sub->GetBlock(), sub, range);
@@ -1087,8 +1084,8 @@
         // than array_length.
         return;
       }
-      ValueRange* range = new (GetGraph()->GetAllocator()) ValueRange(
-          GetGraph()->GetAllocator(),
+      ValueRange* range = new (&allocator_) ValueRange(
+          &allocator_,
           ValueBound(nullptr, std::numeric_limits<int32_t>::min()),
           ValueBound(left, 0));
       AssignRange(instruction->GetBlock(), instruction, range);
@@ -1113,8 +1110,8 @@
       if (constant > 0) {
         // constant serves as a mask so any number masked with it
         // gets a [0, constant] value range.
-        ValueRange* range = new (GetGraph()->GetAllocator()) ValueRange(
-            GetGraph()->GetAllocator(),
+        ValueRange* range = new (&allocator_) ValueRange(
+            &allocator_,
             ValueBound(nullptr, 0),
             ValueBound(nullptr, constant));
         AssignRange(instruction->GetBlock(), instruction, range);
@@ -1139,8 +1136,8 @@
       //   array[i % 10];  // index value range [0, 9]
       //   array[i % -10]; // index value range [0, 9]
       // }
-      ValueRange* right_range = new (GetGraph()->GetAllocator()) ValueRange(
-          GetGraph()->GetAllocator(),
+      ValueRange* right_range = new (&allocator_) ValueRange(
+          &allocator_,
           ValueBound(nullptr, 1 - right_const),
           ValueBound(nullptr, right_const - 1));
 
@@ -1169,8 +1166,8 @@
     if (right->IsArrayLength()) {
       ValueBound lower = ValueBound::Min();  // ideally, lower should be '1-array_length'.
       ValueBound upper = ValueBound(right, -1);  // array_length - 1
-      ValueRange* right_range = new (GetGraph()->GetAllocator()) ValueRange(
-          GetGraph()->GetAllocator(),
+      ValueRange* right_range = new (&allocator_) ValueRange(
+          &allocator_,
           lower,
           upper);
       ValueRange* left_range = LookupValueRange(left, instruction->GetBlock());
@@ -1195,8 +1192,7 @@
         // which isn't available as an instruction yet. new_array will
         // be treated the same as new_array.length when it's used in a ValueBound.
         ValueBound upper = ValueBound(new_array, -right_const);
-        ValueRange* range = new (GetGraph()->GetAllocator())
-            ValueRange(GetGraph()->GetAllocator(), lower, upper);
+        ValueRange* range = new (&allocator_) ValueRange(&allocator_, lower, upper);
         ValueRange* existing_range = LookupValueRange(left, new_array->GetBlock());
         if (existing_range != nullptr) {
           range = existing_range->Narrow(range);
@@ -1291,10 +1287,10 @@
       HInstruction* base = value.GetInstruction();
       int32_t min_c = base == nullptr ? 0 : value.GetConstant();
       int32_t max_c = value.GetConstant();
-      ArenaVector<HBoundsCheck*> candidates(
-          GetGraph()->GetAllocator()->Adapter(kArenaAllocBoundsCheckElimination));
-      ArenaVector<HBoundsCheck*> standby(
-          GetGraph()->GetAllocator()->Adapter(kArenaAllocBoundsCheckElimination));
+      ScopedArenaVector<HBoundsCheck*> candidates(
+          allocator_.Adapter(kArenaAllocBoundsCheckElimination));
+      ScopedArenaVector<HBoundsCheck*> standby(
+          allocator_.Adapter(kArenaAllocBoundsCheckElimination));
       for (const HUseListNode<HInstruction*>& use : array_length->GetUses()) {
         // Another bounds check in same or dominated block?
         HInstruction* user = use.GetUser();
@@ -1378,7 +1374,7 @@
           v2.is_known && (v2.a_constant == 0 || v2.a_constant == 1)) {
         DCHECK(v1.a_constant == 1 || v1.instruction == nullptr);
         DCHECK(v2.a_constant == 1 || v2.instruction == nullptr);
-        ValueRange index_range(GetGraph()->GetAllocator(),
+        ValueRange index_range(&allocator_,
                                ValueBound(v1.instruction, v1.b_constant),
                                ValueBound(v2.instruction, v2.b_constant));
         // If analysis reveals a certain OOB, disable dynamic BCE. Otherwise,
@@ -1410,10 +1406,10 @@
     HInstruction* base = value.GetInstruction();
     int32_t min_c = base == nullptr ? 0 : value.GetConstant();
     int32_t max_c = value.GetConstant();
-    ArenaVector<HBoundsCheck*> candidates(
-        GetGraph()->GetAllocator()->Adapter(kArenaAllocBoundsCheckElimination));
-    ArenaVector<HBoundsCheck*> standby(
-        GetGraph()->GetAllocator()->Adapter(kArenaAllocBoundsCheckElimination));
+    ScopedArenaVector<HBoundsCheck*> candidates(
+        allocator_.Adapter(kArenaAllocBoundsCheckElimination));
+    ScopedArenaVector<HBoundsCheck*> standby(
+        allocator_.Adapter(kArenaAllocBoundsCheckElimination));
     for (const HUseListNode<HInstruction*>& use : array_length->GetUses()) {
       HInstruction* user = use.GetUser();
       if (user->IsBoundsCheck() && loop == user->GetBlock()->GetLoopInformation()) {
@@ -1882,21 +1878,24 @@
     instruction->GetBlock()->RemoveInstruction(instruction);
   }
 
+  // Use local allocator for allocating memory.
+  ScopedArenaAllocator allocator_;
+
   // A set of maps, one per basic block, from instruction to range.
-  ArenaVector<ArenaSafeMap<int, ValueRange*>> maps_;
+  ScopedArenaVector<ScopedArenaSafeMap<int, ValueRange*>> maps_;
 
   // Map an HArrayLength instruction's id to the first HBoundsCheck instruction
   // in a block that checks an index against that HArrayLength.
-  ArenaSafeMap<int, HBoundsCheck*> first_index_bounds_check_map_;
+  ScopedArenaSafeMap<int, HBoundsCheck*> first_index_bounds_check_map_;
 
   // Early-exit loop bookkeeping.
-  ArenaSafeMap<uint32_t, bool> early_exit_loop_;
+  ScopedArenaSafeMap<uint32_t, bool> early_exit_loop_;
 
   // Taken-test loop bookkeeping.
-  ArenaSafeMap<uint32_t, HBasicBlock*> taken_test_loop_;
+  ScopedArenaSafeMap<uint32_t, HBasicBlock*> taken_test_loop_;
 
   // Finite loop bookkeeping.
-  ArenaSet<uint32_t> finite_loop_;
+  ScopedArenaSet<uint32_t> finite_loop_;
 
   // Flag that denotes whether dominator-based dynamic elimination has occurred.
   bool has_dom_based_dynamic_bce_;
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 5117e07..3cc7b0e 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -18,13 +18,18 @@
 
 #include "base/array_ref.h"
 #include "base/bit_vector-inl.h"
+#include "base/scoped_arena_allocator.h"
+#include "base/scoped_arena_containers.h"
 #include "base/stl_util.h"
 #include "ssa_phi_elimination.h"
 
 namespace art {
 
 static void MarkReachableBlocks(HGraph* graph, ArenaBitVector* visited) {
-  ArenaVector<HBasicBlock*> worklist(graph->GetAllocator()->Adapter(kArenaAllocDCE));
+  // Use local allocator for allocating memory.
+  ScopedArenaAllocator allocator(graph->GetArenaStack());
+
+  ScopedArenaVector<HBasicBlock*> worklist(allocator.Adapter(kArenaAllocDCE));
   constexpr size_t kDefaultWorlistSize = 8;
   worklist.reserve(kDefaultWorlistSize);
   visited->SetBit(graph->GetEntryBlock()->GetBlockId());
@@ -305,9 +310,12 @@
 }
 
 bool HDeadCodeElimination::RemoveDeadBlocks() {
+  // Use local allocator for allocating memory.
+  ScopedArenaAllocator allocator(graph_->GetArenaStack());
+
   // Classify blocks as reachable/unreachable.
-  ArenaAllocator* allocator = graph_->GetAllocator();
-  ArenaBitVector live_blocks(allocator, graph_->GetBlocks().size(), false, kArenaAllocDCE);
+  ArenaBitVector live_blocks(&allocator, graph_->GetBlocks().size(), false, kArenaAllocDCE);
+  live_blocks.ClearAllBits();
 
   MarkReachableBlocks(graph_, &live_blocks);
   bool removed_one_or_more_blocks = false;
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 1c7d1a0..b1ac027 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -22,8 +22,9 @@
 
 #include "android-base/stringprintf.h"
 
-#include "base/arena_containers.h"
 #include "base/bit_vector-inl.h"
+#include "base/scoped_arena_allocator.h"
+#include "base/scoped_arena_containers.h"
 
 namespace art {
 
@@ -47,10 +48,13 @@
 void GraphChecker::VisitBasicBlock(HBasicBlock* block) {
   current_block_ = block;
 
+  // Use local allocator for allocating memory.
+  ScopedArenaAllocator allocator(GetGraph()->GetArenaStack());
+
   // Check consistency with respect to predecessors of `block`.
   // Note: Counting duplicates with a sorted vector uses up to 6x less memory
   // than ArenaSafeMap<HBasicBlock*, size_t> and also allows storage reuse.
-  ArenaVector<HBasicBlock*>& sorted_predecessors = blocks_storage_;
+  ScopedArenaVector<HBasicBlock*> sorted_predecessors(allocator.Adapter(kArenaAllocGraphChecker));
   sorted_predecessors.assign(block->GetPredecessors().begin(), block->GetPredecessors().end());
   std::sort(sorted_predecessors.begin(), sorted_predecessors.end());
   for (auto it = sorted_predecessors.begin(), end = sorted_predecessors.end(); it != end; ) {
@@ -73,7 +77,7 @@
   // Check consistency with respect to successors of `block`.
   // Note: Counting duplicates with a sorted vector uses up to 6x less memory
   // than ArenaSafeMap<HBasicBlock*, size_t> and also allows storage reuse.
-  ArenaVector<HBasicBlock*>& sorted_successors = blocks_storage_;
+  ScopedArenaVector<HBasicBlock*> sorted_successors(allocator.Adapter(kArenaAllocGraphChecker));
   sorted_successors.assign(block->GetSuccessors().begin(), block->GetSuccessors().end());
   std::sort(sorted_successors.begin(), sorted_successors.end());
   for (auto it = sorted_successors.begin(), end = sorted_successors.end(); it != end; ) {
@@ -829,10 +833,14 @@
               phi->GetRegNumber(),
               type_str.str().c_str()));
         } else {
+          // Use local allocator for allocating memory.
+          ScopedArenaAllocator allocator(GetGraph()->GetArenaStack());
           // If we get here, make sure we allocate all the necessary storage at once
           // because the BitVector reallocation strategy has very bad worst-case behavior.
-          ArenaBitVector& visited = visited_storage_;
-          visited.SetBit(GetGraph()->GetCurrentInstructionId());
+          ArenaBitVector visited(&allocator,
+                                 GetGraph()->GetCurrentInstructionId(),
+                                 /* expandable */ false,
+                                 kArenaAllocGraphChecker);
           visited.ClearAllBits();
           if (!IsConstantEquivalent(phi, other_phi, &visited)) {
             AddError(StringPrintf("Two phis (%d and %d) found for VReg %d but they "
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index 6af7b42..0f0b49d 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -17,10 +17,13 @@
 #ifndef ART_COMPILER_OPTIMIZING_GRAPH_CHECKER_H_
 #define ART_COMPILER_OPTIMIZING_GRAPH_CHECKER_H_
 
-#include "nodes.h"
-
 #include <ostream>
 
+#include "base/arena_bit_vector.h"
+#include "base/bit_vector-inl.h"
+#include "base/scoped_arena_allocator.h"
+#include "nodes.h"
+
 namespace art {
 
 // A control-flow graph visitor performing various checks.
@@ -30,12 +33,10 @@
     : HGraphDelegateVisitor(graph),
       errors_(graph->GetAllocator()->Adapter(kArenaAllocGraphChecker)),
       dump_prefix_(dump_prefix),
-      seen_ids_(graph->GetAllocator(),
-                graph->GetCurrentInstructionId(),
-                false,
-                kArenaAllocGraphChecker),
-      blocks_storage_(graph->GetAllocator()->Adapter(kArenaAllocGraphChecker)),
-      visited_storage_(graph->GetAllocator(), 0u, true, kArenaAllocGraphChecker) {}
+      allocator_(graph->GetArenaStack()),
+      seen_ids_(&allocator_, graph->GetCurrentInstructionId(), false, kArenaAllocGraphChecker) {
+    seen_ids_.ClearAllBits();
+  }
 
   // Check the whole graph (in reverse post-order).
   void Run() {
@@ -104,12 +105,9 @@
  private:
   // String displayed before dumped errors.
   const char* const dump_prefix_;
+  ScopedArenaAllocator allocator_;
   ArenaBitVector seen_ids_;
 
-  // To reduce the total arena memory allocation, we reuse the same storage.
-  ArenaVector<HBasicBlock*> blocks_storage_;
-  ArenaBitVector visited_storage_;
-
   DISALLOW_COPY_AND_ASSIGN(GraphChecker);
 };
 
diff --git a/compiler/optimizing/load_store_analysis.h b/compiler/optimizing/load_store_analysis.h
index 6a25da3..5940ee7 100644
--- a/compiler/optimizing/load_store_analysis.h
+++ b/compiler/optimizing/load_store_analysis.h
@@ -25,7 +25,7 @@
 
 // A ReferenceInfo contains additional info about a reference such as
 // whether it's a singleton, returned, etc.
-class ReferenceInfo : public ArenaObject<kArenaAllocMisc> {
+class ReferenceInfo : public ArenaObject<kArenaAllocLSA> {
  public:
   ReferenceInfo(HInstruction* reference, size_t pos)
       : reference_(reference),
@@ -99,7 +99,7 @@
 
 // A heap location is a reference-offset/index pair that a value can be loaded from
 // or stored to.
-class HeapLocation : public ArenaObject<kArenaAllocMisc> {
+class HeapLocation : public ArenaObject<kArenaAllocLSA> {
  public:
   static constexpr size_t kInvalidFieldOffset = -1;
 
@@ -172,12 +172,12 @@
 
   explicit HeapLocationCollector(HGraph* graph)
       : HGraphVisitor(graph),
-        ref_info_array_(graph->GetAllocator()->Adapter(kArenaAllocLSE)),
-        heap_locations_(graph->GetAllocator()->Adapter(kArenaAllocLSE)),
+        ref_info_array_(graph->GetAllocator()->Adapter(kArenaAllocLSA)),
+        heap_locations_(graph->GetAllocator()->Adapter(kArenaAllocLSA)),
         aliasing_matrix_(graph->GetAllocator(),
                          kInitialAliasingMatrixBitVectorSize,
                          true,
-                         kArenaAllocLSE),
+                         kArenaAllocLSA),
         has_heap_stores_(false),
         has_volatile_(false),
         has_monitor_operations_(false) {}
diff --git a/compiler/optimizing/load_store_elimination.cc b/compiler/optimizing/load_store_elimination.cc
index 39bfc86..af5585e 100644
--- a/compiler/optimizing/load_store_elimination.cc
+++ b/compiler/optimizing/load_store_elimination.cc
@@ -16,6 +16,9 @@
 
 #include "load_store_elimination.h"
 
+#include "base/array_ref.h"
+#include "base/scoped_arena_allocator.h"
+#include "base/scoped_arena_containers.h"
 #include "escape.h"
 #include "load_store_analysis.h"
 #include "side_effects_analysis.h"
@@ -45,17 +48,18 @@
       : HGraphVisitor(graph, stats),
         heap_location_collector_(heap_locations_collector),
         side_effects_(side_effects),
+        allocator_(graph->GetArenaStack()),
         heap_values_for_(graph->GetBlocks().size(),
-                         ArenaVector<HInstruction*>(heap_locations_collector.
-                                                    GetNumberOfHeapLocations(),
-                                                    kUnknownHeapValue,
-                                                    graph->GetAllocator()->Adapter(kArenaAllocLSE)),
-                         graph->GetAllocator()->Adapter(kArenaAllocLSE)),
-        removed_loads_(graph->GetAllocator()->Adapter(kArenaAllocLSE)),
-        substitute_instructions_for_loads_(graph->GetAllocator()->Adapter(kArenaAllocLSE)),
-        possibly_removed_stores_(graph->GetAllocator()->Adapter(kArenaAllocLSE)),
-        singleton_new_instances_(graph->GetAllocator()->Adapter(kArenaAllocLSE)),
-        singleton_new_arrays_(graph->GetAllocator()->Adapter(kArenaAllocLSE)) {
+                         ScopedArenaVector<HInstruction*>(heap_locations_collector.
+                                                          GetNumberOfHeapLocations(),
+                                                          kUnknownHeapValue,
+                                                          allocator_.Adapter(kArenaAllocLSE)),
+                         allocator_.Adapter(kArenaAllocLSE)),
+        removed_loads_(allocator_.Adapter(kArenaAllocLSE)),
+        substitute_instructions_for_loads_(allocator_.Adapter(kArenaAllocLSE)),
+        possibly_removed_stores_(allocator_.Adapter(kArenaAllocLSE)),
+        singleton_new_instances_(allocator_.Adapter(kArenaAllocLSE)),
+        singleton_new_arrays_(allocator_.Adapter(kArenaAllocLSE)) {
   }
 
   void VisitBasicBlock(HBasicBlock* block) OVERRIDE {
@@ -146,7 +150,7 @@
   void HandleLoopSideEffects(HBasicBlock* block) {
     DCHECK(block->IsLoopHeader());
     int block_id = block->GetBlockId();
-    ArenaVector<HInstruction*>& heap_values = heap_values_for_[block_id];
+    ScopedArenaVector<HInstruction*>& heap_values = heap_values_for_[block_id];
 
     // Don't eliminate loads in irreducible loops. This is safe for singletons, because
     // they are always used by the non-eliminated loop-phi.
@@ -160,7 +164,7 @@
     }
 
     HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader();
-    ArenaVector<HInstruction*>& pre_header_heap_values =
+    ScopedArenaVector<HInstruction*>& pre_header_heap_values =
         heap_values_for_[pre_header->GetBlockId()];
 
     // Inherit the values from pre-header.
@@ -191,12 +195,12 @@
   }
 
   void MergePredecessorValues(HBasicBlock* block) {
-    const ArenaVector<HBasicBlock*>& predecessors = block->GetPredecessors();
+    ArrayRef<HBasicBlock* const> predecessors(block->GetPredecessors());
     if (predecessors.size() == 0) {
       return;
     }
 
-    ArenaVector<HInstruction*>& heap_values = heap_values_for_[block->GetBlockId()];
+    ScopedArenaVector<HInstruction*>& heap_values = heap_values_for_[block->GetBlockId()];
     for (size_t i = 0; i < heap_values.size(); i++) {
       HInstruction* merged_value = nullptr;
       // Whether merged_value is a result that's merged from all predecessors.
@@ -234,7 +238,8 @@
         // or the heap value may be needed after method return or deoptimization.
         // Keep the last store in each predecessor since future loads cannot be eliminated.
         for (HBasicBlock* predecessor : predecessors) {
-          ArenaVector<HInstruction*>& pred_values = heap_values_for_[predecessor->GetBlockId()];
+          ScopedArenaVector<HInstruction*>& pred_values =
+              heap_values_for_[predecessor->GetBlockId()];
           KeepIfIsStore(pred_values[i]);
         }
       }
@@ -303,7 +308,7 @@
     size_t idx = heap_location_collector_.FindHeapLocationIndex(
         ref_info, offset, index, declaring_class_def_index);
     DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound);
-    ArenaVector<HInstruction*>& heap_values =
+    ScopedArenaVector<HInstruction*>& heap_values =
         heap_values_for_[instruction->GetBlock()->GetBlockId()];
     HInstruction* heap_value = heap_values[idx];
     if (heap_value == kDefaultHeapValue) {
@@ -369,7 +374,7 @@
     size_t idx = heap_location_collector_.FindHeapLocationIndex(
         ref_info, offset, index, declaring_class_def_index);
     DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound);
-    ArenaVector<HInstruction*>& heap_values =
+    ScopedArenaVector<HInstruction*>& heap_values =
         heap_values_for_[instruction->GetBlock()->GetBlockId()];
     HInstruction* heap_value = heap_values[idx];
     bool same_value = false;
@@ -496,7 +501,7 @@
   }
 
   void VisitDeoptimize(HDeoptimize* instruction) {
-    const ArenaVector<HInstruction*>& heap_values =
+    const ScopedArenaVector<HInstruction*>& heap_values =
         heap_values_for_[instruction->GetBlock()->GetBlockId()];
     for (HInstruction* heap_value : heap_values) {
       // Filter out fake instructions before checking instruction kind below.
@@ -523,7 +528,7 @@
   }
 
   void HandleInvoke(HInstruction* invoke) {
-    ArenaVector<HInstruction*>& heap_values =
+    ScopedArenaVector<HInstruction*>& heap_values =
         heap_values_for_[invoke->GetBlock()->GetBlockId()];
     for (size_t i = 0; i < heap_values.size(); i++) {
       ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo();
@@ -590,7 +595,7 @@
         !new_instance->NeedsChecks()) {
       singleton_new_instances_.push_back(new_instance);
     }
-    ArenaVector<HInstruction*>& heap_values =
+    ScopedArenaVector<HInstruction*>& heap_values =
         heap_values_for_[new_instance->GetBlock()->GetBlockId()];
     for (size_t i = 0; i < heap_values.size(); i++) {
       HInstruction* ref =
@@ -612,7 +617,7 @@
     if (ref_info->IsSingletonAndRemovable()) {
       singleton_new_arrays_.push_back(new_array);
     }
-    ArenaVector<HInstruction*>& heap_values =
+    ScopedArenaVector<HInstruction*>& heap_values =
         heap_values_for_[new_array->GetBlock()->GetBlockId()];
     for (size_t i = 0; i < heap_values.size(); i++) {
       HeapLocation* location = heap_location_collector_.GetHeapLocation(i);
@@ -639,20 +644,23 @@
   const HeapLocationCollector& heap_location_collector_;
   const SideEffectsAnalysis& side_effects_;
 
+  // Use local allocator for allocating memory.
+  ScopedArenaAllocator allocator_;
+
   // One array of heap values for each block.
-  ArenaVector<ArenaVector<HInstruction*>> heap_values_for_;
+  ScopedArenaVector<ScopedArenaVector<HInstruction*>> heap_values_for_;
 
   // We record the instructions that should be eliminated but may be
   // used by heap locations. They'll be removed in the end.
-  ArenaVector<HInstruction*> removed_loads_;
-  ArenaVector<HInstruction*> substitute_instructions_for_loads_;
+  ScopedArenaVector<HInstruction*> removed_loads_;
+  ScopedArenaVector<HInstruction*> substitute_instructions_for_loads_;
 
   // Stores in this list may be removed from the list later when it's
   // found that the store cannot be eliminated.
-  ArenaVector<HInstruction*> possibly_removed_stores_;
+  ScopedArenaVector<HInstruction*> possibly_removed_stores_;
 
-  ArenaVector<HInstruction*> singleton_new_instances_;
-  ArenaVector<HInstruction*> singleton_new_arrays_;
+  ScopedArenaVector<HInstruction*> singleton_new_instances_;
+  ScopedArenaVector<HInstruction*> singleton_new_arrays_;
 
   DISALLOW_COPY_AND_ASSIGN(LSEVisitor);
 };
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 6d9ebc8..cb9dc42 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -18,8 +18,11 @@
 
 #include "art_field-inl.h"
 #include "art_method-inl.h"
+#include "base/scoped_arena_allocator.h"
+#include "base/scoped_arena_containers.h"
 #include "base/enums.h"
 #include "class_linker-inl.h"
+#include "handle_scope-inl.h"
 #include "mirror/class-inl.h"
 #include "mirror/dex_cache.h"
 #include "scoped_thread_state_change-inl.h"
@@ -70,14 +73,16 @@
              Handle<mirror::ClassLoader> class_loader,
              Handle<mirror::DexCache> hint_dex_cache,
              HandleCache* handle_cache,
-             ArenaVector<HInstruction*>* worklist,
              bool is_first_run)
     : HGraphDelegateVisitor(graph),
       class_loader_(class_loader),
       hint_dex_cache_(hint_dex_cache),
       handle_cache_(handle_cache),
-      worklist_(worklist),
-      is_first_run_(is_first_run) {}
+      allocator_(graph->GetArenaStack()),
+      worklist_(allocator_.Adapter(kArenaAllocReferenceTypePropagation)),
+      is_first_run_(is_first_run) {
+    worklist_.reserve(kDefaultWorklistSize);
+  }
 
   void VisitDeoptimize(HDeoptimize* deopt) OVERRIDE;
   void VisitNewInstance(HNewInstance* new_instance) OVERRIDE;
@@ -87,9 +92,6 @@
   void VisitLoadException(HLoadException* instr) OVERRIDE;
   void VisitNewArray(HNewArray* instr) OVERRIDE;
   void VisitParameterValue(HParameterValue* instr) OVERRIDE;
-  void UpdateFieldAccessTypeInfo(HInstruction* instr, const FieldInfo& info);
-  void SetClassAsTypeInfo(HInstruction* instr, ObjPtr<mirror::Class> klass, bool is_exact)
-      REQUIRES_SHARED(Locks::mutator_lock_);
   void VisitInstanceFieldGet(HInstanceFieldGet* instr) OVERRIDE;
   void VisitStaticFieldGet(HStaticFieldGet* instr) OVERRIDE;
   void VisitUnresolvedInstanceFieldGet(HUnresolvedInstanceFieldGet* instr) OVERRIDE;
@@ -99,16 +101,39 @@
   void VisitCheckCast(HCheckCast* instr) OVERRIDE;
   void VisitBoundType(HBoundType* instr) OVERRIDE;
   void VisitNullCheck(HNullCheck* instr) OVERRIDE;
+  void VisitPhi(HPhi* phi);
+
+  void VisitBasicBlock(HBasicBlock* block);
+  void ProcessWorklist();
+
+ private:
+  void UpdateFieldAccessTypeInfo(HInstruction* instr, const FieldInfo& info);
+  void SetClassAsTypeInfo(HInstruction* instr, ObjPtr<mirror::Class> klass, bool is_exact)
+      REQUIRES_SHARED(Locks::mutator_lock_);
+  void BoundTypeForIfNotNull(HBasicBlock* block);
+  static void BoundTypeForIfInstanceOf(HBasicBlock* block);
+  static bool UpdateNullability(HInstruction* instr);
+  static void UpdateBoundType(HBoundType* bound_type) REQUIRES_SHARED(Locks::mutator_lock_);
+  void UpdateArrayGet(HArrayGet* instr) REQUIRES_SHARED(Locks::mutator_lock_);
+  void UpdatePhi(HPhi* phi) REQUIRES_SHARED(Locks::mutator_lock_);
+  bool UpdateReferenceTypeInfo(HInstruction* instr);
   void UpdateReferenceTypeInfo(HInstruction* instr,
                                dex::TypeIndex type_idx,
                                const DexFile& dex_file,
                                bool is_exact);
 
- private:
+  void AddToWorklist(HInstruction* instruction);
+  void AddDependentInstructionsToWorklist(HInstruction* instruction);
+
+  static constexpr size_t kDefaultWorklistSize = 8;
+
   Handle<mirror::ClassLoader> class_loader_;
   Handle<mirror::DexCache> hint_dex_cache_;
-  HandleCache* handle_cache_;
-  ArenaVector<HInstruction*>* worklist_;
+  HandleCache* const handle_cache_;
+
+  // Use local allocator for allocating memory.
+  ScopedArenaAllocator allocator_;
+  ScopedArenaVector<HInstruction*> worklist_;
   const bool is_first_run_;
 };
 
@@ -122,7 +147,6 @@
       class_loader_(class_loader),
       hint_dex_cache_(hint_dex_cache),
       handle_cache_(handles),
-      worklist_(graph->GetAllocator()->Adapter(kArenaAllocReferenceTypePropagation)),
       is_first_run_(is_first_run) {
 }
 
@@ -158,7 +182,6 @@
                      class_loader_,
                      hint_dex_cache_,
                      &handle_cache_,
-                     &worklist_,
                      is_first_run_);
   instruction->Accept(&visitor);
 }
@@ -319,26 +342,20 @@
 }
 
 void ReferenceTypePropagation::Run() {
-  worklist_.reserve(kDefaultWorklistSize);
+  RTPVisitor visitor(graph_, class_loader_, hint_dex_cache_, &handle_cache_, is_first_run_);
 
   // To properly propagate type info we need to visit in the dominator-based order.
   // Reverse post order guarantees a node's dominators are visited first.
   // We take advantage of this order in `VisitBasicBlock`.
   for (HBasicBlock* block : graph_->GetReversePostOrder()) {
-    VisitBasicBlock(block);
+    visitor.VisitBasicBlock(block);
   }
 
-  ProcessWorklist();
+  visitor.ProcessWorklist();
   ValidateTypes();
 }
 
-void ReferenceTypePropagation::VisitBasicBlock(HBasicBlock* block) {
-  RTPVisitor visitor(graph_,
-                     class_loader_,
-                     hint_dex_cache_,
-                     &handle_cache_,
-                     &worklist_,
-                     is_first_run_);
+void ReferenceTypePropagation::RTPVisitor::VisitBasicBlock(HBasicBlock* block) {
   // Handle Phis first as there might be instructions in the same block who depend on them.
   for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
     VisitPhi(it.Current()->AsPhi());
@@ -348,7 +365,7 @@
   // last visited instruction, use `HInstructionIteratorHandleChanges` iterator.
   for (HInstructionIteratorHandleChanges it(block->GetInstructions()); !it.Done(); it.Advance()) {
     HInstruction* instr = it.Current();
-    instr->Accept(&visitor);
+    instr->Accept(this);
   }
 
   // Add extra nodes to bound types.
@@ -357,7 +374,7 @@
   BoundTypeForClassCheck(block->GetLastInstruction());
 }
 
-void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) {
+void ReferenceTypePropagation::RTPVisitor::BoundTypeForIfNotNull(HBasicBlock* block) {
   HIf* ifInstruction = block->GetLastInstruction()->AsIf();
   if (ifInstruction == nullptr) {
     return;
@@ -391,7 +408,7 @@
       : ifInstruction->IfFalseSuccessor();
 
   ReferenceTypeInfo object_rti = ReferenceTypeInfo::Create(
-      handle_cache_.GetObjectClassHandle(), /* is_exact */ false);
+      handle_cache_->GetObjectClassHandle(), /* is_exact */ false);
 
   BoundTypeIn(obj, notNullBlock, /* start_instruction */ nullptr, object_rti);
 }
@@ -469,7 +486,7 @@
 // `if (x instanceof ClassX) { }`
 // If that's the case insert an HBoundType instruction to bound the type of `x`
 // to `ClassX` in the scope of the dominated blocks.
-void ReferenceTypePropagation::BoundTypeForIfInstanceOf(HBasicBlock* block) {
+void ReferenceTypePropagation::RTPVisitor::BoundTypeForIfInstanceOf(HBasicBlock* block) {
   HIf* ifInstruction = block->GetLastInstruction()->AsIf();
   if (ifInstruction == nullptr) {
     return;
@@ -728,7 +745,7 @@
   }
 }
 
-void ReferenceTypePropagation::VisitPhi(HPhi* phi) {
+void ReferenceTypePropagation::RTPVisitor::VisitPhi(HPhi* phi) {
   if (phi->IsDead() || phi->GetType() != DataType::Type::kReference) {
     return;
   }
@@ -812,7 +829,7 @@
   return ReferenceTypeInfo::Create(result_type_handle, is_exact);
 }
 
-void ReferenceTypePropagation::UpdateArrayGet(HArrayGet* instr, HandleCache* handle_cache) {
+void ReferenceTypePropagation::RTPVisitor::UpdateArrayGet(HArrayGet* instr) {
   DCHECK_EQ(DataType::Type::kReference, instr->GetType());
 
   ReferenceTypeInfo parent_rti = instr->InputAt(0)->GetReferenceTypeInfo();
@@ -823,7 +840,7 @@
   Handle<mirror::Class> handle = parent_rti.GetTypeHandle();
   if (handle->IsObjectArrayClass() && IsAdmissible(handle->GetComponentType())) {
     ReferenceTypeInfo::TypeHandle component_handle =
-        handle_cache->NewHandle(handle->GetComponentType());
+        handle_cache_->NewHandle(handle->GetComponentType());
     bool is_exact = component_handle->CannotBeAssignedFromOtherTypes();
     instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(component_handle, is_exact));
   } else {
@@ -832,7 +849,7 @@
   }
 }
 
-bool ReferenceTypePropagation::UpdateReferenceTypeInfo(HInstruction* instr) {
+bool ReferenceTypePropagation::RTPVisitor::UpdateReferenceTypeInfo(HInstruction* instr) {
   ScopedObjectAccess soa(Thread::Current());
 
   ReferenceTypeInfo previous_rti = instr->GetReferenceTypeInfo();
@@ -848,7 +865,7 @@
   } else if (instr->IsArrayGet()) {
     // TODO: consider if it's worth "looking back" and binding the input object
     // to an array type.
-    UpdateArrayGet(instr->AsArrayGet(), &handle_cache_);
+    UpdateArrayGet(instr->AsArrayGet());
   } else {
     LOG(FATAL) << "Invalid instruction (should not get here)";
   }
@@ -873,13 +890,13 @@
   }
 
   ScopedObjectAccess soa(Thread::Current());
-  UpdateArrayGet(instr, handle_cache_);
+  UpdateArrayGet(instr);
   if (!instr->GetReferenceTypeInfo().IsValid()) {
-    worklist_->push_back(instr);
+    worklist_.push_back(instr);
   }
 }
 
-void ReferenceTypePropagation::UpdateBoundType(HBoundType* instr) {
+void ReferenceTypePropagation::RTPVisitor::UpdateBoundType(HBoundType* instr) {
   ReferenceTypeInfo input_rti = instr->InputAt(0)->GetReferenceTypeInfo();
   if (!input_rti.IsValid()) {
     return;  // No new info yet.
@@ -903,7 +920,7 @@
 
 // NullConstant inputs are ignored during merging as they do not provide any useful information.
 // If all the inputs are NullConstants then the type of the phi will be set to Object.
-void ReferenceTypePropagation::UpdatePhi(HPhi* instr) {
+void ReferenceTypePropagation::RTPVisitor::UpdatePhi(HPhi* instr) {
   DCHECK(instr->IsLive());
 
   HInputsRef inputs = instr->GetInputs();
@@ -931,7 +948,7 @@
     if (inputs[i]->IsNullConstant()) {
       continue;
     }
-    new_rti = MergeTypes(new_rti, inputs[i]->GetReferenceTypeInfo(), &handle_cache_);
+    new_rti = MergeTypes(new_rti, inputs[i]->GetReferenceTypeInfo(), handle_cache_);
     if (new_rti.IsValid() && new_rti.IsObjectClass()) {
       if (!new_rti.IsExact()) {
         break;
@@ -948,7 +965,7 @@
 
 // Re-computes and updates the nullability of the instruction. Returns whether or
 // not the nullability was changed.
-bool ReferenceTypePropagation::UpdateNullability(HInstruction* instr) {
+bool ReferenceTypePropagation::RTPVisitor::UpdateNullability(HInstruction* instr) {
   DCHECK((instr->IsPhi() && instr->AsPhi()->IsLive())
       || instr->IsBoundType()
       || instr->IsNullCheck()
@@ -976,7 +993,7 @@
   return existing_can_be_null != instr->CanBeNull();
 }
 
-void ReferenceTypePropagation::ProcessWorklist() {
+void ReferenceTypePropagation::RTPVisitor::ProcessWorklist() {
   while (!worklist_.empty()) {
     HInstruction* instruction = worklist_.back();
     worklist_.pop_back();
@@ -988,13 +1005,14 @@
   }
 }
 
-void ReferenceTypePropagation::AddToWorklist(HInstruction* instruction) {
+void ReferenceTypePropagation::RTPVisitor::AddToWorklist(HInstruction* instruction) {
   DCHECK_EQ(instruction->GetType(), DataType::Type::kReference)
       << instruction->DebugName() << ":" << instruction->GetType();
   worklist_.push_back(instruction);
 }
 
-void ReferenceTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) {
+void ReferenceTypePropagation::RTPVisitor::AddDependentInstructionsToWorklist(
+    HInstruction* instruction) {
   for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
     HInstruction* user = use.GetUser();
     if ((user->IsPhi() && user->AsPhi()->IsLive())
diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h
index c221282..fd4dad2 100644
--- a/compiler/optimizing/reference_type_propagation.h
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -18,12 +18,10 @@
 #define ART_COMPILER_OPTIMIZING_REFERENCE_TYPE_PROPAGATION_H_
 
 #include "base/arena_containers.h"
-#include "driver/dex_compilation_unit.h"
-#include "handle_scope-inl.h"
+#include "mirror/class-inl.h"
 #include "nodes.h"
 #include "obj_ptr.h"
 #include "optimization.h"
-#include "optimizing_compiler_stats.h"
 
 namespace art {
 
@@ -91,22 +89,6 @@
 
   class RTPVisitor;
 
-  void VisitPhi(HPhi* phi);
-  void VisitBasicBlock(HBasicBlock* block);
-  void UpdateBoundType(HBoundType* bound_type) REQUIRES_SHARED(Locks::mutator_lock_);
-  void UpdatePhi(HPhi* phi) REQUIRES_SHARED(Locks::mutator_lock_);
-  void BoundTypeForIfNotNull(HBasicBlock* block);
-  void BoundTypeForIfInstanceOf(HBasicBlock* block);
-  void ProcessWorklist();
-  void AddToWorklist(HInstruction* instr);
-  void AddDependentInstructionsToWorklist(HInstruction* instr);
-
-  bool UpdateNullability(HInstruction* instr);
-  bool UpdateReferenceTypeInfo(HInstruction* instr);
-
-  static void UpdateArrayGet(HArrayGet* instr, HandleCache* handle_cache)
-      REQUIRES_SHARED(Locks::mutator_lock_);
-
   static ReferenceTypeInfo MergeTypes(const ReferenceTypeInfo& a,
                                       const ReferenceTypeInfo& b,
                                       HandleCache* handle_cache)
@@ -122,13 +104,9 @@
   Handle<mirror::DexCache> hint_dex_cache_;
   HandleCache handle_cache_;
 
-  ArenaVector<HInstruction*> worklist_;
-
   // Whether this reference type propagation is the first run we are doing.
   const bool is_first_run_;
 
-  static constexpr size_t kDefaultWorklistSize = 8;
-
   friend class ReferenceTypePropagationTest;
 
   DISALLOW_COPY_AND_ASSIGN(ReferenceTypePropagation);
diff --git a/compiler/optimizing/select_generator.cc b/compiler/optimizing/select_generator.cc
index 0e46aec..77ec9a6 100644
--- a/compiler/optimizing/select_generator.cc
+++ b/compiler/optimizing/select_generator.cc
@@ -16,6 +16,8 @@
 
 #include "select_generator.h"
 
+#include "reference_type_propagation.h"
+
 namespace art {
 
 static constexpr size_t kMaxInstructionsInBranch = 1u;
diff --git a/compiler/optimizing/select_generator.h b/compiler/optimizing/select_generator.h
index c060146..f8cf00e 100644
--- a/compiler/optimizing/select_generator.h
+++ b/compiler/optimizing/select_generator.h
@@ -58,7 +58,6 @@
 #define ART_COMPILER_OPTIMIZING_SELECT_GENERATOR_H_
 
 #include "optimization.h"
-#include "reference_type_propagation.h"
 
 namespace art {
 
diff --git a/runtime/base/arena_allocator.cc b/runtime/base/arena_allocator.cc
index 79cf087..2e35f8a 100644
--- a/runtime/base/arena_allocator.cc
+++ b/runtime/base/arena_allocator.cc
@@ -72,6 +72,7 @@
   "InductionVar ",
   "BCE          ",
   "DCE          ",
+  "LSA          ",
   "LSE          ",
   "CFRE         ",
   "LICM         ",
diff --git a/runtime/base/arena_allocator.h b/runtime/base/arena_allocator.h
index 212edfb..a327cb0 100644
--- a/runtime/base/arena_allocator.h
+++ b/runtime/base/arena_allocator.h
@@ -79,6 +79,7 @@
   kArenaAllocInductionVarAnalysis,
   kArenaAllocBoundsCheckElimination,
   kArenaAllocDCE,
+  kArenaAllocLSA,
   kArenaAllocLSE,
   kArenaAllocCFRE,
   kArenaAllocLICM,