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 #include <array>
20 #include <string_view>
21 #include <unordered_map>
22 #include <unordered_set>
23
24 #include "base/scoped_arena_allocator.h"
25 #include "class_root.h"
26 #include "dex/dex_file_types.h"
27 #include "dex/method_reference.h"
28 #include "entrypoints/quick/quick_entrypoints_enum.h"
29 #include "execution_subgraph.h"
30 #include "execution_subgraph_test.h"
31 #include "gtest/gtest.h"
32 #include "handle.h"
33 #include "handle_scope.h"
34 #include "nodes.h"
35 #include "optimizing/data_type.h"
36 #include "optimizing_unit_test.h"
37 #include "scoped_thread_state_change.h"
38
39 namespace art {
40
41 class LoadStoreAnalysisTest : public CommonCompilerTest, public OptimizingUnitTestHelper {
42 public:
LoadStoreAnalysisTest()43 LoadStoreAnalysisTest() {}
44
SetupFromAdjacencyList(const std::string_view entry_name,const std::string_view exit_name,const std::vector<AdjacencyListGraph::Edge> & adj)45 AdjacencyListGraph SetupFromAdjacencyList(
46 const std::string_view entry_name,
47 const std::string_view exit_name,
48 const std::vector<AdjacencyListGraph::Edge>& adj) {
49 return AdjacencyListGraph(graph_, GetAllocator(), entry_name, exit_name, adj);
50 }
51
IsValidSubgraph(const ExecutionSubgraph * esg)52 bool IsValidSubgraph(const ExecutionSubgraph* esg) {
53 return ExecutionSubgraphTestHelper::CalculateValidity(graph_, esg);
54 }
55
IsValidSubgraph(const ExecutionSubgraph & esg)56 bool IsValidSubgraph(const ExecutionSubgraph& esg) {
57 return ExecutionSubgraphTestHelper::CalculateValidity(graph_, &esg);
58 }
59 void CheckReachability(const AdjacencyListGraph& adj,
60 const std::vector<AdjacencyListGraph::Edge>& reach);
61 };
62
TEST_F(LoadStoreAnalysisTest,ArrayHeapLocations)63 TEST_F(LoadStoreAnalysisTest, ArrayHeapLocations) {
64 CreateGraph();
65 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
66 graph_->AddBlock(entry);
67 graph_->SetEntryBlock(entry);
68
69 // entry:
70 // array ParameterValue
71 // index ParameterValue
72 // c1 IntConstant
73 // c2 IntConstant
74 // c3 IntConstant
75 // array_get1 ArrayGet [array, c1]
76 // array_get2 ArrayGet [array, c2]
77 // array_set1 ArraySet [array, c1, c3]
78 // array_set2 ArraySet [array, index, c3]
79 HInstruction* array = new (GetAllocator()) HParameterValue(
80 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
81 HInstruction* index = new (GetAllocator()) HParameterValue(
82 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
83 HInstruction* c1 = graph_->GetIntConstant(1);
84 HInstruction* c2 = graph_->GetIntConstant(2);
85 HInstruction* c3 = graph_->GetIntConstant(3);
86 HInstruction* array_get1 = new (GetAllocator()) HArrayGet(array, c1, DataType::Type::kInt32, 0);
87 HInstruction* array_get2 = new (GetAllocator()) HArrayGet(array, c2, DataType::Type::kInt32, 0);
88 HInstruction* array_set1 =
89 new (GetAllocator()) HArraySet(array, c1, c3, DataType::Type::kInt32, 0);
90 HInstruction* array_set2 =
91 new (GetAllocator()) HArraySet(array, index, c3, DataType::Type::kInt32, 0);
92 entry->AddInstruction(array);
93 entry->AddInstruction(index);
94 entry->AddInstruction(array_get1);
95 entry->AddInstruction(array_get2);
96 entry->AddInstruction(array_set1);
97 entry->AddInstruction(array_set2);
98
99 // Test HeapLocationCollector initialization.
100 // Should be no heap locations, no operations on the heap.
101 ScopedArenaAllocator allocator(graph_->GetArenaStack());
102 HeapLocationCollector heap_location_collector(graph_, &allocator, LoadStoreAnalysisType::kFull);
103 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 0U);
104 ASSERT_FALSE(heap_location_collector.HasHeapStores());
105
106 // Test that after visiting the graph_, it must see following heap locations
107 // array[c1], array[c2], array[index]; and it should see heap stores.
108 heap_location_collector.VisitBasicBlock(entry);
109 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 3U);
110 ASSERT_TRUE(heap_location_collector.HasHeapStores());
111
112 // Test queries on HeapLocationCollector's ref info and index records.
113 ReferenceInfo* ref = heap_location_collector.FindReferenceInfoOf(array);
114 DataType::Type type = DataType::Type::kInt32;
115 size_t field = HeapLocation::kInvalidFieldOffset;
116 size_t vec = HeapLocation::kScalar;
117 size_t class_def = HeapLocation::kDeclaringClassDefIndexForArrays;
118 size_t loc1 = heap_location_collector.FindHeapLocationIndex(
119 ref, type, field, c1, vec, class_def);
120 size_t loc2 = heap_location_collector.FindHeapLocationIndex(
121 ref, type, field, c2, vec, class_def);
122 size_t loc3 = heap_location_collector.FindHeapLocationIndex(
123 ref, type, field, index, vec, class_def);
124 // must find this reference info for array in HeapLocationCollector.
125 ASSERT_TRUE(ref != nullptr);
126 // must find these heap locations;
127 // and array[1], array[2], array[3] should be different heap locations.
128 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound);
129 ASSERT_TRUE(loc2 != HeapLocationCollector::kHeapLocationNotFound);
130 ASSERT_TRUE(loc3 != HeapLocationCollector::kHeapLocationNotFound);
131 ASSERT_TRUE(loc1 != loc2);
132 ASSERT_TRUE(loc2 != loc3);
133 ASSERT_TRUE(loc1 != loc3);
134
135 // Test alias relationships after building aliasing matrix.
136 // array[1] and array[2] clearly should not alias;
137 // array[index] should alias with the others, because index is an unknow value.
138 heap_location_collector.BuildAliasingMatrix();
139 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
140 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc3));
141 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc3));
142
143 EXPECT_TRUE(CheckGraph(graph_));
144 }
145
TEST_F(LoadStoreAnalysisTest,FieldHeapLocations)146 TEST_F(LoadStoreAnalysisTest, FieldHeapLocations) {
147 CreateGraph();
148 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
149 graph_->AddBlock(entry);
150 graph_->SetEntryBlock(entry);
151
152 // entry:
153 // object ParameterValue
154 // c1 IntConstant
155 // set_field10 InstanceFieldSet [object, c1, 10]
156 // get_field10 InstanceFieldGet [object, 10]
157 // get_field20 InstanceFieldGet [object, 20]
158
159 HInstruction* c1 = graph_->GetIntConstant(1);
160 HInstruction* object = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
161 dex::TypeIndex(0),
162 0,
163 DataType::Type::kReference);
164 HInstanceFieldSet* set_field10 = new (GetAllocator()) HInstanceFieldSet(object,
165 c1,
166 nullptr,
167 DataType::Type::kInt32,
168 MemberOffset(32),
169 false,
170 kUnknownFieldIndex,
171 kUnknownClassDefIndex,
172 graph_->GetDexFile(),
173 0);
174 HInstanceFieldGet* get_field10 = new (GetAllocator()) HInstanceFieldGet(object,
175 nullptr,
176 DataType::Type::kInt32,
177 MemberOffset(32),
178 false,
179 kUnknownFieldIndex,
180 kUnknownClassDefIndex,
181 graph_->GetDexFile(),
182 0);
183 HInstanceFieldGet* get_field20 = new (GetAllocator()) HInstanceFieldGet(object,
184 nullptr,
185 DataType::Type::kInt32,
186 MemberOffset(20),
187 false,
188 kUnknownFieldIndex,
189 kUnknownClassDefIndex,
190 graph_->GetDexFile(),
191 0);
192 entry->AddInstruction(object);
193 entry->AddInstruction(set_field10);
194 entry->AddInstruction(get_field10);
195 entry->AddInstruction(get_field20);
196
197 // Test HeapLocationCollector initialization.
198 // Should be no heap locations, no operations on the heap.
199 ScopedArenaAllocator allocator(graph_->GetArenaStack());
200 HeapLocationCollector heap_location_collector(graph_, &allocator, LoadStoreAnalysisType::kFull);
201 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 0U);
202 ASSERT_FALSE(heap_location_collector.HasHeapStores());
203
204 // Test that after visiting the graph, it must see following heap locations
205 // object.field10, object.field20 and it should see heap stores.
206 heap_location_collector.VisitBasicBlock(entry);
207 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 2U);
208 ASSERT_TRUE(heap_location_collector.HasHeapStores());
209
210 // Test queries on HeapLocationCollector's ref info and index records.
211 ReferenceInfo* ref = heap_location_collector.FindReferenceInfoOf(object);
212 size_t loc1 = heap_location_collector.GetFieldHeapLocation(object, &get_field10->GetFieldInfo());
213 size_t loc2 = heap_location_collector.GetFieldHeapLocation(object, &get_field20->GetFieldInfo());
214 // must find references info for object and in HeapLocationCollector.
215 ASSERT_TRUE(ref != nullptr);
216 // must find these heap locations.
217 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound);
218 ASSERT_TRUE(loc2 != HeapLocationCollector::kHeapLocationNotFound);
219 // different fields of same object.
220 ASSERT_TRUE(loc1 != loc2);
221 // accesses to different fields of the same object should not alias.
222 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
223
224 EXPECT_TRUE(CheckGraph(graph_));
225 }
226
TEST_F(LoadStoreAnalysisTest,ArrayIndexAliasingTest)227 TEST_F(LoadStoreAnalysisTest, ArrayIndexAliasingTest) {
228 CreateGraph();
229 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
230 graph_->AddBlock(entry);
231 graph_->SetEntryBlock(entry);
232 graph_->BuildDominatorTree();
233
234 HInstruction* array = new (GetAllocator()) HParameterValue(
235 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
236 HInstruction* index = new (GetAllocator()) HParameterValue(
237 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
238 HInstruction* c0 = graph_->GetIntConstant(0);
239 HInstruction* c1 = graph_->GetIntConstant(1);
240 HInstruction* c_neg1 = graph_->GetIntConstant(-1);
241 HInstruction* add0 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c0);
242 HInstruction* add1 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c1);
243 HInstruction* sub0 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c0);
244 HInstruction* sub1 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c1);
245 HInstruction* sub_neg1 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c_neg1);
246 HInstruction* rev_sub1 = new (GetAllocator()) HSub(DataType::Type::kInt32, c1, index);
247 HInstruction* arr_set1 = new (GetAllocator()) HArraySet(array, c0, c0, DataType::Type::kInt32, 0);
248 HInstruction* arr_set2 = new (GetAllocator()) HArraySet(array, c1, c0, DataType::Type::kInt32, 0);
249 HInstruction* arr_set3 =
250 new (GetAllocator()) HArraySet(array, add0, c0, DataType::Type::kInt32, 0);
251 HInstruction* arr_set4 =
252 new (GetAllocator()) HArraySet(array, add1, c0, DataType::Type::kInt32, 0);
253 HInstruction* arr_set5 =
254 new (GetAllocator()) HArraySet(array, sub0, c0, DataType::Type::kInt32, 0);
255 HInstruction* arr_set6 =
256 new (GetAllocator()) HArraySet(array, sub1, c0, DataType::Type::kInt32, 0);
257 HInstruction* arr_set7 =
258 new (GetAllocator()) HArraySet(array, rev_sub1, c0, DataType::Type::kInt32, 0);
259 HInstruction* arr_set8 =
260 new (GetAllocator()) HArraySet(array, sub_neg1, c0, DataType::Type::kInt32, 0);
261
262 entry->AddInstruction(array);
263 entry->AddInstruction(index);
264 entry->AddInstruction(add0);
265 entry->AddInstruction(add1);
266 entry->AddInstruction(sub0);
267 entry->AddInstruction(sub1);
268 entry->AddInstruction(sub_neg1);
269 entry->AddInstruction(rev_sub1);
270
271 entry->AddInstruction(arr_set1); // array[0] = c0
272 entry->AddInstruction(arr_set2); // array[1] = c0
273 entry->AddInstruction(arr_set3); // array[i+0] = c0
274 entry->AddInstruction(arr_set4); // array[i+1] = c0
275 entry->AddInstruction(arr_set5); // array[i-0] = c0
276 entry->AddInstruction(arr_set6); // array[i-1] = c0
277 entry->AddInstruction(arr_set7); // array[1-i] = c0
278 entry->AddInstruction(arr_set8); // array[i-(-1)] = c0
279
280 ScopedArenaAllocator allocator(graph_->GetArenaStack());
281 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, LoadStoreAnalysisType::kBasic);
282 lsa.Run();
283 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
284
285 // LSA/HeapLocationCollector should see those ArrayGet instructions.
286 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 8U);
287 ASSERT_TRUE(heap_location_collector.HasHeapStores());
288
289 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
290 size_t loc1 = HeapLocationCollector::kHeapLocationNotFound;
291 size_t loc2 = HeapLocationCollector::kHeapLocationNotFound;
292
293 // Test alias: array[0] and array[1]
294 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set1);
295 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set2);
296 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
297
298 // Test alias: array[i+0] and array[i-0]
299 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set3);
300 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set5);
301 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
302
303 // Test alias: array[i+1] and array[i-1]
304 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4);
305 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set6);
306 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
307
308 // Test alias: array[i+1] and array[1-i]
309 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4);
310 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set7);
311 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
312
313 // Test alias: array[i+1] and array[i-(-1)]
314 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4);
315 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set8);
316 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
317
318 EXPECT_TRUE(CheckGraphSkipRefTypeInfoChecks(graph_));
319 }
320
TEST_F(LoadStoreAnalysisTest,ArrayAliasingTest)321 TEST_F(LoadStoreAnalysisTest, ArrayAliasingTest) {
322 CreateGraph();
323 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
324 graph_->AddBlock(entry);
325 graph_->SetEntryBlock(entry);
326 graph_->BuildDominatorTree();
327
328 HInstruction* array = new (GetAllocator()) HParameterValue(
329 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
330 HInstruction* index = new (GetAllocator()) HParameterValue(
331 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
332 HInstruction* c0 = graph_->GetIntConstant(0);
333 HInstruction* c1 = graph_->GetIntConstant(1);
334 HInstruction* c6 = graph_->GetIntConstant(6);
335 HInstruction* c8 = graph_->GetIntConstant(8);
336
337 HInstruction* arr_set_0 = new (GetAllocator()) HArraySet(array,
338 c0,
339 c0,
340 DataType::Type::kInt32,
341 0);
342 HInstruction* arr_set_1 = new (GetAllocator()) HArraySet(array,
343 c1,
344 c0,
345 DataType::Type::kInt32,
346 0);
347 HInstruction* arr_set_i = new (GetAllocator()) HArraySet(array,
348 index,
349 c0,
350 DataType::Type::kInt32,
351 0);
352
353 HVecOperation* v1 = new (GetAllocator()) HVecReplicateScalar(GetAllocator(),
354 c1,
355 DataType::Type::kInt32,
356 4,
357 kNoDexPc);
358 HVecOperation* v2 = new (GetAllocator()) HVecReplicateScalar(GetAllocator(),
359 c1,
360 DataType::Type::kInt32,
361 2,
362 kNoDexPc);
363 HInstruction* i_add6 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c6);
364 HInstruction* i_add8 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c8);
365
366 HInstruction* vstore_0 = new (GetAllocator()) HVecStore(
367 GetAllocator(),
368 array,
369 c0,
370 v1,
371 DataType::Type::kInt32,
372 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
373 4,
374 kNoDexPc);
375 HInstruction* vstore_1 = new (GetAllocator()) HVecStore(
376 GetAllocator(),
377 array,
378 c1,
379 v1,
380 DataType::Type::kInt32,
381 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
382 4,
383 kNoDexPc);
384 HInstruction* vstore_8 = new (GetAllocator()) HVecStore(
385 GetAllocator(),
386 array,
387 c8,
388 v1,
389 DataType::Type::kInt32,
390 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
391 4,
392 kNoDexPc);
393 HInstruction* vstore_i = new (GetAllocator()) HVecStore(
394 GetAllocator(),
395 array,
396 index,
397 v1,
398 DataType::Type::kInt32,
399 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
400 4,
401 kNoDexPc);
402 HInstruction* vstore_i_add6 = new (GetAllocator()) HVecStore(
403 GetAllocator(),
404 array,
405 i_add6,
406 v1,
407 DataType::Type::kInt32,
408 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
409 4,
410 kNoDexPc);
411 HInstruction* vstore_i_add8 = new (GetAllocator()) HVecStore(
412 GetAllocator(),
413 array,
414 i_add8,
415 v1,
416 DataType::Type::kInt32,
417 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
418 4,
419 kNoDexPc);
420 HInstruction* vstore_i_add6_vlen2 = new (GetAllocator()) HVecStore(
421 GetAllocator(),
422 array,
423 i_add6,
424 v2,
425 DataType::Type::kInt32,
426 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
427 2,
428 kNoDexPc);
429
430 entry->AddInstruction(array);
431 entry->AddInstruction(index);
432
433 entry->AddInstruction(arr_set_0);
434 entry->AddInstruction(arr_set_1);
435 entry->AddInstruction(arr_set_i);
436 entry->AddInstruction(v1);
437 entry->AddInstruction(v2);
438 entry->AddInstruction(i_add6);
439 entry->AddInstruction(i_add8);
440 entry->AddInstruction(vstore_0);
441 entry->AddInstruction(vstore_1);
442 entry->AddInstruction(vstore_8);
443 entry->AddInstruction(vstore_i);
444 entry->AddInstruction(vstore_i_add6);
445 entry->AddInstruction(vstore_i_add8);
446 entry->AddInstruction(vstore_i_add6_vlen2);
447
448 ScopedArenaAllocator allocator(graph_->GetArenaStack());
449 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, LoadStoreAnalysisType::kBasic);
450 lsa.Run();
451 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
452
453 // LSA/HeapLocationCollector should see those instructions.
454 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 10U);
455 ASSERT_TRUE(heap_location_collector.HasHeapStores());
456
457 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
458 size_t loc1, loc2;
459
460 // Test alias: array[0] and array[0,1,2,3]
461 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
462 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0);
463 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
464
465 // Test alias: array[0] and array[1,2,3,4]
466 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
467 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_1);
468 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
469
470 // Test alias: array[0] and array[8,9,10,11]
471 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
472 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8);
473 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
474
475 // Test alias: array[1] and array[8,9,10,11]
476 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1);
477 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8);
478 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
479
480 // Test alias: array[1] and array[0,1,2,3]
481 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1);
482 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0);
483 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
484
485 // Test alias: array[0,1,2,3] and array[8,9,10,11]
486 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_0);
487 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8);
488 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
489
490 // Test alias: array[0,1,2,3] and array[1,2,3,4]
491 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_0);
492 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_1);
493 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
494
495 // Test alias: array[0] and array[i,i+1,i+2,i+3]
496 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
497 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i);
498 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
499
500 // Test alias: array[i] and array[0,1,2,3]
501 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
502 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0);
503 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
504
505 // Test alias: array[i] and array[i,i+1,i+2,i+3]
506 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
507 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i);
508 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
509
510 // Test alias: array[i] and array[i+8,i+9,i+10,i+11]
511 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
512 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8);
513 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
514
515 // Test alias: array[i+6,i+7,i+8,i+9] and array[i+8,i+9,i+10,i+11]
516 // Test partial overlap.
517 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6);
518 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8);
519 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
520
521 // Test alias: array[i+6,i+7] and array[i,i+1,i+2,i+3]
522 // Test different vector lengths.
523 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6_vlen2);
524 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i);
525 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
526
527 // Test alias: array[i+6,i+7] and array[i+8,i+9,i+10,i+11]
528 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6_vlen2);
529 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8);
530 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
531 }
532
TEST_F(LoadStoreAnalysisTest,ArrayIndexCalculationOverflowTest)533 TEST_F(LoadStoreAnalysisTest, ArrayIndexCalculationOverflowTest) {
534 CreateGraph();
535 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
536 graph_->AddBlock(entry);
537 graph_->SetEntryBlock(entry);
538 graph_->BuildDominatorTree();
539
540 HInstruction* array = new (GetAllocator()) HParameterValue(
541 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
542 HInstruction* index = new (GetAllocator()) HParameterValue(
543 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
544
545 HInstruction* c0 = graph_->GetIntConstant(0);
546 HInstruction* c_0x80000000 = graph_->GetIntConstant(0x80000000);
547 HInstruction* c_0x10 = graph_->GetIntConstant(0x10);
548 HInstruction* c_0xFFFFFFF0 = graph_->GetIntConstant(0xFFFFFFF0);
549 HInstruction* c_0x7FFFFFFF = graph_->GetIntConstant(0x7FFFFFFF);
550 HInstruction* c_0x80000001 = graph_->GetIntConstant(0x80000001);
551
552 // `index+0x80000000` and `index-0x80000000` array indices MAY alias.
553 HInstruction* add_0x80000000 = new (GetAllocator()) HAdd(
554 DataType::Type::kInt32, index, c_0x80000000);
555 HInstruction* sub_0x80000000 = new (GetAllocator()) HSub(
556 DataType::Type::kInt32, index, c_0x80000000);
557 HInstruction* arr_set_1 = new (GetAllocator()) HArraySet(
558 array, add_0x80000000, c0, DataType::Type::kInt32, 0);
559 HInstruction* arr_set_2 = new (GetAllocator()) HArraySet(
560 array, sub_0x80000000, c0, DataType::Type::kInt32, 0);
561
562 // `index+0x10` and `index-0xFFFFFFF0` array indices MAY alias.
563 HInstruction* add_0x10 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c_0x10);
564 HInstruction* sub_0xFFFFFFF0 = new (GetAllocator()) HSub(
565 DataType::Type::kInt32, index, c_0xFFFFFFF0);
566 HInstruction* arr_set_3 = new (GetAllocator()) HArraySet(
567 array, add_0x10, c0, DataType::Type::kInt32, 0);
568 HInstruction* arr_set_4 = new (GetAllocator()) HArraySet(
569 array, sub_0xFFFFFFF0, c0, DataType::Type::kInt32, 0);
570
571 // `index+0x7FFFFFFF` and `index-0x80000001` array indices MAY alias.
572 HInstruction* add_0x7FFFFFFF = new (GetAllocator()) HAdd(
573 DataType::Type::kInt32, index, c_0x7FFFFFFF);
574 HInstruction* sub_0x80000001 = new (GetAllocator()) HSub(
575 DataType::Type::kInt32, index, c_0x80000001);
576 HInstruction* arr_set_5 = new (GetAllocator()) HArraySet(
577 array, add_0x7FFFFFFF, c0, DataType::Type::kInt32, 0);
578 HInstruction* arr_set_6 = new (GetAllocator()) HArraySet(
579 array, sub_0x80000001, c0, DataType::Type::kInt32, 0);
580
581 // `index+0` and `index-0` array indices MAY alias.
582 HInstruction* add_0 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c0);
583 HInstruction* sub_0 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c0);
584 HInstruction* arr_set_7 = new (GetAllocator()) HArraySet(
585 array, add_0, c0, DataType::Type::kInt32, 0);
586 HInstruction* arr_set_8 = new (GetAllocator()) HArraySet(
587 array, sub_0, c0, DataType::Type::kInt32, 0);
588
589 entry->AddInstruction(array);
590 entry->AddInstruction(index);
591 entry->AddInstruction(add_0x80000000);
592 entry->AddInstruction(sub_0x80000000);
593 entry->AddInstruction(add_0x10);
594 entry->AddInstruction(sub_0xFFFFFFF0);
595 entry->AddInstruction(add_0x7FFFFFFF);
596 entry->AddInstruction(sub_0x80000001);
597 entry->AddInstruction(add_0);
598 entry->AddInstruction(sub_0);
599 entry->AddInstruction(arr_set_1);
600 entry->AddInstruction(arr_set_2);
601 entry->AddInstruction(arr_set_3);
602 entry->AddInstruction(arr_set_4);
603 entry->AddInstruction(arr_set_5);
604 entry->AddInstruction(arr_set_6);
605 entry->AddInstruction(arr_set_7);
606 entry->AddInstruction(arr_set_8);
607
608 ScopedArenaAllocator allocator(graph_->GetArenaStack());
609 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, LoadStoreAnalysisType::kBasic);
610 lsa.Run();
611 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
612
613 // LSA/HeapLocationCollector should see those ArrayGet instructions.
614 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 8U);
615 ASSERT_TRUE(heap_location_collector.HasHeapStores());
616
617 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
618 size_t loc1 = HeapLocationCollector::kHeapLocationNotFound;
619 size_t loc2 = HeapLocationCollector::kHeapLocationNotFound;
620
621 // Test alias: array[i+0x80000000] and array[i-0x80000000]
622 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1);
623 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_2);
624 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
625
626 // Test alias: array[i+0x10] and array[i-0xFFFFFFF0]
627 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_3);
628 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_4);
629 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
630
631 // Test alias: array[i+0x7FFFFFFF] and array[i-0x80000001]
632 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_5);
633 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_6);
634 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
635
636 // Test alias: array[i+0] and array[i-0]
637 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_7);
638 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_8);
639 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
640
641 // Should not alias:
642 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_2);
643 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_6);
644 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
645
646 // Should not alias:
647 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_7);
648 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_2);
649 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
650 }
651
TEST_F(LoadStoreAnalysisTest,TestHuntOriginalRef)652 TEST_F(LoadStoreAnalysisTest, TestHuntOriginalRef) {
653 CreateGraph();
654 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
655 graph_->AddBlock(entry);
656 graph_->SetEntryBlock(entry);
657
658 // Different ways where orignal array reference are transformed & passed to ArrayGet.
659 // ParameterValue --> ArrayGet
660 // ParameterValue --> BoundType --> ArrayGet
661 // ParameterValue --> BoundType --> NullCheck --> ArrayGet
662 // ParameterValue --> BoundType --> NullCheck --> IntermediateAddress --> ArrayGet
663 HInstruction* c1 = graph_->GetIntConstant(1);
664 HInstruction* array = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
665 dex::TypeIndex(0),
666 0,
667 DataType::Type::kReference);
668 HInstruction* array_get1 = new (GetAllocator()) HArrayGet(array,
669 c1,
670 DataType::Type::kInt32,
671 0);
672
673 HInstruction* bound_type = new (GetAllocator()) HBoundType(array);
674 HInstruction* array_get2 = new (GetAllocator()) HArrayGet(bound_type,
675 c1,
676 DataType::Type::kInt32,
677 0);
678
679 HInstruction* null_check = new (GetAllocator()) HNullCheck(bound_type, 0);
680 HInstruction* array_get3 = new (GetAllocator()) HArrayGet(null_check,
681 c1,
682 DataType::Type::kInt32,
683 0);
684
685 HInstruction* inter_addr = new (GetAllocator()) HIntermediateAddress(null_check, c1, 0);
686 HInstruction* array_get4 = new (GetAllocator()) HArrayGet(inter_addr,
687 c1,
688 DataType::Type::kInt32,
689 0);
690 entry->AddInstruction(array);
691 entry->AddInstruction(array_get1);
692 entry->AddInstruction(bound_type);
693 entry->AddInstruction(array_get2);
694 entry->AddInstruction(null_check);
695 entry->AddInstruction(array_get3);
696 entry->AddInstruction(inter_addr);
697 entry->AddInstruction(array_get4);
698
699 ScopedArenaAllocator allocator(graph_->GetArenaStack());
700 HeapLocationCollector heap_location_collector(graph_, &allocator, LoadStoreAnalysisType::kFull);
701 heap_location_collector.VisitBasicBlock(entry);
702
703 // Test that the HeapLocationCollector should be able to tell
704 // that there is only ONE array location, no matter how many
705 // times the original reference has been transformed by BoundType,
706 // NullCheck, IntermediateAddress, etc.
707 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 1U);
708 size_t loc1 = heap_location_collector.GetArrayHeapLocation(array_get1);
709 size_t loc2 = heap_location_collector.GetArrayHeapLocation(array_get2);
710 size_t loc3 = heap_location_collector.GetArrayHeapLocation(array_get3);
711 size_t loc4 = heap_location_collector.GetArrayHeapLocation(array_get4);
712 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound);
713 ASSERT_EQ(loc1, loc2);
714 ASSERT_EQ(loc1, loc3);
715 ASSERT_EQ(loc1, loc4);
716 }
717
CheckReachability(const AdjacencyListGraph & adj,const std::vector<AdjacencyListGraph::Edge> & reach)718 void LoadStoreAnalysisTest::CheckReachability(const AdjacencyListGraph& adj,
719 const std::vector<AdjacencyListGraph::Edge>& reach) {
720 uint32_t cnt = 0;
721 for (HBasicBlock* blk : graph_->GetBlocks()) {
722 if (adj.HasBlock(blk)) {
723 for (HBasicBlock* other : graph_->GetBlocks()) {
724 if (other == nullptr) {
725 continue;
726 }
727 if (adj.HasBlock(other)) {
728 bool contains_edge =
729 std::find(reach.begin(),
730 reach.end(),
731 AdjacencyListGraph::Edge { adj.GetName(blk), adj.GetName(other) }) !=
732 reach.end();
733 if (graph_->PathBetween(blk, other)) {
734 cnt++;
735 EXPECT_TRUE(contains_edge) << "Unexpected edge found between " << adj.GetName(blk)
736 << " and " << adj.GetName(other);
737 } else {
738 EXPECT_FALSE(contains_edge) << "Expected edge not found between " << adj.GetName(blk)
739 << " and " << adj.GetName(other);
740 }
741 } else if (graph_->PathBetween(blk, other)) {
742 ADD_FAILURE() << "block " << adj.GetName(blk)
743 << " has path to non-adjacency-graph block id: " << other->GetBlockId();
744 }
745 }
746 } else {
747 for (HBasicBlock* other : graph_->GetBlocks()) {
748 if (other == nullptr) {
749 continue;
750 }
751 EXPECT_FALSE(graph_->PathBetween(blk, other))
752 << "Reachable blocks outside of adjacency-list";
753 }
754 }
755 }
756 EXPECT_EQ(cnt, reach.size());
757 }
758
TEST_F(LoadStoreAnalysisTest,ReachabilityTest1)759 TEST_F(LoadStoreAnalysisTest, ReachabilityTest1) {
760 CreateGraph();
761 AdjacencyListGraph blks(SetupFromAdjacencyList(
762 "entry",
763 "exit",
764 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
765 CheckReachability(blks,
766 {
767 { "entry", "left" },
768 { "entry", "right" },
769 { "entry", "exit" },
770 { "right", "exit" },
771 { "left", "exit" },
772 });
773 }
774
TEST_F(LoadStoreAnalysisTest,ReachabilityTest2)775 TEST_F(LoadStoreAnalysisTest, ReachabilityTest2) {
776 CreateGraph();
777 AdjacencyListGraph blks(SetupFromAdjacencyList(
778 "entry",
779 "exit",
780 { { "entry", "loop-header" }, { "loop-header", "loop" }, { "loop", "loop-header" } }));
781 CheckReachability(blks,
782 {
783 { "entry", "loop-header" },
784 { "entry", "loop" },
785 { "loop-header", "loop-header" },
786 { "loop-header", "loop" },
787 { "loop", "loop-header" },
788 { "loop", "loop" },
789 });
790 }
791
TEST_F(LoadStoreAnalysisTest,ReachabilityTest3)792 TEST_F(LoadStoreAnalysisTest, ReachabilityTest3) {
793 CreateGraph();
794 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
795 "exit",
796 { { "entry", "loop-header" },
797 { "loop-header", "loop" },
798 { "loop", "loop-header" },
799 { "entry", "right" },
800 { "right", "exit" } }));
801 CheckReachability(blks,
802 {
803 { "entry", "loop-header" },
804 { "entry", "loop" },
805 { "entry", "right" },
806 { "entry", "exit" },
807 { "loop-header", "loop-header" },
808 { "loop-header", "loop" },
809 { "loop", "loop-header" },
810 { "loop", "loop" },
811 { "right", "exit" },
812 });
813 }
814
AreExclusionsIndependent(HGraph * graph,const ExecutionSubgraph * esg)815 static bool AreExclusionsIndependent(HGraph* graph, const ExecutionSubgraph* esg) {
816 auto excluded = esg->GetExcludedCohorts();
817 if (excluded.size() < 2) {
818 return true;
819 }
820 for (auto first = excluded.begin(); first != excluded.end(); ++first) {
821 for (auto second = excluded.begin(); second != excluded.end(); ++second) {
822 if (first == second) {
823 continue;
824 }
825 for (const HBasicBlock* entry : first->EntryBlocks()) {
826 for (const HBasicBlock* exit : second->ExitBlocks()) {
827 if (graph->PathBetween(exit, entry)) {
828 return false;
829 }
830 }
831 }
832 }
833 }
834 return true;
835 }
836
837 // // ENTRY
838 // obj = new Obj();
839 // if (parameter_value) {
840 // // LEFT
841 // call_func(obj);
842 // } else {
843 // // RIGHT
844 // obj.field = 1;
845 // }
846 // // EXIT
847 // obj.field;
TEST_F(LoadStoreAnalysisTest,PartialEscape)848 TEST_F(LoadStoreAnalysisTest, PartialEscape) {
849 CreateGraph();
850 AdjacencyListGraph blks(SetupFromAdjacencyList(
851 "entry",
852 "exit",
853 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
854 HBasicBlock* entry = blks.Get("entry");
855 HBasicBlock* left = blks.Get("left");
856 HBasicBlock* right = blks.Get("right");
857 HBasicBlock* exit = blks.Get("exit");
858
859 HInstruction* bool_value = new (GetAllocator())
860 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
861 HInstruction* c0 = graph_->GetIntConstant(0);
862 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
863 dex::TypeIndex(10),
864 graph_->GetDexFile(),
865 ScopedNullHandle<mirror::Class>(),
866 false,
867 0,
868 false);
869 HInstruction* new_inst =
870 new (GetAllocator()) HNewInstance(cls,
871 0,
872 dex::TypeIndex(10),
873 graph_->GetDexFile(),
874 false,
875 QuickEntrypointEnum::kQuickAllocObjectInitialized);
876 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
877 entry->AddInstruction(bool_value);
878 entry->AddInstruction(cls);
879 entry->AddInstruction(new_inst);
880 entry->AddInstruction(if_inst);
881
882 HInstruction* call_left = new (GetAllocator())
883 HInvokeStaticOrDirect(GetAllocator(),
884 1,
885 DataType::Type::kVoid,
886 0,
887 { nullptr, 0 },
888 nullptr,
889 {},
890 InvokeType::kStatic,
891 { nullptr, 0 },
892 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
893 HInstruction* goto_left = new (GetAllocator()) HGoto();
894 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
895 left->AddInstruction(call_left);
896 left->AddInstruction(goto_left);
897
898 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
899 c0,
900 nullptr,
901 DataType::Type::kInt32,
902 MemberOffset(32),
903 false,
904 0,
905 0,
906 graph_->GetDexFile(),
907 0);
908 HInstruction* goto_right = new (GetAllocator()) HGoto();
909 right->AddInstruction(write_right);
910 right->AddInstruction(goto_right);
911
912 HInstruction* read_final = new (GetAllocator()) HInstanceFieldGet(new_inst,
913 nullptr,
914 DataType::Type::kInt32,
915 MemberOffset(32),
916 false,
917 0,
918 0,
919 graph_->GetDexFile(),
920 0);
921 exit->AddInstruction(read_final);
922
923 ScopedArenaAllocator allocator(graph_->GetArenaStack());
924 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, LoadStoreAnalysisType::kFull);
925 lsa.Run();
926
927 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
928 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
929 ASSERT_TRUE(info->IsPartialSingleton());
930 const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
931
932 ASSERT_TRUE(esg->IsValid());
933 ASSERT_TRUE(IsValidSubgraph(esg));
934 ASSERT_TRUE(AreExclusionsIndependent(graph_, esg));
935 std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
936 esg->ReachableBlocks().end());
937
938 ASSERT_EQ(contents.size(), 3u);
939 ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
940
941 ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
942 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
943 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
944 }
945
946 // // ENTRY
947 // obj = new Obj();
948 // if (parameter_value) {
949 // // LEFT
950 // call_func(obj);
951 // } else {
952 // // RIGHT
953 // obj.field = 1;
954 // }
955 // // EXIT
956 // obj.field2;
TEST_F(LoadStoreAnalysisTest,PartialEscape2)957 TEST_F(LoadStoreAnalysisTest, PartialEscape2) {
958 CreateGraph();
959 AdjacencyListGraph blks(SetupFromAdjacencyList(
960 "entry",
961 "exit",
962 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
963 HBasicBlock* entry = blks.Get("entry");
964 HBasicBlock* left = blks.Get("left");
965 HBasicBlock* right = blks.Get("right");
966 HBasicBlock* exit = blks.Get("exit");
967
968 HInstruction* bool_value = new (GetAllocator())
969 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
970 HInstruction* c0 = graph_->GetIntConstant(0);
971 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
972 dex::TypeIndex(10),
973 graph_->GetDexFile(),
974 ScopedNullHandle<mirror::Class>(),
975 false,
976 0,
977 false);
978 HInstruction* new_inst =
979 new (GetAllocator()) HNewInstance(cls,
980 0,
981 dex::TypeIndex(10),
982 graph_->GetDexFile(),
983 false,
984 QuickEntrypointEnum::kQuickAllocObjectInitialized);
985 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
986 entry->AddInstruction(bool_value);
987 entry->AddInstruction(cls);
988 entry->AddInstruction(new_inst);
989 entry->AddInstruction(if_inst);
990
991 HInstruction* call_left = new (GetAllocator())
992 HInvokeStaticOrDirect(GetAllocator(),
993 1,
994 DataType::Type::kVoid,
995 0,
996 { nullptr, 0 },
997 nullptr,
998 {},
999 InvokeType::kStatic,
1000 { nullptr, 0 },
1001 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1002 HInstruction* goto_left = new (GetAllocator()) HGoto();
1003 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
1004 left->AddInstruction(call_left);
1005 left->AddInstruction(goto_left);
1006
1007 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
1008 c0,
1009 nullptr,
1010 DataType::Type::kInt32,
1011 MemberOffset(32),
1012 false,
1013 0,
1014 0,
1015 graph_->GetDexFile(),
1016 0);
1017 HInstruction* goto_right = new (GetAllocator()) HGoto();
1018 right->AddInstruction(write_right);
1019 right->AddInstruction(goto_right);
1020
1021 HInstruction* read_final = new (GetAllocator()) HInstanceFieldGet(new_inst,
1022 nullptr,
1023 DataType::Type::kInt32,
1024 MemberOffset(16),
1025 false,
1026 0,
1027 0,
1028 graph_->GetDexFile(),
1029 0);
1030 exit->AddInstruction(read_final);
1031
1032 ScopedArenaAllocator allocator(graph_->GetArenaStack());
1033 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, LoadStoreAnalysisType::kFull);
1034 lsa.Run();
1035
1036 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
1037 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
1038 ASSERT_TRUE(info->IsPartialSingleton());
1039 const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
1040
1041 ASSERT_TRUE(esg->IsValid());
1042 ASSERT_TRUE(IsValidSubgraph(esg));
1043 ASSERT_TRUE(AreExclusionsIndependent(graph_, esg));
1044 std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
1045 esg->ReachableBlocks().end());
1046
1047 ASSERT_EQ(contents.size(), 3u);
1048 ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
1049
1050 ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
1051 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
1052 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
1053 }
1054
1055 // // ENTRY
1056 // obj = new Obj();
1057 // obj.field = 10;
1058 // if (parameter_value) {
1059 // // LEFT
1060 // call_func(obj);
1061 // } else {
1062 // // RIGHT
1063 // obj.field = 20;
1064 // }
1065 // // EXIT
1066 // obj.field;
TEST_F(LoadStoreAnalysisTest,PartialEscape3)1067 TEST_F(LoadStoreAnalysisTest, PartialEscape3) {
1068 CreateGraph();
1069 AdjacencyListGraph blks(SetupFromAdjacencyList(
1070 "entry",
1071 "exit",
1072 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
1073 HBasicBlock* entry = blks.Get("entry");
1074 HBasicBlock* left = blks.Get("left");
1075 HBasicBlock* right = blks.Get("right");
1076 HBasicBlock* exit = blks.Get("exit");
1077
1078 HInstruction* bool_value = new (GetAllocator())
1079 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
1080 HInstruction* c10 = graph_->GetIntConstant(10);
1081 HInstruction* c20 = graph_->GetIntConstant(20);
1082 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
1083 dex::TypeIndex(10),
1084 graph_->GetDexFile(),
1085 ScopedNullHandle<mirror::Class>(),
1086 false,
1087 0,
1088 false);
1089 HInstruction* new_inst =
1090 new (GetAllocator()) HNewInstance(cls,
1091 0,
1092 dex::TypeIndex(10),
1093 graph_->GetDexFile(),
1094 false,
1095 QuickEntrypointEnum::kQuickAllocObjectInitialized);
1096
1097 HInstruction* write_entry = new (GetAllocator()) HInstanceFieldSet(new_inst,
1098 c10,
1099 nullptr,
1100 DataType::Type::kInt32,
1101 MemberOffset(32),
1102 false,
1103 0,
1104 0,
1105 graph_->GetDexFile(),
1106 0);
1107 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
1108 entry->AddInstruction(bool_value);
1109 entry->AddInstruction(cls);
1110 entry->AddInstruction(new_inst);
1111 entry->AddInstruction(write_entry);
1112 entry->AddInstruction(if_inst);
1113
1114 HInstruction* call_left = new (GetAllocator())
1115 HInvokeStaticOrDirect(GetAllocator(),
1116 1,
1117 DataType::Type::kVoid,
1118 0,
1119 { nullptr, 0 },
1120 nullptr,
1121 {},
1122 InvokeType::kStatic,
1123 { nullptr, 0 },
1124 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1125 HInstruction* goto_left = new (GetAllocator()) HGoto();
1126 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
1127 left->AddInstruction(call_left);
1128 left->AddInstruction(goto_left);
1129
1130 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
1131 c20,
1132 nullptr,
1133 DataType::Type::kInt32,
1134 MemberOffset(32),
1135 false,
1136 0,
1137 0,
1138 graph_->GetDexFile(),
1139 0);
1140 HInstruction* goto_right = new (GetAllocator()) HGoto();
1141 right->AddInstruction(write_right);
1142 right->AddInstruction(goto_right);
1143
1144 HInstruction* read_final = new (GetAllocator()) HInstanceFieldGet(new_inst,
1145 nullptr,
1146 DataType::Type::kInt32,
1147 MemberOffset(32),
1148 false,
1149 0,
1150 0,
1151 graph_->GetDexFile(),
1152 0);
1153 exit->AddInstruction(read_final);
1154
1155 ScopedArenaAllocator allocator(graph_->GetArenaStack());
1156 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, LoadStoreAnalysisType::kFull);
1157 lsa.Run();
1158
1159 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
1160 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
1161 ASSERT_TRUE(info->IsPartialSingleton());
1162 const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
1163
1164 ASSERT_TRUE(esg->IsValid());
1165 ASSERT_TRUE(IsValidSubgraph(esg));
1166 ASSERT_TRUE(AreExclusionsIndependent(graph_, esg));
1167 std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
1168 esg->ReachableBlocks().end());
1169
1170 ASSERT_EQ(contents.size(), 3u);
1171 ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
1172
1173 ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
1174 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
1175 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
1176 }
1177
1178 // For simplicity Partial LSE considers check-casts to escape. It means we don't
1179 // need to worry about inserting throws.
1180 // // ENTRY
1181 // obj = new Obj();
1182 // obj.field = 10;
1183 // if (parameter_value) {
1184 // // LEFT
1185 // (Foo)obj;
1186 // } else {
1187 // // RIGHT
1188 // obj.field = 20;
1189 // }
1190 // // EXIT
1191 // obj.field;
TEST_F(LoadStoreAnalysisTest,PartialEscape4)1192 TEST_F(LoadStoreAnalysisTest, PartialEscape4) {
1193 CreateGraph();
1194 AdjacencyListGraph blks(SetupFromAdjacencyList(
1195 "entry",
1196 "exit",
1197 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
1198 HBasicBlock* entry = blks.Get("entry");
1199 HBasicBlock* left = blks.Get("left");
1200 HBasicBlock* right = blks.Get("right");
1201 HBasicBlock* exit = blks.Get("exit");
1202
1203 HInstruction* bool_value = new (GetAllocator())
1204 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
1205 HInstruction* c10 = graph_->GetIntConstant(10);
1206 HInstruction* c20 = graph_->GetIntConstant(20);
1207 HInstruction* cls = MakeClassLoad();
1208 HInstruction* new_inst = MakeNewInstance(cls);
1209
1210 HInstruction* write_entry = MakeIFieldSet(new_inst, c10, MemberOffset(32));
1211 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
1212 entry->AddInstruction(bool_value);
1213 entry->AddInstruction(cls);
1214 entry->AddInstruction(new_inst);
1215 entry->AddInstruction(write_entry);
1216 entry->AddInstruction(if_inst);
1217
1218 ScopedNullHandle<mirror::Class> null_klass_;
1219 HInstruction* cls2 = MakeClassLoad();
1220 HInstruction* check_cast = new (GetAllocator()) HCheckCast(
1221 new_inst, cls2, TypeCheckKind::kExactCheck, null_klass_, 0, GetAllocator(), nullptr, nullptr);
1222 HInstruction* goto_left = new (GetAllocator()) HGoto();
1223 left->AddInstruction(cls2);
1224 left->AddInstruction(check_cast);
1225 left->AddInstruction(goto_left);
1226
1227 HInstruction* write_right = MakeIFieldSet(new_inst, c20, MemberOffset(32));
1228 HInstruction* goto_right = new (GetAllocator()) HGoto();
1229 right->AddInstruction(write_right);
1230 right->AddInstruction(goto_right);
1231
1232 HInstruction* read_final = MakeIFieldGet(new_inst, DataType::Type::kInt32, MemberOffset(32));
1233 exit->AddInstruction(read_final);
1234
1235 ScopedArenaAllocator allocator(graph_->GetArenaStack());
1236 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, LoadStoreAnalysisType::kFull);
1237 lsa.Run();
1238
1239 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
1240 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
1241 ASSERT_TRUE(info->IsPartialSingleton());
1242 const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
1243
1244 ASSERT_TRUE(esg->IsValid());
1245 ASSERT_TRUE(IsValidSubgraph(esg));
1246 ASSERT_TRUE(AreExclusionsIndependent(graph_, esg));
1247 std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
1248 esg->ReachableBlocks().end());
1249
1250 ASSERT_EQ(contents.size(), 3u);
1251 ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
1252
1253 ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
1254 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
1255 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
1256 }
1257
1258 // For simplicity Partial LSE considers instance-ofs with bitvectors to escape.
1259 // // ENTRY
1260 // obj = new Obj();
1261 // obj.field = 10;
1262 // if (parameter_value) {
1263 // // LEFT
1264 // obj instanceof /*bitvector*/ Foo;
1265 // } else {
1266 // // RIGHT
1267 // obj.field = 20;
1268 // }
1269 // // EXIT
1270 // obj.field;
TEST_F(LoadStoreAnalysisTest,PartialEscape5)1271 TEST_F(LoadStoreAnalysisTest, PartialEscape5) {
1272 ScopedObjectAccess soa(Thread::Current());
1273 VariableSizedHandleScope vshs(soa.Self());
1274 CreateGraph(&vshs);
1275 AdjacencyListGraph blks(SetupFromAdjacencyList(
1276 "entry",
1277 "exit",
1278 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
1279 HBasicBlock* entry = blks.Get("entry");
1280 HBasicBlock* left = blks.Get("left");
1281 HBasicBlock* right = blks.Get("right");
1282 HBasicBlock* exit = blks.Get("exit");
1283
1284 HInstruction* bool_value = new (GetAllocator())
1285 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
1286 HInstruction* c10 = graph_->GetIntConstant(10);
1287 HInstruction* c20 = graph_->GetIntConstant(20);
1288 HIntConstant* bs1 = graph_->GetIntConstant(0xffff);
1289 HIntConstant* bs2 = graph_->GetIntConstant(0x00ff);
1290 HInstruction* cls = MakeClassLoad();
1291 HInstruction* null_const = graph_->GetNullConstant();
1292 HInstruction* new_inst = MakeNewInstance(cls);
1293
1294 HInstruction* write_entry = MakeIFieldSet(new_inst, c10, MemberOffset(32));
1295 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
1296 entry->AddInstruction(bool_value);
1297 entry->AddInstruction(cls);
1298 entry->AddInstruction(new_inst);
1299 entry->AddInstruction(write_entry);
1300 entry->AddInstruction(if_inst);
1301
1302 ScopedNullHandle<mirror::Class> null_klass_;
1303 HInstruction* instanceof = new (GetAllocator()) HInstanceOf(new_inst,
1304 null_const,
1305 TypeCheckKind::kBitstringCheck,
1306 null_klass_,
1307 0,
1308 GetAllocator(),
1309 bs1,
1310 bs2);
1311 HInstruction* goto_left = new (GetAllocator()) HGoto();
1312 left->AddInstruction(instanceof);
1313 left->AddInstruction(goto_left);
1314
1315 HInstruction* write_right = MakeIFieldSet(new_inst, c20, MemberOffset(32));
1316 HInstruction* goto_right = new (GetAllocator()) HGoto();
1317 right->AddInstruction(write_right);
1318 right->AddInstruction(goto_right);
1319
1320 HInstruction* read_final = MakeIFieldGet(new_inst, DataType::Type::kInt32, MemberOffset(32));
1321 exit->AddInstruction(read_final);
1322
1323 ScopedArenaAllocator allocator(graph_->GetArenaStack());
1324 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, LoadStoreAnalysisType::kFull);
1325 lsa.Run();
1326
1327 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
1328 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
1329 ASSERT_TRUE(info->IsPartialSingleton());
1330 const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
1331
1332 ASSERT_TRUE(esg->IsValid());
1333 ASSERT_TRUE(IsValidSubgraph(esg));
1334 ASSERT_TRUE(AreExclusionsIndependent(graph_, esg));
1335 std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
1336 esg->ReachableBlocks().end());
1337
1338 ASSERT_EQ(contents.size(), 3u);
1339 ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
1340
1341 ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
1342 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
1343 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
1344 }
1345
1346 // before we had predicated-set we needed to be able to remove the store as
1347 // well. This test makes sure that still works.
1348 // // ENTRY
1349 // obj = new Obj();
1350 // if (parameter_value) {
1351 // // LEFT
1352 // call_func(obj);
1353 // } else {
1354 // // RIGHT
1355 // obj.f1 = 0;
1356 // }
1357 // // EXIT
1358 // // call_func prevents the elimination of this store.
1359 // obj.f2 = 0;
TEST_F(LoadStoreAnalysisTest,TotalEscapeAdjacentNoPredicated)1360 TEST_F(LoadStoreAnalysisTest, TotalEscapeAdjacentNoPredicated) {
1361 CreateGraph();
1362 AdjacencyListGraph blks(SetupFromAdjacencyList(
1363 "entry",
1364 "exit",
1365 {{"entry", "left"}, {"entry", "right"}, {"left", "exit"}, {"right", "exit"}}));
1366 HBasicBlock* entry = blks.Get("entry");
1367 HBasicBlock* left = blks.Get("left");
1368 HBasicBlock* right = blks.Get("right");
1369 HBasicBlock* exit = blks.Get("exit");
1370
1371 HInstruction* bool_value = new (GetAllocator())
1372 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
1373 HInstruction* c0 = graph_->GetIntConstant(0);
1374 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
1375 dex::TypeIndex(10),
1376 graph_->GetDexFile(),
1377 ScopedNullHandle<mirror::Class>(),
1378 false,
1379 0,
1380 false);
1381 HInstruction* new_inst =
1382 new (GetAllocator()) HNewInstance(cls,
1383 0,
1384 dex::TypeIndex(10),
1385 graph_->GetDexFile(),
1386 false,
1387 QuickEntrypointEnum::kQuickAllocObjectInitialized);
1388 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
1389 entry->AddInstruction(bool_value);
1390 entry->AddInstruction(cls);
1391 entry->AddInstruction(new_inst);
1392 entry->AddInstruction(if_inst);
1393
1394 HInstruction* call_left = new (GetAllocator())
1395 HInvokeStaticOrDirect(GetAllocator(),
1396 1,
1397 DataType::Type::kVoid,
1398 0,
1399 {nullptr, 0},
1400 nullptr,
1401 {},
1402 InvokeType::kStatic,
1403 {nullptr, 0},
1404 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1405 HInstruction* goto_left = new (GetAllocator()) HGoto();
1406 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
1407 left->AddInstruction(call_left);
1408 left->AddInstruction(goto_left);
1409
1410 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
1411 c0,
1412 nullptr,
1413 DataType::Type::kInt32,
1414 MemberOffset(32),
1415 false,
1416 0,
1417 0,
1418 graph_->GetDexFile(),
1419 0);
1420 HInstruction* goto_right = new (GetAllocator()) HGoto();
1421 right->AddInstruction(write_right);
1422 right->AddInstruction(goto_right);
1423
1424 HInstruction* write_final = new (GetAllocator()) HInstanceFieldSet(new_inst,
1425 c0,
1426 nullptr,
1427 DataType::Type::kInt32,
1428 MemberOffset(16),
1429 false,
1430 0,
1431 0,
1432 graph_->GetDexFile(),
1433 0);
1434 exit->AddInstruction(write_final);
1435
1436 ScopedArenaAllocator allocator(graph_->GetArenaStack());
1437 graph_->ClearDominanceInformation();
1438 graph_->BuildDominatorTree();
1439 LoadStoreAnalysis lsa(
1440 graph_, nullptr, &allocator, LoadStoreAnalysisType::kNoPredicatedInstructions);
1441 lsa.Run();
1442
1443 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
1444 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
1445 ASSERT_FALSE(info->IsPartialSingleton());
1446 }
1447
1448 // With predicated-set we can (partially) remove the store as well.
1449 // // ENTRY
1450 // obj = new Obj();
1451 // if (parameter_value) {
1452 // // LEFT
1453 // call_func(obj);
1454 // } else {
1455 // // RIGHT
1456 // obj.f1 = 0;
1457 // }
1458 // // EXIT
1459 // // call_func prevents the elimination of this store.
1460 // obj.f2 = 0;
TEST_F(LoadStoreAnalysisTest,TotalEscapeAdjacent)1461 TEST_F(LoadStoreAnalysisTest, TotalEscapeAdjacent) {
1462 CreateGraph();
1463 AdjacencyListGraph blks(SetupFromAdjacencyList(
1464 "entry",
1465 "exit",
1466 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
1467 HBasicBlock* entry = blks.Get("entry");
1468 HBasicBlock* left = blks.Get("left");
1469 HBasicBlock* right = blks.Get("right");
1470 HBasicBlock* exit = blks.Get("exit");
1471
1472 HInstruction* bool_value = new (GetAllocator())
1473 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
1474 HInstruction* c0 = graph_->GetIntConstant(0);
1475 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
1476 dex::TypeIndex(10),
1477 graph_->GetDexFile(),
1478 ScopedNullHandle<mirror::Class>(),
1479 false,
1480 0,
1481 false);
1482 HInstruction* new_inst =
1483 new (GetAllocator()) HNewInstance(cls,
1484 0,
1485 dex::TypeIndex(10),
1486 graph_->GetDexFile(),
1487 false,
1488 QuickEntrypointEnum::kQuickAllocObjectInitialized);
1489 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
1490 entry->AddInstruction(bool_value);
1491 entry->AddInstruction(cls);
1492 entry->AddInstruction(new_inst);
1493 entry->AddInstruction(if_inst);
1494
1495 HInstruction* call_left = new (GetAllocator())
1496 HInvokeStaticOrDirect(GetAllocator(),
1497 1,
1498 DataType::Type::kVoid,
1499 0,
1500 { nullptr, 0 },
1501 nullptr,
1502 {},
1503 InvokeType::kStatic,
1504 { nullptr, 0 },
1505 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1506 HInstruction* goto_left = new (GetAllocator()) HGoto();
1507 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
1508 left->AddInstruction(call_left);
1509 left->AddInstruction(goto_left);
1510
1511 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
1512 c0,
1513 nullptr,
1514 DataType::Type::kInt32,
1515 MemberOffset(32),
1516 false,
1517 0,
1518 0,
1519 graph_->GetDexFile(),
1520 0);
1521 HInstruction* goto_right = new (GetAllocator()) HGoto();
1522 right->AddInstruction(write_right);
1523 right->AddInstruction(goto_right);
1524
1525 HInstruction* write_final = new (GetAllocator()) HInstanceFieldSet(new_inst,
1526 c0,
1527 nullptr,
1528 DataType::Type::kInt32,
1529 MemberOffset(16),
1530 false,
1531 0,
1532 0,
1533 graph_->GetDexFile(),
1534 0);
1535 exit->AddInstruction(write_final);
1536
1537 ScopedArenaAllocator allocator(graph_->GetArenaStack());
1538 graph_->ClearDominanceInformation();
1539 graph_->BuildDominatorTree();
1540 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, LoadStoreAnalysisType::kFull);
1541 lsa.Run();
1542
1543 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
1544 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
1545 ASSERT_TRUE(info->IsPartialSingleton());
1546 const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
1547
1548 EXPECT_TRUE(esg->IsValid()) << esg->GetExcludedCohorts();
1549 EXPECT_TRUE(IsValidSubgraph(esg));
1550 std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
1551 esg->ReachableBlocks().end());
1552
1553 EXPECT_EQ(contents.size(), 3u);
1554 EXPECT_TRUE(contents.find(blks.Get("left")) == contents.end());
1555 EXPECT_FALSE(contents.find(blks.Get("right")) == contents.end());
1556 EXPECT_FALSE(contents.find(blks.Get("entry")) == contents.end());
1557 EXPECT_FALSE(contents.find(blks.Get("exit")) == contents.end());
1558 }
1559
1560 // // ENTRY
1561 // obj = new Obj();
1562 // if (parameter_value) {
1563 // // LEFT
1564 // call_func(obj);
1565 // } else {
1566 // // RIGHT
1567 // obj.f0 = 0;
1568 // call_func2(obj);
1569 // }
1570 // // EXIT
1571 // obj.f0;
TEST_F(LoadStoreAnalysisTest,TotalEscape)1572 TEST_F(LoadStoreAnalysisTest, TotalEscape) {
1573 CreateGraph();
1574 AdjacencyListGraph blks(SetupFromAdjacencyList(
1575 "entry",
1576 "exit",
1577 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
1578 HBasicBlock* entry = blks.Get("entry");
1579 HBasicBlock* left = blks.Get("left");
1580 HBasicBlock* right = blks.Get("right");
1581 HBasicBlock* exit = blks.Get("exit");
1582
1583 HInstruction* bool_value = new (GetAllocator())
1584 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
1585 HInstruction* c0 = graph_->GetIntConstant(0);
1586 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
1587 dex::TypeIndex(10),
1588 graph_->GetDexFile(),
1589 ScopedNullHandle<mirror::Class>(),
1590 false,
1591 0,
1592 false);
1593 HInstruction* new_inst =
1594 new (GetAllocator()) HNewInstance(cls,
1595 0,
1596 dex::TypeIndex(10),
1597 graph_->GetDexFile(),
1598 false,
1599 QuickEntrypointEnum::kQuickAllocObjectInitialized);
1600 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
1601 entry->AddInstruction(bool_value);
1602 entry->AddInstruction(cls);
1603 entry->AddInstruction(new_inst);
1604 entry->AddInstruction(if_inst);
1605
1606 HInstruction* call_left = new (GetAllocator())
1607 HInvokeStaticOrDirect(GetAllocator(),
1608 1,
1609 DataType::Type::kVoid,
1610 0,
1611 { nullptr, 0 },
1612 nullptr,
1613 {},
1614 InvokeType::kStatic,
1615 { nullptr, 0 },
1616 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1617 HInstruction* goto_left = new (GetAllocator()) HGoto();
1618 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
1619 left->AddInstruction(call_left);
1620 left->AddInstruction(goto_left);
1621
1622 HInstruction* call_right = new (GetAllocator())
1623 HInvokeStaticOrDirect(GetAllocator(),
1624 1,
1625 DataType::Type::kVoid,
1626 0,
1627 { nullptr, 0 },
1628 nullptr,
1629 {},
1630 InvokeType::kStatic,
1631 { nullptr, 0 },
1632 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1633 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
1634 c0,
1635 nullptr,
1636 DataType::Type::kInt32,
1637 MemberOffset(32),
1638 false,
1639 0,
1640 0,
1641 graph_->GetDexFile(),
1642 0);
1643 HInstruction* goto_right = new (GetAllocator()) HGoto();
1644 call_right->AsInvoke()->SetRawInputAt(0, new_inst);
1645 right->AddInstruction(write_right);
1646 right->AddInstruction(call_right);
1647 right->AddInstruction(goto_right);
1648
1649 HInstruction* read_final = new (GetAllocator()) HInstanceFieldGet(new_inst,
1650 nullptr,
1651 DataType::Type::kInt32,
1652 MemberOffset(32),
1653 false,
1654 0,
1655 0,
1656 graph_->GetDexFile(),
1657 0);
1658 exit->AddInstruction(read_final);
1659
1660 ScopedArenaAllocator allocator(graph_->GetArenaStack());
1661 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, LoadStoreAnalysisType::kFull);
1662 lsa.Run();
1663
1664 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
1665 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
1666 ASSERT_FALSE(info->IsPartialSingleton());
1667 }
1668
1669 // // ENTRY
1670 // obj = new Obj();
1671 // obj.foo = 0;
1672 // // EXIT
1673 // return obj;
TEST_F(LoadStoreAnalysisTest,TotalEscape2)1674 TEST_F(LoadStoreAnalysisTest, TotalEscape2) {
1675 CreateGraph();
1676 AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", { { "entry", "exit" } }));
1677 HBasicBlock* entry = blks.Get("entry");
1678 HBasicBlock* exit = blks.Get("exit");
1679
1680 HInstruction* c0 = graph_->GetIntConstant(0);
1681 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
1682 dex::TypeIndex(10),
1683 graph_->GetDexFile(),
1684 ScopedNullHandle<mirror::Class>(),
1685 false,
1686 0,
1687 false);
1688 HInstruction* new_inst =
1689 new (GetAllocator()) HNewInstance(cls,
1690 0,
1691 dex::TypeIndex(10),
1692 graph_->GetDexFile(),
1693 false,
1694 QuickEntrypointEnum::kQuickAllocObjectInitialized);
1695
1696 HInstruction* write_start = new (GetAllocator()) HInstanceFieldSet(new_inst,
1697 c0,
1698 nullptr,
1699 DataType::Type::kInt32,
1700 MemberOffset(32),
1701 false,
1702 0,
1703 0,
1704 graph_->GetDexFile(),
1705 0);
1706 HInstruction* goto_inst = new (GetAllocator()) HGoto();
1707 entry->AddInstruction(cls);
1708 entry->AddInstruction(new_inst);
1709 entry->AddInstruction(write_start);
1710 entry->AddInstruction(goto_inst);
1711
1712 HInstruction* return_final = new (GetAllocator()) HReturn(new_inst);
1713 exit->AddInstruction(return_final);
1714
1715 ScopedArenaAllocator allocator(graph_->GetArenaStack());
1716 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, LoadStoreAnalysisType::kFull);
1717 lsa.Run();
1718
1719 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
1720 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
1721 ASSERT_FALSE(info->IsPartialSingleton());
1722 }
1723
1724 // // ENTRY
1725 // obj = new Obj();
1726 // if (parameter_value) {
1727 // // HIGH_LEFT
1728 // call_func(obj);
1729 // } else {
1730 // // HIGH_RIGHT
1731 // obj.f0 = 1;
1732 // }
1733 // // MID
1734 // obj.f0 *= 2;
1735 // if (parameter_value2) {
1736 // // LOW_LEFT
1737 // call_func(obj);
1738 // } else {
1739 // // LOW_RIGHT
1740 // obj.f0 = 1;
1741 // }
1742 // // EXIT
1743 // obj.f0
TEST_F(LoadStoreAnalysisTest,DoubleDiamondEscape)1744 TEST_F(LoadStoreAnalysisTest, DoubleDiamondEscape) {
1745 CreateGraph();
1746 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
1747 "exit",
1748 { { "entry", "high_left" },
1749 { "entry", "high_right" },
1750 { "low_left", "exit" },
1751 { "low_right", "exit" },
1752 { "high_right", "mid" },
1753 { "high_left", "mid" },
1754 { "mid", "low_left" },
1755 { "mid", "low_right" } }));
1756 HBasicBlock* entry = blks.Get("entry");
1757 HBasicBlock* high_left = blks.Get("high_left");
1758 HBasicBlock* high_right = blks.Get("high_right");
1759 HBasicBlock* mid = blks.Get("mid");
1760 HBasicBlock* low_left = blks.Get("low_left");
1761 HBasicBlock* low_right = blks.Get("low_right");
1762 HBasicBlock* exit = blks.Get("exit");
1763
1764 HInstruction* bool_value1 = new (GetAllocator())
1765 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
1766 HInstruction* bool_value2 = new (GetAllocator())
1767 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 2, DataType::Type::kBool);
1768 HInstruction* c0 = graph_->GetIntConstant(0);
1769 HInstruction* c2 = graph_->GetIntConstant(2);
1770 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
1771 dex::TypeIndex(10),
1772 graph_->GetDexFile(),
1773 ScopedNullHandle<mirror::Class>(),
1774 false,
1775 0,
1776 false);
1777 HInstruction* new_inst =
1778 new (GetAllocator()) HNewInstance(cls,
1779 0,
1780 dex::TypeIndex(10),
1781 graph_->GetDexFile(),
1782 false,
1783 QuickEntrypointEnum::kQuickAllocObjectInitialized);
1784 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value1);
1785 entry->AddInstruction(bool_value1);
1786 entry->AddInstruction(bool_value2);
1787 entry->AddInstruction(cls);
1788 entry->AddInstruction(new_inst);
1789 entry->AddInstruction(if_inst);
1790
1791 HInstruction* call_left = new (GetAllocator())
1792 HInvokeStaticOrDirect(GetAllocator(),
1793 1,
1794 DataType::Type::kVoid,
1795 0,
1796 { nullptr, 0 },
1797 nullptr,
1798 {},
1799 InvokeType::kStatic,
1800 { nullptr, 0 },
1801 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1802 HInstruction* goto_left = new (GetAllocator()) HGoto();
1803 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
1804 high_left->AddInstruction(call_left);
1805 high_left->AddInstruction(goto_left);
1806
1807 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
1808 c0,
1809 nullptr,
1810 DataType::Type::kInt32,
1811 MemberOffset(32),
1812 false,
1813 0,
1814 0,
1815 graph_->GetDexFile(),
1816 0);
1817 HInstruction* goto_right = new (GetAllocator()) HGoto();
1818 high_right->AddInstruction(write_right);
1819 high_right->AddInstruction(goto_right);
1820
1821 HInstruction* read_mid = new (GetAllocator()) HInstanceFieldGet(new_inst,
1822 nullptr,
1823 DataType::Type::kInt32,
1824 MemberOffset(32),
1825 false,
1826 0,
1827 0,
1828 graph_->GetDexFile(),
1829 0);
1830 HInstruction* mul_mid = new (GetAllocator()) HMul(DataType::Type::kInt32, read_mid, c2);
1831 HInstruction* write_mid = new (GetAllocator()) HInstanceFieldSet(new_inst,
1832 mul_mid,
1833 nullptr,
1834 DataType::Type::kInt32,
1835 MemberOffset(32),
1836 false,
1837 0,
1838 0,
1839 graph_->GetDexFile(),
1840 0);
1841 HInstruction* if_mid = new (GetAllocator()) HIf(bool_value2);
1842 mid->AddInstruction(read_mid);
1843 mid->AddInstruction(mul_mid);
1844 mid->AddInstruction(write_mid);
1845 mid->AddInstruction(if_mid);
1846
1847 HInstruction* call_low_left = new (GetAllocator())
1848 HInvokeStaticOrDirect(GetAllocator(),
1849 1,
1850 DataType::Type::kVoid,
1851 0,
1852 { nullptr, 0 },
1853 nullptr,
1854 {},
1855 InvokeType::kStatic,
1856 { nullptr, 0 },
1857 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1858 HInstruction* goto_low_left = new (GetAllocator()) HGoto();
1859 call_low_left->AsInvoke()->SetRawInputAt(0, new_inst);
1860 low_left->AddInstruction(call_low_left);
1861 low_left->AddInstruction(goto_low_left);
1862
1863 HInstruction* write_low_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
1864 c0,
1865 nullptr,
1866 DataType::Type::kInt32,
1867 MemberOffset(32),
1868 false,
1869 0,
1870 0,
1871 graph_->GetDexFile(),
1872 0);
1873 HInstruction* goto_low_right = new (GetAllocator()) HGoto();
1874 low_right->AddInstruction(write_low_right);
1875 low_right->AddInstruction(goto_low_right);
1876
1877 HInstruction* read_final = new (GetAllocator()) HInstanceFieldGet(new_inst,
1878 nullptr,
1879 DataType::Type::kInt32,
1880 MemberOffset(32),
1881 false,
1882 0,
1883 0,
1884 graph_->GetDexFile(),
1885 0);
1886 exit->AddInstruction(read_final);
1887
1888 ScopedArenaAllocator allocator(graph_->GetArenaStack());
1889 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, LoadStoreAnalysisType::kFull);
1890 lsa.Run();
1891
1892 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
1893 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
1894 ASSERT_FALSE(info->IsPartialSingleton());
1895 }
1896
1897 // // ENTRY
1898 // Obj new_inst = new Obj();
1899 // new_inst.foo = 12;
1900 // Obj obj;
1901 // Obj out;
1902 // if (param1) {
1903 // // LEFT_START
1904 // if (param2) {
1905 // // LEFT_LEFT
1906 // obj = new_inst;
1907 // } else {
1908 // // LEFT_RIGHT
1909 // obj = obj_param;
1910 // }
1911 // // LEFT_MERGE
1912 // // technically the phi is enough to cause an escape but might as well be
1913 // // thorough.
1914 // // obj = phi[new_inst, param]
1915 // escape(obj);
1916 // out = obj;
1917 // } else {
1918 // // RIGHT
1919 // out = obj_param;
1920 // }
1921 // // EXIT
1922 // // Can't do anything with this since we don't have good tracking for the heap-locations
1923 // // out = phi[param, phi[new_inst, param]]
1924 // return out.foo
TEST_F(LoadStoreAnalysisTest,PartialPhiPropagation1)1925 TEST_F(LoadStoreAnalysisTest, PartialPhiPropagation1) {
1926 CreateGraph();
1927 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
1928 "exit",
1929 {{"entry", "left"},
1930 {"entry", "right"},
1931 {"left", "left_left"},
1932 {"left", "left_right"},
1933 {"left_left", "left_merge"},
1934 {"left_right", "left_merge"},
1935 {"left_merge", "breturn"},
1936 {"right", "breturn"},
1937 {"breturn", "exit"}}));
1938 #define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
1939 GET_BLOCK(entry);
1940 GET_BLOCK(exit);
1941 GET_BLOCK(breturn);
1942 GET_BLOCK(left);
1943 GET_BLOCK(right);
1944 GET_BLOCK(left_left);
1945 GET_BLOCK(left_right);
1946 GET_BLOCK(left_merge);
1947 #undef GET_BLOCK
1948 EnsurePredecessorOrder(breturn, {left_merge, right});
1949 EnsurePredecessorOrder(left_merge, {left_left, left_right});
1950 HInstruction* param1 = new (GetAllocator())
1951 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
1952 HInstruction* param2 = new (GetAllocator())
1953 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 2, DataType::Type::kBool);
1954 HInstruction* obj_param = new (GetAllocator())
1955 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(10), 3, DataType::Type::kReference);
1956 HInstruction* c12 = graph_->GetIntConstant(12);
1957 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
1958 dex::TypeIndex(10),
1959 graph_->GetDexFile(),
1960 ScopedNullHandle<mirror::Class>(),
1961 false,
1962 0,
1963 false);
1964 HInstruction* new_inst =
1965 new (GetAllocator()) HNewInstance(cls,
1966 0,
1967 dex::TypeIndex(10),
1968 graph_->GetDexFile(),
1969 false,
1970 QuickEntrypointEnum::kQuickAllocObjectInitialized);
1971 HInstruction* store = new (GetAllocator()) HInstanceFieldSet(new_inst,
1972 c12,
1973 nullptr,
1974 DataType::Type::kInt32,
1975 MemberOffset(32),
1976 false,
1977 0,
1978 0,
1979 graph_->GetDexFile(),
1980 0);
1981 HInstruction* if_param1 = new (GetAllocator()) HIf(param1);
1982 entry->AddInstruction(param1);
1983 entry->AddInstruction(param2);
1984 entry->AddInstruction(obj_param);
1985 entry->AddInstruction(cls);
1986 entry->AddInstruction(new_inst);
1987 entry->AddInstruction(store);
1988 entry->AddInstruction(if_param1);
1989 ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
1990 ManuallyBuildEnvFor(cls, ¤t_locals);
1991 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
1992
1993 HInstruction* if_left = new (GetAllocator()) HIf(param2);
1994 left->AddInstruction(if_left);
1995
1996 HInstruction* goto_left_left = new (GetAllocator()) HGoto();
1997 left_left->AddInstruction(goto_left_left);
1998
1999 HInstruction* goto_left_right = new (GetAllocator()) HGoto();
2000 left_right->AddInstruction(goto_left_right);
2001
2002 HPhi* left_phi =
2003 new (GetAllocator()) HPhi(GetAllocator(), kNoRegNumber, 2, DataType::Type::kReference);
2004 HInstruction* call_left = new (GetAllocator())
2005 HInvokeStaticOrDirect(GetAllocator(),
2006 1,
2007 DataType::Type::kVoid,
2008 0,
2009 {nullptr, 0},
2010 nullptr,
2011 {},
2012 InvokeType::kStatic,
2013 {nullptr, 0},
2014 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
2015 HInstruction* goto_left_merge = new (GetAllocator()) HGoto();
2016 left_phi->SetRawInputAt(0, obj_param);
2017 left_phi->SetRawInputAt(1, new_inst);
2018 call_left->AsInvoke()->SetRawInputAt(0, left_phi);
2019 left_merge->AddPhi(left_phi);
2020 left_merge->AddInstruction(call_left);
2021 left_merge->AddInstruction(goto_left_merge);
2022 left_phi->SetCanBeNull(true);
2023 call_left->CopyEnvironmentFrom(cls->GetEnvironment());
2024
2025 HInstruction* goto_right = new (GetAllocator()) HGoto();
2026 right->AddInstruction(goto_right);
2027
2028 HPhi* return_phi =
2029 new (GetAllocator()) HPhi(GetAllocator(), kNoRegNumber, 2, DataType::Type::kReference);
2030 HInstruction* read_exit = new (GetAllocator()) HInstanceFieldGet(return_phi,
2031 nullptr,
2032 DataType::Type::kReference,
2033 MemberOffset(32),
2034 false,
2035 0,
2036 0,
2037 graph_->GetDexFile(),
2038 0);
2039 HInstruction* return_exit = new (GetAllocator()) HReturn(read_exit);
2040 return_phi->SetRawInputAt(0, left_phi);
2041 return_phi->SetRawInputAt(1, obj_param);
2042 breturn->AddPhi(return_phi);
2043 breturn->AddInstruction(read_exit);
2044 breturn->AddInstruction(return_exit);
2045
2046 HInstruction* exit_instruction = new (GetAllocator()) HExit();
2047 exit->AddInstruction(exit_instruction);
2048
2049 graph_->ClearDominanceInformation();
2050 graph_->BuildDominatorTree();
2051
2052 ScopedArenaAllocator allocator(graph_->GetArenaStack());
2053 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, LoadStoreAnalysisType::kFull);
2054 lsa.Run();
2055
2056 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
2057 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
2058 ASSERT_FALSE(info->IsPartialSingleton());
2059 }
2060 } // namespace art
2061