Fix a bug in GVN.
When a predecessor block was killing instructions in a set, we were
not taking into account side effects of blocks between the dominator to
this predecessor.
Implementation now intersects the copied set of the dominator with
the predecessors to take these side effects into account.
Change-Id: If297439cc4e50cee91e9fffd028216a3e49e19ef
diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
index 25168b5..6e5f1bd 100644
--- a/compiler/optimizing/gvn.cc
+++ b/compiler/optimizing/gvn.cc
@@ -91,29 +91,38 @@
return block_effects_.Get(block->GetBlockId());
}
-static bool IsLoopExit(HBasicBlock* block, HBasicBlock* successor) {
- HLoopInformation* block_info = block->GetLoopInformation();
- HLoopInformation* other_info = successor->GetLoopInformation();
- return block_info != other_info && (other_info == nullptr || block_info->IsIn(*other_info));
-}
-
void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) {
- if (kIsDebugBuild) {
- // Check that all non back-edge processors have been visited.
- for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) {
- HBasicBlock* predecessor = block->GetPredecessors().Get(i);
- DCHECK(visited_.Get(predecessor->GetBlockId())
- || (block->GetLoopInformation() != nullptr
- && (block->GetLoopInformation()->GetBackEdges().Get(0) == predecessor)));
+ ValueSet* set = nullptr;
+ const GrowableArray<HBasicBlock*>& predecessors = block->GetPredecessors();
+ if (predecessors.Size() == 0 || predecessors.Get(0)->IsEntryBlock()) {
+ // The entry block should only accumulate constant instructions, and
+ // the builder puts constants only in the entry block.
+ // Therefore, there is no need to propagate the value set to the next block.
+ set = new (allocator_) ValueSet(allocator_);
+ } else {
+ HBasicBlock* dominator = block->GetDominator();
+ set = sets_.Get(dominator->GetBlockId())->Copy();
+ if (dominator->GetSuccessors().Size() != 1 || dominator->GetSuccessors().Get(0) != block) {
+ // We have to copy if the dominator has other successors, or `block` is not a successor
+ // of the dominator.
+ set = set->Copy();
}
- visited_.Put(block->GetBlockId(), true);
+ if (!set->IsEmpty()) {
+ if (block->IsLoopHeader()) {
+ DCHECK_EQ(block->GetDominator(), block->GetLoopInformation()->GetPreHeader());
+ set->Kill(GetLoopEffects(block));
+ } else if (predecessors.Size() > 1) {
+ for (size_t i = 0, e = predecessors.Size(); i < e; ++i) {
+ set->IntersectionWith(sets_.Get(predecessors.Get(i)->GetBlockId()));
+ if (set->IsEmpty()) {
+ break;
+ }
+ }
+ }
+ }
}
- ValueSet* set = sets_.Get(block->GetBlockId());
-
- if (block->IsLoopHeader()) {
- set->Kill(GetLoopEffects(block));
- }
+ sets_.Put(block->GetBlockId(), set);
HInstruction* current = block->GetFirstInstruction();
while (current != nullptr) {
@@ -131,57 +140,6 @@
}
current = next;
}
-
- if (block == graph_->GetEntryBlock()) {
- // The entry block should only accumulate constant instructions, and
- // the builder puts constants only in the entry block.
- // Therefore, there is no need to propagate the value set to the next block.
- DCHECK_EQ(block->GetDominatedBlocks().Size(), 1u);
- HBasicBlock* dominated = block->GetDominatedBlocks().Get(0);
- sets_.Put(dominated->GetBlockId(), new (allocator_) ValueSet(allocator_));
- return;
- }
-
- // Copy the value set to dominated blocks. We can re-use
- // the current set for the last dominated block because we are done visiting
- // this block.
- for (size_t i = 0, e = block->GetDominatedBlocks().Size(); i < e; ++i) {
- HBasicBlock* dominated = block->GetDominatedBlocks().Get(i);
- sets_.Put(dominated->GetBlockId(), i == e - 1 ? set : set->Copy());
- }
-
- // Kill instructions in the value set of each successor. If the successor
- // is a loop exit, then we use the side effects of the loop. If not, we use
- // the side effects of this block.
- for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) {
- HBasicBlock* successor = block->GetSuccessors().Get(i);
- if (successor->IsLoopHeader()
- && successor->GetLoopInformation()->GetBackEdges().Get(0) == block) {
- // In case of a back edge, we already have visited the loop header.
- // We should not update its value set, because the last dominated block
- // of the loop header uses the same value set.
- DCHECK(visited_.Get(successor->GetBlockId()));
- continue;
- }
- DCHECK(!visited_.Get(successor->GetBlockId()));
- ValueSet* successor_set = sets_.Get(successor->GetBlockId());
- // The dominator sets the set, and we are guaranteed to have visited it already.
- DCHECK(successor_set != nullptr);
-
- // If this block dominates this successor there is nothing to do.
- // Also if the set is empty, there is nothing to kill.
- if (successor->GetDominator() != block && !successor_set->IsEmpty()) {
- if (block->IsInLoop() && IsLoopExit(block, successor)) {
- // All instructions killed in the loop must be killed for a loop exit.
- SideEffects effects = GetLoopEffects(block->GetLoopInformation()->GetHeader());
- sets_.Get(successor->GetBlockId())->Kill(effects);
- } else {
- // Following block (that might be in the same loop).
- // Just kill instructions based on this block's side effects.
- sets_.Get(successor->GetBlockId())->Kill(GetBlockEffects(block));
- }
- }
- }
}
} // namespace art
diff --git a/compiler/optimizing/gvn.h b/compiler/optimizing/gvn.h
index 8e739cb..81f2c3f 100644
--- a/compiler/optimizing/gvn.h
+++ b/compiler/optimizing/gvn.h
@@ -96,6 +96,26 @@
return nullptr;
}
+ // Returns whether `instruction` is in the set.
+ HInstruction* IdentityLookup(HInstruction* instruction) const {
+ size_t hash_code = instruction->ComputeHashCode();
+ size_t index = hash_code % kDefaultNumberOfEntries;
+ HInstruction* existing = table_[index];
+ if (existing != nullptr && existing == instruction) {
+ return existing;
+ }
+
+ for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) {
+ if (node->GetHashCode() == hash_code) {
+ existing = node->GetInstruction();
+ if (existing == instruction) {
+ return existing;
+ }
+ }
+ }
+ return nullptr;
+ }
+
// Removes all instructions in the set that are affected by the given side effects.
void Kill(SideEffects side_effects) {
for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
@@ -106,9 +126,9 @@
}
}
- ValueSetNode* current = collisions_;
- ValueSetNode* previous = nullptr;
- while (current != nullptr) {
+ for (ValueSetNode* current = collisions_, *previous = nullptr;
+ current != nullptr;
+ current = current->GetNext()) {
HInstruction* instruction = current->GetInstruction();
if (instruction->GetSideEffects().DependsOn(side_effects)) {
if (previous == nullptr) {
@@ -120,7 +140,6 @@
} else {
previous = current;
}
- current = current->GetNext();
}
}
@@ -143,6 +162,44 @@
return copy;
}
+ void Clear() {
+ number_of_entries_ = 0;
+ collisions_ = nullptr;
+ for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
+ table_[i] = nullptr;
+ }
+ }
+
+ // Update this `ValueSet` by intersecting with instructions in `other`.
+ void IntersectionWith(ValueSet* other) {
+ if (IsEmpty()) {
+ return;
+ } else if (other->IsEmpty()) {
+ Clear();
+ } else {
+ for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
+ if (table_[i] != nullptr && other->IdentityLookup(table_[i]) == nullptr) {
+ --number_of_entries_;
+ table_[i] = nullptr;
+ }
+ }
+ for (ValueSetNode* current = collisions_, *previous = nullptr;
+ current != nullptr;
+ current = current->GetNext()) {
+ if (other->IdentityLookup(current->GetInstruction()) == nullptr) {
+ if (previous == nullptr) {
+ collisions_ = current->GetNext();
+ } else {
+ previous->SetNext(current->GetNext());
+ }
+ --number_of_entries_;
+ } else {
+ previous = current;
+ }
+ }
+ }
+ }
+
bool IsEmpty() const { return number_of_entries_ == 0; }
size_t GetNumberOfEntries() const { return number_of_entries_; }
@@ -173,13 +230,11 @@
allocator_(allocator),
block_effects_(allocator, graph->GetBlocks().Size()),
loop_effects_(allocator, graph->GetBlocks().Size()),
- sets_(allocator, graph->GetBlocks().Size()),
- visited_(allocator, graph->GetBlocks().Size()) {
+ sets_(allocator, graph->GetBlocks().Size()) {
size_t number_of_blocks = graph->GetBlocks().Size();
block_effects_.SetSize(number_of_blocks);
loop_effects_.SetSize(number_of_blocks);
sets_.SetSize(number_of_blocks);
- visited_.SetSize(number_of_blocks);
for (size_t i = 0; i < number_of_blocks; ++i) {
block_effects_.Put(i, SideEffects::None());
@@ -219,9 +274,6 @@
// in the path from the dominator to the block.
GrowableArray<ValueSet*> sets_;
- // Mark visisted blocks. Only used for debugging.
- GrowableArray<bool> visited_;
-
ART_FRIEND_TEST(GVNTest, LoopSideEffects);
DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer);
};