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 19 #include "base/array_ref.h" 20 #include "base/scoped_arena_allocator.h" 21 #include "base/scoped_arena_containers.h" 22 #include "escape.h" 23 #include "load_store_analysis.h" 24 #include "side_effects_analysis.h" 25 26 #include <iostream> 27 28 /** 29 * The general algorithm of load-store elimination (LSE). 30 * Load-store analysis in the previous pass collects a list of heap locations 31 * and does alias analysis of those heap locations. 32 * LSE keeps track of a list of heap values corresponding to the heap 33 * locations. It visits basic blocks in reverse post order and for 34 * each basic block, visits instructions sequentially, and processes 35 * instructions as follows: 36 * - If the instruction is a load, and the heap location for that load has a 37 * valid heap value, the load can be eliminated. In order to maintain the 38 * validity of all heap locations during the optimization phase, the real 39 * elimination is delayed till the end of LSE. 40 * - If the instruction is a store, it updates the heap value for the heap 41 * location of the store with the store instruction. The real heap value 42 * can be fetched from the store instruction. Heap values are invalidated 43 * for heap locations that may alias with the store instruction's heap 44 * location. The store instruction can be eliminated unless the value stored 45 * is later needed e.g. by a load from the same/aliased heap location or 46 * the heap location persists at method return/deoptimization. 47 * The store instruction is also needed if it's not used to track the heap 48 * value anymore, e.g. when it fails to merge with the heap values from other 49 * predecessors. 50 * - A store that stores the same value as the heap value is eliminated. 51 * - The list of heap values are merged at basic block entry from the basic 52 * block's predecessors. The algorithm is single-pass, so loop side-effects is 53 * used as best effort to decide if a heap location is stored inside the loop. 54 * - A special type of objects called singletons are instantiated in the method 55 * and have a single name, i.e. no aliases. Singletons have exclusive heap 56 * locations since they have no aliases. Singletons are helpful in narrowing 57 * down the life span of a heap location such that they do not always 58 * need to participate in merging heap values. Allocation of a singleton 59 * can be eliminated if that singleton is not used and does not persist 60 * at method return/deoptimization. 61 * - For newly instantiated instances, their heap values are initialized to 62 * language defined default values. 63 * - Some instructions such as invokes are treated as loading and invalidating 64 * all the heap values, depending on the instruction's side effects. 65 * - Finalizable objects are considered as persisting at method 66 * return/deoptimization. 67 * - Currently this LSE algorithm doesn't handle SIMD graph, e.g. with VecLoad 68 * and VecStore instructions. 69 * - Currently this LSE algorithm doesn't handle graph with try-catch, due to 70 * the special block merging structure. 71 */ 72 73 namespace art { 74 75 // An unknown heap value. Loads with such a value in the heap location cannot be eliminated. 76 // A heap location can be set to kUnknownHeapValue when: 77 // - initially set a value. 78 // - killed due to aliasing, merging, invocation, or loop side effects. 79 static HInstruction* const kUnknownHeapValue = 80 reinterpret_cast<HInstruction*>(static_cast<uintptr_t>(-1)); 81 82 // Default heap value after an allocation. 83 // A heap location can be set to that value right after an allocation. 84 static HInstruction* const kDefaultHeapValue = 85 reinterpret_cast<HInstruction*>(static_cast<uintptr_t>(-2)); 86 87 // Use HGraphDelegateVisitor for which all VisitInvokeXXX() delegate to VisitInvoke(). 88 class LSEVisitor : public HGraphDelegateVisitor { 89 public: 90 LSEVisitor(HGraph* graph, 91 const HeapLocationCollector& heap_locations_collector, 92 const SideEffectsAnalysis& side_effects, 93 OptimizingCompilerStats* stats) 94 : HGraphDelegateVisitor(graph, stats), 95 heap_location_collector_(heap_locations_collector), 96 side_effects_(side_effects), 97 allocator_(graph->GetArenaStack()), 98 heap_values_for_(graph->GetBlocks().size(), 99 ScopedArenaVector<HInstruction*>(heap_locations_collector. 100 GetNumberOfHeapLocations(), 101 kUnknownHeapValue, 102 allocator_.Adapter(kArenaAllocLSE)), 103 allocator_.Adapter(kArenaAllocLSE)), 104 removed_loads_(allocator_.Adapter(kArenaAllocLSE)), 105 substitute_instructions_for_loads_(allocator_.Adapter(kArenaAllocLSE)), 106 possibly_removed_stores_(allocator_.Adapter(kArenaAllocLSE)), 107 singleton_new_instances_(allocator_.Adapter(kArenaAllocLSE)) { 108 } 109 110 void VisitBasicBlock(HBasicBlock* block) OVERRIDE { 111 // Populate the heap_values array for this block. 112 // TODO: try to reuse the heap_values array from one predecessor if possible. 113 if (block->IsLoopHeader()) { 114 HandleLoopSideEffects(block); 115 } else { 116 MergePredecessorValues(block); 117 } 118 HGraphVisitor::VisitBasicBlock(block); 119 } 120 121 HTypeConversion* AddTypeConversionIfNecessary(HInstruction* instruction, 122 HInstruction* value, 123 DataType::Type expected_type) { 124 HTypeConversion* type_conversion = nullptr; 125 // Should never add type conversion into boolean value. 126 if (expected_type != DataType::Type::kBool && 127 !DataType::IsTypeConversionImplicit(value->GetType(), expected_type)) { 128 type_conversion = new (GetGraph()->GetAllocator()) HTypeConversion( 129 expected_type, value, instruction->GetDexPc()); 130 instruction->GetBlock()->InsertInstructionBefore(type_conversion, instruction); 131 } 132 return type_conversion; 133 } 134 135 // Find an instruction's substitute if it's a removed load. 136 // Return the same instruction if it should not be removed. 137 HInstruction* FindSubstitute(HInstruction* instruction) { 138 if (!IsLoad(instruction)) { 139 return instruction; 140 } 141 size_t size = removed_loads_.size(); 142 for (size_t i = 0; i < size; i++) { 143 if (removed_loads_[i] == instruction) { 144 HInstruction* substitute = substitute_instructions_for_loads_[i]; 145 // The substitute list is a flat hierarchy. 146 DCHECK_EQ(FindSubstitute(substitute), substitute); 147 return substitute; 148 } 149 } 150 return instruction; 151 } 152 153 void AddRemovedLoad(HInstruction* load, HInstruction* heap_value) { 154 DCHECK(IsLoad(load)); 155 DCHECK_EQ(FindSubstitute(heap_value), heap_value) << 156 "Unexpected heap_value that has a substitute " << heap_value->DebugName(); 157 removed_loads_.push_back(load); 158 substitute_instructions_for_loads_.push_back(heap_value); 159 } 160 161 // Scan the list of removed loads to see if we can reuse `type_conversion`, if 162 // the other removed load has the same substitute and type and is dominated 163 // by `type_conversioni`. 164 void TryToReuseTypeConversion(HInstruction* type_conversion, size_t index) { 165 size_t size = removed_loads_.size(); 166 HInstruction* load = removed_loads_[index]; 167 HInstruction* substitute = substitute_instructions_for_loads_[index]; 168 for (size_t j = index + 1; j < size; j++) { 169 HInstruction* load2 = removed_loads_[j]; 170 HInstruction* substitute2 = substitute_instructions_for_loads_[j]; 171 if (load2 == nullptr) { 172 DCHECK(substitute2->IsTypeConversion()); 173 continue; 174 } 175 DCHECK(load2->IsInstanceFieldGet() || 176 load2->IsStaticFieldGet() || 177 load2->IsArrayGet()); 178 DCHECK(substitute2 != nullptr); 179 if (substitute2 == substitute && 180 load2->GetType() == load->GetType() && 181 type_conversion->GetBlock()->Dominates(load2->GetBlock()) && 182 // Don't share across irreducible loop headers. 183 // TODO: can be more fine-grained than this by testing each dominator. 184 (load2->GetBlock() == type_conversion->GetBlock() || 185 !GetGraph()->HasIrreducibleLoops())) { 186 // The removed_loads_ are added in reverse post order. 187 DCHECK(type_conversion->StrictlyDominates(load2)); 188 load2->ReplaceWith(type_conversion); 189 load2->GetBlock()->RemoveInstruction(load2); 190 removed_loads_[j] = nullptr; 191 substitute_instructions_for_loads_[j] = type_conversion; 192 } 193 } 194 } 195 196 // Remove recorded instructions that should be eliminated. 197 void RemoveInstructions() { 198 size_t size = removed_loads_.size(); 199 DCHECK_EQ(size, substitute_instructions_for_loads_.size()); 200 for (size_t i = 0; i < size; i++) { 201 HInstruction* load = removed_loads_[i]; 202 if (load == nullptr) { 203 // The load has been handled in the scan for type conversion below. 204 DCHECK(substitute_instructions_for_loads_[i]->IsTypeConversion()); 205 continue; 206 } 207 DCHECK(load->IsInstanceFieldGet() || 208 load->IsStaticFieldGet() || 209 load->IsArrayGet()); 210 HInstruction* substitute = substitute_instructions_for_loads_[i]; 211 DCHECK(substitute != nullptr); 212 // We proactively retrieve the substitute for a removed load, so 213 // a load that has a substitute should not be observed as a heap 214 // location value. 215 DCHECK_EQ(FindSubstitute(substitute), substitute); 216 217 // The load expects to load the heap value as type load->GetType(). 218 // However the tracked heap value may not be of that type. An explicit 219 // type conversion may be needed. 220 // There are actually three types involved here: 221 // (1) tracked heap value's type (type A) 222 // (2) heap location (field or element)'s type (type B) 223 // (3) load's type (type C) 224 // We guarantee that type A stored as type B and then fetched out as 225 // type C is the same as casting from type A to type C directly, since 226 // type B and type C will have the same size which is guarenteed in 227 // HInstanceFieldGet/HStaticFieldGet/HArrayGet's SetType(). 228 // So we only need one type conversion from type A to type C. 229 HTypeConversion* type_conversion = AddTypeConversionIfNecessary( 230 load, substitute, load->GetType()); 231 if (type_conversion != nullptr) { 232 TryToReuseTypeConversion(type_conversion, i); 233 load->ReplaceWith(type_conversion); 234 substitute_instructions_for_loads_[i] = type_conversion; 235 } else { 236 load->ReplaceWith(substitute); 237 } 238 load->GetBlock()->RemoveInstruction(load); 239 } 240 241 // At this point, stores in possibly_removed_stores_ can be safely removed. 242 for (HInstruction* store : possibly_removed_stores_) { 243 DCHECK(store->IsInstanceFieldSet() || store->IsStaticFieldSet() || store->IsArraySet()); 244 store->GetBlock()->RemoveInstruction(store); 245 } 246 247 // Eliminate singleton-classified instructions: 248 // * - Constructor fences (they never escape this thread). 249 // * - Allocations (if they are unused). 250 for (HInstruction* new_instance : singleton_new_instances_) { 251 size_t removed = HConstructorFence::RemoveConstructorFences(new_instance); 252 MaybeRecordStat(stats_, 253 MethodCompilationStat::kConstructorFenceRemovedLSE, 254 removed); 255 256 if (!new_instance->HasNonEnvironmentUses()) { 257 new_instance->RemoveEnvironmentUsers(); 258 new_instance->GetBlock()->RemoveInstruction(new_instance); 259 } 260 } 261 } 262 263 private: 264 static bool IsLoad(HInstruction* instruction) { 265 if (instruction == kUnknownHeapValue || instruction == kDefaultHeapValue) { 266 return false; 267 } 268 // Unresolved load is not treated as a load. 269 return instruction->IsInstanceFieldGet() || 270 instruction->IsStaticFieldGet() || 271 instruction->IsArrayGet(); 272 } 273 274 static bool IsStore(HInstruction* instruction) { 275 if (instruction == kUnknownHeapValue || instruction == kDefaultHeapValue) { 276 return false; 277 } 278 // Unresolved store is not treated as a store. 279 return instruction->IsInstanceFieldSet() || 280 instruction->IsArraySet() || 281 instruction->IsStaticFieldSet(); 282 } 283 284 // Returns the real heap value by finding its substitute or by "peeling" 285 // a store instruction. 286 HInstruction* GetRealHeapValue(HInstruction* heap_value) { 287 if (IsLoad(heap_value)) { 288 return FindSubstitute(heap_value); 289 } 290 if (!IsStore(heap_value)) { 291 return heap_value; 292 } 293 294 // We keep track of store instructions as the heap values which might be 295 // eliminated if the stores are later found not necessary. The real stored 296 // value needs to be fetched from the store instruction. 297 if (heap_value->IsInstanceFieldSet()) { 298 heap_value = heap_value->AsInstanceFieldSet()->GetValue(); 299 } else if (heap_value->IsStaticFieldSet()) { 300 heap_value = heap_value->AsStaticFieldSet()->GetValue(); 301 } else { 302 DCHECK(heap_value->IsArraySet()); 303 heap_value = heap_value->AsArraySet()->GetValue(); 304 } 305 // heap_value may already be a removed load. 306 return FindSubstitute(heap_value); 307 } 308 309 // If heap_value is a store, need to keep the store. 310 // This is necessary if a heap value is killed or replaced by another value, 311 // so that the store is no longer used to track heap value. 312 void KeepIfIsStore(HInstruction* heap_value) { 313 if (!IsStore(heap_value)) { 314 return; 315 } 316 auto idx = std::find(possibly_removed_stores_.begin(), 317 possibly_removed_stores_.end(), heap_value); 318 if (idx != possibly_removed_stores_.end()) { 319 // Make sure the store is kept. 320 possibly_removed_stores_.erase(idx); 321 } 322 } 323 324 // If a heap location X may alias with heap location at `loc_index` 325 // and heap_values of that heap location X holds a store, keep that store. 326 // It's needed for a dependent load that's not eliminated since any store 327 // that may put value into the load's heap location needs to be kept. 328 void KeepStoresIfAliasedToLocation(ScopedArenaVector<HInstruction*>& heap_values, 329 size_t loc_index) { 330 for (size_t i = 0; i < heap_values.size(); i++) { 331 if ((i == loc_index) || heap_location_collector_.MayAlias(i, loc_index)) { 332 KeepIfIsStore(heap_values[i]); 333 } 334 } 335 } 336 337 void HandleLoopSideEffects(HBasicBlock* block) { 338 DCHECK(block->IsLoopHeader()); 339 int block_id = block->GetBlockId(); 340 ScopedArenaVector<HInstruction*>& heap_values = heap_values_for_[block_id]; 341 HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader(); 342 ScopedArenaVector<HInstruction*>& pre_header_heap_values = 343 heap_values_for_[pre_header->GetBlockId()]; 344 345 // Don't eliminate loads in irreducible loops. 346 // Also keep the stores before the loop. 347 if (block->GetLoopInformation()->IsIrreducible()) { 348 if (kIsDebugBuild) { 349 for (size_t i = 0; i < heap_values.size(); i++) { 350 DCHECK_EQ(heap_values[i], kUnknownHeapValue); 351 } 352 } 353 for (size_t i = 0; i < heap_values.size(); i++) { 354 KeepIfIsStore(pre_header_heap_values[i]); 355 } 356 return; 357 } 358 359 // Inherit the values from pre-header. 360 for (size_t i = 0; i < heap_values.size(); i++) { 361 heap_values[i] = pre_header_heap_values[i]; 362 } 363 364 // We do a single pass in reverse post order. For loops, use the side effects as a hint 365 // to see if the heap values should be killed. 366 if (side_effects_.GetLoopEffects(block).DoesAnyWrite()) { 367 for (size_t i = 0; i < heap_values.size(); i++) { 368 HeapLocation* location = heap_location_collector_.GetHeapLocation(i); 369 ReferenceInfo* ref_info = location->GetReferenceInfo(); 370 if (ref_info->IsSingleton() && !location->IsValueKilledByLoopSideEffects()) { 371 // A singleton's field that's not stored into inside a loop is 372 // invariant throughout the loop. Nothing to do. 373 } else { 374 // heap value is killed by loop side effects. 375 KeepIfIsStore(pre_header_heap_values[i]); 376 heap_values[i] = kUnknownHeapValue; 377 } 378 } 379 } else { 380 // The loop doesn't kill any value. 381 } 382 } 383 384 void MergePredecessorValues(HBasicBlock* block) { 385 ArrayRef<HBasicBlock* const> predecessors(block->GetPredecessors()); 386 if (predecessors.size() == 0) { 387 return; 388 } 389 if (block->IsExitBlock()) { 390 // Exit block doesn't really merge values since the control flow ends in 391 // its predecessors. Each predecessor needs to make sure stores are kept 392 // if necessary. 393 return; 394 } 395 396 ScopedArenaVector<HInstruction*>& heap_values = heap_values_for_[block->GetBlockId()]; 397 for (size_t i = 0; i < heap_values.size(); i++) { 398 HInstruction* merged_value = nullptr; 399 // If we can merge the store itself from the predecessors, we keep 400 // the store as the heap value as long as possible. In case we cannot 401 // merge the store, we try to merge the values of the stores. 402 HInstruction* merged_store_value = nullptr; 403 // Whether merged_value is a result that's merged from all predecessors. 404 bool from_all_predecessors = true; 405 ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo(); 406 HInstruction* ref = ref_info->GetReference(); 407 HInstruction* singleton_ref = nullptr; 408 if (ref_info->IsSingleton()) { 409 // We do more analysis based on singleton's liveness when merging 410 // heap values for such cases. 411 singleton_ref = ref; 412 } 413 414 for (HBasicBlock* predecessor : predecessors) { 415 HInstruction* pred_value = heap_values_for_[predecessor->GetBlockId()][i]; 416 if (!IsStore(pred_value)) { 417 pred_value = FindSubstitute(pred_value); 418 } 419 DCHECK(pred_value != nullptr); 420 HInstruction* pred_store_value = GetRealHeapValue(pred_value); 421 if ((singleton_ref != nullptr) && 422 !singleton_ref->GetBlock()->Dominates(predecessor)) { 423 // singleton_ref is not live in this predecessor. No need to merge 424 // since singleton_ref is not live at the beginning of this block. 425 DCHECK_EQ(pred_value, kUnknownHeapValue); 426 from_all_predecessors = false; 427 break; 428 } 429 if (merged_value == nullptr) { 430 // First seen heap value. 431 DCHECK(pred_value != nullptr); 432 merged_value = pred_value; 433 } else if (pred_value != merged_value) { 434 // There are conflicting values. 435 merged_value = kUnknownHeapValue; 436 // We may still be able to merge store values. 437 } 438 439 // Conflicting stores may be storing the same value. We do another merge 440 // of real stored values. 441 if (merged_store_value == nullptr) { 442 // First seen store value. 443 DCHECK(pred_store_value != nullptr); 444 merged_store_value = pred_store_value; 445 } else if (pred_store_value != merged_store_value) { 446 // There are conflicting store values. 447 merged_store_value = kUnknownHeapValue; 448 // There must be conflicting stores also. 449 DCHECK_EQ(merged_value, kUnknownHeapValue); 450 // No need to merge anymore. 451 break; 452 } 453 } 454 455 if (merged_value == nullptr) { 456 DCHECK(!from_all_predecessors); 457 DCHECK(singleton_ref != nullptr); 458 } 459 if (from_all_predecessors) { 460 if (ref_info->IsSingletonAndRemovable() && 461 block->IsSingleReturnOrReturnVoidAllowingPhis()) { 462 // Values in the singleton are not needed anymore. 463 } else if (!IsStore(merged_value)) { 464 // We don't track merged value as a store anymore. We have to 465 // hold the stores in predecessors live here. 466 for (HBasicBlock* predecessor : predecessors) { 467 ScopedArenaVector<HInstruction*>& pred_values = 468 heap_values_for_[predecessor->GetBlockId()]; 469 KeepIfIsStore(pred_values[i]); 470 } 471 } 472 } else { 473 DCHECK(singleton_ref != nullptr); 474 // singleton_ref is non-existing at the beginning of the block. There is 475 // no need to keep the stores. 476 } 477 478 if (!from_all_predecessors) { 479 DCHECK(singleton_ref != nullptr); 480 DCHECK((singleton_ref->GetBlock() == block) || 481 !singleton_ref->GetBlock()->Dominates(block)) 482 << "method: " << GetGraph()->GetMethodName(); 483 // singleton_ref is not defined before block or defined only in some of its 484 // predecessors, so block doesn't really have the location at its entry. 485 heap_values[i] = kUnknownHeapValue; 486 } else if (predecessors.size() == 1) { 487 // Inherit heap value from the single predecessor. 488 DCHECK_EQ(heap_values_for_[predecessors[0]->GetBlockId()][i], merged_value); 489 heap_values[i] = merged_value; 490 } else { 491 DCHECK(merged_value == kUnknownHeapValue || 492 merged_value == kDefaultHeapValue || 493 merged_value->GetBlock()->Dominates(block)); 494 if (merged_value != kUnknownHeapValue) { 495 heap_values[i] = merged_value; 496 } else { 497 // Stores in different predecessors may be storing the same value. 498 heap_values[i] = merged_store_value; 499 } 500 } 501 } 502 } 503 504 // `instruction` is being removed. Try to see if the null check on it 505 // can be removed. This can happen if the same value is set in two branches 506 // but not in dominators. Such as: 507 // int[] a = foo(); 508 // if () { 509 // a[0] = 2; 510 // } else { 511 // a[0] = 2; 512 // } 513 // // a[0] can now be replaced with constant 2, and the null check on it can be removed. 514 void TryRemovingNullCheck(HInstruction* instruction) { 515 HInstruction* prev = instruction->GetPrevious(); 516 if ((prev != nullptr) && prev->IsNullCheck() && (prev == instruction->InputAt(0))) { 517 // Previous instruction is a null check for this instruction. Remove the null check. 518 prev->ReplaceWith(prev->InputAt(0)); 519 prev->GetBlock()->RemoveInstruction(prev); 520 } 521 } 522 523 HInstruction* GetDefaultValue(DataType::Type type) { 524 switch (type) { 525 case DataType::Type::kReference: 526 return GetGraph()->GetNullConstant(); 527 case DataType::Type::kBool: 528 case DataType::Type::kUint8: 529 case DataType::Type::kInt8: 530 case DataType::Type::kUint16: 531 case DataType::Type::kInt16: 532 case DataType::Type::kInt32: 533 return GetGraph()->GetIntConstant(0); 534 case DataType::Type::kInt64: 535 return GetGraph()->GetLongConstant(0); 536 case DataType::Type::kFloat32: 537 return GetGraph()->GetFloatConstant(0); 538 case DataType::Type::kFloat64: 539 return GetGraph()->GetDoubleConstant(0); 540 default: 541 UNREACHABLE(); 542 } 543 } 544 545 void VisitGetLocation(HInstruction* instruction, 546 HInstruction* ref, 547 size_t offset, 548 HInstruction* index, 549 size_t vector_length, 550 int16_t declaring_class_def_index) { 551 HInstruction* original_ref = heap_location_collector_.HuntForOriginalReference(ref); 552 ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref); 553 size_t idx = heap_location_collector_.FindHeapLocationIndex( 554 ref_info, offset, index, vector_length, declaring_class_def_index); 555 DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); 556 ScopedArenaVector<HInstruction*>& heap_values = 557 heap_values_for_[instruction->GetBlock()->GetBlockId()]; 558 HInstruction* heap_value = heap_values[idx]; 559 if (heap_value == kDefaultHeapValue) { 560 HInstruction* constant = GetDefaultValue(instruction->GetType()); 561 AddRemovedLoad(instruction, constant); 562 heap_values[idx] = constant; 563 return; 564 } 565 heap_value = GetRealHeapValue(heap_value); 566 if (heap_value == kUnknownHeapValue) { 567 // Load isn't eliminated. Put the load as the value into the HeapLocation. 568 // This acts like GVN but with better aliasing analysis. 569 heap_values[idx] = instruction; 570 KeepStoresIfAliasedToLocation(heap_values, idx); 571 } else { 572 if (DataType::Kind(heap_value->GetType()) != DataType::Kind(instruction->GetType())) { 573 // The only situation where the same heap location has different type is when 574 // we do an array get on an instruction that originates from the null constant 575 // (the null could be behind a field access, an array access, a null check or 576 // a bound type). 577 // In order to stay properly typed on primitive types, we do not eliminate 578 // the array gets. 579 if (kIsDebugBuild) { 580 DCHECK(heap_value->IsArrayGet()) << heap_value->DebugName(); 581 DCHECK(instruction->IsArrayGet()) << instruction->DebugName(); 582 } 583 // Load isn't eliminated. Put the load as the value into the HeapLocation. 584 // This acts like GVN but with better aliasing analysis. 585 heap_values[idx] = instruction; 586 KeepStoresIfAliasedToLocation(heap_values, idx); 587 return; 588 } 589 AddRemovedLoad(instruction, heap_value); 590 TryRemovingNullCheck(instruction); 591 } 592 } 593 594 bool Equal(HInstruction* heap_value, HInstruction* value) { 595 DCHECK(!IsStore(value)) << value->DebugName(); 596 if (heap_value == kUnknownHeapValue) { 597 // Don't compare kUnknownHeapValue with other values. 598 return false; 599 } 600 if (heap_value == value) { 601 return true; 602 } 603 if (heap_value == kDefaultHeapValue && GetDefaultValue(value->GetType()) == value) { 604 return true; 605 } 606 HInstruction* real_heap_value = GetRealHeapValue(heap_value); 607 if (real_heap_value != heap_value) { 608 return Equal(real_heap_value, value); 609 } 610 return false; 611 } 612 613 void VisitSetLocation(HInstruction* instruction, 614 HInstruction* ref, 615 size_t offset, 616 HInstruction* index, 617 size_t vector_length, 618 int16_t declaring_class_def_index, 619 HInstruction* value) { 620 DCHECK(!IsStore(value)) << value->DebugName(); 621 // value may already have a substitute. 622 value = FindSubstitute(value); 623 HInstruction* original_ref = heap_location_collector_.HuntForOriginalReference(ref); 624 ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref); 625 size_t idx = heap_location_collector_.FindHeapLocationIndex( 626 ref_info, offset, index, vector_length, declaring_class_def_index); 627 DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); 628 ScopedArenaVector<HInstruction*>& heap_values = 629 heap_values_for_[instruction->GetBlock()->GetBlockId()]; 630 HInstruction* heap_value = heap_values[idx]; 631 bool possibly_redundant = false; 632 633 if (Equal(heap_value, value)) { 634 // Store into the heap location with the same value. 635 // This store can be eliminated right away. 636 instruction->GetBlock()->RemoveInstruction(instruction); 637 return; 638 } else { 639 HLoopInformation* loop_info = instruction->GetBlock()->GetLoopInformation(); 640 if (loop_info == nullptr) { 641 // Store is not in a loop. We try to precisely track the heap value by 642 // the store. 643 possibly_redundant = true; 644 } else if (!loop_info->IsIrreducible()) { 645 // instruction is a store in the loop so the loop must do write. 646 DCHECK(side_effects_.GetLoopEffects(loop_info->GetHeader()).DoesAnyWrite()); 647 if (ref_info->IsSingleton() && !loop_info->IsDefinedOutOfTheLoop(original_ref)) { 648 // original_ref is created inside the loop. Value stored to it isn't needed at 649 // the loop header. This is true for outer loops also. 650 possibly_redundant = true; 651 } else { 652 // Keep the store since its value may be needed at the loop header. 653 } 654 } else { 655 // Keep the store inside irreducible loops. 656 } 657 } 658 if (possibly_redundant) { 659 possibly_removed_stores_.push_back(instruction); 660 } 661 662 // Put the store as the heap value. If the value is loaded or needed after 663 // return/deoptimization later, this store isn't really redundant. 664 heap_values[idx] = instruction; 665 666 // This store may kill values in other heap locations due to aliasing. 667 for (size_t i = 0; i < heap_values.size(); i++) { 668 if (i == idx) { 669 continue; 670 } 671 if (Equal(heap_values[i], value)) { 672 // Same value should be kept even if aliasing happens. 673 continue; 674 } 675 if (heap_values[i] == kUnknownHeapValue) { 676 // Value is already unknown, no need for aliasing check. 677 continue; 678 } 679 if (heap_location_collector_.MayAlias(i, idx)) { 680 // Kill heap locations that may alias and as a result if the heap value 681 // is a store, the store needs to be kept. 682 KeepIfIsStore(heap_values[i]); 683 heap_values[i] = kUnknownHeapValue; 684 } 685 } 686 } 687 688 void VisitInstanceFieldGet(HInstanceFieldGet* instruction) OVERRIDE { 689 HInstruction* obj = instruction->InputAt(0); 690 size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); 691 int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); 692 VisitGetLocation(instruction, 693 obj, 694 offset, 695 nullptr, 696 HeapLocation::kScalar, 697 declaring_class_def_index); 698 } 699 700 void VisitInstanceFieldSet(HInstanceFieldSet* instruction) OVERRIDE { 701 HInstruction* obj = instruction->InputAt(0); 702 size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); 703 int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); 704 HInstruction* value = instruction->InputAt(1); 705 VisitSetLocation(instruction, 706 obj, 707 offset, 708 nullptr, 709 HeapLocation::kScalar, 710 declaring_class_def_index, 711 value); 712 } 713 714 void VisitStaticFieldGet(HStaticFieldGet* instruction) OVERRIDE { 715 HInstruction* cls = instruction->InputAt(0); 716 size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); 717 int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); 718 VisitGetLocation(instruction, 719 cls, 720 offset, 721 nullptr, 722 HeapLocation::kScalar, 723 declaring_class_def_index); 724 } 725 726 void VisitStaticFieldSet(HStaticFieldSet* instruction) OVERRIDE { 727 HInstruction* cls = instruction->InputAt(0); 728 size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); 729 int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); 730 HInstruction* value = instruction->InputAt(1); 731 VisitSetLocation(instruction, 732 cls, 733 offset, 734 nullptr, 735 HeapLocation::kScalar, 736 declaring_class_def_index, 737 value); 738 } 739 740 void VisitArrayGet(HArrayGet* instruction) OVERRIDE { 741 HInstruction* array = instruction->InputAt(0); 742 HInstruction* index = instruction->InputAt(1); 743 VisitGetLocation(instruction, 744 array, 745 HeapLocation::kInvalidFieldOffset, 746 index, 747 HeapLocation::kScalar, 748 HeapLocation::kDeclaringClassDefIndexForArrays); 749 } 750 751 void VisitArraySet(HArraySet* instruction) OVERRIDE { 752 HInstruction* array = instruction->InputAt(0); 753 HInstruction* index = instruction->InputAt(1); 754 HInstruction* value = instruction->InputAt(2); 755 VisitSetLocation(instruction, 756 array, 757 HeapLocation::kInvalidFieldOffset, 758 index, 759 HeapLocation::kScalar, 760 HeapLocation::kDeclaringClassDefIndexForArrays, 761 value); 762 } 763 764 void VisitDeoptimize(HDeoptimize* instruction) { 765 const ScopedArenaVector<HInstruction*>& heap_values = 766 heap_values_for_[instruction->GetBlock()->GetBlockId()]; 767 for (HInstruction* heap_value : heap_values) { 768 // A store is kept as the heap value for possibly removed stores. 769 // That value stored is generally observeable after deoptimization, except 770 // for singletons that don't escape after deoptimization. 771 if (IsStore(heap_value)) { 772 if (heap_value->IsStaticFieldSet()) { 773 KeepIfIsStore(heap_value); 774 continue; 775 } 776 HInstruction* reference = heap_value->InputAt(0); 777 if (heap_location_collector_.FindReferenceInfoOf(reference)->IsSingleton()) { 778 if (reference->IsNewInstance() && reference->AsNewInstance()->IsFinalizable()) { 779 // Finalizable objects alway escape. 780 KeepIfIsStore(heap_value); 781 continue; 782 } 783 // Check whether the reference for a store is used by an environment local of 784 // HDeoptimize. If not, the singleton is not observed after 785 // deoptimizion. 786 for (const HUseListNode<HEnvironment*>& use : reference->GetEnvUses()) { 787 HEnvironment* user = use.GetUser(); 788 if (user->GetHolder() == instruction) { 789 // The singleton for the store is visible at this deoptimization 790 // point. Need to keep the store so that the heap value is 791 // seen by the interpreter. 792 KeepIfIsStore(heap_value); 793 } 794 } 795 } else { 796 KeepIfIsStore(heap_value); 797 } 798 } 799 } 800 } 801 802 // Keep necessary stores before exiting a method via return/throw. 803 void HandleExit(HBasicBlock* block) { 804 const ScopedArenaVector<HInstruction*>& heap_values = 805 heap_values_for_[block->GetBlockId()]; 806 for (size_t i = 0; i < heap_values.size(); i++) { 807 HInstruction* heap_value = heap_values[i]; 808 ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo(); 809 if (!ref_info->IsSingletonAndRemovable()) { 810 KeepIfIsStore(heap_value); 811 } 812 } 813 } 814 815 void VisitReturn(HReturn* instruction) OVERRIDE { 816 HandleExit(instruction->GetBlock()); 817 } 818 819 void VisitReturnVoid(HReturnVoid* return_void) OVERRIDE { 820 HandleExit(return_void->GetBlock()); 821 } 822 823 void VisitThrow(HThrow* throw_instruction) OVERRIDE { 824 HandleExit(throw_instruction->GetBlock()); 825 } 826 827 void HandleInvoke(HInstruction* instruction) { 828 SideEffects side_effects = instruction->GetSideEffects(); 829 ScopedArenaVector<HInstruction*>& heap_values = 830 heap_values_for_[instruction->GetBlock()->GetBlockId()]; 831 for (size_t i = 0; i < heap_values.size(); i++) { 832 ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo(); 833 if (ref_info->IsSingleton()) { 834 // Singleton references cannot be seen by the callee. 835 } else { 836 if (side_effects.DoesAnyRead()) { 837 // Invocation may read the heap value. 838 KeepIfIsStore(heap_values[i]); 839 } 840 if (side_effects.DoesAnyWrite()) { 841 // Keep the store since it's not used to track the heap value anymore. 842 KeepIfIsStore(heap_values[i]); 843 heap_values[i] = kUnknownHeapValue; 844 } 845 } 846 } 847 } 848 849 void VisitInvoke(HInvoke* invoke) OVERRIDE { 850 HandleInvoke(invoke); 851 } 852 853 void VisitClinitCheck(HClinitCheck* clinit) OVERRIDE { 854 HandleInvoke(clinit); 855 } 856 857 void VisitUnresolvedInstanceFieldGet(HUnresolvedInstanceFieldGet* instruction) OVERRIDE { 858 // Conservatively treat it as an invocation. 859 HandleInvoke(instruction); 860 } 861 862 void VisitUnresolvedInstanceFieldSet(HUnresolvedInstanceFieldSet* instruction) OVERRIDE { 863 // Conservatively treat it as an invocation. 864 HandleInvoke(instruction); 865 } 866 867 void VisitUnresolvedStaticFieldGet(HUnresolvedStaticFieldGet* instruction) OVERRIDE { 868 // Conservatively treat it as an invocation. 869 HandleInvoke(instruction); 870 } 871 872 void VisitUnresolvedStaticFieldSet(HUnresolvedStaticFieldSet* instruction) OVERRIDE { 873 // Conservatively treat it as an invocation. 874 HandleInvoke(instruction); 875 } 876 877 void VisitNewInstance(HNewInstance* new_instance) OVERRIDE { 878 ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(new_instance); 879 if (ref_info == nullptr) { 880 // new_instance isn't used for field accesses. No need to process it. 881 return; 882 } 883 if (ref_info->IsSingletonAndRemovable() && !new_instance->NeedsChecks()) { 884 DCHECK(!new_instance->IsFinalizable()); 885 // new_instance can potentially be eliminated. 886 singleton_new_instances_.push_back(new_instance); 887 } 888 ScopedArenaVector<HInstruction*>& heap_values = 889 heap_values_for_[new_instance->GetBlock()->GetBlockId()]; 890 for (size_t i = 0; i < heap_values.size(); i++) { 891 HInstruction* ref = 892 heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo()->GetReference(); 893 size_t offset = heap_location_collector_.GetHeapLocation(i)->GetOffset(); 894 if (ref == new_instance && offset >= mirror::kObjectHeaderSize) { 895 // Instance fields except the header fields are set to default heap values. 896 heap_values[i] = kDefaultHeapValue; 897 } 898 } 899 } 900 901 void VisitNewArray(HNewArray* new_array) OVERRIDE { 902 ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(new_array); 903 if (ref_info == nullptr) { 904 // new_array isn't used for array accesses. No need to process it. 905 return; 906 } 907 if (ref_info->IsSingletonAndRemovable()) { 908 if (new_array->GetLength()->IsIntConstant() && 909 new_array->GetLength()->AsIntConstant()->GetValue() >= 0) { 910 // new_array can potentially be eliminated. 911 singleton_new_instances_.push_back(new_array); 912 } else { 913 // new_array may throw NegativeArraySizeException. Keep it. 914 } 915 } 916 ScopedArenaVector<HInstruction*>& heap_values = 917 heap_values_for_[new_array->GetBlock()->GetBlockId()]; 918 for (size_t i = 0; i < heap_values.size(); i++) { 919 HeapLocation* location = heap_location_collector_.GetHeapLocation(i); 920 HInstruction* ref = location->GetReferenceInfo()->GetReference(); 921 if (ref == new_array && location->GetIndex() != nullptr) { 922 // Array elements are set to default heap values. 923 heap_values[i] = kDefaultHeapValue; 924 } 925 } 926 } 927 928 const HeapLocationCollector& heap_location_collector_; 929 const SideEffectsAnalysis& side_effects_; 930 931 // Use local allocator for allocating memory. 932 ScopedArenaAllocator allocator_; 933 934 // One array of heap values for each block. 935 ScopedArenaVector<ScopedArenaVector<HInstruction*>> heap_values_for_; 936 937 // We record the instructions that should be eliminated but may be 938 // used by heap locations. They'll be removed in the end. 939 ScopedArenaVector<HInstruction*> removed_loads_; 940 ScopedArenaVector<HInstruction*> substitute_instructions_for_loads_; 941 942 // Stores in this list may be removed from the list later when it's 943 // found that the store cannot be eliminated. 944 ScopedArenaVector<HInstruction*> possibly_removed_stores_; 945 946 ScopedArenaVector<HInstruction*> singleton_new_instances_; 947 948 DISALLOW_COPY_AND_ASSIGN(LSEVisitor); 949 }; 950 951 void LoadStoreElimination::Run() { 952 if (graph_->IsDebuggable() || graph_->HasTryCatch()) { 953 // Debugger may set heap values or trigger deoptimization of callers. 954 // Try/catch support not implemented yet. 955 // Skip this optimization. 956 return; 957 } 958 const HeapLocationCollector& heap_location_collector = lsa_.GetHeapLocationCollector(); 959 if (heap_location_collector.GetNumberOfHeapLocations() == 0) { 960 // No HeapLocation information from LSA, skip this optimization. 961 return; 962 } 963 964 // TODO: analyze VecLoad/VecStore better. 965 if (graph_->HasSIMD()) { 966 return; 967 } 968 969 LSEVisitor lse_visitor(graph_, heap_location_collector, side_effects_, stats_); 970 for (HBasicBlock* block : graph_->GetReversePostOrder()) { 971 lse_visitor.VisitBasicBlock(block); 972 } 973 lse_visitor.RemoveInstructions(); 974 } 975 976 } // namespace art 977