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 4d74c4e..35c5269 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 d7dcb4c..c606bd7 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 ff23eda..2097ea6 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 ec53366..fe9ce74 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 e19bfce..cac78f6 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 70dd8d7..cf90bf7 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 7186dbe..12acd08 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 2c8166e..d2a21c8 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 edfafcd..4f9c3b8 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 2cbd51a..2eec87b 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 d41157b..1b06315 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 58cea77..fd30c1b 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 cb5ce20..947427b 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);