diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 084360f..659c6f8 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -1206,9 +1206,9 @@
           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 @@
         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 6412b24..a849448 100644
--- a/compiler/optimizing/common_arm64.h
+++ b/compiler/optimizing/common_arm64.h
@@ -199,7 +199,7 @@
 
   // 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 9ea4b2d..96837a8 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -342,36 +342,34 @@
 
   // 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 @@
   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 @@
   }
 
   // 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 fe47f7d..9efc13f 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -608,12 +608,7 @@
     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 1f66db7..d7b3856 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -409,9 +409,9 @@
     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 @@
   }
 
   // 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 f00d960..e4a711e 100644
--- a/compiler/optimizing/instruction_simplifier_arm64.cc
+++ b/compiler/optimizing/instruction_simplifier_arm64.cc
@@ -140,7 +140,7 @@
                                                                  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 @@
   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 a11b5bd..dab1ebc 100644
--- a/compiler/optimizing/instruction_simplifier_shared.cc
+++ b/compiler/optimizing/instruction_simplifier_shared.cc
@@ -103,13 +103,10 @@
       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 bdaef1d..f9a955f 100644
--- a/compiler/optimizing/live_ranges_test.cc
+++ b/compiler/optimizing/live_ranges_test.cc
@@ -441,7 +441,7 @@
   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 e1977b1..1b23622 100644
--- a/compiler/optimizing/load_store_elimination.cc
+++ b/compiler/optimizing/load_store_elimination.cc
@@ -43,31 +43,29 @@
 
     // 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 5091c7b..6874daf 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -698,8 +698,8 @@
     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);
@@ -791,8 +791,8 @@
   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);
   }
 }
@@ -856,8 +856,11 @@
 }
 
 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 {
@@ -1002,24 +1005,22 @@
 
 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) {
@@ -1297,17 +1298,18 @@
   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();
+  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.Done()) {
+  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);
@@ -1320,10 +1322,10 @@
 
   // 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) {
@@ -1603,10 +1605,10 @@
 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);
     }
@@ -2408,12 +2410,11 @@
 }
 
 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 dc5a8fa..c9adcd4 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 @@
   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 @@
 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_;
 };
 
 /**
@@ -1822,14 +1728,6 @@
   }
 
  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_;
@@ -1938,31 +1836,39 @@
 
   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`?
@@ -2164,7 +2070,45 @@
   }
 
  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 764f5fe..d4e2a58 100644
--- a/compiler/optimizing/nodes_test.cc
+++ b/compiler/optimizing/nodes_test.cc
@@ -91,7 +91,7 @@
   entry->InsertInstructionBefore(to_insert, parameter2);
 
   ASSERT_TRUE(parameter1->HasUses());
-  ASSERT_TRUE(parameter1->GetUses().HasOnlyOneUse());
+  ASSERT_TRUE(parameter1->GetUses().HasExactlyOneElement());
 }
 
 /**
@@ -115,7 +115,7 @@
   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 @@
   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 @@
   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 fc72727..dcc89e8 100644
--- a/compiler/optimizing/prepare_for_register_allocation.cc
+++ b/compiler/optimizing/prepare_for_register_allocation.cc
@@ -63,8 +63,8 @@
 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 @@
   // 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 @@
 
 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 429e6e3..ee32518 100644
--- a/compiler/optimizing/pretty_printer.h
+++ b/compiler/optimizing/pretty_printer.h
@@ -55,13 +55,13 @@
     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 95f10e0..cd4391d 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -187,8 +187,8 @@
   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 @@
       ? 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 @@
           break;
         }
       }
-      user->ReplaceInput(bound_type, it.Current()->GetIndex());
+      user->ReplaceInput(bound_type, index);
     }
   }
 }
@@ -379,8 +383,12 @@
     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 @@
           break;
         }
       }
-      user->ReplaceInput(bound_type, it.Current()->GetIndex());
+      user->ReplaceInput(bound_type, index);
     }
   }
 }
@@ -887,8 +895,8 @@
 }
 
 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 eeadbeb..f935585 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -108,8 +108,8 @@
   // 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());
@@ -409,27 +409,24 @@
 }
 
 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 134c1f6..5534aea 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -283,11 +283,9 @@
       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 6816b6a..aeb3109 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -43,8 +43,8 @@
 
       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 @@
       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 @@
           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 @@
 
       // 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());
         }
diff --git a/compiler/utils/intrusive_forward_list.h b/compiler/utils/intrusive_forward_list.h
new file mode 100644
index 0000000..a90b0f5
--- /dev/null
+++ b/compiler/utils/intrusive_forward_list.h
@@ -0,0 +1,445 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_UTILS_INTRUSIVE_FORWARD_LIST_H_
+#define ART_COMPILER_UTILS_INTRUSIVE_FORWARD_LIST_H_
+
+#include <stdint.h>
+#include <functional>
+#include <iterator>
+#include <memory>
+#include <type_traits>
+
+#include "base/logging.h"
+#include "base/macros.h"
+
+namespace art {
+
+struct IntrusiveForwardListHook {
+  IntrusiveForwardListHook() : next_hook(nullptr) { }
+  explicit IntrusiveForwardListHook(const IntrusiveForwardListHook* hook) : next_hook(hook) { }
+
+  // Allow copyable values but do not copy the hook, it is not part of the value.
+  IntrusiveForwardListHook(const IntrusiveForwardListHook& other ATTRIBUTE_UNUSED)
+      : next_hook(nullptr) { }
+  IntrusiveForwardListHook& operator=(const IntrusiveForwardListHook& src ATTRIBUTE_UNUSED) {
+    return *this;
+  }
+
+  mutable const IntrusiveForwardListHook* next_hook;
+};
+
+template <typename T, IntrusiveForwardListHook T::* NextPtr = &T::hook>
+class IntrusiveForwardListMemberHook;
+
+template <typename T, typename HookTraits = IntrusiveForwardListMemberHook<T>>
+class IntrusiveForwardList;
+
+template <typename T, typename HookTraits>
+class IntrusiveForwardListIterator : public std::iterator<std::forward_iterator_tag, T> {
+ public:
+  // Construct/copy/destroy (except the private constructor used by IntrusiveForwardList<>).
+  IntrusiveForwardListIterator() : hook_(nullptr) { }
+  IntrusiveForwardListIterator(const IntrusiveForwardListIterator& src) = default;
+  IntrusiveForwardListIterator& operator=(const IntrusiveForwardListIterator& src) = default;
+
+  // Conversion from iterator to const_iterator.
+  template <typename OtherT,
+            typename = typename std::enable_if<std::is_same<T, const OtherT>::value>::type>
+  IntrusiveForwardListIterator(const IntrusiveForwardListIterator<OtherT, HookTraits>& src)
+      : hook_(src.hook_) { }
+
+  // Iteration.
+  IntrusiveForwardListIterator& operator++() {
+    DCHECK(hook_ != nullptr);
+    hook_ = hook_->next_hook;
+    return *this;
+  }
+  IntrusiveForwardListIterator operator++(int) {
+    IntrusiveForwardListIterator tmp(*this);
+    ++*this;
+    return tmp;
+  }
+
+  // Dereference
+  T& operator*() const {
+    DCHECK(hook_ != nullptr);
+    return *HookTraits::GetValue(hook_);
+  }
+  T* operator->() const {
+    return &**this;
+  }
+
+ private:
+  explicit IntrusiveForwardListIterator(const IntrusiveForwardListHook* hook) : hook_(hook) { }
+
+  const IntrusiveForwardListHook* hook_;
+
+  template <typename OtherT, typename OtherTraits>
+  friend class IntrusiveForwardListIterator;
+
+  template <typename OtherT, typename OtherTraits>
+  friend class IntrusiveForwardList;
+
+  template <typename OtherT1, typename OtherT2, typename OtherTraits>
+  friend typename std::enable_if<std::is_same<const OtherT1, const OtherT2>::value, bool>::type
+  operator==(const IntrusiveForwardListIterator<OtherT1, OtherTraits>& lhs,
+             const IntrusiveForwardListIterator<OtherT2, OtherTraits>& rhs);
+};
+
+template <typename T, typename OtherT, typename HookTraits>
+typename std::enable_if<std::is_same<const T, const OtherT>::value, bool>::type operator==(
+    const IntrusiveForwardListIterator<T, HookTraits>& lhs,
+    const IntrusiveForwardListIterator<OtherT, HookTraits>& rhs) {
+  return lhs.hook_ == rhs.hook_;
+}
+
+template <typename T, typename OtherT, typename HookTraits>
+typename std::enable_if<std::is_same<const T, const OtherT>::value, bool>::type operator!=(
+    const IntrusiveForwardListIterator<T, HookTraits>& lhs,
+    const IntrusiveForwardListIterator<OtherT, HookTraits>& rhs) {
+  return !(lhs == rhs);
+}
+
+// Intrusive version of std::forward_list<>. See also slist<> in Boost.Intrusive.
+//
+// This class template provides the same interface as std::forward_list<> as long
+// as the functions are meaningful for an intrusive container; this excludes emplace
+// functions and functions taking an std::initializer_list<> as the container does
+// not construct elements.
+template <typename T, typename HookTraits>
+class IntrusiveForwardList {
+ public:
+  typedef HookTraits hook_traits;
+  typedef       T  value_type;
+  typedef       T& reference;
+  typedef const T& const_reference;
+  typedef       T* pointer;
+  typedef const T* const_pointer;
+  typedef IntrusiveForwardListIterator<      T, hook_traits> iterator;
+  typedef IntrusiveForwardListIterator<const T, hook_traits> const_iterator;
+
+  // Construct/copy/destroy.
+  IntrusiveForwardList() = default;
+  template <typename InputIterator>
+  IntrusiveForwardList(InputIterator first, InputIterator last) : IntrusiveForwardList() {
+    insert_after(before_begin(), first, last);
+  }
+  IntrusiveForwardList(IntrusiveForwardList&& src) : first_(src.first_.next_hook) {
+    src.first_.next_hook = nullptr;
+  }
+  IntrusiveForwardList& operator=(const IntrusiveForwardList& src) = delete;
+  IntrusiveForwardList& operator=(IntrusiveForwardList&& src) {
+    IntrusiveForwardList tmp(std::move(src));
+    tmp.swap(*this);
+    return *this;
+  }
+  ~IntrusiveForwardList() = default;
+
+  // Iterators.
+  iterator before_begin() { return iterator(&first_); }
+  const_iterator before_begin() const { return const_iterator(&first_); }
+  iterator begin() { return iterator(first_.next_hook); }
+  const_iterator begin() const { return const_iterator(first_.next_hook); }
+  iterator end() { return iterator(nullptr); }
+  const_iterator end() const { return const_iterator(nullptr); }
+  const_iterator cbefore_begin() const { return const_iterator(&first_); }
+  const_iterator cbegin() const { return const_iterator(first_.next_hook); }
+  const_iterator cend() const { return const_iterator(nullptr); }
+
+  // Capacity.
+  bool empty() const { return begin() == end(); }
+  size_t max_size() { return static_cast<size_t>(-1); }
+
+  // Element access.
+  reference front() { return *begin(); }
+  const_reference front() const { return *begin(); }
+
+  // Modifiers.
+  template <typename InputIterator>
+  void assign(InputIterator first, InputIterator last) {
+    IntrusiveForwardList tmp(first, last);
+    tmp.swap(*this);
+  }
+  void push_front(value_type& value) {
+    insert_after(before_begin(), value);
+  }
+  void pop_front() {
+    DCHECK(!empty());
+    erase_after(before_begin());
+  }
+  iterator insert_after(const_iterator position, value_type& value) {
+    const IntrusiveForwardListHook* new_hook = hook_traits::GetHook(&value);
+    new_hook->next_hook = position.hook_->next_hook;
+    position.hook_->next_hook = new_hook;
+    return iterator(new_hook);
+  }
+  template <typename InputIterator>
+  iterator insert_after(const_iterator position, InputIterator first, InputIterator last) {
+    while (first != last) {
+      position = insert_after(position, *first++);
+    }
+    return iterator(position.hook_);
+  }
+  iterator erase_after(const_iterator position) {
+    const_iterator last = position;
+    std::advance(last, 2);
+    return erase_after(position, last);
+  }
+  iterator erase_after(const_iterator position, const_iterator last) {
+    DCHECK(position != last);
+    position.hook_->next_hook = last.hook_;
+    return iterator(last.hook_);
+  }
+  void swap(IntrusiveForwardList& other) {
+    std::swap(first_.next_hook, other.first_.next_hook);
+  }
+  void clear() {
+    first_.next_hook = nullptr;
+  }
+
+  // Operations.
+  void splice_after(const_iterator position, IntrusiveForwardList& src) {
+    DCHECK(position != end());
+    splice_after(position, src, src.before_begin(), src.end());
+  }
+  void splice_after(const_iterator position, IntrusiveForwardList&& src) {
+    splice_after(position, src);  // Use l-value overload.
+  }
+  // Splice the element after `i`.
+  void splice_after(const_iterator position, IntrusiveForwardList& src, const_iterator i) {
+    const_iterator last = i;
+    std::advance(last, 2);
+    splice_after(position, src, i, last);
+  }
+  // Splice the element after `i`.
+  void splice_after(const_iterator position, IntrusiveForwardList&& src, const_iterator i) {
+    splice_after(position, src, i);  // Use l-value overload.
+  }
+  // Splice elements between `first` and `last`, i.e. open range `(first, last)`.
+  void splice_after(const_iterator position,
+                    IntrusiveForwardList& src,
+                    const_iterator first,
+                    const_iterator last) {
+    DCHECK(position != end());
+    DCHECK(first != last);
+    if (++const_iterator(first) == last) {
+      // Nothing to do.
+      return;
+    }
+    // If position is just before end() and last is src.end(), we can finish this quickly.
+    if (++const_iterator(position) == end() && last == src.end()) {
+      position.hook_->next_hook = first.hook_->next_hook;
+      first.hook_->next_hook = nullptr;
+      return;
+    }
+    // Otherwise we need to find the position before last to fix up the hook.
+    const_iterator before_last = first;
+    while (++const_iterator(before_last) != last) {
+      ++before_last;
+    }
+    // Detach (first, last).
+    const IntrusiveForwardListHook* first_taken = first.hook_->next_hook;
+    first.hook_->next_hook = last.hook_;
+    // Attach the sequence to the new position.
+    before_last.hook_->next_hook = position.hook_->next_hook;
+    position.hook_->next_hook = first_taken;
+  }
+  // Splice elements between `first` and `last`, i.e. open range `(first, last)`.
+  void splice_after(const_iterator position,
+                    IntrusiveForwardList&& src,
+                    const_iterator first,
+                    const_iterator last) {
+    splice_after(position, src, first, last);  // Use l-value overload.
+  }
+  void remove(const value_type& value) {
+    remove_if([value](const value_type& v) { return value == v; });
+  }
+  template <typename Predicate>
+  void remove_if(Predicate pred) {
+    iterator prev = before_begin();
+    for (iterator current = begin(); current != end(); ++current) {
+      if (pred(*current)) {
+        erase_after(prev);
+        current = prev;
+      } else {
+        prev = current;
+      }
+    }
+  }
+  void unique() {
+    unique(std::equal_to<value_type>());
+  }
+  template <typename BinaryPredicate>
+  void unique(BinaryPredicate pred) {
+    if (!empty()) {
+      iterator prev = begin();
+      iterator current = prev;
+      ++current;
+      for (; current != end(); ++current) {
+        if (pred(*prev, *current)) {
+          erase_after(prev);
+          current = prev;
+        } else {
+          prev = current;
+        }
+      }
+    }
+  }
+  void merge(IntrusiveForwardList& other) {
+    merge(other, std::less<value_type>());
+  }
+  void merge(IntrusiveForwardList&& other) {
+    merge(other);  // Use l-value overload.
+  }
+  template <typename Compare>
+  void merge(IntrusiveForwardList& other, Compare cmp) {
+    iterator prev = before_begin();
+    iterator current = begin();
+    iterator other_prev = other.before_begin();
+    iterator other_current = other.begin();
+    while (current != end() && other_current != other.end()) {
+      if (cmp(*other_current, *current)) {
+        ++other_current;
+        splice_after(prev, other, other_prev);
+        ++prev;
+      } else {
+        prev = current;
+        ++current;
+      }
+      DCHECK(++const_iterator(prev) == current);
+      DCHECK(++const_iterator(other_prev) == other_current);
+    }
+    splice_after(prev, other);
+  }
+  template <typename Compare>
+  void merge(IntrusiveForwardList&& other, Compare cmp) {
+    merge(other, cmp);  // Use l-value overload.
+  }
+  void sort() {
+    sort(std::less<value_type>());
+  }
+  template <typename Compare>
+  void sort(Compare cmp) {
+    size_t n = std::distance(begin(), end());
+    if (n >= 2u) {
+      const_iterator middle = before_begin();
+      std::advance(middle, n / 2u);
+      IntrusiveForwardList second_half;
+      second_half.splice_after(second_half.before_begin(), *this, middle, end());
+      sort(cmp);
+      second_half.sort(cmp);
+      merge(second_half, cmp);
+    }
+  }
+  void reverse() {
+    IntrusiveForwardList reversed;
+    while (!empty()) {
+      value_type& value = front();
+      erase_after(before_begin());
+      reversed.insert_after(reversed.before_begin(), value);
+    }
+    reversed.swap(*this);
+  }
+
+  // Extensions.
+  bool HasExactlyOneElement() const {
+    return !empty() && ++begin() == end();
+  }
+  size_t SizeSlow() const {
+    return std::distance(begin(), end());
+  }
+  bool ContainsNode(const_reference node) const {
+    for (auto&& n : *this) {
+      if (std::addressof(n) == std::addressof(node)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+ private:
+  static IntrusiveForwardListHook* ModifiableHook(const IntrusiveForwardListHook* hook) {
+    return const_cast<IntrusiveForwardListHook*>(hook);
+  }
+
+  IntrusiveForwardListHook first_;
+};
+
+template <typename T, typename HookTraits>
+void swap(IntrusiveForwardList<T, HookTraits>& lhs, IntrusiveForwardList<T, HookTraits>& rhs) {
+  lhs.swap(rhs);
+}
+
+template <typename T, typename HookTraits>
+bool operator==(const IntrusiveForwardList<T, HookTraits>& lhs,
+                const IntrusiveForwardList<T, HookTraits>& rhs) {
+  auto lit = lhs.begin();
+  auto rit = rhs.begin();
+  for (; lit != lhs.end() && rit != rhs.end(); ++lit, ++rit) {
+    if (*lit != *rit) {
+      return false;
+    }
+  }
+  return lit == lhs.end() && rit == rhs.end();
+}
+
+template <typename T, typename HookTraits>
+bool operator!=(const IntrusiveForwardList<T, HookTraits>& lhs,
+                const IntrusiveForwardList<T, HookTraits>& rhs) {
+  return !(lhs == rhs);
+}
+
+template <typename T, typename HookTraits>
+bool operator<(const IntrusiveForwardList<T, HookTraits>& lhs,
+               const IntrusiveForwardList<T, HookTraits>& rhs) {
+  return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
+}
+
+template <typename T, typename HookTraits>
+bool operator>(const IntrusiveForwardList<T, HookTraits>& lhs,
+               const IntrusiveForwardList<T, HookTraits>& rhs) {
+  return rhs < lhs;
+}
+
+template <typename T, typename HookTraits>
+bool operator<=(const IntrusiveForwardList<T, HookTraits>& lhs,
+                const IntrusiveForwardList<T, HookTraits>& rhs) {
+  return !(rhs < lhs);
+}
+
+template <typename T, typename HookTraits>
+bool operator>=(const IntrusiveForwardList<T, HookTraits>& lhs,
+                const IntrusiveForwardList<T, HookTraits>& rhs) {
+  return !(lhs < rhs);
+}
+
+template <typename T, IntrusiveForwardListHook T::* NextPtr>
+class IntrusiveForwardListMemberHook {
+ public:
+  static const IntrusiveForwardListHook* GetHook(const T* value) {
+    return &(value->*NextPtr);
+  }
+
+  static T* GetValue(const IntrusiveForwardListHook* hook) {
+    return reinterpret_cast<T*>(
+        reinterpret_cast<uintptr_t>(hook) - OFFSETOF_MEMBERPTR(T, NextPtr));
+  }
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_UTILS_INTRUSIVE_FORWARD_LIST_H_
diff --git a/compiler/utils/intrusive_forward_list_test.cc b/compiler/utils/intrusive_forward_list_test.cc
new file mode 100644
index 0000000..d40ff3a
--- /dev/null
+++ b/compiler/utils/intrusive_forward_list_test.cc
@@ -0,0 +1,480 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <algorithm>
+#include <forward_list>
+#include <vector>
+
+#include "gtest/gtest.h"
+#include "intrusive_forward_list.h"
+
+namespace art {
+
+struct IFLTestValue {
+  // Deliberately not explicit.
+  IFLTestValue(int v) : hook(), value(v) { }  // NOLINT(runtime/explicit)
+
+  IntrusiveForwardListHook hook;
+  int value;
+};
+
+bool operator==(const IFLTestValue& lhs, const IFLTestValue& rhs) {
+  return lhs.value == rhs.value;
+}
+
+bool operator<(const IFLTestValue& lhs, const IFLTestValue& rhs) {
+  return lhs.value < rhs.value;
+}
+
+#define ASSERT_LISTS_EQUAL(expected, value)                                   \
+  do {                                                                        \
+    ASSERT_EQ(expected.empty(), value.empty());                               \
+    ASSERT_EQ(std::distance(expected.begin(), expected.end()),                \
+              std::distance(value.begin(), value.end()));                     \
+    ASSERT_TRUE(std::equal(expected.begin(), expected.end(), value.begin())); \
+  } while (false)
+
+TEST(IntrusiveForwardList, IteratorToConstIterator) {
+  IntrusiveForwardList<IFLTestValue> ifl;
+  IntrusiveForwardList<IFLTestValue>::iterator begin = ifl.begin();
+  IntrusiveForwardList<IFLTestValue>::const_iterator cbegin = ifl.cbegin();
+  IntrusiveForwardList<IFLTestValue>::const_iterator converted_begin = begin;
+  ASSERT_TRUE(converted_begin == cbegin);
+}
+
+TEST(IntrusiveForwardList, IteratorOperators) {
+  IntrusiveForwardList<IFLTestValue> ifl;
+  ASSERT_TRUE(ifl.begin() == ifl.cbegin());
+  ASSERT_FALSE(ifl.begin() != ifl.cbegin());
+  ASSERT_TRUE(ifl.end() == ifl.cend());
+  ASSERT_FALSE(ifl.end() != ifl.cend());
+
+  ASSERT_TRUE(ifl.begin() == ifl.end());  // Empty.
+  ASSERT_FALSE(ifl.begin() != ifl.end());  // Empty.
+
+  IFLTestValue value(1);
+  ifl.insert_after(ifl.cbefore_begin(), value);
+
+  ASSERT_FALSE(ifl.begin() == ifl.end());  // Not empty.
+  ASSERT_TRUE(ifl.begin() != ifl.end());  // Not empty.
+}
+
+TEST(IntrusiveForwardList, ConstructRange) {
+  std::forward_list<int> ref({ 1, 2, 7 });
+  std::vector<IFLTestValue> storage(ref.begin(), ref.end());
+  IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+}
+
+TEST(IntrusiveForwardList, Assign) {
+  std::forward_list<int> ref1({ 2, 8, 5 });
+  std::vector<IFLTestValue> storage1(ref1.begin(), ref1.end());
+  IntrusiveForwardList<IFLTestValue> ifl;
+  ifl.assign(storage1.begin(), storage1.end());
+  ASSERT_LISTS_EQUAL(ref1, ifl);
+  std::forward_list<int> ref2({ 7, 1, 3 });
+  std::vector<IFLTestValue> storage2(ref2.begin(), ref2.end());
+  ifl.assign(storage2.begin(), storage2.end());
+  ASSERT_LISTS_EQUAL(ref2, ifl);
+}
+
+TEST(IntrusiveForwardList, PushPop) {
+  IFLTestValue value3(3);
+  IFLTestValue value7(7);
+  std::forward_list<int> ref;
+  IntrusiveForwardList<IFLTestValue> ifl;
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  ref.push_front(3);
+  ifl.push_front(value3);
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  ASSERT_EQ(3, ifl.front());
+  ref.push_front(7);
+  ifl.push_front(value7);
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  ASSERT_EQ(7, ifl.front());
+  ref.pop_front();
+  ifl.pop_front();
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  ASSERT_EQ(3, ifl.front());
+  ref.pop_front();
+  ifl.pop_front();
+  ASSERT_LISTS_EQUAL(ref, ifl);
+}
+
+TEST(IntrusiveForwardList, InsertAfter1) {
+  IFLTestValue value4(4);
+  IFLTestValue value8(8);
+  IFLTestValue value5(5);
+  IFLTestValue value3(3);
+  std::forward_list<int> ref;
+  IntrusiveForwardList<IFLTestValue> ifl;
+
+  auto ref_it = ref.insert_after(ref.before_begin(), 4);
+  auto ifl_it = ifl.insert_after(ifl.before_begin(), value4);
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  ASSERT_EQ(*ref_it, *ifl_it);
+  CHECK(ref_it == ref.begin());
+  ASSERT_TRUE(ifl_it == ifl.begin());
+
+  ref_it = ref.insert_after(ref.begin(), 8);
+  ifl_it = ifl.insert_after(ifl.begin(), value8);
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  ASSERT_EQ(*ref_it, *ifl_it);
+  CHECK(ref_it != ref.end());
+  ASSERT_TRUE(ifl_it != ifl.end());
+  CHECK(++ref_it == ref.end());
+  ASSERT_TRUE(++ifl_it == ifl.end());
+
+  ref_it = ref.insert_after(ref.begin(), 5);
+  ifl_it = ifl.insert_after(ifl.begin(), value5);
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  ASSERT_EQ(*ref_it, *ifl_it);
+
+  ref_it = ref.insert_after(ref_it, 3);
+  ifl_it = ifl.insert_after(ifl_it, value3);
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  ASSERT_EQ(*ref_it, *ifl_it);
+}
+
+TEST(IntrusiveForwardList, InsertAfter2) {
+  std::forward_list<int> ref;
+  IntrusiveForwardList<IFLTestValue> ifl;
+
+  auto ref_it = ref.insert_after(ref.before_begin(), { 2, 8, 5 });
+  std::vector<IFLTestValue> storage1({ { 2 }, { 8 }, { 5 } });
+  auto ifl_it = ifl.insert_after(ifl.before_begin(), storage1.begin(), storage1.end());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  ASSERT_EQ(*ref_it, *ifl_it);
+
+  std::vector<IFLTestValue> storage2({ { 7 }, { 2 } });
+  ref_it = ref.insert_after(ref.begin(), { 7, 2 });
+  ifl_it = ifl.insert_after(ifl.begin(), storage2.begin(), storage2.end());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  ASSERT_EQ(*ref_it, *ifl_it);
+
+  std::vector<IFLTestValue> storage3({ { 1 }, { 3 }, { 4 }, { 9 } });
+  ref_it = ref.begin();
+  ifl_it = ifl.begin();
+  std::advance(ref_it, std::distance(ref.begin(), ref.end()) - 1);
+  std::advance(ifl_it, std::distance(ifl.begin(), ifl.end()) - 1);
+  ref_it = ref.insert_after(ref_it, { 1, 3, 4, 9 });
+  ifl_it = ifl.insert_after(ifl_it, storage3.begin(), storage3.end());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+}
+
+TEST(IntrusiveForwardList, EraseAfter1) {
+  std::forward_list<int> ref({ 1, 2, 7, 4, 5 });
+  std::vector<IFLTestValue> storage(ref.begin(), ref.end());
+  IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  CHECK_EQ(std::distance(ref.begin(), ref.end()), 5);
+
+  auto ref_it = ref.begin();
+  auto ifl_it = ifl.begin();
+  std::advance(ref_it, 2);
+  std::advance(ifl_it, 2);
+  ref_it = ref.erase_after(ref_it);
+  ifl_it = ifl.erase_after(ifl_it);
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  CHECK_EQ(std::distance(ref.begin(), ref.end()), 4);
+  CHECK(ref_it != ref.end());
+  ASSERT_TRUE(ifl_it != ifl.end());
+  CHECK(++ref_it == ref.end());
+  ASSERT_TRUE(++ifl_it == ifl.end());
+
+  ref_it = ref.begin();
+  ifl_it = ifl.begin();
+  std::advance(ref_it, 2);
+  std::advance(ifl_it, 2);
+  ref_it = ref.erase_after(ref_it);
+  ifl_it = ifl.erase_after(ifl_it);
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  CHECK_EQ(std::distance(ref.begin(), ref.end()), 3);
+  CHECK(ref_it == ref.end());
+  ASSERT_TRUE(ifl_it == ifl.end());
+
+  ref_it = ref.erase_after(ref.begin());
+  ifl_it = ifl.erase_after(ifl.begin());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  CHECK_EQ(std::distance(ref.begin(), ref.end()), 2);
+  CHECK(ref_it != ref.end());
+  ASSERT_TRUE(ifl_it != ifl.end());
+  CHECK(++ref_it == ref.end());
+  ASSERT_TRUE(++ifl_it == ifl.end());
+
+  ref_it = ref.erase_after(ref.before_begin());
+  ifl_it = ifl.erase_after(ifl.before_begin());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  CHECK_EQ(std::distance(ref.begin(), ref.end()), 1);
+  CHECK(ref_it == ref.begin());
+  ASSERT_TRUE(ifl_it == ifl.begin());
+
+  ref_it = ref.erase_after(ref.before_begin());
+  ifl_it = ifl.erase_after(ifl.before_begin());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  CHECK_EQ(std::distance(ref.begin(), ref.end()), 0);
+  CHECK(ref_it == ref.begin());
+  ASSERT_TRUE(ifl_it == ifl.begin());
+}
+
+TEST(IntrusiveForwardList, EraseAfter2) {
+  std::forward_list<int> ref({ 1, 2, 7, 4, 5, 3, 2, 8, 9 });
+  std::vector<IFLTestValue> storage(ref.begin(), ref.end());
+  IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  CHECK_EQ(std::distance(ref.begin(), ref.end()), 9);
+
+  auto ref_it = ref.begin();
+  auto ifl_it = ifl.begin();
+  std::advance(ref_it, 3);
+  std::advance(ifl_it, 3);
+  ref_it = ref.erase_after(ref.begin(), ref_it);
+  ifl_it = ifl.erase_after(ifl.begin(), ifl_it);
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  ASSERT_EQ(std::distance(ref.begin(), ref_it), std::distance(ifl.begin(), ifl_it));
+  CHECK_EQ(std::distance(ref.begin(), ref.end()), 7);
+
+  ref_it = ref.erase_after(ref_it, ref.end());
+  ifl_it = ifl.erase_after(ifl_it, ifl.end());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  CHECK(ref_it == ref.end());
+  ASSERT_TRUE(ifl_it == ifl.end());
+  CHECK_EQ(std::distance(ref.begin(), ref.end()), 2);
+
+  ref_it = ref.erase_after(ref.before_begin(), ref.end());
+  ifl_it = ifl.erase_after(ifl.before_begin(), ifl.end());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  CHECK(ref_it == ref.end());
+  ASSERT_TRUE(ifl_it == ifl.end());
+  CHECK_EQ(std::distance(ref.begin(), ref.end()), 0);
+}
+
+TEST(IntrusiveForwardList, SwapClear) {
+  std::forward_list<int> ref1({ 1, 2, 7 });
+  std::vector<IFLTestValue> storage1(ref1.begin(), ref1.end());
+  IntrusiveForwardList<IFLTestValue> ifl1(storage1.begin(), storage1.end());
+  std::forward_list<int> ref2({ 3, 8, 6 });
+  std::vector<IFLTestValue> storage2(ref2.begin(), ref2.end());
+  IntrusiveForwardList<IFLTestValue> ifl2(storage2.begin(), storage2.end());
+  ASSERT_LISTS_EQUAL(ref1, ifl1);
+  ASSERT_LISTS_EQUAL(ref2, ifl2);
+  ref1.swap(ref2);
+  ifl1.swap(ifl2);
+  ASSERT_LISTS_EQUAL(ref1, ifl1);
+  ASSERT_LISTS_EQUAL(ref2, ifl2);
+  ref1.clear();
+  ifl1.clear();
+  ASSERT_LISTS_EQUAL(ref1, ifl1);
+  ASSERT_LISTS_EQUAL(ref2, ifl2);
+  swap(ref1, ref2);
+  swap(ifl1, ifl2);
+  ASSERT_LISTS_EQUAL(ref1, ifl1);
+  ASSERT_LISTS_EQUAL(ref2, ifl2);
+  ref1.clear();
+  ifl1.clear();
+  ASSERT_LISTS_EQUAL(ref1, ifl1);
+  ASSERT_LISTS_EQUAL(ref2, ifl2);
+}
+
+TEST(IntrusiveForwardList, SpliceAfter) {
+  std::forward_list<int> ref1({ 3, 1, 2, 7, 4, 5, 4, 8, 7 });
+  std::forward_list<int> ref2;
+  std::vector<IFLTestValue> storage(ref1.begin(), ref1.end());
+  IntrusiveForwardList<IFLTestValue> ifl1(storage.begin(), storage.end());
+  IntrusiveForwardList<IFLTestValue> ifl2;
+  ASSERT_LISTS_EQUAL(ref1, ifl1);
+  ASSERT_LISTS_EQUAL(ref2, ifl2);
+
+  // Move everything to ref2/ifl2.
+  ref2.splice_after(ref2.before_begin(), ref1);
+  ifl2.splice_after(ifl2.before_begin(), ifl1);
+  ASSERT_LISTS_EQUAL(ref1, ifl1);
+  ASSERT_LISTS_EQUAL(ref2, ifl2);
+
+  // Move first element (3) to ref1/ifl1.
+  ref1.splice_after(ref1.before_begin(), ref2, ref2.before_begin());
+  ifl1.splice_after(ifl1.before_begin(), ifl2, ifl2.before_begin());
+  ASSERT_LISTS_EQUAL(ref1, ifl1);
+  ASSERT_LISTS_EQUAL(ref2, ifl2);
+
+  // Move second element (2) to ref1/ifl1 after the first element (3).
+  ref1.splice_after(ref1.begin(), ref2, ref2.begin());
+  ifl1.splice_after(ifl1.begin(), ifl2, ifl2.begin());
+  ASSERT_LISTS_EQUAL(ref1, ifl1);
+  ASSERT_LISTS_EQUAL(ref2, ifl2);
+
+  // Move everything from ref2/ifl2 between the 2 elements now in ref1/ifl1.
+  ref1.splice_after(ref1.begin(), ref2);
+  ifl1.splice_after(ifl1.begin(), ifl2);
+  ASSERT_LISTS_EQUAL(ref1, ifl1);
+  ASSERT_LISTS_EQUAL(ref2, ifl2);
+
+  std::forward_list<int> check({ 3, 1, 7, 4, 5, 4, 8, 7, 2 });
+  ASSERT_LISTS_EQUAL(check, ifl1);
+  ASSERT_TRUE(ifl2.empty());
+
+  // Empty splice_after().
+  ref2.splice_after(
+      ref2.before_begin(), ref1, ref1.before_begin(), ref1.begin());
+  ifl2.splice_after(ifl2.before_begin(), ifl1, ifl1.before_begin(), ifl1.begin());
+  ASSERT_LISTS_EQUAL(ref1, ifl1);
+  ASSERT_LISTS_EQUAL(ref2, ifl2);
+
+  // Move { 1, 7 } to ref2/ifl2.
+  auto ref_it = ref1.begin();
+  auto ifl_it = ifl1.begin();
+  std::advance(ref_it, 3);
+  std::advance(ifl_it, 3);
+  ref2.splice_after(ref2.before_begin(), ref1, ref1.begin(), ref_it);
+  ifl2.splice_after(ifl2.before_begin(), ifl1, ifl1.begin(), ifl_it);
+  ASSERT_LISTS_EQUAL(ref1, ifl1);
+  ASSERT_LISTS_EQUAL(ref2, ifl2);
+
+  // Move { 8, 7, 2 } to the beginning of ref1/ifl1.
+  ref_it = ref1.begin();
+  ifl_it = ifl1.begin();
+  std::advance(ref_it, 3);
+  std::advance(ifl_it, 3);
+  ref1.splice_after(ref1.before_begin(), ref1, ref_it, ref1.end());
+  ifl1.splice_after(ifl1.before_begin(), ifl1, ifl_it, ifl1.end());
+  ASSERT_LISTS_EQUAL(ref1, ifl1);
+
+  check.assign({ 8, 7, 2, 3, 4, 5, 4 });
+  ASSERT_LISTS_EQUAL(check, ifl1);
+  check.assign({ 1, 7 });
+  ASSERT_LISTS_EQUAL(check, ifl2);
+
+  // Move all but the first element to ref2/ifl2.
+  ref_it = ref2.begin();
+  ifl_it = ifl2.begin();
+  std::advance(ref_it, 1);
+  std::advance(ifl_it, 1);
+  ref2.splice_after(ref_it, ref1, ref1.begin(), ref1.end());
+  ifl2.splice_after(ifl_it, ifl1, ifl1.begin(), ifl1.end());
+  ASSERT_LISTS_EQUAL(ref1, ifl1);
+  ASSERT_LISTS_EQUAL(ref2, ifl2);
+
+  check.assign({8});
+  ASSERT_LISTS_EQUAL(check, ifl1);
+  check.assign({ 1, 7, 7, 2, 3, 4, 5, 4 });
+  ASSERT_LISTS_EQUAL(check, ifl2);
+}
+
+TEST(IntrusiveForwardList, Remove) {
+  std::forward_list<int> ref({ 3, 1, 2, 7, 4, 5, 4, 8, 7 });
+  std::vector<IFLTestValue> storage(ref.begin(), ref.end());
+  IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  ref.remove(1);
+  ifl.remove(1);
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  ref.remove(4);
+  ifl.remove(4);
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  auto odd = [](IFLTestValue value) { return (value.value & 1) != 0; };  // NOLINT(readability/braces)
+  ref.remove_if(odd);
+  ifl.remove_if(odd);
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  auto all = [](IFLTestValue value ATTRIBUTE_UNUSED) { return true; };  // NOLINT(readability/braces)
+  ref.remove_if(all);
+  ifl.remove_if(all);
+  ASSERT_LISTS_EQUAL(ref, ifl);
+}
+
+TEST(IntrusiveForwardList, Unique) {
+  std::forward_list<int> ref({ 3, 1, 1, 2, 3, 3, 7, 7, 4, 4, 5, 7 });
+  std::vector<IFLTestValue> storage(ref.begin(), ref.end());
+  IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  ref.unique();
+  ifl.unique();
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  std::forward_list<int> check({ 3, 1, 2, 3, 7, 4, 5, 7 });
+  ASSERT_LISTS_EQUAL(check, ifl);
+
+  auto bin_pred = [](IFLTestValue lhs, IFLTestValue rhs) {
+    return (lhs.value & ~1) == (rhs.value & ~1);
+  };
+  ref.unique(bin_pred);
+  ifl.unique(bin_pred);
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  check.assign({ 3, 1, 2, 7, 4, 7 });
+  ASSERT_LISTS_EQUAL(check, ifl);
+}
+
+TEST(IntrusiveForwardList, Merge) {
+  std::forward_list<int> ref1({ 1, 4, 8, 8, 12 });
+  std::vector<IFLTestValue> storage1(ref1.begin(), ref1.end());
+  IntrusiveForwardList<IFLTestValue> ifl1(storage1.begin(), storage1.end());
+  std::forward_list<int> ref2({ 3, 5, 6, 7, 9 });
+  std::vector<IFLTestValue> storage2(ref2.begin(), ref2.end());
+  IntrusiveForwardList<IFLTestValue> ifl2(storage2.begin(), storage2.end());
+  ASSERT_LISTS_EQUAL(ref1, ifl1);
+  ASSERT_LISTS_EQUAL(ref2, ifl2);
+  CHECK(std::is_sorted(ref1.begin(), ref1.end()));
+  CHECK(std::is_sorted(ref2.begin(), ref2.end()));
+  ref1.merge(ref2);
+  ifl1.merge(ifl2);
+  ASSERT_LISTS_EQUAL(ref1, ifl1);
+  ASSERT_LISTS_EQUAL(ref2, ifl2);
+  CHECK(ref2.empty());
+  std::forward_list<int> check({ 1, 3, 4, 5, 6, 7, 8, 8, 9, 12 });
+  ASSERT_LISTS_EQUAL(check, ifl1);
+}
+
+TEST(IntrusiveForwardList, Sort1) {
+  std::forward_list<int> ref({ 2, 9, 8, 3, 7, 4, 1, 5, 3, 0 });
+  std::vector<IFLTestValue> storage(ref.begin(), ref.end());
+  IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  CHECK(!std::is_sorted(ref.begin(), ref.end()));
+  ref.sort();
+  ifl.sort();
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  std::forward_list<int> check({ 0, 1, 2, 3, 3, 4, 5, 7, 8, 9 });
+  ASSERT_LISTS_EQUAL(check, ifl);
+}
+
+TEST(IntrusiveForwardList, Sort2) {
+  std::forward_list<int> ref({ 2, 9, 8, 3, 7, 4, 1, 5, 3, 0 });
+  std::vector<IFLTestValue> storage(ref.begin(), ref.end());
+  IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  auto cmp = [](IFLTestValue lhs, IFLTestValue rhs) {
+    return (lhs.value & ~1) < (rhs.value & ~1);
+  };
+  CHECK(!std::is_sorted(ref.begin(), ref.end(), cmp));
+  ref.sort(cmp);
+  ifl.sort(cmp);
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  std::forward_list<int> check({ 1, 0, 2, 3, 3, 4, 5, 7, 9, 8 });
+  ASSERT_LISTS_EQUAL(check, ifl);
+}
+
+TEST(IntrusiveForwardList, Reverse) {
+  std::forward_list<int> ref({ 8, 3, 5, 4, 1, 3 });
+  std::vector<IFLTestValue> storage(ref.begin(), ref.end());
+  IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  CHECK(!std::is_sorted(ref.begin(), ref.end()));
+  ref.reverse();
+  ifl.reverse();
+  ASSERT_LISTS_EQUAL(ref, ifl);
+  std::forward_list<int> check({ 3, 1, 4, 5, 3, 8 });
+  ASSERT_LISTS_EQUAL(check, ifl);
+}
+
+}  // namespace art