1 /*
2 * Copyright (C) 2017 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_analysis.h"
18
19 namespace art {
20
21 // A cap for the number of heap locations to prevent pathological time/space consumption.
22 // The number of heap locations for most of the methods stays below this threshold.
23 constexpr size_t kMaxNumberOfHeapLocations = 32;
24
25 // Test if two integer ranges [l1,h1] and [l2,h2] overlap.
26 // Note that the ranges are inclusive on both ends.
27 // l1|------|h1
28 // l2|------|h2
CanIntegerRangesOverlap(int64_t l1,int64_t h1,int64_t l2,int64_t h2)29 static bool CanIntegerRangesOverlap(int64_t l1, int64_t h1, int64_t l2, int64_t h2) {
30 return std::max(l1, l2) <= std::min(h1, h2);
31 }
32
CanBinaryOpAndIndexAlias(const HBinaryOperation * idx1,const size_t vector_length1,const HInstruction * idx2,const size_t vector_length2)33 static bool CanBinaryOpAndIndexAlias(const HBinaryOperation* idx1,
34 const size_t vector_length1,
35 const HInstruction* idx2,
36 const size_t vector_length2) {
37 if (!IsAddOrSub(idx1)) {
38 // We currently only support Add and Sub operations.
39 return true;
40 }
41 if (idx1->AsBinaryOperation()->GetLeastConstantLeft() != idx2) {
42 // Cannot analyze [i+CONST1] and [j].
43 return true;
44 }
45 if (!idx1->GetConstantRight()->IsIntConstant()) {
46 return true;
47 }
48
49 // Since 'i' are the same in [i+CONST] and [i],
50 // further compare [CONST] and [0].
51 int64_t l1 = idx1->IsAdd() ?
52 idx1->GetConstantRight()->AsIntConstant()->GetValue() :
53 -idx1->GetConstantRight()->AsIntConstant()->GetValue();
54 int64_t l2 = 0;
55 int64_t h1 = l1 + (vector_length1 - 1);
56 int64_t h2 = l2 + (vector_length2 - 1);
57 return CanIntegerRangesOverlap(l1, h1, l2, h2);
58 }
59
CanBinaryOpsAlias(const HBinaryOperation * idx1,const size_t vector_length1,const HBinaryOperation * idx2,const size_t vector_length2)60 static bool CanBinaryOpsAlias(const HBinaryOperation* idx1,
61 const size_t vector_length1,
62 const HBinaryOperation* idx2,
63 const size_t vector_length2) {
64 if (!IsAddOrSub(idx1) || !IsAddOrSub(idx2)) {
65 // We currently only support Add and Sub operations.
66 return true;
67 }
68 if (idx1->AsBinaryOperation()->GetLeastConstantLeft() !=
69 idx2->AsBinaryOperation()->GetLeastConstantLeft()) {
70 // Cannot analyze [i+CONST1] and [j+CONST2].
71 return true;
72 }
73 if (!idx1->GetConstantRight()->IsIntConstant() ||
74 !idx2->GetConstantRight()->IsIntConstant()) {
75 return true;
76 }
77
78 // Since 'i' are the same in [i+CONST1] and [i+CONST2],
79 // further compare [CONST1] and [CONST2].
80 int64_t l1 = idx1->IsAdd() ?
81 idx1->GetConstantRight()->AsIntConstant()->GetValue() :
82 -idx1->GetConstantRight()->AsIntConstant()->GetValue();
83 int64_t l2 = idx2->IsAdd() ?
84 idx2->GetConstantRight()->AsIntConstant()->GetValue() :
85 -idx2->GetConstantRight()->AsIntConstant()->GetValue();
86 int64_t h1 = l1 + (vector_length1 - 1);
87 int64_t h2 = l2 + (vector_length2 - 1);
88 return CanIntegerRangesOverlap(l1, h1, l2, h2);
89 }
90
CanArrayElementsAlias(const HInstruction * idx1,const size_t vector_length1,const HInstruction * idx2,const size_t vector_length2) const91 bool HeapLocationCollector::CanArrayElementsAlias(const HInstruction* idx1,
92 const size_t vector_length1,
93 const HInstruction* idx2,
94 const size_t vector_length2) const {
95 DCHECK(idx1 != nullptr);
96 DCHECK(idx2 != nullptr);
97 DCHECK_GE(vector_length1, HeapLocation::kScalar);
98 DCHECK_GE(vector_length2, HeapLocation::kScalar);
99
100 // [i] and [i].
101 if (idx1 == idx2) {
102 return true;
103 }
104
105 // [CONST1] and [CONST2].
106 if (idx1->IsIntConstant() && idx2->IsIntConstant()) {
107 int64_t l1 = idx1->AsIntConstant()->GetValue();
108 int64_t l2 = idx2->AsIntConstant()->GetValue();
109 // To avoid any overflow in following CONST+vector_length calculation,
110 // use int64_t instead of int32_t.
111 int64_t h1 = l1 + (vector_length1 - 1);
112 int64_t h2 = l2 + (vector_length2 - 1);
113 return CanIntegerRangesOverlap(l1, h1, l2, h2);
114 }
115
116 // [i+CONST] and [i].
117 if (idx1->IsBinaryOperation() &&
118 idx1->AsBinaryOperation()->GetConstantRight() != nullptr &&
119 idx1->AsBinaryOperation()->GetLeastConstantLeft() == idx2) {
120 return CanBinaryOpAndIndexAlias(idx1->AsBinaryOperation(),
121 vector_length1,
122 idx2,
123 vector_length2);
124 }
125
126 // [i] and [i+CONST].
127 if (idx2->IsBinaryOperation() &&
128 idx2->AsBinaryOperation()->GetConstantRight() != nullptr &&
129 idx2->AsBinaryOperation()->GetLeastConstantLeft() == idx1) {
130 return CanBinaryOpAndIndexAlias(idx2->AsBinaryOperation(),
131 vector_length2,
132 idx1,
133 vector_length1);
134 }
135
136 // [i+CONST1] and [i+CONST2].
137 if (idx1->IsBinaryOperation() &&
138 idx1->AsBinaryOperation()->GetConstantRight() != nullptr &&
139 idx2->IsBinaryOperation() &&
140 idx2->AsBinaryOperation()->GetConstantRight() != nullptr) {
141 return CanBinaryOpsAlias(idx1->AsBinaryOperation(),
142 vector_length1,
143 idx2->AsBinaryOperation(),
144 vector_length2);
145 }
146
147 // By default, MAY alias.
148 return true;
149 }
150
Run()151 bool LoadStoreAnalysis::Run() {
152 for (HBasicBlock* block : graph_->GetReversePostOrder()) {
153 heap_location_collector_.VisitBasicBlock(block);
154 }
155
156 if (heap_location_collector_.GetNumberOfHeapLocations() > kMaxNumberOfHeapLocations) {
157 // Bail out if there are too many heap locations to deal with.
158 heap_location_collector_.CleanUp();
159 return false;
160 }
161 if (!heap_location_collector_.HasHeapStores()) {
162 // Without heap stores, this pass would act mostly as GVN on heap accesses.
163 heap_location_collector_.CleanUp();
164 return false;
165 }
166 if (heap_location_collector_.HasVolatile() || heap_location_collector_.HasMonitorOps()) {
167 // Don't do load/store elimination if the method has volatile field accesses or
168 // monitor operations, for now.
169 // TODO: do it right.
170 heap_location_collector_.CleanUp();
171 return false;
172 }
173
174 heap_location_collector_.BuildAliasingMatrix();
175 return true;
176 }
177
178 } // namespace art
179