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, 27 insertions, 32 deletions

diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 9ea4b2dab4..96837a8266 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -342,36 +342,34 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) {
 
   // 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 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) {
   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 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) {
   }
 
   // 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()));
     }
   }