load_store_elimination.cc revision 4b467ed97bc5886fb800209c0ee94df10163b88d
18df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang/* 28df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * Copyright (C) 2015 The Android Open Source Project 38df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * 48df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * Licensed under the Apache License, Version 2.0 (the "License"); 58df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * you may not use this file except in compliance with the License. 68df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * You may obtain a copy of the License at 78df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * 88df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * http://www.apache.org/licenses/LICENSE-2.0 98df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * 108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * Unless required by applicable law or agreed to in writing, software 118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * distributed under the License is distributed on an "AS IS" BASIS, 128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * See the License for the specific language governing permissions and 148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang * limitations under the License. 158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang */ 168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang#include "load_store_elimination.h" 188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang#include "side_effects_analysis.h" 198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang#include <iostream> 218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangnamespace art { 238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangclass ReferenceInfo; 258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// A cap for the number of heap locations to prevent pathological time/space consumption. 278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// The number of heap locations for most of the methods stays below this threshold. 288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangconstexpr size_t kMaxNumberOfHeapLocations = 32; 298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// A ReferenceInfo contains additional info about a reference such as 318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// whether it's a singleton, returned, etc. 328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangclass ReferenceInfo : public ArenaObject<kArenaAllocMisc> { 338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang public: 348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo(HInstruction* reference, size_t pos) : reference_(reference), position_(pos) { 358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_ = true; 368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_and_not_returned_ = true; 378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (!reference_->IsNewInstance() && !reference_->IsNewArray()) { 388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // For references not allocated in the method, don't assume anything. 398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_ = false; 408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_and_not_returned_ = false; 418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Visit all uses to determine if this reference can spread into the heap, 458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // a method call, etc. 468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (HUseIterator<HInstruction*> use_it(reference_->GetUses()); 478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang !use_it.Done(); 488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang use_it.Advance()) { 498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* use = use_it.Current()->GetUser(); 508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(!use->IsNullCheck()) << "NullCheck should have been eliminated"; 518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (use->IsBoundType()) { 528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // BoundType shouldn't normally be necessary for a NewInstance. 538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Just be conservative for the uncommon cases. 548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_ = false; 558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_and_not_returned_ = false; 568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (use->IsPhi() || use->IsInvoke() || 598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang (use->IsInstanceFieldSet() && (reference_ == use->InputAt(1))) || 608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang (use->IsUnresolvedInstanceFieldSet() && (reference_ == use->InputAt(1))) || 618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang (use->IsStaticFieldSet() && (reference_ == use->InputAt(1))) || 62d930929be93798d790c91dd05adf2c038508f1b0Nicolas Geoffray (use->IsUnresolvedStaticFieldSet() && (reference_ == use->InputAt(0))) || 638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang (use->IsArraySet() && (reference_ == use->InputAt(2)))) { 648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // reference_ is merged to a phi, passed to a callee, or stored to heap. 658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // reference_ isn't the only name that can refer to its value anymore. 668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_ = false; 678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_and_not_returned_ = false; 688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (use->IsReturn()) { 718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang is_singleton_and_not_returned_ = false; 728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* GetReference() const { 778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return reference_; 788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t GetPosition() const { 818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return position_; 828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns true if reference_ is the only name that can refer to its value during 858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // the lifetime of the method. So it's guaranteed to not have any alias in 868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // the method (including its callees). 878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool IsSingleton() const { 888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return is_singleton_; 898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns true if reference_ is a singleton and not returned to the caller. 928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // The allocation and stores into reference_ may be eliminated for such cases. 938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool IsSingletonAndNotReturned() const { 948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return is_singleton_and_not_returned_; 958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang private: 988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* const reference_; 998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const size_t position_; // position in HeapLocationCollector's ref_info_array_. 1008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool is_singleton_; // can only be referred to by a single name in the method. 1018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool is_singleton_and_not_returned_; // reference_ is singleton and not returned to caller. 1028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DISALLOW_COPY_AND_ASSIGN(ReferenceInfo); 1048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang}; 1058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// A heap location is a reference-offset/index pair that a value can be loaded from 1078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// or stored to. 1088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangclass HeapLocation : public ArenaObject<kArenaAllocMisc> { 1098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang public: 1108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang static constexpr size_t kInvalidFieldOffset = -1; 1118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // TODO: more fine-grained array types. 1138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang static constexpr int16_t kDeclaringClassDefIndexForArrays = -1; 1148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation(ReferenceInfo* ref_info, 1168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset, 1178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index, 1188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index) 1198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang : ref_info_(ref_info), 1208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang offset_(offset), 1218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang index_(index), 122fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang declaring_class_def_index_(declaring_class_def_index) { 1238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(ref_info != nullptr); 1248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK((offset == kInvalidFieldOffset && index != nullptr) || 1258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang (offset != kInvalidFieldOffset && index == nullptr)); 1268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* GetReferenceInfo() const { return ref_info_; } 1298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t GetOffset() const { return offset_; } 1308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* GetIndex() const { return index_; } 1318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns the definition of declaring class' dex index. 1338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // It's kDeclaringClassDefIndexForArrays for an array element. 1348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t GetDeclaringClassDefIndex() const { 1358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return declaring_class_def_index_; 1368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool IsArrayElement() const { 1398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return index_ != nullptr; 1408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang private: 1438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* const ref_info_; // reference for instance/static field or array access. 1448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const size_t offset_; // offset of static/instance field. 1458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* const index_; // index of an array element. 1468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const int16_t declaring_class_def_index_; // declaring class's def's dex index. 1478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DISALLOW_COPY_AND_ASSIGN(HeapLocation); 1498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang}; 1508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangstatic HInstruction* HuntForOriginalReference(HInstruction* ref) { 1528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(ref != nullptr); 1538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang while (ref->IsNullCheck() || ref->IsBoundType()) { 1548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref = ref->InputAt(0); 1558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return ref; 1578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang} 1588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// A HeapLocationCollector collects all relevant heap locations and keeps 1608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// an aliasing matrix for all locations. 1618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangclass HeapLocationCollector : public HGraphVisitor { 1628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang public: 1638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang static constexpr size_t kHeapLocationNotFound = -1; 1648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Start with a single uint32_t word. That's enough bits for pair-wise 1658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // aliasing matrix of 8 heap locations. 1668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang static constexpr uint32_t kInitialAliasingMatrixBitVectorSize = 32; 1678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang explicit HeapLocationCollector(HGraph* graph) 1698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang : HGraphVisitor(graph), 1708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref_info_array_(graph->GetArena()->Adapter(kArenaAllocLSE)), 1718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_locations_(graph->GetArena()->Adapter(kArenaAllocLSE)), 1728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang aliasing_matrix_(graph->GetArena(), kInitialAliasingMatrixBitVectorSize, true), 1738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_heap_stores_(false), 1748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_volatile_(false), 1758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_monitor_operations_(false), 1768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang may_deoptimize_(false) {} 1778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t GetNumberOfHeapLocations() const { 1798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return heap_locations_.size(); 1808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* GetHeapLocation(size_t index) const { 1838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return heap_locations_[index]; 1848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* FindReferenceInfoOf(HInstruction* ref) const { 1878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < ref_info_array_.size(); i++) { 1888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = ref_info_array_[i]; 1898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info->GetReference() == ref) { 1908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK_EQ(i, ref_info->GetPosition()); 1918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return ref_info; 1928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return nullptr; 1958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 1968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 1978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool HasHeapStores() const { 1988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return has_heap_stores_; 1998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool HasVolatile() const { 2028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return has_volatile_; 2038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool HasMonitorOps() const { 2068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return has_monitor_operations_; 2078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns whether this method may be deoptimized. 2108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Currently we don't have meta data support for deoptimizing 2118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // a method that eliminates allocations/stores. 2128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool MayDeoptimize() const { 2138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return may_deoptimize_; 2148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Find and return the heap location index in heap_locations_. 2178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t FindHeapLocationIndex(ReferenceInfo* ref_info, 2188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset, 2198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index, 2208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index) const { 2218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < heap_locations_.size(); i++) { 2228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* loc = heap_locations_[i]; 2238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (loc->GetReferenceInfo() == ref_info && 2248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang loc->GetOffset() == offset && 2258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang loc->GetIndex() == index && 2268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang loc->GetDeclaringClassDefIndex() == declaring_class_def_index) { 2278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return i; 2288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return kHeapLocationNotFound; 2318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns true if heap_locations_[index1] and heap_locations_[index2] may alias. 2348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool MayAlias(size_t index1, size_t index2) const { 2358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (index1 < index2) { 2368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return aliasing_matrix_.IsBitSet(AliasingMatrixPosition(index1, index2)); 2378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (index1 > index2) { 2388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return aliasing_matrix_.IsBitSet(AliasingMatrixPosition(index2, index1)); 2398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else { 2408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(false) << "index1 and index2 are expected to be different"; 2418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 2428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void BuildAliasingMatrix() { 2468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const size_t number_of_locations = heap_locations_.size(); 2478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (number_of_locations == 0) { 2488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 2498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t pos = 0; 2518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Compute aliasing info between every pair of different heap locations. 2528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Save the result in a matrix represented as a BitVector. 2538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < number_of_locations - 1; i++) { 2548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t j = i + 1; j < number_of_locations; j++) { 2558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ComputeMayAlias(i, j)) { 2568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang aliasing_matrix_.SetBit(CheckedAliasingMatrixPosition(i, j, pos)); 2578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang pos++; 2598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang private: 2648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // An allocation cannot alias with a name which already exists at the point 2658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // of the allocation, such as a parameter or a load happening before the allocation. 2668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool MayAliasWithPreexistenceChecking(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) const { 2678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info1->GetReference()->IsNewInstance() || ref_info1->GetReference()->IsNewArray()) { 2688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Any reference that can alias with the allocation must appear after it in the block/in 2698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // the block's successors. In reverse post order, those instructions will be visited after 2708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // the allocation. 2718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return ref_info2->GetPosition() >= ref_info1->GetPosition(); 2728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 2748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool CanReferencesAlias(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) const { 2778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info1 == ref_info2) { 2788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 2798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (ref_info1->IsSingleton()) { 2808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 2818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (ref_info2->IsSingleton()) { 2828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 2838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (!MayAliasWithPreexistenceChecking(ref_info1, ref_info2) || 2848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang !MayAliasWithPreexistenceChecking(ref_info2, ref_info1)) { 2858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 2868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 2888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 2908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // `index1` and `index2` are indices in the array of collected heap locations. 2918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Returns the position in the bit vector that tracks whether the two heap 2928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // locations may alias. 2938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t AliasingMatrixPosition(size_t index1, size_t index2) const { 2948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(index2 > index1); 2958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const size_t number_of_locations = heap_locations_.size(); 2968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // It's (num_of_locations - 1) + ... + (num_of_locations - index1) + (index2 - index1 - 1). 2978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return (number_of_locations * index1 - (1 + index1) * index1 / 2 + (index2 - index1 - 1)); 2988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 2998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // An additional position is passed in to make sure the calculated position is correct. 3018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t CheckedAliasingMatrixPosition(size_t index1, size_t index2, size_t position) { 3028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t calculated_position = AliasingMatrixPosition(index1, index2); 3038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK_EQ(calculated_position, position); 3048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return calculated_position; 3058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Compute if two locations may alias to each other. 3088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool ComputeMayAlias(size_t index1, size_t index2) const { 3098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* loc1 = heap_locations_[index1]; 3108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* loc2 = heap_locations_[index2]; 3118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (loc1->GetOffset() != loc2->GetOffset()) { 3128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Either two different instance fields, or one is an instance 3138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // field and the other is an array element. 3148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (loc1->GetDeclaringClassDefIndex() != loc2->GetDeclaringClassDefIndex()) { 3178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Different types. 3188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (!CanReferencesAlias(loc1->GetReferenceInfo(), loc2->GetReferenceInfo())) { 3218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (loc1->IsArrayElement() && loc2->IsArrayElement()) { 3248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* array_index1 = loc1->GetIndex(); 3258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* array_index2 = loc2->GetIndex(); 3268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(array_index1 != nullptr); 3278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK(array_index2 != nullptr); 3288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (array_index1->IsIntConstant() && 3298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang array_index2->IsIntConstant() && 3308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang array_index1->AsIntConstant()->GetValue() != array_index2->AsIntConstant()->GetValue()) { 3318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Different constant indices do not alias. 3328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 3338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 3368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* GetOrCreateReferenceInfo(HInstruction* ref) { 3398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = FindReferenceInfoOf(ref); 3408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info == nullptr) { 3418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t pos = ref_info_array_.size(); 3428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref_info = new (GetGraph()->GetArena()) ReferenceInfo(ref, pos); 3438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref_info_array_.push_back(ref_info); 3448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return ref_info; 3468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* GetOrCreateHeapLocation(HInstruction* ref, 3498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset, 3508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index, 3518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index) { 3528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* original_ref = HuntForOriginalReference(ref); 3538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = GetOrCreateReferenceInfo(original_ref); 3548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t heap_location_idx = FindHeapLocationIndex( 3558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref_info, offset, index, declaring_class_def_index); 3568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_location_idx == kHeapLocationNotFound) { 3578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation* heap_loc = new (GetGraph()->GetArena()) 3588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation(ref_info, offset, index, declaring_class_def_index); 3598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_locations_.push_back(heap_loc); 3608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return heap_loc; 3618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return heap_locations_[heap_location_idx]; 3638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 365fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang void VisitFieldAccess(HInstruction* ref, const FieldInfo& field_info) { 3668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (field_info.IsVolatile()) { 3678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_volatile_ = true; 3688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const uint16_t declaring_class_def_index = field_info.GetDeclaringClassDefIndex(); 3708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const size_t offset = field_info.GetFieldOffset().SizeValue(); 371fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang GetOrCreateHeapLocation(ref, offset, nullptr, declaring_class_def_index); 3728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitArrayAccess(HInstruction* array, HInstruction* index) { 3758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang GetOrCreateHeapLocation(array, HeapLocation::kInvalidFieldOffset, 3768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang index, HeapLocation::kDeclaringClassDefIndexForArrays); 3778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInstanceFieldGet(HInstanceFieldGet* instruction) OVERRIDE { 380fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); 3818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInstanceFieldSet(HInstanceFieldSet* instruction) OVERRIDE { 384fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); 3858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_heap_stores_ = true; 3868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitStaticFieldGet(HStaticFieldGet* instruction) OVERRIDE { 389fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); 3908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitStaticFieldSet(HStaticFieldSet* instruction) OVERRIDE { 393fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); 3948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_heap_stores_ = true; 3958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 3968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 3978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // We intentionally don't collect HUnresolvedInstanceField/HUnresolvedStaticField accesses 3988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // since we cannot accurately track the fields. 3998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitArrayGet(HArrayGet* instruction) OVERRIDE { 4018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitArrayAccess(instruction->InputAt(0), instruction->InputAt(1)); 4028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitArraySet(HArraySet* instruction) OVERRIDE { 4058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitArrayAccess(instruction->InputAt(0), instruction->InputAt(1)); 4068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_heap_stores_ = true; 4078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitNewInstance(HNewInstance* new_instance) OVERRIDE { 4108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Any references appearing in the ref_info_array_ so far cannot alias with new_instance. 4118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang GetOrCreateReferenceInfo(new_instance); 4128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitDeoptimize(HDeoptimize* instruction ATTRIBUTE_UNUSED) OVERRIDE { 4158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang may_deoptimize_ = true; 4168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitMonitorOperation(HMonitorOperation* monitor ATTRIBUTE_UNUSED) OVERRIDE { 4198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang has_monitor_operations_ = true; 4208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<ReferenceInfo*> ref_info_array_; // All references used for heap accesses. 4238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HeapLocation*> heap_locations_; // All heap locations. 4248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaBitVector aliasing_matrix_; // aliasing info between each pair of locations. 4258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool has_heap_stores_; // If there is no heap stores, LSE acts as GVN with better 4268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // alias analysis and won't be as effective. 4278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool has_volatile_; // If there are volatile field accesses. 4288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool has_monitor_operations_; // If there are monitor operations. 4298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool may_deoptimize_; 4308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DISALLOW_COPY_AND_ASSIGN(HeapLocationCollector); 4328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang}; 4338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// An unknown heap value. Loads with such a value in the heap location cannot be eliminated. 435fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang// A heap location can be set to kUnknownHeapValue when: 436fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang// - initially set a value. 437fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang// - killed due to aliasing, merging, invocation, or loop side effects. 4388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangstatic HInstruction* const kUnknownHeapValue = 4398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang reinterpret_cast<HInstruction*>(static_cast<uintptr_t>(-1)); 440fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 4418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang// Default heap value after an allocation. 442fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang// A heap location can be set to that value right after an allocation. 4438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangstatic HInstruction* const kDefaultHeapValue = 4448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang reinterpret_cast<HInstruction*>(static_cast<uintptr_t>(-2)); 4458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangclass LSEVisitor : public HGraphVisitor { 4478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang public: 4488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang LSEVisitor(HGraph* graph, 4498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const HeapLocationCollector& heap_locations_collector, 4508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const SideEffectsAnalysis& side_effects) 4518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang : HGraphVisitor(graph), 4528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_location_collector_(heap_locations_collector), 4538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang side_effects_(side_effects), 4548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values_for_(graph->GetBlocks().size(), 4558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>(heap_locations_collector. 4568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang GetNumberOfHeapLocations(), 4578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang kUnknownHeapValue, 4588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang graph->GetArena()->Adapter(kArenaAllocLSE)), 4598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang graph->GetArena()->Adapter(kArenaAllocLSE)), 460fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang removed_loads_(graph->GetArena()->Adapter(kArenaAllocLSE)), 461fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang substitute_instructions_for_loads_(graph->GetArena()->Adapter(kArenaAllocLSE)), 462fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_removed_stores_(graph->GetArena()->Adapter(kArenaAllocLSE)), 4638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang singleton_new_instances_(graph->GetArena()->Adapter(kArenaAllocLSE)) { 4648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitBasicBlock(HBasicBlock* block) OVERRIDE { 467fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Populate the heap_values array for this block. 4688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // TODO: try to reuse the heap_values array from one predecessor if possible. 4698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (block->IsLoopHeader()) { 470fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HandleLoopSideEffects(block); 4718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else { 4728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang MergePredecessorValues(block); 4738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HGraphVisitor::VisitBasicBlock(block); 4758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 4768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 4778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Remove recorded instructions that should be eliminated. 4788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void RemoveInstructions() { 479fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang size_t size = removed_loads_.size(); 480fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK_EQ(size, substitute_instructions_for_loads_.size()); 4818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < size; i++) { 482fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* load = removed_loads_[i]; 483fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(load != nullptr); 484fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(load->IsInstanceFieldGet() || 485fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang load->IsStaticFieldGet() || 486fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang load->IsArrayGet()); 487fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* substitute = substitute_instructions_for_loads_[i]; 488fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(substitute != nullptr); 489fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Keep tracing substitute till one that's not removed. 490fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* sub_sub = FindSubstitute(substitute); 491fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang while (sub_sub != substitute) { 492fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang substitute = sub_sub; 493fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang sub_sub = FindSubstitute(substitute); 4948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 495fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang load->ReplaceWith(substitute); 496fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang load->GetBlock()->RemoveInstruction(load); 4978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 498fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 499fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // At this point, stores in possibly_removed_stores_ can be safely removed. 500fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang size = possibly_removed_stores_.size(); 501fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang for (size_t i = 0; i < size; i++) { 502fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* store = possibly_removed_stores_[i]; 503fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(store->IsInstanceFieldSet() || store->IsStaticFieldSet() || store->IsArraySet()); 504fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang store->GetBlock()->RemoveInstruction(store); 505fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 506fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 5078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // TODO: remove unnecessary allocations. 5088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Eliminate instructions in singleton_new_instances_ that: 5098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // - don't have uses, 5108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // - don't have finalizers, 5118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // - are instantiable and accessible, 5128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // - have no/separate clinit check. 5138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 5148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 5158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang private: 516fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // If heap_values[index] is an instance field store, need to keep the store. 517fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // This is necessary if a heap value is killed due to merging, or loop side 518fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // effects (which is essentially merging also), since a load later from the 519fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // location won't be eliminated. 520fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang void KeepIfIsStore(HInstruction* heap_value) { 521fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (heap_value == kDefaultHeapValue || 522fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_value == kUnknownHeapValue || 523fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang !heap_value->IsInstanceFieldSet()) { 524fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang return; 525fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 526fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang auto idx = std::find(possibly_removed_stores_.begin(), 527fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_removed_stores_.end(), heap_value); 528fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (idx != possibly_removed_stores_.end()) { 529fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Make sure the store is kept. 530fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_removed_stores_.erase(idx); 531fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 532fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 533fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 534fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang void HandleLoopSideEffects(HBasicBlock* block) { 535fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(block->IsLoopHeader()); 536fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang int block_id = block->GetBlockId(); 537fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*>& heap_values = heap_values_for_[block_id]; 538fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader(); 539fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*>& pre_header_heap_values = 540fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_values_for_[pre_header->GetBlockId()]; 541fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // We do a single pass in reverse post order. For loops, use the side effects as a hint 542fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // to see if the heap values should be killed. 543fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (side_effects_.GetLoopEffects(block).DoesAnyWrite()) { 544fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang for (size_t i = 0; i < pre_header_heap_values.size(); i++) { 545fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // heap value is killed by loop side effects, need to keep the last store. 546fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang KeepIfIsStore(pre_header_heap_values[i]); 547fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 548fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (kIsDebugBuild) { 549fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // heap_values should all be kUnknownHeapValue that it is inited with. 550fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 551fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK_EQ(heap_values[i], kUnknownHeapValue); 552fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 553fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 554fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } else { 555fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Inherit the values from pre-header. 556fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 557fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_values[i] = pre_header_heap_values[i]; 558fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 559fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 560fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 561fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 5628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void MergePredecessorValues(HBasicBlock* block) { 5638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const ArenaVector<HBasicBlock*>& predecessors = block->GetPredecessors(); 5648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (predecessors.size() == 0) { 5658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 5668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 5678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>& heap_values = heap_values_for_[block->GetBlockId()]; 5688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 569fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* pred0_value = heap_values_for_[predecessors[0]->GetBlockId()][i]; 570fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_values[i] = pred0_value; 571fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (pred0_value != kUnknownHeapValue) { 5728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t j = 1; j < predecessors.size(); j++) { 573fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* pred_value = heap_values_for_[predecessors[j]->GetBlockId()][i]; 574fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (pred_value != pred0_value) { 575fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_values[i] = kUnknownHeapValue; 5768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang break; 5778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 5788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 5798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 580fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 581fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (heap_values[i] == kUnknownHeapValue) { 582fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Keep the last store in each predecessor since future loads cannot be eliminated. 583fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang for (size_t j = 0; j < predecessors.size(); j++) { 584fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*>& pred_values = heap_values_for_[predecessors[j]->GetBlockId()]; 585fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang KeepIfIsStore(pred_values[i]); 586fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 587fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 5888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 5898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 5908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 5918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // `instruction` is being removed. Try to see if the null check on it 5928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // can be removed. This can happen if the same value is set in two branches 5938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // but not in dominators. Such as: 5948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // int[] a = foo(); 5958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // if () { 5968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // a[0] = 2; 5978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // } else { 5988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // a[0] = 2; 5998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // } 6008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // // a[0] can now be replaced with constant 2, and the null check on it can be removed. 6018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void TryRemovingNullCheck(HInstruction* instruction) { 6028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* prev = instruction->GetPrevious(); 6038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if ((prev != nullptr) && prev->IsNullCheck() && (prev == instruction->InputAt(0))) { 6048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Previous instruction is a null check for this instruction. Remove the null check. 6058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang prev->ReplaceWith(prev->InputAt(0)); 6068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang prev->GetBlock()->RemoveInstruction(prev); 6078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 6108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* GetDefaultValue(Primitive::Type type) { 6118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang switch (type) { 6128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimNot: 6138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return GetGraph()->GetNullConstant(); 6148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimBoolean: 6158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimByte: 6168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimChar: 6178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimShort: 6188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimInt: 6198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return GetGraph()->GetIntConstant(0); 6208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimLong: 6218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return GetGraph()->GetLongConstant(0); 6228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimFloat: 6238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return GetGraph()->GetFloatConstant(0); 6248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang case Primitive::kPrimDouble: 6258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return GetGraph()->GetDoubleConstant(0); 6268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang default: 6278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang UNREACHABLE(); 6288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 6318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitGetLocation(HInstruction* instruction, 6328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* ref, 6338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset, 6348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index, 6358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index) { 6368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* original_ref = HuntForOriginalReference(ref); 6378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref); 6388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t idx = heap_location_collector_.FindHeapLocationIndex( 6398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref_info, offset, index, declaring_class_def_index); 6408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); 6418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>& heap_values = 6428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values_for_[instruction->GetBlock()->GetBlockId()]; 6438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* heap_value = heap_values[idx]; 6448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_value == kDefaultHeapValue) { 6458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* constant = GetDefaultValue(instruction->GetType()); 646fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang removed_loads_.push_back(instruction); 647fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang substitute_instructions_for_loads_.push_back(constant); 6488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values[idx] = constant; 6498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 6508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 651fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (heap_value != kUnknownHeapValue && heap_value->IsInstanceFieldSet()) { 652fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HInstruction* store = heap_value; 653fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // This load must be from a singleton since it's from the same field 654fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // that a "removed" store puts the value. That store must be to a singleton's field. 655fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(ref_info->IsSingleton()); 656fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Get the real heap value of the store. 657fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_value = store->InputAt(1); 658fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 6598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if ((heap_value != kUnknownHeapValue) && 6608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Keep the load due to possible I/F, J/D array aliasing. 6618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // See b/22538329 for details. 6628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang (heap_value->GetType() == instruction->GetType())) { 663fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang removed_loads_.push_back(instruction); 664fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang substitute_instructions_for_loads_.push_back(heap_value); 6658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang TryRemovingNullCheck(instruction); 6668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 6678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 669fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Load isn't eliminated. 6708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_value == kUnknownHeapValue) { 6718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Put the load as the value into the HeapLocation. 6728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // This acts like GVN but with better aliasing analysis. 6738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values[idx] = instruction; 6748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 6778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang bool Equal(HInstruction* heap_value, HInstruction* value) { 6788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_value == value) { 6798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 6808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_value == kDefaultHeapValue && GetDefaultValue(value->GetType()) == value) { 6828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return true; 6838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return false; 6858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 6868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 6878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitSetLocation(HInstruction* instruction, 6888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* ref, 6898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset, 6908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index, 6918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index, 6928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* value) { 6938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* original_ref = HuntForOriginalReference(ref); 6948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref); 6958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t idx = heap_location_collector_.FindHeapLocationIndex( 6968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ref_info, offset, index, declaring_class_def_index); 6978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); 6988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>& heap_values = 6998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values_for_[instruction->GetBlock()->GetBlockId()]; 7008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* heap_value = heap_values[idx]; 701fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang bool same_value = false; 702fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang bool possibly_redundant = false; 7038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (Equal(heap_value, value)) { 7048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Store into the heap location with the same value. 705fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang same_value = true; 7068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (index != nullptr) { 7078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // For array element, don't eliminate stores since it can be easily aliased 7088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // with non-constant index. 7098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else if (!heap_location_collector_.MayDeoptimize() && 710fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ref_info->IsSingletonAndNotReturned()) { 711fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Store into a field of a singleton that's not returned. The value cannot be 712fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // killed due to aliasing/invocation. It can be redundant since future loads can 713fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // directly get the value set by this instruction. The value can still be killed due to 714fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // merging or loop side effects. Stores whose values are killed due to merging/loop side 715fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // effects later will be removed from possibly_removed_stores_ when that is detected. 716fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_redundant = true; 717fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HNewInstance* new_instance = ref_info->GetReference()->AsNewInstance(); 718fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(new_instance != nullptr); 719fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (new_instance->IsFinalizable()) { 720fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Finalizable objects escape globally. Need to keep the store. 721fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_redundant = false; 7228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else { 723fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang HLoopInformation* loop_info = instruction->GetBlock()->GetLoopInformation(); 724fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (loop_info != nullptr) { 725fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // instruction is a store in the loop so the loop must does write. 726fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(side_effects_.GetLoopEffects(loop_info->GetHeader()).DoesAnyWrite()); 727fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 7284b467ed97bc5886fb800209c0ee94df10163b88dMingyao Yang if (loop_info->IsDefinedOutOfTheLoop(original_ref)) { 729fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(original_ref->GetBlock()->Dominates(loop_info->GetPreHeader())); 730fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Keep the store since its value may be needed at the loop header. 731fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_redundant = false; 732fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } else { 733fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // The singleton is created inside the loop. Value stored to it isn't needed at 734fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // the loop header. This is true for outer loops also. 735fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 736fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 7378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 739fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (same_value || possibly_redundant) { 740fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang possibly_removed_stores_.push_back(instruction); 7418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 742e9d6e6083e845194548e0705fdf9e172c7a043e5Mingyao Yang 743fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (!same_value) { 744fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (possibly_redundant) { 745fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang DCHECK(instruction->IsInstanceFieldSet()); 746fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Put the store as the heap value. If the value is loaded from heap 747fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // by a load later, this store isn't really redundant. 748fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_values[idx] = instruction; 749fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } else { 750fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang heap_values[idx] = value; 751fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 752fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 7538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // This store may kill values in other heap locations due to aliasing. 7548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 755fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (i == idx) { 756fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang continue; 757fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang } 7588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_values[i] == value) { 7598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Same value should be kept even if aliasing happens. 7608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang continue; 7618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_values[i] == kUnknownHeapValue) { 7638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Value is already unknown, no need for aliasing check. 7648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang continue; 7658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_location_collector_.MayAlias(i, idx)) { 7678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Kill heap locations that may alias. 7688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values[i] = kUnknownHeapValue; 7698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 7738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInstanceFieldGet(HInstanceFieldGet* instruction) OVERRIDE { 7748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* obj = instruction->InputAt(0); 7758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); 7768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); 7778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitGetLocation(instruction, obj, offset, nullptr, declaring_class_def_index); 7788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 7808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInstanceFieldSet(HInstanceFieldSet* instruction) OVERRIDE { 7818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* obj = instruction->InputAt(0); 7828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); 7838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); 7848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* value = instruction->InputAt(1); 7858df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitSetLocation(instruction, obj, offset, nullptr, declaring_class_def_index, value); 7868df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7878df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 7888df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitStaticFieldGet(HStaticFieldGet* instruction) OVERRIDE { 7898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* cls = instruction->InputAt(0); 7908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); 7918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); 7928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitGetLocation(instruction, cls, offset, nullptr, declaring_class_def_index); 7938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 7948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 7958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitStaticFieldSet(HStaticFieldSet* instruction) OVERRIDE { 7968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* cls = instruction->InputAt(0); 7978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); 7988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); 7998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* value = instruction->InputAt(1); 8008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitSetLocation(instruction, cls, offset, nullptr, declaring_class_def_index, value); 8018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitArrayGet(HArrayGet* instruction) OVERRIDE { 8048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* array = instruction->InputAt(0); 8058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index = instruction->InputAt(1); 8068df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitGetLocation(instruction, 8078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang array, 8088df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation::kInvalidFieldOffset, 8098df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang index, 8108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation::kDeclaringClassDefIndexForArrays); 8118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitArraySet(HArraySet* instruction) OVERRIDE { 8148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* array = instruction->InputAt(0); 8158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* index = instruction->InputAt(1); 8168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* value = instruction->InputAt(2); 8178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang VisitSetLocation(instruction, 8188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang array, 8198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation::kInvalidFieldOffset, 8208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang index, 8218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocation::kDeclaringClassDefIndexForArrays, 8228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang value); 8238df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8248df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8258df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void HandleInvoke(HInstruction* invoke) { 8268df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>& heap_values = 8278df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values_for_[invoke->GetBlock()->GetBlockId()]; 8288df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 8298df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo(); 8308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info->IsSingleton()) { 8318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Singleton references cannot be seen by the callee. 8328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } else { 8338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values[i] = kUnknownHeapValue; 8348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8368df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8388df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) OVERRIDE { 8398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(invoke); 8408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInvokeVirtual(HInvokeVirtual* invoke) OVERRIDE { 8438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(invoke); 8448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInvokeInterface(HInvokeInterface* invoke) OVERRIDE { 8478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(invoke); 8488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitInvokeUnresolved(HInvokeUnresolved* invoke) OVERRIDE { 8518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(invoke); 8528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitClinitCheck(HClinitCheck* clinit) OVERRIDE { 8558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(clinit); 8568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitUnresolvedInstanceFieldGet(HUnresolvedInstanceFieldGet* instruction) OVERRIDE { 8598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Conservatively treat it as an invocation. 8608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(instruction); 8618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitUnresolvedInstanceFieldSet(HUnresolvedInstanceFieldSet* instruction) OVERRIDE { 8648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Conservatively treat it as an invocation. 8658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(instruction); 8668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitUnresolvedStaticFieldGet(HUnresolvedStaticFieldGet* instruction) OVERRIDE { 8698df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Conservatively treat it as an invocation. 8708df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(instruction); 8718df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8728df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8738df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitUnresolvedStaticFieldSet(HUnresolvedStaticFieldSet* instruction) OVERRIDE { 8748df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Conservatively treat it as an invocation. 8758df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HandleInvoke(instruction); 8768df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8778df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 8788df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang void VisitNewInstance(HNewInstance* new_instance) OVERRIDE { 8798df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(new_instance); 8808df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref_info == nullptr) { 8818df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // new_instance isn't used for field accesses. No need to process it. 8828df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 8838df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8848df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (!heap_location_collector_.MayDeoptimize() && 885fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ref_info->IsSingletonAndNotReturned() && 886fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang !new_instance->IsFinalizable() && 887fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang !new_instance->CanThrow()) { 888fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // TODO: add new_instance to singleton_new_instances_ and enable allocation elimination. 8898df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 8908df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*>& heap_values = 8918df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values_for_[new_instance->GetBlock()->GetBlockId()]; 8928df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < heap_values.size(); i++) { 8938df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* ref = 8948df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo()->GetReference(); 8958df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang size_t offset = heap_location_collector_.GetHeapLocation(i)->GetOffset(); 8968df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (ref == new_instance && offset >= mirror::kObjectHeaderSize) { 8978df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Instance fields except the header fields are set to default heap values. 8988df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_values[i] = kDefaultHeapValue; 8998df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9008df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9018df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9028df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9038df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Find an instruction's substitute if it should be removed. 9048df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Return the same instruction if it should not be removed. 9058df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HInstruction* FindSubstitute(HInstruction* instruction) { 906fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang size_t size = removed_loads_.size(); 9078df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (size_t i = 0; i < size; i++) { 908fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang if (removed_loads_[i] == instruction) { 909fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang return substitute_instructions_for_loads_[i]; 9108df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9118df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9128df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return instruction; 9138df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9148df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9158df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const HeapLocationCollector& heap_location_collector_; 9168df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang const SideEffectsAnalysis& side_effects_; 9178df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9188df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // One array of heap values for each block. 9198df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<ArenaVector<HInstruction*>> heap_values_for_; 9208df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9218df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // We record the instructions that should be eliminated but may be 9228df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // used by heap locations. They'll be removed in the end. 923fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*> removed_loads_; 924fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*> substitute_instructions_for_loads_; 925fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 926fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // Stores in this list may be removed from the list later when it's 927fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang // found that the store cannot be eliminated. 928fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang ArenaVector<HInstruction*> possibly_removed_stores_; 929fb8464ae5f5194dc16278e528cfcbff71498c767Mingyao Yang 9308df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang ArenaVector<HInstruction*> singleton_new_instances_; 9318df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9328df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang DISALLOW_COPY_AND_ASSIGN(LSEVisitor); 9338df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang}; 9348df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9358df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yangvoid LoadStoreElimination::Run() { 9368993caf6571863c8e5eec0b2ce4d72f6f1793f31David Brazdil if (graph_->IsDebuggable() || graph_->HasTryCatch()) { 9378df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Debugger may set heap values or trigger deoptimization of callers. 9388993caf6571863c8e5eec0b2ce4d72f6f1793f31David Brazdil // Try/catch support not implemented yet. 9398df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Skip this optimization. 9408df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 9418df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9428df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang HeapLocationCollector heap_location_collector(graph_); 9438df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 9448df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_location_collector.VisitBasicBlock(it.Current()); 9458df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9468df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_location_collector.GetNumberOfHeapLocations() > kMaxNumberOfHeapLocations) { 9478df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Bail out if there are too many heap locations to deal with. 9488df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 9498df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9508df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (!heap_location_collector.HasHeapStores()) { 9518df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Without heap stores, this pass would act mostly as GVN on heap accesses. 9528df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 9538df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9548df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang if (heap_location_collector.HasVolatile() || heap_location_collector.HasMonitorOps()) { 9558df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // Don't do load/store elimination if the method has volatile field accesses or 9568df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // monitor operations, for now. 9578df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang // TODO: do it right. 9588df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang return; 9598df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9608df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang heap_location_collector.BuildAliasingMatrix(); 9618df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang LSEVisitor lse_visitor(graph_, heap_location_collector, side_effects_); 9628df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 9638df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang lse_visitor.VisitBasicBlock(it.Current()); 9648df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang } 9658df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang lse_visitor.RemoveInstructions(); 9668df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang} 9678df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang 9688df69d42a9e3ccd9456ff72fac8dbd1999f98755Mingyao Yang} // namespace art 969