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, 9 insertions, 13 deletions

diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 6816b6a028..aeb31094d4 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -43,8 +43,8 @@ void SsaDeadPhiElimination::MarkDeadPhis() {
 
       bool keep_alive = (graph_->IsDebuggable() && phi->HasEnvironmentUses());
       if (!keep_alive) {
-        for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) {
-          if (!use_it.Current()->GetUser()->IsPhi()) {
+        for (const HUseListNode<HInstruction*>& use : phi->GetUses()) {
+          if (!use.GetUser()->IsPhi()) {
             keep_alive = true;
             break;
           }
@@ -94,9 +94,8 @@ void SsaDeadPhiElimination::EliminateDeadPhis() {
       if (phi->IsDead()) {
         // Make sure the phi is only used by other dead phis.
         if (kIsDebugBuild) {
-          for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done();
-               use_it.Advance()) {
-            HInstruction* user = use_it.Current()->GetUser();
+          for (const HUseListNode<HInstruction*>& use : phi->GetUses()) {
+            HInstruction* user = use.GetUser();
             DCHECK(user->IsLoopHeaderPhi());
             DCHECK(user->AsPhi()->IsDead());
           }
@@ -106,11 +105,9 @@ void SsaDeadPhiElimination::EliminateDeadPhis() {
           phi->RemoveAsUserOfInput(i);
         }
         // Remove the phi from environments that use it.
-        for (HUseIterator<HEnvironment*> use_it(phi->GetEnvUses()); !use_it.Done();
-             use_it.Advance()) {
-          HUseListNode<HEnvironment*>* user_node = use_it.Current();
-          HEnvironment* user = user_node->GetUser();
-          user->SetRawEnvAt(user_node->GetIndex(), nullptr);
+        for (const HUseListNode<HEnvironment*>& use : phi->GetEnvUses()) {
+          HEnvironment* user = use.GetUser();
+          user->SetRawEnvAt(use.GetIndex(), nullptr);
         }
         // Delete it from the instruction list.
         block->RemovePhi(phi, /*ensure_safety=*/ false);
@@ -233,9 +230,8 @@ void SsaRedundantPhiElimination::Run() {
 
       // Because we're updating the users of this phi, we may have new candidates
       // for elimination. Add phis that use this phi to the worklist.
-      for (HUseIterator<HInstruction*> it(current->GetUses()); !it.Done(); it.Advance()) {
-        HUseListNode<HInstruction*>* use = it.Current();
-        HInstruction* user = use->GetUser();
+      for (const HUseListNode<HInstruction*>& use : current->GetUses()) {
+        HInstruction* user = use.GetUser();
         if (user->IsPhi() && !ContainsElement(visited_phis_in_cycle, user->GetId())) {
           worklist_.push_back(user->AsPhi());
         }