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