/* * 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" #include "side_effects_analysis.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; } // 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); }; /** * 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 sets_; DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer); }; void GlobalValueNumberer::Run() { DCHECK(side_effects_.HasRun()); sets_.Put(graph_->GetEntryBlock()->GetBlockId(), new (allocator_) ValueSet(allocator_)); // Use the 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::VisitBasicBlock(HBasicBlock* block) { ValueSet* set = nullptr; const GrowableArray& 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(); } if (!set->IsEmpty()) { if (block->IsLoopHeader()) { DCHECK_EQ(block->GetDominator(), block->GetLoopInformation()->GetPreHeader()); set->Kill(side_effects_.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; } } } } } sets_.Put(block->GetBlockId(), set); 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; } } void GVNOptimization::Run() { GlobalValueNumberer gvn(graph_->GetArena(), graph_, side_effects_); gvn.Run(); } } // namespace art