Optimizing: Speed up HEnvironment use removal

Removal of use records from HEnvironment vregs involved iterating over
potentially large linked lists which made compilation of huge methods
very slow. This patch turns use lists into doubly-linked lists, stores
pointers to the relevant nodes inside HEnvironment and subsequently
turns the removals into constant-time operations.

Change-Id: I0e1d4d782fd624e7b8075af75d4adf0a0634a1ee

13 files changed, 213 insertions, 151 deletions

diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 4d74c4e936..35c52690de 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -146,7 +146,7 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) {
   }
 
   // Ensure the uses of `instruction` are defined in a block of the graph.
-  for (HUseIterator<HInstruction> use_it(instruction->GetUses());
+  for (HUseIterator<HInstruction*> use_it(instruction->GetUses());
        !use_it.Done(); use_it.Advance()) {
     HInstruction* use = use_it.Current()->GetUser();
     const HInstructionList& list = use->IsPhi()
@@ -254,7 +254,7 @@ void SSAChecker::VisitInstruction(HInstruction* instruction) {
   super_type::VisitInstruction(instruction);
 
   // Ensure an instruction dominates all its uses.
-  for (HUseIterator<HInstruction> use_it(instruction->GetUses());
+  for (HUseIterator<HInstruction*> use_it(instruction->GetUses());
        !use_it.Done(); use_it.Advance()) {
     HInstruction* use = use_it.Current()->GetUser();
     if (!use->IsPhi() && !instruction->StrictlyDominates(use)) {
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index d7dcb4c5db..c606bd7a29 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -225,7 +225,7 @@ class HGraphVisualizerPrinter : public HGraphVisitor {
       HInstruction* instruction = it.Current();
       AddIndent();
       int bci = 0;
-      output_ << bci << " " << instruction->NumberOfUses()
+      output_ << bci << " " << instruction->ExpensiveComputeNumberOfUses()
               << " " << GetTypeId(instruction->GetType()) << instruction->GetId() << " ";
       PrintInstruction(instruction);
       output_ << kEndInstructionMarker << std::endl;
diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc
index ff23eda21e..2097ea6ad8 100644
--- a/compiler/optimizing/live_ranges_test.cc
+++ b/compiler/optimizing/live_ranges_test.cc
@@ -432,7 +432,7 @@ TEST(LiveRangesTest, CFG4) {
   ASSERT_TRUE(range->GetNext() == nullptr);
 
   HPhi* phi = liveness.GetInstructionFromSsaIndex(4)->AsPhi();
-  ASSERT_EQ(phi->NumberOfUses(), 1u);
+  ASSERT_EQ(phi->ExpensiveComputeNumberOfUses(), 1u);
   interval = phi->GetLiveInterval();
   range = interval->GetFirstRange();
   ASSERT_EQ(26u, range->GetStart());
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index ec53366e19..fe9ce740da 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -39,9 +39,11 @@ static void RemoveAsUser(HInstruction* instruction) {
   HEnvironment* environment = instruction->GetEnvironment();
   if (environment != nullptr) {
     for (size_t i = 0, e = environment->Size(); i < e; ++i) {
-      HInstruction* vreg = environment->GetInstructionAt(i);
-      if (vreg != nullptr) {
-        vreg->RemoveEnvironmentUser(environment, i);
+      HUseListNode<HEnvironment*>* vreg_env_use = environment->GetInstructionEnvUseAt(i);
+      if (vreg_env_use != nullptr) {
+        HInstruction* vreg = environment->GetInstructionAt(i);
+        DCHECK(vreg != nullptr);
+        vreg->RemoveEnvironmentUser(vreg_env_use);
       }
     }
   }
@@ -425,8 +427,8 @@ static void Remove(HInstructionList* instruction_list,
                    HBasicBlock* block,
                    HInstruction* instruction) {
   DCHECK_EQ(block, instruction->GetBlock());
-  DCHECK(instruction->GetUses() == nullptr);
-  DCHECK(instruction->GetEnvUses() == nullptr);
+  DCHECK(instruction->GetUses().IsEmpty());
+  DCHECK(instruction->GetEnvUses().IsEmpty());
   instruction->SetBlock(nullptr);
   instruction_list->RemoveInstruction(instruction);
 
@@ -441,22 +443,24 @@ void HBasicBlock::RemovePhi(HPhi* phi) {
   Remove(&phis_, this, phi);
 }
 
+void HEnvironment::CopyFrom(HEnvironment* env) {
+  for (size_t i = 0; i < env->Size(); i++) {
+    HInstruction* instruction = env->GetInstructionAt(i);
+    SetRawEnvAt(i, instruction);
+    if (instruction != nullptr) {
+      instruction->AddEnvUseAt(this, i);
+    }
+  }
+}
+
 template <typename T>
-static void RemoveFromUseList(T* user,
-                              size_t input_index,
-                              HUseListNode<T>** list) {
-  HUseListNode<T>* previous = nullptr;
-  HUseListNode<T>* current = *list;
-  while (current != nullptr) {
+static void RemoveFromUseList(T user, size_t input_index, HUseList<T>* list) {
+  HUseListNode<T>* current;
+  for (HUseIterator<HInstruction*> use_it(*list); !use_it.Done(); use_it.Advance()) {
+    current = use_it.Current();
     if (current->GetUser() == user && current->GetIndex() == input_index) {
-      if (previous == nullptr) {
-        *list = current->GetTail();
-      } else {
-        previous->SetTail(current->GetTail());
-      }
+      list->Remove(current);
     }
-    previous = current;
-    current = current->GetTail();
   }
 }
 
@@ -480,8 +484,8 @@ void HInstruction::RemoveUser(HInstruction* user, size_t input_index) {
   RemoveFromUseList(user, input_index, &uses_);
 }
 
-void HInstruction::RemoveEnvironmentUser(HEnvironment* user, size_t input_index) {
-  RemoveFromUseList(user, input_index, &env_uses_);
+void HInstruction::RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use) {
+  env_uses_.Remove(use);
 }
 
 void HInstructionList::AddInstruction(HInstruction* instruction) {
@@ -573,24 +577,24 @@ bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const {
 
 void HInstruction::ReplaceWith(HInstruction* other) {
   DCHECK(other != nullptr);
-  for (HUseIterator<HInstruction> it(GetUses()); !it.Done(); it.Advance()) {
-    HUseListNode<HInstruction>* current = it.Current();
+  for (HUseIterator<HInstruction*> it(GetUses()); !it.Done(); it.Advance()) {
+    HUseListNode<HInstruction*>* current = it.Current();
     HInstruction* user = current->GetUser();
     size_t input_index = current->GetIndex();
     user->SetRawInputAt(input_index, other);
     other->AddUseAt(user, input_index);
   }
 
-  for (HUseIterator<HEnvironment> it(GetEnvUses()); !it.Done(); it.Advance()) {
-    HUseListNode<HEnvironment>* current = it.Current();
+  for (HUseIterator<HEnvironment*> it(GetEnvUses()); !it.Done(); it.Advance()) {
+    HUseListNode<HEnvironment*>* current = it.Current();
     HEnvironment* user = current->GetUser();
     size_t input_index = current->GetIndex();
     user->SetRawEnvAt(input_index, other);
     other->AddEnvUseAt(user, input_index);
   }
 
-  uses_ = nullptr;
-  env_uses_ = nullptr;
+  uses_.Clear();
+  env_uses_.Clear();
 }
 
 void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) {
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index e19bfce9de..cac78f602c 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -587,26 +587,104 @@ FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
   }                                                                     \
   virtual void Accept(HGraphVisitor* visitor)
 
+template <typename T> class HUseList;
+
 template <typename T>
 class HUseListNode : public ArenaObject<kArenaAllocMisc> {
  public:
-  HUseListNode(T* user, size_t index, HUseListNode* tail)
-      : user_(user), index_(index), tail_(tail) {}
-
-  HUseListNode* GetTail() const { return tail_; }
-  T* GetUser() const { return user_; }
+  HUseListNode* GetPrevious() const { return prev_; }
+  HUseListNode* GetNext() const { return next_; }
+  T GetUser() const { return user_; }
   size_t GetIndex() const { return index_; }
 
-  void SetTail(HUseListNode<T>* node) { tail_ = node; }
-
  private:
-  T* const user_;
+  HUseListNode(T user, size_t index)
+      : user_(user), index_(index), prev_(nullptr), next_(nullptr) {}
+
+  T const user_;
   const size_t index_;
-  HUseListNode<T>* tail_;
+  HUseListNode<T>* prev_;
+  HUseListNode<T>* next_;
+
+  friend class HUseList<T>;
 
   DISALLOW_COPY_AND_ASSIGN(HUseListNode);
 };
 
+template <typename T>
+class HUseList : public ValueObject {
+ public:
+  HUseList() : first_(nullptr) {}
+
+  void Clear() {
+    first_ = nullptr;
+  }
+
+  // Adds a new entry at the beginning of the use list and returns
+  // the newly created node.
+  HUseListNode<T>* AddUse(T user, size_t index, ArenaAllocator* arena) {
+    HUseListNode<T>* new_node = new(arena) HUseListNode<T>(user, index);
+    if (IsEmpty()) {
+      first_ = new_node;
+    } else {
+      first_->prev_ = new_node;
+      new_node->next_ = first_;
+      first_ = new_node;
+    }
+    return new_node;
+  }
+
+  HUseListNode<T>* GetFirst() const {
+    return first_;
+  }
+
+  void Remove(HUseListNode<T>* node) {
+    if (node->prev_ != nullptr) {
+      node->prev_->next_ = node->next_;
+    }
+    if (node->next_ != nullptr) {
+      node->next_->prev_ = node->prev_;
+    }
+    if (node == first_) {
+      first_ = node->next_;
+    }
+  }
+
+  bool IsEmpty() const {
+    return first_ == nullptr;
+  }
+
+  bool HasOnlyOneUse() const {
+    return first_ != nullptr && first_->next_ == nullptr;
+  }
+
+ private:
+  HUseListNode<T>* first_;
+};
+
+template<typename T>
+class HUseIterator : public ValueObject {
+ public:
+  explicit HUseIterator(const HUseList<T>& uses) : current_(uses.GetFirst()) {}
+
+  bool Done() const { return current_ == nullptr; }
+
+  void Advance() {
+    DCHECK(!Done());
+    current_ = current_->GetNext();
+  }
+
+  HUseListNode<T>* Current() const {
+    DCHECK(!Done());
+    return current_;
+  }
+
+ private:
+  HUseListNode<T>* current_;
+
+  friend class HValue;
+};
+
 // Represents the side effects an instruction may have.
 class SideEffects : public ValueObject {
  public:
@@ -670,6 +748,57 @@ class SideEffects : public ValueObject {
   size_t flags_;
 };
 
+// A HEnvironment object contains the values of virtual registers at a given location.
+class HEnvironment : public ArenaObject<kArenaAllocMisc> {
+ public:
+  HEnvironment(ArenaAllocator* arena, size_t number_of_vregs)
+     : vregs_(arena, number_of_vregs) {
+    vregs_.SetSize(number_of_vregs);
+    for (size_t i = 0; i < number_of_vregs; i++) {
+      vregs_.Put(i, VRegInfo(nullptr, nullptr));
+    }
+  }
+
+  void CopyFrom(HEnvironment* env);
+
+  void SetRawEnvAt(size_t index, HInstruction* instruction) {
+    vregs_.Put(index, VRegInfo(instruction, nullptr));
+  }
+
+  // Record instructions' use entries of this environment for constant-time removal.
+  void RecordEnvUse(HUseListNode<HEnvironment*>* env_use) {
+    DCHECK(env_use->GetUser() == this);
+    size_t index = env_use->GetIndex();
+    VRegInfo info = vregs_.Get(index);
+    DCHECK(info.vreg_ != nullptr);
+    DCHECK(info.node_ == nullptr);
+    vregs_.Put(index, VRegInfo(info.vreg_, env_use));
+  }
+
+  HInstruction* GetInstructionAt(size_t index) const {
+    return vregs_.Get(index).vreg_;
+  }
+
+  HUseListNode<HEnvironment*>* GetInstructionEnvUseAt(size_t index) const {
+    return vregs_.Get(index).node_;
+  }
+
+  size_t Size() const { return vregs_.Size(); }
+
+ private:
+  struct VRegInfo {
+    HInstruction* vreg_;
+    HUseListNode<HEnvironment*>* node_;
+
+    VRegInfo(HInstruction* instruction, HUseListNode<HEnvironment*>* env_use)
+        : vreg_(instruction), node_(env_use) {}
+  };
+
+  GrowableArray<VRegInfo> vregs_;
+
+  DISALLOW_COPY_AND_ASSIGN(HEnvironment);
+};
+
 class HInstruction : public ArenaObject<kArenaAllocMisc> {
  public:
   explicit HInstruction(SideEffects side_effects)
@@ -678,8 +807,6 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> {
         block_(nullptr),
         id_(-1),
         ssa_index_(-1),
-        uses_(nullptr),
-        env_uses_(nullptr),
         environment_(nullptr),
         locations_(nullptr),
         live_interval_(nullptr),
@@ -723,30 +850,29 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> {
   virtual bool CanDoImplicitNullCheck() const { return false; }
 
   void AddUseAt(HInstruction* user, size_t index) {
-    uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HInstruction>(user, index, uses_);
+    uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena());
   }
 
   void AddEnvUseAt(HEnvironment* user, size_t index) {
     DCHECK(user != nullptr);
-    env_uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HEnvironment>(
-        user, index, env_uses_);
+    HUseListNode<HEnvironment*>* env_use =
+        env_uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena());
+    user->RecordEnvUse(env_use);
   }
 
   void RemoveUser(HInstruction* user, size_t index);
-  void RemoveEnvironmentUser(HEnvironment* user, size_t index);
+  void RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use);
 
-  HUseListNode<HInstruction>* GetUses() const { return uses_; }
-  HUseListNode<HEnvironment>* GetEnvUses() const { return env_uses_; }
+  HUseList<HInstruction*>& GetUses() { return uses_; }
+  HUseList<HEnvironment*>& GetEnvUses() { return env_uses_; }
 
-  bool HasUses() const { return uses_ != nullptr || env_uses_ != nullptr; }
-  bool HasEnvironmentUses() const { return env_uses_ != nullptr; }
+  bool HasUses() const { return !uses_.IsEmpty() || !env_uses_.IsEmpty(); }
+  bool HasEnvironmentUses() const { return !env_uses_.IsEmpty(); }
 
-  size_t NumberOfUses() const {
+  size_t ExpensiveComputeNumberOfUses() const {
     // TODO: Optimize this method if it is used outside of the HGraphVisualizer.
     size_t result = 0;
-    HUseListNode<HInstruction>* current = uses_;
-    while (current != nullptr) {
-      current = current->GetTail();
+    for (HUseIterator<HInstruction*> it(uses_); !it.Done(); it.Advance()) {
       ++result;
     }
     return result;
@@ -781,10 +907,6 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> {
   // Insert `this` instruction in `cursor`'s graph, just before `cursor`.
   void InsertBefore(HInstruction* cursor);
 
-  bool HasOnlyOneUse() const {
-    return uses_ != nullptr && uses_->GetTail() == nullptr;
-  }
-
 #define INSTRUCTION_TYPE_CHECK(type, super)                                    \
   bool Is##type() const { return (As##type() != nullptr); }                    \
   virtual const H##type* As##type() const { return nullptr; }                  \
@@ -847,10 +969,10 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> {
   int ssa_index_;
 
   // List of instructions that have this instruction as input.
-  HUseListNode<HInstruction>* uses_;
+  HUseList<HInstruction*> uses_;
 
   // List of environments that contain this instruction.
-  HUseListNode<HEnvironment>* env_uses_;
+  HUseList<HEnvironment*> env_uses_;
 
   // The environment associated with this instruction. Not null if the instruction
   // might jump out of the method.
@@ -876,69 +998,6 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> {
 };
 std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs);
 
-template<typename T>
-class HUseIterator : public ValueObject {
- public:
-  explicit HUseIterator(HUseListNode<T>* uses) : current_(uses) {}
-
-  bool Done() const { return current_ == nullptr; }
-
-  void Advance() {
-    DCHECK(!Done());
-    current_ = current_->GetTail();
-  }
-
-  HUseListNode<T>* Current() const {
-    DCHECK(!Done());
-    return current_;
-  }
-
- private:
-  HUseListNode<T>* current_;
-
-  friend class HValue;
-};
-
-// A HEnvironment object contains the values of virtual registers at a given location.
-class HEnvironment : public ArenaObject<kArenaAllocMisc> {
- public:
-  HEnvironment(ArenaAllocator* arena, size_t number_of_vregs) : vregs_(arena, number_of_vregs) {
-    vregs_.SetSize(number_of_vregs);
-    for (size_t i = 0; i < number_of_vregs; i++) {
-      vregs_.Put(i, nullptr);
-    }
-  }
-
-  void Populate(const GrowableArray<HInstruction*>& env) {
-    for (size_t i = 0; i < env.Size(); i++) {
-      HInstruction* instruction = env.Get(i);
-      vregs_.Put(i, instruction);
-      if (instruction != nullptr) {
-        instruction->AddEnvUseAt(this, i);
-      }
-    }
-  }
-
-  void SetRawEnvAt(size_t index, HInstruction* instruction) {
-    vregs_.Put(index, instruction);
-  }
-
-  HInstruction* GetInstructionAt(size_t index) const {
-    return vregs_.Get(index);
-  }
-
-  GrowableArray<HInstruction*>* GetVRegs() {
-    return &vregs_;
-  }
-
-  size_t Size() const { return vregs_.Size(); }
-
- private:
-  GrowableArray<HInstruction*> vregs_;
-
-  DISALLOW_COPY_AND_ASSIGN(HEnvironment);
-};
-
 class HInputIterator : public ValueObject {
  public:
   explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {}
diff --git a/compiler/optimizing/nodes_test.cc b/compiler/optimizing/nodes_test.cc
index 70dd8d7f88..cf90bf7e88 100644
--- a/compiler/optimizing/nodes_test.cc
+++ b/compiler/optimizing/nodes_test.cc
@@ -81,13 +81,13 @@ TEST(Node, InsertInstruction) {
   entry->AddInstruction(new (&allocator) HExit());
 
   ASSERT_FALSE(parameter1->HasUses());
-  ASSERT_EQ(parameter1->NumberOfUses(), 0u);
+  ASSERT_EQ(parameter1->ExpensiveComputeNumberOfUses(), 0u);
 
   HInstruction* to_insert = new (&allocator) HNullCheck(parameter1, 0);
   entry->InsertInstructionBefore(to_insert, parameter2);
 
   ASSERT_TRUE(parameter1->HasUses());
-  ASSERT_EQ(parameter1->NumberOfUses(), 1u);
+  ASSERT_EQ(parameter1->ExpensiveComputeNumberOfUses(), 1u);
 }
 
 /**
@@ -105,13 +105,13 @@ TEST(Node, AddInstruction) {
   entry->AddInstruction(parameter);
 
   ASSERT_FALSE(parameter->HasUses());
-  ASSERT_EQ(parameter->NumberOfUses(), 0u);
+  ASSERT_EQ(parameter->ExpensiveComputeNumberOfUses(), 0u);
 
   HInstruction* to_add = new (&allocator) HNullCheck(parameter, 0);
   entry->AddInstruction(to_add);
 
   ASSERT_TRUE(parameter->HasUses());
-  ASSERT_EQ(parameter->NumberOfUses(), 1u);
+  ASSERT_EQ(parameter->ExpensiveComputeNumberOfUses(), 1u);
 }
 
 }  // namespace art
diff --git a/compiler/optimizing/prepare_for_register_allocation.cc b/compiler/optimizing/prepare_for_register_allocation.cc
index 7186dbe85e..12acd0884a 100644
--- a/compiler/optimizing/prepare_for_register_allocation.cc
+++ b/compiler/optimizing/prepare_for_register_allocation.cc
@@ -55,11 +55,10 @@ void PrepareForRegisterAllocation::VisitClinitCheck(HClinitCheck* check) {
 
 void PrepareForRegisterAllocation::VisitCondition(HCondition* condition) {
   bool needs_materialization = false;
-  if (!condition->HasOnlyOneUse()) {
+  if (!condition->GetUses().HasOnlyOneUse()) {
     needs_materialization = true;
   } else {
-    HUseListNode<HInstruction>* uses = condition->GetUses();
-    HInstruction* user = uses->GetUser();
+    HInstruction* user = condition->GetUses().GetFirst()->GetUser();
     if (!user->IsIf()) {
       needs_materialization = true;
     } else {
diff --git a/compiler/optimizing/pretty_printer.h b/compiler/optimizing/pretty_printer.h
index 2c8166e65b..d2a21c8980 100644
--- a/compiler/optimizing/pretty_printer.h
+++ b/compiler/optimizing/pretty_printer.h
@@ -55,7 +55,7 @@ class HPrettyPrinter : public HGraphVisitor {
     if (instruction->HasUses()) {
       PrintString(" [");
       bool first = true;
-      for (HUseIterator<HInstruction> it(instruction->GetUses()); !it.Done(); it.Advance()) {
+      for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
         if (first) {
           first = false;
         } else {
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index edfafcdd83..4f9c3b87c1 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -68,7 +68,7 @@ void SsaBuilder::BuildSsa() {
 }
 
 HInstruction* SsaBuilder::ValueOfLocal(HBasicBlock* block, size_t local) {
-  return GetLocalsFor(block)->Get(local);
+  return GetLocalsFor(block)->GetInstructionAt(local);
 }
 
 void SsaBuilder::VisitBasicBlock(HBasicBlock* block) {
@@ -85,7 +85,7 @@ void SsaBuilder::VisitBasicBlock(HBasicBlock* block) {
         HPhi* phi = new (GetGraph()->GetArena()) HPhi(
             GetGraph()->GetArena(), local, 0, Primitive::kPrimVoid);
         block->AddPhi(phi);
-        current_locals_->Put(local, phi);
+        current_locals_->SetRawEnvAt(local, phi);
       }
     }
     // Save the loop header so that the last phase of the analysis knows which
@@ -125,7 +125,7 @@ void SsaBuilder::VisitBasicBlock(HBasicBlock* block) {
         block->AddPhi(phi);
         value = phi;
       }
-      current_locals_->Put(local, value);
+      current_locals_->SetRawEnvAt(local, value);
     }
   }
 
@@ -235,7 +235,7 @@ HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* user,
 }
 
 void SsaBuilder::VisitLoadLocal(HLoadLocal* load) {
-  HInstruction* value = current_locals_->Get(load->GetLocal()->GetRegNumber());
+  HInstruction* value = current_locals_->GetInstructionAt(load->GetLocal()->GetRegNumber());
   if (load->GetType() != value->GetType()
       && (load->GetType() == Primitive::kPrimFloat || load->GetType() == Primitive::kPrimDouble)) {
     // If the operation requests a specific type, we make sure its input is of that type.
@@ -246,7 +246,7 @@ void SsaBuilder::VisitLoadLocal(HLoadLocal* load) {
 }
 
 void SsaBuilder::VisitStoreLocal(HStoreLocal* store) {
-  current_locals_->Put(store->GetLocal()->GetRegNumber(), store->InputAt(1));
+  current_locals_->SetRawEnvAt(store->GetLocal()->GetRegNumber(), store->InputAt(1));
   store->GetBlock()->RemoveInstruction(store);
 }
 
@@ -256,7 +256,7 @@ void SsaBuilder::VisitInstruction(HInstruction* instruction) {
   }
   HEnvironment* environment = new (GetGraph()->GetArena()) HEnvironment(
       GetGraph()->GetArena(), current_locals_->Size());
-  environment->Populate(*current_locals_);
+  environment->CopyFrom(current_locals_);
   instruction->SetEnvironment(environment);
 }
 
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index 2cbd51aa10..2eec87b618 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -36,14 +36,14 @@ class SsaBuilder : public HGraphVisitor {
 
   void BuildSsa();
 
-  GrowableArray<HInstruction*>* GetLocalsFor(HBasicBlock* block) {
+  HEnvironment* GetLocalsFor(HBasicBlock* block) {
     HEnvironment* env = locals_for_.Get(block->GetBlockId());
     if (env == nullptr) {
       env = new (GetGraph()->GetArena()) HEnvironment(
           GetGraph()->GetArena(), GetGraph()->GetNumberOfVRegs());
       locals_for_.Put(block->GetBlockId(), env);
     }
-    return env->GetVRegs();
+    return env;
   }
 
   HInstruction* ValueOfLocal(HBasicBlock* block, size_t local);
@@ -60,7 +60,7 @@ class SsaBuilder : public HGraphVisitor {
 
  private:
   // Locals for the current block being visited.
-  GrowableArray<HInstruction*>* current_locals_;
+  HEnvironment* current_locals_;
 
   // Keep track of loop headers found. The last phase of the analysis iterates
   // over these blocks to set the inputs of their phis.
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index d41157b8d8..1b06315fce 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -232,9 +232,9 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
 
       if (current->HasEnvironment()) {
         // All instructions in the environment must be live.
-        GrowableArray<HInstruction*>* environment = current->GetEnvironment()->GetVRegs();
+        HEnvironment* environment = current->GetEnvironment();
         for (size_t i = 0, e = environment->Size(); i < e; ++i) {
-          HInstruction* instruction = environment->Get(i);
+          HInstruction* instruction = environment->GetInstructionAt(i);
           if (instruction != nullptr) {
             DCHECK(instruction->HasSsaIndex());
             live_in->SetBit(instruction->GetSsaIndex());
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 58cea771b9..fd30c1bc76 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -26,8 +26,8 @@ void SsaDeadPhiElimination::Run() {
       HPhi* phi = inst_it.Current()->AsPhi();
       // Set dead ahead of running through uses. The phi may have no use.
       phi->SetDead();
-      for (HUseIterator<HInstruction> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) {
-        HUseListNode<HInstruction>* current = use_it.Current();
+      for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) {
+        HUseListNode<HInstruction*>* current = use_it.Current();
         HInstruction* user = current->GetUser();
         if (!user->IsPhi()) {
           worklist_.Add(phi);
@@ -61,9 +61,9 @@ void SsaDeadPhiElimination::Run() {
       next = current->GetNext();
       if (current->AsPhi()->IsDead()) {
         if (current->HasUses()) {
-          for (HUseIterator<HInstruction> use_it(current->GetUses()); !use_it.Done();
+          for (HUseIterator<HInstruction*> use_it(current->GetUses()); !use_it.Done();
                use_it.Advance()) {
-            HUseListNode<HInstruction>* user_node = use_it.Current();
+            HUseListNode<HInstruction*>* user_node = use_it.Current();
             HInstruction* user = user_node->GetUser();
             DCHECK(user->IsLoopHeaderPhi()) << user->GetId();
             DCHECK(user->AsPhi()->IsDead()) << user->GetId();
@@ -73,12 +73,12 @@ void SsaDeadPhiElimination::Run() {
           }
         }
         if (current->HasEnvironmentUses()) {
-          for (HUseIterator<HEnvironment> use_it(current->GetEnvUses()); !use_it.Done();
+          for (HUseIterator<HEnvironment*> use_it(current->GetEnvUses()); !use_it.Done();
                use_it.Advance()) {
-            HUseListNode<HEnvironment>* user_node = use_it.Current();
+            HUseListNode<HEnvironment*>* user_node = use_it.Current();
             HEnvironment* user = user_node->GetUser();
             user->SetRawEnvAt(user_node->GetIndex(), nullptr);
-            current->RemoveEnvironmentUser(user, user_node->GetIndex());
+            current->RemoveEnvironmentUser(user_node);
           }
         }
         block->RemovePhi(current->AsPhi());
@@ -132,8 +132,8 @@ void SsaRedundantPhiElimination::Run() {
       // Because we're updating the users of this phi, we may have new
       // phis candidate for elimination if this phi is in a loop. Add phis that
       // used this phi to the worklist.
-      for (HUseIterator<HInstruction> it(phi->GetUses()); !it.Done(); it.Advance()) {
-        HUseListNode<HInstruction>* current = it.Current();
+      for (HUseIterator<HInstruction*> it(phi->GetUses()); !it.Done(); it.Advance()) {
+        HUseListNode<HInstruction*>* current = it.Current();
         HInstruction* user = current->GetUser();
         if (user->IsPhi()) {
           worklist_.Add(user->AsPhi());
diff --git a/compiler/optimizing/ssa_type_propagation.cc b/compiler/optimizing/ssa_type_propagation.cc
index cb5ce20c46..947427b67f 100644
--- a/compiler/optimizing/ssa_type_propagation.cc
+++ b/compiler/optimizing/ssa_type_propagation.cc
@@ -114,7 +114,7 @@ void SsaTypePropagation::AddToWorklist(HPhi* instruction) {
 }
 
 void SsaTypePropagation::AddDependentInstructionsToWorklist(HPhi* instruction) {
-  for (HUseIterator<HInstruction> it(instruction->GetUses()); !it.Done(); it.Advance()) {
+  for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
     HPhi* phi = it.Current()->GetUser()->AsPhi();
     if (phi != nullptr) {
       AddToWorklist(phi);