blob: e1977b1798bc7ab2f86505013c4137676171640c [file] [log] [blame]
Mingyao Yang8df69d42015-10-22 15:40:58 -07001/*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include "load_store_elimination.h"
18#include "side_effects_analysis.h"
19
20#include <iostream>
21
22namespace art {
23
24class ReferenceInfo;
25
26// A cap for the number of heap locations to prevent pathological time/space consumption.
27// The number of heap locations for most of the methods stays below this threshold.
28constexpr size_t kMaxNumberOfHeapLocations = 32;
29
30// A ReferenceInfo contains additional info about a reference such as
31// whether it's a singleton, returned, etc.
32class ReferenceInfo : public ArenaObject<kArenaAllocMisc> {
33 public:
34 ReferenceInfo(HInstruction* reference, size_t pos) : reference_(reference), position_(pos) {
35 is_singleton_ = true;
36 is_singleton_and_not_returned_ = true;
37 if (!reference_->IsNewInstance() && !reference_->IsNewArray()) {
38 // For references not allocated in the method, don't assume anything.
39 is_singleton_ = false;
40 is_singleton_and_not_returned_ = false;
41 return;
42 }
43
44 // Visit all uses to determine if this reference can spread into the heap,
45 // a method call, etc.
46 for (HUseIterator<HInstruction*> use_it(reference_->GetUses());
47 !use_it.Done();
48 use_it.Advance()) {
49 HInstruction* use = use_it.Current()->GetUser();
50 DCHECK(!use->IsNullCheck()) << "NullCheck should have been eliminated";
51 if (use->IsBoundType()) {
52 // BoundType shouldn't normally be necessary for a NewInstance.
53 // Just be conservative for the uncommon cases.
54 is_singleton_ = false;
55 is_singleton_and_not_returned_ = false;
56 return;
57 }
Mingyao Yange5c71f92016-02-02 20:10:32 -080058 if (use->IsPhi() || use->IsSelect() || use->IsInvoke() ||
Mingyao Yang8df69d42015-10-22 15:40:58 -070059 (use->IsInstanceFieldSet() && (reference_ == use->InputAt(1))) ||
60 (use->IsUnresolvedInstanceFieldSet() && (reference_ == use->InputAt(1))) ||
61 (use->IsStaticFieldSet() && (reference_ == use->InputAt(1))) ||
Nicolas Geoffrayd9309292015-10-31 22:21:31 +000062 (use->IsUnresolvedStaticFieldSet() && (reference_ == use->InputAt(0))) ||
Mingyao Yang8df69d42015-10-22 15:40:58 -070063 (use->IsArraySet() && (reference_ == use->InputAt(2)))) {
Mingyao Yang40bcb932016-02-03 05:46:57 -080064 // reference_ is merged to HPhi/HSelect, passed to a callee, or stored to heap.
Mingyao Yang8df69d42015-10-22 15:40:58 -070065 // reference_ isn't the only name that can refer to its value anymore.
66 is_singleton_ = false;
67 is_singleton_and_not_returned_ = false;
68 return;
69 }
70 if (use->IsReturn()) {
71 is_singleton_and_not_returned_ = false;
72 }
73 }
74 }
75
76 HInstruction* GetReference() const {
77 return reference_;
78 }
79
80 size_t GetPosition() const {
81 return position_;
82 }
83
84 // Returns true if reference_ is the only name that can refer to its value during
85 // the lifetime of the method. So it's guaranteed to not have any alias in
86 // the method (including its callees).
87 bool IsSingleton() const {
88 return is_singleton_;
89 }
90
91 // Returns true if reference_ is a singleton and not returned to the caller.
92 // The allocation and stores into reference_ may be eliminated for such cases.
93 bool IsSingletonAndNotReturned() const {
94 return is_singleton_and_not_returned_;
95 }
96
97 private:
98 HInstruction* const reference_;
99 const size_t position_; // position in HeapLocationCollector's ref_info_array_.
100 bool is_singleton_; // can only be referred to by a single name in the method.
101 bool is_singleton_and_not_returned_; // reference_ is singleton and not returned to caller.
102
103 DISALLOW_COPY_AND_ASSIGN(ReferenceInfo);
104};
105
106// A heap location is a reference-offset/index pair that a value can be loaded from
107// or stored to.
108class HeapLocation : public ArenaObject<kArenaAllocMisc> {
109 public:
110 static constexpr size_t kInvalidFieldOffset = -1;
111
112 // TODO: more fine-grained array types.
113 static constexpr int16_t kDeclaringClassDefIndexForArrays = -1;
114
115 HeapLocation(ReferenceInfo* ref_info,
116 size_t offset,
117 HInstruction* index,
118 int16_t declaring_class_def_index)
119 : ref_info_(ref_info),
120 offset_(offset),
121 index_(index),
Mingyao Yang803cbb92015-12-01 12:24:36 -0800122 declaring_class_def_index_(declaring_class_def_index),
123 value_killed_by_loop_side_effects_(true) {
Mingyao Yang8df69d42015-10-22 15:40:58 -0700124 DCHECK(ref_info != nullptr);
125 DCHECK((offset == kInvalidFieldOffset && index != nullptr) ||
126 (offset != kInvalidFieldOffset && index == nullptr));
Mingyao Yang803cbb92015-12-01 12:24:36 -0800127 if (ref_info->IsSingleton() && !IsArrayElement()) {
128 // Assume this location's value cannot be killed by loop side effects
129 // until proven otherwise.
130 value_killed_by_loop_side_effects_ = false;
131 }
Mingyao Yang8df69d42015-10-22 15:40:58 -0700132 }
133
134 ReferenceInfo* GetReferenceInfo() const { return ref_info_; }
135 size_t GetOffset() const { return offset_; }
136 HInstruction* GetIndex() const { return index_; }
137
138 // Returns the definition of declaring class' dex index.
139 // It's kDeclaringClassDefIndexForArrays for an array element.
140 int16_t GetDeclaringClassDefIndex() const {
141 return declaring_class_def_index_;
142 }
143
144 bool IsArrayElement() const {
145 return index_ != nullptr;
146 }
147
Mingyao Yang803cbb92015-12-01 12:24:36 -0800148 bool IsValueKilledByLoopSideEffects() const {
149 return value_killed_by_loop_side_effects_;
150 }
151
152 void SetValueKilledByLoopSideEffects(bool val) {
153 value_killed_by_loop_side_effects_ = val;
154 }
155
Mingyao Yang8df69d42015-10-22 15:40:58 -0700156 private:
157 ReferenceInfo* const ref_info_; // reference for instance/static field or array access.
158 const size_t offset_; // offset of static/instance field.
159 HInstruction* const index_; // index of an array element.
160 const int16_t declaring_class_def_index_; // declaring class's def's dex index.
Mingyao Yang803cbb92015-12-01 12:24:36 -0800161 bool value_killed_by_loop_side_effects_; // value of this location may be killed by loop
162 // side effects because this location is stored
163 // into inside a loop.
Mingyao Yang8df69d42015-10-22 15:40:58 -0700164
165 DISALLOW_COPY_AND_ASSIGN(HeapLocation);
166};
167
168static HInstruction* HuntForOriginalReference(HInstruction* ref) {
169 DCHECK(ref != nullptr);
170 while (ref->IsNullCheck() || ref->IsBoundType()) {
171 ref = ref->InputAt(0);
172 }
173 return ref;
174}
175
176// A HeapLocationCollector collects all relevant heap locations and keeps
177// an aliasing matrix for all locations.
178class HeapLocationCollector : public HGraphVisitor {
179 public:
180 static constexpr size_t kHeapLocationNotFound = -1;
181 // Start with a single uint32_t word. That's enough bits for pair-wise
182 // aliasing matrix of 8 heap locations.
183 static constexpr uint32_t kInitialAliasingMatrixBitVectorSize = 32;
184
185 explicit HeapLocationCollector(HGraph* graph)
186 : HGraphVisitor(graph),
187 ref_info_array_(graph->GetArena()->Adapter(kArenaAllocLSE)),
188 heap_locations_(graph->GetArena()->Adapter(kArenaAllocLSE)),
Vladimir Markof6a35de2016-03-21 12:01:50 +0000189 aliasing_matrix_(graph->GetArena(),
190 kInitialAliasingMatrixBitVectorSize,
191 true,
192 kArenaAllocLSE),
Mingyao Yang8df69d42015-10-22 15:40:58 -0700193 has_heap_stores_(false),
194 has_volatile_(false),
195 has_monitor_operations_(false),
196 may_deoptimize_(false) {}
197
198 size_t GetNumberOfHeapLocations() const {
199 return heap_locations_.size();
200 }
201
202 HeapLocation* GetHeapLocation(size_t index) const {
203 return heap_locations_[index];
204 }
205
206 ReferenceInfo* FindReferenceInfoOf(HInstruction* ref) const {
207 for (size_t i = 0; i < ref_info_array_.size(); i++) {
208 ReferenceInfo* ref_info = ref_info_array_[i];
209 if (ref_info->GetReference() == ref) {
210 DCHECK_EQ(i, ref_info->GetPosition());
211 return ref_info;
212 }
213 }
214 return nullptr;
215 }
216
217 bool HasHeapStores() const {
218 return has_heap_stores_;
219 }
220
221 bool HasVolatile() const {
222 return has_volatile_;
223 }
224
225 bool HasMonitorOps() const {
226 return has_monitor_operations_;
227 }
228
229 // Returns whether this method may be deoptimized.
230 // Currently we don't have meta data support for deoptimizing
231 // a method that eliminates allocations/stores.
232 bool MayDeoptimize() const {
233 return may_deoptimize_;
234 }
235
236 // Find and return the heap location index in heap_locations_.
237 size_t FindHeapLocationIndex(ReferenceInfo* ref_info,
238 size_t offset,
239 HInstruction* index,
240 int16_t declaring_class_def_index) const {
241 for (size_t i = 0; i < heap_locations_.size(); i++) {
242 HeapLocation* loc = heap_locations_[i];
243 if (loc->GetReferenceInfo() == ref_info &&
244 loc->GetOffset() == offset &&
245 loc->GetIndex() == index &&
246 loc->GetDeclaringClassDefIndex() == declaring_class_def_index) {
247 return i;
248 }
249 }
250 return kHeapLocationNotFound;
251 }
252
253 // Returns true if heap_locations_[index1] and heap_locations_[index2] may alias.
254 bool MayAlias(size_t index1, size_t index2) const {
255 if (index1 < index2) {
256 return aliasing_matrix_.IsBitSet(AliasingMatrixPosition(index1, index2));
257 } else if (index1 > index2) {
258 return aliasing_matrix_.IsBitSet(AliasingMatrixPosition(index2, index1));
259 } else {
260 DCHECK(false) << "index1 and index2 are expected to be different";
261 return true;
262 }
263 }
264
265 void BuildAliasingMatrix() {
266 const size_t number_of_locations = heap_locations_.size();
267 if (number_of_locations == 0) {
268 return;
269 }
270 size_t pos = 0;
271 // Compute aliasing info between every pair of different heap locations.
272 // Save the result in a matrix represented as a BitVector.
273 for (size_t i = 0; i < number_of_locations - 1; i++) {
274 for (size_t j = i + 1; j < number_of_locations; j++) {
275 if (ComputeMayAlias(i, j)) {
276 aliasing_matrix_.SetBit(CheckedAliasingMatrixPosition(i, j, pos));
277 }
278 pos++;
279 }
280 }
281 }
282
283 private:
284 // An allocation cannot alias with a name which already exists at the point
285 // of the allocation, such as a parameter or a load happening before the allocation.
286 bool MayAliasWithPreexistenceChecking(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) const {
287 if (ref_info1->GetReference()->IsNewInstance() || ref_info1->GetReference()->IsNewArray()) {
288 // Any reference that can alias with the allocation must appear after it in the block/in
289 // the block's successors. In reverse post order, those instructions will be visited after
290 // the allocation.
291 return ref_info2->GetPosition() >= ref_info1->GetPosition();
292 }
293 return true;
294 }
295
296 bool CanReferencesAlias(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) const {
297 if (ref_info1 == ref_info2) {
298 return true;
299 } else if (ref_info1->IsSingleton()) {
300 return false;
301 } else if (ref_info2->IsSingleton()) {
302 return false;
303 } else if (!MayAliasWithPreexistenceChecking(ref_info1, ref_info2) ||
304 !MayAliasWithPreexistenceChecking(ref_info2, ref_info1)) {
305 return false;
306 }
307 return true;
308 }
309
310 // `index1` and `index2` are indices in the array of collected heap locations.
311 // Returns the position in the bit vector that tracks whether the two heap
312 // locations may alias.
313 size_t AliasingMatrixPosition(size_t index1, size_t index2) const {
314 DCHECK(index2 > index1);
315 const size_t number_of_locations = heap_locations_.size();
316 // It's (num_of_locations - 1) + ... + (num_of_locations - index1) + (index2 - index1 - 1).
317 return (number_of_locations * index1 - (1 + index1) * index1 / 2 + (index2 - index1 - 1));
318 }
319
320 // An additional position is passed in to make sure the calculated position is correct.
321 size_t CheckedAliasingMatrixPosition(size_t index1, size_t index2, size_t position) {
322 size_t calculated_position = AliasingMatrixPosition(index1, index2);
323 DCHECK_EQ(calculated_position, position);
324 return calculated_position;
325 }
326
327 // Compute if two locations may alias to each other.
328 bool ComputeMayAlias(size_t index1, size_t index2) const {
329 HeapLocation* loc1 = heap_locations_[index1];
330 HeapLocation* loc2 = heap_locations_[index2];
331 if (loc1->GetOffset() != loc2->GetOffset()) {
332 // Either two different instance fields, or one is an instance
333 // field and the other is an array element.
334 return false;
335 }
336 if (loc1->GetDeclaringClassDefIndex() != loc2->GetDeclaringClassDefIndex()) {
337 // Different types.
338 return false;
339 }
340 if (!CanReferencesAlias(loc1->GetReferenceInfo(), loc2->GetReferenceInfo())) {
341 return false;
342 }
343 if (loc1->IsArrayElement() && loc2->IsArrayElement()) {
344 HInstruction* array_index1 = loc1->GetIndex();
345 HInstruction* array_index2 = loc2->GetIndex();
346 DCHECK(array_index1 != nullptr);
347 DCHECK(array_index2 != nullptr);
348 if (array_index1->IsIntConstant() &&
349 array_index2->IsIntConstant() &&
350 array_index1->AsIntConstant()->GetValue() != array_index2->AsIntConstant()->GetValue()) {
351 // Different constant indices do not alias.
352 return false;
353 }
354 }
355 return true;
356 }
357
Mingyao Yang8ab1d642015-12-03 14:11:15 -0800358 ReferenceInfo* GetOrCreateReferenceInfo(HInstruction* instruction) {
359 ReferenceInfo* ref_info = FindReferenceInfoOf(instruction);
Mingyao Yang8df69d42015-10-22 15:40:58 -0700360 if (ref_info == nullptr) {
361 size_t pos = ref_info_array_.size();
Mingyao Yang8ab1d642015-12-03 14:11:15 -0800362 ref_info = new (GetGraph()->GetArena()) ReferenceInfo(instruction, pos);
Mingyao Yang8df69d42015-10-22 15:40:58 -0700363 ref_info_array_.push_back(ref_info);
364 }
365 return ref_info;
366 }
367
Mingyao Yang8ab1d642015-12-03 14:11:15 -0800368 void CreateReferenceInfoForReferenceType(HInstruction* instruction) {
369 if (instruction->GetType() != Primitive::kPrimNot) {
370 return;
371 }
372 DCHECK(FindReferenceInfoOf(instruction) == nullptr);
373 GetOrCreateReferenceInfo(instruction);
374 }
375
Mingyao Yang8df69d42015-10-22 15:40:58 -0700376 HeapLocation* GetOrCreateHeapLocation(HInstruction* ref,
377 size_t offset,
378 HInstruction* index,
379 int16_t declaring_class_def_index) {
380 HInstruction* original_ref = HuntForOriginalReference(ref);
381 ReferenceInfo* ref_info = GetOrCreateReferenceInfo(original_ref);
382 size_t heap_location_idx = FindHeapLocationIndex(
383 ref_info, offset, index, declaring_class_def_index);
384 if (heap_location_idx == kHeapLocationNotFound) {
385 HeapLocation* heap_loc = new (GetGraph()->GetArena())
386 HeapLocation(ref_info, offset, index, declaring_class_def_index);
387 heap_locations_.push_back(heap_loc);
388 return heap_loc;
389 }
390 return heap_locations_[heap_location_idx];
391 }
392
Mingyao Yang803cbb92015-12-01 12:24:36 -0800393 HeapLocation* VisitFieldAccess(HInstruction* ref, const FieldInfo& field_info) {
Mingyao Yang8df69d42015-10-22 15:40:58 -0700394 if (field_info.IsVolatile()) {
395 has_volatile_ = true;
396 }
397 const uint16_t declaring_class_def_index = field_info.GetDeclaringClassDefIndex();
398 const size_t offset = field_info.GetFieldOffset().SizeValue();
Mingyao Yang803cbb92015-12-01 12:24:36 -0800399 return GetOrCreateHeapLocation(ref, offset, nullptr, declaring_class_def_index);
Mingyao Yang8df69d42015-10-22 15:40:58 -0700400 }
401
402 void VisitArrayAccess(HInstruction* array, HInstruction* index) {
403 GetOrCreateHeapLocation(array, HeapLocation::kInvalidFieldOffset,
404 index, HeapLocation::kDeclaringClassDefIndexForArrays);
405 }
406
407 void VisitInstanceFieldGet(HInstanceFieldGet* instruction) OVERRIDE {
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800408 VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo());
Mingyao Yang8ab1d642015-12-03 14:11:15 -0800409 CreateReferenceInfoForReferenceType(instruction);
Mingyao Yang8df69d42015-10-22 15:40:58 -0700410 }
411
412 void VisitInstanceFieldSet(HInstanceFieldSet* instruction) OVERRIDE {
Mingyao Yang803cbb92015-12-01 12:24:36 -0800413 HeapLocation* location = VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo());
Mingyao Yang8df69d42015-10-22 15:40:58 -0700414 has_heap_stores_ = true;
Mingyao Yang803cbb92015-12-01 12:24:36 -0800415 if (instruction->GetBlock()->GetLoopInformation() != nullptr) {
416 location->SetValueKilledByLoopSideEffects(true);
417 }
Mingyao Yang8df69d42015-10-22 15:40:58 -0700418 }
419
420 void VisitStaticFieldGet(HStaticFieldGet* instruction) OVERRIDE {
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800421 VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo());
Mingyao Yang8ab1d642015-12-03 14:11:15 -0800422 CreateReferenceInfoForReferenceType(instruction);
Mingyao Yang8df69d42015-10-22 15:40:58 -0700423 }
424
425 void VisitStaticFieldSet(HStaticFieldSet* instruction) OVERRIDE {
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800426 VisitFieldAccess(instruction->InputAt(0), instruction->GetFieldInfo());
Mingyao Yang8df69d42015-10-22 15:40:58 -0700427 has_heap_stores_ = true;
428 }
429
430 // We intentionally don't collect HUnresolvedInstanceField/HUnresolvedStaticField accesses
431 // since we cannot accurately track the fields.
432
433 void VisitArrayGet(HArrayGet* instruction) OVERRIDE {
434 VisitArrayAccess(instruction->InputAt(0), instruction->InputAt(1));
Mingyao Yang8ab1d642015-12-03 14:11:15 -0800435 CreateReferenceInfoForReferenceType(instruction);
Mingyao Yang8df69d42015-10-22 15:40:58 -0700436 }
437
438 void VisitArraySet(HArraySet* instruction) OVERRIDE {
439 VisitArrayAccess(instruction->InputAt(0), instruction->InputAt(1));
440 has_heap_stores_ = true;
441 }
442
443 void VisitNewInstance(HNewInstance* new_instance) OVERRIDE {
444 // Any references appearing in the ref_info_array_ so far cannot alias with new_instance.
Mingyao Yang8ab1d642015-12-03 14:11:15 -0800445 CreateReferenceInfoForReferenceType(new_instance);
446 }
447
448 void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* instruction) OVERRIDE {
449 CreateReferenceInfoForReferenceType(instruction);
450 }
451
452 void VisitInvokeVirtual(HInvokeVirtual* instruction) OVERRIDE {
453 CreateReferenceInfoForReferenceType(instruction);
454 }
455
456 void VisitInvokeInterface(HInvokeInterface* instruction) OVERRIDE {
457 CreateReferenceInfoForReferenceType(instruction);
458 }
459
460 void VisitParameterValue(HParameterValue* instruction) OVERRIDE {
461 CreateReferenceInfoForReferenceType(instruction);
Mingyao Yang8df69d42015-10-22 15:40:58 -0700462 }
463
Mingyao Yang40bcb932016-02-03 05:46:57 -0800464 void VisitSelect(HSelect* instruction) OVERRIDE {
465 CreateReferenceInfoForReferenceType(instruction);
466 }
467
Mingyao Yang8df69d42015-10-22 15:40:58 -0700468 void VisitDeoptimize(HDeoptimize* instruction ATTRIBUTE_UNUSED) OVERRIDE {
469 may_deoptimize_ = true;
470 }
471
472 void VisitMonitorOperation(HMonitorOperation* monitor ATTRIBUTE_UNUSED) OVERRIDE {
473 has_monitor_operations_ = true;
474 }
475
476 ArenaVector<ReferenceInfo*> ref_info_array_; // All references used for heap accesses.
477 ArenaVector<HeapLocation*> heap_locations_; // All heap locations.
478 ArenaBitVector aliasing_matrix_; // aliasing info between each pair of locations.
479 bool has_heap_stores_; // If there is no heap stores, LSE acts as GVN with better
480 // alias analysis and won't be as effective.
481 bool has_volatile_; // If there are volatile field accesses.
482 bool has_monitor_operations_; // If there are monitor operations.
483 bool may_deoptimize_;
484
485 DISALLOW_COPY_AND_ASSIGN(HeapLocationCollector);
486};
487
488// An unknown heap value. Loads with such a value in the heap location cannot be eliminated.
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800489// A heap location can be set to kUnknownHeapValue when:
490// - initially set a value.
491// - killed due to aliasing, merging, invocation, or loop side effects.
Mingyao Yang8df69d42015-10-22 15:40:58 -0700492static HInstruction* const kUnknownHeapValue =
493 reinterpret_cast<HInstruction*>(static_cast<uintptr_t>(-1));
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800494
Mingyao Yang8df69d42015-10-22 15:40:58 -0700495// Default heap value after an allocation.
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800496// A heap location can be set to that value right after an allocation.
Mingyao Yang8df69d42015-10-22 15:40:58 -0700497static HInstruction* const kDefaultHeapValue =
498 reinterpret_cast<HInstruction*>(static_cast<uintptr_t>(-2));
499
500class LSEVisitor : public HGraphVisitor {
501 public:
502 LSEVisitor(HGraph* graph,
503 const HeapLocationCollector& heap_locations_collector,
504 const SideEffectsAnalysis& side_effects)
505 : HGraphVisitor(graph),
506 heap_location_collector_(heap_locations_collector),
507 side_effects_(side_effects),
508 heap_values_for_(graph->GetBlocks().size(),
509 ArenaVector<HInstruction*>(heap_locations_collector.
510 GetNumberOfHeapLocations(),
511 kUnknownHeapValue,
512 graph->GetArena()->Adapter(kArenaAllocLSE)),
513 graph->GetArena()->Adapter(kArenaAllocLSE)),
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800514 removed_loads_(graph->GetArena()->Adapter(kArenaAllocLSE)),
515 substitute_instructions_for_loads_(graph->GetArena()->Adapter(kArenaAllocLSE)),
516 possibly_removed_stores_(graph->GetArena()->Adapter(kArenaAllocLSE)),
Mingyao Yang8df69d42015-10-22 15:40:58 -0700517 singleton_new_instances_(graph->GetArena()->Adapter(kArenaAllocLSE)) {
518 }
519
520 void VisitBasicBlock(HBasicBlock* block) OVERRIDE {
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800521 // Populate the heap_values array for this block.
Mingyao Yang8df69d42015-10-22 15:40:58 -0700522 // TODO: try to reuse the heap_values array from one predecessor if possible.
523 if (block->IsLoopHeader()) {
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800524 HandleLoopSideEffects(block);
Mingyao Yang8df69d42015-10-22 15:40:58 -0700525 } else {
526 MergePredecessorValues(block);
527 }
528 HGraphVisitor::VisitBasicBlock(block);
529 }
530
531 // Remove recorded instructions that should be eliminated.
532 void RemoveInstructions() {
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800533 size_t size = removed_loads_.size();
534 DCHECK_EQ(size, substitute_instructions_for_loads_.size());
Mingyao Yang8df69d42015-10-22 15:40:58 -0700535 for (size_t i = 0; i < size; i++) {
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800536 HInstruction* load = removed_loads_[i];
537 DCHECK(load != nullptr);
538 DCHECK(load->IsInstanceFieldGet() ||
539 load->IsStaticFieldGet() ||
540 load->IsArrayGet());
541 HInstruction* substitute = substitute_instructions_for_loads_[i];
542 DCHECK(substitute != nullptr);
543 // Keep tracing substitute till one that's not removed.
544 HInstruction* sub_sub = FindSubstitute(substitute);
545 while (sub_sub != substitute) {
546 substitute = sub_sub;
547 sub_sub = FindSubstitute(substitute);
Mingyao Yang8df69d42015-10-22 15:40:58 -0700548 }
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800549 load->ReplaceWith(substitute);
550 load->GetBlock()->RemoveInstruction(load);
Mingyao Yang8df69d42015-10-22 15:40:58 -0700551 }
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800552
553 // At this point, stores in possibly_removed_stores_ can be safely removed.
554 size = possibly_removed_stores_.size();
555 for (size_t i = 0; i < size; i++) {
556 HInstruction* store = possibly_removed_stores_[i];
557 DCHECK(store->IsInstanceFieldSet() || store->IsStaticFieldSet() || store->IsArraySet());
558 store->GetBlock()->RemoveInstruction(store);
559 }
560
Mingyao Yang8df69d42015-10-22 15:40:58 -0700561 // TODO: remove unnecessary allocations.
562 // Eliminate instructions in singleton_new_instances_ that:
563 // - don't have uses,
564 // - don't have finalizers,
565 // - are instantiable and accessible,
566 // - have no/separate clinit check.
567 }
568
569 private:
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800570 // If heap_values[index] is an instance field store, need to keep the store.
571 // This is necessary if a heap value is killed due to merging, or loop side
572 // effects (which is essentially merging also), since a load later from the
573 // location won't be eliminated.
574 void KeepIfIsStore(HInstruction* heap_value) {
575 if (heap_value == kDefaultHeapValue ||
576 heap_value == kUnknownHeapValue ||
577 !heap_value->IsInstanceFieldSet()) {
578 return;
579 }
580 auto idx = std::find(possibly_removed_stores_.begin(),
581 possibly_removed_stores_.end(), heap_value);
582 if (idx != possibly_removed_stores_.end()) {
583 // Make sure the store is kept.
584 possibly_removed_stores_.erase(idx);
585 }
586 }
587
588 void HandleLoopSideEffects(HBasicBlock* block) {
589 DCHECK(block->IsLoopHeader());
590 int block_id = block->GetBlockId();
591 ArenaVector<HInstruction*>& heap_values = heap_values_for_[block_id];
Nicolas Geoffray15bd2282016-01-05 15:55:41 +0000592
593 // Don't eliminate loads in irreducible loops. This is safe for singletons, because
594 // they are always used by the non-eliminated loop-phi.
595 if (block->GetLoopInformation()->IsIrreducible()) {
596 if (kIsDebugBuild) {
597 for (size_t i = 0; i < heap_values.size(); i++) {
598 DCHECK_EQ(heap_values[i], kUnknownHeapValue);
599 }
600 }
601 return;
602 }
603
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800604 HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader();
605 ArenaVector<HInstruction*>& pre_header_heap_values =
606 heap_values_for_[pre_header->GetBlockId()];
Nicolas Geoffray15bd2282016-01-05 15:55:41 +0000607
Mingyao Yang803cbb92015-12-01 12:24:36 -0800608 // Inherit the values from pre-header.
609 for (size_t i = 0; i < heap_values.size(); i++) {
610 heap_values[i] = pre_header_heap_values[i];
611 }
612
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800613 // We do a single pass in reverse post order. For loops, use the side effects as a hint
614 // to see if the heap values should be killed.
615 if (side_effects_.GetLoopEffects(block).DoesAnyWrite()) {
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800616 for (size_t i = 0; i < heap_values.size(); i++) {
Mingyao Yang803cbb92015-12-01 12:24:36 -0800617 HeapLocation* location = heap_location_collector_.GetHeapLocation(i);
618 ReferenceInfo* ref_info = location->GetReferenceInfo();
619 if (!ref_info->IsSingleton() || location->IsValueKilledByLoopSideEffects()) {
620 // heap value is killed by loop side effects (stored into directly, or due to
621 // aliasing).
622 KeepIfIsStore(pre_header_heap_values[i]);
623 heap_values[i] = kUnknownHeapValue;
624 } else {
625 // A singleton's field that's not stored into inside a loop is invariant throughout
626 // the loop.
627 }
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800628 }
629 }
630 }
631
Mingyao Yang8df69d42015-10-22 15:40:58 -0700632 void MergePredecessorValues(HBasicBlock* block) {
633 const ArenaVector<HBasicBlock*>& predecessors = block->GetPredecessors();
634 if (predecessors.size() == 0) {
635 return;
636 }
637 ArenaVector<HInstruction*>& heap_values = heap_values_for_[block->GetBlockId()];
638 for (size_t i = 0; i < heap_values.size(); i++) {
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800639 HInstruction* pred0_value = heap_values_for_[predecessors[0]->GetBlockId()][i];
640 heap_values[i] = pred0_value;
641 if (pred0_value != kUnknownHeapValue) {
Mingyao Yang8df69d42015-10-22 15:40:58 -0700642 for (size_t j = 1; j < predecessors.size(); j++) {
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800643 HInstruction* pred_value = heap_values_for_[predecessors[j]->GetBlockId()][i];
644 if (pred_value != pred0_value) {
645 heap_values[i] = kUnknownHeapValue;
Mingyao Yang8df69d42015-10-22 15:40:58 -0700646 break;
647 }
648 }
649 }
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800650
651 if (heap_values[i] == kUnknownHeapValue) {
652 // Keep the last store in each predecessor since future loads cannot be eliminated.
653 for (size_t j = 0; j < predecessors.size(); j++) {
654 ArenaVector<HInstruction*>& pred_values = heap_values_for_[predecessors[j]->GetBlockId()];
655 KeepIfIsStore(pred_values[i]);
656 }
657 }
Mingyao Yang8df69d42015-10-22 15:40:58 -0700658 }
659 }
660
661 // `instruction` is being removed. Try to see if the null check on it
662 // can be removed. This can happen if the same value is set in two branches
663 // but not in dominators. Such as:
664 // int[] a = foo();
665 // if () {
666 // a[0] = 2;
667 // } else {
668 // a[0] = 2;
669 // }
670 // // a[0] can now be replaced with constant 2, and the null check on it can be removed.
671 void TryRemovingNullCheck(HInstruction* instruction) {
672 HInstruction* prev = instruction->GetPrevious();
673 if ((prev != nullptr) && prev->IsNullCheck() && (prev == instruction->InputAt(0))) {
674 // Previous instruction is a null check for this instruction. Remove the null check.
675 prev->ReplaceWith(prev->InputAt(0));
676 prev->GetBlock()->RemoveInstruction(prev);
677 }
678 }
679
680 HInstruction* GetDefaultValue(Primitive::Type type) {
681 switch (type) {
682 case Primitive::kPrimNot:
683 return GetGraph()->GetNullConstant();
684 case Primitive::kPrimBoolean:
685 case Primitive::kPrimByte:
686 case Primitive::kPrimChar:
687 case Primitive::kPrimShort:
688 case Primitive::kPrimInt:
689 return GetGraph()->GetIntConstant(0);
690 case Primitive::kPrimLong:
691 return GetGraph()->GetLongConstant(0);
692 case Primitive::kPrimFloat:
693 return GetGraph()->GetFloatConstant(0);
694 case Primitive::kPrimDouble:
695 return GetGraph()->GetDoubleConstant(0);
696 default:
697 UNREACHABLE();
698 }
699 }
700
701 void VisitGetLocation(HInstruction* instruction,
702 HInstruction* ref,
703 size_t offset,
704 HInstruction* index,
705 int16_t declaring_class_def_index) {
706 HInstruction* original_ref = HuntForOriginalReference(ref);
707 ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref);
708 size_t idx = heap_location_collector_.FindHeapLocationIndex(
709 ref_info, offset, index, declaring_class_def_index);
710 DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound);
711 ArenaVector<HInstruction*>& heap_values =
712 heap_values_for_[instruction->GetBlock()->GetBlockId()];
713 HInstruction* heap_value = heap_values[idx];
714 if (heap_value == kDefaultHeapValue) {
715 HInstruction* constant = GetDefaultValue(instruction->GetType());
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800716 removed_loads_.push_back(instruction);
717 substitute_instructions_for_loads_.push_back(constant);
Mingyao Yang8df69d42015-10-22 15:40:58 -0700718 heap_values[idx] = constant;
719 return;
720 }
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800721 if (heap_value != kUnknownHeapValue && heap_value->IsInstanceFieldSet()) {
722 HInstruction* store = heap_value;
723 // This load must be from a singleton since it's from the same field
724 // that a "removed" store puts the value. That store must be to a singleton's field.
725 DCHECK(ref_info->IsSingleton());
726 // Get the real heap value of the store.
727 heap_value = store->InputAt(1);
728 }
David Brazdil15693bf2015-12-16 10:30:45 +0000729 if (heap_value == kUnknownHeapValue) {
730 // Load isn't eliminated. Put the load as the value into the HeapLocation.
731 // This acts like GVN but with better aliasing analysis.
732 heap_values[idx] = instruction;
733 } else {
Nicolas Geoffray03971632016-03-17 10:44:24 +0000734 if (Primitive::PrimitiveKind(heap_value->GetType())
735 != Primitive::PrimitiveKind(instruction->GetType())) {
736 // The only situation where the same heap location has different type is when
737 // we do an array get from a null constant. In order to stay properly typed
738 // we do not merge the array gets.
739 if (kIsDebugBuild) {
740 DCHECK(heap_value->IsArrayGet()) << heap_value->DebugName();
741 DCHECK(instruction->IsArrayGet()) << instruction->DebugName();
742 HInstruction* array = instruction->AsArrayGet()->GetArray();
743 DCHECK(array->IsNullCheck()) << array->DebugName();
Nicolas Geoffrayb1d91572016-03-18 16:25:38 +0000744 HInstruction* input = HuntForOriginalReference(array->InputAt(0));
745 DCHECK(input->IsNullConstant()) << input->DebugName();
Nicolas Geoffray03971632016-03-17 10:44:24 +0000746 array = heap_value->AsArrayGet()->GetArray();
747 DCHECK(array->IsNullCheck()) << array->DebugName();
Nicolas Geoffrayb1d91572016-03-18 16:25:38 +0000748 input = HuntForOriginalReference(array->InputAt(0));
749 DCHECK(input->IsNullConstant()) << input->DebugName();
Nicolas Geoffray03971632016-03-17 10:44:24 +0000750 }
751 return;
752 }
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800753 removed_loads_.push_back(instruction);
754 substitute_instructions_for_loads_.push_back(heap_value);
Mingyao Yang8df69d42015-10-22 15:40:58 -0700755 TryRemovingNullCheck(instruction);
Mingyao Yang8df69d42015-10-22 15:40:58 -0700756 }
757 }
758
759 bool Equal(HInstruction* heap_value, HInstruction* value) {
760 if (heap_value == value) {
761 return true;
762 }
763 if (heap_value == kDefaultHeapValue && GetDefaultValue(value->GetType()) == value) {
764 return true;
765 }
766 return false;
767 }
768
769 void VisitSetLocation(HInstruction* instruction,
770 HInstruction* ref,
771 size_t offset,
772 HInstruction* index,
773 int16_t declaring_class_def_index,
774 HInstruction* value) {
775 HInstruction* original_ref = HuntForOriginalReference(ref);
776 ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref);
777 size_t idx = heap_location_collector_.FindHeapLocationIndex(
778 ref_info, offset, index, declaring_class_def_index);
779 DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound);
780 ArenaVector<HInstruction*>& heap_values =
781 heap_values_for_[instruction->GetBlock()->GetBlockId()];
782 HInstruction* heap_value = heap_values[idx];
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800783 bool same_value = false;
784 bool possibly_redundant = false;
Mingyao Yang8df69d42015-10-22 15:40:58 -0700785 if (Equal(heap_value, value)) {
786 // Store into the heap location with the same value.
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800787 same_value = true;
Mingyao Yang8df69d42015-10-22 15:40:58 -0700788 } else if (index != nullptr) {
789 // For array element, don't eliminate stores since it can be easily aliased
790 // with non-constant index.
791 } else if (!heap_location_collector_.MayDeoptimize() &&
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800792 ref_info->IsSingletonAndNotReturned()) {
793 // Store into a field of a singleton that's not returned. The value cannot be
794 // killed due to aliasing/invocation. It can be redundant since future loads can
795 // directly get the value set by this instruction. The value can still be killed due to
796 // merging or loop side effects. Stores whose values are killed due to merging/loop side
797 // effects later will be removed from possibly_removed_stores_ when that is detected.
798 possibly_redundant = true;
799 HNewInstance* new_instance = ref_info->GetReference()->AsNewInstance();
800 DCHECK(new_instance != nullptr);
801 if (new_instance->IsFinalizable()) {
802 // Finalizable objects escape globally. Need to keep the store.
803 possibly_redundant = false;
Mingyao Yang8df69d42015-10-22 15:40:58 -0700804 } else {
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800805 HLoopInformation* loop_info = instruction->GetBlock()->GetLoopInformation();
806 if (loop_info != nullptr) {
807 // instruction is a store in the loop so the loop must does write.
808 DCHECK(side_effects_.GetLoopEffects(loop_info->GetHeader()).DoesAnyWrite());
Mingyao Yang803cbb92015-12-01 12:24:36 -0800809 // If it's a singleton, IsValueKilledByLoopSideEffects() must be true.
810 DCHECK(!ref_info->IsSingleton() ||
811 heap_location_collector_.GetHeapLocation(idx)->IsValueKilledByLoopSideEffects());
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800812
Mingyao Yang4b467ed2015-11-19 17:04:22 -0800813 if (loop_info->IsDefinedOutOfTheLoop(original_ref)) {
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800814 DCHECK(original_ref->GetBlock()->Dominates(loop_info->GetPreHeader()));
815 // Keep the store since its value may be needed at the loop header.
816 possibly_redundant = false;
817 } else {
818 // The singleton is created inside the loop. Value stored to it isn't needed at
819 // the loop header. This is true for outer loops also.
820 }
821 }
Mingyao Yang8df69d42015-10-22 15:40:58 -0700822 }
Mingyao Yang8df69d42015-10-22 15:40:58 -0700823 }
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800824 if (same_value || possibly_redundant) {
825 possibly_removed_stores_.push_back(instruction);
Mingyao Yang8df69d42015-10-22 15:40:58 -0700826 }
Mingyao Yange9d6e602015-10-23 17:08:42 -0700827
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800828 if (!same_value) {
829 if (possibly_redundant) {
830 DCHECK(instruction->IsInstanceFieldSet());
831 // Put the store as the heap value. If the value is loaded from heap
832 // by a load later, this store isn't really redundant.
833 heap_values[idx] = instruction;
834 } else {
835 heap_values[idx] = value;
836 }
837 }
Mingyao Yang8df69d42015-10-22 15:40:58 -0700838 // This store may kill values in other heap locations due to aliasing.
839 for (size_t i = 0; i < heap_values.size(); i++) {
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800840 if (i == idx) {
841 continue;
842 }
Mingyao Yang8df69d42015-10-22 15:40:58 -0700843 if (heap_values[i] == value) {
844 // Same value should be kept even if aliasing happens.
845 continue;
846 }
847 if (heap_values[i] == kUnknownHeapValue) {
848 // Value is already unknown, no need for aliasing check.
849 continue;
850 }
851 if (heap_location_collector_.MayAlias(i, idx)) {
852 // Kill heap locations that may alias.
853 heap_values[i] = kUnknownHeapValue;
854 }
855 }
856 }
857
858 void VisitInstanceFieldGet(HInstanceFieldGet* instruction) OVERRIDE {
859 HInstruction* obj = instruction->InputAt(0);
860 size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue();
861 int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex();
862 VisitGetLocation(instruction, obj, offset, nullptr, declaring_class_def_index);
863 }
864
865 void VisitInstanceFieldSet(HInstanceFieldSet* instruction) OVERRIDE {
866 HInstruction* obj = instruction->InputAt(0);
867 size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue();
868 int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex();
869 HInstruction* value = instruction->InputAt(1);
870 VisitSetLocation(instruction, obj, offset, nullptr, declaring_class_def_index, value);
871 }
872
873 void VisitStaticFieldGet(HStaticFieldGet* instruction) OVERRIDE {
874 HInstruction* cls = instruction->InputAt(0);
875 size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue();
876 int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex();
877 VisitGetLocation(instruction, cls, offset, nullptr, declaring_class_def_index);
878 }
879
880 void VisitStaticFieldSet(HStaticFieldSet* instruction) OVERRIDE {
881 HInstruction* cls = instruction->InputAt(0);
882 size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue();
883 int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex();
884 HInstruction* value = instruction->InputAt(1);
885 VisitSetLocation(instruction, cls, offset, nullptr, declaring_class_def_index, value);
886 }
887
888 void VisitArrayGet(HArrayGet* instruction) OVERRIDE {
889 HInstruction* array = instruction->InputAt(0);
890 HInstruction* index = instruction->InputAt(1);
891 VisitGetLocation(instruction,
892 array,
893 HeapLocation::kInvalidFieldOffset,
894 index,
895 HeapLocation::kDeclaringClassDefIndexForArrays);
896 }
897
898 void VisitArraySet(HArraySet* instruction) OVERRIDE {
899 HInstruction* array = instruction->InputAt(0);
900 HInstruction* index = instruction->InputAt(1);
901 HInstruction* value = instruction->InputAt(2);
902 VisitSetLocation(instruction,
903 array,
904 HeapLocation::kInvalidFieldOffset,
905 index,
906 HeapLocation::kDeclaringClassDefIndexForArrays,
907 value);
908 }
909
910 void HandleInvoke(HInstruction* invoke) {
911 ArenaVector<HInstruction*>& heap_values =
912 heap_values_for_[invoke->GetBlock()->GetBlockId()];
913 for (size_t i = 0; i < heap_values.size(); i++) {
914 ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo();
915 if (ref_info->IsSingleton()) {
916 // Singleton references cannot be seen by the callee.
917 } else {
918 heap_values[i] = kUnknownHeapValue;
919 }
920 }
921 }
922
923 void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) OVERRIDE {
924 HandleInvoke(invoke);
925 }
926
927 void VisitInvokeVirtual(HInvokeVirtual* invoke) OVERRIDE {
928 HandleInvoke(invoke);
929 }
930
931 void VisitInvokeInterface(HInvokeInterface* invoke) OVERRIDE {
932 HandleInvoke(invoke);
933 }
934
935 void VisitInvokeUnresolved(HInvokeUnresolved* invoke) OVERRIDE {
936 HandleInvoke(invoke);
937 }
938
939 void VisitClinitCheck(HClinitCheck* clinit) OVERRIDE {
940 HandleInvoke(clinit);
941 }
942
943 void VisitUnresolvedInstanceFieldGet(HUnresolvedInstanceFieldGet* instruction) OVERRIDE {
944 // Conservatively treat it as an invocation.
945 HandleInvoke(instruction);
946 }
947
948 void VisitUnresolvedInstanceFieldSet(HUnresolvedInstanceFieldSet* instruction) OVERRIDE {
949 // Conservatively treat it as an invocation.
950 HandleInvoke(instruction);
951 }
952
953 void VisitUnresolvedStaticFieldGet(HUnresolvedStaticFieldGet* instruction) OVERRIDE {
954 // Conservatively treat it as an invocation.
955 HandleInvoke(instruction);
956 }
957
958 void VisitUnresolvedStaticFieldSet(HUnresolvedStaticFieldSet* instruction) OVERRIDE {
959 // Conservatively treat it as an invocation.
960 HandleInvoke(instruction);
961 }
962
963 void VisitNewInstance(HNewInstance* new_instance) OVERRIDE {
964 ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(new_instance);
965 if (ref_info == nullptr) {
966 // new_instance isn't used for field accesses. No need to process it.
967 return;
968 }
969 if (!heap_location_collector_.MayDeoptimize() &&
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800970 ref_info->IsSingletonAndNotReturned() &&
971 !new_instance->IsFinalizable() &&
972 !new_instance->CanThrow()) {
973 // TODO: add new_instance to singleton_new_instances_ and enable allocation elimination.
Mingyao Yang8df69d42015-10-22 15:40:58 -0700974 }
975 ArenaVector<HInstruction*>& heap_values =
976 heap_values_for_[new_instance->GetBlock()->GetBlockId()];
977 for (size_t i = 0; i < heap_values.size(); i++) {
978 HInstruction* ref =
979 heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo()->GetReference();
980 size_t offset = heap_location_collector_.GetHeapLocation(i)->GetOffset();
981 if (ref == new_instance && offset >= mirror::kObjectHeaderSize) {
982 // Instance fields except the header fields are set to default heap values.
983 heap_values[i] = kDefaultHeapValue;
984 }
985 }
986 }
987
988 // Find an instruction's substitute if it should be removed.
989 // Return the same instruction if it should not be removed.
990 HInstruction* FindSubstitute(HInstruction* instruction) {
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800991 size_t size = removed_loads_.size();
Mingyao Yang8df69d42015-10-22 15:40:58 -0700992 for (size_t i = 0; i < size; i++) {
Mingyao Yangfb8464a2015-11-02 10:56:59 -0800993 if (removed_loads_[i] == instruction) {
994 return substitute_instructions_for_loads_[i];
Mingyao Yang8df69d42015-10-22 15:40:58 -0700995 }
996 }
997 return instruction;
998 }
999
1000 const HeapLocationCollector& heap_location_collector_;
1001 const SideEffectsAnalysis& side_effects_;
1002
1003 // One array of heap values for each block.
1004 ArenaVector<ArenaVector<HInstruction*>> heap_values_for_;
1005
1006 // We record the instructions that should be eliminated but may be
1007 // used by heap locations. They'll be removed in the end.
Mingyao Yangfb8464a2015-11-02 10:56:59 -08001008 ArenaVector<HInstruction*> removed_loads_;
1009 ArenaVector<HInstruction*> substitute_instructions_for_loads_;
1010
1011 // Stores in this list may be removed from the list later when it's
1012 // found that the store cannot be eliminated.
1013 ArenaVector<HInstruction*> possibly_removed_stores_;
1014
Mingyao Yang8df69d42015-10-22 15:40:58 -07001015 ArenaVector<HInstruction*> singleton_new_instances_;
1016
1017 DISALLOW_COPY_AND_ASSIGN(LSEVisitor);
1018};
1019
1020void LoadStoreElimination::Run() {
David Brazdil8993caf2015-12-07 10:04:40 +00001021 if (graph_->IsDebuggable() || graph_->HasTryCatch()) {
Mingyao Yang8df69d42015-10-22 15:40:58 -07001022 // Debugger may set heap values or trigger deoptimization of callers.
David Brazdil8993caf2015-12-07 10:04:40 +00001023 // Try/catch support not implemented yet.
Mingyao Yang8df69d42015-10-22 15:40:58 -07001024 // Skip this optimization.
1025 return;
1026 }
1027 HeapLocationCollector heap_location_collector(graph_);
1028 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
1029 heap_location_collector.VisitBasicBlock(it.Current());
1030 }
1031 if (heap_location_collector.GetNumberOfHeapLocations() > kMaxNumberOfHeapLocations) {
1032 // Bail out if there are too many heap locations to deal with.
1033 return;
1034 }
1035 if (!heap_location_collector.HasHeapStores()) {
1036 // Without heap stores, this pass would act mostly as GVN on heap accesses.
1037 return;
1038 }
1039 if (heap_location_collector.HasVolatile() || heap_location_collector.HasMonitorOps()) {
1040 // Don't do load/store elimination if the method has volatile field accesses or
1041 // monitor operations, for now.
1042 // TODO: do it right.
1043 return;
1044 }
1045 heap_location_collector.BuildAliasingMatrix();
1046 LSEVisitor lse_visitor(graph_, heap_location_collector, side_effects_);
1047 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
1048 lse_visitor.VisitBasicBlock(it.Current());
1049 }
1050 lse_visitor.RemoveInstructions();
1051}
1052
1053} // namespace art