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. 46d59f3b1b7f5c1ab9f0731ff9dc60611e8d9a6edeVladimir Marko for (const HUseListNode<HInstruction*>& use : reference_->GetUses()) { 47d59f3b1b7f5c1ab9f0731ff9dc60611e8d9a6edeVladimir Marko HInstruction* user = use.GetUser(); 48d59f3b1b7f5c1ab9f0731ff9dc60611e8d9a6edeVladimir Marko DCHECK(!user->IsNullCheck()) << "NullCheck should have been eliminated"; 49d59f3b1b7f5c1ab9f0731ff9dc60611e8d9a6edeVladimir Marko if (user->IsBoundType()) { 508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // BoundType shouldn't normally be necessary for a NewInstance. 518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Just be conservative for the uncommon cases. 528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_ = false; 538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_and_not_returned_ = false; 548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 56d59f3b1b7f5c1ab9f0731ff9dc60611e8d9a6edeVladimir Marko if (user->IsPhi() || user->IsSelect() || user->IsInvoke() || 57d59f3b1b7f5c1ab9f0731ff9dc60611e8d9a6edeVladimir Marko (user->IsInstanceFieldSet() && (reference_ == user->InputAt(1))) || 58d59f3b1b7f5c1ab9f0731ff9dc60611e8d9a6edeVladimir Marko (user->IsUnresolvedInstanceFieldSet() && (reference_ == user->InputAt(1))) || 59d59f3b1b7f5c1ab9f0731ff9dc60611e8d9a6edeVladimir Marko (user->IsStaticFieldSet() && (reference_ == user->InputAt(1))) || 60d59f3b1b7f5c1ab9f0731ff9dc60611e8d9a6edeVladimir Marko (user->IsUnresolvedStaticFieldSet() && (reference_ == user->InputAt(0))) || 61d59f3b1b7f5c1ab9f0731ff9dc60611e8d9a6edeVladimir Marko (user->IsArraySet() && (reference_ == user->InputAt(2)))) { 6240bcb9356f951af2db4b9b671511841eedf59427Mingyao Yang // reference_ is merged to HPhi/HSelect, passed to a callee, or stored to heap. 638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // reference_ isn't the only name that can refer to its value anymore. 648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_ = false; 658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_and_not_returned_ = false; 668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 68c2f1735e04537c94a8505aa2badd31281087ab51Nicolas Geoffray if ((user->IsUnresolvedInstanceFieldGet() && (reference_ == user->InputAt(0))) || 69c2f1735e04537c94a8505aa2badd31281087ab51Nicolas Geoffray (user->IsUnresolvedInstanceFieldSet() && (reference_ == user->InputAt(0)))) { 70c2f1735e04537c94a8505aa2badd31281087ab51Nicolas Geoffray // The field is accessed in an unresolved way. We mark the object as a singleton to 71c2f1735e04537c94a8505aa2badd31281087ab51Nicolas Geoffray // disable load/store optimizations on it. 72c2f1735e04537c94a8505aa2badd31281087ab51Nicolas Geoffray // Note that we could optimize this case and still perform some optimizations until 73c2f1735e04537c94a8505aa2badd31281087ab51Nicolas Geoffray // we hit the unresolved access, but disabling is the simplest. 74c2f1735e04537c94a8505aa2badd31281087ab51Nicolas Geoffray is_singleton_ = false; 75c2f1735e04537c94a8505aa2badd31281087ab51Nicolas Geoffray is_singleton_and_not_returned_ = false; 76c2f1735e04537c94a8505aa2badd31281087ab51Nicolas Geoffray return; 77c2f1735e04537c94a8505aa2badd31281087ab51Nicolas Geoffray } 78d59f3b1b7f5c1ab9f0731ff9dc60611e8d9a6edeVladimir Marko if (user->IsReturn()) { 798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_and_not_returned_ = false; 808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* GetReference() const { 858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return reference_; 868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t GetPosition() const { 898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return position_; 908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns true if reference_ is the only name that can refer to its value during 938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // the lifetime of the method. So it's guaranteed to not have any alias in 948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // the method (including its callees). 958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool IsSingleton() const { 968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return is_singleton_; 978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns true if reference_ is a singleton and not returned to the caller. 1008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // The allocation and stores into reference_ may be eliminated for such cases. 1018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool IsSingletonAndNotReturned() const { 1028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return is_singleton_and_not_returned_; 1038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang private: 1068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* const reference_; 1078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const size_t position_; // position in HeapLocationCollector's ref_info_array_. 1088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool is_singleton_; // can only be referred to by a single name in the method. 1098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool is_singleton_and_not_returned_; // reference_ is singleton and not returned to caller. 1108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DISALLOW_COPY_AND_ASSIGN(ReferenceInfo); 1128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang}; 1138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// A heap location is a reference-offset/index pair that a value can be loaded from 1158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// or stored to. 1168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangclass HeapLocation : public ArenaObject<kArenaAllocMisc> { 1178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang public: 1188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang static constexpr size_t kInvalidFieldOffset = -1; 1198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // TODO: more fine-grained array types. 1218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang static constexpr int16_t kDeclaringClassDefIndexForArrays = -1; 1228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation(ReferenceInfo* ref_info, 1248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset, 1258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index, 1268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index) 1278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang : ref_info_(ref_info), 1288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang offset_(offset), 1298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang index_(index), 130803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang declaring_class_def_index_(declaring_class_def_index), 131803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang value_killed_by_loop_side_effects_(true) { 1328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(ref_info != nullptr); 1338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK((offset == kInvalidFieldOffset && index != nullptr) || 1348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang (offset != kInvalidFieldOffset && index == nullptr)); 135803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang if (ref_info->IsSingleton() && !IsArrayElement()) { 136803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // Assume this location's value cannot be killed by loop side effects 137803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // until proven otherwise. 138803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang value_killed_by_loop_side_effects_ = false; 139803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang } 1408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* GetReferenceInfo() const { return ref_info_; } 1438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t GetOffset() const { return offset_; } 1448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* GetIndex() const { return index_; } 1458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns the definition of declaring class' dex index. 1478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // It's kDeclaringClassDefIndexForArrays for an array element. 1488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t GetDeclaringClassDefIndex() const { 1498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return declaring_class_def_index_; 1508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool IsArrayElement() const { 1538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return index_ != nullptr; 1548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 156803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang bool IsValueKilledByLoopSideEffects() const { 157803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang return value_killed_by_loop_side_effects_; 158803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang } 159803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang 160803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang void SetValueKilledByLoopSideEffects(bool val) { 161803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang value_killed_by_loop_side_effects_ = val; 162803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang } 163803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang 1648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang private: 1658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* const ref_info_; // reference for instance/static field or array access. 1668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const size_t offset_; // offset of static/instance field. 1678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* const index_; // index of an array element. 1688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const int16_t declaring_class_def_index_; // declaring class's def's dex index. 169803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang bool value_killed_by_loop_side_effects_; // value of this location may be killed by loop 170803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // side effects because this location is stored 171803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // into inside a loop. 1728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DISALLOW_COPY_AND_ASSIGN(HeapLocation); 1748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang}; 1758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangstatic HInstruction* HuntForOriginalReference(HInstruction* ref) { 1778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(ref != nullptr); 1788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang while (ref->IsNullCheck() || ref->IsBoundType()) { 1798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref = ref->InputAt(0); 1808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return ref; 1828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang} 1838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// A HeapLocationCollector collects all relevant heap locations and keeps 1858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// an aliasing matrix for all locations. 1868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangclass HeapLocationCollector : public HGraphVisitor { 1878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang public: 1888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang static constexpr size_t kHeapLocationNotFound = -1; 1898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Start with a single uint32_t word. That's enough bits for pair-wise 1908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // aliasing matrix of 8 heap locations. 1918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang static constexpr uint32_t kInitialAliasingMatrixBitVectorSize = 32; 1928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang explicit HeapLocationCollector(HGraph* graph) 1948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang : HGraphVisitor(graph), 1958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref_info_array_(graph->GetArena()->Adapter(kArenaAllocLSE)), 1968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_locations_(graph->GetArena()->Adapter(kArenaAllocLSE)), 197f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko aliasing_matrix_(graph->GetArena(), 198f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko kInitialAliasingMatrixBitVectorSize, 199f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko true, 200f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko kArenaAllocLSE), 2018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_heap_stores_(false), 2028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_volatile_(false), 2038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_monitor_operations_(false), 2048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang may_deoptimize_(false) {} 2058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t GetNumberOfHeapLocations() const { 2078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return heap_locations_.size(); 2088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* GetHeapLocation(size_t index) const { 2118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return heap_locations_[index]; 2128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* FindReferenceInfoOf(HInstruction* ref) const { 2158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < ref_info_array_.size(); i++) { 2168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = ref_info_array_[i]; 2178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info->GetReference() == ref) { 2188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK_EQ(i, ref_info->GetPosition()); 2198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return ref_info; 2208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return nullptr; 2238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool HasHeapStores() const { 2268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return has_heap_stores_; 2278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool HasVolatile() const { 2308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return has_volatile_; 2318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool HasMonitorOps() const { 2348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return has_monitor_operations_; 2358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns whether this method may be deoptimized. 2388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Currently we don't have meta data support for deoptimizing 2398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // a method that eliminates allocations/stores. 2408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool MayDeoptimize() const { 2418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return may_deoptimize_; 2428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Find and return the heap location index in heap_locations_. 2458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t FindHeapLocationIndex(ReferenceInfo* ref_info, 2468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset, 2478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index, 2488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index) const { 2498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < heap_locations_.size(); i++) { 2508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* loc = heap_locations_[i]; 2518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (loc->GetReferenceInfo() == ref_info && 2528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang loc->GetOffset() == offset && 2538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang loc->GetIndex() == index && 2548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang loc->GetDeclaringClassDefIndex() == declaring_class_def_index) { 2558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return i; 2568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return kHeapLocationNotFound; 2598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns true if heap_locations_[index1] and heap_locations_[index2] may alias. 2628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool MayAlias(size_t index1, size_t index2) const { 2638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (index1 < index2) { 2648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return aliasing_matrix_.IsBitSet(AliasingMatrixPosition(index1, index2)); 2658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (index1 > index2) { 2668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return aliasing_matrix_.IsBitSet(AliasingMatrixPosition(index2, index1)); 2678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else { 2688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(false) << "index1 and index2 are expected to be different"; 2698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 2708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void BuildAliasingMatrix() { 2748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const size_t number_of_locations = heap_locations_.size(); 2758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (number_of_locations == 0) { 2768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 2778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t pos = 0; 2798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Compute aliasing info between every pair of different heap locations. 2808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Save the result in a matrix represented as a BitVector. 2818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < number_of_locations - 1; i++) { 2828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t j = i + 1; j < number_of_locations; j++) { 2838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ComputeMayAlias(i, j)) { 2848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang aliasing_matrix_.SetBit(CheckedAliasingMatrixPosition(i, j, pos)); 2858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang pos++; 2878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang private: 2928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // An allocation cannot alias with a name which already exists at the point 2938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // of the allocation, such as a parameter or a load happening before the allocation. 2948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool MayAliasWithPreexistenceChecking(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) const { 2958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info1->GetReference()->IsNewInstance() || ref_info1->GetReference()->IsNewArray()) { 2968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Any reference that can alias with the allocation must appear after it in the block/in 2978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // the block's successors. In reverse post order, those instructions will be visited after 2988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // the allocation. 2998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return ref_info2->GetPosition() >= ref_info1->GetPosition(); 3008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 3028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool CanReferencesAlias(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) const { 3058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info1 == ref_info2) { 3068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 3078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (ref_info1->IsSingleton()) { 3088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (ref_info2->IsSingleton()) { 3108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (!MayAliasWithPreexistenceChecking(ref_info1, ref_info2) || 3128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang !MayAliasWithPreexistenceChecking(ref_info2, ref_info1)) { 3138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 3168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // `index1` and `index2` are indices in the array of collected heap locations. 3198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns the position in the bit vector that tracks whether the two heap 3208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // locations may alias. 3218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t AliasingMatrixPosition(size_t index1, size_t index2) const { 3228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(index2 > index1); 3238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const size_t number_of_locations = heap_locations_.size(); 3248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // It's (num_of_locations - 1) + ... + (num_of_locations - index1) + (index2 - index1 - 1). 3258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return (number_of_locations * index1 - (1 + index1) * index1 / 2 + (index2 - index1 - 1)); 3268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // An additional position is passed in to make sure the calculated position is correct. 3298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t CheckedAliasingMatrixPosition(size_t index1, size_t index2, size_t position) { 3308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t calculated_position = AliasingMatrixPosition(index1, index2); 3318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK_EQ(calculated_position, position); 3328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return calculated_position; 3338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Compute if two locations may alias to each other. 3368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool ComputeMayAlias(size_t index1, size_t index2) const { 3378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* loc1 = heap_locations_[index1]; 3388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* loc2 = heap_locations_[index2]; 3398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (loc1->GetOffset() != loc2->GetOffset()) { 3408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Either two different instance fields, or one is an instance 3418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // field and the other is an array element. 3428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (loc1->GetDeclaringClassDefIndex() != loc2->GetDeclaringClassDefIndex()) { 3458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Different types. 3468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (!CanReferencesAlias(loc1->GetReferenceInfo(), loc2->GetReferenceInfo())) { 3498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (loc1->IsArrayElement() && loc2->IsArrayElement()) { 3528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* array_index1 = loc1->GetIndex(); 3538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* array_index2 = loc2->GetIndex(); 3548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(array_index1 != nullptr); 3558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(array_index2 != nullptr); 3568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (array_index1->IsIntConstant() && 3578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang array_index2->IsIntConstant() && 3588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang array_index1->AsIntConstant()->GetValue() != array_index2->AsIntConstant()->GetValue()) { 3598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Different constant indices do not alias. 3608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 3648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3668ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang ReferenceInfo* GetOrCreateReferenceInfo(HInstruction* instruction) { 3678ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang ReferenceInfo* ref_info = FindReferenceInfoOf(instruction); 3688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info == nullptr) { 3698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t pos = ref_info_array_.size(); 3708ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang ref_info = new (GetGraph()->GetArena()) ReferenceInfo(instruction, pos); 3718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref_info_array_.push_back(ref_info); 3728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return ref_info; 3748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3768ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang void CreateReferenceInfoForReferenceType(HInstruction* instruction) { 3778ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang if (instruction->GetType() != Primitive::kPrimNot) { 3788ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang return; 3798ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang } 3808ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang DCHECK(FindReferenceInfoOf(instruction) == nullptr); 3818ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang GetOrCreateReferenceInfo(instruction); 3828ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang } 3838ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang 3848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* GetOrCreateHeapLocation(HInstruction* ref, 3858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset, 3868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index, 3878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index) { 3888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* original_ref = HuntForOriginalReference(ref); 3898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = GetOrCreateReferenceInfo(original_ref); 3908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t heap_location_idx = FindHeapLocationIndex( 3918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref_info, offset, index, declaring_class_def_index); 3928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_location_idx == kHeapLocationNotFound) { 3938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* heap_loc = new (GetGraph()->GetArena()) 3948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation(ref_info, offset, index, declaring_class_def_index); 3958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_locations_.push_back(heap_loc); 3968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return heap_loc; 3978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return heap_locations_[heap_location_idx]; 3998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 401803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang HeapLocation* VisitFieldAccess(HInstruction* ref, const FieldInfo& field_info) { 4028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (field_info.IsVolatile()) { 4038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_volatile_ = true; 4048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const uint16_t declaring_class_def_index = field_info.GetDeclaringClassDefIndex(); 4068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const size_t offset = field_info.GetFieldOffset().SizeValue(); 407803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang return GetOrCreateHeapLocation(ref, offset, nullptr, declaring_class_def_index); 4088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitArrayAccess(HInstruction* array, HInstruction* index) { 4118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang GetOrCreateHeapLocation(array, HeapLocation::kInvalidFieldOffset, 4128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang index, HeapLocation::kDeclaringClassDefIndexForArrays); 4138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInstanceFieldGet(HInstanceFieldGet* instruction) OVERRIDE { 416fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); 4178ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang CreateReferenceInfoForReferenceType(instruction); 4188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInstanceFieldSet(HInstanceFieldSet* instruction) OVERRIDE { 421803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang HeapLocation* location = VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); 4228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_heap_stores_ = true; 423803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang if (instruction->GetBlock()->GetLoopInformation() != nullptr) { 424803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang location->SetValueKilledByLoopSideEffects(true); 425803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang } 4268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitStaticFieldGet(HStaticFieldGet* instruction) OVERRIDE { 429fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); 4308ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang CreateReferenceInfoForReferenceType(instruction); 4318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitStaticFieldSet(HStaticFieldSet* instruction) OVERRIDE { 434fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); 4358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_heap_stores_ = true; 4368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // We intentionally don't collect HUnresolvedInstanceField/HUnresolvedStaticField accesses 4398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // since we cannot accurately track the fields. 4408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitArrayGet(HArrayGet* instruction) OVERRIDE { 4428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitArrayAccess(instruction->InputAt(0), instruction->InputAt(1)); 4438ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang CreateReferenceInfoForReferenceType(instruction); 4448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitArraySet(HArraySet* instruction) OVERRIDE { 4478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitArrayAccess(instruction->InputAt(0), instruction->InputAt(1)); 4488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_heap_stores_ = true; 4498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitNewInstance(HNewInstance* new_instance) OVERRIDE { 4528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Any references appearing in the ref_info_array_ so far cannot alias with new_instance. 4538ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang CreateReferenceInfoForReferenceType(new_instance); 4548ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang } 4558ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang 4568ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* instruction) OVERRIDE { 4578ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang CreateReferenceInfoForReferenceType(instruction); 4588ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang } 4598ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang 4608ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang void VisitInvokeVirtual(HInvokeVirtual* instruction) OVERRIDE { 4618ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang CreateReferenceInfoForReferenceType(instruction); 4628ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang } 4638ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang 4648ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang void VisitInvokeInterface(HInvokeInterface* instruction) OVERRIDE { 4658ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang CreateReferenceInfoForReferenceType(instruction); 4668ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang } 4678ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang 4688ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang void VisitParameterValue(HParameterValue* instruction) OVERRIDE { 4698ab1d645dfbc84e4b19c0db5e3a0d3081924dc0fMingyao Yang CreateReferenceInfoForReferenceType(instruction); 4708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 47240bcb9356f951af2db4b9b671511841eedf59427Mingyao Yang void VisitSelect(HSelect* instruction) OVERRIDE { 47340bcb9356f951af2db4b9b671511841eedf59427Mingyao Yang CreateReferenceInfoForReferenceType(instruction); 47440bcb9356f951af2db4b9b671511841eedf59427Mingyao Yang } 47540bcb9356f951af2db4b9b671511841eedf59427Mingyao Yang 4768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitDeoptimize(HDeoptimize* instruction ATTRIBUTE_UNUSED) OVERRIDE { 4778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang may_deoptimize_ = true; 4788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitMonitorOperation(HMonitorOperation* monitor ATTRIBUTE_UNUSED) OVERRIDE { 4818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_monitor_operations_ = true; 4828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<ReferenceInfo*> ref_info_array_; // All references used for heap accesses. 4858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HeapLocation*> heap_locations_; // All heap locations. 4868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaBitVector aliasing_matrix_; // aliasing info between each pair of locations. 4878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool has_heap_stores_; // If there is no heap stores, LSE acts as GVN with better 4888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // alias analysis and won't be as effective. 4898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool has_volatile_; // If there are volatile field accesses. 4908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool has_monitor_operations_; // If there are monitor operations. 4918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool may_deoptimize_; 4928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DISALLOW_COPY_AND_ASSIGN(HeapLocationCollector); 4948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang}; 4958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// An unknown heap value. Loads with such a value in the heap location cannot be eliminated. 497fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang// A heap location can be set to kUnknownHeapValue when: 498fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang// - initially set a value. 499fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang// - killed due to aliasing, merging, invocation, or loop side effects. 5008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangstatic HInstruction* const kUnknownHeapValue = 5018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang reinterpret_cast<HInstruction*>(static_cast<uintptr_t>(-1)); 502fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 5038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// Default heap value after an allocation. 504fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang// A heap location can be set to that value right after an allocation. 5058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangstatic HInstruction* const kDefaultHeapValue = 5068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang reinterpret_cast<HInstruction*>(static_cast<uintptr_t>(-2)); 5078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 5088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangclass LSEVisitor : public HGraphVisitor { 5098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang public: 5108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang LSEVisitor(HGraph* graph, 5118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const HeapLocationCollector& heap_locations_collector, 5128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const SideEffectsAnalysis& side_effects) 5138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang : HGraphVisitor(graph), 5148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_location_collector_(heap_locations_collector), 5158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang side_effects_(side_effects), 5168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values_for_(graph->GetBlocks().size(), 5178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>(heap_locations_collector. 5188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang GetNumberOfHeapLocations(), 5198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang kUnknownHeapValue, 5208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang graph->GetArena()->Adapter(kArenaAllocLSE)), 5218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang graph->GetArena()->Adapter(kArenaAllocLSE)), 522fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang removed_loads_(graph->GetArena()->Adapter(kArenaAllocLSE)), 523fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang substitute_instructions_for_loads_(graph->GetArena()->Adapter(kArenaAllocLSE)), 524fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_removed_stores_(graph->GetArena()->Adapter(kArenaAllocLSE)), 5258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang singleton_new_instances_(graph->GetArena()->Adapter(kArenaAllocLSE)) { 5268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 5278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 5288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitBasicBlock(HBasicBlock* block) OVERRIDE { 529fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Populate the heap_values array for this block. 5308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // TODO: try to reuse the heap_values array from one predecessor if possible. 5318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (block->IsLoopHeader()) { 532fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HandleLoopSideEffects(block); 5338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else { 5348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang MergePredecessorValues(block); 5358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 5368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HGraphVisitor::VisitBasicBlock(block); 5378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 5388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 5398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Remove recorded instructions that should be eliminated. 5408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void RemoveInstructions() { 541fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang size_t size = removed_loads_.size(); 542fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK_EQ(size, substitute_instructions_for_loads_.size()); 5438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < size; i++) { 544fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* load = removed_loads_[i]; 545fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(load != nullptr); 546fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(load->IsInstanceFieldGet() || 547fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang load->IsStaticFieldGet() || 548fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang load->IsArrayGet()); 549fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* substitute = substitute_instructions_for_loads_[i]; 550fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(substitute != nullptr); 551fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Keep tracing substitute till one that's not removed. 552fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* sub_sub = FindSubstitute(substitute); 553fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang while (sub_sub != substitute) { 554fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang substitute = sub_sub; 555fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang sub_sub = FindSubstitute(substitute); 5568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 557fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang load->ReplaceWith(substitute); 558fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang load->GetBlock()->RemoveInstruction(load); 5598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 560fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 561fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // At this point, stores in possibly_removed_stores_ can be safely removed. 562fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang size = possibly_removed_stores_.size(); 563fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang for (size_t i = 0; i < size; i++) { 564fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* store = possibly_removed_stores_[i]; 565fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(store->IsInstanceFieldSet() || store->IsStaticFieldSet() || store->IsArraySet()); 566fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang store->GetBlock()->RemoveInstruction(store); 567fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 568fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 5698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // TODO: remove unnecessary allocations. 5708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Eliminate instructions in singleton_new_instances_ that: 5718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // - don't have uses, 5728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // - don't have finalizers, 5738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // - are instantiable and accessible, 5748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // - have no/separate clinit check. 5758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 5768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 5778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang private: 578fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // If heap_values[index] is an instance field store, need to keep the store. 579fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // This is necessary if a heap value is killed due to merging, or loop side 580fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // effects (which is essentially merging also), since a load later from the 581fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // location won't be eliminated. 582fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang void KeepIfIsStore(HInstruction* heap_value) { 583fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (heap_value == kDefaultHeapValue || 584fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_value == kUnknownHeapValue || 585fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang !heap_value->IsInstanceFieldSet()) { 586fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang return; 587fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 588fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang auto idx = std::find(possibly_removed_stores_.begin(), 589fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_removed_stores_.end(), heap_value); 590fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (idx != possibly_removed_stores_.end()) { 591fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Make sure the store is kept. 592fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_removed_stores_.erase(idx); 593fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 594fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 595fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 596fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang void HandleLoopSideEffects(HBasicBlock* block) { 597fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(block->IsLoopHeader()); 598fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang int block_id = block->GetBlockId(); 599fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*>& heap_values = heap_values_for_[block_id]; 60015bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray 60115bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // Don't eliminate loads in irreducible loops. This is safe for singletons, because 60215bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // they are always used by the non-eliminated loop-phi. 60315bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray if (block->GetLoopInformation()->IsIrreducible()) { 60415bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray if (kIsDebugBuild) { 60515bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray for (size_t i = 0; i < heap_values.size(); i++) { 60615bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray DCHECK_EQ(heap_values[i], kUnknownHeapValue); 60715bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray } 60815bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray } 60915bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray return; 61015bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray } 61115bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray 612fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader(); 613fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*>& pre_header_heap_values = 614fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_values_for_[pre_header->GetBlockId()]; 61515bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray 616803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // Inherit the values from pre-header. 617803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 618803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang heap_values[i] = pre_header_heap_values[i]; 619803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang } 620803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang 621fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // We do a single pass in reverse post order. For loops, use the side effects as a hint 622fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // to see if the heap values should be killed. 623fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (side_effects_.GetLoopEffects(block).DoesAnyWrite()) { 624fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 625803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang HeapLocation* location = heap_location_collector_.GetHeapLocation(i); 626803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang ReferenceInfo* ref_info = location->GetReferenceInfo(); 627803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang if (!ref_info->IsSingleton() || location->IsValueKilledByLoopSideEffects()) { 628803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // heap value is killed by loop side effects (stored into directly, or due to 629803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // aliasing). 630803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang KeepIfIsStore(pre_header_heap_values[i]); 631803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang heap_values[i] = kUnknownHeapValue; 632803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang } else { 633803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // A singleton's field that's not stored into inside a loop is invariant throughout 634803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // the loop. 635803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang } 636fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 637fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 638fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 639fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 6408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void MergePredecessorValues(HBasicBlock* block) { 6418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const ArenaVector<HBasicBlock*>& predecessors = block->GetPredecessors(); 6428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (predecessors.size() == 0) { 6438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 6448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>& heap_values = heap_values_for_[block->GetBlockId()]; 6468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 647fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* pred0_value = heap_values_for_[predecessors[0]->GetBlockId()][i]; 648fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_values[i] = pred0_value; 649fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (pred0_value != kUnknownHeapValue) { 6508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t j = 1; j < predecessors.size(); j++) { 651fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* pred_value = heap_values_for_[predecessors[j]->GetBlockId()][i]; 652fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (pred_value != pred0_value) { 653fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_values[i] = kUnknownHeapValue; 6548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang break; 6558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 658fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 659fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (heap_values[i] == kUnknownHeapValue) { 660fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Keep the last store in each predecessor since future loads cannot be eliminated. 661fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang for (size_t j = 0; j < predecessors.size(); j++) { 662fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*>& pred_values = heap_values_for_[predecessors[j]->GetBlockId()]; 663fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang KeepIfIsStore(pred_values[i]); 664fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 665fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 6668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 6698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // `instruction` is being removed. Try to see if the null check on it 6708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // can be removed. This can happen if the same value is set in two branches 6718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // but not in dominators. Such as: 6728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // int[] a = foo(); 6738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // if () { 6748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // a[0] = 2; 6758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // } else { 6768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // a[0] = 2; 6778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // } 6788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // // a[0] can now be replaced with constant 2, and the null check on it can be removed. 6798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void TryRemovingNullCheck(HInstruction* instruction) { 6808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* prev = instruction->GetPrevious(); 6818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if ((prev != nullptr) && prev->IsNullCheck() && (prev == instruction->InputAt(0))) { 6828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Previous instruction is a null check for this instruction. Remove the null check. 6838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang prev->ReplaceWith(prev->InputAt(0)); 6848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang prev->GetBlock()->RemoveInstruction(prev); 6858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 6888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* GetDefaultValue(Primitive::Type type) { 6898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang switch (type) { 6908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimNot: 6918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return GetGraph()->GetNullConstant(); 6928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimBoolean: 6938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimByte: 6948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimChar: 6958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimShort: 6968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimInt: 6978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return GetGraph()->GetIntConstant(0); 6988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimLong: 6998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return GetGraph()->GetLongConstant(0); 7008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimFloat: 7018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return GetGraph()->GetFloatConstant(0); 7028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimDouble: 7038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return GetGraph()->GetDoubleConstant(0); 7048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang default: 7058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang UNREACHABLE(); 7068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 7098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitGetLocation(HInstruction* instruction, 7108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* ref, 7118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset, 7128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index, 7138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index) { 7148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* original_ref = HuntForOriginalReference(ref); 7158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref); 7168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t idx = heap_location_collector_.FindHeapLocationIndex( 7178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref_info, offset, index, declaring_class_def_index); 7188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); 7198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>& heap_values = 7208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values_for_[instruction->GetBlock()->GetBlockId()]; 7218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* heap_value = heap_values[idx]; 7228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_value == kDefaultHeapValue) { 7238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* constant = GetDefaultValue(instruction->GetType()); 724fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang removed_loads_.push_back(instruction); 725fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang substitute_instructions_for_loads_.push_back(constant); 7268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values[idx] = constant; 7278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 7288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 729fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (heap_value != kUnknownHeapValue && heap_value->IsInstanceFieldSet()) { 730fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* store = heap_value; 731fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // This load must be from a singleton since it's from the same field 732fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // that a "removed" store puts the value. That store must be to a singleton's field. 733fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(ref_info->IsSingleton()); 734fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Get the real heap value of the store. 735fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_value = store->InputAt(1); 736fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 7378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_value == kUnknownHeapValue) { 73815693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // Load isn't eliminated. Put the load as the value into the HeapLocation. 7398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // This acts like GVN but with better aliasing analysis. 7408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values[idx] = instruction; 74115693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil } else { 7420397163516fb882589c5be734439dedfe4d271fbNicolas Geoffray if (Primitive::PrimitiveKind(heap_value->GetType()) 7430397163516fb882589c5be734439dedfe4d271fbNicolas Geoffray != Primitive::PrimitiveKind(instruction->GetType())) { 7440397163516fb882589c5be734439dedfe4d271fbNicolas Geoffray // The only situation where the same heap location has different type is when 745bb2c93b8d833db3b872fe7130712d73260c5503fNicolas Geoffray // we do an array get on an instruction that originates from the null constant 746bb2c93b8d833db3b872fe7130712d73260c5503fNicolas Geoffray // (the null could be behind a field access, an array access, a null check or 747bb2c93b8d833db3b872fe7130712d73260c5503fNicolas Geoffray // a bound type). 748bb2c93b8d833db3b872fe7130712d73260c5503fNicolas Geoffray // In order to stay properly typed on primitive types, we do not eliminate 749bb2c93b8d833db3b872fe7130712d73260c5503fNicolas Geoffray // the array gets. 7500397163516fb882589c5be734439dedfe4d271fbNicolas Geoffray if (kIsDebugBuild) { 7510397163516fb882589c5be734439dedfe4d271fbNicolas Geoffray DCHECK(heap_value->IsArrayGet()) << heap_value->DebugName(); 7520397163516fb882589c5be734439dedfe4d271fbNicolas Geoffray DCHECK(instruction->IsArrayGet()) << instruction->DebugName(); 7530397163516fb882589c5be734439dedfe4d271fbNicolas Geoffray } 7540397163516fb882589c5be734439dedfe4d271fbNicolas Geoffray return; 7550397163516fb882589c5be734439dedfe4d271fbNicolas Geoffray } 75615693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil removed_loads_.push_back(instruction); 75715693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil substitute_instructions_for_loads_.push_back(heap_value); 75815693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil TryRemovingNullCheck(instruction); 7598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 7628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool Equal(HInstruction* heap_value, HInstruction* value) { 7638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_value == value) { 7648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 7658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_value == kDefaultHeapValue && GetDefaultValue(value->GetType()) == value) { 7678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 7688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 7708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 7728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitSetLocation(HInstruction* instruction, 7738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* ref, 7748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset, 7758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index, 7768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index, 7778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* value) { 7788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* original_ref = HuntForOriginalReference(ref); 7798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref); 7808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t idx = heap_location_collector_.FindHeapLocationIndex( 7818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref_info, offset, index, declaring_class_def_index); 7828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); 7838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>& heap_values = 7848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values_for_[instruction->GetBlock()->GetBlockId()]; 7858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* heap_value = heap_values[idx]; 786fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang bool same_value = false; 787fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang bool possibly_redundant = false; 7888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (Equal(heap_value, value)) { 7898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Store into the heap location with the same value. 790fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang same_value = true; 7918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (index != nullptr) { 7928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // For array element, don't eliminate stores since it can be easily aliased 7938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // with non-constant index. 7948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (!heap_location_collector_.MayDeoptimize() && 795fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ref_info->IsSingletonAndNotReturned()) { 796fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Store into a field of a singleton that's not returned. The value cannot be 797fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // killed due to aliasing/invocation. It can be redundant since future loads can 798fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // directly get the value set by this instruction. The value can still be killed due to 799fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // merging or loop side effects. Stores whose values are killed due to merging/loop side 800fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // effects later will be removed from possibly_removed_stores_ when that is detected. 801fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_redundant = true; 802fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HNewInstance* new_instance = ref_info->GetReference()->AsNewInstance(); 803fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(new_instance != nullptr); 804fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (new_instance->IsFinalizable()) { 805fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Finalizable objects escape globally. Need to keep the store. 806fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_redundant = false; 8078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else { 808fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HLoopInformation* loop_info = instruction->GetBlock()->GetLoopInformation(); 809fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (loop_info != nullptr) { 810fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // instruction is a store in the loop so the loop must does write. 811fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(side_effects_.GetLoopEffects(loop_info->GetHeader()).DoesAnyWrite()); 812803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang // If it's a singleton, IsValueKilledByLoopSideEffects() must be true. 813803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang DCHECK(!ref_info->IsSingleton() || 814803cbb9c9319af10b01317abb849303fb8329fb7Mingyao Yang heap_location_collector_.GetHeapLocation(idx)->IsValueKilledByLoopSideEffects()); 815fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 8164b467ed97bc5886fb800209c0ee94df10163b88dMingyao Yang if (loop_info->IsDefinedOutOfTheLoop(original_ref)) { 817fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(original_ref->GetBlock()->Dominates(loop_info->GetPreHeader())); 818fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Keep the store since its value may be needed at the loop header. 819fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_redundant = false; 820fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } else { 821fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // The singleton is created inside the loop. Value stored to it isn't needed at 822fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // the loop header. This is true for outer loops also. 823fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 824fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 8258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 827fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (same_value || possibly_redundant) { 828fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_removed_stores_.push_back(instruction); 8298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 830e9d6e6083e845194548e0705fdf9e172c7a043e5Mingyao Yang 831fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (!same_value) { 832fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (possibly_redundant) { 833fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(instruction->IsInstanceFieldSet()); 834fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Put the store as the heap value. If the value is loaded from heap 835fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // by a load later, this store isn't really redundant. 836fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_values[idx] = instruction; 837fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } else { 838fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_values[idx] = value; 839fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 840fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 8418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // This store may kill values in other heap locations due to aliasing. 8428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 843fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (i == idx) { 844fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang continue; 845fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 8468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_values[i] == value) { 8478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Same value should be kept even if aliasing happens. 8488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang continue; 8498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_values[i] == kUnknownHeapValue) { 8518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Value is already unknown, no need for aliasing check. 8528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang continue; 8538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_location_collector_.MayAlias(i, idx)) { 8558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Kill heap locations that may alias. 8568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values[i] = kUnknownHeapValue; 8578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInstanceFieldGet(HInstanceFieldGet* instruction) OVERRIDE { 8628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* obj = instruction->InputAt(0); 8638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); 8648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); 8658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitGetLocation(instruction, obj, offset, nullptr, declaring_class_def_index); 8668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInstanceFieldSet(HInstanceFieldSet* instruction) OVERRIDE { 8698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* obj = instruction->InputAt(0); 8708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); 8718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); 8728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* value = instruction->InputAt(1); 8738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitSetLocation(instruction, obj, offset, nullptr, declaring_class_def_index, value); 8748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitStaticFieldGet(HStaticFieldGet* instruction) OVERRIDE { 8778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* cls = instruction->InputAt(0); 8788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); 8798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); 8808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitGetLocation(instruction, cls, offset, nullptr, declaring_class_def_index); 8818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitStaticFieldSet(HStaticFieldSet* instruction) OVERRIDE { 8848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* cls = instruction->InputAt(0); 8858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); 8868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); 8878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* value = instruction->InputAt(1); 8888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitSetLocation(instruction, cls, offset, nullptr, declaring_class_def_index, value); 8898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitArrayGet(HArrayGet* instruction) OVERRIDE { 8928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* array = instruction->InputAt(0); 8938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index = instruction->InputAt(1); 8948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitGetLocation(instruction, 8958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang array, 8968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation::kInvalidFieldOffset, 8978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang index, 8988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation::kDeclaringClassDefIndexForArrays); 8998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitArraySet(HArraySet* instruction) OVERRIDE { 9028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* array = instruction->InputAt(0); 9038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index = instruction->InputAt(1); 9048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* value = instruction->InputAt(2); 9058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitSetLocation(instruction, 9068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang array, 9078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation::kInvalidFieldOffset, 9088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang index, 9098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation::kDeclaringClassDefIndexForArrays, 9108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang value); 9118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void HandleInvoke(HInstruction* invoke) { 9148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>& heap_values = 9158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values_for_[invoke->GetBlock()->GetBlockId()]; 9168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 9178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo(); 9188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info->IsSingleton()) { 9198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Singleton references cannot be seen by the callee. 9208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else { 9218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values[i] = kUnknownHeapValue; 9228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) OVERRIDE { 9278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(invoke); 9288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInvokeVirtual(HInvokeVirtual* invoke) OVERRIDE { 9318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(invoke); 9328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInvokeInterface(HInvokeInterface* invoke) OVERRIDE { 9358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(invoke); 9368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInvokeUnresolved(HInvokeUnresolved* invoke) OVERRIDE { 9398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(invoke); 9408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitClinitCheck(HClinitCheck* clinit) OVERRIDE { 9438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(clinit); 9448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitUnresolvedInstanceFieldGet(HUnresolvedInstanceFieldGet* instruction) OVERRIDE { 9478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Conservatively treat it as an invocation. 9488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(instruction); 9498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitUnresolvedInstanceFieldSet(HUnresolvedInstanceFieldSet* instruction) OVERRIDE { 9528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Conservatively treat it as an invocation. 9538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(instruction); 9548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitUnresolvedStaticFieldGet(HUnresolvedStaticFieldGet* instruction) OVERRIDE { 9578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Conservatively treat it as an invocation. 9588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(instruction); 9598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitUnresolvedStaticFieldSet(HUnresolvedStaticFieldSet* instruction) OVERRIDE { 9628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Conservatively treat it as an invocation. 9638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(instruction); 9648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitNewInstance(HNewInstance* new_instance) OVERRIDE { 9678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(new_instance); 9688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info == nullptr) { 9698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // new_instance isn't used for field accesses. No need to process it. 9708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 9718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (!heap_location_collector_.MayDeoptimize() && 973fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ref_info->IsSingletonAndNotReturned() && 974fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang !new_instance->IsFinalizable() && 975fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang !new_instance->CanThrow()) { 976fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // TODO: add new_instance to singleton_new_instances_ and enable allocation elimination. 9778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>& heap_values = 9798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values_for_[new_instance->GetBlock()->GetBlockId()]; 9808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 9818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* ref = 9828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo()->GetReference(); 9838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset = heap_location_collector_.GetHeapLocation(i)->GetOffset(); 9848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref == new_instance && offset >= mirror::kObjectHeaderSize) { 9858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Instance fields except the header fields are set to default heap values. 9868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values[i] = kDefaultHeapValue; 9878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Find an instruction's substitute if it should be removed. 9928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Return the same instruction if it should not be removed. 9938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* FindSubstitute(HInstruction* instruction) { 994fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang size_t size = removed_loads_.size(); 9958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < size; i++) { 996fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (removed_loads_[i] == instruction) { 997fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang return substitute_instructions_for_loads_[i]; 9988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 10008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return instruction; 10018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 10028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 10038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const HeapLocationCollector& heap_location_collector_; 10048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const SideEffectsAnalysis& side_effects_; 10058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 10068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // One array of heap values for each block. 10078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<ArenaVector<HInstruction*>> heap_values_for_; 10088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 10098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // We record the instructions that should be eliminated but may be 10108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // used by heap locations. They'll be removed in the end. 1011fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*> removed_loads_; 1012fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*> substitute_instructions_for_loads_; 1013fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 1014fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Stores in this list may be removed from the list later when it's 1015fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // found that the store cannot be eliminated. 1016fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*> possibly_removed_stores_; 1017fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 10188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*> singleton_new_instances_; 10198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 10208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DISALLOW_COPY_AND_ASSIGN(LSEVisitor); 10218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang}; 10228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 10238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangvoid LoadStoreElimination::Run() { 10248993caf6571863c8e5eec0b2ce4d72f6f1793f31David Brazdil if (graph_->IsDebuggable() || graph_->HasTryCatch()) { 10258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Debugger may set heap values or trigger deoptimization of callers. 10268993caf6571863c8e5eec0b2ce4d72f6f1793f31David Brazdil // Try/catch support not implemented yet. 10278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Skip this optimization. 10288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 10298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 10308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocationCollector heap_location_collector(graph_); 10318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 10328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_location_collector.VisitBasicBlock(it.Current()); 10338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 10348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_location_collector.GetNumberOfHeapLocations() > kMaxNumberOfHeapLocations) { 10358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Bail out if there are too many heap locations to deal with. 10368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 10378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 10388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (!heap_location_collector.HasHeapStores()) { 10398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Without heap stores, this pass would act mostly as GVN on heap accesses. 10408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 10418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 10428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_location_collector.HasVolatile() || heap_location_collector.HasMonitorOps()) { 10438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Don't do load/store elimination if the method has volatile field accesses or 10448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // monitor operations, for now. 10458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // TODO: do it right. 10468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 10478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 10488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_location_collector.BuildAliasingMatrix(); 10498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang LSEVisitor lse_visitor(graph_, heap_location_collector, side_effects_); 10508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 10518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang lse_visitor.VisitBasicBlock(it.Current()); 10528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 10538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang lse_visitor.RemoveInstructions(); 10548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang} 10558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 10568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang} // namespace art 1057