Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2015 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 "load_store_elimination.h" |
| 18 | #include "side_effects_analysis.h" |
| 19 | |
| 20 | #include <iostream> |
| 21 | |
| 22 | namespace art { |
| 23 | |
| 24 | class ReferenceInfo; |
| 25 | |
| 26 | // A cap for the number of heap locations to prevent pathological time/space consumption. |
| 27 | // The number of heap locations for most of the methods stays below this threshold. |
| 28 | constexpr size_t kMaxNumberOfHeapLocations = 32; |
| 29 | |
| 30 | // A ReferenceInfo contains additional info about a reference such as |
| 31 | // whether it's a singleton, returned, etc. |
| 32 | class ReferenceInfo : public ArenaObject<kArenaAllocMisc> { |
| 33 | public: |
| 34 | ReferenceInfo(HInstruction* reference, size_t pos) : reference_(reference), position_(pos) { |
| 35 | is_singleton_ = true; |
Mingyao Yang | e58bdca | 2016-10-28 11:07:24 -0700 | [diff] [blame] | 36 | is_singleton_and_non_escaping_ = true; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 37 | if (!reference_->IsNewInstance() && !reference_->IsNewArray()) { |
| 38 | // For references not allocated in the method, don't assume anything. |
| 39 | is_singleton_ = false; |
Mingyao Yang | e58bdca | 2016-10-28 11:07:24 -0700 | [diff] [blame] | 40 | is_singleton_and_non_escaping_ = false; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 41 | return; |
| 42 | } |
| 43 | |
| 44 | // Visit all uses to determine if this reference can spread into the heap, |
| 45 | // a method call, etc. |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 46 | for (const HUseListNode<HInstruction*>& use : reference_->GetUses()) { |
| 47 | HInstruction* user = use.GetUser(); |
| 48 | DCHECK(!user->IsNullCheck()) << "NullCheck should have been eliminated"; |
| 49 | if (user->IsBoundType()) { |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 50 | // BoundType shouldn't normally be necessary for a NewInstance. |
| 51 | // Just be conservative for the uncommon cases. |
| 52 | is_singleton_ = false; |
Mingyao Yang | e58bdca | 2016-10-28 11:07:24 -0700 | [diff] [blame] | 53 | is_singleton_and_non_escaping_ = false; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 54 | return; |
| 55 | } |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 56 | if (user->IsPhi() || user->IsSelect() || user->IsInvoke() || |
| 57 | (user->IsInstanceFieldSet() && (reference_ == user->InputAt(1))) || |
| 58 | (user->IsUnresolvedInstanceFieldSet() && (reference_ == user->InputAt(1))) || |
| 59 | (user->IsStaticFieldSet() && (reference_ == user->InputAt(1))) || |
| 60 | (user->IsUnresolvedStaticFieldSet() && (reference_ == user->InputAt(0))) || |
| 61 | (user->IsArraySet() && (reference_ == user->InputAt(2)))) { |
Mingyao Yang | 40bcb93 | 2016-02-03 05:46:57 -0800 | [diff] [blame] | 62 | // reference_ is merged to HPhi/HSelect, passed to a callee, or stored to heap. |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 63 | // reference_ isn't the only name that can refer to its value anymore. |
| 64 | is_singleton_ = false; |
Mingyao Yang | e58bdca | 2016-10-28 11:07:24 -0700 | [diff] [blame] | 65 | is_singleton_and_non_escaping_ = false; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 66 | return; |
| 67 | } |
Nicolas Geoffray | b93a165 | 2016-06-27 10:03:29 +0100 | [diff] [blame] | 68 | if ((user->IsUnresolvedInstanceFieldGet() && (reference_ == user->InputAt(0))) || |
| 69 | (user->IsUnresolvedInstanceFieldSet() && (reference_ == user->InputAt(0)))) { |
Mingyao Yang | e58bdca | 2016-10-28 11:07:24 -0700 | [diff] [blame] | 70 | // The field is accessed in an unresolved way. We mark the object as a non-singleton |
| 71 | // to disable load/store optimizations on it. |
Nicolas Geoffray | b93a165 | 2016-06-27 10:03:29 +0100 | [diff] [blame] | 72 | // Note that we could optimize this case and still perform some optimizations until |
| 73 | // we hit the unresolved access, but disabling is the simplest. |
| 74 | is_singleton_ = false; |
Mingyao Yang | e58bdca | 2016-10-28 11:07:24 -0700 | [diff] [blame] | 75 | is_singleton_and_non_escaping_ = false; |
Nicolas Geoffray | b93a165 | 2016-06-27 10:03:29 +0100 | [diff] [blame] | 76 | return; |
| 77 | } |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 78 | if (user->IsReturn()) { |
Mingyao Yang | e58bdca | 2016-10-28 11:07:24 -0700 | [diff] [blame] | 79 | is_singleton_and_non_escaping_ = false; |
| 80 | } |
| 81 | } |
| 82 | |
| 83 | if (!is_singleton_ || !is_singleton_and_non_escaping_) { |
| 84 | return; |
| 85 | } |
| 86 | |
| 87 | // Look at Environment uses and if it's for HDeoptimize, it's treated the same |
| 88 | // as a return which escapes at the end of executing the compiled code. We don't |
| 89 | // do store elimination for singletons that escape through HDeoptimize. |
| 90 | // Other Environment uses are fine since LSE is disabled for debuggable. |
| 91 | for (const HUseListNode<HEnvironment*>& use : reference_->GetEnvUses()) { |
| 92 | HEnvironment* user = use.GetUser(); |
| 93 | if (user->GetHolder()->IsDeoptimize()) { |
| 94 | is_singleton_and_non_escaping_ = false; |
| 95 | break; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 96 | } |
| 97 | } |
| 98 | } |
| 99 | |
| 100 | HInstruction* GetReference() const { |
| 101 | return reference_; |
| 102 | } |
| 103 | |
| 104 | size_t GetPosition() const { |
| 105 | return position_; |
| 106 | } |
| 107 | |
| 108 | // Returns true if reference_ is the only name that can refer to its value during |
| 109 | // the lifetime of the method. So it's guaranteed to not have any alias in |
| 110 | // the method (including its callees). |
| 111 | bool IsSingleton() const { |
| 112 | return is_singleton_; |
| 113 | } |
| 114 | |
Mingyao Yang | e58bdca | 2016-10-28 11:07:24 -0700 | [diff] [blame] | 115 | // Returns true if reference_ is a singleton and not returned to the caller or |
| 116 | // used as an environment local of an HDeoptimize instruction. |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 117 | // The allocation and stores into reference_ may be eliminated for such cases. |
Mingyao Yang | e58bdca | 2016-10-28 11:07:24 -0700 | [diff] [blame] | 118 | bool IsSingletonAndNonEscaping() const { |
| 119 | return is_singleton_and_non_escaping_; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 120 | } |
| 121 | |
| 122 | private: |
| 123 | HInstruction* const reference_; |
| 124 | const size_t position_; // position in HeapLocationCollector's ref_info_array_. |
| 125 | bool is_singleton_; // can only be referred to by a single name in the method. |
Mingyao Yang | e58bdca | 2016-10-28 11:07:24 -0700 | [diff] [blame] | 126 | |
| 127 | // reference_ is singleton and does not escape in the end either by |
| 128 | // returning to the caller, or being used as an environment local of an |
| 129 | // HDeoptimize instruction. |
| 130 | bool is_singleton_and_non_escaping_; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 131 | |
| 132 | DISALLOW_COPY_AND_ASSIGN(ReferenceInfo); |
| 133 | }; |
| 134 | |
| 135 | // A heap location is a reference-offset/index pair that a value can be loaded from |
| 136 | // or stored to. |
| 137 | class HeapLocation : public ArenaObject<kArenaAllocMisc> { |
| 138 | public: |
| 139 | static constexpr size_t kInvalidFieldOffset = -1; |
| 140 | |
| 141 | // TODO: more fine-grained array types. |
| 142 | static constexpr int16_t kDeclaringClassDefIndexForArrays = -1; |
| 143 | |
| 144 | HeapLocation(ReferenceInfo* ref_info, |
| 145 | size_t offset, |
| 146 | HInstruction* index, |
| 147 | int16_t declaring_class_def_index) |
| 148 | : ref_info_(ref_info), |
| 149 | offset_(offset), |
| 150 | index_(index), |
Mingyao Yang | 803cbb9 | 2015-12-01 12:24:36 -0800 | [diff] [blame] | 151 | declaring_class_def_index_(declaring_class_def_index), |
| 152 | value_killed_by_loop_side_effects_(true) { |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 153 | DCHECK(ref_info != nullptr); |
| 154 | DCHECK((offset == kInvalidFieldOffset && index != nullptr) || |
| 155 | (offset != kInvalidFieldOffset && index == nullptr)); |
Mingyao Yang | 803cbb9 | 2015-12-01 12:24:36 -0800 | [diff] [blame] | 156 | if (ref_info->IsSingleton() && !IsArrayElement()) { |
| 157 | // Assume this location's value cannot be killed by loop side effects |
| 158 | // until proven otherwise. |
| 159 | value_killed_by_loop_side_effects_ = false; |
| 160 | } |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 161 | } |
| 162 | |
| 163 | ReferenceInfo* GetReferenceInfo() const { return ref_info_; } |
| 164 | size_t GetOffset() const { return offset_; } |
| 165 | HInstruction* GetIndex() const { return index_; } |
| 166 | |
| 167 | // Returns the definition of declaring class' dex index. |
| 168 | // It's kDeclaringClassDefIndexForArrays for an array element. |
| 169 | int16_t GetDeclaringClassDefIndex() const { |
| 170 | return declaring_class_def_index_; |
| 171 | } |
| 172 | |
| 173 | bool IsArrayElement() const { |
| 174 | return index_ != nullptr; |
| 175 | } |
| 176 | |
Mingyao Yang | 803cbb9 | 2015-12-01 12:24:36 -0800 | [diff] [blame] | 177 | bool IsValueKilledByLoopSideEffects() const { |
| 178 | return value_killed_by_loop_side_effects_; |
| 179 | } |
| 180 | |
| 181 | void SetValueKilledByLoopSideEffects(bool val) { |
| 182 | value_killed_by_loop_side_effects_ = val; |
| 183 | } |
| 184 | |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 185 | private: |
| 186 | ReferenceInfo* const ref_info_; // reference for instance/static field or array access. |
| 187 | const size_t offset_; // offset of static/instance field. |
| 188 | HInstruction* const index_; // index of an array element. |
| 189 | const int16_t declaring_class_def_index_; // declaring class's def's dex index. |
Mingyao Yang | 803cbb9 | 2015-12-01 12:24:36 -0800 | [diff] [blame] | 190 | bool value_killed_by_loop_side_effects_; // value of this location may be killed by loop |
| 191 | // side effects because this location is stored |
Mingyao Yang | 0a84520 | 2016-10-14 16:26:08 -0700 | [diff] [blame] | 192 | // into inside a loop. This gives |
| 193 | // better info on whether a singleton's location |
| 194 | // value may be killed by loop side effects. |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 195 | |
| 196 | DISALLOW_COPY_AND_ASSIGN(HeapLocation); |
| 197 | }; |
| 198 | |
| 199 | static HInstruction* HuntForOriginalReference(HInstruction* ref) { |
| 200 | DCHECK(ref != nullptr); |
| 201 | while (ref->IsNullCheck() || ref->IsBoundType()) { |
| 202 | ref = ref->InputAt(0); |
| 203 | } |
| 204 | return ref; |
| 205 | } |
| 206 | |
| 207 | // A HeapLocationCollector collects all relevant heap locations and keeps |
| 208 | // an aliasing matrix for all locations. |
| 209 | class HeapLocationCollector : public HGraphVisitor { |
| 210 | public: |
| 211 | static constexpr size_t kHeapLocationNotFound = -1; |
| 212 | // Start with a single uint32_t word. That's enough bits for pair-wise |
| 213 | // aliasing matrix of 8 heap locations. |
| 214 | static constexpr uint32_t kInitialAliasingMatrixBitVectorSize = 32; |
| 215 | |
| 216 | explicit HeapLocationCollector(HGraph* graph) |
| 217 | : HGraphVisitor(graph), |
| 218 | ref_info_array_(graph->GetArena()->Adapter(kArenaAllocLSE)), |
| 219 | heap_locations_(graph->GetArena()->Adapter(kArenaAllocLSE)), |
Vladimir Marko | f6a35de | 2016-03-21 12:01:50 +0000 | [diff] [blame] | 220 | aliasing_matrix_(graph->GetArena(), |
| 221 | kInitialAliasingMatrixBitVectorSize, |
| 222 | true, |
| 223 | kArenaAllocLSE), |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 224 | has_heap_stores_(false), |
| 225 | has_volatile_(false), |
Mingyao Yang | e58bdca | 2016-10-28 11:07:24 -0700 | [diff] [blame] | 226 | has_monitor_operations_(false) {} |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 227 | |
| 228 | size_t GetNumberOfHeapLocations() const { |
| 229 | return heap_locations_.size(); |
| 230 | } |
| 231 | |
| 232 | HeapLocation* GetHeapLocation(size_t index) const { |
| 233 | return heap_locations_[index]; |
| 234 | } |
| 235 | |
| 236 | ReferenceInfo* FindReferenceInfoOf(HInstruction* ref) const { |
| 237 | for (size_t i = 0; i < ref_info_array_.size(); i++) { |
| 238 | ReferenceInfo* ref_info = ref_info_array_[i]; |
| 239 | if (ref_info->GetReference() == ref) { |
| 240 | DCHECK_EQ(i, ref_info->GetPosition()); |
| 241 | return ref_info; |
| 242 | } |
| 243 | } |
| 244 | return nullptr; |
| 245 | } |
| 246 | |
| 247 | bool HasHeapStores() const { |
| 248 | return has_heap_stores_; |
| 249 | } |
| 250 | |
| 251 | bool HasVolatile() const { |
| 252 | return has_volatile_; |
| 253 | } |
| 254 | |
| 255 | bool HasMonitorOps() const { |
| 256 | return has_monitor_operations_; |
| 257 | } |
| 258 | |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 259 | // Find and return the heap location index in heap_locations_. |
| 260 | size_t FindHeapLocationIndex(ReferenceInfo* ref_info, |
| 261 | size_t offset, |
| 262 | HInstruction* index, |
| 263 | int16_t declaring_class_def_index) const { |
| 264 | for (size_t i = 0; i < heap_locations_.size(); i++) { |
| 265 | HeapLocation* loc = heap_locations_[i]; |
| 266 | if (loc->GetReferenceInfo() == ref_info && |
| 267 | loc->GetOffset() == offset && |
| 268 | loc->GetIndex() == index && |
| 269 | loc->GetDeclaringClassDefIndex() == declaring_class_def_index) { |
| 270 | return i; |
| 271 | } |
| 272 | } |
| 273 | return kHeapLocationNotFound; |
| 274 | } |
| 275 | |
| 276 | // Returns true if heap_locations_[index1] and heap_locations_[index2] may alias. |
| 277 | bool MayAlias(size_t index1, size_t index2) const { |
| 278 | if (index1 < index2) { |
| 279 | return aliasing_matrix_.IsBitSet(AliasingMatrixPosition(index1, index2)); |
| 280 | } else if (index1 > index2) { |
| 281 | return aliasing_matrix_.IsBitSet(AliasingMatrixPosition(index2, index1)); |
| 282 | } else { |
| 283 | DCHECK(false) << "index1 and index2 are expected to be different"; |
| 284 | return true; |
| 285 | } |
| 286 | } |
| 287 | |
| 288 | void BuildAliasingMatrix() { |
| 289 | const size_t number_of_locations = heap_locations_.size(); |
| 290 | if (number_of_locations == 0) { |
| 291 | return; |
| 292 | } |
| 293 | size_t pos = 0; |
| 294 | // Compute aliasing info between every pair of different heap locations. |
| 295 | // Save the result in a matrix represented as a BitVector. |
| 296 | for (size_t i = 0; i < number_of_locations - 1; i++) { |
| 297 | for (size_t j = i + 1; j < number_of_locations; j++) { |
| 298 | if (ComputeMayAlias(i, j)) { |
| 299 | aliasing_matrix_.SetBit(CheckedAliasingMatrixPosition(i, j, pos)); |
| 300 | } |
| 301 | pos++; |
| 302 | } |
| 303 | } |
| 304 | } |
| 305 | |
| 306 | private: |
| 307 | // An allocation cannot alias with a name which already exists at the point |
| 308 | // of the allocation, such as a parameter or a load happening before the allocation. |
| 309 | bool MayAliasWithPreexistenceChecking(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) const { |
| 310 | if (ref_info1->GetReference()->IsNewInstance() || ref_info1->GetReference()->IsNewArray()) { |
| 311 | // Any reference that can alias with the allocation must appear after it in the block/in |
| 312 | // the block's successors. In reverse post order, those instructions will be visited after |
| 313 | // the allocation. |
| 314 | return ref_info2->GetPosition() >= ref_info1->GetPosition(); |
| 315 | } |
| 316 | return true; |
| 317 | } |
| 318 | |
| 319 | bool CanReferencesAlias(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) const { |
| 320 | if (ref_info1 == ref_info2) { |
| 321 | return true; |
| 322 | } else if (ref_info1->IsSingleton()) { |
| 323 | return false; |
| 324 | } else if (ref_info2->IsSingleton()) { |
| 325 | return false; |
| 326 | } else if (!MayAliasWithPreexistenceChecking(ref_info1, ref_info2) || |
| 327 | !MayAliasWithPreexistenceChecking(ref_info2, ref_info1)) { |
| 328 | return false; |
| 329 | } |
| 330 | return true; |
| 331 | } |
| 332 | |
| 333 | // `index1` and `index2` are indices in the array of collected heap locations. |
| 334 | // Returns the position in the bit vector that tracks whether the two heap |
| 335 | // locations may alias. |
| 336 | size_t AliasingMatrixPosition(size_t index1, size_t index2) const { |
| 337 | DCHECK(index2 > index1); |
| 338 | const size_t number_of_locations = heap_locations_.size(); |
| 339 | // It's (num_of_locations - 1) + ... + (num_of_locations - index1) + (index2 - index1 - 1). |
| 340 | return (number_of_locations * index1 - (1 + index1) * index1 / 2 + (index2 - index1 - 1)); |
| 341 | } |
| 342 | |
| 343 | // An additional position is passed in to make sure the calculated position is correct. |
| 344 | size_t CheckedAliasingMatrixPosition(size_t index1, size_t index2, size_t position) { |
| 345 | size_t calculated_position = AliasingMatrixPosition(index1, index2); |
| 346 | DCHECK_EQ(calculated_position, position); |
| 347 | return calculated_position; |
| 348 | } |
| 349 | |
| 350 | // Compute if two locations may alias to each other. |
| 351 | bool ComputeMayAlias(size_t index1, size_t index2) const { |
| 352 | HeapLocation* loc1 = heap_locations_[index1]; |
| 353 | HeapLocation* loc2 = heap_locations_[index2]; |
| 354 | if (loc1->GetOffset() != loc2->GetOffset()) { |
| 355 | // Either two different instance fields, or one is an instance |
| 356 | // field and the other is an array element. |
| 357 | return false; |
| 358 | } |
| 359 | if (loc1->GetDeclaringClassDefIndex() != loc2->GetDeclaringClassDefIndex()) { |
| 360 | // Different types. |
| 361 | return false; |
| 362 | } |
| 363 | if (!CanReferencesAlias(loc1->GetReferenceInfo(), loc2->GetReferenceInfo())) { |
| 364 | return false; |
| 365 | } |
| 366 | if (loc1->IsArrayElement() && loc2->IsArrayElement()) { |
| 367 | HInstruction* array_index1 = loc1->GetIndex(); |
| 368 | HInstruction* array_index2 = loc2->GetIndex(); |
| 369 | DCHECK(array_index1 != nullptr); |
| 370 | DCHECK(array_index2 != nullptr); |
| 371 | if (array_index1->IsIntConstant() && |
| 372 | array_index2->IsIntConstant() && |
| 373 | array_index1->AsIntConstant()->GetValue() != array_index2->AsIntConstant()->GetValue()) { |
| 374 | // Different constant indices do not alias. |
| 375 | return false; |
| 376 | } |
| 377 | } |
| 378 | return true; |
| 379 | } |
| 380 | |
Mingyao Yang | 8ab1d64 | 2015-12-03 14:11:15 -0800 | [diff] [blame] | 381 | ReferenceInfo* GetOrCreateReferenceInfo(HInstruction* instruction) { |
| 382 | ReferenceInfo* ref_info = FindReferenceInfoOf(instruction); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 383 | if (ref_info == nullptr) { |
| 384 | size_t pos = ref_info_array_.size(); |
Mingyao Yang | 8ab1d64 | 2015-12-03 14:11:15 -0800 | [diff] [blame] | 385 | ref_info = new (GetGraph()->GetArena()) ReferenceInfo(instruction, pos); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 386 | ref_info_array_.push_back(ref_info); |
| 387 | } |
| 388 | return ref_info; |
| 389 | } |
| 390 | |
Mingyao Yang | 8ab1d64 | 2015-12-03 14:11:15 -0800 | [diff] [blame] | 391 | void CreateReferenceInfoForReferenceType(HInstruction* instruction) { |
| 392 | if (instruction->GetType() != Primitive::kPrimNot) { |
| 393 | return; |
| 394 | } |
| 395 | DCHECK(FindReferenceInfoOf(instruction) == nullptr); |
| 396 | GetOrCreateReferenceInfo(instruction); |
| 397 | } |
| 398 | |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 399 | HeapLocation* GetOrCreateHeapLocation(HInstruction* ref, |
| 400 | size_t offset, |
| 401 | HInstruction* index, |
| 402 | int16_t declaring_class_def_index) { |
| 403 | HInstruction* original_ref = HuntForOriginalReference(ref); |
| 404 | ReferenceInfo* ref_info = GetOrCreateReferenceInfo(original_ref); |
| 405 | size_t heap_location_idx = FindHeapLocationIndex( |
| 406 | ref_info, offset, index, declaring_class_def_index); |
| 407 | if (heap_location_idx == kHeapLocationNotFound) { |
| 408 | HeapLocation* heap_loc = new (GetGraph()->GetArena()) |
| 409 | HeapLocation(ref_info, offset, index, declaring_class_def_index); |
| 410 | heap_locations_.push_back(heap_loc); |
| 411 | return heap_loc; |
| 412 | } |
| 413 | return heap_locations_[heap_location_idx]; |
| 414 | } |
| 415 | |
Mingyao Yang | 803cbb9 | 2015-12-01 12:24:36 -0800 | [diff] [blame] | 416 | HeapLocation* VisitFieldAccess(HInstruction* ref, const FieldInfo& field_info) { |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 417 | if (field_info.IsVolatile()) { |
| 418 | has_volatile_ = true; |
| 419 | } |
| 420 | const uint16_t declaring_class_def_index = field_info.GetDeclaringClassDefIndex(); |
| 421 | const size_t offset = field_info.GetFieldOffset().SizeValue(); |
Mingyao Yang | 803cbb9 | 2015-12-01 12:24:36 -0800 | [diff] [blame] | 422 | return GetOrCreateHeapLocation(ref, offset, nullptr, declaring_class_def_index); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 423 | } |
| 424 | |
| 425 | void VisitArrayAccess(HInstruction* array, HInstruction* index) { |
| 426 | GetOrCreateHeapLocation(array, HeapLocation::kInvalidFieldOffset, |
| 427 | index, HeapLocation::kDeclaringClassDefIndexForArrays); |
| 428 | } |
| 429 | |
| 430 | void VisitInstanceFieldGet(HInstanceFieldGet* instruction) OVERRIDE { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 431 | VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); |
Mingyao Yang | 8ab1d64 | 2015-12-03 14:11:15 -0800 | [diff] [blame] | 432 | CreateReferenceInfoForReferenceType(instruction); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 433 | } |
| 434 | |
| 435 | void VisitInstanceFieldSet(HInstanceFieldSet* instruction) OVERRIDE { |
Mingyao Yang | 803cbb9 | 2015-12-01 12:24:36 -0800 | [diff] [blame] | 436 | HeapLocation* location = VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 437 | has_heap_stores_ = true; |
Mingyao Yang | 0a84520 | 2016-10-14 16:26:08 -0700 | [diff] [blame] | 438 | if (location->GetReferenceInfo()->IsSingleton()) { |
| 439 | // A singleton's location value may be killed by loop side effects if it's |
| 440 | // defined before that loop, and it's stored into inside that loop. |
| 441 | HLoopInformation* loop_info = instruction->GetBlock()->GetLoopInformation(); |
| 442 | if (loop_info != nullptr) { |
| 443 | HInstruction* ref = location->GetReferenceInfo()->GetReference(); |
| 444 | DCHECK(ref->IsNewInstance()); |
| 445 | if (loop_info->IsDefinedOutOfTheLoop(ref)) { |
| 446 | // ref's location value may be killed by this loop's side effects. |
| 447 | location->SetValueKilledByLoopSideEffects(true); |
| 448 | } else { |
| 449 | // ref is defined inside this loop so this loop's side effects cannot |
| 450 | // kill its location value at the loop header since ref/its location doesn't |
| 451 | // exist yet at the loop header. |
| 452 | } |
| 453 | } |
| 454 | } else { |
| 455 | // For non-singletons, value_killed_by_loop_side_effects_ is inited to |
| 456 | // true. |
| 457 | DCHECK_EQ(location->IsValueKilledByLoopSideEffects(), true); |
Mingyao Yang | 803cbb9 | 2015-12-01 12:24:36 -0800 | [diff] [blame] | 458 | } |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 459 | } |
| 460 | |
| 461 | void VisitStaticFieldGet(HStaticFieldGet* instruction) OVERRIDE { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 462 | VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); |
Mingyao Yang | 8ab1d64 | 2015-12-03 14:11:15 -0800 | [diff] [blame] | 463 | CreateReferenceInfoForReferenceType(instruction); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 464 | } |
| 465 | |
| 466 | void VisitStaticFieldSet(HStaticFieldSet* instruction) OVERRIDE { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 467 | VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 468 | has_heap_stores_ = true; |
| 469 | } |
| 470 | |
| 471 | // We intentionally don't collect HUnresolvedInstanceField/HUnresolvedStaticField accesses |
| 472 | // since we cannot accurately track the fields. |
| 473 | |
| 474 | void VisitArrayGet(HArrayGet* instruction) OVERRIDE { |
| 475 | VisitArrayAccess(instruction->InputAt(0), instruction->InputAt(1)); |
Mingyao Yang | 8ab1d64 | 2015-12-03 14:11:15 -0800 | [diff] [blame] | 476 | CreateReferenceInfoForReferenceType(instruction); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 477 | } |
| 478 | |
| 479 | void VisitArraySet(HArraySet* instruction) OVERRIDE { |
| 480 | VisitArrayAccess(instruction->InputAt(0), instruction->InputAt(1)); |
| 481 | has_heap_stores_ = true; |
| 482 | } |
| 483 | |
| 484 | void VisitNewInstance(HNewInstance* new_instance) OVERRIDE { |
| 485 | // Any references appearing in the ref_info_array_ so far cannot alias with new_instance. |
Mingyao Yang | 8ab1d64 | 2015-12-03 14:11:15 -0800 | [diff] [blame] | 486 | CreateReferenceInfoForReferenceType(new_instance); |
| 487 | } |
| 488 | |
| 489 | void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* instruction) OVERRIDE { |
| 490 | CreateReferenceInfoForReferenceType(instruction); |
| 491 | } |
| 492 | |
| 493 | void VisitInvokeVirtual(HInvokeVirtual* instruction) OVERRIDE { |
| 494 | CreateReferenceInfoForReferenceType(instruction); |
| 495 | } |
| 496 | |
| 497 | void VisitInvokeInterface(HInvokeInterface* instruction) OVERRIDE { |
| 498 | CreateReferenceInfoForReferenceType(instruction); |
| 499 | } |
| 500 | |
| 501 | void VisitParameterValue(HParameterValue* instruction) OVERRIDE { |
| 502 | CreateReferenceInfoForReferenceType(instruction); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 503 | } |
| 504 | |
Mingyao Yang | 40bcb93 | 2016-02-03 05:46:57 -0800 | [diff] [blame] | 505 | void VisitSelect(HSelect* instruction) OVERRIDE { |
| 506 | CreateReferenceInfoForReferenceType(instruction); |
| 507 | } |
| 508 | |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 509 | void VisitMonitorOperation(HMonitorOperation* monitor ATTRIBUTE_UNUSED) OVERRIDE { |
| 510 | has_monitor_operations_ = true; |
| 511 | } |
| 512 | |
| 513 | ArenaVector<ReferenceInfo*> ref_info_array_; // All references used for heap accesses. |
| 514 | ArenaVector<HeapLocation*> heap_locations_; // All heap locations. |
| 515 | ArenaBitVector aliasing_matrix_; // aliasing info between each pair of locations. |
| 516 | bool has_heap_stores_; // If there is no heap stores, LSE acts as GVN with better |
| 517 | // alias analysis and won't be as effective. |
| 518 | bool has_volatile_; // If there are volatile field accesses. |
| 519 | bool has_monitor_operations_; // If there are monitor operations. |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 520 | |
| 521 | DISALLOW_COPY_AND_ASSIGN(HeapLocationCollector); |
| 522 | }; |
| 523 | |
| 524 | // An unknown heap value. Loads with such a value in the heap location cannot be eliminated. |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 525 | // A heap location can be set to kUnknownHeapValue when: |
| 526 | // - initially set a value. |
| 527 | // - killed due to aliasing, merging, invocation, or loop side effects. |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 528 | static HInstruction* const kUnknownHeapValue = |
| 529 | reinterpret_cast<HInstruction*>(static_cast<uintptr_t>(-1)); |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 530 | |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 531 | // Default heap value after an allocation. |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 532 | // A heap location can be set to that value right after an allocation. |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 533 | static HInstruction* const kDefaultHeapValue = |
| 534 | reinterpret_cast<HInstruction*>(static_cast<uintptr_t>(-2)); |
| 535 | |
| 536 | class LSEVisitor : public HGraphVisitor { |
| 537 | public: |
| 538 | LSEVisitor(HGraph* graph, |
| 539 | const HeapLocationCollector& heap_locations_collector, |
| 540 | const SideEffectsAnalysis& side_effects) |
| 541 | : HGraphVisitor(graph), |
| 542 | heap_location_collector_(heap_locations_collector), |
| 543 | side_effects_(side_effects), |
| 544 | heap_values_for_(graph->GetBlocks().size(), |
| 545 | ArenaVector<HInstruction*>(heap_locations_collector. |
| 546 | GetNumberOfHeapLocations(), |
| 547 | kUnknownHeapValue, |
| 548 | graph->GetArena()->Adapter(kArenaAllocLSE)), |
| 549 | graph->GetArena()->Adapter(kArenaAllocLSE)), |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 550 | removed_loads_(graph->GetArena()->Adapter(kArenaAllocLSE)), |
| 551 | substitute_instructions_for_loads_(graph->GetArena()->Adapter(kArenaAllocLSE)), |
| 552 | possibly_removed_stores_(graph->GetArena()->Adapter(kArenaAllocLSE)), |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 553 | singleton_new_instances_(graph->GetArena()->Adapter(kArenaAllocLSE)) { |
| 554 | } |
| 555 | |
| 556 | void VisitBasicBlock(HBasicBlock* block) OVERRIDE { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 557 | // Populate the heap_values array for this block. |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 558 | // TODO: try to reuse the heap_values array from one predecessor if possible. |
| 559 | if (block->IsLoopHeader()) { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 560 | HandleLoopSideEffects(block); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 561 | } else { |
| 562 | MergePredecessorValues(block); |
| 563 | } |
| 564 | HGraphVisitor::VisitBasicBlock(block); |
| 565 | } |
| 566 | |
| 567 | // Remove recorded instructions that should be eliminated. |
| 568 | void RemoveInstructions() { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 569 | size_t size = removed_loads_.size(); |
| 570 | DCHECK_EQ(size, substitute_instructions_for_loads_.size()); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 571 | for (size_t i = 0; i < size; i++) { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 572 | HInstruction* load = removed_loads_[i]; |
| 573 | DCHECK(load != nullptr); |
| 574 | DCHECK(load->IsInstanceFieldGet() || |
| 575 | load->IsStaticFieldGet() || |
| 576 | load->IsArrayGet()); |
| 577 | HInstruction* substitute = substitute_instructions_for_loads_[i]; |
| 578 | DCHECK(substitute != nullptr); |
| 579 | // Keep tracing substitute till one that's not removed. |
| 580 | HInstruction* sub_sub = FindSubstitute(substitute); |
| 581 | while (sub_sub != substitute) { |
| 582 | substitute = sub_sub; |
| 583 | sub_sub = FindSubstitute(substitute); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 584 | } |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 585 | load->ReplaceWith(substitute); |
| 586 | load->GetBlock()->RemoveInstruction(load); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 587 | } |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 588 | |
| 589 | // At this point, stores in possibly_removed_stores_ can be safely removed. |
Mingyao Yang | 062157f | 2016-03-02 10:15:36 -0800 | [diff] [blame] | 590 | for (size_t i = 0, e = possibly_removed_stores_.size(); i < e; i++) { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 591 | HInstruction* store = possibly_removed_stores_[i]; |
| 592 | DCHECK(store->IsInstanceFieldSet() || store->IsStaticFieldSet() || store->IsArraySet()); |
| 593 | store->GetBlock()->RemoveInstruction(store); |
| 594 | } |
| 595 | |
Mingyao Yang | 062157f | 2016-03-02 10:15:36 -0800 | [diff] [blame] | 596 | // Eliminate allocations that are not used. |
| 597 | for (size_t i = 0, e = singleton_new_instances_.size(); i < e; i++) { |
| 598 | HInstruction* new_instance = singleton_new_instances_[i]; |
| 599 | if (!new_instance->HasNonEnvironmentUses()) { |
| 600 | new_instance->RemoveEnvironmentUsers(); |
| 601 | new_instance->GetBlock()->RemoveInstruction(new_instance); |
| 602 | } |
| 603 | } |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 604 | } |
| 605 | |
| 606 | private: |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 607 | // If heap_values[index] is an instance field store, need to keep the store. |
| 608 | // This is necessary if a heap value is killed due to merging, or loop side |
| 609 | // effects (which is essentially merging also), since a load later from the |
| 610 | // location won't be eliminated. |
| 611 | void KeepIfIsStore(HInstruction* heap_value) { |
| 612 | if (heap_value == kDefaultHeapValue || |
| 613 | heap_value == kUnknownHeapValue || |
| 614 | !heap_value->IsInstanceFieldSet()) { |
| 615 | return; |
| 616 | } |
| 617 | auto idx = std::find(possibly_removed_stores_.begin(), |
| 618 | possibly_removed_stores_.end(), heap_value); |
| 619 | if (idx != possibly_removed_stores_.end()) { |
| 620 | // Make sure the store is kept. |
| 621 | possibly_removed_stores_.erase(idx); |
| 622 | } |
| 623 | } |
| 624 | |
| 625 | void HandleLoopSideEffects(HBasicBlock* block) { |
| 626 | DCHECK(block->IsLoopHeader()); |
| 627 | int block_id = block->GetBlockId(); |
| 628 | ArenaVector<HInstruction*>& heap_values = heap_values_for_[block_id]; |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 629 | |
| 630 | // Don't eliminate loads in irreducible loops. This is safe for singletons, because |
| 631 | // they are always used by the non-eliminated loop-phi. |
| 632 | if (block->GetLoopInformation()->IsIrreducible()) { |
| 633 | if (kIsDebugBuild) { |
| 634 | for (size_t i = 0; i < heap_values.size(); i++) { |
| 635 | DCHECK_EQ(heap_values[i], kUnknownHeapValue); |
| 636 | } |
| 637 | } |
| 638 | return; |
| 639 | } |
| 640 | |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 641 | HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader(); |
| 642 | ArenaVector<HInstruction*>& pre_header_heap_values = |
| 643 | heap_values_for_[pre_header->GetBlockId()]; |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 644 | |
Mingyao Yang | 803cbb9 | 2015-12-01 12:24:36 -0800 | [diff] [blame] | 645 | // Inherit the values from pre-header. |
| 646 | for (size_t i = 0; i < heap_values.size(); i++) { |
| 647 | heap_values[i] = pre_header_heap_values[i]; |
| 648 | } |
| 649 | |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 650 | // We do a single pass in reverse post order. For loops, use the side effects as a hint |
| 651 | // to see if the heap values should be killed. |
| 652 | if (side_effects_.GetLoopEffects(block).DoesAnyWrite()) { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 653 | for (size_t i = 0; i < heap_values.size(); i++) { |
Mingyao Yang | 803cbb9 | 2015-12-01 12:24:36 -0800 | [diff] [blame] | 654 | HeapLocation* location = heap_location_collector_.GetHeapLocation(i); |
| 655 | ReferenceInfo* ref_info = location->GetReferenceInfo(); |
| 656 | if (!ref_info->IsSingleton() || location->IsValueKilledByLoopSideEffects()) { |
| 657 | // heap value is killed by loop side effects (stored into directly, or due to |
| 658 | // aliasing). |
| 659 | KeepIfIsStore(pre_header_heap_values[i]); |
| 660 | heap_values[i] = kUnknownHeapValue; |
| 661 | } else { |
| 662 | // A singleton's field that's not stored into inside a loop is invariant throughout |
| 663 | // the loop. |
| 664 | } |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 665 | } |
| 666 | } |
| 667 | } |
| 668 | |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 669 | void MergePredecessorValues(HBasicBlock* block) { |
| 670 | const ArenaVector<HBasicBlock*>& predecessors = block->GetPredecessors(); |
| 671 | if (predecessors.size() == 0) { |
| 672 | return; |
| 673 | } |
Mingyao Yang | 58d9bfc | 2016-11-01 13:31:58 -0700 | [diff] [blame] | 674 | |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 675 | ArenaVector<HInstruction*>& heap_values = heap_values_for_[block->GetBlockId()]; |
| 676 | for (size_t i = 0; i < heap_values.size(); i++) { |
Mingyao Yang | 58d9bfc | 2016-11-01 13:31:58 -0700 | [diff] [blame] | 677 | HInstruction* merged_value = nullptr; |
| 678 | // Whether merged_value is a result that's merged from all predecessors. |
| 679 | bool from_all_predecessors = true; |
| 680 | ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo(); |
| 681 | HInstruction* singleton_ref = nullptr; |
Mingyao Yang | e58bdca | 2016-10-28 11:07:24 -0700 | [diff] [blame] | 682 | if (ref_info->IsSingletonAndNonEscaping()) { |
Mingyao Yang | 58d9bfc | 2016-11-01 13:31:58 -0700 | [diff] [blame] | 683 | // We do more analysis of liveness when merging heap values for such |
| 684 | // cases since stores into such references may potentially be eliminated. |
| 685 | singleton_ref = ref_info->GetReference(); |
| 686 | } |
| 687 | |
| 688 | for (HBasicBlock* predecessor : predecessors) { |
| 689 | HInstruction* pred_value = heap_values_for_[predecessor->GetBlockId()][i]; |
| 690 | if ((singleton_ref != nullptr) && |
| 691 | !singleton_ref->GetBlock()->Dominates(predecessor)) { |
| 692 | // singleton_ref is not live in this predecessor. Skip this predecessor since |
| 693 | // it does not really have the location. |
| 694 | DCHECK_EQ(pred_value, kUnknownHeapValue); |
| 695 | from_all_predecessors = false; |
| 696 | continue; |
| 697 | } |
| 698 | if (merged_value == nullptr) { |
| 699 | // First seen heap value. |
| 700 | merged_value = pred_value; |
| 701 | } else if (pred_value != merged_value) { |
| 702 | // There are conflicting values. |
| 703 | merged_value = kUnknownHeapValue; |
| 704 | break; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 705 | } |
| 706 | } |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 707 | |
Mingyao Yang | 58d9bfc | 2016-11-01 13:31:58 -0700 | [diff] [blame] | 708 | if (merged_value == kUnknownHeapValue) { |
| 709 | // There are conflicting heap values from different predecessors. |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 710 | // Keep the last store in each predecessor since future loads cannot be eliminated. |
Mingyao Yang | 58d9bfc | 2016-11-01 13:31:58 -0700 | [diff] [blame] | 711 | for (HBasicBlock* predecessor : predecessors) { |
| 712 | ArenaVector<HInstruction*>& pred_values = heap_values_for_[predecessor->GetBlockId()]; |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 713 | KeepIfIsStore(pred_values[i]); |
| 714 | } |
| 715 | } |
Mingyao Yang | 58d9bfc | 2016-11-01 13:31:58 -0700 | [diff] [blame] | 716 | |
| 717 | if ((merged_value == nullptr) || !from_all_predecessors) { |
| 718 | DCHECK(singleton_ref != nullptr); |
| 719 | DCHECK((singleton_ref->GetBlock() == block) || |
| 720 | !singleton_ref->GetBlock()->Dominates(block)); |
| 721 | // singleton_ref is not defined before block or defined only in some of its |
| 722 | // predecessors, so block doesn't really have the location at its entry. |
| 723 | heap_values[i] = kUnknownHeapValue; |
| 724 | } else { |
| 725 | heap_values[i] = merged_value; |
| 726 | } |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 727 | } |
| 728 | } |
| 729 | |
| 730 | // `instruction` is being removed. Try to see if the null check on it |
| 731 | // can be removed. This can happen if the same value is set in two branches |
| 732 | // but not in dominators. Such as: |
| 733 | // int[] a = foo(); |
| 734 | // if () { |
| 735 | // a[0] = 2; |
| 736 | // } else { |
| 737 | // a[0] = 2; |
| 738 | // } |
| 739 | // // a[0] can now be replaced with constant 2, and the null check on it can be removed. |
| 740 | void TryRemovingNullCheck(HInstruction* instruction) { |
| 741 | HInstruction* prev = instruction->GetPrevious(); |
| 742 | if ((prev != nullptr) && prev->IsNullCheck() && (prev == instruction->InputAt(0))) { |
| 743 | // Previous instruction is a null check for this instruction. Remove the null check. |
| 744 | prev->ReplaceWith(prev->InputAt(0)); |
| 745 | prev->GetBlock()->RemoveInstruction(prev); |
| 746 | } |
| 747 | } |
| 748 | |
| 749 | HInstruction* GetDefaultValue(Primitive::Type type) { |
| 750 | switch (type) { |
| 751 | case Primitive::kPrimNot: |
| 752 | return GetGraph()->GetNullConstant(); |
| 753 | case Primitive::kPrimBoolean: |
| 754 | case Primitive::kPrimByte: |
| 755 | case Primitive::kPrimChar: |
| 756 | case Primitive::kPrimShort: |
| 757 | case Primitive::kPrimInt: |
| 758 | return GetGraph()->GetIntConstant(0); |
| 759 | case Primitive::kPrimLong: |
| 760 | return GetGraph()->GetLongConstant(0); |
| 761 | case Primitive::kPrimFloat: |
| 762 | return GetGraph()->GetFloatConstant(0); |
| 763 | case Primitive::kPrimDouble: |
| 764 | return GetGraph()->GetDoubleConstant(0); |
| 765 | default: |
| 766 | UNREACHABLE(); |
| 767 | } |
| 768 | } |
| 769 | |
| 770 | void VisitGetLocation(HInstruction* instruction, |
| 771 | HInstruction* ref, |
| 772 | size_t offset, |
| 773 | HInstruction* index, |
| 774 | int16_t declaring_class_def_index) { |
| 775 | HInstruction* original_ref = HuntForOriginalReference(ref); |
| 776 | ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref); |
| 777 | size_t idx = heap_location_collector_.FindHeapLocationIndex( |
| 778 | ref_info, offset, index, declaring_class_def_index); |
| 779 | DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); |
| 780 | ArenaVector<HInstruction*>& heap_values = |
| 781 | heap_values_for_[instruction->GetBlock()->GetBlockId()]; |
| 782 | HInstruction* heap_value = heap_values[idx]; |
| 783 | if (heap_value == kDefaultHeapValue) { |
| 784 | HInstruction* constant = GetDefaultValue(instruction->GetType()); |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 785 | removed_loads_.push_back(instruction); |
| 786 | substitute_instructions_for_loads_.push_back(constant); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 787 | heap_values[idx] = constant; |
| 788 | return; |
| 789 | } |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 790 | if (heap_value != kUnknownHeapValue && heap_value->IsInstanceFieldSet()) { |
| 791 | HInstruction* store = heap_value; |
| 792 | // This load must be from a singleton since it's from the same field |
| 793 | // that a "removed" store puts the value. That store must be to a singleton's field. |
| 794 | DCHECK(ref_info->IsSingleton()); |
| 795 | // Get the real heap value of the store. |
| 796 | heap_value = store->InputAt(1); |
| 797 | } |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 798 | if (heap_value == kUnknownHeapValue) { |
| 799 | // Load isn't eliminated. Put the load as the value into the HeapLocation. |
| 800 | // This acts like GVN but with better aliasing analysis. |
| 801 | heap_values[idx] = instruction; |
| 802 | } else { |
Nicolas Geoffray | 0397163 | 2016-03-17 10:44:24 +0000 | [diff] [blame] | 803 | if (Primitive::PrimitiveKind(heap_value->GetType()) |
| 804 | != Primitive::PrimitiveKind(instruction->GetType())) { |
| 805 | // The only situation where the same heap location has different type is when |
Nicolas Geoffray | 65fef30 | 2016-05-04 14:00:12 +0100 | [diff] [blame] | 806 | // we do an array get on an instruction that originates from the null constant |
| 807 | // (the null could be behind a field access, an array access, a null check or |
| 808 | // a bound type). |
| 809 | // In order to stay properly typed on primitive types, we do not eliminate |
| 810 | // the array gets. |
Nicolas Geoffray | 0397163 | 2016-03-17 10:44:24 +0000 | [diff] [blame] | 811 | if (kIsDebugBuild) { |
| 812 | DCHECK(heap_value->IsArrayGet()) << heap_value->DebugName(); |
| 813 | DCHECK(instruction->IsArrayGet()) << instruction->DebugName(); |
Nicolas Geoffray | 0397163 | 2016-03-17 10:44:24 +0000 | [diff] [blame] | 814 | } |
| 815 | return; |
| 816 | } |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 817 | removed_loads_.push_back(instruction); |
| 818 | substitute_instructions_for_loads_.push_back(heap_value); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 819 | TryRemovingNullCheck(instruction); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 820 | } |
| 821 | } |
| 822 | |
| 823 | bool Equal(HInstruction* heap_value, HInstruction* value) { |
| 824 | if (heap_value == value) { |
| 825 | return true; |
| 826 | } |
| 827 | if (heap_value == kDefaultHeapValue && GetDefaultValue(value->GetType()) == value) { |
| 828 | return true; |
| 829 | } |
| 830 | return false; |
| 831 | } |
| 832 | |
| 833 | void VisitSetLocation(HInstruction* instruction, |
| 834 | HInstruction* ref, |
| 835 | size_t offset, |
| 836 | HInstruction* index, |
| 837 | int16_t declaring_class_def_index, |
| 838 | HInstruction* value) { |
| 839 | HInstruction* original_ref = HuntForOriginalReference(ref); |
| 840 | ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref); |
| 841 | size_t idx = heap_location_collector_.FindHeapLocationIndex( |
| 842 | ref_info, offset, index, declaring_class_def_index); |
| 843 | DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); |
| 844 | ArenaVector<HInstruction*>& heap_values = |
| 845 | heap_values_for_[instruction->GetBlock()->GetBlockId()]; |
| 846 | HInstruction* heap_value = heap_values[idx]; |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 847 | bool same_value = false; |
| 848 | bool possibly_redundant = false; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 849 | if (Equal(heap_value, value)) { |
| 850 | // Store into the heap location with the same value. |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 851 | same_value = true; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 852 | } else if (index != nullptr) { |
| 853 | // For array element, don't eliminate stores since it can be easily aliased |
| 854 | // with non-constant index. |
Mingyao Yang | e58bdca | 2016-10-28 11:07:24 -0700 | [diff] [blame] | 855 | } else if (ref_info->IsSingletonAndNonEscaping()) { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 856 | // Store into a field of a singleton that's not returned. The value cannot be |
| 857 | // killed due to aliasing/invocation. It can be redundant since future loads can |
| 858 | // directly get the value set by this instruction. The value can still be killed due to |
| 859 | // merging or loop side effects. Stores whose values are killed due to merging/loop side |
| 860 | // effects later will be removed from possibly_removed_stores_ when that is detected. |
| 861 | possibly_redundant = true; |
| 862 | HNewInstance* new_instance = ref_info->GetReference()->AsNewInstance(); |
| 863 | DCHECK(new_instance != nullptr); |
| 864 | if (new_instance->IsFinalizable()) { |
| 865 | // Finalizable objects escape globally. Need to keep the store. |
| 866 | possibly_redundant = false; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 867 | } else { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 868 | HLoopInformation* loop_info = instruction->GetBlock()->GetLoopInformation(); |
| 869 | if (loop_info != nullptr) { |
| 870 | // instruction is a store in the loop so the loop must does write. |
| 871 | DCHECK(side_effects_.GetLoopEffects(loop_info->GetHeader()).DoesAnyWrite()); |
| 872 | |
Mingyao Yang | 4b467ed | 2015-11-19 17:04:22 -0800 | [diff] [blame] | 873 | if (loop_info->IsDefinedOutOfTheLoop(original_ref)) { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 874 | DCHECK(original_ref->GetBlock()->Dominates(loop_info->GetPreHeader())); |
| 875 | // Keep the store since its value may be needed at the loop header. |
| 876 | possibly_redundant = false; |
| 877 | } else { |
| 878 | // The singleton is created inside the loop. Value stored to it isn't needed at |
| 879 | // the loop header. This is true for outer loops also. |
| 880 | } |
| 881 | } |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 882 | } |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 883 | } |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 884 | if (same_value || possibly_redundant) { |
| 885 | possibly_removed_stores_.push_back(instruction); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 886 | } |
Mingyao Yang | e9d6e60 | 2015-10-23 17:08:42 -0700 | [diff] [blame] | 887 | |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 888 | if (!same_value) { |
| 889 | if (possibly_redundant) { |
| 890 | DCHECK(instruction->IsInstanceFieldSet()); |
| 891 | // Put the store as the heap value. If the value is loaded from heap |
| 892 | // by a load later, this store isn't really redundant. |
| 893 | heap_values[idx] = instruction; |
| 894 | } else { |
| 895 | heap_values[idx] = value; |
| 896 | } |
| 897 | } |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 898 | // This store may kill values in other heap locations due to aliasing. |
| 899 | for (size_t i = 0; i < heap_values.size(); i++) { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 900 | if (i == idx) { |
| 901 | continue; |
| 902 | } |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 903 | if (heap_values[i] == value) { |
| 904 | // Same value should be kept even if aliasing happens. |
| 905 | continue; |
| 906 | } |
| 907 | if (heap_values[i] == kUnknownHeapValue) { |
| 908 | // Value is already unknown, no need for aliasing check. |
| 909 | continue; |
| 910 | } |
| 911 | if (heap_location_collector_.MayAlias(i, idx)) { |
| 912 | // Kill heap locations that may alias. |
| 913 | heap_values[i] = kUnknownHeapValue; |
| 914 | } |
| 915 | } |
| 916 | } |
| 917 | |
| 918 | void VisitInstanceFieldGet(HInstanceFieldGet* instruction) OVERRIDE { |
| 919 | HInstruction* obj = instruction->InputAt(0); |
| 920 | size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); |
| 921 | int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); |
| 922 | VisitGetLocation(instruction, obj, offset, nullptr, declaring_class_def_index); |
| 923 | } |
| 924 | |
| 925 | void VisitInstanceFieldSet(HInstanceFieldSet* instruction) OVERRIDE { |
| 926 | HInstruction* obj = instruction->InputAt(0); |
| 927 | size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); |
| 928 | int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); |
| 929 | HInstruction* value = instruction->InputAt(1); |
| 930 | VisitSetLocation(instruction, obj, offset, nullptr, declaring_class_def_index, value); |
| 931 | } |
| 932 | |
| 933 | void VisitStaticFieldGet(HStaticFieldGet* instruction) OVERRIDE { |
| 934 | HInstruction* cls = instruction->InputAt(0); |
| 935 | size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); |
| 936 | int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); |
| 937 | VisitGetLocation(instruction, cls, offset, nullptr, declaring_class_def_index); |
| 938 | } |
| 939 | |
| 940 | void VisitStaticFieldSet(HStaticFieldSet* instruction) OVERRIDE { |
| 941 | HInstruction* cls = instruction->InputAt(0); |
| 942 | size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); |
| 943 | int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); |
| 944 | HInstruction* value = instruction->InputAt(1); |
| 945 | VisitSetLocation(instruction, cls, offset, nullptr, declaring_class_def_index, value); |
| 946 | } |
| 947 | |
| 948 | void VisitArrayGet(HArrayGet* instruction) OVERRIDE { |
| 949 | HInstruction* array = instruction->InputAt(0); |
| 950 | HInstruction* index = instruction->InputAt(1); |
| 951 | VisitGetLocation(instruction, |
| 952 | array, |
| 953 | HeapLocation::kInvalidFieldOffset, |
| 954 | index, |
| 955 | HeapLocation::kDeclaringClassDefIndexForArrays); |
| 956 | } |
| 957 | |
| 958 | void VisitArraySet(HArraySet* instruction) OVERRIDE { |
| 959 | HInstruction* array = instruction->InputAt(0); |
| 960 | HInstruction* index = instruction->InputAt(1); |
| 961 | HInstruction* value = instruction->InputAt(2); |
| 962 | VisitSetLocation(instruction, |
| 963 | array, |
| 964 | HeapLocation::kInvalidFieldOffset, |
| 965 | index, |
| 966 | HeapLocation::kDeclaringClassDefIndexForArrays, |
| 967 | value); |
| 968 | } |
| 969 | |
| 970 | void HandleInvoke(HInstruction* invoke) { |
| 971 | ArenaVector<HInstruction*>& heap_values = |
| 972 | heap_values_for_[invoke->GetBlock()->GetBlockId()]; |
| 973 | for (size_t i = 0; i < heap_values.size(); i++) { |
| 974 | ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo(); |
| 975 | if (ref_info->IsSingleton()) { |
| 976 | // Singleton references cannot be seen by the callee. |
| 977 | } else { |
| 978 | heap_values[i] = kUnknownHeapValue; |
| 979 | } |
| 980 | } |
| 981 | } |
| 982 | |
| 983 | void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) OVERRIDE { |
| 984 | HandleInvoke(invoke); |
| 985 | } |
| 986 | |
| 987 | void VisitInvokeVirtual(HInvokeVirtual* invoke) OVERRIDE { |
| 988 | HandleInvoke(invoke); |
| 989 | } |
| 990 | |
| 991 | void VisitInvokeInterface(HInvokeInterface* invoke) OVERRIDE { |
| 992 | HandleInvoke(invoke); |
| 993 | } |
| 994 | |
| 995 | void VisitInvokeUnresolved(HInvokeUnresolved* invoke) OVERRIDE { |
| 996 | HandleInvoke(invoke); |
| 997 | } |
| 998 | |
| 999 | void VisitClinitCheck(HClinitCheck* clinit) OVERRIDE { |
| 1000 | HandleInvoke(clinit); |
| 1001 | } |
| 1002 | |
| 1003 | void VisitUnresolvedInstanceFieldGet(HUnresolvedInstanceFieldGet* instruction) OVERRIDE { |
| 1004 | // Conservatively treat it as an invocation. |
| 1005 | HandleInvoke(instruction); |
| 1006 | } |
| 1007 | |
| 1008 | void VisitUnresolvedInstanceFieldSet(HUnresolvedInstanceFieldSet* instruction) OVERRIDE { |
| 1009 | // Conservatively treat it as an invocation. |
| 1010 | HandleInvoke(instruction); |
| 1011 | } |
| 1012 | |
| 1013 | void VisitUnresolvedStaticFieldGet(HUnresolvedStaticFieldGet* instruction) OVERRIDE { |
| 1014 | // Conservatively treat it as an invocation. |
| 1015 | HandleInvoke(instruction); |
| 1016 | } |
| 1017 | |
| 1018 | void VisitUnresolvedStaticFieldSet(HUnresolvedStaticFieldSet* instruction) OVERRIDE { |
| 1019 | // Conservatively treat it as an invocation. |
| 1020 | HandleInvoke(instruction); |
| 1021 | } |
| 1022 | |
| 1023 | void VisitNewInstance(HNewInstance* new_instance) OVERRIDE { |
| 1024 | ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(new_instance); |
| 1025 | if (ref_info == nullptr) { |
| 1026 | // new_instance isn't used for field accesses. No need to process it. |
| 1027 | return; |
| 1028 | } |
Mingyao Yang | e58bdca | 2016-10-28 11:07:24 -0700 | [diff] [blame] | 1029 | if (ref_info->IsSingletonAndNonEscaping() && |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 1030 | !new_instance->IsFinalizable() && |
Mingyao Yang | 062157f | 2016-03-02 10:15:36 -0800 | [diff] [blame] | 1031 | !new_instance->NeedsAccessCheck()) { |
| 1032 | singleton_new_instances_.push_back(new_instance); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 1033 | } |
| 1034 | ArenaVector<HInstruction*>& heap_values = |
| 1035 | heap_values_for_[new_instance->GetBlock()->GetBlockId()]; |
| 1036 | for (size_t i = 0; i < heap_values.size(); i++) { |
| 1037 | HInstruction* ref = |
| 1038 | heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo()->GetReference(); |
| 1039 | size_t offset = heap_location_collector_.GetHeapLocation(i)->GetOffset(); |
| 1040 | if (ref == new_instance && offset >= mirror::kObjectHeaderSize) { |
| 1041 | // Instance fields except the header fields are set to default heap values. |
| 1042 | heap_values[i] = kDefaultHeapValue; |
| 1043 | } |
| 1044 | } |
| 1045 | } |
| 1046 | |
| 1047 | // Find an instruction's substitute if it should be removed. |
| 1048 | // Return the same instruction if it should not be removed. |
| 1049 | HInstruction* FindSubstitute(HInstruction* instruction) { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 1050 | size_t size = removed_loads_.size(); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 1051 | for (size_t i = 0; i < size; i++) { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 1052 | if (removed_loads_[i] == instruction) { |
| 1053 | return substitute_instructions_for_loads_[i]; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 1054 | } |
| 1055 | } |
| 1056 | return instruction; |
| 1057 | } |
| 1058 | |
| 1059 | const HeapLocationCollector& heap_location_collector_; |
| 1060 | const SideEffectsAnalysis& side_effects_; |
| 1061 | |
| 1062 | // One array of heap values for each block. |
| 1063 | ArenaVector<ArenaVector<HInstruction*>> heap_values_for_; |
| 1064 | |
| 1065 | // We record the instructions that should be eliminated but may be |
| 1066 | // used by heap locations. They'll be removed in the end. |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 1067 | ArenaVector<HInstruction*> removed_loads_; |
| 1068 | ArenaVector<HInstruction*> substitute_instructions_for_loads_; |
| 1069 | |
| 1070 | // Stores in this list may be removed from the list later when it's |
| 1071 | // found that the store cannot be eliminated. |
| 1072 | ArenaVector<HInstruction*> possibly_removed_stores_; |
| 1073 | |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 1074 | ArenaVector<HInstruction*> singleton_new_instances_; |
| 1075 | |
| 1076 | DISALLOW_COPY_AND_ASSIGN(LSEVisitor); |
| 1077 | }; |
| 1078 | |
| 1079 | void LoadStoreElimination::Run() { |
David Brazdil | 8993caf | 2015-12-07 10:04:40 +0000 | [diff] [blame] | 1080 | if (graph_->IsDebuggable() || graph_->HasTryCatch()) { |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 1081 | // Debugger may set heap values or trigger deoptimization of callers. |
David Brazdil | 8993caf | 2015-12-07 10:04:40 +0000 | [diff] [blame] | 1082 | // Try/catch support not implemented yet. |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 1083 | // Skip this optimization. |
| 1084 | return; |
| 1085 | } |
| 1086 | HeapLocationCollector heap_location_collector(graph_); |
Vladimir Marko | 2c45bc9 | 2016-10-25 16:54:12 +0100 | [diff] [blame] | 1087 | for (HBasicBlock* block : graph_->GetReversePostOrder()) { |
| 1088 | heap_location_collector.VisitBasicBlock(block); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 1089 | } |
| 1090 | if (heap_location_collector.GetNumberOfHeapLocations() > kMaxNumberOfHeapLocations) { |
| 1091 | // Bail out if there are too many heap locations to deal with. |
| 1092 | return; |
| 1093 | } |
| 1094 | if (!heap_location_collector.HasHeapStores()) { |
| 1095 | // Without heap stores, this pass would act mostly as GVN on heap accesses. |
| 1096 | return; |
| 1097 | } |
| 1098 | if (heap_location_collector.HasVolatile() || heap_location_collector.HasMonitorOps()) { |
| 1099 | // Don't do load/store elimination if the method has volatile field accesses or |
| 1100 | // monitor operations, for now. |
| 1101 | // TODO: do it right. |
| 1102 | return; |
| 1103 | } |
| 1104 | heap_location_collector.BuildAliasingMatrix(); |
| 1105 | LSEVisitor lse_visitor(graph_, heap_location_collector, side_effects_); |
Vladimir Marko | 2c45bc9 | 2016-10-25 16:54:12 +0100 | [diff] [blame] | 1106 | for (HBasicBlock* block : graph_->GetReversePostOrder()) { |
| 1107 | lse_visitor.VisitBasicBlock(block); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 1108 | } |
| 1109 | lse_visitor.RemoveInstructions(); |
| 1110 | } |
| 1111 | |
| 1112 | } // namespace art |