Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2014 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | #include "gvn.h" |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 18 | |
Mathieu Chartier | e5d80f8 | 2015-10-15 17:47:48 -0700 | [diff] [blame] | 19 | #include "base/arena_bit_vector.h" |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 20 | #include "base/scoped_arena_allocator.h" |
| 21 | #include "base/scoped_arena_containers.h" |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 22 | #include "base/bit_vector-inl.h" |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 23 | #include "side_effects_analysis.h" |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 24 | #include "utils.h" |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 25 | |
| 26 | namespace art { |
| 27 | |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 28 | /** |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 29 | * A ValueSet holds instructions that can replace other instructions. It is updated |
| 30 | * through the `Add` method, and the `Kill` method. The `Kill` method removes |
| 31 | * instructions that are affected by the given side effect. |
| 32 | * |
| 33 | * The `Lookup` method returns an equivalent instruction to the given instruction |
| 34 | * if there is one in the set. In GVN, we would say those instructions have the |
| 35 | * same "number". |
| 36 | */ |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 37 | class ValueSet : public ArenaObject<kArenaAllocGvn> { |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 38 | public: |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 39 | // Constructs an empty ValueSet which owns all its buckets. |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 40 | explicit ValueSet(ScopedArenaAllocator* allocator) |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 41 | : allocator_(allocator), |
| 42 | num_buckets_(kMinimumNumberOfBuckets), |
Vladimir Marko | 5233f93 | 2015-09-29 19:01:15 +0100 | [diff] [blame] | 43 | buckets_(allocator->AllocArray<Node*>(num_buckets_, kArenaAllocGvn)), |
Vladimir Marko | f6a35de | 2016-03-21 12:01:50 +0000 | [diff] [blame] | 44 | buckets_owned_(allocator, num_buckets_, false, kArenaAllocGvn), |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 45 | num_entries_(0u) { |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 46 | // ArenaAllocator returns zeroed memory, so no need to set buckets to null. |
| 47 | DCHECK(IsPowerOfTwo(num_buckets_)); |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 48 | std::fill_n(buckets_, num_buckets_, nullptr); |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 49 | buckets_owned_.SetInitialBits(num_buckets_); |
| 50 | } |
| 51 | |
| 52 | // Copy constructor. Depending on the load factor, it will either make a deep |
| 53 | // copy (all buckets owned) or a shallow one (buckets pointing to the parent). |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 54 | ValueSet(ScopedArenaAllocator* allocator, const ValueSet& other) |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 55 | : allocator_(allocator), |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 56 | num_buckets_(other.IdealBucketCount()), |
Vladimir Marko | 5233f93 | 2015-09-29 19:01:15 +0100 | [diff] [blame] | 57 | buckets_(allocator->AllocArray<Node*>(num_buckets_, kArenaAllocGvn)), |
Vladimir Marko | f6a35de | 2016-03-21 12:01:50 +0000 | [diff] [blame] | 58 | buckets_owned_(allocator, num_buckets_, false, kArenaAllocGvn), |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 59 | num_entries_(0u) { |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 60 | // ArenaAllocator returns zeroed memory, so entries of buckets_ and |
Mathieu Chartier | 2cebb24 | 2015-04-21 16:50:40 -0700 | [diff] [blame] | 61 | // buckets_owned_ are initialized to null and false, respectively. |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 62 | DCHECK(IsPowerOfTwo(num_buckets_)); |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 63 | PopulateFromInternal(other); |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 64 | } |
| 65 | |
| 66 | // Erases all values in this set and populates it with values from `other`. |
| 67 | void PopulateFrom(const ValueSet& other) { |
| 68 | if (this == &other) { |
| 69 | return; |
| 70 | } |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 71 | PopulateFromInternal(other); |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 72 | } |
| 73 | |
| 74 | // Returns true if `this` has enough buckets so that if `other` is copied into |
| 75 | // it, the load factor will not cross the upper threshold. |
David Brazdil | d974379 | 2016-04-21 14:00:15 +0100 | [diff] [blame] | 76 | // If `exact_match` is set, true is returned only if `this` has the ideal |
| 77 | // number of buckets. Larger number of buckets is allowed otherwise. |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 78 | bool CanHoldCopyOf(const ValueSet& other, bool exact_match) { |
| 79 | if (exact_match) { |
| 80 | return other.IdealBucketCount() == num_buckets_; |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 81 | } else { |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 82 | return other.IdealBucketCount() <= num_buckets_; |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 83 | } |
| 84 | } |
| 85 | |
| 86 | // Adds an instruction in the set. |
| 87 | void Add(HInstruction* instruction) { |
| 88 | DCHECK(Lookup(instruction) == nullptr); |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 89 | size_t hash_code = HashCode(instruction); |
| 90 | size_t index = BucketIndex(hash_code); |
| 91 | |
| 92 | if (!buckets_owned_.IsBitSet(index)) { |
| 93 | CloneBucket(index); |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 94 | } |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 95 | buckets_[index] = new (allocator_) Node(instruction, hash_code, buckets_[index]); |
| 96 | ++num_entries_; |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 97 | } |
| 98 | |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 99 | // If in the set, returns an equivalent instruction to the given instruction. |
| 100 | // Returns null otherwise. |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 101 | HInstruction* Lookup(HInstruction* instruction) const { |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 102 | size_t hash_code = HashCode(instruction); |
| 103 | size_t index = BucketIndex(hash_code); |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 104 | |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 105 | for (Node* node = buckets_[index]; node != nullptr; node = node->GetNext()) { |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 106 | if (node->GetHashCode() == hash_code) { |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 107 | HInstruction* existing = node->GetInstruction(); |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 108 | if (existing->Equals(instruction)) { |
| 109 | return existing; |
| 110 | } |
| 111 | } |
| 112 | } |
| 113 | return nullptr; |
| 114 | } |
| 115 | |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 116 | // Returns whether instruction is in the set. |
| 117 | bool Contains(HInstruction* instruction) const { |
| 118 | size_t hash_code = HashCode(instruction); |
| 119 | size_t index = BucketIndex(hash_code); |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 120 | |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 121 | for (Node* node = buckets_[index]; node != nullptr; node = node->GetNext()) { |
| 122 | if (node->GetInstruction() == instruction) { |
| 123 | return true; |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 124 | } |
| 125 | } |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 126 | return false; |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 127 | } |
| 128 | |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 129 | // Removes all instructions in the set affected by the given side effects. |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 130 | void Kill(SideEffects side_effects) { |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 131 | DeleteAllImpureWhich([side_effects](Node* node) { |
Aart Bik | 854a02b | 2015-07-14 16:07:00 -0700 | [diff] [blame] | 132 | return node->GetInstruction()->GetSideEffects().MayDependOn(side_effects); |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 133 | }); |
| 134 | } |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 135 | |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 136 | void Clear() { |
| 137 | num_entries_ = 0; |
| 138 | for (size_t i = 0; i < num_buckets_; ++i) { |
| 139 | buckets_[i] = nullptr; |
| 140 | } |
| 141 | buckets_owned_.SetInitialBits(num_buckets_); |
| 142 | } |
| 143 | |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 144 | // Updates this set by intersecting with instructions in a predecessor's set. |
| 145 | void IntersectWith(ValueSet* predecessor) { |
| 146 | if (IsEmpty()) { |
| 147 | return; |
| 148 | } else if (predecessor->IsEmpty()) { |
| 149 | Clear(); |
| 150 | } else { |
| 151 | // Pure instructions do not need to be tested because only impure |
| 152 | // instructions can be killed. |
| 153 | DeleteAllImpureWhich([predecessor](Node* node) { |
| 154 | return !predecessor->Contains(node->GetInstruction()); |
| 155 | }); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 156 | } |
| 157 | } |
| 158 | |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 159 | bool IsEmpty() const { return num_entries_ == 0; } |
| 160 | size_t GetNumberOfEntries() const { return num_entries_; } |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 161 | |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 162 | private: |
David Brazdil | d974379 | 2016-04-21 14:00:15 +0100 | [diff] [blame] | 163 | // Copies all entries from `other` to `this`. |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 164 | void PopulateFromInternal(const ValueSet& other) { |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 165 | DCHECK_NE(this, &other); |
| 166 | DCHECK_GE(num_buckets_, other.IdealBucketCount()); |
| 167 | |
| 168 | if (num_buckets_ == other.num_buckets_) { |
| 169 | // Hash table remains the same size. We copy the bucket pointers and leave |
| 170 | // all buckets_owned_ bits false. |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 171 | buckets_owned_.ClearAllBits(); |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 172 | memcpy(buckets_, other.buckets_, num_buckets_ * sizeof(Node*)); |
| 173 | } else { |
| 174 | // Hash table size changes. We copy and rehash all entries, and set all |
| 175 | // buckets_owned_ bits to true. |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 176 | std::fill_n(buckets_, num_buckets_, nullptr); |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 177 | for (size_t i = 0; i < other.num_buckets_; ++i) { |
| 178 | for (Node* node = other.buckets_[i]; node != nullptr; node = node->GetNext()) { |
| 179 | size_t new_index = BucketIndex(node->GetHashCode()); |
| 180 | buckets_[new_index] = node->Dup(allocator_, buckets_[new_index]); |
| 181 | } |
| 182 | } |
| 183 | buckets_owned_.SetInitialBits(num_buckets_); |
| 184 | } |
| 185 | |
| 186 | num_entries_ = other.num_entries_; |
| 187 | } |
| 188 | |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 189 | class Node : public ArenaObject<kArenaAllocGvn> { |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 190 | public: |
| 191 | Node(HInstruction* instruction, size_t hash_code, Node* next) |
| 192 | : instruction_(instruction), hash_code_(hash_code), next_(next) {} |
| 193 | |
| 194 | size_t GetHashCode() const { return hash_code_; } |
| 195 | HInstruction* GetInstruction() const { return instruction_; } |
| 196 | Node* GetNext() const { return next_; } |
| 197 | void SetNext(Node* node) { next_ = node; } |
| 198 | |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 199 | Node* Dup(ScopedArenaAllocator* allocator, Node* new_next = nullptr) { |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 200 | return new (allocator) Node(instruction_, hash_code_, new_next); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 201 | } |
| 202 | |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 203 | private: |
| 204 | HInstruction* const instruction_; |
| 205 | const size_t hash_code_; |
| 206 | Node* next_; |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 207 | |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 208 | DISALLOW_COPY_AND_ASSIGN(Node); |
| 209 | }; |
| 210 | |
| 211 | // Creates our own copy of a bucket that is currently pointing to a parent. |
| 212 | // This algorithm can be called while iterating over the bucket because it |
| 213 | // preserves the order of entries in the bucket and will return the clone of |
| 214 | // the given 'iterator'. |
| 215 | Node* CloneBucket(size_t index, Node* iterator = nullptr) { |
| 216 | DCHECK(!buckets_owned_.IsBitSet(index)); |
| 217 | Node* clone_current = nullptr; |
| 218 | Node* clone_previous = nullptr; |
| 219 | Node* clone_iterator = nullptr; |
| 220 | for (Node* node = buckets_[index]; node != nullptr; node = node->GetNext()) { |
| 221 | clone_current = node->Dup(allocator_, nullptr); |
| 222 | if (node == iterator) { |
| 223 | clone_iterator = clone_current; |
| 224 | } |
| 225 | if (clone_previous == nullptr) { |
| 226 | buckets_[index] = clone_current; |
| 227 | } else { |
| 228 | clone_previous->SetNext(clone_current); |
| 229 | } |
| 230 | clone_previous = clone_current; |
| 231 | } |
| 232 | buckets_owned_.SetBit(index); |
| 233 | return clone_iterator; |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 234 | } |
| 235 | |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 236 | // Iterates over buckets with impure instructions (even indices) and deletes |
| 237 | // the ones on which 'cond' returns true. |
| 238 | template<typename Functor> |
| 239 | void DeleteAllImpureWhich(Functor cond) { |
| 240 | for (size_t i = 0; i < num_buckets_; i += 2) { |
| 241 | Node* node = buckets_[i]; |
| 242 | Node* previous = nullptr; |
| 243 | |
| 244 | if (node == nullptr) { |
| 245 | continue; |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 246 | } |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 247 | |
| 248 | if (!buckets_owned_.IsBitSet(i)) { |
| 249 | // Bucket is not owned but maybe we won't need to change it at all. |
| 250 | // Iterate as long as the entries don't satisfy 'cond'. |
| 251 | while (node != nullptr) { |
| 252 | if (cond(node)) { |
| 253 | // We do need to delete an entry but we do not own the bucket. |
| 254 | // Clone the bucket, make sure 'previous' and 'node' point to |
| 255 | // the cloned entries and break. |
| 256 | previous = CloneBucket(i, previous); |
| 257 | node = (previous == nullptr) ? buckets_[i] : previous->GetNext(); |
| 258 | break; |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 259 | } |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 260 | previous = node; |
| 261 | node = node->GetNext(); |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 262 | } |
| 263 | } |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 264 | |
| 265 | // By this point we either own the bucket and can start deleting entries, |
| 266 | // or we do not own it but no entries matched 'cond'. |
| 267 | DCHECK(buckets_owned_.IsBitSet(i) || node == nullptr); |
| 268 | |
| 269 | // We iterate over the remainder of entries and delete those that match |
| 270 | // the given condition. |
| 271 | while (node != nullptr) { |
| 272 | Node* next = node->GetNext(); |
| 273 | if (cond(node)) { |
| 274 | if (previous == nullptr) { |
| 275 | buckets_[i] = next; |
| 276 | } else { |
| 277 | previous->SetNext(next); |
| 278 | } |
| 279 | } else { |
| 280 | previous = node; |
| 281 | } |
| 282 | node = next; |
| 283 | } |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 284 | } |
| 285 | } |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 286 | |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 287 | // Computes a bucket count such that the load factor is reasonable. |
| 288 | // This is estimated as (num_entries_ * 1.5) and rounded up to nearest pow2. |
| 289 | size_t IdealBucketCount() const { |
| 290 | size_t bucket_count = RoundUpToPowerOfTwo(num_entries_ + (num_entries_ >> 1)); |
| 291 | if (bucket_count > kMinimumNumberOfBuckets) { |
| 292 | return bucket_count; |
| 293 | } else { |
| 294 | return kMinimumNumberOfBuckets; |
| 295 | } |
| 296 | } |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 297 | |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 298 | // Generates a hash code for an instruction. |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 299 | size_t HashCode(HInstruction* instruction) const { |
| 300 | size_t hash_code = instruction->ComputeHashCode(); |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 301 | // Pure instructions are put into odd buckets to speed up deletion. Note that in the |
| 302 | // case of irreducible loops, we don't put pure instructions in odd buckets, as we |
| 303 | // need to delete them when entering the loop. |
Mingyao Yang | 217eb06 | 2017-12-11 15:20:07 -0800 | [diff] [blame] | 304 | // ClinitCheck is treated as a pure instruction since it's only executed |
| 305 | // once. |
| 306 | bool pure = !instruction->GetSideEffects().HasDependencies() || |
| 307 | instruction->IsClinitCheck(); |
| 308 | if (!pure || instruction->GetBlock()->GetGraph()->HasIrreducibleLoops()) { |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 309 | return (hash_code << 1) | 0; |
| 310 | } else { |
| 311 | return (hash_code << 1) | 1; |
| 312 | } |
| 313 | } |
| 314 | |
| 315 | // Converts a hash code to a bucket index. |
| 316 | size_t BucketIndex(size_t hash_code) const { |
| 317 | return hash_code & (num_buckets_ - 1); |
| 318 | } |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 319 | |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 320 | ScopedArenaAllocator* const allocator_; |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 321 | |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 322 | // The internal bucket implementation of the set. |
| 323 | size_t const num_buckets_; |
| 324 | Node** const buckets_; |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 325 | |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 326 | // Flags specifying which buckets were copied into the set from its parent. |
| 327 | // If a flag is not set, the corresponding bucket points to entries in the |
| 328 | // parent and must be cloned prior to making changes. |
| 329 | ArenaBitVector buckets_owned_; |
| 330 | |
| 331 | // The number of entries in the set. |
| 332 | size_t num_entries_; |
| 333 | |
| 334 | static constexpr size_t kMinimumNumberOfBuckets = 8; |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 335 | |
| 336 | DISALLOW_COPY_AND_ASSIGN(ValueSet); |
| 337 | }; |
| 338 | |
| 339 | /** |
| 340 | * Optimization phase that removes redundant instruction. |
| 341 | */ |
| 342 | class GlobalValueNumberer : public ValueObject { |
| 343 | public: |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 344 | GlobalValueNumberer(HGraph* graph, |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 345 | const SideEffectsAnalysis& side_effects) |
| 346 | : graph_(graph), |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 347 | allocator_(graph->GetArenaStack()), |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 348 | side_effects_(side_effects), |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 349 | sets_(graph->GetBlocks().size(), nullptr, allocator_.Adapter(kArenaAllocGvn)), |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 350 | visited_blocks_( |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 351 | &allocator_, graph->GetBlocks().size(), /* expandable */ false, kArenaAllocGvn) { |
| 352 | visited_blocks_.ClearAllBits(); |
| 353 | } |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 354 | |
| 355 | void Run(); |
| 356 | |
| 357 | private: |
| 358 | // Per-block GVN. Will also update the ValueSet of the dominated and |
| 359 | // successor blocks. |
| 360 | void VisitBasicBlock(HBasicBlock* block); |
| 361 | |
| 362 | HGraph* graph_; |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 363 | ScopedArenaAllocator allocator_; |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 364 | const SideEffectsAnalysis& side_effects_; |
| 365 | |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 366 | ValueSet* FindSetFor(HBasicBlock* block) const { |
| 367 | ValueSet* result = sets_[block->GetBlockId()]; |
| 368 | DCHECK(result != nullptr) << "Could not find set for block B" << block->GetBlockId(); |
| 369 | return result; |
| 370 | } |
| 371 | |
| 372 | void AbandonSetFor(HBasicBlock* block) { |
| 373 | DCHECK(sets_[block->GetBlockId()] != nullptr) |
| 374 | << "Block B" << block->GetBlockId() << " expected to have a set"; |
| 375 | sets_[block->GetBlockId()] = nullptr; |
| 376 | } |
| 377 | |
| 378 | // Returns false if the GlobalValueNumberer has already visited all blocks |
| 379 | // which may reference `block`. |
| 380 | bool WillBeReferencedAgain(HBasicBlock* block) const; |
| 381 | |
| 382 | // Iterates over visited blocks and finds one which has a ValueSet such that: |
| 383 | // (a) it will not be referenced in the future, and |
| 384 | // (b) it can hold a copy of `reference_set` with a reasonable load factor. |
| 385 | HBasicBlock* FindVisitedBlockWithRecyclableSet(HBasicBlock* block, |
| 386 | const ValueSet& reference_set) const; |
| 387 | |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 388 | // ValueSet for blocks. Initially null, but for an individual block they |
| 389 | // are allocated and populated by the dominator, and updated by all blocks |
| 390 | // in the path from the dominator to the block. |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 391 | ScopedArenaVector<ValueSet*> sets_; |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 392 | |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 393 | // BitVector which serves as a fast-access map from block id to |
Roland Levillain | 5e8d5f0 | 2016-10-18 18:03:43 +0100 | [diff] [blame] | 394 | // visited/unvisited Boolean. |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 395 | ArenaBitVector visited_blocks_; |
| 396 | |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 397 | DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer); |
| 398 | }; |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 399 | |
Nicolas Geoffray | 86dde16 | 2015-01-26 12:54:33 +0000 | [diff] [blame] | 400 | void GlobalValueNumberer::Run() { |
| 401 | DCHECK(side_effects_.HasRun()); |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 402 | sets_[graph_->GetEntryBlock()->GetBlockId()] = new (&allocator_) ValueSet(&allocator_); |
Nicolas Geoffray | 86dde16 | 2015-01-26 12:54:33 +0000 | [diff] [blame] | 403 | |
| 404 | // Use the reverse post order to ensure the non back-edge predecessors of a block are |
| 405 | // visited before the block itself. |
Vladimir Marko | 2c45bc9 | 2016-10-25 16:54:12 +0100 | [diff] [blame] | 406 | for (HBasicBlock* block : graph_->GetReversePostOrder()) { |
| 407 | VisitBasicBlock(block); |
Nicolas Geoffray | 86dde16 | 2015-01-26 12:54:33 +0000 | [diff] [blame] | 408 | } |
| 409 | } |
| 410 | |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 411 | void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) { |
Nicolas Geoffray | dbca6fa | 2014-11-27 12:01:59 +0000 | [diff] [blame] | 412 | ValueSet* set = nullptr; |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 413 | |
Vladimir Marko | 6058455 | 2015-09-03 13:35:12 +0000 | [diff] [blame] | 414 | const ArenaVector<HBasicBlock*>& predecessors = block->GetPredecessors(); |
| 415 | if (predecessors.size() == 0 || predecessors[0]->IsEntryBlock()) { |
Nicolas Geoffray | dbca6fa | 2014-11-27 12:01:59 +0000 | [diff] [blame] | 416 | // The entry block should only accumulate constant instructions, and |
| 417 | // the builder puts constants only in the entry block. |
| 418 | // Therefore, there is no need to propagate the value set to the next block. |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 419 | set = new (&allocator_) ValueSet(&allocator_); |
Nicolas Geoffray | dbca6fa | 2014-11-27 12:01:59 +0000 | [diff] [blame] | 420 | } else { |
| 421 | HBasicBlock* dominator = block->GetDominator(); |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 422 | ValueSet* dominator_set = FindSetFor(dominator); |
| 423 | |
Vladimir Marko | 6058455 | 2015-09-03 13:35:12 +0000 | [diff] [blame] | 424 | if (dominator->GetSuccessors().size() == 1) { |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 425 | // `block` is a direct successor of its dominator. No need to clone the |
| 426 | // dominator's set, `block` can take over its ownership including its buckets. |
| 427 | DCHECK_EQ(dominator->GetSingleSuccessor(), block); |
| 428 | AbandonSetFor(dominator); |
David Brazdil | 6d340c4 | 2015-03-03 11:54:54 +0000 | [diff] [blame] | 429 | set = dominator_set; |
| 430 | } else { |
David Brazdil | d974379 | 2016-04-21 14:00:15 +0100 | [diff] [blame] | 431 | // Try to find a basic block which will never be referenced again and whose |
| 432 | // ValueSet can therefore be recycled. We will need to copy `dominator_set` |
| 433 | // into the recycled set, so we pass `dominator_set` as a reference for size. |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 434 | HBasicBlock* recyclable = FindVisitedBlockWithRecyclableSet(block, *dominator_set); |
| 435 | if (recyclable == nullptr) { |
David Brazdil | d974379 | 2016-04-21 14:00:15 +0100 | [diff] [blame] | 436 | // No block with a suitable ValueSet found. Allocate a new one and |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 437 | // copy `dominator_set` into it. |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 438 | set = new (&allocator_) ValueSet(&allocator_, *dominator_set); |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 439 | } else { |
| 440 | // Block with a recyclable ValueSet found. Clone `dominator_set` into it. |
| 441 | set = FindSetFor(recyclable); |
| 442 | AbandonSetFor(recyclable); |
| 443 | set->PopulateFrom(*dominator_set); |
| 444 | } |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 445 | } |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 446 | |
Nicolas Geoffray | dbca6fa | 2014-11-27 12:01:59 +0000 | [diff] [blame] | 447 | if (!set->IsEmpty()) { |
| 448 | if (block->IsLoopHeader()) { |
Nicolas Geoffray | 77ce643 | 2016-05-10 14:35:34 +0100 | [diff] [blame] | 449 | if (block->GetLoopInformation()->ContainsIrreducibleLoop()) { |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 450 | // To satisfy our linear scan algorithm, no instruction should flow in an irreducible |
Nicolas Geoffray | 77ce643 | 2016-05-10 14:35:34 +0100 | [diff] [blame] | 451 | // loop header. We clear the set at entry of irreducible loops and any loop containing |
| 452 | // an irreducible loop, as in both cases, GVN can extend the liveness of an instruction |
| 453 | // across the irreducible loop. |
| 454 | // Note that, if we're not compiling OSR, we could still do GVN and introduce |
| 455 | // phis at irreducible loop headers. We decided it was not worth the complexity. |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 456 | set->Clear(); |
| 457 | } else { |
Nicolas Geoffray | 77ce643 | 2016-05-10 14:35:34 +0100 | [diff] [blame] | 458 | DCHECK(!block->GetLoopInformation()->IsIrreducible()); |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 459 | DCHECK_EQ(block->GetDominator(), block->GetLoopInformation()->GetPreHeader()); |
| 460 | set->Kill(side_effects_.GetLoopEffects(block)); |
| 461 | } |
Vladimir Marko | 6058455 | 2015-09-03 13:35:12 +0000 | [diff] [blame] | 462 | } else if (predecessors.size() > 1) { |
| 463 | for (HBasicBlock* predecessor : predecessors) { |
David Brazdil | d974379 | 2016-04-21 14:00:15 +0100 | [diff] [blame] | 464 | set->IntersectWith(FindSetFor(predecessor)); |
| 465 | if (set->IsEmpty()) { |
| 466 | break; |
Nicolas Geoffray | dbca6fa | 2014-11-27 12:01:59 +0000 | [diff] [blame] | 467 | } |
| 468 | } |
| 469 | } |
| 470 | } |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 471 | } |
| 472 | |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 473 | sets_[block->GetBlockId()] = set; |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 474 | |
| 475 | HInstruction* current = block->GetFirstInstruction(); |
| 476 | while (current != nullptr) { |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 477 | // Save the next instruction in case `current` is removed from the graph. |
| 478 | HInstruction* next = current->GetNext(); |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 479 | // Do not kill the set with the side effects of the instruction just now: if |
| 480 | // the instruction is GVN'ed, we don't need to kill. |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 481 | if (current->CanBeMoved()) { |
Mingyao Yang | dc5ac73 | 2015-02-25 11:28:05 -0800 | [diff] [blame] | 482 | if (current->IsBinaryOperation() && current->AsBinaryOperation()->IsCommutative()) { |
| 483 | // For commutative ops, (x op y) will be treated the same as (y op x) |
| 484 | // after fixed ordering. |
| 485 | current->AsBinaryOperation()->OrderInputs(); |
| 486 | } |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 487 | HInstruction* existing = set->Lookup(current); |
| 488 | if (existing != nullptr) { |
Mingyao Yang | dc5ac73 | 2015-02-25 11:28:05 -0800 | [diff] [blame] | 489 | // This replacement doesn't make more OrderInputs() necessary since |
| 490 | // current is either used by an instruction that it dominates, |
| 491 | // which hasn't been visited yet due to the order we visit instructions. |
| 492 | // Or current is used by a phi, and we don't do OrderInputs() on a phi anyway. |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 493 | current->ReplaceWith(existing); |
| 494 | current->GetBlock()->RemoveInstruction(current); |
| 495 | } else { |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 496 | set->Kill(current->GetSideEffects()); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 497 | set->Add(current); |
| 498 | } |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 499 | } else { |
| 500 | set->Kill(current->GetSideEffects()); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 501 | } |
| 502 | current = next; |
| 503 | } |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 504 | |
| 505 | visited_blocks_.SetBit(block->GetBlockId()); |
| 506 | } |
| 507 | |
| 508 | bool GlobalValueNumberer::WillBeReferencedAgain(HBasicBlock* block) const { |
| 509 | DCHECK(visited_blocks_.IsBitSet(block->GetBlockId())); |
| 510 | |
Vladimir Marko | 7d157fc | 2017-05-10 16:29:23 +0100 | [diff] [blame] | 511 | for (const HBasicBlock* dominated_block : block->GetDominatedBlocks()) { |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 512 | if (!visited_blocks_.IsBitSet(dominated_block->GetBlockId())) { |
| 513 | return true; |
| 514 | } |
| 515 | } |
| 516 | |
Vladimir Marko | 7d157fc | 2017-05-10 16:29:23 +0100 | [diff] [blame] | 517 | for (const HBasicBlock* successor : block->GetSuccessors()) { |
David Brazdil | 4283aa9 | 2016-04-20 14:24:12 +0100 | [diff] [blame] | 518 | if (!visited_blocks_.IsBitSet(successor->GetBlockId())) { |
| 519 | return true; |
| 520 | } |
| 521 | } |
| 522 | |
| 523 | return false; |
| 524 | } |
| 525 | |
| 526 | HBasicBlock* GlobalValueNumberer::FindVisitedBlockWithRecyclableSet( |
| 527 | HBasicBlock* block, const ValueSet& reference_set) const { |
| 528 | HBasicBlock* secondary_match = nullptr; |
| 529 | |
| 530 | for (size_t block_id : visited_blocks_.Indexes()) { |
| 531 | ValueSet* current_set = sets_[block_id]; |
| 532 | if (current_set == nullptr) { |
| 533 | // Set was already recycled. |
| 534 | continue; |
| 535 | } |
| 536 | |
| 537 | HBasicBlock* current_block = block->GetGraph()->GetBlocks()[block_id]; |
| 538 | |
| 539 | // We test if `current_set` has enough buckets to store a copy of |
| 540 | // `reference_set` with a reasonable load factor. If we find a set whose |
| 541 | // number of buckets matches perfectly, we return right away. If we find one |
| 542 | // that is larger, we return it if no perfectly-matching set is found. |
| 543 | // Note that we defer testing WillBeReferencedAgain until all other criteria |
| 544 | // have been satisfied because it might be expensive. |
| 545 | if (current_set->CanHoldCopyOf(reference_set, /* exact_match */ true)) { |
| 546 | if (!WillBeReferencedAgain(current_block)) { |
| 547 | return current_block; |
| 548 | } |
| 549 | } else if (secondary_match == nullptr && |
| 550 | current_set->CanHoldCopyOf(reference_set, /* exact_match */ false)) { |
| 551 | if (!WillBeReferencedAgain(current_block)) { |
| 552 | secondary_match = current_block; |
| 553 | } |
| 554 | } |
| 555 | } |
| 556 | |
| 557 | return secondary_match; |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 558 | } |
| 559 | |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 560 | void GVNOptimization::Run() { |
Vladimir Marko | 52d52f5 | 2017-10-10 11:04:48 +0100 | [diff] [blame] | 561 | GlobalValueNumberer gvn(graph_, side_effects_); |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 562 | gvn.Run(); |
| 563 | } |
| 564 | |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 565 | } // namespace art |