From d31cf3d55a0847c018c4eaa2b349b8eea509de64 Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Mon, 8 Sep 2014 17:30:24 +0100 Subject: First optimization in new compiler: simple GVN. Change-Id: Ibe0efa4e84fd020a53ded310a92e0b4363f91b12 --- compiler/optimizing/graph_visualizer.h | 2 + compiler/optimizing/gvn.cc | 186 ++++++++++++++++++ compiler/optimizing/gvn.h | 230 ++++++++++++++++++++++ compiler/optimizing/gvn_test.cc | 294 +++++++++++++++++++++++++++++ compiler/optimizing/nodes.cc | 3 + compiler/optimizing/nodes.h | 64 ++++++- compiler/optimizing/optimizing_compiler.cc | 6 + 7 files changed, 783 insertions(+), 2 deletions(-) create mode 100644 compiler/optimizing/gvn.cc create mode 100644 compiler/optimizing/gvn.h create mode 100644 compiler/optimizing/gvn_test.cc (limited to 'compiler/optimizing') diff --git a/compiler/optimizing/graph_visualizer.h b/compiler/optimizing/graph_visualizer.h index 7cd74e9b7a..6e2c6fd11f 100644 --- a/compiler/optimizing/graph_visualizer.h +++ b/compiler/optimizing/graph_visualizer.h @@ -25,8 +25,10 @@ class CodeGenerator; class DexCompilationUnit; class HGraph; +// TODO: Create an analysis/optimization abstraction. static const char* kLivenessPassName = "liveness"; static const char* kRegisterAllocatorPassName = "register"; +static const char* kGVNPassName = "gvn"; /** * If enabled, emits compilation information suitable for the c1visualizer tool diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc new file mode 100644 index 0000000000..027b3d4ff3 --- /dev/null +++ b/compiler/optimizing/gvn.cc @@ -0,0 +1,186 @@ +/* + * Copyright (C) 2014 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "gvn.h" + +namespace art { + +void GlobalValueNumberer::Run() { + ComputeSideEffects(); + + sets_.Put(graph_->GetEntryBlock()->GetBlockId(), new (allocator_) ValueSet(allocator_)); + + // Do reverse post order to ensure the non back-edge predecessors of a block are + // visited before the block itself. + for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { + VisitBasicBlock(it.Current()); + } +} + +void GlobalValueNumberer::UpdateLoopEffects(HLoopInformation* info, SideEffects effects) { + int id = info->GetHeader()->GetBlockId(); + loop_effects_.Put(id, loop_effects_.Get(id).Union(effects)); +} + +void GlobalValueNumberer::ComputeSideEffects() { + if (kIsDebugBuild) { + for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + SideEffects effects = GetBlockEffects(block); + DCHECK(!effects.HasSideEffects() && !effects.HasDependencies()); + if (block->IsLoopHeader()) { + effects = GetLoopEffects(block); + DCHECK(!effects.HasSideEffects() && !effects.HasDependencies()); + } + } + } + + // Do a post order visit to ensure we visit a loop header after its loop body. + for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + + SideEffects effects = SideEffects::None(); + // Update `effects` with the side effects of all instructions in this block. + for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { + HInstruction* instruction = it.Current(); + effects = effects.Union(instruction->GetSideEffects()); + if (effects.HasAllSideEffects()) { + break; + } + } + + block_effects_.Put(block->GetBlockId(), effects); + + if (block->IsLoopHeader()) { + // The side effects of the loop header are part of the loop. + UpdateLoopEffects(block->GetLoopInformation(), effects); + HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader(); + if (pre_header->IsInLoop()) { + // Update the side effects of the outer loop with the side effects of the inner loop. + // Note that this works because we know all the blocks of the inner loop are visited + // before the loop header of the outer loop. + UpdateLoopEffects(pre_header->GetLoopInformation(), GetLoopEffects(block)); + } + } else if (block->IsInLoop()) { + // Update the side effects of the loop with the side effects of this block. + UpdateLoopEffects(block->GetLoopInformation(), effects); + } + } +} + +SideEffects GlobalValueNumberer::GetLoopEffects(HBasicBlock* block) const { + DCHECK(block->IsLoopHeader()); + return loop_effects_.Get(block->GetBlockId()); +} + +SideEffects GlobalValueNumberer::GetBlockEffects(HBasicBlock* block) const { + 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))); + } + visited_.Put(block->GetBlockId(), true); + } + + ValueSet* set = sets_.Get(block->GetBlockId()); + + if (block->IsLoopHeader()) { + set->Kill(GetLoopEffects(block)); + } + + HInstruction* current = block->GetFirstInstruction(); + while (current != nullptr) { + set->Kill(current->GetSideEffects()); + // Save the next instruction in case `current` is removed from the graph. + HInstruction* next = current->GetNext(); + if (current->CanBeMoved()) { + HInstruction* existing = set->Lookup(current); + if (existing != nullptr) { + current->ReplaceWith(existing); + current->GetBlock()->RemoveInstruction(current); + } else { + set->Add(current); + } + } + 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 new file mode 100644 index 0000000000..41b3ceb509 --- /dev/null +++ b/compiler/optimizing/gvn.h @@ -0,0 +1,230 @@ +/* + * Copyright (C) 2014 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef ART_COMPILER_OPTIMIZING_GVN_H_ +#define ART_COMPILER_OPTIMIZING_GVN_H_ + +#include +#include "nodes.h" + +namespace art { + +/** + * A node in the collision list of a ValueSet. Encodes the instruction, + * the hash code, and the next node in the collision list. + */ +class ValueSetNode : public ArenaObject { + public: + ValueSetNode(HInstruction* instruction, size_t hash_code, ValueSetNode* next) + : instruction_(instruction), hash_code_(hash_code), next_(next) {} + + size_t GetHashCode() const { return hash_code_; } + HInstruction* GetInstruction() const { return instruction_; } + ValueSetNode* GetNext() const { return next_; } + void SetNext(ValueSetNode* node) { next_ = node; } + + private: + HInstruction* const instruction_; + const size_t hash_code_; + ValueSetNode* next_; + + DISALLOW_COPY_AND_ASSIGN(ValueSetNode); +}; + +/** + * A ValueSet holds instructions that can replace other instructions. It is updated + * through the `Add` method, and the `Kill` method. The `Kill` method removes + * instructions that are affected by the given side effect. + * + * The `Lookup` method returns an equivalent instruction to the given instruction + * if there is one in the set. In GVN, we would say those instructions have the + * same "number". + */ +class ValueSet : public ArenaObject { + public: + explicit ValueSet(ArenaAllocator* allocator) + : allocator_(allocator), number_of_entries_(0), collisions_(nullptr) { + for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) { + table_[i] = nullptr; + } + } + + // Adds an instruction in the set. + void Add(HInstruction* instruction) { + DCHECK(Lookup(instruction) == nullptr); + size_t hash_code = instruction->ComputeHashCode(); + size_t index = hash_code % kDefaultNumberOfEntries; + if (table_[index] == nullptr) { + table_[index] = instruction; + } else { + collisions_ = new (allocator_) ValueSetNode(instruction, hash_code, collisions_); + } + ++number_of_entries_; + } + + // If in the set, returns an equivalent instruction to the given instruction. Returns + // null otherwise. + HInstruction* Lookup(HInstruction* instruction) const { + size_t hash_code = instruction->ComputeHashCode(); + size_t index = hash_code % kDefaultNumberOfEntries; + HInstruction* existing = table_[index]; + if (existing != nullptr && existing->Equals(instruction)) { + return existing; + } + + for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) { + if (node->GetHashCode() == hash_code) { + existing = node->GetInstruction(); + if (existing->Equals(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) { + HInstruction* instruction = table_[i]; + if (instruction != nullptr && instruction->GetSideEffects().DependsOn(side_effects)) { + table_[i] = nullptr; + --number_of_entries_; + } + } + + ValueSetNode* current = collisions_; + ValueSetNode* previous = nullptr; + while (current != nullptr) { + HInstruction* instruction = current->GetInstruction(); + if (instruction->GetSideEffects().DependsOn(side_effects)) { + if (previous == nullptr) { + collisions_ = current->GetNext(); + } else { + previous->SetNext(current->GetNext()); + } + --number_of_entries_; + } else { + previous = current; + } + current = current->GetNext(); + } + } + + // Returns a copy of this set. + ValueSet* Copy() const { + ValueSet* copy = new (allocator_) ValueSet(allocator_); + + for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) { + copy->table_[i] = table_[i]; + } + + // Note that the order will be inverted in the copy. This is fine, as the order is not + // relevant for a ValueSet. + for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) { + copy->collisions_ = new (allocator_) ValueSetNode( + node->GetInstruction(), node->GetHashCode(), copy->collisions_); + } + + copy->number_of_entries_ = number_of_entries_; + return copy; + } + + bool IsEmpty() const { return number_of_entries_ == 0; } + size_t GetNumberOfEntries() const { return number_of_entries_; } + + private: + static constexpr size_t kDefaultNumberOfEntries = 8; + + ArenaAllocator* const allocator_; + + // The number of entries in the set. + size_t number_of_entries_; + + // The internal implementation of the set. It uses a combination of a hash code based + // fixed-size list, and a linked list to handle hash code collisions. + // TODO: Tune the fixed size list original size, and support growing it. + ValueSetNode* collisions_; + HInstruction* table_[kDefaultNumberOfEntries]; + + DISALLOW_COPY_AND_ASSIGN(ValueSet); +}; + +/** + * Optimization phase that removes redundant instruction. + */ +class GlobalValueNumberer : public ValueObject { + public: + GlobalValueNumberer(ArenaAllocator* allocator, HGraph* graph) + : allocator_(allocator), + graph_(graph), + block_effects_(allocator, graph->GetBlocks().Size()), + loop_effects_(allocator, graph->GetBlocks().Size()), + sets_(allocator, graph->GetBlocks().Size()), + visited_(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()); + loop_effects_.Put(i, SideEffects::None()); + } + } + + void Run(); + + private: + // Per-block GVN. Will also update the ValueSet of the dominated and + // successor blocks. + void VisitBasicBlock(HBasicBlock* block); + + // Compute side effects of individual blocks and loops. The GVN algorithm + // will use these side effects to update the ValueSet of individual blocks. + void ComputeSideEffects(); + + void UpdateLoopEffects(HLoopInformation* info, SideEffects effects); + SideEffects GetLoopEffects(HBasicBlock* block) const; + SideEffects GetBlockEffects(HBasicBlock* block) const; + + ArenaAllocator* const allocator_; + HGraph* const graph_; + + // Side effects of individual blocks, that is the union of the side effects + // of the instructions in the block. + GrowableArray block_effects_; + + // Side effects of loops, that is the union of the side effects of the + // blocks contained in that loop. + GrowableArray loop_effects_; + + // ValueSet for blocks. Initially null, but for an individual block they + // are allocated and populated by the dominator, and updated by all blocks + // in the path from the dominator to the block. + GrowableArray sets_; + + // Mark visisted blocks. Only used for debugging. + GrowableArray visited_; + + FRIEND_TEST(GVNTest, LoopSideEffects); + DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_GVN_H_ diff --git a/compiler/optimizing/gvn_test.cc b/compiler/optimizing/gvn_test.cc new file mode 100644 index 0000000000..ad6e3382bc --- /dev/null +++ b/compiler/optimizing/gvn_test.cc @@ -0,0 +1,294 @@ +/* + * Copyright (C) 2014 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "builder.h" +#include "gvn.h" +#include "nodes.h" +#include "optimizing_unit_test.h" +#include "utils/arena_allocator.h" + +#include "gtest/gtest.h" + +namespace art { + +TEST(GVNTest, LocalFieldElimination) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = new (&allocator) HGraph(&allocator); + HBasicBlock* entry = new (&allocator) HBasicBlock(graph); + graph->AddBlock(entry); + graph->SetEntryBlock(entry); + HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot); + entry->AddInstruction(parameter); + + HBasicBlock* block = new (&allocator) HBasicBlock(graph); + graph->AddBlock(block); + entry->AddSuccessor(block); + + block->AddInstruction( + new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, MemberOffset(42))); + block->AddInstruction( + new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, MemberOffset(42))); + HInstruction* to_remove = block->GetLastInstruction(); + block->AddInstruction( + new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, MemberOffset(43))); + HInstruction* different_offset = block->GetLastInstruction(); + // Kill the value. + block->AddInstruction(new (&allocator) HInstanceFieldSet( + parameter, parameter, Primitive::kPrimNot, MemberOffset(42))); + block->AddInstruction( + new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, MemberOffset(42))); + HInstruction* use_after_kill = block->GetLastInstruction(); + block->AddInstruction(new (&allocator) HExit()); + + ASSERT_EQ(to_remove->GetBlock(), block); + ASSERT_EQ(different_offset->GetBlock(), block); + ASSERT_EQ(use_after_kill->GetBlock(), block); + + graph->BuildDominatorTree(); + graph->TransformToSSA(); + GlobalValueNumberer(&allocator, graph).Run(); + + ASSERT_TRUE(to_remove->GetBlock() == nullptr); + ASSERT_EQ(different_offset->GetBlock(), block); + ASSERT_EQ(use_after_kill->GetBlock(), block); +} + +TEST(GVNTest, GlobalFieldElimination) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = new (&allocator) HGraph(&allocator); + HBasicBlock* entry = new (&allocator) HBasicBlock(graph); + graph->AddBlock(entry); + graph->SetEntryBlock(entry); + HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot); + entry->AddInstruction(parameter); + + HBasicBlock* block = new (&allocator) HBasicBlock(graph); + graph->AddBlock(block); + entry->AddSuccessor(block); + block->AddInstruction( + new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42))); + + block->AddInstruction(new (&allocator) HIf(block->GetLastInstruction())); + HBasicBlock* then = new (&allocator) HBasicBlock(graph); + HBasicBlock* else_ = new (&allocator) HBasicBlock(graph); + HBasicBlock* join = new (&allocator) HBasicBlock(graph); + graph->AddBlock(then); + graph->AddBlock(else_); + graph->AddBlock(join); + + block->AddSuccessor(then); + block->AddSuccessor(else_); + then->AddSuccessor(join); + else_->AddSuccessor(join); + + then->AddInstruction( + new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42))); + then->AddInstruction(new (&allocator) HGoto()); + else_->AddInstruction( + new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42))); + else_->AddInstruction(new (&allocator) HGoto()); + join->AddInstruction( + new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42))); + join->AddInstruction(new (&allocator) HExit()); + + graph->BuildDominatorTree(); + graph->TransformToSSA(); + GlobalValueNumberer(&allocator, graph).Run(); + + // Check that all field get instructions have been GVN'ed. + ASSERT_TRUE(then->GetFirstInstruction()->IsGoto()); + ASSERT_TRUE(else_->GetFirstInstruction()->IsGoto()); + ASSERT_TRUE(join->GetFirstInstruction()->IsExit()); +} + +TEST(GVNTest, LoopFieldElimination) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = new (&allocator) HGraph(&allocator); + HBasicBlock* entry = new (&allocator) HBasicBlock(graph); + graph->AddBlock(entry); + graph->SetEntryBlock(entry); + + HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot); + entry->AddInstruction(parameter); + + HBasicBlock* block = new (&allocator) HBasicBlock(graph); + graph->AddBlock(block); + entry->AddSuccessor(block); + block->AddInstruction( + new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42))); + block->AddInstruction(new (&allocator) HGoto()); + + HBasicBlock* loop_header = new (&allocator) HBasicBlock(graph); + HBasicBlock* loop_body = new (&allocator) HBasicBlock(graph); + HBasicBlock* exit = new (&allocator) HBasicBlock(graph); + + graph->AddBlock(loop_header); + graph->AddBlock(loop_body); + graph->AddBlock(exit); + block->AddSuccessor(loop_header); + loop_header->AddSuccessor(loop_body); + loop_header->AddSuccessor(exit); + loop_body->AddSuccessor(loop_header); + + loop_header->AddInstruction( + new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42))); + HInstruction* field_get_in_loop_header = loop_header->GetLastInstruction(); + loop_header->AddInstruction(new (&allocator) HIf(block->GetLastInstruction())); + + // Kill inside the loop body to prevent field gets inside the loop header + // and the body to be GVN'ed. + loop_body->AddInstruction(new (&allocator) HInstanceFieldSet( + parameter, parameter, Primitive::kPrimNot, MemberOffset(42))); + HInstruction* field_set = loop_body->GetLastInstruction(); + loop_body->AddInstruction( + new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42))); + HInstruction* field_get_in_loop_body = loop_body->GetLastInstruction(); + loop_body->AddInstruction(new (&allocator) HGoto()); + + exit->AddInstruction( + new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42))); + HInstruction* field_get_in_exit = exit->GetLastInstruction(); + exit->AddInstruction(new (&allocator) HExit()); + + ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header); + ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body); + ASSERT_EQ(field_get_in_exit->GetBlock(), exit); + + graph->BuildDominatorTree(); + graph->TransformToSSA(); + graph->FindNaturalLoops(); + GlobalValueNumberer(&allocator, graph).Run(); + + // Check that all field get instructions are still there. + ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header); + ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body); + // The exit block is dominated by the loop header, whose field get + // does not get killed by the loop flags. + ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr); + + // Now remove the field set, and check that all field get instructions have been GVN'ed. + loop_body->RemoveInstruction(field_set); + GlobalValueNumberer(&allocator, graph).Run(); + + ASSERT_TRUE(field_get_in_loop_header->GetBlock() == nullptr); + ASSERT_TRUE(field_get_in_loop_body->GetBlock() == nullptr); + ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr); +} + +// Test that inner loops affect the side effects of the outer loop. +TEST(GVNTest, LoopSideEffects) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = new (&allocator) HGraph(&allocator); + HBasicBlock* entry = new (&allocator) HBasicBlock(graph); + graph->AddBlock(entry); + graph->SetEntryBlock(entry); + + HBasicBlock* outer_loop_header = new (&allocator) HBasicBlock(graph); + HBasicBlock* outer_loop_body = new (&allocator) HBasicBlock(graph); + HBasicBlock* outer_loop_exit = new (&allocator) HBasicBlock(graph); + HBasicBlock* inner_loop_header = new (&allocator) HBasicBlock(graph); + HBasicBlock* inner_loop_body = new (&allocator) HBasicBlock(graph); + HBasicBlock* inner_loop_exit = new (&allocator) HBasicBlock(graph); + + graph->AddBlock(outer_loop_header); + graph->AddBlock(outer_loop_body); + graph->AddBlock(outer_loop_exit); + graph->AddBlock(inner_loop_header); + graph->AddBlock(inner_loop_body); + graph->AddBlock(inner_loop_exit); + + entry->AddSuccessor(outer_loop_header); + outer_loop_header->AddSuccessor(outer_loop_body); + outer_loop_header->AddSuccessor(outer_loop_exit); + outer_loop_body->AddSuccessor(inner_loop_header); + inner_loop_header->AddSuccessor(inner_loop_body); + inner_loop_header->AddSuccessor(inner_loop_exit); + inner_loop_body->AddSuccessor(inner_loop_header); + inner_loop_exit->AddSuccessor(outer_loop_header); + + HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimBoolean); + entry->AddInstruction(parameter); + entry->AddInstruction(new (&allocator) HGoto()); + outer_loop_header->AddInstruction(new (&allocator) HIf(parameter)); + outer_loop_body->AddInstruction(new (&allocator) HGoto()); + inner_loop_header->AddInstruction(new (&allocator) HIf(parameter)); + inner_loop_body->AddInstruction(new (&allocator) HGoto()); + inner_loop_exit->AddInstruction(new (&allocator) HGoto()); + outer_loop_exit->AddInstruction(new (&allocator) HExit()); + + graph->BuildDominatorTree(); + graph->TransformToSSA(); + graph->FindNaturalLoops(); + + ASSERT_TRUE(inner_loop_header->GetLoopInformation()->IsIn( + *outer_loop_header->GetLoopInformation())); + + // Check that the loops don't have side effects. + { + // Make one block with a side effect. + entry->AddInstruction(new (&allocator) HInstanceFieldSet( + parameter, parameter, Primitive::kPrimNot, MemberOffset(42))); + + GlobalValueNumberer gvn(&allocator, graph); + gvn.Run(); + + ASSERT_TRUE(gvn.GetBlockEffects(entry).HasSideEffects()); + ASSERT_FALSE(gvn.GetLoopEffects(outer_loop_header).HasSideEffects()); + ASSERT_FALSE(gvn.GetLoopEffects(inner_loop_header).HasSideEffects()); + } + + // Check that the side effects of the outer loop does not affect the inner loop. + { + outer_loop_body->InsertInstructionBefore( + new (&allocator) HInstanceFieldSet( + parameter, parameter, Primitive::kPrimNot, MemberOffset(42)), + outer_loop_body->GetLastInstruction()); + + GlobalValueNumberer gvn(&allocator, graph); + gvn.Run(); + + ASSERT_TRUE(gvn.GetBlockEffects(entry).HasSideEffects()); + ASSERT_TRUE(gvn.GetBlockEffects(outer_loop_body).HasSideEffects()); + ASSERT_TRUE(gvn.GetLoopEffects(outer_loop_header).HasSideEffects()); + ASSERT_FALSE(gvn.GetLoopEffects(inner_loop_header).HasSideEffects()); + } + + // Check that the side effects of the inner loop affects the outer loop. + { + outer_loop_body->RemoveInstruction(outer_loop_body->GetFirstInstruction()); + inner_loop_body->InsertInstructionBefore( + new (&allocator) HInstanceFieldSet( + parameter, parameter, Primitive::kPrimNot, MemberOffset(42)), + inner_loop_body->GetLastInstruction()); + + GlobalValueNumberer gvn(&allocator, graph); + gvn.Run(); + + ASSERT_TRUE(gvn.GetBlockEffects(entry).HasSideEffects()); + ASSERT_FALSE(gvn.GetBlockEffects(outer_loop_body).HasSideEffects()); + ASSERT_TRUE(gvn.GetLoopEffects(outer_loop_header).HasSideEffects()); + ASSERT_TRUE(gvn.GetLoopEffects(inner_loop_header).HasSideEffects()); + } +} +} // namespace art diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 376d1af3ef..1a24677261 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -124,6 +124,7 @@ void HGraph::VisitBlockForDominatorTree(HBasicBlock* block, // dominator of the block. We can then start visiting its successors. if (visits->Get(block->GetBlockId()) == block->GetPredecessors().Size() - block->NumberOfBackEdges()) { + block->GetDominator()->AddDominatedBlock(block); reverse_post_order_.Add(block); for (size_t i = 0; i < block->GetSuccessors().Size(); i++) { VisitBlockForDominatorTree(block->GetSuccessors().Get(i), block, visits); @@ -543,6 +544,7 @@ bool HCondition::NeedsMaterialization() const { bool HInstruction::Equals(HInstruction* other) const { if (!InstructionTypeEquals(other)) return false; + DCHECK_EQ(GetKind(), other->GetKind()); if (!InstructionDataEquals(other)) return false; if (GetType() != other->GetType()) return false; if (InputCount() != other->InputCount()) return false; @@ -550,6 +552,7 @@ bool HInstruction::Equals(HInstruction* other) const { for (size_t i = 0, e = InputCount(); i < e; ++i) { if (InputAt(i) != other->InputAt(i)) return false; } + DCHECK_EQ(ComputeHashCode(), other->ComputeHashCode()); return true; } diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index d98d2ad75f..af173c8087 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -38,6 +38,7 @@ class LocationSummary; static const int kDefaultNumberOfBlocks = 8; static const int kDefaultNumberOfSuccessors = 2; static const int kDefaultNumberOfPredecessors = 2; +static const int kDefaultNumberOfDominatedBlocks = 1; static const int kDefaultNumberOfBackEdges = 1; enum IfCondition { @@ -272,6 +273,7 @@ class HBasicBlock : public ArenaObject { successors_(graph->GetArena(), kDefaultNumberOfSuccessors), loop_information_(nullptr), dominator_(nullptr), + dominated_blocks_(graph->GetArena(), kDefaultNumberOfDominatedBlocks), block_id_(-1), lifetime_start_(kNoLifetime), lifetime_end_(kNoLifetime) {} @@ -284,6 +286,10 @@ class HBasicBlock : public ArenaObject { return successors_; } + const GrowableArray& GetDominatedBlocks() const { + return dominated_blocks_; + } + void AddBackEdge(HBasicBlock* back_edge) { if (loop_information_ == nullptr) { loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_); @@ -299,6 +305,7 @@ class HBasicBlock : public ArenaObject { HBasicBlock* GetDominator() const { return dominator_; } void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; } + void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); } int NumberOfBackEdges() const { return loop_information_ == nullptr @@ -418,6 +425,7 @@ class HBasicBlock : public ArenaObject { HInstructionList phis_; HLoopInformation* loop_information_; HBasicBlock* dominator_; + GrowableArray dominated_blocks_; int block_id_; size_t lifetime_start_; size_t lifetime_end_; @@ -473,6 +481,7 @@ FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) #undef FORWARD_DECLARATION #define DECLARE_INSTRUCTION(type) \ + virtual InstructionKind GetKind() const { return k##type; } \ virtual const char* DebugName() const { return #type; } \ virtual const H##type* As##type() const OVERRIDE { return this; } \ virtual H##type* As##type() OVERRIDE { return this; } \ @@ -504,6 +513,8 @@ class HUseListNode : public ArenaObject { // Represents the side effects an instruction may have. class SideEffects : public ValueObject { public: + SideEffects() : flags_(0) {} + static SideEffects None() { return SideEffects(0); } @@ -521,11 +532,31 @@ class SideEffects : public ValueObject { return SideEffects(((1 << count) - 1) << kFlagChangesCount); } + SideEffects Union(SideEffects other) const { + return SideEffects(flags_ | other.flags_); + } + bool HasSideEffects() const { size_t all_bits_set = (1 << kFlagChangesCount) - 1; return (flags_ & all_bits_set) != 0; } + bool HasAllSideEffects() const { + size_t all_bits_set = (1 << kFlagChangesCount) - 1; + return all_bits_set == (flags_ & all_bits_set); + } + + bool DependsOn(SideEffects other) const { + size_t depends_flags = other.ComputeDependsFlags(); + return (flags_ & depends_flags) != 0; + } + + bool HasDependencies() const { + int count = kFlagDependsOnCount - kFlagChangesCount; + size_t all_bits_set = (1 << count) - 1; + return ((flags_ >> kFlagChangesCount) & all_bits_set) != 0; + } + private: static constexpr int kFlagChangesSomething = 0; static constexpr int kFlagChangesCount = kFlagChangesSomething + 1; @@ -533,10 +564,13 @@ class SideEffects : public ValueObject { static constexpr int kFlagDependsOnSomething = kFlagChangesCount; static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1; - private: explicit SideEffects(size_t flags) : flags_(flags) {} - const size_t flags_; + size_t ComputeDependsFlags() const { + return flags_ << kFlagChangesCount; + } + + size_t flags_; }; class HInstruction : public ArenaObject { @@ -557,6 +591,12 @@ class HInstruction : public ArenaObject { virtual ~HInstruction() {} +#define DECLARE_KIND(type) k##type, + enum InstructionKind { + FOR_EACH_INSTRUCTION(DECLARE_KIND) + }; +#undef DECLARE_KIND + HInstruction* GetNext() const { return next_; } HInstruction* GetPrevious() const { return previous_; } @@ -659,6 +699,18 @@ class HInstruction : public ArenaObject { // 2) Their inputs are identical. bool Equals(HInstruction* other) const; + virtual InstructionKind GetKind() const = 0; + + virtual size_t ComputeHashCode() const { + size_t result = GetKind(); + for (size_t i = 0, e = InputCount(); i < e; ++i) { + result = (result * 31) + InputAt(i)->GetId(); + } + return result; + } + + SideEffects GetSideEffects() const { return side_effects_; } + size_t GetLifetimePosition() const { return lifetime_position_; } void SetLifetimePosition(size_t position) { lifetime_position_ = position; } LiveInterval* GetLiveInterval() const { return live_interval_; } @@ -1258,6 +1310,8 @@ class HIntConstant : public HConstant { return other->AsIntConstant()->value_ == value_; } + virtual size_t ComputeHashCode() const { return GetValue(); } + DECLARE_INSTRUCTION(IntConstant); private: @@ -1276,6 +1330,8 @@ class HLongConstant : public HConstant { return other->AsLongConstant()->value_ == value_; } + virtual size_t ComputeHashCode() const { return static_cast(GetValue()); } + DECLARE_INSTRUCTION(LongConstant); private: @@ -1545,6 +1601,10 @@ class HInstanceFieldGet : public HExpression<1> { return other_offset == GetFieldOffset().SizeValue(); } + virtual size_t ComputeHashCode() const { + return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); + } + MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index 3ce8e7797b..702eba183c 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -25,6 +25,7 @@ #include "driver/compiler_driver.h" #include "driver/dex_compilation_unit.h" #include "graph_visualizer.h" +#include "gvn.h" #include "nodes.h" #include "register_allocator.h" #include "ssa_phi_elimination.h" @@ -260,6 +261,8 @@ CompiledMethod* OptimizingCompiler::TryCompile(const DexFile::CodeItem* code_ite SsaRedundantPhiElimination(graph).Run(); SsaDeadPhiElimination(graph).Run(); + GlobalValueNumberer(graph->GetArena(), graph).Run(); + visualizer.DumpGraph(kGVNPassName); SsaLivenessAnalysis liveness(*graph, codegen); liveness.Analyze(); @@ -300,6 +303,9 @@ CompiledMethod* OptimizingCompiler::TryCompile(const DexFile::CodeItem* code_ite graph->TransformToSSA(); visualizer.DumpGraph("ssa"); graph->FindNaturalLoops(); + SsaRedundantPhiElimination(graph).Run(); + SsaDeadPhiElimination(graph).Run(); + GlobalValueNumberer(graph->GetArena(), graph).Run(); SsaLivenessAnalysis liveness(*graph, codegen); liveness.Analyze(); visualizer.DumpGraph(kLivenessPassName); -- cgit v1.2.3-59-g8ed1b