load_store_analysis.h revision b50b16a68ababbc9acab6102bf0bb63bd5083763
1c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong/* 2c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong * Copyright (C) 2017 The Android Open Source Project 3c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong * 4c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong * Licensed under the Apache License, Version 2.0 (the "License"); 5c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong * you may not use this file except in compliance with the License. 6c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong * You may obtain a copy of the License at 7c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong * 8c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong * http://www.apache.org/licenses/LICENSE-2.0 9c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong * 10c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong * Unless required by applicable law or agreed to in writing, software 11c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong * distributed under the License is distributed on an "AS IS" BASIS, 12c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong * See the License for the specific language governing permissions and 14c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong * limitations under the License. 15c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong */ 16c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 17c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong#ifndef ART_COMPILER_OPTIMIZING_LOAD_STORE_ANALYSIS_H_ 18c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong#define ART_COMPILER_OPTIMIZING_LOAD_STORE_ANALYSIS_H_ 19c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 20c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong#include "escape.h" 21c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong#include "nodes.h" 22c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong#include "optimization.h" 23c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 24c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhongnamespace art { 25c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 26c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong// A ReferenceInfo contains additional info about a reference such as 27c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong// whether it's a singleton, returned, etc. 28009d166842195711eca4d5768c59a8f7404e6875Vladimir Markoclass ReferenceInfo : public ArenaObject<kArenaAllocLSA> { 29c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong public: 30c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong ReferenceInfo(HInstruction* reference, size_t pos) 31c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong : reference_(reference), 32c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong position_(pos), 33c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong is_singleton_(true), 34c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong is_singleton_and_not_returned_(true), 35c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong is_singleton_and_not_deopt_visible_(true), 36c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong has_index_aliasing_(false) { 37c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong CalculateEscape(reference_, 38c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong nullptr, 39c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong &is_singleton_, 40c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong &is_singleton_and_not_returned_, 41c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong &is_singleton_and_not_deopt_visible_); 42c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 43c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 44c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HInstruction* GetReference() const { 45c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return reference_; 46c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 47c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 48c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong size_t GetPosition() const { 49c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return position_; 50c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 51c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 52c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Returns true if reference_ is the only name that can refer to its value during 53c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // the lifetime of the method. So it's guaranteed to not have any alias in 54c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // the method (including its callees). 55c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool IsSingleton() const { 56c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return is_singleton_; 57c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 58c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 59c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Returns true if reference_ is a singleton and not returned to the caller or 60c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // used as an environment local of an HDeoptimize instruction. 61c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // The allocation and stores into reference_ may be eliminated for such cases. 62c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool IsSingletonAndRemovable() const { 63c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return is_singleton_and_not_returned_ && is_singleton_and_not_deopt_visible_; 64c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 65c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 66c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Returns true if reference_ is a singleton and returned to the caller or 67c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // used as an environment local of an HDeoptimize instruction. 68c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool IsSingletonAndNonRemovable() const { 69c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return is_singleton_ && 70c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong (!is_singleton_and_not_returned_ || !is_singleton_and_not_deopt_visible_); 71c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 72c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 73c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool HasIndexAliasing() { 74c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return has_index_aliasing_; 75c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 76c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 77c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong void SetHasIndexAliasing(bool has_index_aliasing) { 78c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Only allow setting to true. 79c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong DCHECK(has_index_aliasing); 80c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong has_index_aliasing_ = has_index_aliasing; 81c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 82c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 83c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong private: 84c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HInstruction* const reference_; 85c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong const size_t position_; // position in HeapLocationCollector's ref_info_array_. 86c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 87c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Can only be referred to by a single name in the method. 88c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool is_singleton_; 89c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Is singleton and not returned to caller. 90c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool is_singleton_and_not_returned_; 91c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Is singleton and not used as an environment local of HDeoptimize. 92c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool is_singleton_and_not_deopt_visible_; 93c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Some heap locations with reference_ have array index aliasing, 94c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // e.g. arr[i] and arr[j] may be the same location. 95c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool has_index_aliasing_; 96c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 97c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong DISALLOW_COPY_AND_ASSIGN(ReferenceInfo); 98c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong}; 99c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 100c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong// A heap location is a reference-offset/index pair that a value can be loaded from 101c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong// or stored to. 102009d166842195711eca4d5768c59a8f7404e6875Vladimir Markoclass HeapLocation : public ArenaObject<kArenaAllocLSA> { 103c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong public: 104c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong static constexpr size_t kInvalidFieldOffset = -1; 105b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // Default value for heap locations which are not vector data. 106b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong static constexpr size_t kScalar = 1; 107c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // TODO: more fine-grained array types. 108c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong static constexpr int16_t kDeclaringClassDefIndexForArrays = -1; 109c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 110c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HeapLocation(ReferenceInfo* ref_info, 111c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong size_t offset, 112c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HInstruction* index, 113b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong size_t vector_length, 114c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong int16_t declaring_class_def_index) 115c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong : ref_info_(ref_info), 116c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong offset_(offset), 117c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong index_(index), 118b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong vector_length_(vector_length), 119c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong declaring_class_def_index_(declaring_class_def_index), 120c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong value_killed_by_loop_side_effects_(true) { 121c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong DCHECK(ref_info != nullptr); 122c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong DCHECK((offset == kInvalidFieldOffset && index != nullptr) || 123c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong (offset != kInvalidFieldOffset && index == nullptr)); 124b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong if (ref_info->IsSingleton() && !IsArray()) { 125c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Assume this location's value cannot be killed by loop side effects 126c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // until proven otherwise. 127c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong value_killed_by_loop_side_effects_ = false; 128c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 129c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 130c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 131c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong ReferenceInfo* GetReferenceInfo() const { return ref_info_; } 132c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong size_t GetOffset() const { return offset_; } 133c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HInstruction* GetIndex() const { return index_; } 134b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong size_t GetVectorLength() const { return vector_length_; } 135c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 136c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Returns the definition of declaring class' dex index. 137c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // It's kDeclaringClassDefIndexForArrays for an array element. 138c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong int16_t GetDeclaringClassDefIndex() const { 139c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return declaring_class_def_index_; 140c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 141c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 142b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong bool IsArray() const { 143c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return index_ != nullptr; 144c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 145c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 146c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool IsValueKilledByLoopSideEffects() const { 147c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return value_killed_by_loop_side_effects_; 148c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 149c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 150c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong void SetValueKilledByLoopSideEffects(bool val) { 151c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong value_killed_by_loop_side_effects_ = val; 152c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 153c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 154c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong private: 155b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // Reference for instance/static field, array element or vector data. 156b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong ReferenceInfo* const ref_info_; 157b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // Offset of static/instance field. 158b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // Invalid when this HeapLocation is not field. 159b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong const size_t offset_; 160b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // Index of an array element or starting index of vector data. 161b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // Invalid when this HeapLocation is not array. 162b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HInstruction* const index_; 163b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // Vector length of vector data. 164b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // When this HeapLocation is not vector data, it's value is kScalar. 165b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong const size_t vector_length_; 166b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // Declaring class's def's dex index. 167b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // Invalid when this HeapLocation is not field access. 168b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong const int16_t declaring_class_def_index_; 169b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong 170b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // Value of this location may be killed by loop side effects 171b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // because this location is stored into inside a loop. 172b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // This gives better info on whether a singleton's location 173b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // value may be killed by loop side effects. 174b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong bool value_killed_by_loop_side_effects_; 175c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 176c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong DISALLOW_COPY_AND_ASSIGN(HeapLocation); 177c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong}; 178c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 179c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong// A HeapLocationCollector collects all relevant heap locations and keeps 180c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong// an aliasing matrix for all locations. 181c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhongclass HeapLocationCollector : public HGraphVisitor { 182c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong public: 183c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong static constexpr size_t kHeapLocationNotFound = -1; 184c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Start with a single uint32_t word. That's enough bits for pair-wise 185c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // aliasing matrix of 8 heap locations. 186c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong static constexpr uint32_t kInitialAliasingMatrixBitVectorSize = 32; 187c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 188c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong explicit HeapLocationCollector(HGraph* graph) 189c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong : HGraphVisitor(graph), 190009d166842195711eca4d5768c59a8f7404e6875Vladimir Marko ref_info_array_(graph->GetAllocator()->Adapter(kArenaAllocLSA)), 191009d166842195711eca4d5768c59a8f7404e6875Vladimir Marko heap_locations_(graph->GetAllocator()->Adapter(kArenaAllocLSA)), 192ca6fff898afcb62491458ae8bcd428bfb3043da1Vladimir Marko aliasing_matrix_(graph->GetAllocator(), 193c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong kInitialAliasingMatrixBitVectorSize, 194c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong true, 195009d166842195711eca4d5768c59a8f7404e6875Vladimir Marko kArenaAllocLSA), 196c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong has_heap_stores_(false), 197c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong has_volatile_(false), 198c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong has_monitor_operations_(false) {} 199c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 200c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong void CleanUp() { 201c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong heap_locations_.clear(); 202c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong ref_info_array_.clear(); 203c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 204c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 205c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong size_t GetNumberOfHeapLocations() const { 206c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return heap_locations_.size(); 207c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 208c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 209c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HeapLocation* GetHeapLocation(size_t index) const { 210c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return heap_locations_[index]; 211c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 212c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 213c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HInstruction* HuntForOriginalReference(HInstruction* ref) const { 214e0eb48353ddf0c1b79bfec2ba15c899a413c2c70xueliang.zhong // An original reference can be transformed by instructions like: 215e0eb48353ddf0c1b79bfec2ba15c899a413c2c70xueliang.zhong // i0 NewArray 216e0eb48353ddf0c1b79bfec2ba15c899a413c2c70xueliang.zhong // i1 HInstruction(i0) <-- NullCheck, BoundType, IntermediateAddress. 217e0eb48353ddf0c1b79bfec2ba15c899a413c2c70xueliang.zhong // i2 ArrayGet(i1, index) 218c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong DCHECK(ref != nullptr); 219e0eb48353ddf0c1b79bfec2ba15c899a413c2c70xueliang.zhong while (ref->IsNullCheck() || ref->IsBoundType() || ref->IsIntermediateAddress()) { 220c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong ref = ref->InputAt(0); 221c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 222c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return ref; 223c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 224c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 225c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong ReferenceInfo* FindReferenceInfoOf(HInstruction* ref) const { 226c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong for (size_t i = 0; i < ref_info_array_.size(); i++) { 227c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong ReferenceInfo* ref_info = ref_info_array_[i]; 228c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong if (ref_info->GetReference() == ref) { 229c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong DCHECK_EQ(i, ref_info->GetPosition()); 230c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return ref_info; 231c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 232c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 233c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return nullptr; 234c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 235c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 236b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong size_t GetFieldHeapLocation(HInstruction* object, const FieldInfo* field) const { 237b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong DCHECK(object != nullptr); 238b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong DCHECK(field != nullptr); 239b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong return FindHeapLocationIndex(FindReferenceInfoOf(HuntForOriginalReference(object)), 240b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong field->GetFieldOffset().SizeValue(), 241b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong nullptr, 242b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HeapLocation::kScalar, 243b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong field->GetDeclaringClassDefIndex()); 244b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong } 245b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong 246b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong size_t GetArrayHeapLocation(HInstruction* array, 247b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HInstruction* index, 248b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong size_t vector_length = HeapLocation::kScalar) const { 249016c0f165dc6872d22c12c239d19b094983519f1xueliang.zhong DCHECK(array != nullptr); 250016c0f165dc6872d22c12c239d19b094983519f1xueliang.zhong DCHECK(index != nullptr); 251b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong DCHECK_GE(vector_length, HeapLocation::kScalar); 252b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong return FindHeapLocationIndex(FindReferenceInfoOf(HuntForOriginalReference(array)), 253016c0f165dc6872d22c12c239d19b094983519f1xueliang.zhong HeapLocation::kInvalidFieldOffset, 254016c0f165dc6872d22c12c239d19b094983519f1xueliang.zhong index, 255b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong vector_length, 256016c0f165dc6872d22c12c239d19b094983519f1xueliang.zhong HeapLocation::kDeclaringClassDefIndexForArrays); 257016c0f165dc6872d22c12c239d19b094983519f1xueliang.zhong } 258016c0f165dc6872d22c12c239d19b094983519f1xueliang.zhong 259c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool HasHeapStores() const { 260c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return has_heap_stores_; 261c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 262c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 263c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool HasVolatile() const { 264c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return has_volatile_; 265c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 266c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 267c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool HasMonitorOps() const { 268c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return has_monitor_operations_; 269c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 270c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 271c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Find and return the heap location index in heap_locations_. 272b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // NOTE: When heap locations are created, potentially aliasing/overlapping 273b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // accesses are given different indexes. This find function also 274b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // doesn't take aliasing/overlapping into account. For example, 275b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // this function returns three different indexes for: 276b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // - ref_info=array, index=i, vector_length=kScalar; 277b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // - ref_info=array, index=i, vector_length=2; 278b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // - ref_info=array, index=i, vector_length=4; 279b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // In later analysis, ComputeMayAlias() and MayAlias() compute and tell whether 280b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // these indexes alias. 281c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong size_t FindHeapLocationIndex(ReferenceInfo* ref_info, 282c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong size_t offset, 283c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HInstruction* index, 284b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong size_t vector_length, 285c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong int16_t declaring_class_def_index) const { 286c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong for (size_t i = 0; i < heap_locations_.size(); i++) { 287c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HeapLocation* loc = heap_locations_[i]; 288c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong if (loc->GetReferenceInfo() == ref_info && 289c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong loc->GetOffset() == offset && 290c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong loc->GetIndex() == index && 291b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong loc->GetVectorLength() == vector_length && 292c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong loc->GetDeclaringClassDefIndex() == declaring_class_def_index) { 293c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return i; 294c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 295c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 296c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return kHeapLocationNotFound; 297c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 298c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 299c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Returns true if heap_locations_[index1] and heap_locations_[index2] may alias. 300c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool MayAlias(size_t index1, size_t index2) const { 301c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong if (index1 < index2) { 302c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return aliasing_matrix_.IsBitSet(AliasingMatrixPosition(index1, index2)); 303c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } else if (index1 > index2) { 304c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return aliasing_matrix_.IsBitSet(AliasingMatrixPosition(index2, index1)); 305c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } else { 306c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong DCHECK(false) << "index1 and index2 are expected to be different"; 307c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return true; 308c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 309c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 310c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 311c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong void BuildAliasingMatrix() { 312c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong const size_t number_of_locations = heap_locations_.size(); 313c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong if (number_of_locations == 0) { 314c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return; 315c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 316c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong size_t pos = 0; 317c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Compute aliasing info between every pair of different heap locations. 318c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Save the result in a matrix represented as a BitVector. 319c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong for (size_t i = 0; i < number_of_locations - 1; i++) { 320c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong for (size_t j = i + 1; j < number_of_locations; j++) { 321c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong if (ComputeMayAlias(i, j)) { 322c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong aliasing_matrix_.SetBit(CheckedAliasingMatrixPosition(i, j, pos)); 323c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 324c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong pos++; 325c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 326c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 327c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 328c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 329c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong private: 330c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // An allocation cannot alias with a name which already exists at the point 331c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // of the allocation, such as a parameter or a load happening before the allocation. 332c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool MayAliasWithPreexistenceChecking(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) const { 333c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong if (ref_info1->GetReference()->IsNewInstance() || ref_info1->GetReference()->IsNewArray()) { 334c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Any reference that can alias with the allocation must appear after it in the block/in 335c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // the block's successors. In reverse post order, those instructions will be visited after 336c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // the allocation. 337c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return ref_info2->GetPosition() >= ref_info1->GetPosition(); 338c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 339c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return true; 340c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 341c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 342c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool CanReferencesAlias(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) const { 343c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong if (ref_info1 == ref_info2) { 344c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return true; 345c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } else if (ref_info1->IsSingleton()) { 346c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return false; 347c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } else if (ref_info2->IsSingleton()) { 348c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return false; 349c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } else if (!MayAliasWithPreexistenceChecking(ref_info1, ref_info2) || 350c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong !MayAliasWithPreexistenceChecking(ref_info2, ref_info1)) { 351c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return false; 352c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 353c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return true; 354c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 355c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 356b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong bool CanArrayElementsAlias(const HInstruction* idx1, 357b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong const size_t vector_length1, 358b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong const HInstruction* idx2, 359b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong const size_t vector_length2) const; 360016c0f165dc6872d22c12c239d19b094983519f1xueliang.zhong 361c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // `index1` and `index2` are indices in the array of collected heap locations. 362c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Returns the position in the bit vector that tracks whether the two heap 363c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // locations may alias. 364c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong size_t AliasingMatrixPosition(size_t index1, size_t index2) const { 365c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong DCHECK(index2 > index1); 366c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong const size_t number_of_locations = heap_locations_.size(); 367c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // It's (num_of_locations - 1) + ... + (num_of_locations - index1) + (index2 - index1 - 1). 368c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return (number_of_locations * index1 - (1 + index1) * index1 / 2 + (index2 - index1 - 1)); 369c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 370c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 371c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // An additional position is passed in to make sure the calculated position is correct. 372c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong size_t CheckedAliasingMatrixPosition(size_t index1, size_t index2, size_t position) { 373c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong size_t calculated_position = AliasingMatrixPosition(index1, index2); 374c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong DCHECK_EQ(calculated_position, position); 375c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return calculated_position; 376c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 377c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 378c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Compute if two locations may alias to each other. 379c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool ComputeMayAlias(size_t index1, size_t index2) const { 380c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HeapLocation* loc1 = heap_locations_[index1]; 381c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HeapLocation* loc2 = heap_locations_[index2]; 382c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong if (loc1->GetOffset() != loc2->GetOffset()) { 383c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Either two different instance fields, or one is an instance 384b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong // field and the other is an array data. 385c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return false; 386c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 387c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong if (loc1->GetDeclaringClassDefIndex() != loc2->GetDeclaringClassDefIndex()) { 388c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // Different types. 389c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return false; 390c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 391c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong if (!CanReferencesAlias(loc1->GetReferenceInfo(), loc2->GetReferenceInfo())) { 392c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return false; 393c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 394b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong if (loc1->IsArray() && loc2->IsArray()) { 395b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HInstruction* idx1 = loc1->GetIndex(); 396b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HInstruction* idx2 = loc2->GetIndex(); 397b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong size_t vector_length1 = loc1->GetVectorLength(); 398b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong size_t vector_length2 = loc2->GetVectorLength(); 399b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong if (!CanArrayElementsAlias(idx1, vector_length1, idx2, vector_length2)) { 400c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return false; 401c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 402c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong ReferenceInfo* ref_info = loc1->GetReferenceInfo(); 403c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong ref_info->SetHasIndexAliasing(true); 404c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 405c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return true; 406c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 407c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 408c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong ReferenceInfo* GetOrCreateReferenceInfo(HInstruction* instruction) { 409c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong ReferenceInfo* ref_info = FindReferenceInfoOf(instruction); 410c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong if (ref_info == nullptr) { 411c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong size_t pos = ref_info_array_.size(); 412ca6fff898afcb62491458ae8bcd428bfb3043da1Vladimir Marko ref_info = new (GetGraph()->GetAllocator()) ReferenceInfo(instruction, pos); 413c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong ref_info_array_.push_back(ref_info); 414c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 415c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return ref_info; 416c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 417c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 418c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong void CreateReferenceInfoForReferenceType(HInstruction* instruction) { 4190ebe0d83138bba1996e9c8007969b5381d972b32Vladimir Marko if (instruction->GetType() != DataType::Type::kReference) { 420c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return; 421c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 422c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong DCHECK(FindReferenceInfoOf(instruction) == nullptr); 423c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong GetOrCreateReferenceInfo(instruction); 424c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 425c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 426c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HeapLocation* GetOrCreateHeapLocation(HInstruction* ref, 427c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong size_t offset, 428c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HInstruction* index, 429b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong size_t vector_length, 430c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong int16_t declaring_class_def_index) { 431c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HInstruction* original_ref = HuntForOriginalReference(ref); 432c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong ReferenceInfo* ref_info = GetOrCreateReferenceInfo(original_ref); 433c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong size_t heap_location_idx = FindHeapLocationIndex( 434b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong ref_info, offset, index, vector_length, declaring_class_def_index); 435c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong if (heap_location_idx == kHeapLocationNotFound) { 436ca6fff898afcb62491458ae8bcd428bfb3043da1Vladimir Marko HeapLocation* heap_loc = new (GetGraph()->GetAllocator()) 437b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HeapLocation(ref_info, offset, index, vector_length, declaring_class_def_index); 438c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong heap_locations_.push_back(heap_loc); 439c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return heap_loc; 440c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 441c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return heap_locations_[heap_location_idx]; 442c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 443c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 444c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HeapLocation* VisitFieldAccess(HInstruction* ref, const FieldInfo& field_info) { 445c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong if (field_info.IsVolatile()) { 446c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong has_volatile_ = true; 447c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 448c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong const uint16_t declaring_class_def_index = field_info.GetDeclaringClassDefIndex(); 449c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong const size_t offset = field_info.GetFieldOffset().SizeValue(); 450b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong return GetOrCreateHeapLocation(ref, 451b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong offset, 452b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong nullptr, 453b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HeapLocation::kScalar, 454b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong declaring_class_def_index); 455c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 456c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 457b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong void VisitArrayAccess(HInstruction* array, HInstruction* index, size_t vector_length) { 458b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong GetOrCreateHeapLocation(array, 459b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HeapLocation::kInvalidFieldOffset, 460b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong index, 461b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong vector_length, 462b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HeapLocation::kDeclaringClassDefIndexForArrays); 463c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 464c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 465c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong void VisitInstanceFieldGet(HInstanceFieldGet* instruction) OVERRIDE { 466c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); 467c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong CreateReferenceInfoForReferenceType(instruction); 468c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 469c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 470c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong void VisitInstanceFieldSet(HInstanceFieldSet* instruction) OVERRIDE { 471c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HeapLocation* location = VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); 472c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong has_heap_stores_ = true; 473c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong if (location->GetReferenceInfo()->IsSingleton()) { 474c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // A singleton's location value may be killed by loop side effects if it's 475c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // defined before that loop, and it's stored into inside that loop. 476c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HLoopInformation* loop_info = instruction->GetBlock()->GetLoopInformation(); 477c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong if (loop_info != nullptr) { 478c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HInstruction* ref = location->GetReferenceInfo()->GetReference(); 479c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong DCHECK(ref->IsNewInstance()); 480c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong if (loop_info->IsDefinedOutOfTheLoop(ref)) { 481c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // ref's location value may be killed by this loop's side effects. 482c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong location->SetValueKilledByLoopSideEffects(true); 483c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } else { 484c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // ref is defined inside this loop so this loop's side effects cannot 485c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // kill its location value at the loop header since ref/its location doesn't 486c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // exist yet at the loop header. 487c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 488c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 489c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } else { 490c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // For non-singletons, value_killed_by_loop_side_effects_ is inited to 491c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // true. 492c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong DCHECK_EQ(location->IsValueKilledByLoopSideEffects(), true); 493c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 494c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 495c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 496c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong void VisitStaticFieldGet(HStaticFieldGet* instruction) OVERRIDE { 497c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); 498c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong CreateReferenceInfoForReferenceType(instruction); 499c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 500c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 501c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong void VisitStaticFieldSet(HStaticFieldSet* instruction) OVERRIDE { 502c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo()); 503c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong has_heap_stores_ = true; 504c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 505c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 506c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // We intentionally don't collect HUnresolvedInstanceField/HUnresolvedStaticField accesses 507c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // since we cannot accurately track the fields. 508c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 509c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong void VisitArrayGet(HArrayGet* instruction) OVERRIDE { 510b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HInstruction* array = instruction->InputAt(0); 511b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HInstruction* index = instruction->InputAt(1); 512b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong VisitArrayAccess(array, index, HeapLocation::kScalar); 513c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong CreateReferenceInfoForReferenceType(instruction); 514c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 515c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 516c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong void VisitArraySet(HArraySet* instruction) OVERRIDE { 517b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HInstruction* array = instruction->InputAt(0); 518b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HInstruction* index = instruction->InputAt(1); 519b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong VisitArrayAccess(array, index, HeapLocation::kScalar); 520b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong has_heap_stores_ = true; 521b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong } 522b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong 523b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong void VisitVecLoad(HVecLoad* instruction) OVERRIDE { 524b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HInstruction* array = instruction->InputAt(0); 525b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HInstruction* index = instruction->InputAt(1); 526b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong VisitArrayAccess(array, index, instruction->GetVectorLength()); 527b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong CreateReferenceInfoForReferenceType(instruction); 528b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong } 529b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong 530b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong void VisitVecStore(HVecStore* instruction) OVERRIDE { 531b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HInstruction* array = instruction->InputAt(0); 532b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong HInstruction* index = instruction->InputAt(1); 533b50b16a68ababbc9acab6102bf0bb63bd5083763xueliang.zhong VisitArrayAccess(array, index, instruction->GetVectorLength()); 534c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong has_heap_stores_ = true; 535c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 536c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 537fef2884b18bcc01cc40edb2ae809d42b5a510c33Mingyao Yang void VisitInstruction(HInstruction* instruction) OVERRIDE { 538fef2884b18bcc01cc40edb2ae809d42b5a510c33Mingyao Yang // Any new-instance or new-array cannot alias with references that 539fef2884b18bcc01cc40edb2ae809d42b5a510c33Mingyao Yang // pre-exist the new-instance/new-array. We append entries into 540fef2884b18bcc01cc40edb2ae809d42b5a510c33Mingyao Yang // ref_info_array_ which keeps track of the order of creation 541fef2884b18bcc01cc40edb2ae809d42b5a510c33Mingyao Yang // of reference values since we visit the blocks in reverse post order. 542fef2884b18bcc01cc40edb2ae809d42b5a510c33Mingyao Yang // 543fef2884b18bcc01cc40edb2ae809d42b5a510c33Mingyao Yang // By default, VisitXXX() (including VisitPhi()) calls VisitInstruction(), 544fef2884b18bcc01cc40edb2ae809d42b5a510c33Mingyao Yang // unless VisitXXX() is overridden. VisitInstanceFieldGet() etc. above 545fef2884b18bcc01cc40edb2ae809d42b5a510c33Mingyao Yang // also call CreateReferenceInfoForReferenceType() explicitly. 546c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong CreateReferenceInfoForReferenceType(instruction); 547c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 548c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 549c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong void VisitMonitorOperation(HMonitorOperation* monitor ATTRIBUTE_UNUSED) OVERRIDE { 550c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong has_monitor_operations_ = true; 551c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 552c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 553c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong ArenaVector<ReferenceInfo*> ref_info_array_; // All references used for heap accesses. 554c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong ArenaVector<HeapLocation*> heap_locations_; // All heap locations. 555c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong ArenaBitVector aliasing_matrix_; // aliasing info between each pair of locations. 556c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool has_heap_stores_; // If there is no heap stores, LSE acts as GVN with better 557c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong // alias analysis and won't be as effective. 558c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool has_volatile_; // If there are volatile field accesses. 559c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong bool has_monitor_operations_; // If there are monitor operations. 560c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 561c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong DISALLOW_COPY_AND_ASSIGN(HeapLocationCollector); 562c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong}; 563c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 564c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhongclass LoadStoreAnalysis : public HOptimization { 565c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong public: 566c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong explicit LoadStoreAnalysis(HGraph* graph) 567c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong : HOptimization(graph, kLoadStoreAnalysisPassName), 568c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong heap_location_collector_(graph) {} 569c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 570c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong const HeapLocationCollector& GetHeapLocationCollector() const { 571c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong return heap_location_collector_; 572c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong } 573c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 574c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong void Run() OVERRIDE; 575c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 576c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong static constexpr const char* kLoadStoreAnalysisPassName = "load_store_analysis"; 577c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 578c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong private: 579c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong HeapLocationCollector heap_location_collector_; 580c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 581c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong DISALLOW_COPY_AND_ASSIGN(LoadStoreAnalysis); 582c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong}; 583c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 584c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong} // namespace art 585c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong 586c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong#endif // ART_COMPILER_OPTIMIZING_LOAD_STORE_ANALYSIS_H_ 587