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