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, 12 insertions, 15 deletions

diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 2fe2f2053a..600e1d3b0b 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -108,8 +108,8 @@ static void AddDependentInstructionsToWorklist(HInstruction* instruction,
   // marked dead/conflicting too, so we add them to the worklist. Otherwise we
   // add users whose type does not match and needs to be updated.
   bool add_all_live_phis = instruction->IsPhi() && instruction->AsPhi()->IsDead();
-  for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
-    HInstruction* user = it.Current()->GetUser();
+  for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
+    HInstruction* user = use.GetUser();
     if (user->IsPhi() && user->AsPhi()->IsLive()) {
       if (add_all_live_phis || user->GetType() != instruction->GetType()) {
         worklist->push_back(user->AsPhi());
@@ -412,27 +412,24 @@ bool SsaBuilder::FixAmbiguousArrayOps() {
 }
 
 static bool HasAliasInEnvironments(HInstruction* instruction) {
-  for (HUseIterator<HEnvironment*> use_it(instruction->GetEnvUses());
-       !use_it.Done();
-       use_it.Advance()) {
-    HEnvironment* use = use_it.Current()->GetUser();
-    HUseListNode<HEnvironment*>* next = use_it.Current()->GetNext();
-    if (next != nullptr && next->GetUser() == use) {
+  HEnvironment* last_user = nullptr;
+  for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
+    DCHECK(use.GetUser() != nullptr);
+    // Note: The first comparison (== null) always fails.
+    if (use.GetUser() == last_user) {
       return true;
     }
+    last_user = use.GetUser();
   }
 
   if (kIsDebugBuild) {
     // Do a quadratic search to ensure same environment uses are next
     // to each other.
-    for (HUseIterator<HEnvironment*> use_it(instruction->GetEnvUses());
-         !use_it.Done();
-         use_it.Advance()) {
-      HUseListNode<HEnvironment*>* current = use_it.Current();
-      HUseListNode<HEnvironment*>* next = current->GetNext();
-      while (next != nullptr) {
+    const HUseList<HEnvironment*>& env_uses = instruction->GetEnvUses();
+    for (auto current = env_uses.begin(), end = env_uses.end(); current != end; ++current) {
+      auto next = current;
+      for (++next; next != end; ++next) {
         DCHECK(next->GetUser() != current->GetUser());
-        next = next->GetNext();
       }
     }
   }