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

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

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

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

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

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

Bug: 28173563
Change-Id: I985eabd4816f845372d8aaa825a1489cf9569208

1 files changed, 18 insertions, 14 deletions

diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 084360f22b..659c6f8497 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -1206,9 +1206,9 @@ class BCEVisitor : public HGraphVisitor {
           GetGraph()->GetArena()->Adapter(kArenaAllocBoundsCheckElimination));
       ArenaVector<HBoundsCheck*> standby(
           GetGraph()->GetArena()->Adapter(kArenaAllocBoundsCheckElimination));
-      for (HUseIterator<HInstruction*> it2(array_length->GetUses()); !it2.Done(); it2.Advance()) {
+      for (const HUseListNode<HInstruction*>& use : array_length->GetUses()) {
         // Another bounds check in same or dominated block?
-        HInstruction* user = it2.Current()->GetUser();
+        HInstruction* user = use.GetUser();
         HBasicBlock* other_block = user->GetBlock();
         if (user->IsBoundsCheck() && block->Dominates(other_block)) {
           HBoundsCheck* other_bounds_check = user->AsBoundsCheck();
@@ -1635,29 +1635,33 @@ class BCEVisitor : public HGraphVisitor {
         Primitive::Type type = instruction->GetType();
         HPhi* phi = nullptr;
         // Scan all uses of an instruction and replace each later use with a phi node.
-        for (HUseIterator<HInstruction*> it2(instruction->GetUses());
-             !it2.Done();
-             it2.Advance()) {
-          HInstruction* user = it2.Current()->GetUser();
+        const HUseList<HInstruction*>& uses = instruction->GetUses();
+        for (auto it2 = uses.begin(), end2 = uses.end(); it2 != end2; /* ++it2 below */) {
+          HInstruction* user = it2->GetUser();
+          size_t index = it2->GetIndex();
+          // Increment `it2` now because `*it2` may disappear thanks to user->ReplaceInput().
+          ++it2;
           if (user->GetBlock() != true_block) {
             if (phi == nullptr) {
               phi = NewPhi(new_preheader, instruction, type);
             }
-            user->ReplaceInput(phi, it2.Current()->GetIndex());
+            user->ReplaceInput(phi, index);  // Removes the use node from the list.
           }
         }
         // Scan all environment uses of an instruction and replace each later use with a phi node.
-        for (HUseIterator<HEnvironment*> it2(instruction->GetEnvUses());
-             !it2.Done();
-             it2.Advance()) {
-          HEnvironment* user = it2.Current()->GetUser();
+        const HUseList<HEnvironment*>& env_uses = instruction->GetEnvUses();
+        for (auto it2 = env_uses.begin(), end2 = env_uses.end(); it2 != end2; /* ++it2 below */) {
+          HEnvironment* user = it2->GetUser();
+          size_t index = it2->GetIndex();
+          // Increment `it2` now because `*it2` may disappear thanks to user->RemoveAsUserOfInput().
+          ++it2;
           if (user->GetHolder()->GetBlock() != true_block) {
             if (phi == nullptr) {
               phi = NewPhi(new_preheader, instruction, type);
             }
-            user->RemoveAsUserOfInput(it2.Current()->GetIndex());
-            user->SetRawEnvAt(it2.Current()->GetIndex(), phi);
-            phi->AddEnvUseAt(user, it2.Current()->GetIndex());
+            user->RemoveAsUserOfInput(index);
+            user->SetRawEnvAt(index, phi);
+            phi->AddEnvUseAt(user, index);
           }
         }
       }