Use IntrusiveForwardList<> for Env-/UsePosition.

Test: m test-art-host-gtest
Test: testrunner.py --host
Change-Id: I2b720e2ed8f96303cf80e9daa6d5278bf0c3da2f
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 02816cf..7dcf244 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -34,6 +34,7 @@
 #include "register_allocator_linear_scan.h"
 #include "ssa_liveness_analysis.h"
 #include "utils/assembler.h"
+#include "utils/intrusive_forward_list.h"
 
 namespace art {
 
@@ -66,6 +67,13 @@
       current->Dump(NewEntryStream());
     }
   }
+  // Construct StringList from a list of elements. The value type must provide method `Dump`.
+  template <typename Container>
+  explicit StringList(const Container& list, Format format = kArrayBrackets) : StringList(format) {
+    for (const typename Container::value_type& current : list) {
+      current.Dump(NewEntryStream());
+    }
+  }
 
   std::ostream& NewEntryStream() {
     if (is_empty_) {
@@ -584,8 +592,8 @@
         LiveInterval* interval = instruction->GetLiveInterval();
         StartAttributeStream("ranges")
             << StringList(interval->GetFirstRange(), StringList::kSetBrackets);
-        StartAttributeStream("uses") << StringList(interval->GetFirstUse());
-        StartAttributeStream("env_uses") << StringList(interval->GetFirstEnvironmentUse());
+        StartAttributeStream("uses") << StringList(interval->GetUses());
+        StartAttributeStream("env_uses") << StringList(interval->GetEnvironmentUses());
         StartAttributeStream("is_fixed") << interval->IsFixed();
         StartAttributeStream("is_split") << interval->IsSplit();
         StartAttributeStream("is_low") << interval->IsLowInterval();
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 4d96fbe..85e37ca 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1485,7 +1485,8 @@
   H##type* As##type() { return this; }
 
 template <typename T>
-class HUseListNode : public ArenaObject<kArenaAllocUseListNode> {
+class HUseListNode : public ArenaObject<kArenaAllocUseListNode>,
+                     public IntrusiveForwardListNode<HUseListNode<T>> {
  public:
   // Get the instruction which has this use as one of the inputs.
   T GetUser() const { return user_; }
@@ -1494,10 +1495,6 @@
   // Set the position of the input record that this use corresponds to.
   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) {}
diff --git a/compiler/optimizing/register_allocation_resolver.cc b/compiler/optimizing/register_allocation_resolver.cc
index c6a0b6a..ce3a496 100644
--- a/compiler/optimizing/register_allocation_resolver.cc
+++ b/compiler/optimizing/register_allocation_resolver.cc
@@ -308,8 +308,10 @@
     }
     InsertMoveAfter(interval->GetDefinedBy(), interval->ToLocation(), loc);
   }
-  UsePosition* use = current->GetFirstUse();
-  EnvUsePosition* env_use = current->GetFirstEnvironmentUse();
+  UsePositionList::const_iterator use_it = current->GetUses().begin();
+  const UsePositionList::const_iterator use_end = current->GetUses().end();
+  EnvUsePositionList::const_iterator env_use_it = current->GetEnvironmentUses().begin();
+  const EnvUsePositionList::const_iterator env_use_end = current->GetEnvironmentUses().end();
 
   // Walk over all siblings, updating locations of use positions, and
   // connecting them when they are adjacent.
@@ -321,43 +323,47 @@
 
     LiveRange* range = current->GetFirstRange();
     while (range != nullptr) {
-      while (use != nullptr && use->GetPosition() < range->GetStart()) {
-        DCHECK(use->IsSynthesized());
-        use = use->GetNext();
-      }
-      while (use != nullptr && use->GetPosition() <= range->GetEnd()) {
-        DCHECK(current->CoversSlow(use->GetPosition()) || (use->GetPosition() == range->GetEnd()));
-        if (!use->IsSynthesized()) {
-          LocationSummary* locations = use->GetUser()->GetLocations();
-          Location expected_location = locations->InAt(use->GetInputIndex());
+      // Process uses in the closed interval [range->GetStart(), range->GetEnd()].
+      // FindMatchingUseRange() expects a half-open interval, so pass `range->GetEnd() + 1u`.
+      size_t range_begin = range->GetStart();
+      size_t range_end = range->GetEnd() + 1u;
+      auto matching_use_range =
+          FindMatchingUseRange(use_it, use_end, range_begin, range_end);
+      DCHECK(std::all_of(use_it,
+                         matching_use_range.begin(),
+                         [](const UsePosition& pos) { return pos.IsSynthesized(); }));
+      for (const UsePosition& use : matching_use_range) {
+        DCHECK(current->CoversSlow(use.GetPosition()) || (use.GetPosition() == range->GetEnd()));
+        if (!use.IsSynthesized()) {
+          LocationSummary* locations = use.GetUser()->GetLocations();
+          Location expected_location = locations->InAt(use.GetInputIndex());
           // The expected (actual) location may be invalid in case the input is unused. Currently
           // this only happens for intrinsics.
           if (expected_location.IsValid()) {
             if (expected_location.IsUnallocated()) {
-              locations->SetInAt(use->GetInputIndex(), source);
+              locations->SetInAt(use.GetInputIndex(), source);
             } else if (!expected_location.IsConstant()) {
-              AddInputMoveFor(interval->GetDefinedBy(), use->GetUser(), source, expected_location);
+              AddInputMoveFor(
+                  interval->GetDefinedBy(), use.GetUser(), source, expected_location);
             }
           } else {
-            DCHECK(use->GetUser()->IsInvoke());
-            DCHECK(use->GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone);
+            DCHECK(use.GetUser()->IsInvoke());
+            DCHECK(use.GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone);
           }
         }
-        use = use->GetNext();
       }
+      use_it = matching_use_range.end();
 
       // Walk over the environment uses, and update their locations.
-      while (env_use != nullptr && env_use->GetPosition() < range->GetStart()) {
-        env_use = env_use->GetNext();
+      auto matching_env_use_range =
+          FindMatchingUseRange(env_use_it, env_use_end, range_begin, range_end);
+      for (const EnvUsePosition& env_use : matching_env_use_range) {
+        DCHECK(current->CoversSlow(env_use.GetPosition())
+               || (env_use.GetPosition() == range->GetEnd()));
+        HEnvironment* environment = env_use.GetEnvironment();
+        environment->SetLocationAt(env_use.GetInputIndex(), source);
       }
-
-      while (env_use != nullptr && env_use->GetPosition() <= range->GetEnd()) {
-        DCHECK(current->CoversSlow(env_use->GetPosition())
-               || (env_use->GetPosition() == range->GetEnd()));
-        HEnvironment* environment = env_use->GetEnvironment();
-        environment->SetLocationAt(env_use->GetInputIndex(), source);
-        env_use = env_use->GetNext();
-      }
+      env_use_it = matching_env_use_range.end();
 
       range = range->GetNext();
     }
@@ -395,13 +401,8 @@
     current = next_sibling;
   } while (current != nullptr);
 
-  if (kIsDebugBuild) {
-    // Following uses can only be synthesized uses.
-    while (use != nullptr) {
-      DCHECK(use->IsSynthesized());
-      use = use->GetNext();
-    }
-  }
+  // Following uses can only be synthesized uses.
+  DCHECK(std::all_of(use_it, use_end, [](const UsePosition& pos) { return pos.IsSynthesized(); }));
 }
 
 static bool IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(
diff --git a/compiler/optimizing/register_allocator_graph_color.cc b/compiler/optimizing/register_allocator_graph_color.cc
index 300f4c6..090ba31 100644
--- a/compiler/optimizing/register_allocator_graph_color.cc
+++ b/compiler/optimizing/register_allocator_graph_color.cc
@@ -178,18 +178,17 @@
     use_weight += CostForMoveAt(interval->GetStart() + 1, liveness);
   }
 
-  UsePosition* use = interval->GetFirstUse();
-  while (use != nullptr && use->GetPosition() <= interval->GetStart()) {
-    // Skip uses before the start of this live interval.
-    use = use->GetNext();
-  }
-
-  while (use != nullptr && use->GetPosition() <= interval->GetEnd()) {
-    if (use->GetUser() != nullptr && use->RequiresRegister()) {
+  // Process uses in the range (interval->GetStart(), interval->GetEnd()], i.e.
+  // [interval->GetStart() + 1, interval->GetEnd() + 1)
+  auto matching_use_range = FindMatchingUseRange(interval->GetUses().begin(),
+                                                 interval->GetUses().end(),
+                                                 interval->GetStart() + 1u,
+                                                 interval->GetEnd() + 1u);
+  for (const UsePosition& use : matching_use_range) {
+    if (use.GetUser() != nullptr && use.RequiresRegister()) {
       // Cost for spilling at a register use point.
-      use_weight += CostForMoveAt(use->GetUser()->GetLifetimePosition() - 1, liveness);
+      use_weight += CostForMoveAt(use.GetUser()->GetLifetimePosition() - 1, liveness);
     }
-    use = use->GetNext();
   }
 
   // We divide by the length of the interval because we want to prioritize
@@ -989,16 +988,16 @@
     interval = TrySplit(interval, interval->GetStart() + 1);
   }
 
-  UsePosition* use = interval->GetFirstUse();
-  while (use != nullptr && use->GetPosition() < interval->GetStart()) {
-    use = use->GetNext();
-  }
-
+  // Process uses in the range [interval->GetStart(), interval->GetEnd()], i.e.
+  // [interval->GetStart(), interval->GetEnd() + 1)
+  auto matching_use_range = FindMatchingUseRange(interval->GetUses().begin(),
+                                                 interval->GetUses().end(),
+                                                 interval->GetStart(),
+                                                 interval->GetEnd() + 1u);
   // Split around register uses.
-  size_t end = interval->GetEnd();
-  while (use != nullptr && use->GetPosition() <= end) {
-    if (use->RequiresRegister()) {
-      size_t position = use->GetPosition();
+  for (const UsePosition& use : matching_use_range) {
+    if (use.RequiresRegister()) {
+      size_t position = use.GetPosition();
       interval = TrySplit(interval, position - 1);
       if (liveness_.GetInstructionFromPosition(position / 2)->IsControlFlow()) {
         // If we are at the very end of a basic block, we cannot split right
@@ -1008,7 +1007,6 @@
         interval = TrySplit(interval, position);
       }
     }
-    use = use->GetNext();
   }
 }
 
@@ -1398,18 +1396,20 @@
     }
 
     // Try to prevent moves into fixed input locations.
-    UsePosition* use = interval->GetFirstUse();
-    for (; use != nullptr && use->GetPosition() <= interval->GetStart(); use = use->GetNext()) {
-      // Skip past uses before the start of this interval.
-    }
-    for (; use != nullptr && use->GetPosition() <= interval->GetEnd(); use = use->GetNext()) {
-      HInstruction* user = use->GetUser();
+    // Process uses in the range (interval->GetStart(), interval->GetEnd()], i.e.
+    // [interval->GetStart() + 1, interval->GetEnd() + 1)
+    auto matching_use_range = FindMatchingUseRange(interval->GetUses().begin(),
+                                                   interval->GetUses().end(),
+                                                   interval->GetStart() + 1u,
+                                                   interval->GetEnd() + 1u);
+    for (const UsePosition& use : matching_use_range) {
+      HInstruction* user = use.GetUser();
       if (user == nullptr) {
         // User may be null for certain intervals, such as temp intervals.
         continue;
       }
       LocationSummary* locations = user->GetLocations();
-      Location input = locations->InAt(use->GetInputIndex());
+      Location input = locations->InAt(use.GetInputIndex());
       if (input.IsRegister() || input.IsFpuRegister()) {
         // TODO: Could try to handle pair interval too, but coalescing with fixed pair nodes
         //       is currently not supported.
diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc
index 667afb1..24a2ab2 100644
--- a/compiler/optimizing/register_allocator_test.cc
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -912,9 +912,9 @@
   // Create an interval with lifetime holes.
   static constexpr size_t ranges1[][2] = {{0, 2}, {4, 6}, {8, 10}};
   LiveInterval* first = BuildInterval(ranges1, arraysize(ranges1), &allocator, -1, one);
-  first->first_use_ = new(&allocator) UsePosition(user, false, 8, first->first_use_);
-  first->first_use_ = new(&allocator) UsePosition(user, false, 7, first->first_use_);
-  first->first_use_ = new(&allocator) UsePosition(user, false, 6, first->first_use_);
+  first->uses_.push_front(*new(&allocator) UsePosition(user, false, 8));
+  first->uses_.push_front(*new(&allocator) UsePosition(user, false, 7));
+  first->uses_.push_front(*new(&allocator) UsePosition(user, false, 6));
 
   locations = new (&allocator) LocationSummary(first->GetDefinedBy(), LocationSummary::kNoCall);
   locations->SetOut(Location::RequiresRegister());
@@ -934,9 +934,9 @@
   // before lifetime position 6 yet.
   static constexpr size_t ranges3[][2] = {{2, 4}, {8, 10}};
   LiveInterval* third = BuildInterval(ranges3, arraysize(ranges3), &allocator, -1, three);
-  third->first_use_ = new(&allocator) UsePosition(user, false, 8, third->first_use_);
-  third->first_use_ = new(&allocator) UsePosition(user, false, 4, third->first_use_);
-  third->first_use_ = new(&allocator) UsePosition(user, false, 3, third->first_use_);
+  third->uses_.push_front(*new(&allocator) UsePosition(user, false, 8));
+  third->uses_.push_front(*new(&allocator) UsePosition(user, false, 4));
+  third->uses_.push_front(*new(&allocator) UsePosition(user, false, 3));
   locations = new (&allocator) LocationSummary(third->GetDefinedBy(), LocationSummary::kNoCall);
   locations->SetOut(Location::RequiresRegister());
   third = third->SplitAt(3);
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index b538a89..7b7495b 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -356,14 +356,16 @@
     }
   }
 
-  UsePosition* use = first_use_;
   size_t start = GetStart();
   size_t end = GetEnd();
-  while (use != nullptr && use->GetPosition() <= end) {
-    size_t use_position = use->GetPosition();
-    if (use_position >= start && !use->IsSynthesized()) {
-      HInstruction* user = use->GetUser();
-      size_t input_index = use->GetInputIndex();
+  for (const UsePosition& use : GetUses()) {
+    size_t use_position = use.GetPosition();
+    if (use_position > end) {
+      break;
+    }
+    if (use_position >= start && !use.IsSynthesized()) {
+      HInstruction* user = use.GetUser();
+      size_t input_index = use.GetInputIndex();
       if (user->IsPhi()) {
         // If the phi has a register, try to use the same.
         Location phi_location = user->GetLiveInterval()->ToLocation();
@@ -395,7 +397,7 @@
       } else {
         // If the instruction is expected in a register, try to use it.
         LocationSummary* locations = user->GetLocations();
-        Location expected = locations->InAt(use->GetInputIndex());
+        Location expected = locations->InAt(use.GetInputIndex());
         // We use the user's lifetime position - 1 (and not `use_position`) because the
         // register is blocked at the beginning of the user.
         size_t position = user->GetLifetimePosition() - 1;
@@ -408,7 +410,6 @@
         }
       }
     }
-    use = use->GetNext();
   }
 
   return kNoRegister;
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index e9dffc1..a668157 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -19,7 +19,9 @@
 
 #include <iostream>
 
+#include "base/iteration_range.h"
 #include "nodes.h"
+#include "utils/intrusive_forward_list.h"
 
 namespace art {
 
@@ -102,28 +104,23 @@
 /**
  * A use position represents a live interval use at a given position.
  */
-class UsePosition : public ArenaObject<kArenaAllocSsaLiveness> {
+class UsePosition : public ArenaObject<kArenaAllocSsaLiveness>,
+                    public IntrusiveForwardListNode<UsePosition> {
  public:
-  UsePosition(HInstruction* user, size_t input_index, size_t position, UsePosition* next)
+  UsePosition(HInstruction* user, size_t input_index, size_t position)
       : user_(user),
         input_index_(input_index),
-        position_(position),
-        next_(next) {
-    DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition());
+        position_(position) {
   }
 
   explicit UsePosition(size_t position)
       : user_(nullptr),
         input_index_(kNoInput),
-        position_(dchecked_integral_cast<uint32_t>(position)),
-        next_(nullptr) {
+        position_(dchecked_integral_cast<uint32_t>(position)) {
   }
 
   size_t GetPosition() const { return position_; }
 
-  UsePosition* GetNext() const { return next_; }
-  void SetNext(UsePosition* next) { next_ = next; }
-
   HInstruction* GetUser() const { return user_; }
 
   bool IsSynthesized() const { return user_ == nullptr; }
@@ -138,10 +135,8 @@
     return user_->GetBlock()->GetLoopInformation();
   }
 
-  UsePosition* Dup(ArenaAllocator* allocator) const {
-    return new (allocator) UsePosition(
-        user_, input_index_, position_,
-        next_ == nullptr ? nullptr : next_->Dup(allocator));
+  UsePosition* Clone(ArenaAllocator* allocator) const {
+    return new (allocator) UsePosition(user_, input_index_, position_);
   }
 
   bool RequiresRegister() const {
@@ -156,33 +151,28 @@
   HInstruction* const user_;
   const size_t input_index_;
   const size_t position_;
-  UsePosition* next_;
 
   DISALLOW_COPY_AND_ASSIGN(UsePosition);
 };
+using UsePositionList = IntrusiveForwardList<UsePosition>;
 
 /**
  * An environment use position represents a live interval for environment use at a given position.
  */
-class EnvUsePosition : public ArenaObject<kArenaAllocSsaLiveness> {
+class EnvUsePosition : public ArenaObject<kArenaAllocSsaLiveness>,
+                       public IntrusiveForwardListNode<EnvUsePosition> {
  public:
   EnvUsePosition(HEnvironment* environment,
                  size_t input_index,
-                 size_t position,
-                 EnvUsePosition* next)
+                 size_t position)
       : environment_(environment),
         input_index_(input_index),
-        position_(position),
-        next_(next) {
+        position_(position) {
     DCHECK(environment != nullptr);
-    DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition());
   }
 
   size_t GetPosition() const { return position_; }
 
-  EnvUsePosition* GetNext() const { return next_; }
-  void SetNext(EnvUsePosition* next) { next_ = next; }
-
   HEnvironment* GetEnvironment() const { return environment_; }
   size_t GetInputIndex() const { return input_index_; }
 
@@ -190,20 +180,47 @@
     stream << position_;
   }
 
-  EnvUsePosition* Dup(ArenaAllocator* allocator) const {
-    return new (allocator) EnvUsePosition(
-        environment_, input_index_, position_,
-        next_ == nullptr ? nullptr : next_->Dup(allocator));
+  EnvUsePosition* Clone(ArenaAllocator* allocator) const {
+    return new (allocator) EnvUsePosition(environment_, input_index_, position_);
   }
 
  private:
   HEnvironment* const environment_;
   const size_t input_index_;
   const size_t position_;
-  EnvUsePosition* next_;
 
   DISALLOW_COPY_AND_ASSIGN(EnvUsePosition);
 };
+using EnvUsePositionList = IntrusiveForwardList<EnvUsePosition>;
+
+template <typename Iterator>
+inline Iterator FindUseAtOrAfterPosition(Iterator first, Iterator last, size_t position) {
+  using value_type = const typename Iterator::value_type;
+  static_assert(std::is_same<value_type, const UsePosition>::value ||
+                    std::is_same<value_type, const EnvUsePosition>::value,
+                "Expecting value type UsePosition or EnvUsePosition.");
+  Iterator ret = std::find_if(
+      first, last, [position](const value_type& use) { return use.GetPosition() >= position; });
+  // Check that the processed range is sorted. Do not check the rest of the range to avoid
+  // increasing the complexity of callers from O(n) to O(n^2).
+  DCHECK(std::is_sorted(
+      first,
+      ret,
+      [](const value_type& lhs, const value_type& rhs) {
+          return lhs.GetPosition() < rhs.GetPosition();
+      }));
+  return ret;
+}
+
+template <typename Iterator>
+inline IterationRange<Iterator> FindMatchingUseRange(Iterator first,
+                                                     Iterator last,
+                                                     size_t position_begin,
+                                                     size_t position_end) {
+  Iterator begin = FindUseAtOrAfterPosition(first, last, position_begin);
+  Iterator end = FindUseAtOrAfterPosition(begin, last, position_end);
+  return MakeIterationRange(begin, end);
+}
 
 class SafepointPosition : public ArenaObject<kArenaAllocSsaLiveness> {
  public:
@@ -265,11 +282,11 @@
 
   void AddTempUse(HInstruction* instruction, size_t temp_index) {
     DCHECK(IsTemp());
-    DCHECK(first_use_ == nullptr) << "A temporary can only have one user";
-    DCHECK(first_env_use_ == nullptr) << "A temporary cannot have environment user";
+    DCHECK(GetUses().empty()) << "A temporary can only have one user";
+    DCHECK(GetEnvironmentUses().empty()) << "A temporary cannot have environment user";
     size_t position = instruction->GetLifetimePosition();
-    first_use_ = new (allocator_) UsePosition(
-        instruction, temp_index, position, first_use_);
+    UsePosition* new_use = new (allocator_) UsePosition(instruction, temp_index, position);
+    uses_.push_front(*new_use);
     AddRange(position, position + 1);
   }
 
@@ -306,32 +323,36 @@
       AddBackEdgeUses(*instruction->GetBlock());
     }
 
-    if ((first_use_ != nullptr)
-        && (first_use_->GetUser() == actual_user)
-        && (first_use_->GetPosition() < position)) {
+    if ((!uses_.empty()) &&
+        (uses_.front().GetUser() == actual_user) &&
+        (uses_.front().GetPosition() < position)) {
       // The user uses the instruction multiple times, and one use dies before the other.
       // We update the use list so that the latter is first.
       DCHECK(!is_environment);
-      UsePosition* cursor = first_use_;
-      while ((cursor->GetNext() != nullptr) && (cursor->GetNext()->GetPosition() < position)) {
-        cursor = cursor->GetNext();
-      }
-      DCHECK(first_use_->GetPosition() + 1 == position);
-      UsePosition* new_use = new (allocator_) UsePosition(
-          instruction, input_index, position, cursor->GetNext());
-      cursor->SetNext(new_use);
-      if (first_range_->GetEnd() == first_use_->GetPosition()) {
+      DCHECK(uses_.front().GetPosition() + 1 == position);
+      UsePositionList::iterator next_pos = uses_.begin();
+      UsePositionList::iterator insert_pos;
+      do {
+        insert_pos = next_pos;
+        ++next_pos;
+      } while (next_pos != uses_.end() && next_pos->GetPosition() < position);
+      UsePosition* new_use = new (allocator_) UsePosition(instruction, input_index, position);
+      uses_.insert_after(insert_pos, *new_use);
+      if (first_range_->GetEnd() == uses_.front().GetPosition()) {
         first_range_->end_ = position;
       }
       return;
     }
 
     if (is_environment) {
-      first_env_use_ = new (allocator_) EnvUsePosition(
-          environment, input_index, position, first_env_use_);
+      DCHECK(env_uses_.empty() || position <= env_uses_.front().GetPosition());
+      EnvUsePosition* new_env_use =
+          new (allocator_) EnvUsePosition(environment, input_index, position);
+      env_uses_.push_front(*new_env_use);
     } else {
-      first_use_ = new (allocator_) UsePosition(
-          instruction, input_index, position, first_use_);
+      DCHECK(uses_.empty() || position <= uses_.front().GetPosition());
+      UsePosition* new_use = new (allocator_) UsePosition(instruction, input_index, position);
+      uses_.push_front(*new_use);
     }
 
     if (is_environment && !keep_alive) {
@@ -369,8 +390,9 @@
     if (block->IsInLoop()) {
       AddBackEdgeUses(*block);
     }
-    first_use_ = new (allocator_) UsePosition(
-        instruction, input_index, block->GetLifetimeEnd(), first_use_);
+    UsePosition* new_use =
+        new (allocator_) UsePosition(instruction, input_index, block->GetLifetimeEnd());
+    uses_.push_front(*new_use);
   }
 
   ALWAYS_INLINE void AddRange(size_t start, size_t end) {
@@ -430,7 +452,7 @@
       first_range_->start_ = from;
     } else {
       // Instruction without uses.
-      DCHECK(first_use_ == nullptr);
+      DCHECK(uses_.empty());
       DCHECK(from == defined_by_->GetLifetimePosition());
       first_range_ = last_range_ = range_search_start_ =
           new (allocator_) LiveRange(from, from + 2, nullptr);
@@ -528,16 +550,17 @@
       return position;
     }
 
-    UsePosition* use = first_use_;
     size_t end = GetEnd();
-    while (use != nullptr && use->GetPosition() <= end) {
-      size_t use_position = use->GetPosition();
+    for (const UsePosition& use : GetUses()) {
+      size_t use_position = use.GetPosition();
+      if (use_position > end) {
+        break;
+      }
       if (use_position > position) {
-        if (use->RequiresRegister()) {
+        if (use.RequiresRegister()) {
           return use_position;
         }
       }
-      use = use->GetNext();
     }
     return kNoLifetime;
   }
@@ -564,24 +587,25 @@
       return position;
     }
 
-    UsePosition* use = first_use_;
     size_t end = GetEnd();
-    while (use != nullptr && use->GetPosition() <= end) {
-      size_t use_position = use->GetPosition();
+    for (const UsePosition& use : GetUses()) {
+      size_t use_position = use.GetPosition();
+      if (use_position > end) {
+        break;
+      }
       if (use_position > position) {
         return use_position;
       }
-      use = use->GetNext();
     }
     return kNoLifetime;
   }
 
-  UsePosition* GetFirstUse() const {
-    return first_use_;
+  const UsePositionList& GetUses() const {
+    return parent_->uses_;
   }
 
-  EnvUsePosition* GetFirstEnvironmentUse() const {
-    return first_env_use_;
+  const EnvUsePositionList& GetEnvironmentUses() const {
+    return parent_->env_uses_;
   }
 
   Primitive::Type GetType() const {
@@ -645,8 +669,6 @@
     next_sibling_ = new_interval;
     new_interval->parent_ = parent_;
 
-    new_interval->first_use_ = first_use_;
-    new_interval->first_env_use_ = first_env_use_;
     LiveRange* current = first_range_;
     LiveRange* previous = nullptr;
     // Iterate over the ranges, and either find a range that covers this position, or
@@ -718,20 +740,14 @@
       current = current->GetNext();
     }
     stream << "}, uses: { ";
-    const UsePosition* use = first_use_;
-    if (use != nullptr) {
-      do {
-        use->Dump(stream);
-        stream << " ";
-      } while ((use = use->GetNext()) != nullptr);
+    for (const UsePosition& use : GetUses()) {
+      use.Dump(stream);
+      stream << " ";
     }
     stream << "}, { ";
-    const EnvUsePosition* env_use = first_env_use_;
-    if (env_use != nullptr) {
-      do {
-        env_use->Dump(stream);
-        stream << " ";
-      } while ((env_use = env_use->GetNext()) != nullptr);
+    for (const EnvUsePosition& env_use : GetEnvironmentUses()) {
+      env_use.Dump(stream);
+      stream << " ";
     }
     stream << "}";
     stream << " is_fixed: " << is_fixed_ << ", is_split: " << IsSplit();
@@ -833,12 +849,16 @@
       high_or_low_interval_->last_range_ = high_or_low_interval_->first_range_->GetLastRange();
       high_or_low_interval_->range_search_start_ = high_or_low_interval_->first_range_;
     }
-    if (first_use_ != nullptr) {
-      high_or_low_interval_->first_use_ = first_use_->Dup(allocator_);
+    auto pos = high_or_low_interval_->uses_.before_begin();
+    for (const UsePosition& use : uses_) {
+      UsePosition* new_use = use.Clone(allocator_);
+      pos = high_or_low_interval_->uses_.insert_after(pos, *new_use);
     }
 
-    if (first_env_use_ != nullptr) {
-      high_or_low_interval_->first_env_use_ = first_env_use_->Dup(allocator_);
+    auto env_pos = high_or_low_interval_->env_uses_.before_begin();
+    for (const EnvUsePosition& env_use : env_uses_) {
+      EnvUsePosition* new_env_use = env_use.Clone(allocator_);
+      env_pos = high_or_low_interval_->env_uses_.insert_after(env_pos, *new_env_use);
     }
   }
 
@@ -962,8 +982,8 @@
         range_search_start_(nullptr),
         first_safepoint_(nullptr),
         last_safepoint_(nullptr),
-        first_use_(nullptr),
-        first_env_use_(nullptr),
+        uses_(),
+        env_uses_(),
         type_(type),
         next_sibling_(nullptr),
         parent_(this),
@@ -1005,14 +1025,12 @@
   }
 
   bool HasSynthesizeUseAt(size_t position) const {
-    UsePosition* use = first_use_;
-    while (use != nullptr) {
-      size_t use_position = use->GetPosition();
-      if ((use_position == position) && use->IsSynthesized()) {
+    for (const UsePosition& use : GetUses()) {
+      size_t use_position = use.GetPosition();
+      if ((use_position == position) && use.IsSynthesized()) {
         return true;
       }
       if (use_position > position) break;
-      use = use->GetNext();
     }
     return false;
   }
@@ -1028,11 +1046,11 @@
 
     // Add synthesized uses at the back edge of loops to help the register allocator.
     // Note that this method is called in decreasing liveness order, to faciliate adding
-    // uses at the head of the `first_use_` linked list. Because below
+    // uses at the head of the `uses_` list. Because below
     // we iterate from inner-most to outer-most, which is in increasing liveness order,
-    // we need to take extra care of how the `first_use_` linked list is being updated.
-    UsePosition* first_in_new_list = nullptr;
-    UsePosition* last_in_new_list = nullptr;
+    // we need to add subsequent entries after the last inserted entry.
+    const UsePositionList::iterator old_begin = uses_.begin();
+    UsePositionList::iterator insert_pos = uses_.before_begin();
     for (HLoopInformationOutwardIterator it(block_at_use);
          !it.Done();
          it.Advance()) {
@@ -1042,37 +1060,25 @@
         break;
       }
 
-      // We're only adding a synthesized use at the last back edge. Adding syntehsized uses on
+      // We're only adding a synthesized use at the last back edge. Adding synthesized uses on
       // all back edges is not necessary: anything used in the loop will have its use at the
       // last back edge. If we want branches in a loop to have better register allocation than
       // another branch, then it is the linear order we should change.
       size_t back_edge_use_position = current->GetLifetimeEnd();
-      if ((first_use_ != nullptr) && (first_use_->GetPosition() <= back_edge_use_position)) {
+      if ((old_begin != uses_.end()) && (old_begin->GetPosition() <= back_edge_use_position)) {
         // There was a use already seen in this loop. Therefore the previous call to `AddUse`
         // already inserted the backedge use. We can stop going outward.
         DCHECK(HasSynthesizeUseAt(back_edge_use_position));
         break;
       }
 
-      DCHECK(last_in_new_list == nullptr ||
-             back_edge_use_position > last_in_new_list->GetPosition());
+      DCHECK(insert_pos != uses_.before_begin()
+             ? back_edge_use_position > insert_pos->GetPosition()
+             : current == block_at_use.GetLoopInformation())
+          << std::distance(uses_.before_begin(), insert_pos);
 
       UsePosition* new_use = new (allocator_) UsePosition(back_edge_use_position);
-
-      if (last_in_new_list != nullptr) {
-        // Going outward. The latest created use needs to point to the new use.
-        last_in_new_list->SetNext(new_use);
-      } else {
-        // This is the inner-most loop.
-        DCHECK_EQ(current, block_at_use.GetLoopInformation());
-        first_in_new_list = new_use;
-      }
-      last_in_new_list = new_use;
-    }
-    // Link the newly created linked list with `first_use_`.
-    if (last_in_new_list != nullptr) {
-      last_in_new_list->SetNext(first_use_);
-      first_use_ = first_in_new_list;
+      insert_pos = uses_.insert_after(insert_pos, *new_use);
     }
   }
 
@@ -1091,9 +1097,9 @@
   SafepointPosition* first_safepoint_;
   SafepointPosition* last_safepoint_;
 
-  // Uses of this interval. Note that this linked list is shared amongst siblings.
-  UsePosition* first_use_;
-  EnvUsePosition* first_env_use_;
+  // Uses of this interval. Only the parent interval keeps these lists.
+  UsePositionList uses_;
+  EnvUsePositionList env_uses_;
 
   // The instruction type this interval corresponds to.
   const Primitive::Type type_;
@@ -1202,14 +1208,14 @@
     // A temporary shares the same lifetime start as the instruction that requires it.
     DCHECK(temp->IsTemp());
     HInstruction* user = GetInstructionFromPosition(temp->GetStart() / 2);
-    DCHECK_EQ(user, temp->GetFirstUse()->GetUser());
+    DCHECK_EQ(user, temp->GetUses().front().GetUser());
     return user;
   }
 
   size_t GetTempIndex(LiveInterval* temp) const {
     // We use the input index to store the index of the temporary in the user's temporary list.
     DCHECK(temp->IsTemp());
-    return temp->GetFirstUse()->GetInputIndex();
+    return temp->GetUses().front().GetInputIndex();
   }
 
   size_t GetMaxLifetimePosition() const {
diff --git a/compiler/utils/intrusive_forward_list.h b/compiler/utils/intrusive_forward_list.h
index b5fc2f2..5a358ac 100644
--- a/compiler/utils/intrusive_forward_list.h
+++ b/compiler/utils/intrusive_forward_list.h
@@ -23,6 +23,7 @@
 #include <memory>
 #include <type_traits>
 
+#include "base/casts.h"
 #include "base/logging.h"
 #include "base/macros.h"
 
@@ -42,10 +43,19 @@
   mutable const IntrusiveForwardListHook* next_hook;
 };
 
-template <typename T, IntrusiveForwardListHook T::* NextPtr = &T::hook>
-class IntrusiveForwardListMemberHook;
+template <typename Derived, typename Tag = void>
+struct IntrusiveForwardListNode : public IntrusiveForwardListHook {
+};
 
-template <typename T, typename HookTraits = IntrusiveForwardListMemberHook<T>>
+template <typename T, IntrusiveForwardListHook T::* NextPtr = &T::hook>
+class IntrusiveForwardListMemberHookTraits;
+
+template <typename T, typename Tag = void>
+class IntrusiveForwardListBaseHookTraits;
+
+template <typename T,
+          typename HookTraits =
+              IntrusiveForwardListBaseHookTraits<typename std::remove_const<T>::type>>
 class IntrusiveForwardList;
 
 template <typename T, typename HookTraits>
@@ -435,7 +445,7 @@
 }
 
 template <typename T, IntrusiveForwardListHook T::* NextPtr>
-class IntrusiveForwardListMemberHook {
+class IntrusiveForwardListMemberHookTraits {
  public:
   static const IntrusiveForwardListHook* GetHook(const T* value) {
     return &(value->*NextPtr);
@@ -447,6 +457,20 @@
   }
 };
 
+template <typename T, typename Tag>
+class IntrusiveForwardListBaseHookTraits {
+ public:
+  static const IntrusiveForwardListHook* GetHook(const T* value) {
+    // Explicit conversion to the "node" followed by implicit conversion to the "hook".
+    return static_cast<const IntrusiveForwardListNode<T, Tag>*>(value);
+  }
+
+  static T* GetValue(const IntrusiveForwardListHook* hook) {
+    return down_cast<T*>(down_cast<IntrusiveForwardListNode<T, Tag>*>(
+        const_cast<IntrusiveForwardListHook*>(hook)));
+  }
+};
+
 }  // 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
index f2efa4d..939676c 100644
--- a/compiler/utils/intrusive_forward_list_test.cc
+++ b/compiler/utils/intrusive_forward_list_test.cc
@@ -23,13 +23,14 @@
 
 namespace art {
 
-struct IFLTestValue {
+struct IFLTestValue : public IntrusiveForwardListNode<IFLTestValue> {
   // Deliberately not explicit.
-  IFLTestValue(int v) : hook(), value(v) { }  // NOLINT(runtime/explicit)
+  IFLTestValue(int v) : value(v) { }  // NOLINT(runtime/explicit)
 
-  IntrusiveForwardListHook hook;
   int value;
 };
+using IFLTestValueList = IntrusiveForwardList<IFLTestValue>;
+using ConstIFLTestValueList = IntrusiveForwardList<const IFLTestValue>;
 
 bool operator==(const IFLTestValue& lhs, const IFLTestValue& rhs) {
   return lhs.value == rhs.value;
@@ -39,6 +40,24 @@
   return lhs.value < rhs.value;
 }
 
+struct IFLTestValue2 {
+  // Deliberately not explicit.
+  IFLTestValue2(int v) : hook(), value(v) { }  // NOLINT(runtime/explicit)
+
+  IntrusiveForwardListHook hook;
+  int value;
+};
+using IFLTestValue2List =
+    IntrusiveForwardList<IFLTestValue2, IntrusiveForwardListMemberHookTraits<IFLTestValue2>>;
+
+bool operator==(const IFLTestValue2& lhs, const IFLTestValue2& rhs) {
+  return lhs.value == rhs.value;
+}
+
+bool operator<(const IFLTestValue2& lhs, const IFLTestValue2& rhs) {
+  return lhs.value < rhs.value;
+}
+
 #define ASSERT_LISTS_EQUAL(expected, value)                                         \
   do {                                                                              \
     ASSERT_EQ((expected).empty(), (value).empty());                                 \
@@ -47,16 +66,82 @@
     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;
+class IntrusiveForwardListTest : public testing::Test {
+ public:
+  template <typename ListType>
+  void IteratorToConstIterator();
+
+  template <typename ListType>
+  void IteratorOperators();
+
+  template <typename ListType>
+  void ConstructRange();
+
+  template <typename ListType>
+  void Assign();
+
+  template <typename ListType>
+  void PushPop();
+
+  template <typename ListType>
+  void InsertAfter1();
+
+  template <typename ListType>
+  void InsertAfter2();
+
+  template <typename ListType>
+  void EraseAfter1();
+
+  template <typename ListType>
+  void EraseAfter2();
+
+  template <typename ListType>
+  void SwapClear();
+
+  template <typename ListType>
+  void SpliceAfter();
+
+  template <typename ListType>
+  void Remove();
+
+  template <typename ListType>
+  void Unique();
+
+  template <typename ListType>
+  void Merge();
+
+  template <typename ListType>
+  void Sort1();
+
+  template <typename ListType>
+  void Sort2();
+
+  template <typename ListType>
+  void Reverse();
+
+  template <typename ListType>
+  void ModifyValue();
+};
+
+template <typename ListType>
+void IntrusiveForwardListTest::IteratorToConstIterator() {
+  ListType ifl;
+  typename ListType::iterator begin = ifl.begin();
+  typename ListType::const_iterator cbegin = ifl.cbegin();
+  typename ListType::const_iterator converted_begin = begin;
   ASSERT_TRUE(converted_begin == cbegin);
 }
 
-TEST(IntrusiveForwardList, IteratorOperators) {
-  IntrusiveForwardList<IFLTestValue> ifl;
+TEST_F(IntrusiveForwardListTest, IteratorToConstIterator) {
+  IteratorToConstIterator<IFLTestValueList>();
+  IteratorToConstIterator<ConstIFLTestValueList>();
+  IteratorToConstIterator<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::IteratorOperators() {
+  using ValueType = typename ListType::value_type;
+  ListType ifl;
   ASSERT_TRUE(ifl.begin() == ifl.cbegin());
   ASSERT_FALSE(ifl.begin() != ifl.cbegin());
   ASSERT_TRUE(ifl.end() == ifl.cend());
@@ -65,37 +150,61 @@
   ASSERT_TRUE(ifl.begin() == ifl.end());  // Empty.
   ASSERT_FALSE(ifl.begin() != ifl.end());  // Empty.
 
-  IFLTestValue value(1);
+  ValueType 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) {
+TEST_F(IntrusiveForwardListTest, IteratorOperators) {
+  IteratorOperators<IFLTestValueList>();
+  IteratorOperators<ConstIFLTestValueList>();
+  IteratorOperators<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::ConstructRange() {
+  using ValueType = typename ListType::value_type;
   std::forward_list<int> ref({ 1, 2, 7 });
-  std::vector<IFLTestValue> storage(ref.begin(), ref.end());
-  IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+  std::vector<ValueType> storage(ref.begin(), ref.end());
+  ListType ifl(storage.begin(), storage.end());
   ASSERT_LISTS_EQUAL(ref, ifl);
 }
 
-TEST(IntrusiveForwardList, Assign) {
+TEST_F(IntrusiveForwardListTest, ConstructRange) {
+  ConstructRange<IFLTestValueList>();
+  ConstructRange<ConstIFLTestValueList>();
+  ConstructRange<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::Assign() {
+  using ValueType = typename ListType::value_type;
   std::forward_list<int> ref1({ 2, 8, 5 });
-  std::vector<IFLTestValue> storage1(ref1.begin(), ref1.end());
-  IntrusiveForwardList<IFLTestValue> ifl;
+  std::vector<ValueType> storage1(ref1.begin(), ref1.end());
+  ListType 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());
+  std::vector<ValueType> 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);
+TEST_F(IntrusiveForwardListTest, Assign) {
+  Assign<IFLTestValueList>();
+  Assign<ConstIFLTestValueList>();
+  Assign<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::PushPop() {
+  using ValueType = typename ListType::value_type;
+  ValueType value3(3);
+  ValueType value7(7);
   std::forward_list<int> ref;
-  IntrusiveForwardList<IFLTestValue> ifl;
+  ListType ifl;
   ASSERT_LISTS_EQUAL(ref, ifl);
   ref.push_front(3);
   ifl.push_front(value3);
@@ -114,13 +223,21 @@
   ASSERT_LISTS_EQUAL(ref, ifl);
 }
 
-TEST(IntrusiveForwardList, InsertAfter1) {
-  IFLTestValue value4(4);
-  IFLTestValue value8(8);
-  IFLTestValue value5(5);
-  IFLTestValue value3(3);
+TEST_F(IntrusiveForwardListTest, PushPop) {
+  PushPop<IFLTestValueList>();
+  PushPop<ConstIFLTestValueList>();
+  PushPop<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::InsertAfter1() {
+  using ValueType = typename ListType::value_type;
+  ValueType value4(4);
+  ValueType value8(8);
+  ValueType value5(5);
+  ValueType value3(3);
   std::forward_list<int> ref;
-  IntrusiveForwardList<IFLTestValue> ifl;
+  ListType ifl;
 
   auto ref_it = ref.insert_after(ref.before_begin(), 4);
   auto ifl_it = ifl.insert_after(ifl.before_begin(), value4);
@@ -149,23 +266,31 @@
   ASSERT_EQ(*ref_it, *ifl_it);
 }
 
-TEST(IntrusiveForwardList, InsertAfter2) {
+TEST_F(IntrusiveForwardListTest, InsertAfter1) {
+  InsertAfter1<IFLTestValueList>();
+  InsertAfter1<ConstIFLTestValueList>();
+  InsertAfter1<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::InsertAfter2() {
+  using ValueType = typename ListType::value_type;
   std::forward_list<int> ref;
-  IntrusiveForwardList<IFLTestValue> ifl;
+  ListType ifl;
 
   auto ref_it = ref.insert_after(ref.before_begin(), { 2, 8, 5 });
-  std::vector<IFLTestValue> storage1({ { 2 }, { 8 }, { 5 } });
+  std::vector<ValueType> 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 } });
+  std::vector<ValueType> 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 } });
+  std::vector<ValueType> storage3({ { 1 }, { 3 }, { 4 }, { 9 } });
   ref_it = ref.begin();
   ifl_it = ifl.begin();
   std::advance(ref_it, std::distance(ref.begin(), ref.end()) - 1);
@@ -175,10 +300,18 @@
   ASSERT_LISTS_EQUAL(ref, ifl);
 }
 
-TEST(IntrusiveForwardList, EraseAfter1) {
+TEST_F(IntrusiveForwardListTest, InsertAfter2) {
+  InsertAfter2<IFLTestValueList>();
+  InsertAfter2<ConstIFLTestValueList>();
+  InsertAfter2<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::EraseAfter1() {
+  using ValueType = typename ListType::value_type;
   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());
+  std::vector<ValueType> storage(ref.begin(), ref.end());
+  ListType ifl(storage.begin(), storage.end());
   ASSERT_LISTS_EQUAL(ref, ifl);
   CHECK_EQ(std::distance(ref.begin(), ref.end()), 5);
 
@@ -230,10 +363,18 @@
   ASSERT_TRUE(ifl_it == ifl.begin());
 }
 
-TEST(IntrusiveForwardList, EraseAfter2) {
+TEST_F(IntrusiveForwardListTest, EraseAfter1) {
+  EraseAfter1<IFLTestValueList>();
+  EraseAfter1<ConstIFLTestValueList>();
+  EraseAfter1<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::EraseAfter2() {
+  using ValueType = typename ListType::value_type;
   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());
+  std::vector<ValueType> storage(ref.begin(), ref.end());
+  ListType ifl(storage.begin(), storage.end());
   ASSERT_LISTS_EQUAL(ref, ifl);
   CHECK_EQ(std::distance(ref.begin(), ref.end()), 9);
 
@@ -262,13 +403,21 @@
   CHECK_EQ(std::distance(ref.begin(), ref.end()), 0);
 }
 
-TEST(IntrusiveForwardList, SwapClear) {
+TEST_F(IntrusiveForwardListTest, EraseAfter2) {
+  EraseAfter2<IFLTestValueList>();
+  EraseAfter2<ConstIFLTestValueList>();
+  EraseAfter2<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::SwapClear() {
+  using ValueType = typename ListType::value_type;
   std::forward_list<int> ref1({ 1, 2, 7 });
-  std::vector<IFLTestValue> storage1(ref1.begin(), ref1.end());
-  IntrusiveForwardList<IFLTestValue> ifl1(storage1.begin(), storage1.end());
+  std::vector<ValueType> storage1(ref1.begin(), ref1.end());
+  ListType 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());
+  std::vector<ValueType> storage2(ref2.begin(), ref2.end());
+  ListType ifl2(storage2.begin(), storage2.end());
   ASSERT_LISTS_EQUAL(ref1, ifl1);
   ASSERT_LISTS_EQUAL(ref2, ifl2);
   ref1.swap(ref2);
@@ -289,12 +438,20 @@
   ASSERT_LISTS_EQUAL(ref2, ifl2);
 }
 
-TEST(IntrusiveForwardList, SpliceAfter) {
+TEST_F(IntrusiveForwardListTest, SwapClear) {
+  SwapClear<IFLTestValueList>();
+  SwapClear<ConstIFLTestValueList>();
+  SwapClear<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::SpliceAfter() {
+  using ValueType = typename ListType::value_type;
   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;
+  std::vector<ValueType> storage(ref1.begin(), ref1.end());
+  ListType ifl1(storage.begin(), storage.end());
+  ListType ifl2;
   ASSERT_LISTS_EQUAL(ref1, ifl1);
   ASSERT_LISTS_EQUAL(ref2, ifl2);
 
@@ -398,10 +555,18 @@
   ASSERT_LISTS_EQUAL(check, ifl2);
 }
 
-TEST(IntrusiveForwardList, Remove) {
+TEST_F(IntrusiveForwardListTest, SpliceAfter) {
+  SpliceAfter<IFLTestValueList>();
+  SpliceAfter<ConstIFLTestValueList>();
+  SpliceAfter<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::Remove() {
+  using ValueType = typename ListType::value_type;
   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());
+  std::vector<ValueType> storage(ref.begin(), ref.end());
+  ListType ifl(storage.begin(), storage.end());
   ASSERT_LISTS_EQUAL(ref, ifl);
   ref.remove(1);
   ifl.remove(1);
@@ -409,20 +574,28 @@
   ref.remove(4);
   ifl.remove(4);
   ASSERT_LISTS_EQUAL(ref, ifl);
-  auto odd = [](IFLTestValue value) { return (value.value & 1) != 0; };  // NOLINT(readability/braces)
+  auto odd = [](ValueType 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)
+  auto all = [](ValueType value ATTRIBUTE_UNUSED) { return true; };  // NOLINT(readability/braces)
   ref.remove_if(all);
   ifl.remove_if(all);
   ASSERT_LISTS_EQUAL(ref, ifl);
 }
 
-TEST(IntrusiveForwardList, Unique) {
+TEST_F(IntrusiveForwardListTest, Remove) {
+  Remove<IFLTestValueList>();
+  Remove<ConstIFLTestValueList>();
+  Remove<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::Unique() {
+  using ValueType = typename ListType::value_type;
   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());
+  std::vector<ValueType> storage(ref.begin(), ref.end());
+  ListType ifl(storage.begin(), storage.end());
   ASSERT_LISTS_EQUAL(ref, ifl);
   ref.unique();
   ifl.unique();
@@ -430,7 +603,7 @@
   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) {
+  auto bin_pred = [](const ValueType& lhs, const ValueType& rhs) {
     return (lhs.value & ~1) == (rhs.value & ~1);
   };
   ref.unique(bin_pred);
@@ -440,13 +613,21 @@
   ASSERT_LISTS_EQUAL(check, ifl);
 }
 
-TEST(IntrusiveForwardList, Merge) {
+TEST_F(IntrusiveForwardListTest, Unique) {
+  Unique<IFLTestValueList>();
+  Unique<ConstIFLTestValueList>();
+  Unique<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::Merge() {
+  using ValueType = typename ListType::value_type;
   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::vector<ValueType> storage1(ref1.begin(), ref1.end());
+  ListType 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());
+  std::vector<ValueType> storage2(ref2.begin(), ref2.end());
+  ListType ifl2(storage2.begin(), storage2.end());
   ASSERT_LISTS_EQUAL(ref1, ifl1);
   ASSERT_LISTS_EQUAL(ref2, ifl2);
   CHECK(std::is_sorted(ref1.begin(), ref1.end()));
@@ -460,10 +641,18 @@
   ASSERT_LISTS_EQUAL(check, ifl1);
 }
 
-TEST(IntrusiveForwardList, Sort1) {
+TEST_F(IntrusiveForwardListTest, Merge) {
+  Merge<IFLTestValueList>();
+  Merge<ConstIFLTestValueList>();
+  Merge<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::Sort1() {
+  using ValueType = typename ListType::value_type;
   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());
+  std::vector<ValueType> storage(ref.begin(), ref.end());
+  ListType ifl(storage.begin(), storage.end());
   ASSERT_LISTS_EQUAL(ref, ifl);
   CHECK(!std::is_sorted(ref.begin(), ref.end()));
   ref.sort();
@@ -473,12 +662,20 @@
   ASSERT_LISTS_EQUAL(check, ifl);
 }
 
-TEST(IntrusiveForwardList, Sort2) {
+TEST_F(IntrusiveForwardListTest, Sort1) {
+  Sort1<IFLTestValueList>();
+  Sort1<ConstIFLTestValueList>();
+  Sort1<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::Sort2() {
+  using ValueType = typename ListType::value_type;
   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());
+  std::vector<ValueType> storage(ref.begin(), ref.end());
+  ListType ifl(storage.begin(), storage.end());
   ASSERT_LISTS_EQUAL(ref, ifl);
-  auto cmp = [](IFLTestValue lhs, IFLTestValue rhs) {
+  auto cmp = [](const ValueType& lhs, const ValueType& rhs) {
     return (lhs.value & ~1) < (rhs.value & ~1);
   };
   CHECK(!std::is_sorted(ref.begin(), ref.end(), cmp));
@@ -489,10 +686,18 @@
   ASSERT_LISTS_EQUAL(check, ifl);
 }
 
-TEST(IntrusiveForwardList, Reverse) {
+TEST_F(IntrusiveForwardListTest, Sort2) {
+  Sort2<IFLTestValueList>();
+  Sort2<ConstIFLTestValueList>();
+  Sort2<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::Reverse() {
+  using ValueType = typename ListType::value_type;
   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());
+  std::vector<ValueType> storage(ref.begin(), ref.end());
+  ListType ifl(storage.begin(), storage.end());
   ASSERT_LISTS_EQUAL(ref, ifl);
   CHECK(!std::is_sorted(ref.begin(), ref.end()));
   ref.reverse();
@@ -502,4 +707,73 @@
   ASSERT_LISTS_EQUAL(check, ifl);
 }
 
+TEST_F(IntrusiveForwardListTest, Reverse) {
+  Reverse<IFLTestValueList>();
+  Reverse<ConstIFLTestValueList>();
+  Reverse<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::ModifyValue() {
+  using ValueType = typename ListType::value_type;
+  std::forward_list<int> ref({ 3, 7, 42 });
+  std::vector<ValueType> storage(ref.begin(), ref.end());
+  ListType ifl(storage.begin(), storage.end());
+  ASSERT_LISTS_EQUAL(ref, ifl);
+
+  auto add1 = [](const ValueType& value) { return value.value + 1; };  // NOLINT [readability/braces]
+  std::transform(ref.begin(), ref.end(), ref.begin(), add1);
+  std::transform(ifl.begin(), ifl.end(), ifl.begin(), add1);
+  ASSERT_LISTS_EQUAL(ref, ifl);
+}
+
+TEST_F(IntrusiveForwardListTest, ModifyValue) {
+  ModifyValue<IFLTestValueList>();
+  // Does not compile with ConstIFLTestValueList because LHS of the assignment is const.
+  // ModifyValue<ConstIFLTestValueList>();
+  static_assert(std::is_const<ConstIFLTestValueList::iterator::value_type>::value, "Const check.");
+  ModifyValue<IFLTestValue2List>();
+}
+
+struct Tag1;
+struct Tag2;
+struct TwoListsValue : public IntrusiveForwardListNode<TwoListsValue, Tag1>,
+                       public IntrusiveForwardListNode<TwoListsValue, Tag2> {
+  // Deliberately not explicit.
+  TwoListsValue(int v) : value(v) { }  // NOLINT(runtime/explicit)
+
+  int value;
+};
+using FirstList =
+    IntrusiveForwardList<TwoListsValue, IntrusiveForwardListBaseHookTraits<TwoListsValue, Tag1>>;
+using SecondList =
+    IntrusiveForwardList<TwoListsValue, IntrusiveForwardListBaseHookTraits<TwoListsValue, Tag2>>;
+
+bool operator==(const TwoListsValue& lhs, const TwoListsValue& rhs) {
+  return lhs.value == rhs.value;
+}
+
+TEST_F(IntrusiveForwardListTest, TwoLists) {
+  // Test that a value can be in two lists at the same time and the hooks do not interfere.
+  std::vector<TwoListsValue> storage({ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 });  // storage[i] = i
+
+  std::vector<int> order1({ 3, 1, 7, 2, 8, 9, 4, 0, 6, 5 });
+  FirstList list1;
+  auto pos1 = list1.before_begin();
+  for (size_t idx : order1) {
+    pos1 = list1.insert_after(pos1, storage[idx]);
+  }
+
+  std::vector<int> order2({ 8, 5, 1, 6, 7, 2, 9, 3, 0, 4 });
+  SecondList list2;
+  auto pos2 = list2.before_begin();
+  for (size_t idx : order2) {
+    pos2 = list2.insert_after(pos2, storage[idx]);
+  }
+
+  // Using `storage[i] = i`, we can easily compare that nodes of each list are in the right order.
+  ASSERT_LISTS_EQUAL(order1, list1);
+  ASSERT_LISTS_EQUAL(order2, list2);
+}
+
 }  // namespace art