From ed59619b370ef23ffbb25d1d01f615e60a9262b6 Mon Sep 17 00:00:00 2001
From: David Brazdil <dbrazdil@google.com>
Date: Fri, 23 Jan 2015 10:39:45 +0000
Subject: Optimizing: Speed up HEnvironment use removal

Removal of use records from HEnvironment vregs involved iterating over
potentially large linked lists which made compilation of huge methods
very slow. This patch turns use lists into doubly-linked lists, stores
pointers to the relevant nodes inside HEnvironment and subsequently
turns the removals into constant-time operations.

Change-Id: I0e1d4d782fd624e7b8075af75d4adf0a0634a1ee
---
 compiler/optimizing/nodes.cc | 56 ++++++++++++++++++++++++--------------------
 1 file changed, 30 insertions(+), 26 deletions(-)

(limited to 'compiler/optimizing/nodes.cc')

diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index ec53366e19..fe9ce740da 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -39,9 +39,11 @@ static void RemoveAsUser(HInstruction* instruction) {
   HEnvironment* environment = instruction->GetEnvironment();
   if (environment != nullptr) {
     for (size_t i = 0, e = environment->Size(); i < e; ++i) {
-      HInstruction* vreg = environment->GetInstructionAt(i);
-      if (vreg != nullptr) {
-        vreg->RemoveEnvironmentUser(environment, i);
+      HUseListNode<HEnvironment*>* vreg_env_use = environment->GetInstructionEnvUseAt(i);
+      if (vreg_env_use != nullptr) {
+        HInstruction* vreg = environment->GetInstructionAt(i);
+        DCHECK(vreg != nullptr);
+        vreg->RemoveEnvironmentUser(vreg_env_use);
       }
     }
   }
@@ -425,8 +427,8 @@ static void Remove(HInstructionList* instruction_list,
                    HBasicBlock* block,
                    HInstruction* instruction) {
   DCHECK_EQ(block, instruction->GetBlock());
-  DCHECK(instruction->GetUses() == nullptr);
-  DCHECK(instruction->GetEnvUses() == nullptr);
+  DCHECK(instruction->GetUses().IsEmpty());
+  DCHECK(instruction->GetEnvUses().IsEmpty());
   instruction->SetBlock(nullptr);
   instruction_list->RemoveInstruction(instruction);
 
@@ -441,22 +443,24 @@ void HBasicBlock::RemovePhi(HPhi* phi) {
   Remove(&phis_, this, phi);
 }
 
+void HEnvironment::CopyFrom(HEnvironment* env) {
+  for (size_t i = 0; i < env->Size(); i++) {
+    HInstruction* instruction = env->GetInstructionAt(i);
+    SetRawEnvAt(i, instruction);
+    if (instruction != nullptr) {
+      instruction->AddEnvUseAt(this, i);
+    }
+  }
+}
+
 template <typename T>
-static void RemoveFromUseList(T* user,
-                              size_t input_index,
-                              HUseListNode<T>** list) {
-  HUseListNode<T>* previous = nullptr;
-  HUseListNode<T>* current = *list;
-  while (current != nullptr) {
+static void RemoveFromUseList(T user, size_t input_index, HUseList<T>* list) {
+  HUseListNode<T>* current;
+  for (HUseIterator<HInstruction*> use_it(*list); !use_it.Done(); use_it.Advance()) {
+    current = use_it.Current();
     if (current->GetUser() == user && current->GetIndex() == input_index) {
-      if (previous == nullptr) {
-        *list = current->GetTail();
-      } else {
-        previous->SetTail(current->GetTail());
-      }
+      list->Remove(current);
     }
-    previous = current;
-    current = current->GetTail();
   }
 }
 
@@ -480,8 +484,8 @@ void HInstruction::RemoveUser(HInstruction* user, size_t input_index) {
   RemoveFromUseList(user, input_index, &uses_);
 }
 
-void HInstruction::RemoveEnvironmentUser(HEnvironment* user, size_t input_index) {
-  RemoveFromUseList(user, input_index, &env_uses_);
+void HInstruction::RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use) {
+  env_uses_.Remove(use);
 }
 
 void HInstructionList::AddInstruction(HInstruction* instruction) {
@@ -573,24 +577,24 @@ bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const {
 
 void HInstruction::ReplaceWith(HInstruction* other) {
   DCHECK(other != nullptr);
-  for (HUseIterator<HInstruction> it(GetUses()); !it.Done(); it.Advance()) {
-    HUseListNode<HInstruction>* current = it.Current();
+  for (HUseIterator<HInstruction*> it(GetUses()); !it.Done(); it.Advance()) {
+    HUseListNode<HInstruction*>* current = it.Current();
     HInstruction* user = current->GetUser();
     size_t input_index = current->GetIndex();
     user->SetRawInputAt(input_index, other);
     other->AddUseAt(user, input_index);
   }
 
-  for (HUseIterator<HEnvironment> it(GetEnvUses()); !it.Done(); it.Advance()) {
-    HUseListNode<HEnvironment>* current = it.Current();
+  for (HUseIterator<HEnvironment*> it(GetEnvUses()); !it.Done(); it.Advance()) {
+    HUseListNode<HEnvironment*>* current = it.Current();
     HEnvironment* user = current->GetUser();
     size_t input_index = current->GetIndex();
     user->SetRawEnvAt(input_index, other);
     other->AddEnvUseAt(user, input_index);
   }
 
-  uses_ = nullptr;
-  env_uses_ = nullptr;
+  uses_.Clear();
+  env_uses_.Clear();
 }
 
 void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) {
-- 
cgit v1.2.3-59-g8ed1b