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
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 7a75d26..93787b8 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -34,17 +34,14 @@
static void RemoveAsUser(HInstruction* instruction) {
for (size_t i = 0; i < instruction->InputCount(); i++) {
- instruction->InputAt(i)->RemoveUser(instruction, i);
+ instruction->RemoveAsUserOfInput(i);
}
HEnvironment* environment = instruction->GetEnvironment();
if (environment != nullptr) {
for (size_t i = 0, e = environment->Size(); i < e; ++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);
+ if (environment->GetInstructionAt(i) != nullptr) {
+ environment->RemoveAsUserOfInput(i);
}
}
}
@@ -64,22 +61,19 @@
}
}
-void HGraph::RemoveBlock(HBasicBlock* block) const {
- for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
- block->GetSuccessors().Get(j)->RemovePredecessor(block);
- }
- for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
- block->RemovePhi(it.Current()->AsPhi());
- }
- for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
- block->RemoveInstruction(it.Current());
- }
-}
-
void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const {
for (size_t i = 0; i < blocks_.Size(); ++i) {
if (!visited.IsBitSet(i)) {
- RemoveBlock(blocks_.Get(i));
+ HBasicBlock* block = blocks_.Get(i);
+ for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
+ block->GetSuccessors().Get(j)->RemovePredecessor(block);
+ }
+ for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
+ block->RemovePhi(it.Current()->AsPhi(), /*ensure_safety=*/ false);
+ }
+ for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+ block->RemoveInstruction(it.Current(), /*ensure_safety=*/ false);
+ }
}
}
}
@@ -439,22 +433,24 @@
static void Remove(HInstructionList* instruction_list,
HBasicBlock* block,
- HInstruction* instruction) {
+ HInstruction* instruction,
+ bool ensure_safety) {
DCHECK_EQ(block, instruction->GetBlock());
- DCHECK(instruction->GetUses().IsEmpty());
- DCHECK(instruction->GetEnvUses().IsEmpty());
instruction->SetBlock(nullptr);
instruction_list->RemoveInstruction(instruction);
-
- RemoveAsUser(instruction);
+ if (ensure_safety) {
+ DCHECK(instruction->GetUses().IsEmpty());
+ DCHECK(instruction->GetEnvUses().IsEmpty());
+ RemoveAsUser(instruction);
+ }
}
-void HBasicBlock::RemoveInstruction(HInstruction* instruction) {
- Remove(&instructions_, this, instruction);
+void HBasicBlock::RemoveInstruction(HInstruction* instruction, bool ensure_safety) {
+ Remove(&instructions_, this, instruction, ensure_safety);
}
-void HBasicBlock::RemovePhi(HPhi* phi) {
- Remove(&phis_, this, phi);
+void HBasicBlock::RemovePhi(HPhi* phi, bool ensure_safety) {
+ Remove(&phis_, this, phi, ensure_safety);
}
void HEnvironment::CopyFrom(HEnvironment* env) {
@@ -467,15 +463,9 @@
}
}
-template <typename T>
-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) {
- list->Remove(current);
- }
- }
+void HEnvironment::RemoveAsUserOfInput(size_t index) const {
+ const HUserRecord<HEnvironment*> user_record = vregs_.Get(index);
+ user_record.GetInstruction()->RemoveEnvironmentUser(user_record.GetUseNode());
}
HInstruction* HInstruction::GetNextDisregardingMoves() const {
@@ -494,14 +484,6 @@
return previous;
}
-void HInstruction::RemoveUser(HInstruction* user, size_t input_index) {
- RemoveFromUseList(user, input_index, &uses_);
-}
-
-void HInstruction::RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use) {
- env_uses_.Remove(use);
-}
-
void HInstructionList::AddInstruction(HInstruction* instruction) {
if (first_instruction_ == nullptr) {
DCHECK(last_instruction_ == nullptr);
@@ -612,7 +594,7 @@
}
void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) {
- InputAt(index)->RemoveUser(this, index);
+ RemoveAsUserOfInput(index);
SetRawInputAt(index, replacement);
replacement->AddUseAt(this, index);
}
@@ -623,7 +605,7 @@
void HPhi::AddInput(HInstruction* input) {
DCHECK(input->GetBlock() != nullptr);
- inputs_.Add(input);
+ inputs_.Add(HUserRecord<HInstruction*>(input));
input->AddUseAt(this, inputs_.Size() - 1);
}