diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index 17cb8f3..66c873e 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -400,7 +400,6 @@
   loop_body->AddSuccessor(loop_header);
 
   HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
-  phi->AddInput(constant_initial);
   HInstruction* null_check = new (allocator) HNullCheck(parameter, 0);
   HInstruction* array_length = new (allocator) HArrayLength(null_check);
   HInstruction* cmp = nullptr;
@@ -416,6 +415,7 @@
   loop_header->AddInstruction(array_length);
   loop_header->AddInstruction(cmp);
   loop_header->AddInstruction(if_inst);
+  phi->AddInput(constant_initial);
 
   null_check = new (allocator) HNullCheck(parameter, 0);
   array_length = new (allocator) HArrayLength(null_check);
@@ -544,7 +544,6 @@
   loop_body->AddSuccessor(loop_header);
 
   HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
-  phi->AddInput(array_length);
   HInstruction* cmp = nullptr;
   if (cond == kCondLE) {
     cmp = new (allocator) HLessThanOrEqual(phi, constant_initial);
@@ -556,6 +555,7 @@
   loop_header->AddPhi(phi);
   loop_header->AddInstruction(cmp);
   loop_header->AddInstruction(if_inst);
+  phi->AddInput(array_length);
 
   HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_minus_1);
   null_check = new (allocator) HNullCheck(parameter, 0);
@@ -672,7 +672,6 @@
   loop_body->AddSuccessor(loop_header);
 
   HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
-  phi->AddInput(constant_initial);
   HInstruction* cmp = nullptr;
   if (cond == kCondGE) {
     cmp = new (allocator) HGreaterThanOrEqual(phi, constant_10);
@@ -684,6 +683,7 @@
   loop_header->AddPhi(phi);
   loop_header->AddInstruction(cmp);
   loop_header->AddInstruction(if_inst);
+  phi->AddInput(constant_initial);
 
   HNullCheck* null_check = new (allocator) HNullCheck(new_array, 0);
   HArrayLength* array_length = new (allocator) HArrayLength(null_check);
@@ -785,7 +785,6 @@
   loop_body->AddSuccessor(loop_header);
 
   HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
-  phi->AddInput(constant_initial);
   HInstruction* null_check = new (allocator) HNullCheck(parameter, 0);
   HInstruction* array_length = new (allocator) HArrayLength(null_check);
   HInstruction* cmp = nullptr;
@@ -800,6 +799,7 @@
   loop_header->AddInstruction(array_length);
   loop_header->AddInstruction(cmp);
   loop_header->AddInstruction(if_inst);
+  phi->AddInput(constant_initial);
 
   null_check = new (allocator) HNullCheck(parameter, 0);
   array_length = new (allocator) HArrayLength(null_check);
@@ -904,7 +904,6 @@
   HBasicBlock* outer_header = new (&allocator) HBasicBlock(graph);
   graph->AddBlock(outer_header);
   HPhi* phi_i = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt);
-  phi_i->AddInput(constant_0);
   HNullCheck* null_check = new (&allocator) HNullCheck(parameter, 0);
   HArrayLength* array_length = new (&allocator) HArrayLength(null_check);
   HAdd* add = new (&allocator) HAdd(Primitive::kPrimInt, array_length, constant_minus_1);
@@ -916,11 +915,11 @@
   outer_header->AddInstruction(add);
   outer_header->AddInstruction(cmp);
   outer_header->AddInstruction(if_inst);
+  phi_i->AddInput(constant_0);
 
   HBasicBlock* inner_header = new (&allocator) HBasicBlock(graph);
   graph->AddBlock(inner_header);
   HPhi* phi_j = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt);
-  phi_j->AddInput(constant_0);
   null_check = new (&allocator) HNullCheck(parameter, 0);
   array_length = new (&allocator) HArrayLength(null_check);
   HSub* sub = new (&allocator) HSub(Primitive::kPrimInt, array_length, phi_i);
@@ -934,6 +933,7 @@
   inner_header->AddInstruction(add);
   inner_header->AddInstruction(cmp);
   inner_header->AddInstruction(if_inst);
+  phi_j->AddInput(constant_0);
 
   HBasicBlock* inner_body_compare = new (&allocator) HBasicBlock(graph);
   graph->AddBlock(inner_body_compare);
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index ef10428..a7f1f74 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -160,6 +160,22 @@
                             instruction->GetId()));
     }
   }
+
+  // Ensure 'instruction' has pointers to its inputs' use entries.
+  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
+    HUserRecord<HInstruction*> input_record = instruction->InputRecordAt(i);
+    HInstruction* input = input_record.GetInstruction();
+    HUseListNode<HInstruction*>* use_node = input_record.GetUseNode();
+    if (use_node == nullptr || !input->GetUses().Contains(use_node)) {
+      AddError(StringPrintf("Instruction %s:%d has an invalid pointer to use entry "
+                            "at input %u (%s:%d).",
+                            instruction->DebugName(),
+                            instruction->GetId(),
+                            static_cast<unsigned>(i),
+                            input->DebugName(),
+                            input->GetId()));
+    }
+  }
 }
 
 void SSAChecker::VisitBasicBlock(HBasicBlock* block) {
diff --git a/compiler/optimizing/licm.cc b/compiler/optimizing/licm.cc
index 10f24d8..bf9b8e5 100644
--- a/compiler/optimizing/licm.cc
+++ b/compiler/optimizing/licm.cc
@@ -66,8 +66,7 @@
   for (size_t i = 0, e = environment->Size(); i < e; ++i) {
     HInstruction* input = environment->GetInstructionAt(i);
     if (input != nullptr && IsPhiOf(input, info->GetHeader())) {
-      HUseListNode<HEnvironment*>* env_use = environment->GetInstructionEnvUseAt(i);
-      input->RemoveEnvironmentUser(env_use);
+      environment->RemoveAsUserOfInput(i);
       HInstruction* incoming = input->InputAt(0);
       environment->SetRawEnvAt(i, incoming);
       incoming->AddEnvUseAt(environment, i);
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 7a75d26..93787b8 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -34,17 +34,14 @@
 
 static void RemoveAsUser(HInstruction* instruction) {
   for (size_t i = 0; i < instruction->InputCount(); i++) {
-    instruction->InputAt(i)->RemoveUser(instruction, i);
+    instruction->RemoveAsUserOfInput(i);
   }
 
   HEnvironment* environment = instruction->GetEnvironment();
   if (environment != nullptr) {
     for (size_t i = 0, e = environment->Size(); i < e; ++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);
+      if (environment->GetInstructionAt(i) != nullptr) {
+        environment->RemoveAsUserOfInput(i);
       }
     }
   }
@@ -64,22 +61,19 @@
   }
 }
 
-void HGraph::RemoveBlock(HBasicBlock* block) const {
-  for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
-    block->GetSuccessors().Get(j)->RemovePredecessor(block);
-  }
-  for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
-    block->RemovePhi(it.Current()->AsPhi());
-  }
-  for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
-    block->RemoveInstruction(it.Current());
-  }
-}
-
 void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const {
   for (size_t i = 0; i < blocks_.Size(); ++i) {
     if (!visited.IsBitSet(i)) {
-      RemoveBlock(blocks_.Get(i));
+      HBasicBlock* block = blocks_.Get(i);
+      for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
+        block->GetSuccessors().Get(j)->RemovePredecessor(block);
+      }
+      for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
+        block->RemovePhi(it.Current()->AsPhi(), /*ensure_safety=*/ false);
+      }
+      for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+        block->RemoveInstruction(it.Current(), /*ensure_safety=*/ false);
+      }
     }
   }
 }
@@ -439,22 +433,24 @@
 
 static void Remove(HInstructionList* instruction_list,
                    HBasicBlock* block,
-                   HInstruction* instruction) {
+                   HInstruction* instruction,
+                   bool ensure_safety) {
   DCHECK_EQ(block, instruction->GetBlock());
-  DCHECK(instruction->GetUses().IsEmpty());
-  DCHECK(instruction->GetEnvUses().IsEmpty());
   instruction->SetBlock(nullptr);
   instruction_list->RemoveInstruction(instruction);
-
-  RemoveAsUser(instruction);
+  if (ensure_safety) {
+    DCHECK(instruction->GetUses().IsEmpty());
+    DCHECK(instruction->GetEnvUses().IsEmpty());
+    RemoveAsUser(instruction);
+  }
 }
 
-void HBasicBlock::RemoveInstruction(HInstruction* instruction) {
-  Remove(&instructions_, this, instruction);
+void HBasicBlock::RemoveInstruction(HInstruction* instruction, bool ensure_safety) {
+  Remove(&instructions_, this, instruction, ensure_safety);
 }
 
-void HBasicBlock::RemovePhi(HPhi* phi) {
-  Remove(&phis_, this, phi);
+void HBasicBlock::RemovePhi(HPhi* phi, bool ensure_safety) {
+  Remove(&phis_, this, phi, ensure_safety);
 }
 
 void HEnvironment::CopyFrom(HEnvironment* env) {
@@ -467,15 +463,9 @@
   }
 }
 
-template <typename T>
-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) {
-      list->Remove(current);
-    }
-  }
+void HEnvironment::RemoveAsUserOfInput(size_t index) const {
+  const HUserRecord<HEnvironment*> user_record = vregs_.Get(index);
+  user_record.GetInstruction()->RemoveEnvironmentUser(user_record.GetUseNode());
 }
 
 HInstruction* HInstruction::GetNextDisregardingMoves() const {
@@ -494,14 +484,6 @@
   return previous;
 }
 
-void HInstruction::RemoveUser(HInstruction* user, size_t input_index) {
-  RemoveFromUseList(user, input_index, &uses_);
-}
-
-void HInstruction::RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use) {
-  env_uses_.Remove(use);
-}
-
 void HInstructionList::AddInstruction(HInstruction* instruction) {
   if (first_instruction_ == nullptr) {
     DCHECK(last_instruction_ == nullptr);
@@ -612,7 +594,7 @@
 }
 
 void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) {
-  InputAt(index)->RemoveUser(this, index);
+  RemoveAsUserOfInput(index);
   SetRawInputAt(index, replacement);
   replacement->AddUseAt(this, index);
 }
@@ -623,7 +605,7 @@
 
 void HPhi::AddInput(HInstruction* input) {
   DCHECK(input->GetBlock() != nullptr);
-  inputs_.Add(input);
+  inputs_.Add(HUserRecord<HInstruction*>(input));
   input->AddUseAt(this, inputs_.Size() - 1);
 }
 
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 352403d..de448cc 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -31,6 +31,7 @@
 
 namespace art {
 
+class GraphChecker;
 class HBasicBlock;
 class HEnvironment;
 class HInstruction;
@@ -211,7 +212,6 @@
                               ArenaBitVector* visiting);
   void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const;
   void RemoveDeadBlocks(const ArenaBitVector& visited) const;
-  void RemoveBlock(HBasicBlock* block) const;
 
   ArenaAllocator* const arena_;
 
@@ -490,14 +490,17 @@
   void ReplaceWith(HBasicBlock* other);
 
   void AddInstruction(HInstruction* instruction);
-  void RemoveInstruction(HInstruction* instruction);
   void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor);
   // Replace instruction `initial` with `replacement` within this block.
   void ReplaceAndRemoveInstructionWith(HInstruction* initial,
                                        HInstruction* replacement);
   void AddPhi(HPhi* phi);
   void InsertPhiAfter(HPhi* instruction, HPhi* cursor);
-  void RemovePhi(HPhi* phi);
+  // RemoveInstruction and RemovePhi delete a given instruction from the respective
+  // instruction list. With 'ensure_safety' set to true, it verifies that the
+  // instruction is not in use and removes it from the use lists of its inputs.
+  void RemoveInstruction(HInstruction* instruction, bool ensure_safety = true);
+  void RemovePhi(HPhi* phi, bool ensure_safety = true);
 
   bool IsLoopHeader() const {
     return (loop_information_ != nullptr) && (loop_information_->GetHeader() == this);
@@ -715,6 +718,9 @@
   }
 
   void Remove(HUseListNode<T>* node) {
+    DCHECK(node != nullptr);
+    DCHECK(Contains(node));
+
     if (node->prev_ != nullptr) {
       node->prev_->next_ = node->next_;
     }
@@ -726,6 +732,18 @@
     }
   }
 
+  bool Contains(const HUseListNode<T>* node) const {
+    if (node == nullptr) {
+      return false;
+    }
+    for (HUseListNode<T>* current = first_; current != nullptr; current = current->GetNext()) {
+      if (current == node) {
+        return true;
+      }
+    }
+    return false;
+  }
+
   bool IsEmpty() const {
     return first_ == nullptr;
   }
@@ -761,6 +779,33 @@
   friend class HValue;
 };
 
+// This class is used by HEnvironment and HInstruction classes to record the
+// instructions they use and pointers to the corresponding HUseListNodes kept
+// by the used instructions.
+template <typename T>
+class HUserRecord : public ValueObject {
+ public:
+  HUserRecord() : instruction_(nullptr), use_node_(nullptr) {}
+  explicit HUserRecord(HInstruction* instruction) : instruction_(instruction), use_node_(nullptr) {}
+
+  HUserRecord(const HUserRecord<T>& old_record, HUseListNode<T>* use_node)
+    : instruction_(old_record.instruction_), use_node_(use_node) {
+    DCHECK(instruction_ != nullptr);
+    DCHECK(use_node_ != nullptr);
+    DCHECK(old_record.use_node_ == nullptr);
+  }
+
+  HInstruction* GetInstruction() const { return instruction_; }
+  HUseListNode<T>* GetUseNode() const { return use_node_; }
+
+ private:
+  // Instruction used by the user.
+  HInstruction* instruction_;
+
+  // Corresponding entry in the use list kept by 'instruction_'.
+  HUseListNode<T>* use_node_;
+};
+
 // Represents the side effects an instruction may have.
 class SideEffects : public ValueObject {
  public:
@@ -831,46 +876,36 @@
      : 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));
+      vregs_.Put(i, HUserRecord<HEnvironment*>());
     }
   }
 
   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));
+    vregs_.Put(index, HUserRecord<HEnvironment*>(instruction));
   }
 
   HInstruction* GetInstructionAt(size_t index) const {
-    return vregs_.Get(index).vreg_;
+    return vregs_.Get(index).GetInstruction();
   }
 
-  HUseListNode<HEnvironment*>* GetInstructionEnvUseAt(size_t index) const {
-    return vregs_.Get(index).node_;
-  }
+  void RemoveAsUserOfInput(size_t index) const;
 
   size_t Size() const { return vregs_.Size(); }
 
  private:
-  struct VRegInfo {
-    HInstruction* vreg_;
-    HUseListNode<HEnvironment*>* node_;
+  // Record instructions' use entries of this environment for constant-time removal.
+  // It should only be called by HInstruction when a new environment use is added.
+  void RecordEnvUse(HUseListNode<HEnvironment*>* env_use) {
+    DCHECK(env_use->GetUser() == this);
+    size_t index = env_use->GetIndex();
+    vregs_.Put(index, HUserRecord<HEnvironment*>(vregs_.Get(index), env_use));
+  }
 
-    VRegInfo(HInstruction* instruction, HUseListNode<HEnvironment*>* env_use)
-        : vreg_(instruction), node_(env_use) {}
-  };
+  GrowableArray<HUserRecord<HEnvironment*> > vregs_;
 
-  GrowableArray<VRegInfo> vregs_;
+  friend HInstruction;
 
   DISALLOW_COPY_AND_ASSIGN(HEnvironment);
 };
@@ -989,13 +1024,15 @@
   bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); }
 
   virtual size_t InputCount() const = 0;
-  virtual HInstruction* InputAt(size_t i) const = 0;
+  HInstruction* InputAt(size_t i) const { return InputRecordAt(i).GetInstruction(); }
 
   virtual void Accept(HGraphVisitor* visitor) = 0;
   virtual const char* DebugName() const = 0;
 
   virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; }
-  virtual void SetRawInputAt(size_t index, HInstruction* input) = 0;
+  void SetRawInputAt(size_t index, HInstruction* input) {
+    SetRawInputRecordAt(index, HUserRecord<HInstruction*>(input));
+  }
 
   virtual bool NeedsEnvironment() const { return false; }
   virtual bool IsControlFlow() const { return false; }
@@ -1018,7 +1055,10 @@
   ReferenceTypeInfo GetReferenceTypeInfo() const { return reference_type_info_; }
 
   void AddUseAt(HInstruction* user, size_t index) {
-    uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena());
+    DCHECK(user != nullptr);
+    HUseListNode<HInstruction*>* use =
+        uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena());
+    user->SetRawInputRecordAt(index, HUserRecord<HInstruction*>(user->InputRecordAt(index), use));
   }
 
   void AddEnvUseAt(HEnvironment* user, size_t index) {
@@ -1028,11 +1068,13 @@
     user->RecordEnvUse(env_use);
   }
 
-  void RemoveUser(HInstruction* user, size_t index);
-  void RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use);
+  void RemoveAsUserOfInput(size_t input) {
+    HUserRecord<HInstruction*> input_use = InputRecordAt(input);
+    input_use.GetInstruction()->uses_.Remove(input_use.GetUseNode());
+  }
 
-  const HUseList<HInstruction*>& GetUses() { return uses_; }
-  const HUseList<HEnvironment*>& GetEnvUses() { return env_uses_; }
+  const HUseList<HInstruction*>& GetUses() const { return uses_; }
+  const HUseList<HEnvironment*>& GetEnvUses() const { return env_uses_; }
 
   bool HasUses() const { return !uses_.IsEmpty() || !env_uses_.IsEmpty(); }
   bool HasEnvironmentUses() const { return !env_uses_.IsEmpty(); }
@@ -1126,7 +1168,13 @@
     return NeedsEnvironment() || IsLoadClass() || IsLoadString();
   }
 
+ protected:
+  virtual const HUserRecord<HInstruction*> InputRecordAt(size_t i) const = 0;
+  virtual void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) = 0;
+
  private:
+  void RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use_node) { env_uses_.Remove(use_node); }
+
   HInstruction* previous_;
   HInstruction* next_;
   HBasicBlock* block_;
@@ -1164,7 +1212,9 @@
   // TODO: for primitive types this should be marked as invalid.
   ReferenceTypeInfo reference_type_info_;
 
+  friend class GraphChecker;
   friend class HBasicBlock;
+  friend class HEnvironment;
   friend class HGraph;
   friend class HInstructionList;
 
@@ -1284,15 +1334,16 @@
   virtual ~HTemplateInstruction() {}
 
   virtual size_t InputCount() const { return N; }
-  virtual HInstruction* InputAt(size_t i) const { return inputs_[i]; }
 
  protected:
-  virtual void SetRawInputAt(size_t i, HInstruction* instruction) {
-    inputs_[i] = instruction;
+  const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_[i]; }
+
+  void SetRawInputRecordAt(size_t i, const HUserRecord<HInstruction*>& input) OVERRIDE {
+    inputs_[i] = input;
   }
 
  private:
-  EmbeddedArray<HInstruction*, N> inputs_;
+  EmbeddedArray<HUserRecord<HInstruction*>, N> inputs_;
 
   friend class SsaBuilder;
 };
@@ -1848,7 +1899,6 @@
 class HInvoke : public HInstruction {
  public:
   virtual size_t InputCount() const { return inputs_.Size(); }
-  virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); }
 
   // Runtime needs to walk the stack, so Dex -> Dex calls need to
   // know their environment.
@@ -1858,10 +1908,6 @@
     SetRawInputAt(index, argument);
   }
 
-  virtual void SetRawInputAt(size_t index, HInstruction* input) {
-    inputs_.Put(index, input);
-  }
-
   virtual Primitive::Type GetType() const { return return_type_; }
 
   uint32_t GetDexPc() const { return dex_pc_; }
@@ -1893,7 +1939,12 @@
     inputs_.SetSize(number_of_arguments);
   }
 
-  GrowableArray<HInstruction*> inputs_;
+  const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); }
+  void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE {
+    inputs_.Put(index, input);
+  }
+
+  GrowableArray<HUserRecord<HInstruction*> > inputs_;
   const Primitive::Type return_type_;
   const uint32_t dex_pc_;
   const uint32_t dex_method_index_;
@@ -2389,11 +2440,6 @@
   }
 
   size_t InputCount() const OVERRIDE { return inputs_.Size(); }
-  HInstruction* InputAt(size_t i) const OVERRIDE { return inputs_.Get(i); }
-
-  void SetRawInputAt(size_t index, HInstruction* input) OVERRIDE {
-    inputs_.Put(index, input);
-  }
 
   void AddInput(HInstruction* input);
 
@@ -2412,8 +2458,15 @@
 
   DECLARE_INSTRUCTION(Phi);
 
+ protected:
+  const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); }
+
+  void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE {
+    inputs_.Put(index, input);
+  }
+
  private:
-  GrowableArray<HInstruction*> inputs_;
+  GrowableArray<HUserRecord<HInstruction*> > inputs_;
   const uint32_t reg_number_;
   Primitive::Type type_;
   bool is_live_;
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index f66a1c8..2f2e2d1 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -64,31 +64,33 @@
     HBasicBlock* block = it.Current();
     HInstruction* current = block->GetFirstPhi();
     HInstruction* next = nullptr;
+    HPhi* phi;
     while (current != nullptr) {
+      phi = current->AsPhi();
       next = current->GetNext();
-      if (current->AsPhi()->IsDead()) {
-        if (current->HasUses()) {
-          for (HUseIterator<HInstruction*> use_it(current->GetUses()); !use_it.Done();
+      if (phi->IsDead()) {
+        // Make sure the phi is only used by other dead phis.
+        if (kIsDebugBuild) {
+          for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done();
                use_it.Advance()) {
-            HUseListNode<HInstruction*>* user_node = use_it.Current();
-            HInstruction* user = user_node->GetUser();
+            HInstruction* user = use_it.Current()->GetUser();
             DCHECK(user->IsLoopHeaderPhi()) << user->GetId();
             DCHECK(user->AsPhi()->IsDead()) << user->GetId();
-            // Just put itself as an input. The phi will be removed in this loop anyway.
-            user->SetRawInputAt(user_node->GetIndex(), user);
-            current->RemoveUser(user, user_node->GetIndex());
           }
         }
-        if (current->HasEnvironmentUses()) {
-          for (HUseIterator<HEnvironment*> use_it(current->GetEnvUses()); !use_it.Done();
-               use_it.Advance()) {
-            HUseListNode<HEnvironment*>* user_node = use_it.Current();
-            HEnvironment* user = user_node->GetUser();
-            user->SetRawEnvAt(user_node->GetIndex(), nullptr);
-            current->RemoveEnvironmentUser(user_node);
-          }
+        // Remove the phi from use lists of its inputs.
+        for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
+          phi->RemoveAsUserOfInput(i);
         }
-        block->RemovePhi(current->AsPhi());
+        // Remove the phi from environments that use it.
+        for (HUseIterator<HEnvironment*> use_it(phi->GetEnvUses()); !use_it.Done();
+             use_it.Advance()) {
+          HUseListNode<HEnvironment*>* user_node = use_it.Current();
+          HEnvironment* user = user_node->GetUser();
+          user->SetRawEnvAt(user_node->GetIndex(), nullptr);
+        }
+        // Delete it from the instruction list.
+        block->RemovePhi(phi, /*ensure_safety=*/ false);
       }
       current = next;
     }