Reuse HUseListNode<>s when replacing instruction or input.

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 ~5.6MiB:

Before:
  MEM: used: 44393040, allocated: 45361248, lost: 968208
  Number of arenas allocated: 319,
  Number of allocations: 815492, avg size: 54
  ...
  UseListNode    10308480
  ...
After:
  MEM: used: 38554536, allocated: 39463008, lost: 908472
  Number of arenas allocated: 274,
  Number of allocations: 572221, avg size: 67
  ...
  UseListNode     4469976
  ...

With 32-bit dex2oat, the UseListNode would be 2/3 of the
values for 64-bit dex2oat (both before and after).

Bug: 28173563
Change-Id: Ia4fabe03568f0e0dbf2cdf2b031863602aea3530

2 files changed, 23 insertions, 18 deletions

diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index d259c21108..7c6e9318fb 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1005,28 +1005,33 @@ void HInstruction::RemoveEnvironment() {
 
 void HInstruction::ReplaceWith(HInstruction* other) {
   DCHECK(other != nullptr);
-  for (const HUseListNode<HInstruction*>& use : GetUses()) {
-    HInstruction* user = use.GetUser();
-    size_t input_index = use.GetIndex();
-    user->SetRawInputAt(input_index, other);
-    other->AddUseAt(user, input_index);
-  }
+  // Note: fixup_end remains valid across splice_after().
+  auto fixup_end = other->uses_.empty() ? other->uses_.begin() : ++other->uses_.begin();
+  other->uses_.splice_after(other->uses_.before_begin(), uses_);
+  other->FixUpUserRecordsAfterUseInsertion(fixup_end);
 
-  for (const HUseListNode<HEnvironment*>& use : GetEnvUses()) {
-    HEnvironment* user = use.GetUser();
-    size_t input_index = use.GetIndex();
-    user->SetRawEnvAt(input_index, other);
-    other->AddEnvUseAt(user, input_index);
-  }
+  // Note: env_fixup_end remains valid across splice_after().
+  auto env_fixup_end =
+      other->env_uses_.empty() ? other->env_uses_.begin() : ++other->env_uses_.begin();
+  other->env_uses_.splice_after(other->env_uses_.before_begin(), env_uses_);
+  other->FixUpUserRecordsAfterEnvUseInsertion(env_fixup_end);
 
-  uses_.clear();
-  env_uses_.clear();
+  DCHECK(uses_.empty());
+  DCHECK(env_uses_.empty());
 }
 
 void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) {
-  RemoveAsUserOfInput(index);
-  SetRawInputAt(index, replacement);
-  replacement->AddUseAt(this, index);
+  HUserRecord<HInstruction*> input_use = InputRecordAt(index);
+  HUseList<HInstruction*>::iterator before_use_node = input_use.GetBeforeUseNode();
+  DCHECK(input_use.GetInstruction() != replacement);
+  // Note: fixup_end remains valid across splice_after().
+  auto fixup_end =
+      replacement->uses_.empty() ? replacement->uses_.begin() : ++replacement->uses_.begin();
+  replacement->uses_.splice_after(replacement->uses_.before_begin(),
+                                  input_use.GetInstruction()->uses_,
+                                  before_use_node);
+  replacement->FixUpUserRecordsAfterUseInsertion(fixup_end);
+  input_use.GetInstruction()->FixUpUserRecordsAfterUseRemoval(before_use_node);
 }
 
 size_t HInstruction::EnvironmentSize() const {
diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc
index 218bd53bc2..429763423c 100644
--- a/compiler/optimizing/ssa_test.cc
+++ b/compiler/optimizing/ssa_test.cc
@@ -346,7 +346,7 @@ TEST_F(SsaTest, Loop5) {
     "BasicBlock 7, pred: 6\n"
     "  12: Exit\n"
     "BasicBlock 8, pred: 2, 3, succ: 4\n"
-    "  13: Phi(2, 1) [8, 8, 11]\n"
+    "  13: Phi(2, 1) [11, 8, 8]\n"
     "  14: Goto\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(