commit 1abb4191a2e56d8dbf518efcaeefb266c1acdf2b
author David Brazdil <dbrazdil@google.com> Tue Feb 17 18:33:36 2015 +0000
committer David Brazdil <dbrazdil@google.com> Mon Feb 23 15:12:24 2015 +0000
tree e9cd0006df96b167c5da9f8f872713ff05b72803
parent 735969139b162f9d45a3c0e47dc24a8aec63c736

Optimizing: Speed up HInstruction use removal

Similarly to a previous commit on HEnvironment use removal, this patch
adds links from instructions to their respective inputs' use lists for
contant-time removal at the cost of doubling the size of input lists
(from one pointer per entry to two). Manual testing shows that this
significantly reduces the time required to transform HGraph to SSA
form for some huge methods.

Change-Id: I8dc3e4b0c48a50ac1481eb55c31093b99f4dc29f

compiler/optimizing/bounds_check_elimination_test.cc

diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index 17cb8f3..66c873e 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -400,7 +400,6 @@
   loop_body->AddSuccessor(loop_header);
 
   HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
-  phi->AddInput(constant_initial);
   HInstruction* null_check = new (allocator) HNullCheck(parameter, 0);
   HInstruction* array_length = new (allocator) HArrayLength(null_check);
   HInstruction* cmp = nullptr;
@@ -416,6 +415,7 @@
   loop_header->AddInstruction(array_length);
   loop_header->AddInstruction(cmp);
   loop_header->AddInstruction(if_inst);
+  phi->AddInput(constant_initial);
 
   null_check = new (allocator) HNullCheck(parameter, 0);
   array_length = new (allocator) HArrayLength(null_check);
@@ -544,7 +544,6 @@
   loop_body->AddSuccessor(loop_header);
 
   HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
-  phi->AddInput(array_length);
   HInstruction* cmp = nullptr;
   if (cond == kCondLE) {
     cmp = new (allocator) HLessThanOrEqual(phi, constant_initial);
@@ -556,6 +555,7 @@
   loop_header->AddPhi(phi);
   loop_header->AddInstruction(cmp);
   loop_header->AddInstruction(if_inst);
+  phi->AddInput(array_length);
 
   HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_minus_1);
   null_check = new (allocator) HNullCheck(parameter, 0);
@@ -672,7 +672,6 @@
   loop_body->AddSuccessor(loop_header);
 
   HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
-  phi->AddInput(constant_initial);
   HInstruction* cmp = nullptr;
   if (cond == kCondGE) {
     cmp = new (allocator) HGreaterThanOrEqual(phi, constant_10);
@@ -684,6 +683,7 @@
   loop_header->AddPhi(phi);
   loop_header->AddInstruction(cmp);
   loop_header->AddInstruction(if_inst);
+  phi->AddInput(constant_initial);
 
   HNullCheck* null_check = new (allocator) HNullCheck(new_array, 0);
   HArrayLength* array_length = new (allocator) HArrayLength(null_check);
@@ -785,7 +785,6 @@
   loop_body->AddSuccessor(loop_header);
 
   HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
-  phi->AddInput(constant_initial);
   HInstruction* null_check = new (allocator) HNullCheck(parameter, 0);
   HInstruction* array_length = new (allocator) HArrayLength(null_check);
   HInstruction* cmp = nullptr;
@@ -800,6 +799,7 @@
   loop_header->AddInstruction(array_length);
   loop_header->AddInstruction(cmp);
   loop_header->AddInstruction(if_inst);
+  phi->AddInput(constant_initial);
 
   null_check = new (allocator) HNullCheck(parameter, 0);
   array_length = new (allocator) HArrayLength(null_check);
@@ -904,7 +904,6 @@
   HBasicBlock* outer_header = new (&allocator) HBasicBlock(graph);
   graph->AddBlock(outer_header);
   HPhi* phi_i = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt);
-  phi_i->AddInput(constant_0);
   HNullCheck* null_check = new (&allocator) HNullCheck(parameter, 0);
   HArrayLength* array_length = new (&allocator) HArrayLength(null_check);
   HAdd* add = new (&allocator) HAdd(Primitive::kPrimInt, array_length, constant_minus_1);
@@ -916,11 +915,11 @@
   outer_header->AddInstruction(add);
   outer_header->AddInstruction(cmp);
   outer_header->AddInstruction(if_inst);
+  phi_i->AddInput(constant_0);
 
   HBasicBlock* inner_header = new (&allocator) HBasicBlock(graph);
   graph->AddBlock(inner_header);
   HPhi* phi_j = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt);
-  phi_j->AddInput(constant_0);
   null_check = new (&allocator) HNullCheck(parameter, 0);
   array_length = new (&allocator) HArrayLength(null_check);
   HSub* sub = new (&allocator) HSub(Primitive::kPrimInt, array_length, phi_i);
@@ -934,6 +933,7 @@
   inner_header->AddInstruction(add);
   inner_header->AddInstruction(cmp);
   inner_header->AddInstruction(if_inst);
+  phi_j->AddInput(constant_0);
 
   HBasicBlock* inner_body_compare = new (&allocator) HBasicBlock(graph);
   graph->AddBlock(inner_body_compare);