diff options
Diffstat (limited to 'compiler/optimizing')
-rw-r--r-- | compiler/optimizing/bounds_check_elimination_test.cc | 3 | ||||
-rw-r--r-- | compiler/optimizing/gvn.cc | 270 | ||||
-rw-r--r-- | compiler/optimizing/gvn.h | 272 | ||||
-rw-r--r-- | compiler/optimizing/gvn_test.cc | 9 | ||||
-rw-r--r-- | compiler/optimizing/optimizing_compiler.cc | 1 | ||||
-rw-r--r-- | compiler/optimizing/side_effects_analysis.cc | 83 | ||||
-rw-r--r-- | compiler/optimizing/side_effects_analysis.h | 64 |
7 files changed, 379 insertions, 323 deletions
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc index d5de3efa62..b6aaab5ef5 100644 --- a/compiler/optimizing/bounds_check_elimination_test.cc +++ b/compiler/optimizing/bounds_check_elimination_test.cc @@ -19,6 +19,7 @@ #include "gvn.h" #include "nodes.h" #include "optimizing_unit_test.h" +#include "side_effects_analysis.h" #include "utils/arena_allocator.h" #include "gtest/gtest.h" @@ -28,7 +29,7 @@ namespace art { static void RunGvn(HGraph* graph) { SideEffectsAnalysis side_effects(graph); side_effects.Run(); - GlobalValueNumberer(graph->GetArena(), graph, side_effects).Run(); + GVNOptimization(graph, side_effects).Run(); } // if (i < 0) { array[i] = 1; // Can't eliminate. } diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc index 781aad5c72..89bba2d9f6 100644 --- a/compiler/optimizing/gvn.cc +++ b/compiler/optimizing/gvn.cc @@ -15,70 +15,239 @@ */ #include "gvn.h" +#include "side_effects_analysis.h" namespace art { -void SideEffectsAnalysis::UpdateLoopEffects(HLoopInformation* info, SideEffects effects) { - int id = info->GetHeader()->GetBlockId(); - loop_effects_.Put(id, loop_effects_.Get(id).Union(effects)); -} +/** + * 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<kArenaAllocMisc> { + public: + ValueSetNode(HInstruction* instruction, size_t hash_code, ValueSetNode* next) + : instruction_(instruction), hash_code_(hash_code), next_(next) {} -void SideEffectsAnalysis::Run() { - 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()); + 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<kArenaAllocMisc> { + 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; } - // 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 inst_it(block->GetInstructions()); !inst_it.Done(); - inst_it.Advance()) { - HInstruction* instruction = inst_it.Current(); - effects = effects.Union(instruction->GetSideEffects()); - if (effects.HasAllSideEffects()) { - break; + // 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; + } - 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)); + // 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_; + } + } + + for (ValueSetNode* current = collisions_, *previous = nullptr; + current != nullptr; + current = current->GetNext()) { + 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; } - } else if (block->IsInLoop()) { - // Update the side effects of the loop with the side effects of this block. - UpdateLoopEffects(block->GetLoopInformation(), effects); } } - has_run_ = true; -} -SideEffects SideEffectsAnalysis::GetLoopEffects(HBasicBlock* block) const { - DCHECK(block->IsLoopHeader()); - return loop_effects_.Get(block->GetBlockId()); -} + // Returns a copy of this set. + ValueSet* Copy() const { + ValueSet* copy = new (allocator_) ValueSet(allocator_); -SideEffects SideEffectsAnalysis::GetBlockEffects(HBasicBlock* block) const { - return block_effects_.Get(block->GetBlockId()); -} + 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; + } + + 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_; } + + 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, + const SideEffectsAnalysis& side_effects) + : graph_(graph), + allocator_(allocator), + side_effects_(side_effects), + sets_(allocator, graph->GetBlocks().Size(), nullptr) {} + + void Run(); + + private: + // Per-block GVN. Will also update the ValueSet of the dominated and + // successor blocks. + void VisitBasicBlock(HBasicBlock* block); + + HGraph* graph_; + ArenaAllocator* const allocator_; + const SideEffectsAnalysis& side_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<ValueSet*> sets_; + + DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer); +}; void GlobalValueNumberer::Run() { DCHECK(side_effects_.HasRun()); @@ -142,4 +311,9 @@ void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) { } } +void GVNOptimization::Run() { + GlobalValueNumberer gvn(graph_->GetArena(), graph_, side_effects_); + gvn.Run(); +} + } // namespace art diff --git a/compiler/optimizing/gvn.h b/compiler/optimizing/gvn.h index 2e38511532..57e0487fca 100644 --- a/compiler/optimizing/gvn.h +++ b/compiler/optimizing/gvn.h @@ -22,282 +22,14 @@ 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<kArenaAllocMisc> { - 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<kArenaAllocMisc> { - 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; - } - - // 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) { - HInstruction* instruction = table_[i]; - if (instruction != nullptr && instruction->GetSideEffects().DependsOn(side_effects)) { - table_[i] = nullptr; - --number_of_entries_; - } - } - - for (ValueSetNode* current = collisions_, *previous = nullptr; - current != nullptr; - current = current->GetNext()) { - 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; - } - } - } - - // 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; - } - - 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_; } - - 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); -}; - -class SideEffectsAnalysis : public HOptimization { - public: - explicit SideEffectsAnalysis(HGraph* graph) - : HOptimization(graph, true, "SideEffects"), - graph_(graph), - block_effects_(graph->GetArena(), graph->GetBlocks().Size(), SideEffects::None()), - loop_effects_(graph->GetArena(), graph->GetBlocks().Size(), SideEffects::None()) {} - - SideEffects GetLoopEffects(HBasicBlock* block) const; - SideEffects GetBlockEffects(HBasicBlock* block) const; - - // Compute side effects of individual blocks and loops. - void Run(); - - bool HasRun() const { return has_run_; } - - private: - void UpdateLoopEffects(HLoopInformation* info, SideEffects effects); - - HGraph* graph_; - - // Checked in debug build, to ensure the pass has been run prior to - // running a pass that depends on it. - bool has_run_ = false; - - // Side effects of individual blocks, that is the union of the side effects - // of the instructions in the block. - GrowableArray<SideEffects> block_effects_; - - // Side effects of loops, that is the union of the side effects of the - // blocks contained in that loop. - GrowableArray<SideEffects> loop_effects_; - - ART_FRIEND_TEST(GVNTest, LoopSideEffects); - DISALLOW_COPY_AND_ASSIGN(SideEffectsAnalysis); -}; - -/** - * Optimization phase that removes redundant instruction. - */ -class GlobalValueNumberer : public ValueObject { - public: - GlobalValueNumberer(ArenaAllocator* allocator, - HGraph* graph, - const SideEffectsAnalysis& side_effects) - : graph_(graph), - allocator_(allocator), - side_effects_(side_effects), - sets_(allocator, graph->GetBlocks().Size(), nullptr) {} - - void Run(); - - private: - // Per-block GVN. Will also update the ValueSet of the dominated and - // successor blocks. - void VisitBasicBlock(HBasicBlock* block); - - HGraph* graph_; - ArenaAllocator* const allocator_; - const SideEffectsAnalysis& side_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<ValueSet*> sets_; - - DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer); -}; +class SideEffectsAnalysis; class GVNOptimization : public HOptimization { public: GVNOptimization(HGraph* graph, const SideEffectsAnalysis& side_effects) : HOptimization(graph, true, "GVN"), side_effects_(side_effects) {} - void Run() OVERRIDE { - GlobalValueNumberer gvn(graph_->GetArena(), graph_, side_effects_); - gvn.Run(); - } + void Run() OVERRIDE; private: const SideEffectsAnalysis& side_effects_; diff --git a/compiler/optimizing/gvn_test.cc b/compiler/optimizing/gvn_test.cc index 9e630a7db0..4a48fee2fb 100644 --- a/compiler/optimizing/gvn_test.cc +++ b/compiler/optimizing/gvn_test.cc @@ -18,6 +18,7 @@ #include "gvn.h" #include "nodes.h" #include "optimizing_unit_test.h" +#include "side_effects_analysis.h" #include "utils/arena_allocator.h" #include "gtest/gtest.h" @@ -66,7 +67,7 @@ TEST(GVNTest, LocalFieldElimination) { graph->TryBuildingSsa(); SideEffectsAnalysis side_effects(graph); side_effects.Run(); - GlobalValueNumberer(&allocator, graph, side_effects).Run(); + GVNOptimization(graph, side_effects).Run(); ASSERT_TRUE(to_remove->GetBlock() == nullptr); ASSERT_EQ(different_offset->GetBlock(), block); @@ -120,7 +121,7 @@ TEST(GVNTest, GlobalFieldElimination) { graph->TryBuildingSsa(); SideEffectsAnalysis side_effects(graph); side_effects.Run(); - GlobalValueNumberer(&allocator, graph, side_effects).Run(); + GVNOptimization(graph, side_effects).Run(); // Check that all field get instructions have been GVN'ed. ASSERT_TRUE(then->GetFirstInstruction()->IsGoto()); @@ -191,7 +192,7 @@ TEST(GVNTest, LoopFieldElimination) { { SideEffectsAnalysis side_effects(graph); side_effects.Run(); - GlobalValueNumberer(&allocator, graph, side_effects).Run(); + GVNOptimization(graph, side_effects).Run(); } // Check that all field get instructions are still there. @@ -206,7 +207,7 @@ TEST(GVNTest, LoopFieldElimination) { { SideEffectsAnalysis side_effects(graph); side_effects.Run(); - GlobalValueNumberer(&allocator, graph, side_effects).Run(); + GVNOptimization(graph, side_effects).Run(); } ASSERT_TRUE(field_get_in_loop_header->GetBlock() == nullptr); diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index 7f99edb0a8..a590c439a9 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -39,6 +39,7 @@ #include "nodes.h" #include "prepare_for_register_allocation.h" #include "register_allocator.h" +#include "side_effects_analysis.h" #include "ssa_builder.h" #include "ssa_phi_elimination.h" #include "ssa_liveness_analysis.h" diff --git a/compiler/optimizing/side_effects_analysis.cc b/compiler/optimizing/side_effects_analysis.cc new file mode 100644 index 0000000000..96e1c8f8eb --- /dev/null +++ b/compiler/optimizing/side_effects_analysis.cc @@ -0,0 +1,83 @@ +/* + * 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 "side_effects_analysis.h" + +namespace art { + +void SideEffectsAnalysis::Run() { + 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 inst_it(block->GetInstructions()); !inst_it.Done(); + inst_it.Advance()) { + HInstruction* instruction = inst_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); + } + } + has_run_ = true; +} + +SideEffects SideEffectsAnalysis::GetLoopEffects(HBasicBlock* block) const { + DCHECK(block->IsLoopHeader()); + return loop_effects_.Get(block->GetBlockId()); +} + +SideEffects SideEffectsAnalysis::GetBlockEffects(HBasicBlock* block) const { + return block_effects_.Get(block->GetBlockId()); +} + +void SideEffectsAnalysis::UpdateLoopEffects(HLoopInformation* info, SideEffects effects) { + int id = info->GetHeader()->GetBlockId(); + loop_effects_.Put(id, loop_effects_.Get(id).Union(effects)); +} + +} // namespace art diff --git a/compiler/optimizing/side_effects_analysis.h b/compiler/optimizing/side_effects_analysis.h new file mode 100644 index 0000000000..f1c98ac218 --- /dev/null +++ b/compiler/optimizing/side_effects_analysis.h @@ -0,0 +1,64 @@ +/* + * 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_SIDE_EFFECTS_ANALYSIS_H_ +#define ART_COMPILER_OPTIMIZING_SIDE_EFFECTS_ANALYSIS_H_ + +#include "nodes.h" +#include "optimization.h" + +namespace art { + +class SideEffectsAnalysis : public HOptimization { + public: + explicit SideEffectsAnalysis(HGraph* graph) + : HOptimization(graph, true, "SideEffects"), + graph_(graph), + block_effects_(graph->GetArena(), graph->GetBlocks().Size(), SideEffects::None()), + loop_effects_(graph->GetArena(), graph->GetBlocks().Size(), SideEffects::None()) {} + + SideEffects GetLoopEffects(HBasicBlock* block) const; + SideEffects GetBlockEffects(HBasicBlock* block) const; + + // Compute side effects of individual blocks and loops. + void Run(); + + bool HasRun() const { return has_run_; } + + private: + void UpdateLoopEffects(HLoopInformation* info, SideEffects effects); + + HGraph* graph_; + + // Checked in debug build, to ensure the pass has been run prior to + // running a pass that depends on it. + bool has_run_ = false; + + // Side effects of individual blocks, that is the union of the side effects + // of the instructions in the block. + GrowableArray<SideEffects> block_effects_; + + // Side effects of loops, that is the union of the side effects of the + // blocks contained in that loop. + GrowableArray<SideEffects> loop_effects_; + + ART_FRIEND_TEST(GVNTest, LoopSideEffects); + DISALLOW_COPY_AND_ASSIGN(SideEffectsAnalysis); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_SIDE_EFFECTS_ANALYSIS_H_ |