Use iterators "before" the use node in HUserRecord<>.

Create a new template class IntrusiveForwardList<> that
mimicks std::forward_list<> except that all allocations
are handled externally. This is essentially the same as
boost::intrusive::slist<> but since we're not using Boost
we have to reinvent the wheel.

Use the new container to replace the HUseList and use the
iterators to "before" use nodes in HUserRecord<> to avoid
the extra pointer to the previous node which was used
exclusively for removing nodes from the list. This reduces
the size of the HUseListNode by 25%, 32B to 24B in 64-bit
compiler, 16B to 12B in 32-bit compiler. This translates
directly to overall memory savings for the 64-bit compiler
but due to rounding up of the arena allocations to 8B, we
do not get any improvement in the 32-bit compiler.

Compiling the Nexus 5 boot image with the 64-bit dex2oat
on host this CL reduces the memory used for compiling the
most hungry method, BatteryStats.dumpLocked(), by ~3.3MiB:

Before:
  MEM: used: 47829200, allocated: 48769120, lost: 939920
  Number of arenas allocated: 345,
  Number of allocations: 815492, avg size: 58
  ...
  UseListNode    13744640
  ...
After:
  MEM: used: 44393040, allocated: 45361248, lost: 968208
  Number of arenas allocated: 319,
  Number of allocations: 815492, avg size: 54
  ...
  UseListNode    10308480
  ...

Note that while we do not ship the 64-bit dex2oat to the
device, the JIT compilation for 64-bit processes is using
the 64-bit libart-compiler.

Bug: 28173563
Change-Id: I985eabd4816f845372d8aaa825a1489cf9569208

18 files changed, 245 insertions, 309 deletions

diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 084360f22b..659c6f8497 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -1206,9 +1206,9 @@ class BCEVisitor : public HGraphVisitor {
           GetGraph()->GetArena()->Adapter(kArenaAllocBoundsCheckElimination));
       ArenaVector<HBoundsCheck*> standby(
           GetGraph()->GetArena()->Adapter(kArenaAllocBoundsCheckElimination));
-      for (HUseIterator<HInstruction*> it2(array_length->GetUses()); !it2.Done(); it2.Advance()) {
+      for (const HUseListNode<HInstruction*>& use : array_length->GetUses()) {
         // Another bounds check in same or dominated block?
-        HInstruction* user = it2.Current()->GetUser();
+        HInstruction* user = use.GetUser();
         HBasicBlock* other_block = user->GetBlock();
         if (user->IsBoundsCheck() && block->Dominates(other_block)) {
           HBoundsCheck* other_bounds_check = user->AsBoundsCheck();
@@ -1635,29 +1635,33 @@ class BCEVisitor : public HGraphVisitor {
         Primitive::Type type = instruction->GetType();
         HPhi* phi = nullptr;
         // Scan all uses of an instruction and replace each later use with a phi node.
-        for (HUseIterator<HInstruction*> it2(instruction->GetUses());
-             !it2.Done();
-             it2.Advance()) {
-          HInstruction* user = it2.Current()->GetUser();
+        const HUseList<HInstruction*>& uses = instruction->GetUses();
+        for (auto it2 = uses.begin(), end2 = uses.end(); it2 != end2; /* ++it2 below */) {
+          HInstruction* user = it2->GetUser();
+          size_t index = it2->GetIndex();
+          // Increment `it2` now because `*it2` may disappear thanks to user->ReplaceInput().
+          ++it2;
           if (user->GetBlock() != true_block) {
             if (phi == nullptr) {
               phi = NewPhi(new_preheader, instruction, type);
             }
-            user->ReplaceInput(phi, it2.Current()->GetIndex());
+            user->ReplaceInput(phi, index);  // Removes the use node from the list.
           }
         }
         // Scan all environment uses of an instruction and replace each later use with a phi node.
-        for (HUseIterator<HEnvironment*> it2(instruction->GetEnvUses());
-             !it2.Done();
-             it2.Advance()) {
-          HEnvironment* user = it2.Current()->GetUser();
+        const HUseList<HEnvironment*>& env_uses = instruction->GetEnvUses();
+        for (auto it2 = env_uses.begin(), end2 = env_uses.end(); it2 != end2; /* ++it2 below */) {
+          HEnvironment* user = it2->GetUser();
+          size_t index = it2->GetIndex();
+          // Increment `it2` now because `*it2` may disappear thanks to user->RemoveAsUserOfInput().
+          ++it2;
           if (user->GetHolder()->GetBlock() != true_block) {
             if (phi == nullptr) {
               phi = NewPhi(new_preheader, instruction, type);
             }
-            user->RemoveAsUserOfInput(it2.Current()->GetIndex());
-            user->SetRawEnvAt(it2.Current()->GetIndex(), phi);
-            phi->AddEnvUseAt(user, it2.Current()->GetIndex());
+            user->RemoveAsUserOfInput(index);
+            user->SetRawEnvAt(index, phi);
+            phi->AddEnvUseAt(user, index);
           }
         }
       }
diff --git a/compiler/optimizing/common_arm64.h b/compiler/optimizing/common_arm64.h
index 6412b24362..a849448cf9 100644
--- a/compiler/optimizing/common_arm64.h
+++ b/compiler/optimizing/common_arm64.h
@@ -199,7 +199,7 @@ static bool CanEncodeConstantAsImmediate(HConstant* constant, HInstruction* inst
 
   // For single uses we let VIXL handle the constant generation since it will
   // use registers that are not managed by the register allocator (wip0, wip1).
-  if (constant->GetUses().HasOnlyOneUse()) {
+  if (constant->GetUses().HasExactlyOneElement()) {
     return true;
   }
 
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 9ea4b2dab4..96837a8266 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -342,36 +342,34 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) {
 
   // Ensure the uses of `instruction` are defined in a block of the graph,
   // and the entry in the use list is consistent.
-  for (HUseIterator<HInstruction*> use_it(instruction->GetUses());
-       !use_it.Done(); use_it.Advance()) {
-    HInstruction* use = use_it.Current()->GetUser();
-    const HInstructionList& list = use->IsPhi()
-        ? use->GetBlock()->GetPhis()
-        : use->GetBlock()->GetInstructions();
-    if (!list.Contains(use)) {
+  for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
+    HInstruction* user = use.GetUser();
+    const HInstructionList& list = user->IsPhi()
+        ? user->GetBlock()->GetPhis()
+        : user->GetBlock()->GetInstructions();
+    if (!list.Contains(user)) {
       AddError(StringPrintf("User %s:%d of instruction %d is not defined "
                             "in a basic block of the control-flow graph.",
-                            use->DebugName(),
-                            use->GetId(),
+                            user->DebugName(),
+                            user->GetId(),
                             instruction->GetId()));
     }
-    size_t use_index = use_it.Current()->GetIndex();
-    if ((use_index >= use->InputCount()) || (use->InputAt(use_index) != instruction)) {
+    size_t use_index = use.GetIndex();
+    if ((use_index >= user->InputCount()) || (user->InputAt(use_index) != instruction)) {
       AddError(StringPrintf("User %s:%d of instruction %s:%d has a wrong "
                             "UseListNode index.",
-                            use->DebugName(),
-                            use->GetId(),
+                            user->DebugName(),
+                            user->GetId(),
                             instruction->DebugName(),
                             instruction->GetId()));
     }
   }
 
   // Ensure the environment uses entries are consistent.
-  for (HUseIterator<HEnvironment*> use_it(instruction->GetEnvUses());
-       !use_it.Done(); use_it.Advance()) {
-    HEnvironment* use = use_it.Current()->GetUser();
-    size_t use_index = use_it.Current()->GetIndex();
-    if ((use_index >= use->Size()) || (use->GetInstructionAt(use_index) != instruction)) {
+  for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
+    HEnvironment* user = use.GetUser();
+    size_t use_index = use.GetIndex();
+    if ((use_index >= user->Size()) || (user->GetInstructionAt(use_index) != instruction)) {
       AddError(StringPrintf("Environment user of %s:%d has a wrong "
                             "UseListNode index.",
                             instruction->DebugName(),
@@ -383,13 +381,11 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) {
   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();
-    size_t use_index = use_node->GetIndex();
-    if ((use_node == nullptr)
-        || !input->GetUses().Contains(use_node)
-        || (use_index >= e)
-        || (use_index != i)) {
-      AddError(StringPrintf("Instruction %s:%d has an invalid pointer to use entry "
+    if ((input_record.GetBeforeUseNode() == input->GetUses().end()) ||
+        (input_record.GetUseNode() == input->GetUses().end()) ||
+        !input->GetUses().ContainsNode(*input_record.GetUseNode()) ||
+        (input_record.GetUseNode()->GetIndex() != i)) {
+      AddError(StringPrintf("Instruction %s:%d has an invalid iterator before use entry "
                             "at input %u (%s:%d).",
                             instruction->DebugName(),
                             instruction->GetId(),
@@ -400,18 +396,17 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) {
   }
 
   // Ensure an instruction dominates all its uses.
-  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)) {
+  for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
+    HInstruction* user = use.GetUser();
+    if (!user->IsPhi() && !instruction->StrictlyDominates(user)) {
       AddError(StringPrintf("Instruction %s:%d in block %d does not dominate "
                             "use %s:%d in block %d.",
                             instruction->DebugName(),
                             instruction->GetId(),
                             current_block_->GetBlockId(),
-                            use->DebugName(),
-                            use->GetId(),
-                            use->GetBlock()->GetBlockId()));
+                            user->DebugName(),
+                            user->GetId(),
+                            user->GetBlock()->GetBlockId()));
     }
   }
 
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index fe47f7db7d..9efc13f61b 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -608,12 +608,7 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor {
     for (HInstructionIterator it(list); !it.Done(); it.Advance()) {
       HInstruction* instruction = it.Current();
       int bci = 0;
-      size_t num_uses = 0;
-      for (HUseIterator<HInstruction*> use_it(instruction->GetUses());
-           !use_it.Done();
-           use_it.Advance()) {
-        ++num_uses;
-      }
+      size_t num_uses = instruction->GetUses().SizeSlow();
       AddIndent();
       output_ << bci << " " << num_uses << " "
               << GetTypeId(instruction->GetType()) << instruction->GetId() << " ";
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 1f66db7909..d7b3856bf4 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -409,9 +409,9 @@ bool InstructionSimplifierVisitor::CanEnsureNotNullAt(HInstruction* input, HInst
     return true;
   }
 
-  for (HUseIterator<HInstruction*> it(input->GetUses()); !it.Done(); it.Advance()) {
-    HInstruction* use = it.Current()->GetUser();
-    if (use->IsNullCheck() && use->StrictlyDominates(at)) {
+  for (const HUseListNode<HInstruction*>& use : input->GetUses()) {
+    HInstruction* user = use.GetUser();
+    if (user->IsNullCheck() && user->StrictlyDominates(at)) {
       return true;
     }
   }
@@ -1070,12 +1070,12 @@ void InstructionSimplifierVisitor::VisitCondition(HCondition* condition) {
   }
 
   // Is the Compare only used for this purpose?
-  if (!left->GetUses().HasOnlyOneUse()) {
+  if (!left->GetUses().HasExactlyOneElement()) {
     // Someone else also wants the result of the compare.
     return;
   }
 
-  if (!left->GetEnvUses().IsEmpty()) {
+  if (!left->GetEnvUses().empty()) {
     // There is a reference to the compare result in an environment. Do we really need it?
     if (GetGraph()->IsDebuggable()) {
       return;
diff --git a/compiler/optimizing/instruction_simplifier_arm64.cc b/compiler/optimizing/instruction_simplifier_arm64.cc
index f00d960877..e4a711ec83 100644
--- a/compiler/optimizing/instruction_simplifier_arm64.cc
+++ b/compiler/optimizing/instruction_simplifier_arm64.cc
@@ -140,7 +140,7 @@ bool InstructionSimplifierArm64Visitor::TryMergeIntoShifterOperand(HInstruction*
                                                                  shift_amount,
                                                                  use->GetDexPc());
     use->GetBlock()->ReplaceAndRemoveInstructionWith(use, alu_with_op);
-    if (bitfield_op->GetUses().IsEmpty()) {
+    if (bitfield_op->GetUses().empty()) {
       bitfield_op->GetBlock()->RemoveInstruction(bitfield_op);
     }
     RecordSimplification();
@@ -160,20 +160,22 @@ bool InstructionSimplifierArm64Visitor::TryMergeIntoUsersShifterOperand(HInstruc
   const HUseList<HInstruction*>& uses = bitfield_op->GetUses();
 
   // Check whether we can merge the instruction in all its users' shifter operand.
-  for (HUseIterator<HInstruction*> it_use(uses); !it_use.Done(); it_use.Advance()) {
-    HInstruction* use = it_use.Current()->GetUser();
-    if (!HasShifterOperand(use)) {
+  for (const HUseListNode<HInstruction*>& use : uses) {
+    HInstruction* user = use.GetUser();
+    if (!HasShifterOperand(user)) {
       return false;
     }
-    if (!CanMergeIntoShifterOperand(use, bitfield_op)) {
+    if (!CanMergeIntoShifterOperand(user, bitfield_op)) {
       return false;
     }
   }
 
   // Merge the instruction into its uses.
-  for (HUseIterator<HInstruction*> it_use(uses); !it_use.Done(); it_use.Advance()) {
-    HInstruction* use = it_use.Current()->GetUser();
-    bool merged = MergeIntoShifterOperand(use, bitfield_op);
+  for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) {
+    HInstruction* user = it->GetUser();
+    // Increment `it` now because `*it` will disappear thanks to MergeIntoShifterOperand().
+    ++it;
+    bool merged = MergeIntoShifterOperand(user, bitfield_op);
     DCHECK(merged);
   }
 
diff --git a/compiler/optimizing/instruction_simplifier_shared.cc b/compiler/optimizing/instruction_simplifier_shared.cc
index a11b5bd5c3..dab1ebc16d 100644
--- a/compiler/optimizing/instruction_simplifier_shared.cc
+++ b/compiler/optimizing/instruction_simplifier_shared.cc
@@ -103,13 +103,10 @@ bool TryCombineMultiplyAccumulate(HMul* mul, InstructionSet isa) {
       return false;
   }
 
-  HInstruction* use = mul->HasNonEnvironmentUses()
-      ? mul->GetUses().GetFirst()->GetUser()
-      : nullptr;
-
   ArenaAllocator* arena = mul->GetBlock()->GetGraph()->GetArena();
 
   if (mul->HasOnlyOneNonEnvironmentUse()) {
+    HInstruction* use = mul->GetUses().front().GetUser();
     if (use->IsAdd() || use->IsSub()) {
       // Replace code looking like
       //    MUL tmp, x, y
diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc
index bdaef1d0e9..f9a955fb0a 100644
--- a/compiler/optimizing/live_ranges_test.cc
+++ b/compiler/optimizing/live_ranges_test.cc
@@ -441,7 +441,7 @@ TEST_F(LiveRangesTest, CFG4) {
   ASSERT_TRUE(range->GetNext() == nullptr);
 
   HPhi* phi = liveness.GetInstructionFromSsaIndex(4)->AsPhi();
-  ASSERT_TRUE(phi->GetUses().HasOnlyOneUse());
+  ASSERT_TRUE(phi->GetUses().HasExactlyOneElement());
   interval = phi->GetLiveInterval();
   range = interval->GetFirstRange();
   ASSERT_EQ(26u, range->GetStart());
diff --git a/compiler/optimizing/load_store_elimination.cc b/compiler/optimizing/load_store_elimination.cc
index ac7ed86d1d..2de41580b6 100644
--- a/compiler/optimizing/load_store_elimination.cc
+++ b/compiler/optimizing/load_store_elimination.cc
@@ -43,31 +43,29 @@ class ReferenceInfo : public ArenaObject<kArenaAllocMisc> {
 
     // Visit all uses to determine if this reference can spread into the heap,
     // a method call, etc.
-    for (HUseIterator<HInstruction*> use_it(reference_->GetUses());
-         !use_it.Done();
-         use_it.Advance()) {
-      HInstruction* use = use_it.Current()->GetUser();
-      DCHECK(!use->IsNullCheck()) << "NullCheck should have been eliminated";
-      if (use->IsBoundType()) {
+    for (const HUseListNode<HInstruction*>& use : reference_->GetUses()) {
+      HInstruction* user = use.GetUser();
+      DCHECK(!user->IsNullCheck()) << "NullCheck should have been eliminated";
+      if (user->IsBoundType()) {
         // BoundType shouldn't normally be necessary for a NewInstance.
         // Just be conservative for the uncommon cases.
         is_singleton_ = false;
         is_singleton_and_not_returned_ = false;
         return;
       }
-      if (use->IsPhi() || use->IsSelect() || use->IsInvoke() ||
-          (use->IsInstanceFieldSet() && (reference_ == use->InputAt(1))) ||
-          (use->IsUnresolvedInstanceFieldSet() && (reference_ == use->InputAt(1))) ||
-          (use->IsStaticFieldSet() && (reference_ == use->InputAt(1))) ||
-          (use->IsUnresolvedStaticFieldSet() && (reference_ == use->InputAt(0))) ||
-          (use->IsArraySet() && (reference_ == use->InputAt(2)))) {
+      if (user->IsPhi() || user->IsSelect() || user->IsInvoke() ||
+          (user->IsInstanceFieldSet() && (reference_ == user->InputAt(1))) ||
+          (user->IsUnresolvedInstanceFieldSet() && (reference_ == user->InputAt(1))) ||
+          (user->IsStaticFieldSet() && (reference_ == user->InputAt(1))) ||
+          (user->IsUnresolvedStaticFieldSet() && (reference_ == user->InputAt(0))) ||
+          (user->IsArraySet() && (reference_ == user->InputAt(2)))) {
         // reference_ is merged to HPhi/HSelect, passed to a callee, or stored to heap.
         // reference_ isn't the only name that can refer to its value anymore.
         is_singleton_ = false;
         is_singleton_and_not_returned_ = false;
         return;
       }
-      if (use->IsReturn()) {
+      if (user->IsReturn()) {
         is_singleton_and_not_returned_ = false;
       }
     }
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 1afa36a89c..53a10f3128 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -681,8 +681,8 @@ void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial,
     DCHECK_EQ(replacement->GetType(), Primitive::kPrimVoid);
     DCHECK_EQ(initial->GetBlock(), this);
     DCHECK_EQ(initial->GetType(), Primitive::kPrimVoid);
-    DCHECK(initial->GetUses().IsEmpty());
-    DCHECK(initial->GetEnvUses().IsEmpty());
+    DCHECK(initial->GetUses().empty());
+    DCHECK(initial->GetEnvUses().empty());
     replacement->SetBlock(this);
     replacement->SetId(GetGraph()->GetNextInstructionId());
     instructions_.InsertInstructionBefore(replacement, initial);
@@ -774,8 +774,8 @@ static void Remove(HInstructionList* instruction_list,
   instruction->SetBlock(nullptr);
   instruction_list->RemoveInstruction(instruction);
   if (ensure_safety) {
-    DCHECK(instruction->GetUses().IsEmpty());
-    DCHECK(instruction->GetEnvUses().IsEmpty());
+    DCHECK(instruction->GetUses().empty());
+    DCHECK(instruction->GetEnvUses().empty());
     RemoveAsUser(instruction);
   }
 }
@@ -839,8 +839,11 @@ void HEnvironment::CopyFromWithLoopPhiAdjustment(HEnvironment* env,
 }
 
 void HEnvironment::RemoveAsUserOfInput(size_t index) const {
-  const HUserRecord<HEnvironment*>& user_record = vregs_[index];
-  user_record.GetInstruction()->RemoveEnvironmentUser(user_record.GetUseNode());
+  const HUserRecord<HEnvironment*>& env_use = vregs_[index];
+  HInstruction* user = env_use.GetInstruction();
+  auto before_env_use_node = env_use.GetBeforeUseNode();
+  user->env_uses_.erase_after(before_env_use_node);
+  user->FixUpUserRecordsAfterEnvUseRemoval(before_env_use_node);
 }
 
 HInstruction::InstructionKind HInstruction::GetKind() const {
@@ -985,24 +988,22 @@ void HInstruction::RemoveEnvironment() {
 
 void HInstruction::ReplaceWith(HInstruction* other) {
   DCHECK(other != nullptr);
-  for (HUseIterator<HInstruction*> it(GetUses()); !it.Done(); it.Advance()) {
-    HUseListNode<HInstruction*>* current = it.Current();
-    HInstruction* user = current->GetUser();
-    size_t input_index = current->GetIndex();
+  for (const HUseListNode<HInstruction*>& use : GetUses()) {
+    HInstruction* user = use.GetUser();
+    size_t input_index = use.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();
-    HEnvironment* user = current->GetUser();
-    size_t input_index = current->GetIndex();
+  for (const HUseListNode<HEnvironment*>& use : GetEnvUses()) {
+    HEnvironment* user = use.GetUser();
+    size_t input_index = use.GetIndex();
     user->SetRawEnvAt(input_index, other);
     other->AddEnvUseAt(user, input_index);
   }
 
-  uses_.Clear();
-  env_uses_.Clear();
+  uses_.clear();
+  env_uses_.clear();
 }
 
 void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) {
@@ -1280,17 +1281,18 @@ void HInstruction::MoveBeforeFirstUserAndOutOfLoops() {
   DCHECK_EQ(InputCount(), 0u);
 
   // Find the target block.
-  HUseIterator<HInstruction*> uses_it(GetUses());
-  HBasicBlock* target_block = uses_it.Current()->GetUser()->GetBlock();
-  uses_it.Advance();
-  while (!uses_it.Done() && uses_it.Current()->GetUser()->GetBlock() == target_block) {
-    uses_it.Advance();
-  }
-  if (!uses_it.Done()) {
+  auto uses_it = GetUses().begin();
+  auto uses_end = GetUses().end();
+  HBasicBlock* target_block = uses_it->GetUser()->GetBlock();
+  ++uses_it;
+  while (uses_it != uses_end && uses_it->GetUser()->GetBlock() == target_block) {
+    ++uses_it;
+  }
+  if (uses_it != uses_end) {
     // This instruction has uses in two or more blocks. Find the common dominator.
     CommonDominator finder(target_block);
-    for (; !uses_it.Done(); uses_it.Advance()) {
-      finder.Update(uses_it.Current()->GetUser()->GetBlock());
+    for (; uses_it != uses_end; ++uses_it) {
+      finder.Update(uses_it->GetUser()->GetBlock());
     }
     target_block = finder.Get();
     DCHECK(target_block != nullptr);
@@ -1303,10 +1305,10 @@ void HInstruction::MoveBeforeFirstUserAndOutOfLoops() {
 
   // Find insertion position.
   HInstruction* insert_pos = nullptr;
-  for (HUseIterator<HInstruction*> uses_it2(GetUses()); !uses_it2.Done(); uses_it2.Advance()) {
-    if (uses_it2.Current()->GetUser()->GetBlock() == target_block &&
-        (insert_pos == nullptr || uses_it2.Current()->GetUser()->StrictlyDominates(insert_pos))) {
-      insert_pos = uses_it2.Current()->GetUser();
+  for (const HUseListNode<HInstruction*>& use : GetUses()) {
+    if (use.GetUser()->GetBlock() == target_block &&
+        (insert_pos == nullptr || use.GetUser()->StrictlyDominates(insert_pos))) {
+      insert_pos = use.GetUser();
     }
   }
   if (insert_pos == nullptr) {
@@ -1586,10 +1588,10 @@ void HInstructionList::Add(const HInstructionList& instruction_list) {
 static void RemoveUsesOfDeadInstruction(HInstruction* insn) {
   DCHECK(!insn->HasEnvironmentUses());
   while (insn->HasNonEnvironmentUses()) {
-    HUseListNode<HInstruction*>* use = insn->GetUses().GetFirst();
-    size_t use_index = use->GetIndex();
-    HBasicBlock* user_block =  use->GetUser()->GetBlock();
-    DCHECK(use->GetUser()->IsPhi() && user_block->IsCatchBlock());
+    const HUseListNode<HInstruction*>& use = insn->GetUses().front();
+    size_t use_index = use.GetIndex();
+    HBasicBlock* user_block =  use.GetUser()->GetBlock();
+    DCHECK(use.GetUser()->IsPhi() && user_block->IsCatchBlock());
     for (HInstructionIterator phi_it(user_block->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
       phi_it.Current()->AsPhi()->RemoveInputAt(use_index);
     }
@@ -2391,12 +2393,11 @@ std::ostream& operator<<(std::ostream& os, HLoadString::LoadKind rhs) {
 }
 
 void HInstruction::RemoveEnvironmentUsers() {
-  for (HUseIterator<HEnvironment*> use_it(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);
+  for (const HUseListNode<HEnvironment*>& use : GetEnvUses()) {
+    HEnvironment* user = use.GetUser();
+    user->SetRawEnvAt(use.GetIndex(), nullptr);
   }
-  env_uses_.Clear();
+  env_uses_.clear();
 }
 
 // Returns an instruction with the opposite Boolean value from 'cond'.
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 1ea2247da6..885abff7f5 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -36,6 +36,7 @@
 #include "offsets.h"
 #include "primitive.h"
 #include "utils/array_ref.h"
+#include "utils/intrusive_forward_list.h"
 
 namespace art {
 
@@ -1334,127 +1335,31 @@ FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
   const H##type* As##type() const { return this; }                      \
   H##type* As##type() { return this; }
 
-template <typename T> class HUseList;
-
 template <typename T>
 class HUseListNode : public ArenaObject<kArenaAllocUseListNode> {
  public:
-  HUseListNode* GetPrevious() const { return prev_; }
-  HUseListNode* GetNext() const { return next_; }
   T GetUser() const { return user_; }
   size_t GetIndex() const { return index_; }
   void SetIndex(size_t index) { index_ = index; }
 
+  // Hook for the IntrusiveForwardList<>.
+  // TODO: Hide this better.
+  IntrusiveForwardListHook hook;
+
  private:
   HUseListNode(T user, size_t index)
-      : user_(user), index_(index), prev_(nullptr), next_(nullptr) {}
+      : user_(user), index_(index) {}
 
   T const user_;
   size_t index_;
-  HUseListNode<T>* prev_;
-  HUseListNode<T>* next_;
 
-  friend class HUseList<T>;
+  friend class HInstruction;
 
   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) {
-    DCHECK(node != nullptr);
-    DCHECK(Contains(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 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;
-  }
-
-  bool HasOnlyOneUse() const {
-    return first_ != nullptr && first_->next_ == nullptr;
-  }
-
-  size_t SizeSlow() const {
-    size_t count = 0;
-    for (HUseListNode<T>* current = first_; current != nullptr; current = current->GetNext()) {
-      ++count;
-    }
-    return count;
-  }
-
- 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;
-};
+using HUseList = IntrusiveForwardList<HUseListNode<T>>;
 
 // This class is used by HEnvironment and HInstruction classes to record the
 // instructions they use and pointers to the corresponding HUseListNodes kept
@@ -1462,25 +1367,26 @@ class HUseIterator : public ValueObject {
 template <typename T>
 class HUserRecord : public ValueObject {
  public:
-  HUserRecord() : instruction_(nullptr), use_node_(nullptr) {}
-  explicit HUserRecord(HInstruction* instruction) : instruction_(instruction), use_node_(nullptr) {}
+  HUserRecord() : instruction_(nullptr), before_use_node_() {}
+  explicit HUserRecord(HInstruction* instruction) : instruction_(instruction), before_use_node_() {}
 
-  HUserRecord(const HUserRecord<T>& old_record, HUseListNode<T>* use_node)
-    : instruction_(old_record.instruction_), use_node_(use_node) {
+  HUserRecord(const HUserRecord<T>& old_record, typename HUseList<T>::iterator before_use_node)
+      : HUserRecord(old_record.instruction_, before_use_node) {}
+  HUserRecord(HInstruction* instruction, typename HUseList<T>::iterator before_use_node)
+      : instruction_(instruction), before_use_node_(before_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_; }
+  typename HUseList<T>::iterator GetBeforeUseNode() const { return before_use_node_; }
+  typename HUseList<T>::iterator GetUseNode() const { return ++GetBeforeUseNode(); }
 
  private:
   // Instruction used by the user.
   HInstruction* instruction_;
 
-  // Corresponding entry in the use list kept by 'instruction_'.
-  HUseListNode<T>* use_node_;
+  // Iterator before the corresponding entry in the use list kept by 'instruction_'.
+  typename HUseList<T>::iterator before_use_node_;
 };
 
 /**
@@ -1805,14 +1711,6 @@ class HEnvironment : public ArenaObject<kArenaAllocEnvironment> {
   }
 
  private:
-  // 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_[index] = HUserRecord<HEnvironment*>(vregs_[index], env_use);
-  }
-
   ArenaVector<HUserRecord<HEnvironment*>> vregs_;
   ArenaVector<Location> locations_;
   HEnvironment* parent_;
@@ -1921,31 +1819,39 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> {
 
   void AddUseAt(HInstruction* user, size_t index) {
     DCHECK(user != nullptr);
-    HUseListNode<HInstruction*>* use =
-        uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena());
-    user->SetRawInputRecordAt(index, HUserRecord<HInstruction*>(user->InputRecordAt(index), use));
+    // Note: fixup_end remains valid across push_front().
+    auto fixup_end = uses_.empty() ? uses_.begin() : ++uses_.begin();
+    HUseListNode<HInstruction*>* new_node =
+        new (GetBlock()->GetGraph()->GetArena()) HUseListNode<HInstruction*>(user, index);
+    uses_.push_front(*new_node);
+    FixUpUserRecordsAfterUseInsertion(fixup_end);
   }
 
   void AddEnvUseAt(HEnvironment* user, size_t index) {
     DCHECK(user != nullptr);
-    HUseListNode<HEnvironment*>* env_use =
-        env_uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena());
-    user->RecordEnvUse(env_use);
+    // Note: env_fixup_end remains valid across push_front().
+    auto env_fixup_end = env_uses_.empty() ? env_uses_.begin() : ++env_uses_.begin();
+    HUseListNode<HEnvironment*>* new_node =
+        new (GetBlock()->GetGraph()->GetArena()) HUseListNode<HEnvironment*>(user, index);
+    env_uses_.push_front(*new_node);
+    FixUpUserRecordsAfterEnvUseInsertion(env_fixup_end);
   }
 
   void RemoveAsUserOfInput(size_t input) {
     HUserRecord<HInstruction*> input_use = InputRecordAt(input);
-    input_use.GetInstruction()->uses_.Remove(input_use.GetUseNode());
+    HUseList<HInstruction*>::iterator before_use_node = input_use.GetBeforeUseNode();
+    input_use.GetInstruction()->uses_.erase_after(before_use_node);
+    input_use.GetInstruction()->FixUpUserRecordsAfterUseRemoval(before_use_node);
   }
 
   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(); }
-  bool HasNonEnvironmentUses() const { return !uses_.IsEmpty(); }
+  bool HasUses() const { return !uses_.empty() || !env_uses_.empty(); }
+  bool HasEnvironmentUses() const { return !env_uses_.empty(); }
+  bool HasNonEnvironmentUses() const { return !uses_.empty(); }
   bool HasOnlyOneNonEnvironmentUse() const {
-    return !HasEnvironmentUses() && GetUses().HasOnlyOneUse();
+    return !HasEnvironmentUses() && GetUses().HasExactlyOneElement();
   }
 
   // Does this instruction strictly dominate `other_instruction`?
@@ -2147,7 +2053,45 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> {
   }
 
  private:
-  void RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use_node) { env_uses_.Remove(use_node); }
+  void FixUpUserRecordsAfterUseInsertion(HUseList<HInstruction*>::iterator fixup_end) {
+    auto before_use_node = uses_.before_begin();
+    for (auto use_node = uses_.begin(); use_node != fixup_end; ++use_node) {
+      HInstruction* user = use_node->GetUser();
+      size_t input_index = use_node->GetIndex();
+      user->SetRawInputRecordAt(input_index, HUserRecord<HInstruction*>(this, before_use_node));
+      before_use_node = use_node;
+    }
+  }
+
+  void FixUpUserRecordsAfterUseRemoval(HUseList<HInstruction*>::iterator before_use_node) {
+    auto next = ++HUseList<HInstruction*>::iterator(before_use_node);
+    if (next != uses_.end()) {
+      HInstruction* next_user = next->GetUser();
+      size_t next_index = next->GetIndex();
+      DCHECK(next_user->InputRecordAt(next_index).GetInstruction() == this);
+      next_user->SetRawInputRecordAt(next_index, HUserRecord<HInstruction*>(this, before_use_node));
+    }
+  }
+
+  void FixUpUserRecordsAfterEnvUseInsertion(HUseList<HEnvironment*>::iterator env_fixup_end) {
+    auto before_env_use_node = env_uses_.before_begin();
+    for (auto env_use_node = env_uses_.begin(); env_use_node != env_fixup_end; ++env_use_node) {
+      HEnvironment* user = env_use_node->GetUser();
+      size_t input_index = env_use_node->GetIndex();
+      user->vregs_[input_index] = HUserRecord<HEnvironment*>(this, before_env_use_node);
+      before_env_use_node = env_use_node;
+    }
+  }
+
+  void FixUpUserRecordsAfterEnvUseRemoval(HUseList<HEnvironment*>::iterator before_env_use_node) {
+    auto next = ++HUseList<HEnvironment*>::iterator(before_env_use_node);
+    if (next != env_uses_.end()) {
+      HEnvironment* next_user = next->GetUser();
+      size_t next_index = next->GetIndex();
+      DCHECK(next_user->vregs_[next_index].GetInstruction() == this);
+      next_user->vregs_[next_index] = HUserRecord<HEnvironment*>(this, before_env_use_node);
+    }
+  }
 
   HInstruction* previous_;
   HInstruction* next_;
diff --git a/compiler/optimizing/nodes_test.cc b/compiler/optimizing/nodes_test.cc
index 764f5fec5b..d4e2a58103 100644
--- a/compiler/optimizing/nodes_test.cc
+++ b/compiler/optimizing/nodes_test.cc
@@ -91,7 +91,7 @@ TEST(Node, InsertInstruction) {
   entry->InsertInstructionBefore(to_insert, parameter2);
 
   ASSERT_TRUE(parameter1->HasUses());
-  ASSERT_TRUE(parameter1->GetUses().HasOnlyOneUse());
+  ASSERT_TRUE(parameter1->GetUses().HasExactlyOneElement());
 }
 
 /**
@@ -115,7 +115,7 @@ TEST(Node, AddInstruction) {
   entry->AddInstruction(to_add);
 
   ASSERT_TRUE(parameter->HasUses());
-  ASSERT_TRUE(parameter->GetUses().HasOnlyOneUse());
+  ASSERT_TRUE(parameter->GetUses().HasExactlyOneElement());
 }
 
 TEST(Node, ParentEnvironment) {
@@ -134,7 +134,7 @@ TEST(Node, ParentEnvironment) {
   entry->AddInstruction(new (&allocator) HExit());
 
   ASSERT_TRUE(parameter1->HasUses());
-  ASSERT_TRUE(parameter1->GetUses().HasOnlyOneUse());
+  ASSERT_TRUE(parameter1->GetUses().HasExactlyOneElement());
 
   HEnvironment* environment = new (&allocator) HEnvironment(
       &allocator, 1, graph->GetDexFile(), graph->GetMethodIdx(), 0, kStatic, with_environment);
@@ -145,7 +145,7 @@ TEST(Node, ParentEnvironment) {
   with_environment->SetRawEnvironment(environment);
 
   ASSERT_TRUE(parameter1->HasEnvironmentUses());
-  ASSERT_TRUE(parameter1->GetEnvUses().HasOnlyOneUse());
+  ASSERT_TRUE(parameter1->GetEnvUses().HasExactlyOneElement());
 
   HEnvironment* parent1 = new (&allocator) HEnvironment(
       &allocator, 1, graph->GetDexFile(), graph->GetMethodIdx(), 0, kStatic, nullptr);
diff --git a/compiler/optimizing/prepare_for_register_allocation.cc b/compiler/optimizing/prepare_for_register_allocation.cc
index fc72727196..dcc89e8d8f 100644
--- a/compiler/optimizing/prepare_for_register_allocation.cc
+++ b/compiler/optimizing/prepare_for_register_allocation.cc
@@ -63,8 +63,8 @@ void PrepareForRegisterAllocation::VisitArraySet(HArraySet* instruction) {
 void PrepareForRegisterAllocation::VisitClinitCheck(HClinitCheck* check) {
   // Try to find a static invoke or a new-instance from which this check originated.
   HInstruction* implicit_clinit = nullptr;
-  for (HUseIterator<HInstruction*> it(check->GetUses()); !it.Done(); it.Advance()) {
-    HInstruction* user = it.Current()->GetUser();
+  for (const HUseListNode<HInstruction*>& use : check->GetUses()) {
+    HInstruction* user = use.GetUser();
     if ((user->IsInvokeStaticOrDirect() || user->IsNewInstance()) &&
         CanMoveClinitCheck(check, user)) {
       implicit_clinit = user;
@@ -85,11 +85,12 @@ void PrepareForRegisterAllocation::VisitClinitCheck(HClinitCheck* check) {
   // If we found a static invoke or new-instance for merging, remove the check
   // from dominated static invokes.
   if (implicit_clinit != nullptr) {
-    for (HUseIterator<HInstruction*> it(check->GetUses()); !it.Done(); ) {
-      HInstruction* user = it.Current()->GetUser();
+    const HUseList<HInstruction*>& uses = check->GetUses();
+    for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) {
+      HInstruction* user = it->GetUser();
       // All other uses must be dominated.
       DCHECK(implicit_clinit->StrictlyDominates(user) || (implicit_clinit == user));
-      it.Advance();  // Advance before we remove the node, reference to the next node is preserved.
+      ++it;  // Advance before we remove the node, reference to the next node is preserved.
       if (user->IsInvokeStaticOrDirect()) {
         user->AsInvokeStaticOrDirect()->RemoveExplicitClinitCheck(
             HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
@@ -159,7 +160,7 @@ bool PrepareForRegisterAllocation::CanEmitConditionAt(HCondition* condition,
 
 void PrepareForRegisterAllocation::VisitCondition(HCondition* condition) {
   if (condition->HasOnlyOneNonEnvironmentUse()) {
-    HInstruction* user = condition->GetUses().GetFirst()->GetUser();
+    HInstruction* user = condition->GetUses().front().GetUser();
     if (CanEmitConditionAt(condition, user)) {
       condition->MarkEmittedAtUseSite();
     }
diff --git a/compiler/optimizing/pretty_printer.h b/compiler/optimizing/pretty_printer.h
index 429e6e3d3f..ee32518c01 100644
--- a/compiler/optimizing/pretty_printer.h
+++ b/compiler/optimizing/pretty_printer.h
@@ -55,13 +55,13 @@ class HPrettyPrinter : public HGraphVisitor {
     if (instruction->HasUses()) {
       PrintString(" [");
       bool first = true;
-      for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
+      for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
         if (first) {
           first = false;
         } else {
           PrintString(", ");
         }
-        PrintInt(it.Current()->GetUser()->GetId());
+        PrintInt(use.GetUser()->GetId());
       }
       PrintString("]");
     }
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 95f10e0720..cd4391d2db 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -187,8 +187,8 @@ static bool ShouldCreateBoundType(HInstruction* position,
   if (existing_bound_type->GetUpperBound().IsSupertypeOf(upper_bound)) {
     if (kIsDebugBuild) {
       // Check that the existing HBoundType dominates all the uses.
-      for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) {
-        HInstruction* user = it.Current()->GetUser();
+      for (const HUseListNode<HInstruction*>& use : obj->GetUses()) {
+        HInstruction* user = use.GetUser();
         if (dominator_instr != nullptr) {
           DCHECK(!dominator_instr->StrictlyDominates(user)
               || user == existing_bound_type
@@ -242,8 +242,12 @@ void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) {
       ? ifInstruction->IfTrueSuccessor()
       : ifInstruction->IfFalseSuccessor();
 
-  for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) {
-    HInstruction* user = it.Current()->GetUser();
+  const HUseList<HInstruction*>& uses = obj->GetUses();
+  for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) {
+    HInstruction* user = it->GetUser();
+    size_t index = it->GetIndex();
+    // Increment `it` now because `*it` may disappear thanks to user->ReplaceInput().
+    ++it;
     if (notNullBlock->Dominates(user->GetBlock())) {
       if (bound_type == nullptr) {
         ScopedObjectAccess soa(Thread::Current());
@@ -264,7 +268,7 @@ void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) {
           break;
         }
       }
-      user->ReplaceInput(bound_type, it.Current()->GetIndex());
+      user->ReplaceInput(bound_type, index);
     }
   }
 }
@@ -379,8 +383,12 @@ void ReferenceTypePropagation::BoundTypeForIfInstanceOf(HBasicBlock* block) {
     return;
   }
   DCHECK(!obj->IsLoadClass()) << "We should not replace HLoadClass instructions";
-  for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) {
-    HInstruction* user = it.Current()->GetUser();
+  const HUseList<HInstruction*>& uses = obj->GetUses();
+  for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) {
+    HInstruction* user = it->GetUser();
+    size_t index = it->GetIndex();
+    // Increment `it` now because `*it` may disappear thanks to user->ReplaceInput().
+    ++it;
     if (instanceOfTrueBlock->Dominates(user->GetBlock())) {
       if (bound_type == nullptr) {
         ScopedObjectAccess soa(Thread::Current());
@@ -396,7 +404,7 @@ void ReferenceTypePropagation::BoundTypeForIfInstanceOf(HBasicBlock* block) {
           break;
         }
       }
-      user->ReplaceInput(bound_type, it.Current()->GetIndex());
+      user->ReplaceInput(bound_type, index);
     }
   }
 }
@@ -887,8 +895,8 @@ void ReferenceTypePropagation::AddToWorklist(HInstruction* instruction) {
 }
 
 void ReferenceTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) {
-  for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
-    HInstruction* user = it.Current()->GetUser();
+  for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
+    HInstruction* user = use.GetUser();
     if ((user->IsPhi() && user->AsPhi()->IsLive())
        || user->IsBoundType()
        || user->IsNullCheck()
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 2fe2f2053a..600e1d3b0b 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -108,8 +108,8 @@ static void AddDependentInstructionsToWorklist(HInstruction* instruction,
   // marked dead/conflicting too, so we add them to the worklist. Otherwise we
   // add users whose type does not match and needs to be updated.
   bool add_all_live_phis = instruction->IsPhi() && instruction->AsPhi()->IsDead();
-  for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
-    HInstruction* user = it.Current()->GetUser();
+  for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
+    HInstruction* user = use.GetUser();
     if (user->IsPhi() && user->AsPhi()->IsLive()) {
       if (add_all_live_phis || user->GetType() != instruction->GetType()) {
         worklist->push_back(user->AsPhi());
@@ -412,27 +412,24 @@ bool SsaBuilder::FixAmbiguousArrayOps() {
 }
 
 static bool HasAliasInEnvironments(HInstruction* instruction) {
-  for (HUseIterator<HEnvironment*> use_it(instruction->GetEnvUses());
-       !use_it.Done();
-       use_it.Advance()) {
-    HEnvironment* use = use_it.Current()->GetUser();
-    HUseListNode<HEnvironment*>* next = use_it.Current()->GetNext();
-    if (next != nullptr && next->GetUser() == use) {
+  HEnvironment* last_user = nullptr;
+  for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
+    DCHECK(use.GetUser() != nullptr);
+    // Note: The first comparison (== null) always fails.
+    if (use.GetUser() == last_user) {
       return true;
     }
+    last_user = use.GetUser();
   }
 
   if (kIsDebugBuild) {
     // Do a quadratic search to ensure same environment uses are next
     // to each other.
-    for (HUseIterator<HEnvironment*> use_it(instruction->GetEnvUses());
-         !use_it.Done();
-         use_it.Advance()) {
-      HUseListNode<HEnvironment*>* current = use_it.Current();
-      HUseListNode<HEnvironment*>* next = current->GetNext();
-      while (next != nullptr) {
+    const HUseList<HEnvironment*>& env_uses = instruction->GetEnvUses();
+    for (auto current = env_uses.begin(), end = env_uses.end(); current != end; ++current) {
+      auto next = current;
+      for (++next; next != end; ++next) {
         DCHECK(next->GetUser() != current->GetUser());
-        next = next->GetNext();
       }
     }
   }
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 83e9dacb1a..d33eca7da3 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -283,11 +283,9 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
       if (current->IsEmittedAtUseSite()) {
         if (kIsDebugBuild) {
           DCHECK(!current->GetLocations()->Out().IsValid());
-          for (HUseIterator<HInstruction*> use_it(current->GetUses());
-               !use_it.Done();
-               use_it.Advance()) {
-            HInstruction* user = use_it.Current()->GetUser();
-            size_t index = use_it.Current()->GetIndex();
+          for (const HUseListNode<HInstruction*>& use : current->GetUses()) {
+            HInstruction* user = use.GetUser();
+            size_t index = use.GetIndex();
             DCHECK(!user->GetLocations()->InAt(index).IsValid());
           }
           DCHECK(!current->HasEnvironmentUses());
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 6816b6a028..aeb31094d4 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -43,8 +43,8 @@ void SsaDeadPhiElimination::MarkDeadPhis() {
 
       bool keep_alive = (graph_->IsDebuggable() && phi->HasEnvironmentUses());
       if (!keep_alive) {
-        for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) {
-          if (!use_it.Current()->GetUser()->IsPhi()) {
+        for (const HUseListNode<HInstruction*>& use : phi->GetUses()) {
+          if (!use.GetUser()->IsPhi()) {
             keep_alive = true;
             break;
           }
@@ -94,9 +94,8 @@ void SsaDeadPhiElimination::EliminateDeadPhis() {
       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()) {
-            HInstruction* user = use_it.Current()->GetUser();
+          for (const HUseListNode<HInstruction*>& use : phi->GetUses()) {
+            HInstruction* user = use.GetUser();
             DCHECK(user->IsLoopHeaderPhi());
             DCHECK(user->AsPhi()->IsDead());
           }
@@ -106,11 +105,9 @@ void SsaDeadPhiElimination::EliminateDeadPhis() {
           phi->RemoveAsUserOfInput(i);
         }
         // 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);
+        for (const HUseListNode<HEnvironment*>& use : phi->GetEnvUses()) {
+          HEnvironment* user = use.GetUser();
+          user->SetRawEnvAt(use.GetIndex(), nullptr);
         }
         // Delete it from the instruction list.
         block->RemovePhi(phi, /*ensure_safety=*/ false);
@@ -233,9 +230,8 @@ void SsaRedundantPhiElimination::Run() {
 
       // Because we're updating the users of this phi, we may have new candidates
       // for elimination. Add phis that use this phi to the worklist.
-      for (HUseIterator<HInstruction*> it(current->GetUses()); !it.Done(); it.Advance()) {
-        HUseListNode<HInstruction*>* use = it.Current();
-        HInstruction* user = use->GetUser();
+      for (const HUseListNode<HInstruction*>& use : current->GetUses()) {
+        HInstruction* user = use.GetUser();
         if (user->IsPhi() && !ContainsElement(visited_phis_in_cycle, user->GetId())) {
           worklist_.push_back(user->AsPhi());
         }