/* * Copyright (C) 2015 The Android Open Source Project * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ #include "load_store_elimination.h" #include "base/array_ref.h" #include "base/scoped_arena_allocator.h" #include "base/scoped_arena_containers.h" #include "escape.h" #include "load_store_analysis.h" #include "side_effects_analysis.h" /** * The general algorithm of load-store elimination (LSE). * Load-store analysis in the previous pass collects a list of heap locations * and does alias analysis of those heap locations. * LSE keeps track of a list of heap values corresponding to the heap * locations. It visits basic blocks in reverse post order and for * each basic block, visits instructions sequentially, and processes * instructions as follows: * - If the instruction is a load, and the heap location for that load has a * valid heap value, the load can be eliminated. In order to maintain the * validity of all heap locations during the optimization phase, the real * elimination is delayed till the end of LSE. * - If the instruction is a store, it updates the heap value for the heap * location of the store with the store instruction. The real heap value * can be fetched from the store instruction. Heap values are invalidated * for heap locations that may alias with the store instruction's heap * location. The store instruction can be eliminated unless the value stored * is later needed e.g. by a load from the same/aliased heap location or * the heap location persists at method return/deoptimization. * The store instruction is also needed if it's not used to track the heap * value anymore, e.g. when it fails to merge with the heap values from other * predecessors. * - A store that stores the same value as the heap value is eliminated. * - The list of heap values are merged at basic block entry from the basic * block's predecessors. The algorithm is single-pass, so loop side-effects is * used as best effort to decide if a heap location is stored inside the loop. * - A special type of objects called singletons are instantiated in the method * and have a single name, i.e. no aliases. Singletons have exclusive heap * locations since they have no aliases. Singletons are helpful in narrowing * down the life span of a heap location such that they do not always * need to participate in merging heap values. Allocation of a singleton * can be eliminated if that singleton is not used and does not persist * at method return/deoptimization. * - For newly instantiated instances, their heap values are initialized to * language defined default values. * - Some instructions such as invokes are treated as loading and invalidating * all the heap values, depending on the instruction's side effects. * - Finalizable objects are considered as persisting at method * return/deoptimization. * - SIMD graphs (with VecLoad and VecStore instructions) are also handled. Any * partial overlap access among ArrayGet/ArraySet/VecLoad/Store is seen as * alias and no load/store is eliminated in such case. * - Currently this LSE algorithm doesn't handle graph with try-catch, due to * the special block merging structure. */ namespace art { // An unknown heap value. Loads with such a value in the heap location cannot be eliminated. // A heap location can be set to kUnknownHeapValue when: // - initially set a value. // - killed due to aliasing, merging, invocation, or loop side effects. static HInstruction* const kUnknownHeapValue = reinterpret_cast(static_cast(-1)); // Default heap value after an allocation. // A heap location can be set to that value right after an allocation. static HInstruction* const kDefaultHeapValue = reinterpret_cast(static_cast(-2)); // Use HGraphDelegateVisitor for which all VisitInvokeXXX() delegate to VisitInvoke(). class LSEVisitor : public HGraphDelegateVisitor { public: LSEVisitor(HGraph* graph, const HeapLocationCollector& heap_locations_collector, const SideEffectsAnalysis& side_effects, OptimizingCompilerStats* stats) : HGraphDelegateVisitor(graph, stats), heap_location_collector_(heap_locations_collector), side_effects_(side_effects), allocator_(graph->GetArenaStack()), heap_values_for_(graph->GetBlocks().size(), ScopedArenaVector(heap_locations_collector. GetNumberOfHeapLocations(), kUnknownHeapValue, allocator_.Adapter(kArenaAllocLSE)), allocator_.Adapter(kArenaAllocLSE)), removed_loads_(allocator_.Adapter(kArenaAllocLSE)), substitute_instructions_for_loads_(allocator_.Adapter(kArenaAllocLSE)), possibly_removed_stores_(allocator_.Adapter(kArenaAllocLSE)), singleton_new_instances_(allocator_.Adapter(kArenaAllocLSE)) { } void VisitBasicBlock(HBasicBlock* block) override { // Populate the heap_values array for this block. // TODO: try to reuse the heap_values array from one predecessor if possible. if (block->IsLoopHeader()) { HandleLoopSideEffects(block); } else { MergePredecessorValues(block); } HGraphVisitor::VisitBasicBlock(block); } HTypeConversion* AddTypeConversionIfNecessary(HInstruction* instruction, HInstruction* value, DataType::Type expected_type) { HTypeConversion* type_conversion = nullptr; // Should never add type conversion into boolean value. if (expected_type != DataType::Type::kBool && !DataType::IsTypeConversionImplicit(value->GetType(), expected_type)) { type_conversion = new (GetGraph()->GetAllocator()) HTypeConversion( expected_type, value, instruction->GetDexPc()); instruction->GetBlock()->InsertInstructionBefore(type_conversion, instruction); } return type_conversion; } // Find an instruction's substitute if it's a removed load. // Return the same instruction if it should not be removed. HInstruction* FindSubstitute(HInstruction* instruction) { if (!IsLoad(instruction)) { return instruction; } size_t size = removed_loads_.size(); for (size_t i = 0; i < size; i++) { if (removed_loads_[i] == instruction) { HInstruction* substitute = substitute_instructions_for_loads_[i]; // The substitute list is a flat hierarchy. DCHECK_EQ(FindSubstitute(substitute), substitute); return substitute; } } return instruction; } void AddRemovedLoad(HInstruction* load, HInstruction* heap_value) { DCHECK(IsLoad(load)); DCHECK_EQ(FindSubstitute(heap_value), heap_value) << "Unexpected heap_value that has a substitute " << heap_value->DebugName(); removed_loads_.push_back(load); substitute_instructions_for_loads_.push_back(heap_value); } // Scan the list of removed loads to see if we can reuse `type_conversion`, if // the other removed load has the same substitute and type and is dominated // by `type_conversion`. void TryToReuseTypeConversion(HInstruction* type_conversion, size_t index) { size_t size = removed_loads_.size(); HInstruction* load = removed_loads_[index]; HInstruction* substitute = substitute_instructions_for_loads_[index]; for (size_t j = index + 1; j < size; j++) { HInstruction* load2 = removed_loads_[j]; HInstruction* substitute2 = substitute_instructions_for_loads_[j]; if (load2 == nullptr) { DCHECK(substitute2->IsTypeConversion()); continue; } DCHECK(IsLoad(load2)); DCHECK(substitute2 != nullptr); if (substitute2 == substitute && load2->GetType() == load->GetType() && type_conversion->GetBlock()->Dominates(load2->GetBlock()) && // Don't share across irreducible loop headers. // TODO: can be more fine-grained than this by testing each dominator. (load2->GetBlock() == type_conversion->GetBlock() || !GetGraph()->HasIrreducibleLoops())) { // The removed_loads_ are added in reverse post order. DCHECK(type_conversion->StrictlyDominates(load2)); load2->ReplaceWith(type_conversion); load2->GetBlock()->RemoveInstruction(load2); removed_loads_[j] = nullptr; substitute_instructions_for_loads_[j] = type_conversion; } } } // Remove recorded instructions that should be eliminated. void RemoveInstructions() { size_t size = removed_loads_.size(); DCHECK_EQ(size, substitute_instructions_for_loads_.size()); for (size_t i = 0; i < size; i++) { HInstruction* load = removed_loads_[i]; if (load == nullptr) { // The load has been handled in the scan for type conversion below. DCHECK(substitute_instructions_for_loads_[i]->IsTypeConversion()); continue; } DCHECK(IsLoad(load)); HInstruction* substitute = substitute_instructions_for_loads_[i]; DCHECK(substitute != nullptr); // We proactively retrieve the substitute for a removed load, so // a load that has a substitute should not be observed as a heap // location value. DCHECK_EQ(FindSubstitute(substitute), substitute); // The load expects to load the heap value as type load->GetType(). // However the tracked heap value may not be of that type. An explicit // type conversion may be needed. // There are actually three types involved here: // (1) tracked heap value's type (type A) // (2) heap location (field or element)'s type (type B) // (3) load's type (type C) // We guarantee that type A stored as type B and then fetched out as // type C is the same as casting from type A to type C directly, since // type B and type C will have the same size which is guarenteed in // HInstanceFieldGet/HStaticFieldGet/HArrayGet/HVecLoad's SetType(). // So we only need one type conversion from type A to type C. HTypeConversion* type_conversion = AddTypeConversionIfNecessary( load, substitute, load->GetType()); if (type_conversion != nullptr) { TryToReuseTypeConversion(type_conversion, i); load->ReplaceWith(type_conversion); substitute_instructions_for_loads_[i] = type_conversion; } else { load->ReplaceWith(substitute); } load->GetBlock()->RemoveInstruction(load); } // At this point, stores in possibly_removed_stores_ can be safely removed. for (HInstruction* store : possibly_removed_stores_) { DCHECK(IsStore(store)); store->GetBlock()->RemoveInstruction(store); } // Eliminate singleton-classified instructions: // * - Constructor fences (they never escape this thread). // * - Allocations (if they are unused). for (HInstruction* new_instance : singleton_new_instances_) { size_t removed = HConstructorFence::RemoveConstructorFences(new_instance); MaybeRecordStat(stats_, MethodCompilationStat::kConstructorFenceRemovedLSE, removed); if (!new_instance->HasNonEnvironmentUses()) { new_instance->RemoveEnvironmentUsers(); new_instance->GetBlock()->RemoveInstruction(new_instance); } } } private: static bool IsLoad(const HInstruction* instruction) { if (instruction == kUnknownHeapValue || instruction == kDefaultHeapValue) { return false; } // Unresolved load is not treated as a load. return instruction->IsInstanceFieldGet() || instruction->IsStaticFieldGet() || instruction->IsVecLoad() || instruction->IsArrayGet(); } static bool IsStore(const HInstruction* instruction) { if (instruction == kUnknownHeapValue || instruction == kDefaultHeapValue) { return false; } // Unresolved store is not treated as a store. return instruction->IsInstanceFieldSet() || instruction->IsArraySet() || instruction->IsVecStore() || instruction->IsStaticFieldSet(); } // Check if it is allowed to use default values for the specified load. static bool IsDefaultAllowedForLoad(const HInstruction* load) { DCHECK(IsLoad(load)); // Using defaults for VecLoads requires to create additional vector operations. // As there are some issues with scheduling vector operations it is better to avoid creating // them. return !load->IsVecOperation(); } // Returns the real heap value by finding its substitute or by "peeling" // a store instruction. HInstruction* GetRealHeapValue(HInstruction* heap_value) { if (IsLoad(heap_value)) { return FindSubstitute(heap_value); } if (!IsStore(heap_value)) { return heap_value; } // We keep track of store instructions as the heap values which might be // eliminated if the stores are later found not necessary. The real stored // value needs to be fetched from the store instruction. if (heap_value->IsInstanceFieldSet()) { heap_value = heap_value->AsInstanceFieldSet()->GetValue(); } else if (heap_value->IsStaticFieldSet()) { heap_value = heap_value->AsStaticFieldSet()->GetValue(); } else if (heap_value->IsVecStore()) { heap_value = heap_value->AsVecStore()->GetValue(); } else { DCHECK(heap_value->IsArraySet()); heap_value = heap_value->AsArraySet()->GetValue(); } // heap_value may already be a removed load. return FindSubstitute(heap_value); } // If heap_value is a store, need to keep the store. // This is necessary if a heap value is killed or replaced by another value, // so that the store is no longer used to track heap value. void KeepIfIsStore(HInstruction* heap_value) { if (!IsStore(heap_value)) { return; } auto idx = std::find(possibly_removed_stores_.begin(), possibly_removed_stores_.end(), heap_value); if (idx != possibly_removed_stores_.end()) { // Make sure the store is kept. possibly_removed_stores_.erase(idx); } } // If a heap location X may alias with heap location at `loc_index` // and heap_values of that heap location X holds a store, keep that store. // It's needed for a dependent load that's not eliminated since any store // that may put value into the load's heap location needs to be kept. void KeepStoresIfAliasedToLocation(ScopedArenaVector& heap_values, size_t loc_index) { for (size_t i = 0; i < heap_values.size(); i++) { if ((i == loc_index) || heap_location_collector_.MayAlias(i, loc_index)) { KeepIfIsStore(heap_values[i]); } } } void HandleLoopSideEffects(HBasicBlock* block) { DCHECK(block->IsLoopHeader()); int block_id = block->GetBlockId(); ScopedArenaVector& heap_values = heap_values_for_[block_id]; HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader(); ScopedArenaVector& pre_header_heap_values = heap_values_for_[pre_header->GetBlockId()]; // Don't eliminate loads in irreducible loops. // Also keep the stores before the loop. if (block->GetLoopInformation()->IsIrreducible()) { if (kIsDebugBuild) { for (size_t i = 0; i < heap_values.size(); i++) { DCHECK_EQ(heap_values[i], kUnknownHeapValue); } } for (size_t i = 0; i < heap_values.size(); i++) { KeepIfIsStore(pre_header_heap_values[i]); } return; } // Inherit the values from pre-header. for (size_t i = 0; i < heap_values.size(); i++) { heap_values[i] = pre_header_heap_values[i]; } // We do a single pass in reverse post order. For loops, use the side effects as a hint // to see if the heap values should be killed. if (side_effects_.GetLoopEffects(block).DoesAnyWrite()) { for (size_t i = 0; i < heap_values.size(); i++) { HeapLocation* location = heap_location_collector_.GetHeapLocation(i); ReferenceInfo* ref_info = location->GetReferenceInfo(); if (ref_info->IsSingleton() && !location->IsValueKilledByLoopSideEffects()) { // A singleton's field that's not stored into inside a loop is // invariant throughout the loop. Nothing to do. } else { // heap value is killed by loop side effects. KeepIfIsStore(pre_header_heap_values[i]); heap_values[i] = kUnknownHeapValue; } } } else { // The loop doesn't kill any value. } } void MergePredecessorValues(HBasicBlock* block) { ArrayRef predecessors(block->GetPredecessors()); if (predecessors.size() == 0) { return; } if (block->IsExitBlock()) { // Exit block doesn't really merge values since the control flow ends in // its predecessors. Each predecessor needs to make sure stores are kept // if necessary. return; } ScopedArenaVector& heap_values = heap_values_for_[block->GetBlockId()]; for (size_t i = 0; i < heap_values.size(); i++) { HInstruction* merged_value = nullptr; // If we can merge the store itself from the predecessors, we keep // the store as the heap value as long as possible. In case we cannot // merge the store, we try to merge the values of the stores. HInstruction* merged_store_value = nullptr; // Whether merged_value is a result that's merged from all predecessors. bool from_all_predecessors = true; ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo(); HInstruction* ref = ref_info->GetReference(); HInstruction* singleton_ref = nullptr; if (ref_info->IsSingleton()) { // We do more analysis based on singleton's liveness when merging // heap values for such cases. singleton_ref = ref; } for (HBasicBlock* predecessor : predecessors) { HInstruction* pred_value = heap_values_for_[predecessor->GetBlockId()][i]; if (!IsStore(pred_value)) { pred_value = FindSubstitute(pred_value); } DCHECK(pred_value != nullptr); HInstruction* pred_store_value = GetRealHeapValue(pred_value); if ((singleton_ref != nullptr) && !singleton_ref->GetBlock()->Dominates(predecessor)) { // singleton_ref is not live in this predecessor. No need to merge // since singleton_ref is not live at the beginning of this block. DCHECK_EQ(pred_value, kUnknownHeapValue); from_all_predecessors = false; break; } if (merged_value == nullptr) { // First seen heap value. DCHECK(pred_value != nullptr); merged_value = pred_value; } else if (pred_value != merged_value) { // There are conflicting values. merged_value = kUnknownHeapValue; // We may still be able to merge store values. } // Conflicting stores may be storing the same value. We do another merge // of real stored values. if (merged_store_value == nullptr) { // First seen store value. DCHECK(pred_store_value != nullptr); merged_store_value = pred_store_value; } else if (pred_store_value != merged_store_value) { // There are conflicting store values. merged_store_value = kUnknownHeapValue; // There must be conflicting stores also. DCHECK_EQ(merged_value, kUnknownHeapValue); // No need to merge anymore. break; } } if (merged_value == nullptr) { DCHECK(!from_all_predecessors); DCHECK(singleton_ref != nullptr); } if (from_all_predecessors) { if (ref_info->IsSingletonAndRemovable() && (block->IsSingleReturnOrReturnVoidAllowingPhis() || (block->EndsWithReturn() && (merged_value != kUnknownHeapValue || merged_store_value != kUnknownHeapValue)))) { // Values in the singleton are not needed anymore: // (1) if this block consists of a sole return, or // (2) if this block returns and a usable merged value is obtained // (loads prior to the return will always use that value). } else if (!IsStore(merged_value)) { // We don't track merged value as a store anymore. We have to // hold the stores in predecessors live here. for (HBasicBlock* predecessor : predecessors) { ScopedArenaVector& pred_values = heap_values_for_[predecessor->GetBlockId()]; KeepIfIsStore(pred_values[i]); } } } else { DCHECK(singleton_ref != nullptr); // singleton_ref is non-existing at the beginning of the block. There is // no need to keep the stores. } if (!from_all_predecessors) { DCHECK(singleton_ref != nullptr); DCHECK((singleton_ref->GetBlock() == block) || !singleton_ref->GetBlock()->Dominates(block)) << "method: " << GetGraph()->GetMethodName(); // singleton_ref is not defined before block or defined only in some of its // predecessors, so block doesn't really have the location at its entry. heap_values[i] = kUnknownHeapValue; } else if (predecessors.size() == 1) { // Inherit heap value from the single predecessor. DCHECK_EQ(heap_values_for_[predecessors[0]->GetBlockId()][i], merged_value); heap_values[i] = merged_value; } else { DCHECK(merged_value == kUnknownHeapValue || merged_value == kDefaultHeapValue || merged_value->GetBlock()->Dominates(block)); if (merged_value != kUnknownHeapValue) { heap_values[i] = merged_value; } else { // Stores in different predecessors may be storing the same value. heap_values[i] = merged_store_value; } } } } // `instruction` is being removed. Try to see if the null check on it // can be removed. This can happen if the same value is set in two branches // but not in dominators. Such as: // int[] a = foo(); // if () { // a[0] = 2; // } else { // a[0] = 2; // } // // a[0] can now be replaced with constant 2, and the null check on it can be removed. void TryRemovingNullCheck(HInstruction* instruction) { HInstruction* prev = instruction->GetPrevious(); if ((prev != nullptr) && prev->IsNullCheck() && (prev == instruction->InputAt(0))) { // Previous instruction is a null check for this instruction. Remove the null check. prev->ReplaceWith(prev->InputAt(0)); prev->GetBlock()->RemoveInstruction(prev); } } HInstruction* GetDefaultValue(DataType::Type type) { switch (type) { case DataType::Type::kReference: return GetGraph()->GetNullConstant(); case DataType::Type::kBool: case DataType::Type::kUint8: case DataType::Type::kInt8: case DataType::Type::kUint16: case DataType::Type::kInt16: case DataType::Type::kInt32: return GetGraph()->GetIntConstant(0); case DataType::Type::kInt64: return GetGraph()->GetLongConstant(0); case DataType::Type::kFloat32: return GetGraph()->GetFloatConstant(0); case DataType::Type::kFloat64: return GetGraph()->GetDoubleConstant(0); default: UNREACHABLE(); } } void VisitGetLocation(HInstruction* instruction, size_t idx) { DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); ScopedArenaVector& heap_values = heap_values_for_[instruction->GetBlock()->GetBlockId()]; HInstruction* heap_value = heap_values[idx]; if (heap_value == kDefaultHeapValue) { if (IsDefaultAllowedForLoad(instruction)) { HInstruction* constant = GetDefaultValue(instruction->GetType()); AddRemovedLoad(instruction, constant); heap_values[idx] = constant; return; } else { heap_values[idx] = kUnknownHeapValue; heap_value = kUnknownHeapValue; } } heap_value = GetRealHeapValue(heap_value); if (heap_value == kUnknownHeapValue) { // Load isn't eliminated. Put the load as the value into the HeapLocation. // This acts like GVN but with better aliasing analysis. heap_values[idx] = instruction; KeepStoresIfAliasedToLocation(heap_values, idx); } else { // Load is eliminated. AddRemovedLoad(instruction, heap_value); TryRemovingNullCheck(instruction); } } bool Equal(HInstruction* heap_value, HInstruction* value) { DCHECK(!IsStore(value)) << value->DebugName(); if (heap_value == kUnknownHeapValue) { // Don't compare kUnknownHeapValue with other values. return false; } if (heap_value == value) { return true; } if (heap_value == kDefaultHeapValue && GetDefaultValue(value->GetType()) == value) { return true; } HInstruction* real_heap_value = GetRealHeapValue(heap_value); if (real_heap_value != heap_value) { return Equal(real_heap_value, value); } return false; } bool CanValueBeKeptIfSameAsNew(HInstruction* value, HInstruction* new_value, HInstruction* new_value_set_instr) { // For field/array set location operations, if the value is the same as the new_value // it can be kept even if aliasing happens. All aliased operations will access the same memory // range. // For vector values, this is not true. For example: // packed_data = [0xA, 0xB, 0xC, 0xD]; <-- Different values in each lane. // VecStore array[i ,i+1,i+2,i+3] = packed_data; // VecStore array[i+1,i+2,i+3,i+4] = packed_data; <-- We are here (partial overlap). // VecLoad vx = array[i,i+1,i+2,i+3]; <-- Cannot be eliminated because the value // here is not packed_data anymore. // // TODO: to allow such 'same value' optimization on vector data, // LSA needs to report more fine-grain MAY alias information: // (1) May alias due to two vector data partial overlap. // e.g. a[i..i+3] and a[i+1,..,i+4]. // (2) May alias due to two vector data may complete overlap each other. // e.g. a[i..i+3] and b[i..i+3]. // (3) May alias but the exact relationship between two locations is unknown. // e.g. a[i..i+3] and b[j..j+3], where values of a,b,i,j are all unknown. // This 'same value' optimization can apply only on case (2). if (new_value_set_instr->IsVecOperation()) { return false; } return Equal(value, new_value); } void VisitSetLocation(HInstruction* instruction, size_t idx, HInstruction* value) { DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); DCHECK(!IsStore(value)) << value->DebugName(); // value may already have a substitute. value = FindSubstitute(value); ScopedArenaVector& heap_values = heap_values_for_[instruction->GetBlock()->GetBlockId()]; HInstruction* heap_value = heap_values[idx]; bool possibly_redundant = false; if (Equal(heap_value, value)) { // Store into the heap location with the same value. // This store can be eliminated right away. instruction->GetBlock()->RemoveInstruction(instruction); return; } else { HLoopInformation* loop_info = instruction->GetBlock()->GetLoopInformation(); if (loop_info == nullptr) { // Store is not in a loop. We try to precisely track the heap value by // the store. possibly_redundant = true; } else if (!loop_info->IsIrreducible()) { // instruction is a store in the loop so the loop must do write. DCHECK(side_effects_.GetLoopEffects(loop_info->GetHeader()).DoesAnyWrite()); ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(idx)->GetReferenceInfo(); if (ref_info->IsSingleton() && !loop_info->IsDefinedOutOfTheLoop(ref_info->GetReference())) { // original_ref is created inside the loop. Value stored to it isn't needed at // the loop header. This is true for outer loops also. possibly_redundant = true; } else { // Keep the store since its value may be needed at the loop header. } } else { // Keep the store inside irreducible loops. } } if (possibly_redundant) { possibly_removed_stores_.push_back(instruction); } // Put the store as the heap value. If the value is loaded or needed after // return/deoptimization later, this store isn't really redundant. heap_values[idx] = instruction; // This store may kill values in other heap locations due to aliasing. for (size_t i = 0; i < heap_values.size(); i++) { if (i == idx || heap_values[i] == kUnknownHeapValue || CanValueBeKeptIfSameAsNew(heap_values[i], value, instruction) || !heap_location_collector_.MayAlias(i, idx)) { continue; } // Kill heap locations that may alias and as a result if the heap value // is a store, the store needs to be kept. KeepIfIsStore(heap_values[i]); heap_values[i] = kUnknownHeapValue; } } void VisitInstanceFieldGet(HInstanceFieldGet* instruction) override { HInstruction* object = instruction->InputAt(0); const FieldInfo& field = instruction->GetFieldInfo(); VisitGetLocation(instruction, heap_location_collector_.GetFieldHeapLocation(object, &field)); } void VisitInstanceFieldSet(HInstanceFieldSet* instruction) override { HInstruction* object = instruction->InputAt(0); const FieldInfo& field = instruction->GetFieldInfo(); HInstruction* value = instruction->InputAt(1); size_t idx = heap_location_collector_.GetFieldHeapLocation(object, &field); VisitSetLocation(instruction, idx, value); } void VisitStaticFieldGet(HStaticFieldGet* instruction) override { HInstruction* cls = instruction->InputAt(0); const FieldInfo& field = instruction->GetFieldInfo(); VisitGetLocation(instruction, heap_location_collector_.GetFieldHeapLocation(cls, &field)); } void VisitStaticFieldSet(HStaticFieldSet* instruction) override { HInstruction* cls = instruction->InputAt(0); const FieldInfo& field = instruction->GetFieldInfo(); size_t idx = heap_location_collector_.GetFieldHeapLocation(cls, &field); VisitSetLocation(instruction, idx, instruction->InputAt(1)); } void VisitArrayGet(HArrayGet* instruction) override { VisitGetLocation(instruction, heap_location_collector_.GetArrayHeapLocation(instruction)); } void VisitArraySet(HArraySet* instruction) override { size_t idx = heap_location_collector_.GetArrayHeapLocation(instruction); VisitSetLocation(instruction, idx, instruction->GetValue()); } void VisitVecLoad(HVecLoad* instruction) override { VisitGetLocation(instruction, heap_location_collector_.GetArrayHeapLocation(instruction)); } void VisitVecStore(HVecStore* instruction) override { size_t idx = heap_location_collector_.GetArrayHeapLocation(instruction); VisitSetLocation(instruction, idx, instruction->GetValue()); } void VisitDeoptimize(HDeoptimize* instruction) override { const ScopedArenaVector& heap_values = heap_values_for_[instruction->GetBlock()->GetBlockId()]; for (HInstruction* heap_value : heap_values) { // A store is kept as the heap value for possibly removed stores. // That value stored is generally observeable after deoptimization, except // for singletons that don't escape after deoptimization. if (IsStore(heap_value)) { if (heap_value->IsStaticFieldSet()) { KeepIfIsStore(heap_value); continue; } HInstruction* reference = heap_value->InputAt(0); if (heap_location_collector_.FindReferenceInfoOf(reference)->IsSingleton()) { if (reference->IsNewInstance() && reference->AsNewInstance()->IsFinalizable()) { // Finalizable objects alway escape. KeepIfIsStore(heap_value); continue; } // Check whether the reference for a store is used by an environment local of // HDeoptimize. If not, the singleton is not observed after // deoptimizion. for (const HUseListNode& use : reference->GetEnvUses()) { HEnvironment* user = use.GetUser(); if (user->GetHolder() == instruction) { // The singleton for the store is visible at this deoptimization // point. Need to keep the store so that the heap value is // seen by the interpreter. KeepIfIsStore(heap_value); } } } else { KeepIfIsStore(heap_value); } } } } // Keep necessary stores before exiting a method via return/throw. void HandleExit(HBasicBlock* block) { const ScopedArenaVector& heap_values = heap_values_for_[block->GetBlockId()]; for (size_t i = 0; i < heap_values.size(); i++) { HInstruction* heap_value = heap_values[i]; ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo(); if (!ref_info->IsSingletonAndRemovable()) { KeepIfIsStore(heap_value); } } } void VisitReturn(HReturn* instruction) override { HandleExit(instruction->GetBlock()); } void VisitReturnVoid(HReturnVoid* return_void) override { HandleExit(return_void->GetBlock()); } void VisitThrow(HThrow* throw_instruction) override { HandleExit(throw_instruction->GetBlock()); } void HandleInvoke(HInstruction* instruction) { SideEffects side_effects = instruction->GetSideEffects(); ScopedArenaVector& heap_values = heap_values_for_[instruction->GetBlock()->GetBlockId()]; for (size_t i = 0; i < heap_values.size(); i++) { ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo(); if (ref_info->IsSingleton()) { // Singleton references cannot be seen by the callee. } else { if (side_effects.DoesAnyRead()) { // Invocation may read the heap value. KeepIfIsStore(heap_values[i]); } if (side_effects.DoesAnyWrite()) { // Keep the store since it's not used to track the heap value anymore. KeepIfIsStore(heap_values[i]); heap_values[i] = kUnknownHeapValue; } } } } void VisitInvoke(HInvoke* invoke) override { HandleInvoke(invoke); } void VisitClinitCheck(HClinitCheck* clinit) override { HandleInvoke(clinit); } void VisitUnresolvedInstanceFieldGet(HUnresolvedInstanceFieldGet* instruction) override { // Conservatively treat it as an invocation. HandleInvoke(instruction); } void VisitUnresolvedInstanceFieldSet(HUnresolvedInstanceFieldSet* instruction) override { // Conservatively treat it as an invocation. HandleInvoke(instruction); } void VisitUnresolvedStaticFieldGet(HUnresolvedStaticFieldGet* instruction) override { // Conservatively treat it as an invocation. HandleInvoke(instruction); } void VisitUnresolvedStaticFieldSet(HUnresolvedStaticFieldSet* instruction) override { // Conservatively treat it as an invocation. HandleInvoke(instruction); } void VisitNewInstance(HNewInstance* new_instance) override { ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(new_instance); if (ref_info == nullptr) { // new_instance isn't used for field accesses. No need to process it. return; } if (ref_info->IsSingletonAndRemovable() && !new_instance->NeedsChecks()) { DCHECK(!new_instance->IsFinalizable()); // new_instance can potentially be eliminated. singleton_new_instances_.push_back(new_instance); } ScopedArenaVector& heap_values = heap_values_for_[new_instance->GetBlock()->GetBlockId()]; for (size_t i = 0; i < heap_values.size(); i++) { HInstruction* ref = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo()->GetReference(); size_t offset = heap_location_collector_.GetHeapLocation(i)->GetOffset(); if (ref == new_instance && offset >= mirror::kObjectHeaderSize) { // Instance fields except the header fields are set to default heap values. heap_values[i] = kDefaultHeapValue; } } } void VisitNewArray(HNewArray* new_array) override { ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(new_array); if (ref_info == nullptr) { // new_array isn't used for array accesses. No need to process it. return; } if (ref_info->IsSingletonAndRemovable()) { if (new_array->GetLength()->IsIntConstant() && new_array->GetLength()->AsIntConstant()->GetValue() >= 0) { // new_array can potentially be eliminated. singleton_new_instances_.push_back(new_array); } else { // new_array may throw NegativeArraySizeException. Keep it. } } ScopedArenaVector& heap_values = heap_values_for_[new_array->GetBlock()->GetBlockId()]; for (size_t i = 0; i < heap_values.size(); i++) { HeapLocation* location = heap_location_collector_.GetHeapLocation(i); HInstruction* ref = location->GetReferenceInfo()->GetReference(); if (ref == new_array && location->GetIndex() != nullptr) { // Array elements are set to default heap values. heap_values[i] = kDefaultHeapValue; } } } const HeapLocationCollector& heap_location_collector_; const SideEffectsAnalysis& side_effects_; // Use local allocator for allocating memory. ScopedArenaAllocator allocator_; // One array of heap values for each block. ScopedArenaVector> heap_values_for_; // We record the instructions that should be eliminated but may be // used by heap locations. They'll be removed in the end. ScopedArenaVector removed_loads_; ScopedArenaVector substitute_instructions_for_loads_; // Stores in this list may be removed from the list later when it's // found that the store cannot be eliminated. ScopedArenaVector possibly_removed_stores_; ScopedArenaVector singleton_new_instances_; DISALLOW_COPY_AND_ASSIGN(LSEVisitor); }; bool LoadStoreElimination::Run() { if (graph_->IsDebuggable() || graph_->HasTryCatch()) { // Debugger may set heap values or trigger deoptimization of callers. // Try/catch support not implemented yet. // Skip this optimization. return false; } const HeapLocationCollector& heap_location_collector = lsa_.GetHeapLocationCollector(); if (heap_location_collector.GetNumberOfHeapLocations() == 0) { // No HeapLocation information from LSA, skip this optimization. return false; } LSEVisitor lse_visitor(graph_, heap_location_collector, side_effects_, stats_); for (HBasicBlock* block : graph_->GetReversePostOrder()) { lse_visitor.VisitBasicBlock(block); } lse_visitor.RemoveInstructions(); return true; } } // namespace art