diff options
| -rw-r--r-- | compiler/optimizing/gvn.cc | 339 |
1 files changed, 210 insertions, 129 deletions
diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc index ea65dc0780..74848d5d96 100644 --- a/compiler/optimizing/gvn.cc +++ b/compiler/optimizing/gvn.cc @@ -16,30 +16,12 @@ #include "gvn.h" #include "side_effects_analysis.h" +#include "utils.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<kArenaAllocMisc> { - public: - ValueSetNode(HInstruction* instruction, size_t hash_code, ValueSetNode* next) - : instruction_(instruction), hash_code_(hash_code), next_(next) {} +#include "utils/arena_bit_vector.h" +#include "base/bit_vector-inl.h" - 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); -}; +namespace art { /** * A ValueSet holds instructions that can replace other instructions. It is updated @@ -52,39 +34,68 @@ class ValueSetNode : public ArenaObject<kArenaAllocMisc> { */ class ValueSet : public ArenaObject<kArenaAllocMisc> { public: + // Constructs an empty ValueSet which owns all its buckets. explicit ValueSet(ArenaAllocator* allocator) - : allocator_(allocator), number_of_entries_(0), collisions_(nullptr) { - for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) { - table_[i] = nullptr; + : allocator_(allocator), + num_buckets_(kMinimumNumberOfBuckets), + buckets_(allocator->AllocArray<Node*>(num_buckets_)), + buckets_owned_(allocator, num_buckets_, false), + num_entries_(0) { + // ArenaAllocator returns zeroed memory, so no need to set buckets to null. + DCHECK(IsPowerOfTwo(num_buckets_)); + buckets_owned_.SetInitialBits(num_buckets_); + } + + // Copy constructor. Depending on the load factor, it will either make a deep + // copy (all buckets owned) or a shallow one (buckets pointing to the parent). + ValueSet(ArenaAllocator* allocator, const ValueSet& to_copy) + : allocator_(allocator), + num_buckets_(to_copy.IdealBucketCount()), + buckets_(allocator->AllocArray<Node*>(num_buckets_)), + buckets_owned_(allocator, num_buckets_, false), + num_entries_(to_copy.num_entries_) { + // ArenaAllocator returns zeroed memory, so entries of buckets_ and + // buckets_owned_ are initialized to nullptr and false, respectively. + DCHECK(IsPowerOfTwo(num_buckets_)); + if (num_buckets_ == to_copy.num_buckets_) { + // Hash table remains the same size. We copy the bucket pointers and leave + // all buckets_owned_ bits false. + memcpy(buckets_, to_copy.buckets_, num_buckets_ * sizeof(Node*)); + } else { + // Hash table size changes. We copy and rehash all entries, and set all + // buckets_owned_ bits to true. + for (size_t i = 0; i < to_copy.num_buckets_; ++i) { + for (Node* node = to_copy.buckets_[i]; node != nullptr; node = node->GetNext()) { + size_t new_index = BucketIndex(node->GetHashCode()); + buckets_[new_index] = node->Dup(allocator_, buckets_[new_index]); + } + } + buckets_owned_.SetInitialBits(num_buckets_); } } // 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_); + size_t hash_code = HashCode(instruction); + size_t index = BucketIndex(hash_code); + + if (!buckets_owned_.IsBitSet(index)) { + CloneBucket(index); } - ++number_of_entries_; + buckets_[index] = new (allocator_) Node(instruction, hash_code, buckets_[index]); + ++num_entries_; } - // If in the set, returns an equivalent instruction to the given instruction. Returns - // null otherwise. + // 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; - } + size_t hash_code = HashCode(instruction); + size_t index = BucketIndex(hash_code); - for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) { + for (Node* node = buckets_[index]; node != nullptr; node = node->GetNext()) { if (node->GetHashCode() == hash_code) { - existing = node->GetInstruction(); + HInstruction* existing = node->GetInstruction(); if (existing->Equals(instruction)) { return existing; } @@ -93,126 +104,193 @@ class ValueSet : public ArenaObject<kArenaAllocMisc> { 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; - } + // Returns whether instruction is in the set. + bool Contains(HInstruction* instruction) const { + size_t hash_code = HashCode(instruction); + size_t index = BucketIndex(hash_code); - for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) { - if (node->GetHashCode() == hash_code) { - existing = node->GetInstruction(); - if (existing == instruction) { - return existing; - } + for (Node* node = buckets_[index]; node != nullptr; node = node->GetNext()) { + if (node->GetInstruction() == instruction) { + return true; } } - return nullptr; + return false; } - // Removes all instructions in the set that are affected by the given side effects. + // Removes all instructions in the set 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_; - } - } + DeleteAllImpureWhich([side_effects](Node* node) { + return node->GetInstruction()->GetSideEffects().DependsOn(side_effects); + }); + } - 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; - } + // Updates this set by intersecting with instructions in a predecessor's set. + void IntersectWith(ValueSet* predecessor) { + if (IsEmpty()) { + return; + } else if (predecessor->IsEmpty()) { + Clear(); + } else { + // Pure instructions do not need to be tested because only impure + // instructions can be killed. + DeleteAllImpureWhich([predecessor](Node* node) { + return !predecessor->Contains(node->GetInstruction()); + }); } } - // Returns a copy of this set. - ValueSet* Copy() const { - ValueSet* copy = new (allocator_) ValueSet(allocator_); + bool IsEmpty() const { return num_entries_ == 0; } + size_t GetNumberOfEntries() const { return num_entries_; } - for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) { - copy->table_[i] = table_[i]; + private: + class Node : public ArenaObject<kArenaAllocMisc> { + public: + Node(HInstruction* instruction, size_t hash_code, Node* next) + : instruction_(instruction), hash_code_(hash_code), next_(next) {} + + size_t GetHashCode() const { return hash_code_; } + HInstruction* GetInstruction() const { return instruction_; } + Node* GetNext() const { return next_; } + void SetNext(Node* node) { next_ = node; } + + Node* Dup(ArenaAllocator* allocator, Node* new_next = nullptr) { + return new (allocator) Node(instruction_, hash_code_, new_next); } - // 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_); + private: + HInstruction* const instruction_; + const size_t hash_code_; + Node* next_; + + DISALLOW_COPY_AND_ASSIGN(Node); + }; + + // Creates our own copy of a bucket that is currently pointing to a parent. + // This algorithm can be called while iterating over the bucket because it + // preserves the order of entries in the bucket and will return the clone of + // the given 'iterator'. + Node* CloneBucket(size_t index, Node* iterator = nullptr) { + DCHECK(!buckets_owned_.IsBitSet(index)); + Node* clone_current = nullptr; + Node* clone_previous = nullptr; + Node* clone_iterator = nullptr; + for (Node* node = buckets_[index]; node != nullptr; node = node->GetNext()) { + clone_current = node->Dup(allocator_, nullptr); + if (node == iterator) { + clone_iterator = clone_current; + } + if (clone_previous == nullptr) { + buckets_[index] = clone_current; + } else { + clone_previous->SetNext(clone_current); + } + clone_previous = clone_current; } - - copy->number_of_entries_ = number_of_entries_; - return copy; + buckets_owned_.SetBit(index); + return clone_iterator; } void Clear() { - number_of_entries_ = 0; - collisions_ = nullptr; - for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) { - table_[i] = nullptr; + num_entries_ = 0; + for (size_t i = 0; i < num_buckets_; ++i) { + buckets_[i] = nullptr; } + buckets_owned_.SetInitialBits(num_buckets_); } - // 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; + // Iterates over buckets with impure instructions (even indices) and deletes + // the ones on which 'cond' returns true. + template<typename Functor> + void DeleteAllImpureWhich(Functor cond) { + for (size_t i = 0; i < num_buckets_; i += 2) { + Node* node = buckets_[i]; + Node* previous = nullptr; + + if (node == nullptr) { + continue; + } + + if (!buckets_owned_.IsBitSet(i)) { + // Bucket is not owned but maybe we won't need to change it at all. + // Iterate as long as the entries don't satisfy 'cond'. + while (node != nullptr) { + if (cond(node)) { + // We do need to delete an entry but we do not own the bucket. + // Clone the bucket, make sure 'previous' and 'node' point to + // the cloned entries and break. + previous = CloneBucket(i, previous); + node = (previous == nullptr) ? buckets_[i] : previous->GetNext(); + break; + } + previous = node; + node = node->GetNext(); } } - for (ValueSetNode* current = collisions_, *previous = nullptr; - current != nullptr; - current = current->GetNext()) { - if (other->IdentityLookup(current->GetInstruction()) == nullptr) { + + // By this point we either own the bucket and can start deleting entries, + // or we do not own it but no entries matched 'cond'. + DCHECK(buckets_owned_.IsBitSet(i) || node == nullptr); + + // We iterate over the remainder of entries and delete those that match + // the given condition. + while (node != nullptr) { + Node* next = node->GetNext(); + if (cond(node)) { if (previous == nullptr) { - collisions_ = current->GetNext(); + buckets_[i] = next; } else { - previous->SetNext(current->GetNext()); + previous->SetNext(next); } - --number_of_entries_; } else { - previous = current; + previous = node; } + node = next; } } } - bool IsEmpty() const { return number_of_entries_ == 0; } - size_t GetNumberOfEntries() const { return number_of_entries_; } + // Computes a bucket count such that the load factor is reasonable. + // This is estimated as (num_entries_ * 1.5) and rounded up to nearest pow2. + size_t IdealBucketCount() const { + size_t bucket_count = RoundUpToPowerOfTwo(num_entries_ + (num_entries_ >> 1)); + if (bucket_count > kMinimumNumberOfBuckets) { + return bucket_count; + } else { + return kMinimumNumberOfBuckets; + } + } - private: - static constexpr size_t kDefaultNumberOfEntries = 8; + // Generates a hash code for an instruction. Pure instructions are put into + // odd buckets to speed up deletion. + size_t HashCode(HInstruction* instruction) const { + size_t hash_code = instruction->ComputeHashCode(); + if (instruction->GetSideEffects().HasDependencies()) { + return (hash_code << 1) | 0; + } else { + return (hash_code << 1) | 1; + } + } + + // Converts a hash code to a bucket index. + size_t BucketIndex(size_t hash_code) const { + return hash_code & (num_buckets_ - 1); + } ArenaAllocator* const allocator_; + // The internal bucket implementation of the set. + size_t const num_buckets_; + Node** const buckets_; + + // Flags specifying which buckets were copied into the set from its parent. + // If a flag is not set, the corresponding bucket points to entries in the + // parent and must be cloned prior to making changes. + ArenaBitVector buckets_owned_; + // The number of entries in the set. - size_t number_of_entries_; + size_t num_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]; + static constexpr size_t kMinimumNumberOfBuckets = 8; DISALLOW_COPY_AND_ASSIGN(ValueSet); }; @@ -270,11 +348,14 @@ void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) { set = new (allocator_) ValueSet(allocator_); } else { HBasicBlock* dominator = block->GetDominator(); - set = sets_.Get(dominator->GetBlockId()); - if (dominator->GetSuccessors().Size() != 1 || dominator->GetSuccessors().Get(0) != block) { + ValueSet* dominator_set = sets_.Get(dominator->GetBlockId()); + if (dominator->GetSuccessors().Size() == 1) { + DCHECK_EQ(dominator->GetSuccessors().Get(0), block); + set = dominator_set; + } else { // We have to copy if the dominator has other successors, or `block` is not a successor // of the dominator. - set = set->Copy(); + set = new (allocator_) ValueSet(allocator_, *dominator_set); } if (!set->IsEmpty()) { if (block->IsLoopHeader()) { @@ -282,7 +363,7 @@ void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) { 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())); + set->IntersectWith(sets_.Get(predecessors.Get(i)->GetBlockId())); if (set->IsEmpty()) { break; } |