load_store_analysis.h revision c239a2bb9474a1266c4882638fdb19056370e16d
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.
28c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhongclass ReferenceInfo : public ArenaObject<kArenaAllocMisc> {
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.
102c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhongclass HeapLocation : public ArenaObject<kArenaAllocMisc> {
103c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong public:
104c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  static constexpr size_t kInvalidFieldOffset = -1;
105c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
106c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  // TODO: more fine-grained array types.
107c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  static constexpr int16_t kDeclaringClassDefIndexForArrays = -1;
108c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
109c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  HeapLocation(ReferenceInfo* ref_info,
110c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong               size_t offset,
111c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong               HInstruction* index,
112c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong               int16_t declaring_class_def_index)
113c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      : ref_info_(ref_info),
114c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        offset_(offset),
115c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        index_(index),
116c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        declaring_class_def_index_(declaring_class_def_index),
117c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        value_killed_by_loop_side_effects_(true) {
118c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    DCHECK(ref_info != nullptr);
119c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    DCHECK((offset == kInvalidFieldOffset && index != nullptr) ||
120c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong           (offset != kInvalidFieldOffset && index == nullptr));
121c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    if (ref_info->IsSingleton() && !IsArrayElement()) {
122c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      // Assume this location's value cannot be killed by loop side effects
123c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      // until proven otherwise.
124c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      value_killed_by_loop_side_effects_ = false;
125c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
126c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
127c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
128c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  ReferenceInfo* GetReferenceInfo() const { return ref_info_; }
129c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  size_t GetOffset() const { return offset_; }
130c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  HInstruction* GetIndex() const { return index_; }
131c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
132c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  // Returns the definition of declaring class' dex index.
133c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  // It's kDeclaringClassDefIndexForArrays for an array element.
134c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  int16_t GetDeclaringClassDefIndex() const {
135c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return declaring_class_def_index_;
136c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
137c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
138c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  bool IsArrayElement() const {
139c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return index_ != nullptr;
140c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
141c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
142c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  bool IsValueKilledByLoopSideEffects() const {
143c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return value_killed_by_loop_side_effects_;
144c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
145c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
146c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void SetValueKilledByLoopSideEffects(bool val) {
147c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    value_killed_by_loop_side_effects_ = val;
148c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
149c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
150c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong private:
151c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  ReferenceInfo* const ref_info_;      // reference for instance/static field or array access.
152c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  const size_t offset_;                // offset of static/instance field.
153c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  HInstruction* const index_;          // index of an array element.
154c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  const int16_t declaring_class_def_index_;  // declaring class's def's dex index.
155c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  bool value_killed_by_loop_side_effects_;   // value of this location may be killed by loop
156c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong                                             // side effects because this location is stored
157c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong                                             // into inside a loop. This gives
158c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong                                             // better info on whether a singleton's location
159c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong                                             // value may be killed by loop side effects.
160c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
161c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  DISALLOW_COPY_AND_ASSIGN(HeapLocation);
162c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong};
163c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
164c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong// A HeapLocationCollector collects all relevant heap locations and keeps
165c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong// an aliasing matrix for all locations.
166c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhongclass HeapLocationCollector : public HGraphVisitor {
167c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong public:
168c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  static constexpr size_t kHeapLocationNotFound = -1;
169c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  // Start with a single uint32_t word. That's enough bits for pair-wise
170c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  // aliasing matrix of 8 heap locations.
171c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  static constexpr uint32_t kInitialAliasingMatrixBitVectorSize = 32;
172c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
173c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  explicit HeapLocationCollector(HGraph* graph)
174c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      : HGraphVisitor(graph),
175c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        ref_info_array_(graph->GetArena()->Adapter(kArenaAllocLSE)),
176c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        heap_locations_(graph->GetArena()->Adapter(kArenaAllocLSE)),
177c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        aliasing_matrix_(graph->GetArena(),
178c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong                         kInitialAliasingMatrixBitVectorSize,
179c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong                         true,
180c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong                         kArenaAllocLSE),
181c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        has_heap_stores_(false),
182c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        has_volatile_(false),
183c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        has_monitor_operations_(false) {}
184c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
185c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void CleanUp() {
186c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    heap_locations_.clear();
187c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    ref_info_array_.clear();
188c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
189c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
190c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  size_t GetNumberOfHeapLocations() const {
191c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return heap_locations_.size();
192c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
193c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
194c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  HeapLocation* GetHeapLocation(size_t index) const {
195c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return heap_locations_[index];
196c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
197c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
198c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  HInstruction* HuntForOriginalReference(HInstruction* ref) const {
199c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    DCHECK(ref != nullptr);
200c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    while (ref->IsNullCheck() || ref->IsBoundType()) {
201c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      ref = ref->InputAt(0);
202c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
203c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return ref;
204c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
205c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
206c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  ReferenceInfo* FindReferenceInfoOf(HInstruction* ref) const {
207c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    for (size_t i = 0; i < ref_info_array_.size(); i++) {
208c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      ReferenceInfo* ref_info = ref_info_array_[i];
209c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      if (ref_info->GetReference() == ref) {
210c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        DCHECK_EQ(i, ref_info->GetPosition());
211c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        return ref_info;
212c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      }
213c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
214c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return nullptr;
215c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
216c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
217c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  bool HasHeapStores() const {
218c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return has_heap_stores_;
219c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
220c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
221c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  bool HasVolatile() const {
222c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return has_volatile_;
223c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
224c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
225c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  bool HasMonitorOps() const {
226c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return has_monitor_operations_;
227c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
228c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
229c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  // Find and return the heap location index in heap_locations_.
230c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  size_t FindHeapLocationIndex(ReferenceInfo* ref_info,
231c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong                               size_t offset,
232c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong                               HInstruction* index,
233c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong                               int16_t declaring_class_def_index) const {
234c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    for (size_t i = 0; i < heap_locations_.size(); i++) {
235c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      HeapLocation* loc = heap_locations_[i];
236c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      if (loc->GetReferenceInfo() == ref_info &&
237c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong          loc->GetOffset() == offset &&
238c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong          loc->GetIndex() == index &&
239c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong          loc->GetDeclaringClassDefIndex() == declaring_class_def_index) {
240c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        return i;
241c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      }
242c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
243c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return kHeapLocationNotFound;
244c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
245c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
246c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  // Returns true if heap_locations_[index1] and heap_locations_[index2] may alias.
247c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  bool MayAlias(size_t index1, size_t index2) const {
248c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    if (index1 < index2) {
249c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      return aliasing_matrix_.IsBitSet(AliasingMatrixPosition(index1, index2));
250c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    } else if (index1 > index2) {
251c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      return aliasing_matrix_.IsBitSet(AliasingMatrixPosition(index2, index1));
252c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    } else {
253c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      DCHECK(false) << "index1 and index2 are expected to be different";
254c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      return true;
255c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
256c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
257c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
258c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void BuildAliasingMatrix() {
259c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    const size_t number_of_locations = heap_locations_.size();
260c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    if (number_of_locations == 0) {
261c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      return;
262c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
263c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    size_t pos = 0;
264c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    // Compute aliasing info between every pair of different heap locations.
265c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    // Save the result in a matrix represented as a BitVector.
266c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    for (size_t i = 0; i < number_of_locations - 1; i++) {
267c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      for (size_t j = i + 1; j < number_of_locations; j++) {
268c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        if (ComputeMayAlias(i, j)) {
269c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong          aliasing_matrix_.SetBit(CheckedAliasingMatrixPosition(i, j, pos));
270c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        }
271c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        pos++;
272c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      }
273c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
274c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
275c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
276c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong private:
277c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  // An allocation cannot alias with a name which already exists at the point
278c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  // of the allocation, such as a parameter or a load happening before the allocation.
279c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  bool MayAliasWithPreexistenceChecking(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) const {
280c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    if (ref_info1->GetReference()->IsNewInstance() || ref_info1->GetReference()->IsNewArray()) {
281c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      // Any reference that can alias with the allocation must appear after it in the block/in
282c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      // the block's successors. In reverse post order, those instructions will be visited after
283c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      // the allocation.
284c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      return ref_info2->GetPosition() >= ref_info1->GetPosition();
285c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
286c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return true;
287c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
288c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
289c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  bool CanReferencesAlias(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) const {
290c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    if (ref_info1 == ref_info2) {
291c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      return true;
292c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    } else if (ref_info1->IsSingleton()) {
293c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      return false;
294c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    } else if (ref_info2->IsSingleton()) {
295c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      return false;
296c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    } else if (!MayAliasWithPreexistenceChecking(ref_info1, ref_info2) ||
297c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        !MayAliasWithPreexistenceChecking(ref_info2, ref_info1)) {
298c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      return false;
299c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
300c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return true;
301c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
302c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
303c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  // `index1` and `index2` are indices in the array of collected heap locations.
304c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  // Returns the position in the bit vector that tracks whether the two heap
305c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  // locations may alias.
306c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  size_t AliasingMatrixPosition(size_t index1, size_t index2) const {
307c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    DCHECK(index2 > index1);
308c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    const size_t number_of_locations = heap_locations_.size();
309c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    // It's (num_of_locations - 1) + ... + (num_of_locations - index1) + (index2 - index1 - 1).
310c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return (number_of_locations * index1 - (1 + index1) * index1 / 2 + (index2 - index1 - 1));
311c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
312c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
313c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  // An additional position is passed in to make sure the calculated position is correct.
314c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  size_t CheckedAliasingMatrixPosition(size_t index1, size_t index2, size_t position) {
315c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    size_t calculated_position = AliasingMatrixPosition(index1, index2);
316c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    DCHECK_EQ(calculated_position, position);
317c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return calculated_position;
318c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
319c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
320c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  // Compute if two locations may alias to each other.
321c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  bool ComputeMayAlias(size_t index1, size_t index2) const {
322c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    HeapLocation* loc1 = heap_locations_[index1];
323c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    HeapLocation* loc2 = heap_locations_[index2];
324c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    if (loc1->GetOffset() != loc2->GetOffset()) {
325c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      // Either two different instance fields, or one is an instance
326c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      // field and the other is an array element.
327c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      return false;
328c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
329c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    if (loc1->GetDeclaringClassDefIndex() != loc2->GetDeclaringClassDefIndex()) {
330c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      // Different types.
331c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      return false;
332c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
333c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    if (!CanReferencesAlias(loc1->GetReferenceInfo(), loc2->GetReferenceInfo())) {
334c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      return false;
335c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
336c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    if (loc1->IsArrayElement() && loc2->IsArrayElement()) {
337c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      HInstruction* array_index1 = loc1->GetIndex();
338c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      HInstruction* array_index2 = loc2->GetIndex();
339c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      DCHECK(array_index1 != nullptr);
340c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      DCHECK(array_index2 != nullptr);
341c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      if (array_index1->IsIntConstant() &&
342c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong          array_index2->IsIntConstant() &&
343c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong          array_index1->AsIntConstant()->GetValue() != array_index2->AsIntConstant()->GetValue()) {
344c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        // Different constant indices do not alias.
345c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        return false;
346c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      }
347c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      ReferenceInfo* ref_info = loc1->GetReferenceInfo();
348c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      ref_info->SetHasIndexAliasing(true);
349c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
350c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return true;
351c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
352c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
353c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  ReferenceInfo* GetOrCreateReferenceInfo(HInstruction* instruction) {
354c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    ReferenceInfo* ref_info = FindReferenceInfoOf(instruction);
355c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    if (ref_info == nullptr) {
356c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      size_t pos = ref_info_array_.size();
357c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      ref_info = new (GetGraph()->GetArena()) ReferenceInfo(instruction, pos);
358c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      ref_info_array_.push_back(ref_info);
359c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
360c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return ref_info;
361c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
362c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
363c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void CreateReferenceInfoForReferenceType(HInstruction* instruction) {
364c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    if (instruction->GetType() != Primitive::kPrimNot) {
365c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      return;
366c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
367c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    DCHECK(FindReferenceInfoOf(instruction) == nullptr);
368c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    GetOrCreateReferenceInfo(instruction);
369c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
370c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
371c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  HeapLocation* GetOrCreateHeapLocation(HInstruction* ref,
372c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong                                        size_t offset,
373c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong                                        HInstruction* index,
374c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong                                        int16_t declaring_class_def_index) {
375c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    HInstruction* original_ref = HuntForOriginalReference(ref);
376c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    ReferenceInfo* ref_info = GetOrCreateReferenceInfo(original_ref);
377c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    size_t heap_location_idx = FindHeapLocationIndex(
378c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        ref_info, offset, index, declaring_class_def_index);
379c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    if (heap_location_idx == kHeapLocationNotFound) {
380c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      HeapLocation* heap_loc = new (GetGraph()->GetArena())
381c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong          HeapLocation(ref_info, offset, index, declaring_class_def_index);
382c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      heap_locations_.push_back(heap_loc);
383c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      return heap_loc;
384c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
385c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return heap_locations_[heap_location_idx];
386c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
387c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
388c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  HeapLocation* VisitFieldAccess(HInstruction* ref, const FieldInfo& field_info) {
389c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    if (field_info.IsVolatile()) {
390c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      has_volatile_ = true;
391c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
392c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    const uint16_t declaring_class_def_index = field_info.GetDeclaringClassDefIndex();
393c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    const size_t offset = field_info.GetFieldOffset().SizeValue();
394c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return GetOrCreateHeapLocation(ref, offset, nullptr, declaring_class_def_index);
395c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
396c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
397c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void VisitArrayAccess(HInstruction* array, HInstruction* index) {
398c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    GetOrCreateHeapLocation(array, HeapLocation::kInvalidFieldOffset,
399c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        index, HeapLocation::kDeclaringClassDefIndexForArrays);
400c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
401c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
402c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void VisitInstanceFieldGet(HInstanceFieldGet* instruction) OVERRIDE {
403c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo());
404c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    CreateReferenceInfoForReferenceType(instruction);
405c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
406c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
407c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void VisitInstanceFieldSet(HInstanceFieldSet* instruction) OVERRIDE {
408c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    HeapLocation* location = VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo());
409c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    has_heap_stores_ = true;
410c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    if (location->GetReferenceInfo()->IsSingleton()) {
411c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      // A singleton's location value may be killed by loop side effects if it's
412c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      // defined before that loop, and it's stored into inside that loop.
413c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      HLoopInformation* loop_info = instruction->GetBlock()->GetLoopInformation();
414c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      if (loop_info != nullptr) {
415c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        HInstruction* ref = location->GetReferenceInfo()->GetReference();
416c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        DCHECK(ref->IsNewInstance());
417c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        if (loop_info->IsDefinedOutOfTheLoop(ref)) {
418c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong          // ref's location value may be killed by this loop's side effects.
419c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong          location->SetValueKilledByLoopSideEffects(true);
420c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        } else {
421c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong          // ref is defined inside this loop so this loop's side effects cannot
422c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong          // kill its location value at the loop header since ref/its location doesn't
423c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong          // exist yet at the loop header.
424c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong        }
425c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      }
426c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    } else {
427c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      // For non-singletons, value_killed_by_loop_side_effects_ is inited to
428c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      // true.
429c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      DCHECK_EQ(location->IsValueKilledByLoopSideEffects(), true);
430c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    }
431c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
432c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
433c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void VisitStaticFieldGet(HStaticFieldGet* instruction) OVERRIDE {
434c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo());
435c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    CreateReferenceInfoForReferenceType(instruction);
436c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
437c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
438c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void VisitStaticFieldSet(HStaticFieldSet* instruction) OVERRIDE {
439c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo());
440c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    has_heap_stores_ = true;
441c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
442c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
443c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  // We intentionally don't collect HUnresolvedInstanceField/HUnresolvedStaticField accesses
444c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  // since we cannot accurately track the fields.
445c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
446c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void VisitArrayGet(HArrayGet* instruction) OVERRIDE {
447c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    VisitArrayAccess(instruction->InputAt(0), instruction->InputAt(1));
448c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    CreateReferenceInfoForReferenceType(instruction);
449c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
450c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
451c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void VisitArraySet(HArraySet* instruction) OVERRIDE {
452c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    VisitArrayAccess(instruction->InputAt(0), instruction->InputAt(1));
453c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    has_heap_stores_ = true;
454c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
455c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
456c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void VisitNewInstance(HNewInstance* new_instance) OVERRIDE {
457c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    // Any references appearing in the ref_info_array_ so far cannot alias with new_instance.
458c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    CreateReferenceInfoForReferenceType(new_instance);
459c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
460c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
461c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* instruction) OVERRIDE {
462c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    CreateReferenceInfoForReferenceType(instruction);
463c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
464c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
465c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void VisitInvokeVirtual(HInvokeVirtual* instruction) OVERRIDE {
466c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    CreateReferenceInfoForReferenceType(instruction);
467c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
468c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
469c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void VisitInvokeInterface(HInvokeInterface* instruction) OVERRIDE {
470c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    CreateReferenceInfoForReferenceType(instruction);
471c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
472c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
473c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void VisitParameterValue(HParameterValue* instruction) OVERRIDE {
474c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    CreateReferenceInfoForReferenceType(instruction);
475c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
476c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
477c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void VisitSelect(HSelect* instruction) OVERRIDE {
478c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    CreateReferenceInfoForReferenceType(instruction);
479c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
480c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
481c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void VisitMonitorOperation(HMonitorOperation* monitor ATTRIBUTE_UNUSED) OVERRIDE {
482c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    has_monitor_operations_ = true;
483c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
484c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
485c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  ArenaVector<ReferenceInfo*> ref_info_array_;   // All references used for heap accesses.
486c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  ArenaVector<HeapLocation*> heap_locations_;    // All heap locations.
487c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  ArenaBitVector aliasing_matrix_;    // aliasing info between each pair of locations.
488c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  bool has_heap_stores_;    // If there is no heap stores, LSE acts as GVN with better
489c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong                            // alias analysis and won't be as effective.
490c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  bool has_volatile_;       // If there are volatile field accesses.
491c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  bool has_monitor_operations_;    // If there are monitor operations.
492c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
493c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  DISALLOW_COPY_AND_ASSIGN(HeapLocationCollector);
494c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong};
495c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
496c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhongclass LoadStoreAnalysis : public HOptimization {
497c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong public:
498c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  explicit LoadStoreAnalysis(HGraph* graph)
499c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    : HOptimization(graph, kLoadStoreAnalysisPassName),
500c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong      heap_location_collector_(graph) {}
501c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
502c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  const HeapLocationCollector& GetHeapLocationCollector() const {
503c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong    return heap_location_collector_;
504c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  }
505c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
506c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  void Run() OVERRIDE;
507c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
508c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  static constexpr const char* kLoadStoreAnalysisPassName = "load_store_analysis";
509c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
510c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong private:
511c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  HeapLocationCollector heap_location_collector_;
512c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
513c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong  DISALLOW_COPY_AND_ASSIGN(LoadStoreAnalysis);
514c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong};
515c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
516c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong}  // namespace art
517c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong
518c239a2bb9474a1266c4882638fdb19056370e16dxueliang.zhong#endif  // ART_COMPILER_OPTIMIZING_LOAD_STORE_ANALYSIS_H_
519