load_store_elimination.cc revision 803cbb9c9319af10b01317abb849303fb8329fb7
18df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang/* 28df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * Copyright (C) 2015 The Android Open Source Project 38df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * 48df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * Licensed under the Apache License, Version 2.0 (the "License"); 58df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * you may not use this file except in compliance with the License. 68df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * You may obtain a copy of the License at 78df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * 88df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * http://www.apache.org/licenses/LICENSE-2.0 98df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * 108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * Unless required by applicable law or agreed to in writing, software 118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * distributed under the License is distributed on an "AS IS" BASIS, 128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * See the License for the specific language governing permissions and 148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * limitations under the License. 158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang */ 168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang#include "load_store_elimination.h" 188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang#include "side_effects_analysis.h" 198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang#include <iostream> 218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangnamespace art { 238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangclass ReferenceInfo; 258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// A cap for the number of heap locations to prevent pathological time/space consumption. 278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// The number of heap locations for most of the methods stays below this threshold. 288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangconstexpr size_t kMaxNumberOfHeapLocations = 32; 298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// A ReferenceInfo contains additional info about a reference such as 318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// whether it's a singleton, returned, etc. 328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangclass ReferenceInfo : public ArenaObject<kArenaAllocMisc> { 338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang public: 348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo(HInstruction* reference, size_t pos) : reference_(reference), position_(pos) { 358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_ = true; 368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_and_not_returned_ = true; 378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (!reference_->IsNewInstance() && !reference_->IsNewArray()) { 388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // For references not allocated in the method, don't assume anything. 398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_ = false; 408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_and_not_returned_ = false; 418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Visit all uses to determine if this reference can spread into the heap, 458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // a method call, etc. 468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (HUseIterator<HInstruction*> use_it(reference_->GetUses()); 478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang !use_it.Done(); 488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang use_it.Advance()) { 498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* use = use_it.Current()->GetUser(); 508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(!use->IsNullCheck()) << "NullCheck should have been eliminated"; 518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (use->IsBoundType()) { 528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // BoundType shouldn't normally be necessary for a NewInstance. 538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Just be conservative for the uncommon cases. 548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_ = false; 558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_and_not_returned_ = false; 568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (use->IsPhi() || use->IsInvoke() || 598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang (use->IsInstanceFieldSet() && (reference_ == use->InputAt(1))) || 608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang (use->IsUnresolvedInstanceFieldSet() && (reference_ == use->InputAt(1))) || 618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang (use->IsStaticFieldSet() && (reference_ == use->InputAt(1))) || 62d930929be93798d790c91dd05adf2c038508f1b0Nicolas Geoffray (use->IsUnresolvedStaticFieldSet() && (reference_ == use->InputAt(0))) || 638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang (use->IsArraySet() && (reference_ == use->InputAt(2)))) { 648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // reference_ is merged to a phi, passed to a callee, or stored to heap. 658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // reference_ isn't the only name that can refer to its value anymore. 668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_ = false; 678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_and_not_returned_ = false; 688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (use->IsReturn()) { 718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_and_not_returned_ = false; 728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* GetReference() const { 778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return reference_; 788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t GetPosition() const { 818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return position_; 828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns true if reference_ is the only name that can refer to its value during 858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // the lifetime of the method. So it's guaranteed to not have any alias in 868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // the method (including its callees). 878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool IsSingleton() const { 888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return is_singleton_; 898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns true if reference_ is a singleton and not returned to the caller. 928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // The allocation and stores into reference_ may be eliminated for such cases. 938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool IsSingletonAndNotReturned() const { 948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return is_singleton_and_not_returned_; 958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang private: 988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* const reference_; 998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const size_t position_; // position in HeapLocationCollector's ref_info_array_. 1008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool is_singleton_; // can only be referred to by a single name in the method. 1018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool is_singleton_and_not_returned_; // reference_ is singleton and not returned to caller. 1028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DISALLOW_COPY_AND_ASSIGN(ReferenceInfo); 1048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang}; 1058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// A heap location is a reference-offset/index pair that a value can be loaded from 1078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// or stored to. 1088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangclass HeapLocation : public ArenaObject<kArenaAllocMisc> { 1098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang public: 1108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang static constexpr size_t kInvalidFieldOffset = -1; 1118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // TODO: more fine-grained array types. 1138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang static constexpr int16_t kDeclaringClassDefIndexForArrays = -1; 1148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation(ReferenceInfo* ref_info, 1168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset, 1178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index, 1188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index) 1198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang : ref_info_(ref_info), 1208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang offset_(offset), 1218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang index_(index), 122803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang declaring_class_def_index_(declaring_class_def_index), 123803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang value_killed_by_loop_side_effects_(true) { 1248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(ref_info != nullptr); 1258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK((offset == kInvalidFieldOffset && index != nullptr) || 1268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang (offset != kInvalidFieldOffset && index == nullptr)); 127803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang if (ref_info->IsSingleton() && !IsArrayElement()) { 128803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // Assume this location's value cannot be killed by loop side effects 129803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // until proven otherwise. 130803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang value_killed_by_loop_side_effects_ = false; 131803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang } 1328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* GetReferenceInfo() const { return ref_info_; } 1358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t GetOffset() const { return offset_; } 1368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* GetIndex() const { return index_; } 1378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns the definition of declaring class' dex index. 1398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // It's kDeclaringClassDefIndexForArrays for an array element. 1408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t GetDeclaringClassDefIndex() const { 1418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return declaring_class_def_index_; 1428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool IsArrayElement() const { 1458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return index_ != nullptr; 1468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 148803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang bool IsValueKilledByLoopSideEffects() const { 149803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang return value_killed_by_loop_side_effects_; 150803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang } 151803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang 152803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang void SetValueKilledByLoopSideEffects(bool val) { 153803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang value_killed_by_loop_side_effects_ = val; 154803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang } 155803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang 1568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang private: 1578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* const ref_info_; // reference for instance/static field or array access. 1588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const size_t offset_; // offset of static/instance field. 1598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* const index_; // index of an array element. 1608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const int16_t declaring_class_def_index_; // declaring class's def's dex index. 161803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang bool value_killed_by_loop_side_effects_; // value of this location may be killed by loop 162803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // side effects because this location is stored 163803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // into inside a loop. 1648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DISALLOW_COPY_AND_ASSIGN(HeapLocation); 1668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang}; 1678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangstatic HInstruction* HuntForOriginalReference(HInstruction* ref) { 1698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(ref != nullptr); 1708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang while (ref->IsNullCheck() || ref->IsBoundType()) { 1718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref = ref->InputAt(0); 1728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return ref; 1748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang} 1758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// A HeapLocationCollector collects all relevant heap locations and keeps 1778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// an aliasing matrix for all locations. 1788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangclass HeapLocationCollector : public HGraphVisitor { 1798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang public: 1808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang static constexpr size_t kHeapLocationNotFound = -1; 1818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Start with a single uint32_t word. That's enough bits for pair-wise 1828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // aliasing matrix of 8 heap locations. 1838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang static constexpr uint32_t kInitialAliasingMatrixBitVectorSize = 32; 1848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang explicit HeapLocationCollector(HGraph* graph) 1868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang : HGraphVisitor(graph), 1878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref_info_array_(graph->GetArena()->Adapter(kArenaAllocLSE)), 1888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_locations_(graph->GetArena()->Adapter(kArenaAllocLSE)), 1898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang aliasing_matrix_(graph->GetArena(), kInitialAliasingMatrixBitVectorSize, true), 1908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_heap_stores_(false), 1918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_volatile_(false), 1928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_monitor_operations_(false), 1938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang may_deoptimize_(false) {} 1948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t GetNumberOfHeapLocations() const { 1968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return heap_locations_.size(); 1978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* GetHeapLocation(size_t index) const { 2008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return heap_locations_[index]; 2018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* FindReferenceInfoOf(HInstruction* ref) const { 2048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < ref_info_array_.size(); i++) { 2058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = ref_info_array_[i]; 2068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info->GetReference() == ref) { 2078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK_EQ(i, ref_info->GetPosition()); 2088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return ref_info; 2098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return nullptr; 2128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool HasHeapStores() const { 2158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return has_heap_stores_; 2168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool HasVolatile() const { 2198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return has_volatile_; 2208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool HasMonitorOps() const { 2238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return has_monitor_operations_; 2248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns whether this method may be deoptimized. 2278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Currently we don't have meta data support for deoptimizing 2288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // a method that eliminates allocations/stores. 2298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool MayDeoptimize() const { 2308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return may_deoptimize_; 2318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Find and return the heap location index in heap_locations_. 2348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t FindHeapLocationIndex(ReferenceInfo* ref_info, 2358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset, 2368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index, 2378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index) const { 2388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < heap_locations_.size(); i++) { 2398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* loc = heap_locations_[i]; 2408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (loc->GetReferenceInfo() == ref_info && 2418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang loc->GetOffset() == offset && 2428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang loc->GetIndex() == index && 2438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang loc->GetDeclaringClassDefIndex() == declaring_class_def_index) { 2448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return i; 2458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return kHeapLocationNotFound; 2488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns true if heap_locations_[index1] and heap_locations_[index2] may alias. 2518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool MayAlias(size_t index1, size_t index2) const { 2528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (index1 < index2) { 2538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return aliasing_matrix_.IsBitSet(AliasingMatrixPosition(index1, index2)); 2548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (index1 > index2) { 2558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return aliasing_matrix_.IsBitSet(AliasingMatrixPosition(index2, index1)); 2568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else { 2578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(false) << "index1 and index2 are expected to be different"; 2588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 2598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void BuildAliasingMatrix() { 2638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const size_t number_of_locations = heap_locations_.size(); 2648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (number_of_locations == 0) { 2658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 2668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t pos = 0; 2688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Compute aliasing info between every pair of different heap locations. 2698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Save the result in a matrix represented as a BitVector. 2708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < number_of_locations - 1; i++) { 2718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t j = i + 1; j < number_of_locations; j++) { 2728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ComputeMayAlias(i, j)) { 2738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang aliasing_matrix_.SetBit(CheckedAliasingMatrixPosition(i, j, pos)); 2748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang pos++; 2768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang private: 2818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // An allocation cannot alias with a name which already exists at the point 2828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // of the allocation, such as a parameter or a load happening before the allocation. 2838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool MayAliasWithPreexistenceChecking(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) const { 2848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info1->GetReference()->IsNewInstance() || ref_info1->GetReference()->IsNewArray()) { 2858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Any reference that can alias with the allocation must appear after it in the block/in 2868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // the block's successors. In reverse post order, those instructions will be visited after 2878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // the allocation. 2888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return ref_info2->GetPosition() >= ref_info1->GetPosition(); 2898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 2918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool CanReferencesAlias(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) const { 2948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info1 == ref_info2) { 2958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 2968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (ref_info1->IsSingleton()) { 2978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 2988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (ref_info2->IsSingleton()) { 2998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (!MayAliasWithPreexistenceChecking(ref_info1, ref_info2) || 3018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang !MayAliasWithPreexistenceChecking(ref_info2, ref_info1)) { 3028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 3058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // `index1` and `index2` are indices in the array of collected heap locations. 3088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns the position in the bit vector that tracks whether the two heap 3098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // locations may alias. 3108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t AliasingMatrixPosition(size_t index1, size_t index2) const { 3118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(index2 > index1); 3128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const size_t number_of_locations = heap_locations_.size(); 3138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // It's (num_of_locations - 1) + ... + (num_of_locations - index1) + (index2 - index1 - 1). 3148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return (number_of_locations * index1 - (1 + index1) * index1 / 2 + (index2 - index1 - 1)); 3158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // An additional position is passed in to make sure the calculated position is correct. 3188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t CheckedAliasingMatrixPosition(size_t index1, size_t index2, size_t position) { 3198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t calculated_position = AliasingMatrixPosition(index1, index2); 3208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK_EQ(calculated_position, position); 3218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return calculated_position; 3228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Compute if two locations may alias to each other. 3258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool ComputeMayAlias(size_t index1, size_t index2) const { 3268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* loc1 = heap_locations_[index1]; 3278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* loc2 = heap_locations_[index2]; 3288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (loc1->GetOffset() != loc2->GetOffset()) { 3298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Either two different instance fields, or one is an instance 3308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // field and the other is an array element. 3318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (loc1->GetDeclaringClassDefIndex() != loc2->GetDeclaringClassDefIndex()) { 3348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Different types. 3358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (!CanReferencesAlias(loc1->GetReferenceInfo(), loc2->GetReferenceInfo())) { 3388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (loc1->IsArrayElement() && loc2->IsArrayElement()) { 3418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* array_index1 = loc1->GetIndex(); 3428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* array_index2 = loc2->GetIndex(); 3438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(array_index1 != nullptr); 3448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(array_index2 != nullptr); 3458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (array_index1->IsIntConstant() && 3468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang array_index2->IsIntConstant() && 3478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang array_index1->AsIntConstant()->GetValue() != array_index2->AsIntConstant()->GetValue()) { 3488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Different constant indices do not alias. 3498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 3538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3558ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang ReferenceInfo* GetOrCreateReferenceInfo(HInstruction* instruction) { 3568ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang ReferenceInfo* ref_info = FindReferenceInfoOf(instruction); 3578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info == nullptr) { 3588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t pos = ref_info_array_.size(); 3598ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang ref_info = new (GetGraph()->GetArena()) ReferenceInfo(instruction, pos); 3608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref_info_array_.push_back(ref_info); 3618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return ref_info; 3638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3658ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang void CreateReferenceInfoForReferenceType(HInstruction* instruction) { 3668ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang if (instruction->GetType() != Primitive::kPrimNot) { 3678ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang return; 3688ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang } 3698ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang DCHECK(FindReferenceInfoOf(instruction) == nullptr); 3708ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang GetOrCreateReferenceInfo(instruction); 3718ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang } 3728ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang 3738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* GetOrCreateHeapLocation(HInstruction* ref, 3748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset, 3758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index, 3768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index) { 3778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* original_ref = HuntForOriginalReference(ref); 3788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = GetOrCreateReferenceInfo(original_ref); 3798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t heap_location_idx = FindHeapLocationIndex( 3808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref_info, offset, index, declaring_class_def_index); 3818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_location_idx == kHeapLocationNotFound) { 3828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* heap_loc = new (GetGraph()->GetArena()) 3838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation(ref_info, offset, index, declaring_class_def_index); 3848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_locations_.push_back(heap_loc); 3858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return heap_loc; 3868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return heap_locations_[heap_location_idx]; 3888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 390803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang HeapLocation* VisitFieldAccess(HInstruction* ref, const FieldInfo& field_info) { 3918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (field_info.IsVolatile()) { 3928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_volatile_ = true; 3938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const uint16_t declaring_class_def_index = field_info.GetDeclaringClassDefIndex(); 3958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const size_t offset = field_info.GetFieldOffset().SizeValue(); 396803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang return GetOrCreateHeapLocation(ref, offset, nullptr, declaring_class_def_index); 3978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitArrayAccess(HInstruction* array, HInstruction* index) { 4008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang GetOrCreateHeapLocation(array, HeapLocation::kInvalidFieldOffset, 4018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang index, HeapLocation::kDeclaringClassDefIndexForArrays); 4028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInstanceFieldGet(HInstanceFieldGet* instruction) OVERRIDE { 405fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); 4068ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang CreateReferenceInfoForReferenceType(instruction); 4078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInstanceFieldSet(HInstanceFieldSet* instruction) OVERRIDE { 410803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang HeapLocation* location = VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); 4118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_heap_stores_ = true; 412803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang if (instruction->GetBlock()->GetLoopInformation() != nullptr) { 413803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang location->SetValueKilledByLoopSideEffects(true); 414803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang } 4158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitStaticFieldGet(HStaticFieldGet* instruction) OVERRIDE { 418fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); 4198ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang CreateReferenceInfoForReferenceType(instruction); 4208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitStaticFieldSet(HStaticFieldSet* instruction) OVERRIDE { 423fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); 4248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_heap_stores_ = true; 4258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // We intentionally don't collect HUnresolvedInstanceField/HUnresolvedStaticField accesses 4288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // since we cannot accurately track the fields. 4298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitArrayGet(HArrayGet* instruction) OVERRIDE { 4318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitArrayAccess(instruction->InputAt(0), instruction->InputAt(1)); 4328ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang CreateReferenceInfoForReferenceType(instruction); 4338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitArraySet(HArraySet* instruction) OVERRIDE { 4368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitArrayAccess(instruction->InputAt(0), instruction->InputAt(1)); 4378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_heap_stores_ = true; 4388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitNewInstance(HNewInstance* new_instance) OVERRIDE { 4418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Any references appearing in the ref_info_array_ so far cannot alias with new_instance. 4428ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang CreateReferenceInfoForReferenceType(new_instance); 4438ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang } 4448ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang 4458ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* instruction) OVERRIDE { 4468ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang CreateReferenceInfoForReferenceType(instruction); 4478ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang } 4488ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang 4498ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang void VisitInvokeVirtual(HInvokeVirtual* instruction) OVERRIDE { 4508ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang CreateReferenceInfoForReferenceType(instruction); 4518ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang } 4528ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang 4538ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang void VisitInvokeInterface(HInvokeInterface* instruction) OVERRIDE { 4548ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang CreateReferenceInfoForReferenceType(instruction); 4558ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang } 4568ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang 4578ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang void VisitParameterValue(HParameterValue* instruction) OVERRIDE { 4588ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang CreateReferenceInfoForReferenceType(instruction); 4598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitDeoptimize(HDeoptimize* instruction ATTRIBUTE_UNUSED) OVERRIDE { 4628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang may_deoptimize_ = true; 4638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitMonitorOperation(HMonitorOperation* monitor ATTRIBUTE_UNUSED) OVERRIDE { 4668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_monitor_operations_ = true; 4678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<ReferenceInfo*> ref_info_array_; // All references used for heap accesses. 4708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HeapLocation*> heap_locations_; // All heap locations. 4718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaBitVector aliasing_matrix_; // aliasing info between each pair of locations. 4728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool has_heap_stores_; // If there is no heap stores, LSE acts as GVN with better 4738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // alias analysis and won't be as effective. 4748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool has_volatile_; // If there are volatile field accesses. 4758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool has_monitor_operations_; // If there are monitor operations. 4768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool may_deoptimize_; 4778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DISALLOW_COPY_AND_ASSIGN(HeapLocationCollector); 4798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang}; 4808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// An unknown heap value. Loads with such a value in the heap location cannot be eliminated. 482fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang// A heap location can be set to kUnknownHeapValue when: 483fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang// - initially set a value. 484fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang// - killed due to aliasing, merging, invocation, or loop side effects. 4858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangstatic HInstruction* const kUnknownHeapValue = 4868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang reinterpret_cast<HInstruction*>(static_cast<uintptr_t>(-1)); 487fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 4888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// Default heap value after an allocation. 489fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang// A heap location can be set to that value right after an allocation. 4908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangstatic HInstruction* const kDefaultHeapValue = 4918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang reinterpret_cast<HInstruction*>(static_cast<uintptr_t>(-2)); 4928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangclass LSEVisitor : public HGraphVisitor { 4948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang public: 4958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang LSEVisitor(HGraph* graph, 4968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const HeapLocationCollector& heap_locations_collector, 4978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const SideEffectsAnalysis& side_effects) 4988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang : HGraphVisitor(graph), 4998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_location_collector_(heap_locations_collector), 5008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang side_effects_(side_effects), 5018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values_for_(graph->GetBlocks().size(), 5028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>(heap_locations_collector. 5038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang GetNumberOfHeapLocations(), 5048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang kUnknownHeapValue, 5058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang graph->GetArena()->Adapter(kArenaAllocLSE)), 5068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang graph->GetArena()->Adapter(kArenaAllocLSE)), 507fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang removed_loads_(graph->GetArena()->Adapter(kArenaAllocLSE)), 508fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang substitute_instructions_for_loads_(graph->GetArena()->Adapter(kArenaAllocLSE)), 509fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_removed_stores_(graph->GetArena()->Adapter(kArenaAllocLSE)), 5108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang singleton_new_instances_(graph->GetArena()->Adapter(kArenaAllocLSE)) { 5118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 5128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 5138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitBasicBlock(HBasicBlock* block) OVERRIDE { 514fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Populate the heap_values array for this block. 5158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // TODO: try to reuse the heap_values array from one predecessor if possible. 5168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (block->IsLoopHeader()) { 517fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HandleLoopSideEffects(block); 5188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else { 5198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang MergePredecessorValues(block); 5208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 5218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HGraphVisitor::VisitBasicBlock(block); 5228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 5238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 5248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Remove recorded instructions that should be eliminated. 5258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void RemoveInstructions() { 526fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang size_t size = removed_loads_.size(); 527fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK_EQ(size, substitute_instructions_for_loads_.size()); 5288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < size; i++) { 529fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* load = removed_loads_[i]; 530fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(load != nullptr); 531fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(load->IsInstanceFieldGet() || 532fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang load->IsStaticFieldGet() || 533fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang load->IsArrayGet()); 534fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* substitute = substitute_instructions_for_loads_[i]; 535fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(substitute != nullptr); 536fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Keep tracing substitute till one that's not removed. 537fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* sub_sub = FindSubstitute(substitute); 538fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang while (sub_sub != substitute) { 539fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang substitute = sub_sub; 540fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang sub_sub = FindSubstitute(substitute); 5418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 542fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang load->ReplaceWith(substitute); 543fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang load->GetBlock()->RemoveInstruction(load); 5448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 545fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 546fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // At this point, stores in possibly_removed_stores_ can be safely removed. 547fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang size = possibly_removed_stores_.size(); 548fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang for (size_t i = 0; i < size; i++) { 549fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* store = possibly_removed_stores_[i]; 550fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(store->IsInstanceFieldSet() || store->IsStaticFieldSet() || store->IsArraySet()); 551fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang store->GetBlock()->RemoveInstruction(store); 552fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 553fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 5548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // TODO: remove unnecessary allocations. 5558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Eliminate instructions in singleton_new_instances_ that: 5568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // - don't have uses, 5578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // - don't have finalizers, 5588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // - are instantiable and accessible, 5598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // - have no/separate clinit check. 5608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 5618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 5628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang private: 563fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // If heap_values[index] is an instance field store, need to keep the store. 564fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // This is necessary if a heap value is killed due to merging, or loop side 565fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // effects (which is essentially merging also), since a load later from the 566fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // location won't be eliminated. 567fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang void KeepIfIsStore(HInstruction* heap_value) { 568fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (heap_value == kDefaultHeapValue || 569fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_value == kUnknownHeapValue || 570fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang !heap_value->IsInstanceFieldSet()) { 571fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang return; 572fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 573fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang auto idx = std::find(possibly_removed_stores_.begin(), 574fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_removed_stores_.end(), heap_value); 575fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (idx != possibly_removed_stores_.end()) { 576fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Make sure the store is kept. 577fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_removed_stores_.erase(idx); 578fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 579fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 580fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 581fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang void HandleLoopSideEffects(HBasicBlock* block) { 582fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(block->IsLoopHeader()); 583fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang int block_id = block->GetBlockId(); 584fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*>& heap_values = heap_values_for_[block_id]; 585fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader(); 586fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*>& pre_header_heap_values = 587fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_values_for_[pre_header->GetBlockId()]; 588803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // Inherit the values from pre-header. 589803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 590803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang heap_values[i] = pre_header_heap_values[i]; 591803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang } 592803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang 593fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // We do a single pass in reverse post order. For loops, use the side effects as a hint 594fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // to see if the heap values should be killed. 595fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (side_effects_.GetLoopEffects(block).DoesAnyWrite()) { 596fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 597803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang HeapLocation* location = heap_location_collector_.GetHeapLocation(i); 598803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang ReferenceInfo* ref_info = location->GetReferenceInfo(); 599803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang if (!ref_info->IsSingleton() || location->IsValueKilledByLoopSideEffects()) { 600803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // heap value is killed by loop side effects (stored into directly, or due to 601803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // aliasing). 602803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang KeepIfIsStore(pre_header_heap_values[i]); 603803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang heap_values[i] = kUnknownHeapValue; 604803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang } else { 605803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // A singleton's field that's not stored into inside a loop is invariant throughout 606803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // the loop. 607803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang } 608fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 609fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 610fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 611fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 6128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void MergePredecessorValues(HBasicBlock* block) { 6138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const ArenaVector<HBasicBlock*>& predecessors = block->GetPredecessors(); 6148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (predecessors.size() == 0) { 6158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 6168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>& heap_values = heap_values_for_[block->GetBlockId()]; 6188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 619fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* pred0_value = heap_values_for_[predecessors[0]->GetBlockId()][i]; 620fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_values[i] = pred0_value; 621fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (pred0_value != kUnknownHeapValue) { 6228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t j = 1; j < predecessors.size(); j++) { 623fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* pred_value = heap_values_for_[predecessors[j]->GetBlockId()][i]; 624fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (pred_value != pred0_value) { 625fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_values[i] = kUnknownHeapValue; 6268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang break; 6278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 630fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 631fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (heap_values[i] == kUnknownHeapValue) { 632fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Keep the last store in each predecessor since future loads cannot be eliminated. 633fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang for (size_t j = 0; j < predecessors.size(); j++) { 634fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*>& pred_values = heap_values_for_[predecessors[j]->GetBlockId()]; 635fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang KeepIfIsStore(pred_values[i]); 636fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 637fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 6388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 6418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // `instruction` is being removed. Try to see if the null check on it 6428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // can be removed. This can happen if the same value is set in two branches 6438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // but not in dominators. Such as: 6448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // int[] a = foo(); 6458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // if () { 6468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // a[0] = 2; 6478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // } else { 6488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // a[0] = 2; 6498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // } 6508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // // a[0] can now be replaced with constant 2, and the null check on it can be removed. 6518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void TryRemovingNullCheck(HInstruction* instruction) { 6528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* prev = instruction->GetPrevious(); 6538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if ((prev != nullptr) && prev->IsNullCheck() && (prev == instruction->InputAt(0))) { 6548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Previous instruction is a null check for this instruction. Remove the null check. 6558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang prev->ReplaceWith(prev->InputAt(0)); 6568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang prev->GetBlock()->RemoveInstruction(prev); 6578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 6608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* GetDefaultValue(Primitive::Type type) { 6618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang switch (type) { 6628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimNot: 6638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return GetGraph()->GetNullConstant(); 6648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimBoolean: 6658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimByte: 6668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimChar: 6678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimShort: 6688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimInt: 6698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return GetGraph()->GetIntConstant(0); 6708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimLong: 6718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return GetGraph()->GetLongConstant(0); 6728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimFloat: 6738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return GetGraph()->GetFloatConstant(0); 6748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimDouble: 6758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return GetGraph()->GetDoubleConstant(0); 6768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang default: 6778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang UNREACHABLE(); 6788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 681ecf52dfa46addbbd5d1ee92a4bc9b7a9fd960629David Brazdil static bool IsIntFloatAlias(Primitive::Type type1, Primitive::Type type2) { 682ecf52dfa46addbbd5d1ee92a4bc9b7a9fd960629David Brazdil return (type1 == Primitive::kPrimFloat && type2 == Primitive::kPrimInt) || 683ecf52dfa46addbbd5d1ee92a4bc9b7a9fd960629David Brazdil (type2 == Primitive::kPrimFloat && type1 == Primitive::kPrimInt); 684ecf52dfa46addbbd5d1ee92a4bc9b7a9fd960629David Brazdil } 685ecf52dfa46addbbd5d1ee92a4bc9b7a9fd960629David Brazdil 686ecf52dfa46addbbd5d1ee92a4bc9b7a9fd960629David Brazdil static bool IsLongDoubleAlias(Primitive::Type type1, Primitive::Type type2) { 687ecf52dfa46addbbd5d1ee92a4bc9b7a9fd960629David Brazdil return (type1 == Primitive::kPrimDouble && type2 == Primitive::kPrimLong) || 688ecf52dfa46addbbd5d1ee92a4bc9b7a9fd960629David Brazdil (type2 == Primitive::kPrimDouble && type1 == Primitive::kPrimLong); 689ecf52dfa46addbbd5d1ee92a4bc9b7a9fd960629David Brazdil } 690ecf52dfa46addbbd5d1ee92a4bc9b7a9fd960629David Brazdil 6918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitGetLocation(HInstruction* instruction, 6928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* ref, 6938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset, 6948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index, 6958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index) { 6968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* original_ref = HuntForOriginalReference(ref); 6978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref); 6988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t idx = heap_location_collector_.FindHeapLocationIndex( 6998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref_info, offset, index, declaring_class_def_index); 7008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); 7018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>& heap_values = 7028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values_for_[instruction->GetBlock()->GetBlockId()]; 7038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* heap_value = heap_values[idx]; 7048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_value == kDefaultHeapValue) { 7058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* constant = GetDefaultValue(instruction->GetType()); 706fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang removed_loads_.push_back(instruction); 707fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang substitute_instructions_for_loads_.push_back(constant); 7088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values[idx] = constant; 7098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 7108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 711fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (heap_value != kUnknownHeapValue && heap_value->IsInstanceFieldSet()) { 712fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* store = heap_value; 713fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // This load must be from a singleton since it's from the same field 714fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // that a "removed" store puts the value. That store must be to a singleton's field. 715fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(ref_info->IsSingleton()); 716fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Get the real heap value of the store. 717fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_value = store->InputAt(1); 718fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 7198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if ((heap_value != kUnknownHeapValue) && 7208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Keep the load due to possible I/F, J/D array aliasing. 7218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // See b/22538329 for details. 722ecf52dfa46addbbd5d1ee92a4bc9b7a9fd960629David Brazdil !IsIntFloatAlias(heap_value->GetType(), instruction->GetType()) && 723ecf52dfa46addbbd5d1ee92a4bc9b7a9fd960629David Brazdil !IsLongDoubleAlias(heap_value->GetType(), instruction->GetType())) { 724fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang removed_loads_.push_back(instruction); 725fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang substitute_instructions_for_loads_.push_back(heap_value); 7268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang TryRemovingNullCheck(instruction); 7278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 7288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 730fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Load isn't eliminated. 7318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_value == kUnknownHeapValue) { 7328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Put the load as the value into the HeapLocation. 7338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // This acts like GVN but with better aliasing analysis. 7348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values[idx] = instruction; 7358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 7388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool Equal(HInstruction* heap_value, HInstruction* value) { 7398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_value == value) { 7408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 7418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_value == kDefaultHeapValue && GetDefaultValue(value->GetType()) == value) { 7438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 7448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 7468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 7488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitSetLocation(HInstruction* instruction, 7498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* ref, 7508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset, 7518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index, 7528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index, 7538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* value) { 7548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* original_ref = HuntForOriginalReference(ref); 7558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref); 7568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t idx = heap_location_collector_.FindHeapLocationIndex( 7578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref_info, offset, index, declaring_class_def_index); 7588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); 7598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>& heap_values = 7608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values_for_[instruction->GetBlock()->GetBlockId()]; 7618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* heap_value = heap_values[idx]; 762fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang bool same_value = false; 763fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang bool possibly_redundant = false; 7648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (Equal(heap_value, value)) { 7658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Store into the heap location with the same value. 766fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang same_value = true; 7678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (index != nullptr) { 7688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // For array element, don't eliminate stores since it can be easily aliased 7698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // with non-constant index. 7708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (!heap_location_collector_.MayDeoptimize() && 771fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ref_info->IsSingletonAndNotReturned()) { 772fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Store into a field of a singleton that's not returned. The value cannot be 773fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // killed due to aliasing/invocation. It can be redundant since future loads can 774fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // directly get the value set by this instruction. The value can still be killed due to 775fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // merging or loop side effects. Stores whose values are killed due to merging/loop side 776fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // effects later will be removed from possibly_removed_stores_ when that is detected. 777fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_redundant = true; 778fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HNewInstance* new_instance = ref_info->GetReference()->AsNewInstance(); 779fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(new_instance != nullptr); 780fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (new_instance->IsFinalizable()) { 781fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Finalizable objects escape globally. Need to keep the store. 782fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_redundant = false; 7838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else { 784fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HLoopInformation* loop_info = instruction->GetBlock()->GetLoopInformation(); 785fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (loop_info != nullptr) { 786fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // instruction is a store in the loop so the loop must does write. 787fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(side_effects_.GetLoopEffects(loop_info->GetHeader()).DoesAnyWrite()); 788803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // If it's a singleton, IsValueKilledByLoopSideEffects() must be true. 789803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang DCHECK(!ref_info->IsSingleton() || 790803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang heap_location_collector_.GetHeapLocation(idx)->IsValueKilledByLoopSideEffects()); 791fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 7924b467ed97bc5886fb800209c0ee94df10163b88dMingyao Yang if (loop_info->IsDefinedOutOfTheLoop(original_ref)) { 793fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(original_ref->GetBlock()->Dominates(loop_info->GetPreHeader())); 794fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Keep the store since its value may be needed at the loop header. 795fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_redundant = false; 796fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } else { 797fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // The singleton is created inside the loop. Value stored to it isn't needed at 798fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // the loop header. This is true for outer loops also. 799fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 800fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 8018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 803fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (same_value || possibly_redundant) { 804fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_removed_stores_.push_back(instruction); 8058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 806e9d6e6083e845194548e0705fdf9e172c7a043e5Mingyao Yang 807fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (!same_value) { 808fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (possibly_redundant) { 809fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(instruction->IsInstanceFieldSet()); 810fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Put the store as the heap value. If the value is loaded from heap 811fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // by a load later, this store isn't really redundant. 812fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_values[idx] = instruction; 813fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } else { 814fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_values[idx] = value; 815fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 816fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 8178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // This store may kill values in other heap locations due to aliasing. 8188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 819fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (i == idx) { 820fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang continue; 821fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 8228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_values[i] == value) { 8238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Same value should be kept even if aliasing happens. 8248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang continue; 8258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_values[i] == kUnknownHeapValue) { 8278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Value is already unknown, no need for aliasing check. 8288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang continue; 8298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_location_collector_.MayAlias(i, idx)) { 8318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Kill heap locations that may alias. 8328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values[i] = kUnknownHeapValue; 8338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInstanceFieldGet(HInstanceFieldGet* instruction) OVERRIDE { 8388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* obj = instruction->InputAt(0); 8398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); 8408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); 8418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitGetLocation(instruction, obj, offset, nullptr, declaring_class_def_index); 8428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInstanceFieldSet(HInstanceFieldSet* instruction) OVERRIDE { 8458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* obj = instruction->InputAt(0); 8468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); 8478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); 8488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* value = instruction->InputAt(1); 8498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitSetLocation(instruction, obj, offset, nullptr, declaring_class_def_index, value); 8508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitStaticFieldGet(HStaticFieldGet* instruction) OVERRIDE { 8538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* cls = instruction->InputAt(0); 8548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); 8558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); 8568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitGetLocation(instruction, cls, offset, nullptr, declaring_class_def_index); 8578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitStaticFieldSet(HStaticFieldSet* instruction) OVERRIDE { 8608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* cls = instruction->InputAt(0); 8618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); 8628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); 8638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* value = instruction->InputAt(1); 8648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitSetLocation(instruction, cls, offset, nullptr, declaring_class_def_index, value); 8658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitArrayGet(HArrayGet* instruction) OVERRIDE { 8688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* array = instruction->InputAt(0); 8698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index = instruction->InputAt(1); 8708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitGetLocation(instruction, 8718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang array, 8728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation::kInvalidFieldOffset, 8738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang index, 8748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation::kDeclaringClassDefIndexForArrays); 8758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitArraySet(HArraySet* instruction) OVERRIDE { 8788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* array = instruction->InputAt(0); 8798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index = instruction->InputAt(1); 8808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* value = instruction->InputAt(2); 8818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitSetLocation(instruction, 8828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang array, 8838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation::kInvalidFieldOffset, 8848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang index, 8858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation::kDeclaringClassDefIndexForArrays, 8868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang value); 8878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void HandleInvoke(HInstruction* invoke) { 8908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>& heap_values = 8918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values_for_[invoke->GetBlock()->GetBlockId()]; 8928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 8938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo(); 8948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info->IsSingleton()) { 8958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Singleton references cannot be seen by the callee. 8968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else { 8978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values[i] = kUnknownHeapValue; 8988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) OVERRIDE { 9038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(invoke); 9048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInvokeVirtual(HInvokeVirtual* invoke) OVERRIDE { 9078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(invoke); 9088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInvokeInterface(HInvokeInterface* invoke) OVERRIDE { 9118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(invoke); 9128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInvokeUnresolved(HInvokeUnresolved* invoke) OVERRIDE { 9158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(invoke); 9168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitClinitCheck(HClinitCheck* clinit) OVERRIDE { 9198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(clinit); 9208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitUnresolvedInstanceFieldGet(HUnresolvedInstanceFieldGet* instruction) OVERRIDE { 9238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Conservatively treat it as an invocation. 9248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(instruction); 9258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitUnresolvedInstanceFieldSet(HUnresolvedInstanceFieldSet* instruction) OVERRIDE { 9288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Conservatively treat it as an invocation. 9298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(instruction); 9308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitUnresolvedStaticFieldGet(HUnresolvedStaticFieldGet* instruction) OVERRIDE { 9338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Conservatively treat it as an invocation. 9348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(instruction); 9358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitUnresolvedStaticFieldSet(HUnresolvedStaticFieldSet* instruction) OVERRIDE { 9388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Conservatively treat it as an invocation. 9398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(instruction); 9408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitNewInstance(HNewInstance* new_instance) OVERRIDE { 9438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(new_instance); 9448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info == nullptr) { 9458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // new_instance isn't used for field accesses. No need to process it. 9468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 9478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (!heap_location_collector_.MayDeoptimize() && 949fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ref_info->IsSingletonAndNotReturned() && 950fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang !new_instance->IsFinalizable() && 951fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang !new_instance->CanThrow()) { 952fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // TODO: add new_instance to singleton_new_instances_ and enable allocation elimination. 9538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>& heap_values = 9558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values_for_[new_instance->GetBlock()->GetBlockId()]; 9568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 9578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* ref = 9588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo()->GetReference(); 9598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset = heap_location_collector_.GetHeapLocation(i)->GetOffset(); 9608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref == new_instance && offset >= mirror::kObjectHeaderSize) { 9618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Instance fields except the header fields are set to default heap values. 9628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values[i] = kDefaultHeapValue; 9638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Find an instruction's substitute if it should be removed. 9688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Return the same instruction if it should not be removed. 9698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* FindSubstitute(HInstruction* instruction) { 970fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang size_t size = removed_loads_.size(); 9718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < size; i++) { 972fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (removed_loads_[i] == instruction) { 973fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang return substitute_instructions_for_loads_[i]; 9748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return instruction; 9778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const HeapLocationCollector& heap_location_collector_; 9808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const SideEffectsAnalysis& side_effects_; 9818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // One array of heap values for each block. 9838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<ArenaVector<HInstruction*>> heap_values_for_; 9848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // We record the instructions that should be eliminated but may be 9868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // used by heap locations. They'll be removed in the end. 987fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*> removed_loads_; 988fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*> substitute_instructions_for_loads_; 989fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 990fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Stores in this list may be removed from the list later when it's 991fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // found that the store cannot be eliminated. 992fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*> possibly_removed_stores_; 993fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 9948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*> singleton_new_instances_; 9958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DISALLOW_COPY_AND_ASSIGN(LSEVisitor); 9978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang}; 9988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangvoid LoadStoreElimination::Run() { 10008993caf6571863c8e5eec0b2ce4d72f6f1793f31David Brazdil if (graph_->IsDebuggable() || graph_->HasTryCatch()) { 10018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Debugger may set heap values or trigger deoptimization of callers. 10028993caf6571863c8e5eec0b2ce4d72f6f1793f31David Brazdil // Try/catch support not implemented yet. 10038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Skip this optimization. 10048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 10058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 10068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocationCollector heap_location_collector(graph_); 10078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 10088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_location_collector.VisitBasicBlock(it.Current()); 10098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 10108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_location_collector.GetNumberOfHeapLocations() > kMaxNumberOfHeapLocations) { 10118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Bail out if there are too many heap locations to deal with. 10128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 10138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 10148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (!heap_location_collector.HasHeapStores()) { 10158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Without heap stores, this pass would act mostly as GVN on heap accesses. 10168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 10178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 10188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_location_collector.HasVolatile() || heap_location_collector.HasMonitorOps()) { 10198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Don't do load/store elimination if the method has volatile field accesses or 10208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // monitor operations, for now. 10218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // TODO: do it right. 10228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 10238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 10248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_location_collector.BuildAliasingMatrix(); 10258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang LSEVisitor lse_visitor(graph_, heap_location_collector, side_effects_); 10268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 10278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang lse_visitor.VisitBasicBlock(it.Current()); 10288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 10298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang lse_visitor.RemoveInstructions(); 10308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang} 10318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 10328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang} // namespace art 1033