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 "base/macros.h"
18 #include "load_store_analysis.h"
19
20 #include <array>
21 #include <string_view>
22 #include <unordered_map>
23 #include <unordered_set>
24
25 #include "base/scoped_arena_allocator.h"
26 #include "class_root.h"
27 #include "dex/dex_file_types.h"
28 #include "dex/method_reference.h"
29 #include "entrypoints/quick/quick_entrypoints_enum.h"
30 #include "gtest/gtest.h"
31 #include "handle.h"
32 #include "handle_scope.h"
33 #include "nodes.h"
34 #include "optimizing/data_type.h"
35 #include "optimizing_unit_test.h"
36 #include "scoped_thread_state_change.h"
37
38 namespace art HIDDEN {
39
40 class LoadStoreAnalysisTest : public CommonCompilerTest, public OptimizingUnitTestHelper {
41 public:
LoadStoreAnalysisTest()42 LoadStoreAnalysisTest() {
43 use_boot_image_ = true; // Make the Runtime creation cheaper.
44 }
45 };
46
TEST_F(LoadStoreAnalysisTest,ArrayHeapLocations)47 TEST_F(LoadStoreAnalysisTest, ArrayHeapLocations) {
48 HBasicBlock* main = InitEntryMainExitGraphWithReturnVoid();
49
50 // entry
51 HInstruction* array = MakeParam(DataType::Type::kReference);
52 HInstruction* index = MakeParam(DataType::Type::kInt32);
53 HInstruction* c1 = graph_->GetIntConstant(1);
54 HInstruction* c2 = graph_->GetIntConstant(2);
55 HInstruction* c3 = graph_->GetIntConstant(3);
56
57 // main
58 HInstruction* array_get1 = MakeArrayGet(main, array, c1, DataType::Type::kInt32);
59 HInstruction* array_get2 = MakeArrayGet(main, array, c2, DataType::Type::kInt32);
60 HInstruction* array_set1 = MakeArraySet(main, array, c1, c3, DataType::Type::kInt32);
61 HInstruction* array_set2 = MakeArraySet(main, array, index, c3, DataType::Type::kInt32);
62
63 // Test HeapLocationCollector initialization.
64 // Should be no heap locations, no operations on the heap.
65 ScopedArenaAllocator allocator(graph_->GetArenaStack());
66 HeapLocationCollector heap_location_collector(graph_, &allocator);
67 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 0U);
68 ASSERT_FALSE(heap_location_collector.HasHeapStores());
69
70 // Test that after visiting the graph_, it must see following heap locations
71 // array[c1], array[c2], array[index]; and it should see heap stores.
72 heap_location_collector.VisitBasicBlock(main);
73 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 3U);
74 ASSERT_TRUE(heap_location_collector.HasHeapStores());
75
76 // Test queries on HeapLocationCollector's ref info and index records.
77 ReferenceInfo* ref = heap_location_collector.FindReferenceInfoOf(array);
78 DataType::Type type = DataType::Type::kInt32;
79 size_t field = HeapLocation::kInvalidFieldOffset;
80 size_t vec = HeapLocation::kScalar;
81 size_t class_def = HeapLocation::kDeclaringClassDefIndexForArrays;
82 const bool is_vec_op = false;
83 size_t loc1 = heap_location_collector.FindHeapLocationIndex(
84 ref, type, field, c1, vec, class_def, is_vec_op);
85 size_t loc2 = heap_location_collector.FindHeapLocationIndex(
86 ref, type, field, c2, vec, class_def, is_vec_op);
87 size_t loc3 = heap_location_collector.FindHeapLocationIndex(
88 ref, type, field, index, vec, class_def, is_vec_op);
89 // must find this reference info for array in HeapLocationCollector.
90 ASSERT_TRUE(ref != nullptr);
91 // must find these heap locations;
92 // and array[1], array[2], array[3] should be different heap locations.
93 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound);
94 ASSERT_TRUE(loc2 != HeapLocationCollector::kHeapLocationNotFound);
95 ASSERT_TRUE(loc3 != HeapLocationCollector::kHeapLocationNotFound);
96 ASSERT_TRUE(loc1 != loc2);
97 ASSERT_TRUE(loc2 != loc3);
98 ASSERT_TRUE(loc1 != loc3);
99
100 // Test alias relationships after building aliasing matrix.
101 // array[1] and array[2] clearly should not alias;
102 // array[index] should alias with the others, because index is an unknow value.
103 heap_location_collector.BuildAliasingMatrix();
104 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
105 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc3));
106 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc3));
107
108 EXPECT_TRUE(CheckGraph());
109 }
110
TEST_F(LoadStoreAnalysisTest,FieldHeapLocations)111 TEST_F(LoadStoreAnalysisTest, FieldHeapLocations) {
112 HBasicBlock* main = InitEntryMainExitGraphWithReturnVoid();
113
114 // entry
115 HInstruction* object = MakeParam(DataType::Type::kReference);
116 HInstruction* c1 = graph_->GetIntConstant(1);
117
118 // main
119 HInstanceFieldSet* set_field10 = MakeIFieldSet(main, object, c1, MemberOffset(10));
120 HInstanceFieldGet* get_field10 =
121 MakeIFieldGet(main, object, DataType::Type::kInt32, MemberOffset(10));
122 HInstanceFieldGet* get_field20 =
123 MakeIFieldGet(main, object, DataType::Type::kInt32, MemberOffset(20));
124
125 // Test HeapLocationCollector initialization.
126 // Should be no heap locations, no operations on the heap.
127 ScopedArenaAllocator allocator(graph_->GetArenaStack());
128 HeapLocationCollector heap_location_collector(graph_, &allocator);
129 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 0U);
130 ASSERT_FALSE(heap_location_collector.HasHeapStores());
131
132 // Test that after visiting the graph, it must see following heap locations
133 // object.field10, object.field20 and it should see heap stores.
134 heap_location_collector.VisitBasicBlock(main);
135 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 2U);
136 ASSERT_TRUE(heap_location_collector.HasHeapStores());
137
138 // Test queries on HeapLocationCollector's ref info and index records.
139 ReferenceInfo* ref = heap_location_collector.FindReferenceInfoOf(object);
140 size_t loc1 = heap_location_collector.GetFieldHeapLocation(object, &get_field10->GetFieldInfo());
141 size_t loc2 = heap_location_collector.GetFieldHeapLocation(object, &get_field20->GetFieldInfo());
142 // must find references info for object and in HeapLocationCollector.
143 ASSERT_TRUE(ref != nullptr);
144 // must find these heap locations.
145 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound);
146 ASSERT_TRUE(loc2 != HeapLocationCollector::kHeapLocationNotFound);
147 // different fields of same object.
148 ASSERT_TRUE(loc1 != loc2);
149 // accesses to different fields of the same object should not alias.
150 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
151
152 EXPECT_TRUE(CheckGraph());
153 }
154
TEST_F(LoadStoreAnalysisTest,ArrayIndexAliasingTest)155 TEST_F(LoadStoreAnalysisTest, ArrayIndexAliasingTest) {
156 HBasicBlock* body = InitEntryMainExitGraphWithReturnVoid();
157
158 HInstruction* array = MakeParam(DataType::Type::kReference);
159 HInstruction* index = MakeParam(DataType::Type::kInt32);
160 HInstruction* c0 = graph_->GetIntConstant(0);
161 HInstruction* c1 = graph_->GetIntConstant(1);
162 HInstruction* c_neg1 = graph_->GetIntConstant(-1);
163 HInstruction* add0 = MakeBinOp<HAdd>(body, DataType::Type::kInt32, index, c0);
164 HInstruction* add1 = MakeBinOp<HAdd>(body, DataType::Type::kInt32, index, c1);
165 HInstruction* sub0 = MakeBinOp<HSub>(body, DataType::Type::kInt32, index, c0);
166 HInstruction* sub1 = MakeBinOp<HSub>(body, DataType::Type::kInt32, index, c1);
167 HInstruction* sub_neg1 = MakeBinOp<HSub>(body, DataType::Type::kInt32, index, c_neg1);
168 HInstruction* rev_sub1 = MakeBinOp<HSub>(body, DataType::Type::kInt32, c1, index);
169 // array[0] = c0
170 HInstruction* arr_set1 = MakeArraySet(body, array, c0, c0, DataType::Type::kInt32);
171 // array[1] = c0
172 HInstruction* arr_set2 = MakeArraySet(body, array, c1, c0, DataType::Type::kInt32);
173 // array[i+0] = c0
174 HInstruction* arr_set3 = MakeArraySet(body, array, add0, c0, DataType::Type::kInt32);
175 // array[i+1] = c0
176 HInstruction* arr_set4 = MakeArraySet(body, array, add1, c0, DataType::Type::kInt32);
177 // array[i-0] = c0
178 HInstruction* arr_set5 = MakeArraySet(body, array, sub0, c0, DataType::Type::kInt32);
179 // array[i-1] = c0
180 HInstruction* arr_set6 = MakeArraySet(body, array, sub1, c0, DataType::Type::kInt32);
181 // array[1-i] = c0
182 HInstruction* arr_set7 = MakeArraySet(body, array, rev_sub1, c0, DataType::Type::kInt32);
183 // array[i-(-1)] = c0
184 HInstruction* arr_set8 = MakeArraySet(body, array, sub_neg1, c0, DataType::Type::kInt32);
185
186 graph_->ComputeDominanceInformation();
187 ScopedArenaAllocator allocator(graph_->GetArenaStack());
188 LoadStoreAnalysis lsa(graph_, nullptr, &allocator);
189 lsa.Run();
190 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
191
192 // LSA/HeapLocationCollector should see those ArrayGet instructions.
193 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 8U);
194 ASSERT_TRUE(heap_location_collector.HasHeapStores());
195
196 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
197 size_t loc1 = HeapLocationCollector::kHeapLocationNotFound;
198 size_t loc2 = HeapLocationCollector::kHeapLocationNotFound;
199
200 // Test alias: array[0] and array[1]
201 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set1);
202 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set2);
203 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
204
205 // Test alias: array[i+0] and array[i-0]
206 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set3);
207 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set5);
208 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
209
210 // Test alias: array[i+1] and array[i-1]
211 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4);
212 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set6);
213 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
214
215 // Test alias: array[i+1] and array[1-i]
216 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4);
217 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set7);
218 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
219
220 // Test alias: array[i+1] and array[i-(-1)]
221 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4);
222 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set8);
223 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
224
225 EXPECT_TRUE(CheckGraph());
226 }
227
TEST_F(LoadStoreAnalysisTest,ArrayAliasingTest)228 TEST_F(LoadStoreAnalysisTest, ArrayAliasingTest) {
229 constexpr size_t vlen1 = kDefaultTestVectorSizeInBytes;
230 constexpr size_t vlen2 = vlen1 / 2;
231
232 HBasicBlock* main = InitEntryMainExitGraphWithReturnVoid();
233
234 HInstruction* array = MakeParam(DataType::Type::kReference);
235 HInstruction* index = MakeParam(DataType::Type::kInt32);
236 HInstruction* c0 = graph_->GetIntConstant(0);
237 HInstruction* c1 = graph_->GetIntConstant(1);
238 HInstruction* c6 = graph_->GetIntConstant(6);
239 HInstruction* c8 = graph_->GetIntConstant(8);
240
241 HInstruction* arr_set_0 = MakeArraySet(main, array, c0, c0, DataType::Type::kInt32);
242 HInstruction* arr_set_1 = MakeArraySet(main, array, c1, c0, DataType::Type::kInt32);
243 HInstruction* arr_set_i = MakeArraySet(main, array, index, c0, DataType::Type::kInt32);
244
245 HVecOperation* v1 = new (GetAllocator()) HVecReplicateScalar(GetAllocator(),
246 c1,
247 DataType::Type::kInt32,
248 vlen1,
249 kNoDexPc);
250 AddOrInsertInstruction(main, v1);
251 HVecOperation* v2 = new (GetAllocator()) HVecReplicateScalar(GetAllocator(),
252 c1,
253 DataType::Type::kInt32,
254 vlen2,
255 kNoDexPc);
256 AddOrInsertInstruction(main, v2);
257 HInstruction* i_add6 = MakeBinOp<HAdd>(main, DataType::Type::kInt32, index, c6);
258 HInstruction* i_add8 = MakeBinOp<HAdd>(main, DataType::Type::kInt32, index, c8);
259
260 HInstruction* vstore_0 =
261 MakeVecStore(main, array, c0, v1, DataType::Type::kInt32, vlen1);
262 HInstruction* vstore_1 =
263 MakeVecStore(main, array, c1, v1, DataType::Type::kInt32, vlen1);
264 HInstruction* vstore_8 =
265 MakeVecStore(main, array, c8, v1, DataType::Type::kInt32, vlen1);
266 HInstruction* vstore_i =
267 MakeVecStore(main, array, index, v1, DataType::Type::kInt32, vlen1);
268 HInstruction* vstore_i_add6 =
269 MakeVecStore(main, array, i_add6, v1, DataType::Type::kInt32, vlen1);
270 HInstruction* vstore_i_add8 =
271 MakeVecStore(main, array, i_add8, v1, DataType::Type::kInt32, vlen1);
272 HInstruction* vstore_i_add6_vlen2 =
273 MakeVecStore(main, array, i_add6, v2, DataType::Type::kInt32, vlen2);
274
275 graph_->BuildDominatorTree();
276 ScopedArenaAllocator allocator(graph_->GetArenaStack());
277 LoadStoreAnalysis lsa(graph_, nullptr, &allocator);
278 lsa.Run();
279 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
280
281 // LSA/HeapLocationCollector should see those instructions.
282 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 10U);
283 ASSERT_TRUE(heap_location_collector.HasHeapStores());
284
285 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
286 size_t loc1, loc2;
287
288 // Test alias: array[0] and array[0,1,2,3]
289 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
290 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0);
291 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
292
293 // Test alias: array[0] and array[1,2,3,4]
294 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
295 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_1);
296 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
297
298 // Test alias: array[0] and array[8,9,10,11]
299 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
300 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8);
301 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
302
303 // Test alias: array[1] and array[8,9,10,11]
304 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1);
305 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8);
306 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
307
308 // Test alias: array[1] and array[0,1,2,3]
309 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1);
310 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0);
311 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
312
313 // Test alias: array[0,1,2,3] and array[8,9,10,11]
314 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_0);
315 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8);
316 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
317
318 // Test alias: array[0,1,2,3] and array[1,2,3,4]
319 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_0);
320 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_1);
321 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
322
323 // Test alias: array[0] and array[i,i+1,i+2,i+3]
324 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
325 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i);
326 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
327
328 // Test alias: array[i] and array[0,1,2,3]
329 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
330 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0);
331 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
332
333 // Test alias: array[i] and array[i,i+1,i+2,i+3]
334 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
335 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i);
336 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
337
338 // Test alias: array[i] and array[i+8,i+9,i+10,i+11]
339 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
340 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8);
341 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
342
343 // Test alias: array[i+6,i+7,i+8,i+9] and array[i+8,i+9,i+10,i+11]
344 // Test partial overlap.
345 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6);
346 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8);
347 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
348
349 // Test alias: array[i+6,i+7] and array[i,i+1,i+2,i+3]
350 // Test different vector lengths.
351 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6_vlen2);
352 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i);
353 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
354
355 // Test alias: array[i+6,i+7] and array[i+8,i+9,i+10,i+11]
356 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6_vlen2);
357 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8);
358 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
359 }
360
TEST_F(LoadStoreAnalysisTest,ArrayIndexCalculationOverflowTest)361 TEST_F(LoadStoreAnalysisTest, ArrayIndexCalculationOverflowTest) {
362 HBasicBlock* main = InitEntryMainExitGraphWithReturnVoid();
363
364 HInstruction* array = MakeParam(DataType::Type::kReference);
365 HInstruction* index = MakeParam(DataType::Type::kInt32);
366
367 HInstruction* c0 = graph_->GetIntConstant(0);
368 HInstruction* c_0x80000000 = graph_->GetIntConstant(0x80000000);
369 HInstruction* c_0x10 = graph_->GetIntConstant(0x10);
370 HInstruction* c_0xFFFFFFF0 = graph_->GetIntConstant(0xFFFFFFF0);
371 HInstruction* c_0x7FFFFFFF = graph_->GetIntConstant(0x7FFFFFFF);
372 HInstruction* c_0x80000001 = graph_->GetIntConstant(0x80000001);
373
374 // `index+0x80000000` and `index-0x80000000` array indices MAY alias.
375 HInstruction* add_0x80000000 = MakeBinOp<HAdd>(main, DataType::Type::kInt32, index, c_0x80000000);
376 HInstruction* sub_0x80000000 = MakeBinOp<HSub>(main, DataType::Type::kInt32, index, c_0x80000000);
377 HInstruction* arr_set_1 = MakeArraySet(main, array, add_0x80000000, c0, DataType::Type::kInt32);
378 HInstruction* arr_set_2 = MakeArraySet(main, array, sub_0x80000000, c0, DataType::Type::kInt32);
379
380 // `index+0x10` and `index-0xFFFFFFF0` array indices MAY alias.
381 HInstruction* add_0x10 = MakeBinOp<HAdd>(main, DataType::Type::kInt32, index, c_0x10);
382 HInstruction* sub_0xFFFFFFF0 = MakeBinOp<HSub>(main, DataType::Type::kInt32, index, c_0xFFFFFFF0);
383 HInstruction* arr_set_3 = MakeArraySet(main, array, add_0x10, c0, DataType::Type::kInt32);
384 HInstruction* arr_set_4 = MakeArraySet(main, array, sub_0xFFFFFFF0, c0, DataType::Type::kInt32);
385
386 // `index+0x7FFFFFFF` and `index-0x80000001` array indices MAY alias.
387 HInstruction* add_0x7FFFFFFF = MakeBinOp<HAdd>(main, DataType::Type::kInt32, index, c_0x7FFFFFFF);
388 HInstruction* sub_0x80000001 = MakeBinOp<HSub>(main, DataType::Type::kInt32, index, c_0x80000001);
389 HInstruction* arr_set_5 = MakeArraySet(main, array, add_0x7FFFFFFF, c0, DataType::Type::kInt32);
390 HInstruction* arr_set_6 = MakeArraySet(main, array, sub_0x80000001, c0, DataType::Type::kInt32);
391
392 // `index+0` and `index-0` array indices MAY alias.
393 HInstruction* add_0 = MakeBinOp<HAdd>(main, DataType::Type::kInt32, index, c0);
394 HInstruction* sub_0 = MakeBinOp<HSub>(main, DataType::Type::kInt32, index, c0);
395 HInstruction* arr_set_7 = MakeArraySet(main, array, add_0, c0, DataType::Type::kInt32);
396 HInstruction* arr_set_8 = MakeArraySet(main, array, sub_0, c0, DataType::Type::kInt32);
397
398 graph_->BuildDominatorTree();
399 ScopedArenaAllocator allocator(graph_->GetArenaStack());
400 LoadStoreAnalysis lsa(graph_, nullptr, &allocator);
401 lsa.Run();
402 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
403
404 // LSA/HeapLocationCollector should see those ArrayGet instructions.
405 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 8U);
406 ASSERT_TRUE(heap_location_collector.HasHeapStores());
407
408 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
409 size_t loc1 = HeapLocationCollector::kHeapLocationNotFound;
410 size_t loc2 = HeapLocationCollector::kHeapLocationNotFound;
411
412 // Test alias: array[i+0x80000000] and array[i-0x80000000]
413 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1);
414 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_2);
415 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
416
417 // Test alias: array[i+0x10] and array[i-0xFFFFFFF0]
418 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_3);
419 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_4);
420 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
421
422 // Test alias: array[i+0x7FFFFFFF] and array[i-0x80000001]
423 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_5);
424 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_6);
425 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
426
427 // Test alias: array[i+0] and array[i-0]
428 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_7);
429 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_8);
430 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
431
432 // Should not alias:
433 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_2);
434 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_6);
435 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
436
437 // Should not alias:
438 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_7);
439 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_2);
440 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
441 }
442
TEST_F(LoadStoreAnalysisTest,TestHuntOriginalRef)443 TEST_F(LoadStoreAnalysisTest, TestHuntOriginalRef) {
444 HBasicBlock* main = InitEntryMainExitGraphWithReturnVoid();
445
446 // Different ways where orignal array reference are transformed & passed to ArrayGet.
447 // ParameterValue --> ArrayGet
448 // ParameterValue --> BoundType --> ArrayGet
449 // ParameterValue --> BoundType --> NullCheck --> ArrayGet
450 // ParameterValue --> BoundType --> NullCheck --> IntermediateAddress --> ArrayGet
451 HInstruction* c1 = graph_->GetIntConstant(1);
452 HInstruction* array = MakeParam(DataType::Type::kReference);
453
454 HInstruction* array_get1 = MakeArrayGet(main, array, c1, DataType::Type::kInt32);
455
456 HInstruction* bound_type = new (GetAllocator()) HBoundType(array);
457 AddOrInsertInstruction(main, bound_type);
458 HInstruction* array_get2 = MakeArrayGet(main, bound_type, c1, DataType::Type::kInt32);
459
460 HInstruction* null_check = MakeNullCheck(main, bound_type);
461 HInstruction* array_get3 = MakeArrayGet(main, null_check, c1, DataType::Type::kInt32);
462
463 HInstruction* inter_addr = new (GetAllocator()) HIntermediateAddress(null_check, c1, 0);
464 AddOrInsertInstruction(main, inter_addr);
465 HInstruction* array_get4 = MakeArrayGet(main, inter_addr, c1, DataType::Type::kInt32);
466
467 ScopedArenaAllocator allocator(graph_->GetArenaStack());
468 HeapLocationCollector heap_location_collector(graph_, &allocator);
469 heap_location_collector.VisitBasicBlock(main);
470
471 // Test that the HeapLocationCollector should be able to tell
472 // that there is only ONE array location, no matter how many
473 // times the original reference has been transformed by BoundType,
474 // NullCheck, IntermediateAddress, etc.
475 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 1U);
476 size_t loc1 = heap_location_collector.GetArrayHeapLocation(array_get1);
477 size_t loc2 = heap_location_collector.GetArrayHeapLocation(array_get2);
478 size_t loc3 = heap_location_collector.GetArrayHeapLocation(array_get3);
479 size_t loc4 = heap_location_collector.GetArrayHeapLocation(array_get4);
480 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound);
481 ASSERT_EQ(loc1, loc2);
482 ASSERT_EQ(loc1, loc3);
483 ASSERT_EQ(loc1, loc4);
484 }
485
486 // // IF_BLOCK
487 // obj = new Obj();
488 // if (parameter_value) {
489 // // LEFT
490 // call_func(obj);
491 // } else {
492 // // RIGHT
493 // obj.f0 = 0;
494 // call_func2(obj);
495 // }
496 // // RETURN_BLOCK
497 // obj.f0;
TEST_F(LoadStoreAnalysisTest,TotalEscape)498 TEST_F(LoadStoreAnalysisTest, TotalEscape) {
499 HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
500 auto [if_block, left, right] = CreateDiamondPattern(return_block);
501
502 HInstruction* bool_value = MakeParam(DataType::Type::kBool);
503 HInstruction* c0 = graph_->GetIntConstant(0);
504
505 HInstruction* cls = MakeLoadClass(if_block);
506 HInstruction* new_inst = MakeNewInstance(if_block, cls);
507 MakeIf(if_block, bool_value);
508
509 HInstruction* call_left = MakeInvokeStatic(left, DataType::Type::kVoid, {new_inst});
510
511 HInstruction* call_right = MakeInvokeStatic(right, DataType::Type::kVoid, {new_inst});
512 HInstruction* write_right = MakeIFieldSet(right, new_inst, c0, MemberOffset(32));
513
514 HInstruction* read_final =
515 MakeIFieldGet(return_block, new_inst, DataType::Type::kInt32, MemberOffset(32));
516
517 graph_->ComputeDominanceInformation();
518 ScopedArenaAllocator allocator(graph_->GetArenaStack());
519 LoadStoreAnalysis lsa(graph_, nullptr, &allocator);
520 lsa.Run();
521
522 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
523 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
524 ASSERT_FALSE(info->IsSingleton());
525 }
526
527 // // MAIN
528 // obj = new Obj();
529 // obj.foo = 0;
530 // return obj;
TEST_F(LoadStoreAnalysisTest,TotalEscape2)531 TEST_F(LoadStoreAnalysisTest, TotalEscape2) {
532 HBasicBlock* main = InitEntryMainExitGraph();
533
534 HInstruction* c0 = graph_->GetIntConstant(0);
535
536 HInstruction* cls = MakeLoadClass(main);
537 HInstruction* new_inst = MakeNewInstance(main, cls);
538 HInstruction* write_start = MakeIFieldSet(main, new_inst, c0, MemberOffset(32));
539 MakeReturn(main, new_inst);
540
541 graph_->ComputeDominanceInformation();
542 ScopedArenaAllocator allocator(graph_->GetArenaStack());
543 LoadStoreAnalysis lsa(graph_, nullptr, &allocator);
544 lsa.Run();
545
546 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
547 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
548 ASSERT_TRUE(info->IsSingletonAndNonRemovable());
549 }
550
551 // // TOP
552 // obj = new Obj();
553 // if (parameter_value) {
554 // // HIGH_LEFT
555 // call_func(obj);
556 // } else {
557 // // HIGH_RIGHT
558 // obj.f0 = 1;
559 // }
560 // // MID
561 // obj.f0 *= 2;
562 // if (parameter_value2) {
563 // // LOW_LEFT
564 // call_func(obj);
565 // } else {
566 // // LOW_RIGHT
567 // obj.f0 = 1;
568 // }
569 // // BOTTOM
570 // obj.f0
TEST_F(LoadStoreAnalysisTest,DoubleDiamondEscape)571 TEST_F(LoadStoreAnalysisTest, DoubleDiamondEscape) {
572 HBasicBlock* bottom = InitEntryMainExitGraphWithReturnVoid();
573 auto [mid, low_left, low_right] = CreateDiamondPattern(bottom);
574 auto [top, high_left, high_right] = CreateDiamondPattern(mid);
575
576 HInstruction* bool_value1 = MakeParam(DataType::Type::kBool);
577 HInstruction* bool_value2 = MakeParam(DataType::Type::kBool);
578 HInstruction* c0 = graph_->GetIntConstant(0);
579 HInstruction* c2 = graph_->GetIntConstant(2);
580
581 HInstruction* cls = MakeLoadClass(top);
582 HInstruction* new_inst = MakeNewInstance(top, cls);
583 MakeIf(top, bool_value1);
584
585 HInstruction* call_left = MakeInvokeStatic(high_left, DataType::Type::kVoid, {new_inst});
586
587 HInstruction* write_right = MakeIFieldSet(high_right, new_inst, c0, MemberOffset(32));
588
589 HInstruction* read_mid = MakeIFieldGet(mid, new_inst, DataType::Type::kInt32, MemberOffset(32));
590 HInstruction* mul_mid = MakeBinOp<HMul>(mid, DataType::Type::kInt32, read_mid, c2);
591 HInstruction* write_mid = MakeIFieldSet(mid, new_inst, mul_mid, MemberOffset(32));
592 MakeIf(mid, bool_value2);
593
594 HInstruction* call_low_left = MakeInvokeStatic(low_left, DataType::Type::kVoid, {new_inst});
595
596 HInstruction* write_low_right = MakeIFieldSet(low_right, new_inst, c0, MemberOffset(32));
597
598 HInstruction* read_final =
599 MakeIFieldGet(bottom, new_inst, DataType::Type::kInt32, MemberOffset(32));
600
601 graph_->ComputeDominanceInformation();
602 ScopedArenaAllocator allocator(graph_->GetArenaStack());
603 LoadStoreAnalysis lsa(graph_, nullptr, &allocator);
604 lsa.Run();
605
606 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
607 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
608 ASSERT_FALSE(info->IsSingleton());
609 }
610
611 // // START
612 // Obj new_inst = new Obj();
613 // new_inst.foo = 12;
614 // Obj obj;
615 // Obj out;
616 // if (param1) {
617 // // LEFT_START
618 // if (param2) {
619 // // LEFT_LEFT
620 // obj = new_inst;
621 // } else {
622 // // LEFT_RIGHT
623 // obj = obj_param;
624 // }
625 // // LEFT_MERGE
626 // // technically the phi is enough to cause an escape but might as well be
627 // // thorough.
628 // // obj = phi[new_inst, param]
629 // escape(obj);
630 // out = obj;
631 // } else {
632 // // RIGHT
633 // out = obj_param;
634 // }
635 // // BRETURN
636 // // Can't do anything with this since we don't have good tracking for the heap-locations
637 // // out = phi[param, phi[new_inst, param]]
638 // return out.foo
TEST_F(LoadStoreAnalysisTest,PartialPhiPropagation1)639 TEST_F(LoadStoreAnalysisTest, PartialPhiPropagation1) {
640 HBasicBlock* breturn = InitEntryMainExitGraph();
641 auto [start, left_merge, right] = CreateDiamondPattern(breturn);
642 auto [left, left_left, left_right] = CreateDiamondPattern(left_merge);
643 EnsurePredecessorOrder(breturn, {left_merge, right});
644 EnsurePredecessorOrder(left_merge, {left_left, left_right});
645 HInstruction* param1 = MakeParam(DataType::Type::kBool);
646 HInstruction* param2 = MakeParam(DataType::Type::kBool);
647 HInstruction* obj_param = MakeParam(DataType::Type::kReference);
648 HInstruction* c12 = graph_->GetIntConstant(12);
649
650 HInstruction* cls = MakeLoadClass(start);
651 HInstruction* new_inst = MakeNewInstance(start, cls);
652 HInstruction* store = MakeIFieldSet(start, new_inst, c12, MemberOffset(32));
653 MakeIf(start, param1);
654
655 MakeIf(left, param2);
656
657 HPhi* left_phi = MakePhi(left_merge, {obj_param, new_inst});
658 HInstruction* call_left = MakeInvokeStatic(left_merge, DataType::Type::kVoid, {left_phi});
659 MakeGoto(left_merge);
660 left_phi->SetCanBeNull(true);
661
662 HPhi* return_phi = MakePhi(breturn, {left_phi, obj_param});
663 HInstruction* read_exit =
664 MakeIFieldGet(breturn, return_phi, DataType::Type::kReference, MemberOffset(32));
665 MakeReturn(breturn, read_exit);
666
667 graph_->ClearDominanceInformation();
668 graph_->BuildDominatorTree();
669
670 ScopedArenaAllocator allocator(graph_->GetArenaStack());
671 LoadStoreAnalysis lsa(graph_, nullptr, &allocator);
672 lsa.Run();
673
674 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
675 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
676 ASSERT_FALSE(info->IsSingleton());
677 }
678 } // namespace art
679