Gitiles
Code Review Sign In
gerrit.witaqua.org / art / b171bc4b117e0d8d399f7a71a95ca5ec6cff19ca / . / compiler / optimizing / load_store_analysis_test.cc
blob: a5b628cf05c59b4d922894e3ad0ee5b196a1e2dc [file] [log] [blame]
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]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"
Alex Light2316b3a2020-11-14 01:28:22 +0000[diff] [blame]18
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]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"
Alex Light2316b3a2020-11-14 01:28:22 +0000[diff] [blame]31#include "gtest/gtest.h"
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]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"
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]38
Vladimir Marko0a516052019-10-14 13:00:44 +0000[diff] [blame]39namespace art {
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]40
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]41class LoadStoreAnalysisTest : public OptimizingUnitTest {
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]42 public:
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]43 LoadStoreAnalysisTest() : graph_(CreateGraph()) {}
44
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
52 bool IsValidSubgraph(const ExecutionSubgraph* esg) {
53 return ExecutionSubgraphTestHelper::CalculateValidity(graph_, esg);
54 }
55
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);
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]61
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]62 HGraph* graph_;
63};
64
65TEST_F(LoadStoreAnalysisTest, ArrayHeapLocations) {
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]66 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]67 graph_->AddBlock(entry);
68 graph_->SetEntryBlock(entry);
69
70 // entry:
71 // array ParameterValue
72 // index ParameterValue
73 // c1 IntConstant
74 // c2 IntConstant
75 // c3 IntConstant
76 // array_get1 ArrayGet [array, c1]
77 // array_get2 ArrayGet [array, c2]
78 // array_set1 ArraySet [array, c1, c3]
79 // array_set2 ArraySet [array, index, c3]
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]80 HInstruction* array = new (GetAllocator()) HParameterValue(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]81 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]82 HInstruction* index = new (GetAllocator()) HParameterValue(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]83 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]84 HInstruction* c1 = graph_->GetIntConstant(1);
85 HInstruction* c2 = graph_->GetIntConstant(2);
86 HInstruction* c3 = graph_->GetIntConstant(3);
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]87 HInstruction* array_get1 = new (GetAllocator()) HArrayGet(array, c1, DataType::Type::kInt32, 0);
88 HInstruction* array_get2 = new (GetAllocator()) HArrayGet(array, c2, DataType::Type::kInt32, 0);
89 HInstruction* array_set1 =
90 new (GetAllocator()) HArraySet(array, c1, c3, DataType::Type::kInt32, 0);
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]91 HInstruction* array_set2 =
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]92 new (GetAllocator()) HArraySet(array, index, c3, DataType::Type::kInt32, 0);
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]93 entry->AddInstruction(array);
94 entry->AddInstruction(index);
95 entry->AddInstruction(array_get1);
96 entry->AddInstruction(array_get2);
97 entry->AddInstruction(array_set1);
98 entry->AddInstruction(array_set2);
99
100 // Test HeapLocationCollector initialization.
101 // Should be no heap locations, no operations on the heap.
Vladimir Markoef898422020-06-08 10:26:06 +0100[diff] [blame]102 ScopedArenaAllocator allocator(graph_->GetArenaStack());
Nicolas Geoffray47ac5312021-01-22 08:41:08 +0000[diff] [blame]103 HeapLocationCollector heap_location_collector(
104 graph_, &allocator, /*for_partial_elimination=*/true);
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]105 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 0U);
106 ASSERT_FALSE(heap_location_collector.HasHeapStores());
107
108 // Test that after visiting the graph_, it must see following heap locations
109 // array[c1], array[c2], array[index]; and it should see heap stores.
110 heap_location_collector.VisitBasicBlock(entry);
111 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 3U);
112 ASSERT_TRUE(heap_location_collector.HasHeapStores());
113
114 // Test queries on HeapLocationCollector's ref info and index records.
115 ReferenceInfo* ref = heap_location_collector.FindReferenceInfoOf(array);
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]116 DataType::Type type = DataType::Type::kInt32;
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]117 size_t field = HeapLocation::kInvalidFieldOffset;
118 size_t vec = HeapLocation::kScalar;
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]119 size_t class_def = HeapLocation::kDeclaringClassDefIndexForArrays;
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]120 size_t loc1 = heap_location_collector.FindHeapLocationIndex(
121 ref, type, field, c1, vec, class_def);
122 size_t loc2 = heap_location_collector.FindHeapLocationIndex(
123 ref, type, field, c2, vec, class_def);
124 size_t loc3 = heap_location_collector.FindHeapLocationIndex(
125 ref, type, field, index, vec, class_def);
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]126 // must find this reference info for array in HeapLocationCollector.
127 ASSERT_TRUE(ref != nullptr);
128 // must find these heap locations;
129 // and array[1], array[2], array[3] should be different heap locations.
130 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound);
131 ASSERT_TRUE(loc2 != HeapLocationCollector::kHeapLocationNotFound);
132 ASSERT_TRUE(loc3 != HeapLocationCollector::kHeapLocationNotFound);
133 ASSERT_TRUE(loc1 != loc2);
134 ASSERT_TRUE(loc2 != loc3);
135 ASSERT_TRUE(loc1 != loc3);
136
137 // Test alias relationships after building aliasing matrix.
138 // array[1] and array[2] clearly should not alias;
139 // array[index] should alias with the others, because index is an unknow value.
140 heap_location_collector.BuildAliasingMatrix();
141 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
142 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc3));
143 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc3));
Evgeny Astigeevich7ee34a12019-12-10 11:36:33 +0000[diff] [blame]144
145 EXPECT_TRUE(CheckGraph(graph_));
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]146}
147
148TEST_F(LoadStoreAnalysisTest, FieldHeapLocations) {
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]149 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]150 graph_->AddBlock(entry);
151 graph_->SetEntryBlock(entry);
152
153 // entry:
154 // object ParameterValue
155 // c1 IntConstant
156 // set_field10 InstanceFieldSet [object, c1, 10]
157 // get_field10 InstanceFieldGet [object, 10]
158 // get_field20 InstanceFieldGet [object, 20]
159
160 HInstruction* c1 = graph_->GetIntConstant(1);
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]161 HInstruction* object = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
162 dex::TypeIndex(0),
163 0,
164 DataType::Type::kReference);
165 HInstanceFieldSet* set_field10 = new (GetAllocator()) HInstanceFieldSet(object,
166 c1,
167 nullptr,
168 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]169 MemberOffset(32),
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]170 false,
171 kUnknownFieldIndex,
172 kUnknownClassDefIndex,
173 graph_->GetDexFile(),
174 0);
175 HInstanceFieldGet* get_field10 = new (GetAllocator()) HInstanceFieldGet(object,
176 nullptr,
177 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]178 MemberOffset(32),
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]179 false,
180 kUnknownFieldIndex,
181 kUnknownClassDefIndex,
182 graph_->GetDexFile(),
183 0);
184 HInstanceFieldGet* get_field20 = new (GetAllocator()) HInstanceFieldGet(object,
185 nullptr,
186 DataType::Type::kInt32,
187 MemberOffset(20),
188 false,
189 kUnknownFieldIndex,
190 kUnknownClassDefIndex,
191 graph_->GetDexFile(),
192 0);
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]193 entry->AddInstruction(object);
194 entry->AddInstruction(set_field10);
195 entry->AddInstruction(get_field10);
196 entry->AddInstruction(get_field20);
197
198 // Test HeapLocationCollector initialization.
199 // Should be no heap locations, no operations on the heap.
Vladimir Markoef898422020-06-08 10:26:06 +0100[diff] [blame]200 ScopedArenaAllocator allocator(graph_->GetArenaStack());
Nicolas Geoffray47ac5312021-01-22 08:41:08 +0000[diff] [blame]201 HeapLocationCollector heap_location_collector(
202 graph_, &allocator, /*for_partial_elimination=*/true);
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]203 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 0U);
204 ASSERT_FALSE(heap_location_collector.HasHeapStores());
205
206 // Test that after visiting the graph, it must see following heap locations
207 // object.field10, object.field20 and it should see heap stores.
208 heap_location_collector.VisitBasicBlock(entry);
209 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 2U);
210 ASSERT_TRUE(heap_location_collector.HasHeapStores());
211
212 // Test queries on HeapLocationCollector's ref info and index records.
213 ReferenceInfo* ref = heap_location_collector.FindReferenceInfoOf(object);
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]214 size_t loc1 = heap_location_collector.GetFieldHeapLocation(object, &get_field10->GetFieldInfo());
215 size_t loc2 = heap_location_collector.GetFieldHeapLocation(object, &get_field20->GetFieldInfo());
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]216 // must find references info for object and in HeapLocationCollector.
217 ASSERT_TRUE(ref != nullptr);
218 // must find these heap locations.
219 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound);
220 ASSERT_TRUE(loc2 != HeapLocationCollector::kHeapLocationNotFound);
221 // different fields of same object.
222 ASSERT_TRUE(loc1 != loc2);
223 // accesses to different fields of the same object should not alias.
224 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
Evgeny Astigeevich7ee34a12019-12-10 11:36:33 +0000[diff] [blame]225
226 EXPECT_TRUE(CheckGraph(graph_));
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]227}
228
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]229TEST_F(LoadStoreAnalysisTest, ArrayIndexAliasingTest) {
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]230 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]231 graph_->AddBlock(entry);
232 graph_->SetEntryBlock(entry);
233 graph_->BuildDominatorTree();
234
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]235 HInstruction* array = new (GetAllocator()) HParameterValue(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]236 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]237 HInstruction* index = new (GetAllocator()) HParameterValue(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]238 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]239 HInstruction* c0 = graph_->GetIntConstant(0);
240 HInstruction* c1 = graph_->GetIntConstant(1);
241 HInstruction* c_neg1 = graph_->GetIntConstant(-1);
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]242 HInstruction* add0 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c0);
243 HInstruction* add1 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c1);
244 HInstruction* sub0 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c0);
245 HInstruction* sub1 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c1);
246 HInstruction* sub_neg1 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c_neg1);
247 HInstruction* rev_sub1 = new (GetAllocator()) HSub(DataType::Type::kInt32, c1, index);
248 HInstruction* arr_set1 = new (GetAllocator()) HArraySet(array, c0, c0, DataType::Type::kInt32, 0);
249 HInstruction* arr_set2 = new (GetAllocator()) HArraySet(array, c1, c0, DataType::Type::kInt32, 0);
250 HInstruction* arr_set3 =
251 new (GetAllocator()) HArraySet(array, add0, c0, DataType::Type::kInt32, 0);
252 HInstruction* arr_set4 =
253 new (GetAllocator()) HArraySet(array, add1, c0, DataType::Type::kInt32, 0);
254 HInstruction* arr_set5 =
255 new (GetAllocator()) HArraySet(array, sub0, c0, DataType::Type::kInt32, 0);
256 HInstruction* arr_set6 =
257 new (GetAllocator()) HArraySet(array, sub1, c0, DataType::Type::kInt32, 0);
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]258 HInstruction* arr_set7 =
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]259 new (GetAllocator()) HArraySet(array, rev_sub1, c0, DataType::Type::kInt32, 0);
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]260 HInstruction* arr_set8 =
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]261 new (GetAllocator()) HArraySet(array, sub_neg1, c0, DataType::Type::kInt32, 0);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]262
263 entry->AddInstruction(array);
264 entry->AddInstruction(index);
265 entry->AddInstruction(add0);
266 entry->AddInstruction(add1);
267 entry->AddInstruction(sub0);
268 entry->AddInstruction(sub1);
269 entry->AddInstruction(sub_neg1);
270 entry->AddInstruction(rev_sub1);
271
272 entry->AddInstruction(arr_set1); // array[0] = c0
273 entry->AddInstruction(arr_set2); // array[1] = c0
274 entry->AddInstruction(arr_set3); // array[i+0] = c0
275 entry->AddInstruction(arr_set4); // array[i+1] = c0
276 entry->AddInstruction(arr_set5); // array[i-0] = c0
277 entry->AddInstruction(arr_set6); // array[i-1] = c0
278 entry->AddInstruction(arr_set7); // array[1-i] = c0
279 entry->AddInstruction(arr_set8); // array[i-(-1)] = c0
280
Vladimir Markoef898422020-06-08 10:26:06 +0100[diff] [blame]281 ScopedArenaAllocator allocator(graph_->GetArenaStack());
Nicolas Geoffray47ac5312021-01-22 08:41:08 +0000[diff] [blame]282 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/false);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]283 lsa.Run();
284 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
285
286 // LSA/HeapLocationCollector should see those ArrayGet instructions.
287 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 8U);
288 ASSERT_TRUE(heap_location_collector.HasHeapStores());
289
290 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
291 size_t loc1 = HeapLocationCollector::kHeapLocationNotFound;
292 size_t loc2 = HeapLocationCollector::kHeapLocationNotFound;
293
294 // Test alias: array[0] and array[1]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]295 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set1);
296 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set2);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]297 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
298
299 // Test alias: array[i+0] and array[i-0]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]300 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set3);
301 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set5);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]302 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
303
304 // Test alias: array[i+1] and array[i-1]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]305 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4);
306 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set6);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]307 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
308
309 // Test alias: array[i+1] and array[1-i]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]310 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4);
311 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set7);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]312 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
313
314 // Test alias: array[i+1] and array[i-(-1)]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]315 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4);
316 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set8);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]317 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
Evgeny Astigeevich7ee34a12019-12-10 11:36:33 +0000[diff] [blame]318
319 EXPECT_TRUE(CheckGraphSkipRefTypeInfoChecks(graph_));
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]320}
321
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]322TEST_F(LoadStoreAnalysisTest, ArrayAliasingTest) {
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
Vladimir Markoef898422020-06-08 10:26:06 +0100[diff] [blame]448 ScopedArenaAllocator allocator(graph_->GetArenaStack());
Nicolas Geoffray47ac5312021-01-22 08:41:08 +0000[diff] [blame]449 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/false);
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]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]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]461 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
462 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0);
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]463 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
464
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]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
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]470 // Test alias: array[0] and array[8,9,10,11]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]471 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
472 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8);
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]473 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
474
475 // Test alias: array[1] and array[8,9,10,11]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]476 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1);
477 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8);
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]478 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
479
480 // Test alias: array[1] and array[0,1,2,3]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]481 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1);
482 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0);
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]483 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
484
485 // Test alias: array[0,1,2,3] and array[8,9,10,11]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]486 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_0);
487 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8);
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]488 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
489
490 // Test alias: array[0,1,2,3] and array[1,2,3,4]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]491 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_0);
492 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_1);
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]493 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
494
495 // Test alias: array[0] and array[i,i+1,i+2,i+3]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]496 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
497 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i);
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]498 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
499
500 // Test alias: array[i] and array[0,1,2,3]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]501 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
502 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0);
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]503 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
504
505 // Test alias: array[i] and array[i,i+1,i+2,i+3]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]506 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
507 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i);
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]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]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]511 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
512 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8);
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]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.
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]517 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6);
518 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8);
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]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.
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]523 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6_vlen2);
524 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i);
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]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]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]528 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6_vlen2);
529 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8);
xueliang.zhongb50b16a2017-09-19 17:43:29 +0100[diff] [blame]530 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
531}
532
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]533TEST_F(LoadStoreAnalysisTest, ArrayIndexCalculationOverflowTest) {
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]534 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]535 graph_->AddBlock(entry);
536 graph_->SetEntryBlock(entry);
537 graph_->BuildDominatorTree();
538
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]539 HInstruction* array = new (GetAllocator()) HParameterValue(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]540 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]541 HInstruction* index = new (GetAllocator()) HParameterValue(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]542 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]543
544 HInstruction* c0 = graph_->GetIntConstant(0);
545 HInstruction* c_0x80000000 = graph_->GetIntConstant(0x80000000);
546 HInstruction* c_0x10 = graph_->GetIntConstant(0x10);
547 HInstruction* c_0xFFFFFFF0 = graph_->GetIntConstant(0xFFFFFFF0);
548 HInstruction* c_0x7FFFFFFF = graph_->GetIntConstant(0x7FFFFFFF);
549 HInstruction* c_0x80000001 = graph_->GetIntConstant(0x80000001);
550
551 // `index+0x80000000` and `index-0x80000000` array indices MAY alias.
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]552 HInstruction* add_0x80000000 = new (GetAllocator()) HAdd(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]553 DataType::Type::kInt32, index, c_0x80000000);
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]554 HInstruction* sub_0x80000000 = new (GetAllocator()) HSub(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]555 DataType::Type::kInt32, index, c_0x80000000);
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]556 HInstruction* arr_set_1 = new (GetAllocator()) HArraySet(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]557 array, add_0x80000000, c0, DataType::Type::kInt32, 0);
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]558 HInstruction* arr_set_2 = new (GetAllocator()) HArraySet(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]559 array, sub_0x80000000, c0, DataType::Type::kInt32, 0);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]560
561 // `index+0x10` and `index-0xFFFFFFF0` array indices MAY alias.
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]562 HInstruction* add_0x10 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c_0x10);
563 HInstruction* sub_0xFFFFFFF0 = new (GetAllocator()) HSub(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]564 DataType::Type::kInt32, index, c_0xFFFFFFF0);
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]565 HInstruction* arr_set_3 = new (GetAllocator()) HArraySet(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]566 array, add_0x10, c0, DataType::Type::kInt32, 0);
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]567 HInstruction* arr_set_4 = new (GetAllocator()) HArraySet(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]568 array, sub_0xFFFFFFF0, c0, DataType::Type::kInt32, 0);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]569
570 // `index+0x7FFFFFFF` and `index-0x80000001` array indices MAY alias.
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]571 HInstruction* add_0x7FFFFFFF = new (GetAllocator()) HAdd(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]572 DataType::Type::kInt32, index, c_0x7FFFFFFF);
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]573 HInstruction* sub_0x80000001 = new (GetAllocator()) HSub(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]574 DataType::Type::kInt32, index, c_0x80000001);
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]575 HInstruction* arr_set_5 = new (GetAllocator()) HArraySet(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]576 array, add_0x7FFFFFFF, c0, DataType::Type::kInt32, 0);
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]577 HInstruction* arr_set_6 = new (GetAllocator()) HArraySet(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]578 array, sub_0x80000001, c0, DataType::Type::kInt32, 0);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]579
580 // `index+0` and `index-0` array indices MAY alias.
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]581 HInstruction* add_0 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c0);
582 HInstruction* sub_0 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c0);
583 HInstruction* arr_set_7 = new (GetAllocator()) HArraySet(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]584 array, add_0, c0, DataType::Type::kInt32, 0);
Vladimir Markoca6fff82017-10-03 14:49:14 +0100[diff] [blame]585 HInstruction* arr_set_8 = new (GetAllocator()) HArraySet(
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100[diff] [blame]586 array, sub_0, c0, DataType::Type::kInt32, 0);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]587
588 entry->AddInstruction(array);
589 entry->AddInstruction(index);
590 entry->AddInstruction(add_0x80000000);
591 entry->AddInstruction(sub_0x80000000);
592 entry->AddInstruction(add_0x10);
593 entry->AddInstruction(sub_0xFFFFFFF0);
594 entry->AddInstruction(add_0x7FFFFFFF);
595 entry->AddInstruction(sub_0x80000001);
596 entry->AddInstruction(add_0);
597 entry->AddInstruction(sub_0);
598 entry->AddInstruction(arr_set_1);
599 entry->AddInstruction(arr_set_2);
600 entry->AddInstruction(arr_set_3);
601 entry->AddInstruction(arr_set_4);
602 entry->AddInstruction(arr_set_5);
603 entry->AddInstruction(arr_set_6);
604 entry->AddInstruction(arr_set_7);
605 entry->AddInstruction(arr_set_8);
606
Vladimir Markoef898422020-06-08 10:26:06 +0100[diff] [blame]607 ScopedArenaAllocator allocator(graph_->GetArenaStack());
Nicolas Geoffray47ac5312021-01-22 08:41:08 +0000[diff] [blame]608 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/false);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]609 lsa.Run();
610 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
611
612 // LSA/HeapLocationCollector should see those ArrayGet instructions.
613 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 8U);
614 ASSERT_TRUE(heap_location_collector.HasHeapStores());
615
616 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
617 size_t loc1 = HeapLocationCollector::kHeapLocationNotFound;
618 size_t loc2 = HeapLocationCollector::kHeapLocationNotFound;
619
620 // Test alias: array[i+0x80000000] and array[i-0x80000000]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]621 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1);
622 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_2);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]623 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
624
625 // Test alias: array[i+0x10] and array[i-0xFFFFFFF0]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]626 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_3);
627 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_4);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]628 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
629
630 // Test alias: array[i+0x7FFFFFFF] and array[i-0x80000001]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]631 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_5);
632 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_6);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]633 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
634
635 // Test alias: array[i+0] and array[i-0]
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]636 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_7);
637 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_8);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]638 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
639
640 // Should not alias:
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]641 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_2);
642 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_6);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]643 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
644
645 // Should not alias:
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]646 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_7);
647 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_2);
xueliang.zhong016c0f12017-05-12 18:16:31 +0100[diff] [blame]648 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
649}
650
xueliang.zhonge0eb4832017-10-30 13:43:14 +0000[diff] [blame]651TEST_F(LoadStoreAnalysisTest, TestHuntOriginalRef) {
652 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
653 graph_->AddBlock(entry);
654 graph_->SetEntryBlock(entry);
655
656 // Different ways where orignal array reference are transformed & passed to ArrayGet.
657 // ParameterValue --> ArrayGet
658 // ParameterValue --> BoundType --> ArrayGet
659 // ParameterValue --> BoundType --> NullCheck --> ArrayGet
660 // ParameterValue --> BoundType --> NullCheck --> IntermediateAddress --> ArrayGet
661 HInstruction* c1 = graph_->GetIntConstant(1);
662 HInstruction* array = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
663 dex::TypeIndex(0),
664 0,
665 DataType::Type::kReference);
666 HInstruction* array_get1 = new (GetAllocator()) HArrayGet(array,
667 c1,
668 DataType::Type::kInt32,
669 0);
670
671 HInstruction* bound_type = new (GetAllocator()) HBoundType(array);
672 HInstruction* array_get2 = new (GetAllocator()) HArrayGet(bound_type,
673 c1,
674 DataType::Type::kInt32,
675 0);
676
677 HInstruction* null_check = new (GetAllocator()) HNullCheck(bound_type, 0);
678 HInstruction* array_get3 = new (GetAllocator()) HArrayGet(null_check,
679 c1,
680 DataType::Type::kInt32,
681 0);
682
683 HInstruction* inter_addr = new (GetAllocator()) HIntermediateAddress(null_check, c1, 0);
684 HInstruction* array_get4 = new (GetAllocator()) HArrayGet(inter_addr,
685 c1,
686 DataType::Type::kInt32,
687 0);
688 entry->AddInstruction(array);
689 entry->AddInstruction(array_get1);
690 entry->AddInstruction(bound_type);
691 entry->AddInstruction(array_get2);
692 entry->AddInstruction(null_check);
693 entry->AddInstruction(array_get3);
694 entry->AddInstruction(inter_addr);
695 entry->AddInstruction(array_get4);
696
Vladimir Markoef898422020-06-08 10:26:06 +0100[diff] [blame]697 ScopedArenaAllocator allocator(graph_->GetArenaStack());
Nicolas Geoffray47ac5312021-01-22 08:41:08 +0000[diff] [blame]698 HeapLocationCollector heap_location_collector(
699 graph_, &allocator, /*for_partial_elimination=*/true);
xueliang.zhonge0eb4832017-10-30 13:43:14 +0000[diff] [blame]700 heap_location_collector.VisitBasicBlock(entry);
701
702 // Test that the HeapLocationCollector should be able to tell
703 // that there is only ONE array location, no matter how many
704 // times the original reference has been transformed by BoundType,
705 // NullCheck, IntermediateAddress, etc.
706 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 1U);
Aart Bikb765a3f2018-05-10 14:47:48 -0700[diff] [blame]707 size_t loc1 = heap_location_collector.GetArrayHeapLocation(array_get1);
708 size_t loc2 = heap_location_collector.GetArrayHeapLocation(array_get2);
709 size_t loc3 = heap_location_collector.GetArrayHeapLocation(array_get3);
710 size_t loc4 = heap_location_collector.GetArrayHeapLocation(array_get4);
xueliang.zhonge0eb4832017-10-30 13:43:14 +0000[diff] [blame]711 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound);
712 ASSERT_EQ(loc1, loc2);
713 ASSERT_EQ(loc1, loc3);
714 ASSERT_EQ(loc1, loc4);
715}
716
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]717void LoadStoreAnalysisTest::CheckReachability(const AdjacencyListGraph& adj,
718 const std::vector<AdjacencyListGraph::Edge>& reach) {
719 uint32_t cnt = 0;
720 for (HBasicBlock* blk : graph_->GetBlocks()) {
721 if (adj.HasBlock(blk)) {
722 for (HBasicBlock* other : graph_->GetBlocks()) {
723 if (other == nullptr) {
724 continue;
725 }
726 if (adj.HasBlock(other)) {
727 bool contains_edge =
728 std::find(reach.begin(),
729 reach.end(),
730 AdjacencyListGraph::Edge { adj.GetName(blk), adj.GetName(other) }) !=
731 reach.end();
732 if (graph_->PathBetween(blk, other)) {
733 cnt++;
734 EXPECT_TRUE(contains_edge) << "Unexpected edge found between " << adj.GetName(blk)
735 << " and " << adj.GetName(other);
736 } else {
737 EXPECT_FALSE(contains_edge) << "Expected edge not found between " << adj.GetName(blk)
738 << " and " << adj.GetName(other);
739 }
740 } else if (graph_->PathBetween(blk, other)) {
741 ADD_FAILURE() << "block " << adj.GetName(blk)
742 << " has path to non-adjacency-graph block id: " << other->GetBlockId();
743 }
744 }
745 } else {
746 for (HBasicBlock* other : graph_->GetBlocks()) {
747 if (other == nullptr) {
748 continue;
749 }
750 EXPECT_FALSE(graph_->PathBetween(blk, other))
751 << "Reachable blocks outside of adjacency-list";
752 }
753 }
754 }
755 EXPECT_EQ(cnt, reach.size());
756}
757
758TEST_F(LoadStoreAnalysisTest, ReachabilityTest1) {
759 AdjacencyListGraph blks(SetupFromAdjacencyList(
760 "entry",
761 "exit",
762 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
763 CheckReachability(blks,
764 {
765 { "entry", "left" },
766 { "entry", "right" },
767 { "entry", "exit" },
768 { "right", "exit" },
769 { "left", "exit" },
770 });
771}
772
773TEST_F(LoadStoreAnalysisTest, ReachabilityTest2) {
774 AdjacencyListGraph blks(SetupFromAdjacencyList(
775 "entry",
776 "exit",
777 { { "entry", "loop-header" }, { "loop-header", "loop" }, { "loop", "loop-header" } }));
778 CheckReachability(blks,
779 {
780 { "entry", "loop-header" },
781 { "entry", "loop" },
782 { "loop-header", "loop-header" },
783 { "loop-header", "loop" },
784 { "loop", "loop-header" },
785 { "loop", "loop" },
786 });
787}
788
789TEST_F(LoadStoreAnalysisTest, ReachabilityTest3) {
790 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
791 "exit",
792 { { "entry", "loop-header" },
793 { "loop-header", "loop" },
794 { "loop", "loop-header" },
795 { "entry", "right" },
796 { "right", "exit" } }));
797 CheckReachability(blks,
798 {
799 { "entry", "loop-header" },
800 { "entry", "loop" },
801 { "entry", "right" },
802 { "entry", "exit" },
803 { "loop-header", "loop-header" },
804 { "loop-header", "loop" },
805 { "loop", "loop-header" },
806 { "loop", "loop" },
807 { "right", "exit" },
808 });
809}
810
811static bool AreExclusionsIndependent(HGraph* graph, const ExecutionSubgraph* esg) {
812 auto excluded = esg->GetExcludedCohorts();
813 if (excluded.size() < 2) {
814 return true;
815 }
816 for (auto first = excluded.begin(); first != excluded.end(); ++first) {
817 for (auto second = excluded.begin(); second != excluded.end(); ++second) {
818 if (first == second) {
819 continue;
820 }
821 for (const HBasicBlock* entry : first->EntryBlocks()) {
822 for (const HBasicBlock* exit : second->ExitBlocks()) {
823 if (graph->PathBetween(exit, entry)) {
824 return false;
825 }
826 }
827 }
828 }
829 }
830 return true;
831}
832
833// // ENTRY
834// obj = new Obj();
835// if (parameter_value) {
836// // LEFT
837// call_func(obj);
838// } else {
839// // RIGHT
840// obj.field = 1;
841// }
842// // EXIT
843// obj.field;
844TEST_F(LoadStoreAnalysisTest, PartialEscape) {
845 AdjacencyListGraph blks(SetupFromAdjacencyList(
846 "entry",
847 "exit",
848 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
849 HBasicBlock* entry = blks.Get("entry");
850 HBasicBlock* left = blks.Get("left");
851 HBasicBlock* right = blks.Get("right");
852 HBasicBlock* exit = blks.Get("exit");
853
854 HInstruction* bool_value = new (GetAllocator())
855 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
856 HInstruction* c0 = graph_->GetIntConstant(0);
857 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
858 dex::TypeIndex(10),
859 graph_->GetDexFile(),
860 ScopedNullHandle<mirror::Class>(),
861 false,
862 0,
863 false);
864 HInstruction* new_inst =
865 new (GetAllocator()) HNewInstance(cls,
866 0,
867 dex::TypeIndex(10),
868 graph_->GetDexFile(),
869 false,
870 QuickEntrypointEnum::kQuickAllocObjectInitialized);
871 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
872 entry->AddInstruction(bool_value);
873 entry->AddInstruction(cls);
874 entry->AddInstruction(new_inst);
875 entry->AddInstruction(if_inst);
876
877 HInstruction* call_left = new (GetAllocator())
878 HInvokeStaticOrDirect(GetAllocator(),
879 1,
880 DataType::Type::kVoid,
881 0,
882 { nullptr, 0 },
883 nullptr,
884 {},
885 InvokeType::kStatic,
886 { nullptr, 0 },
887 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
888 HInstruction* goto_left = new (GetAllocator()) HGoto();
889 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
890 left->AddInstruction(call_left);
891 left->AddInstruction(goto_left);
892
893 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
894 c0,
895 nullptr,
896 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]897 MemberOffset(32),
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]898 false,
899 0,
900 0,
901 graph_->GetDexFile(),
902 0);
903 HInstruction* goto_right = new (GetAllocator()) HGoto();
904 right->AddInstruction(write_right);
905 right->AddInstruction(goto_right);
906
907 HInstruction* read_final = new (GetAllocator()) HInstanceFieldGet(new_inst,
908 nullptr,
909 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]910 MemberOffset(32),
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]911 false,
912 0,
913 0,
914 graph_->GetDexFile(),
915 0);
916 exit->AddInstruction(read_final);
917
918 ScopedArenaAllocator allocator(graph_->GetArenaStack());
Nicolas Geoffray47ac5312021-01-22 08:41:08 +0000[diff] [blame]919 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/true);
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]920 lsa.Run();
921
922 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
923 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
924 const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
925
926 ASSERT_TRUE(esg->IsValid());
927 ASSERT_TRUE(IsValidSubgraph(esg));
928 ASSERT_TRUE(AreExclusionsIndependent(graph_, esg));
929 std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
930 esg->ReachableBlocks().end());
931
932 ASSERT_EQ(contents.size(), 3u);
933 ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
934
935 ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
936 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
937 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
938}
939
940// // ENTRY
941// obj = new Obj();
942// if (parameter_value) {
943// // LEFT
944// call_func(obj);
945// } else {
946// // RIGHT
947// obj.field = 1;
948// }
949// // EXIT
950// obj.field2;
951TEST_F(LoadStoreAnalysisTest, PartialEscape2) {
952 AdjacencyListGraph blks(SetupFromAdjacencyList(
953 "entry",
954 "exit",
955 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
956 HBasicBlock* entry = blks.Get("entry");
957 HBasicBlock* left = blks.Get("left");
958 HBasicBlock* right = blks.Get("right");
959 HBasicBlock* exit = blks.Get("exit");
960
961 HInstruction* bool_value = new (GetAllocator())
962 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
963 HInstruction* c0 = graph_->GetIntConstant(0);
964 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
965 dex::TypeIndex(10),
966 graph_->GetDexFile(),
967 ScopedNullHandle<mirror::Class>(),
968 false,
969 0,
970 false);
971 HInstruction* new_inst =
972 new (GetAllocator()) HNewInstance(cls,
973 0,
974 dex::TypeIndex(10),
975 graph_->GetDexFile(),
976 false,
977 QuickEntrypointEnum::kQuickAllocObjectInitialized);
978 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
979 entry->AddInstruction(bool_value);
980 entry->AddInstruction(cls);
981 entry->AddInstruction(new_inst);
982 entry->AddInstruction(if_inst);
983
984 HInstruction* call_left = new (GetAllocator())
985 HInvokeStaticOrDirect(GetAllocator(),
986 1,
987 DataType::Type::kVoid,
988 0,
989 { nullptr, 0 },
990 nullptr,
991 {},
992 InvokeType::kStatic,
993 { nullptr, 0 },
994 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
995 HInstruction* goto_left = new (GetAllocator()) HGoto();
996 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
997 left->AddInstruction(call_left);
998 left->AddInstruction(goto_left);
999
1000 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
1001 c0,
1002 nullptr,
1003 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]1004 MemberOffset(32),
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1005 false,
1006 0,
1007 0,
1008 graph_->GetDexFile(),
1009 0);
1010 HInstruction* goto_right = new (GetAllocator()) HGoto();
1011 right->AddInstruction(write_right);
1012 right->AddInstruction(goto_right);
1013
1014 HInstruction* read_final = new (GetAllocator()) HInstanceFieldGet(new_inst,
1015 nullptr,
1016 DataType::Type::kInt32,
1017 MemberOffset(16),
1018 false,
1019 0,
1020 0,
1021 graph_->GetDexFile(),
1022 0);
1023 exit->AddInstruction(read_final);
1024
1025 ScopedArenaAllocator allocator(graph_->GetArenaStack());
Nicolas Geoffray47ac5312021-01-22 08:41:08 +0000[diff] [blame]1026 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/true);
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1027 lsa.Run();
1028
1029 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
1030 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
1031 const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
1032
1033 ASSERT_TRUE(esg->IsValid());
1034 ASSERT_TRUE(IsValidSubgraph(esg));
1035 ASSERT_TRUE(AreExclusionsIndependent(graph_, esg));
1036 std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
1037 esg->ReachableBlocks().end());
1038
1039 ASSERT_EQ(contents.size(), 3u);
1040 ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
1041
1042 ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
1043 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
1044 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
1045}
1046
1047// // ENTRY
1048// obj = new Obj();
1049// obj.field = 10;
1050// if (parameter_value) {
1051// // LEFT
1052// call_func(obj);
1053// } else {
1054// // RIGHT
1055// obj.field = 20;
1056// }
1057// // EXIT
1058// obj.field;
1059TEST_F(LoadStoreAnalysisTest, PartialEscape3) {
1060 AdjacencyListGraph blks(SetupFromAdjacencyList(
1061 "entry",
1062 "exit",
1063 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
1064 HBasicBlock* entry = blks.Get("entry");
1065 HBasicBlock* left = blks.Get("left");
1066 HBasicBlock* right = blks.Get("right");
1067 HBasicBlock* exit = blks.Get("exit");
1068
1069 HInstruction* bool_value = new (GetAllocator())
1070 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
1071 HInstruction* c10 = graph_->GetIntConstant(10);
1072 HInstruction* c20 = graph_->GetIntConstant(20);
1073 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
1074 dex::TypeIndex(10),
1075 graph_->GetDexFile(),
1076 ScopedNullHandle<mirror::Class>(),
1077 false,
1078 0,
1079 false);
1080 HInstruction* new_inst =
1081 new (GetAllocator()) HNewInstance(cls,
1082 0,
1083 dex::TypeIndex(10),
1084 graph_->GetDexFile(),
1085 false,
1086 QuickEntrypointEnum::kQuickAllocObjectInitialized);
1087
1088 HInstruction* write_entry = new (GetAllocator()) HInstanceFieldSet(new_inst,
1089 c10,
1090 nullptr,
1091 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]1092 MemberOffset(32),
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1093 false,
1094 0,
1095 0,
1096 graph_->GetDexFile(),
1097 0);
1098 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
1099 entry->AddInstruction(bool_value);
1100 entry->AddInstruction(cls);
1101 entry->AddInstruction(new_inst);
1102 entry->AddInstruction(write_entry);
1103 entry->AddInstruction(if_inst);
1104
1105 HInstruction* call_left = new (GetAllocator())
1106 HInvokeStaticOrDirect(GetAllocator(),
1107 1,
1108 DataType::Type::kVoid,
1109 0,
1110 { nullptr, 0 },
1111 nullptr,
1112 {},
1113 InvokeType::kStatic,
1114 { nullptr, 0 },
1115 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1116 HInstruction* goto_left = new (GetAllocator()) HGoto();
1117 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
1118 left->AddInstruction(call_left);
1119 left->AddInstruction(goto_left);
1120
1121 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
1122 c20,
1123 nullptr,
1124 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]1125 MemberOffset(32),
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1126 false,
1127 0,
1128 0,
1129 graph_->GetDexFile(),
1130 0);
1131 HInstruction* goto_right = new (GetAllocator()) HGoto();
1132 right->AddInstruction(write_right);
1133 right->AddInstruction(goto_right);
1134
1135 HInstruction* read_final = new (GetAllocator()) HInstanceFieldGet(new_inst,
1136 nullptr,
1137 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]1138 MemberOffset(32),
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1139 false,
1140 0,
1141 0,
1142 graph_->GetDexFile(),
1143 0);
1144 exit->AddInstruction(read_final);
1145
1146 ScopedArenaAllocator allocator(graph_->GetArenaStack());
Nicolas Geoffray47ac5312021-01-22 08:41:08 +0000[diff] [blame]1147 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/true);
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1148 lsa.Run();
1149
1150 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
1151 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
1152 const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
1153
1154 ASSERT_TRUE(esg->IsValid());
1155 ASSERT_TRUE(IsValidSubgraph(esg));
1156 ASSERT_TRUE(AreExclusionsIndependent(graph_, esg));
1157 std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
1158 esg->ReachableBlocks().end());
1159
1160 ASSERT_EQ(contents.size(), 3u);
1161 ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
1162
1163 ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
1164 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
1165 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
1166}
1167
1168// // ENTRY
1169// obj = new Obj();
1170// if (parameter_value) {
1171// // LEFT
1172// call_func(obj);
1173// } else {
1174// // RIGHT
1175// obj.f1 = 0;
1176// }
1177// // EXIT
1178// // call_func prevents the elimination of this store.
1179// obj.f2 = 0;
1180TEST_F(LoadStoreAnalysisTest, TotalEscapeAdjacent) {
1181 AdjacencyListGraph blks(SetupFromAdjacencyList(
1182 "entry",
1183 "exit",
1184 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
1185 HBasicBlock* entry = blks.Get("entry");
1186 HBasicBlock* left = blks.Get("left");
1187 HBasicBlock* right = blks.Get("right");
1188 HBasicBlock* exit = blks.Get("exit");
1189
1190 HInstruction* bool_value = new (GetAllocator())
1191 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
1192 HInstruction* c0 = graph_->GetIntConstant(0);
1193 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
1194 dex::TypeIndex(10),
1195 graph_->GetDexFile(),
1196 ScopedNullHandle<mirror::Class>(),
1197 false,
1198 0,
1199 false);
1200 HInstruction* new_inst =
1201 new (GetAllocator()) HNewInstance(cls,
1202 0,
1203 dex::TypeIndex(10),
1204 graph_->GetDexFile(),
1205 false,
1206 QuickEntrypointEnum::kQuickAllocObjectInitialized);
1207 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
1208 entry->AddInstruction(bool_value);
1209 entry->AddInstruction(cls);
1210 entry->AddInstruction(new_inst);
1211 entry->AddInstruction(if_inst);
1212
1213 HInstruction* call_left = new (GetAllocator())
1214 HInvokeStaticOrDirect(GetAllocator(),
1215 1,
1216 DataType::Type::kVoid,
1217 0,
1218 { nullptr, 0 },
1219 nullptr,
1220 {},
1221 InvokeType::kStatic,
1222 { nullptr, 0 },
1223 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1224 HInstruction* goto_left = new (GetAllocator()) HGoto();
1225 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
1226 left->AddInstruction(call_left);
1227 left->AddInstruction(goto_left);
1228
1229 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
1230 c0,
1231 nullptr,
1232 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]1233 MemberOffset(32),
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1234 false,
1235 0,
1236 0,
1237 graph_->GetDexFile(),
1238 0);
1239 HInstruction* goto_right = new (GetAllocator()) HGoto();
1240 right->AddInstruction(write_right);
1241 right->AddInstruction(goto_right);
1242
1243 HInstruction* write_final = new (GetAllocator()) HInstanceFieldSet(new_inst,
1244 c0,
1245 nullptr,
1246 DataType::Type::kInt32,
1247 MemberOffset(16),
1248 false,
1249 0,
1250 0,
1251 graph_->GetDexFile(),
1252 0);
1253 exit->AddInstruction(write_final);
1254
1255 ScopedArenaAllocator allocator(graph_->GetArenaStack());
Nicolas Geoffray47ac5312021-01-22 08:41:08 +0000[diff] [blame]1256 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/true);
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1257 lsa.Run();
1258
1259 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
1260 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
1261 const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
1262
Nicolas Geoffray47ac5312021-01-22 08:41:08 +0000[diff] [blame]1263 ASSERT_FALSE(esg->IsValid()) << esg->GetExcludedCohorts();
1264 ASSERT_FALSE(IsValidSubgraph(esg));
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1265 std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
1266 esg->ReachableBlocks().end());
1267
Nicolas Geoffray47ac5312021-01-22 08:41:08 +0000[diff] [blame]1268 ASSERT_EQ(contents.size(), 0u);
1269 ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
1270 ASSERT_TRUE(contents.find(blks.Get("right")) == contents.end());
1271 ASSERT_TRUE(contents.find(blks.Get("entry")) == contents.end());
1272 ASSERT_TRUE(contents.find(blks.Get("exit")) == contents.end());
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1273}
1274
1275// // ENTRY
1276// obj = new Obj();
1277// if (parameter_value) {
1278// // LEFT
1279// call_func(obj);
1280// } else {
1281// // RIGHT
1282// obj.f0 = 0;
1283// call_func2(obj);
1284// }
1285// // EXIT
1286// obj.f0;
1287TEST_F(LoadStoreAnalysisTest, TotalEscape) {
1288 AdjacencyListGraph blks(SetupFromAdjacencyList(
1289 "entry",
1290 "exit",
1291 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
1292 HBasicBlock* entry = blks.Get("entry");
1293 HBasicBlock* left = blks.Get("left");
1294 HBasicBlock* right = blks.Get("right");
1295 HBasicBlock* exit = blks.Get("exit");
1296
1297 HInstruction* bool_value = new (GetAllocator())
1298 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
1299 HInstruction* c0 = graph_->GetIntConstant(0);
1300 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
1301 dex::TypeIndex(10),
1302 graph_->GetDexFile(),
1303 ScopedNullHandle<mirror::Class>(),
1304 false,
1305 0,
1306 false);
1307 HInstruction* new_inst =
1308 new (GetAllocator()) HNewInstance(cls,
1309 0,
1310 dex::TypeIndex(10),
1311 graph_->GetDexFile(),
1312 false,
1313 QuickEntrypointEnum::kQuickAllocObjectInitialized);
1314 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
1315 entry->AddInstruction(bool_value);
1316 entry->AddInstruction(cls);
1317 entry->AddInstruction(new_inst);
1318 entry->AddInstruction(if_inst);
1319
1320 HInstruction* call_left = new (GetAllocator())
1321 HInvokeStaticOrDirect(GetAllocator(),
1322 1,
1323 DataType::Type::kVoid,
1324 0,
1325 { nullptr, 0 },
1326 nullptr,
1327 {},
1328 InvokeType::kStatic,
1329 { nullptr, 0 },
1330 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1331 HInstruction* goto_left = new (GetAllocator()) HGoto();
1332 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
1333 left->AddInstruction(call_left);
1334 left->AddInstruction(goto_left);
1335
1336 HInstruction* call_right = new (GetAllocator())
1337 HInvokeStaticOrDirect(GetAllocator(),
1338 1,
1339 DataType::Type::kVoid,
1340 0,
1341 { nullptr, 0 },
1342 nullptr,
1343 {},
1344 InvokeType::kStatic,
1345 { nullptr, 0 },
1346 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1347 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
1348 c0,
1349 nullptr,
1350 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]1351 MemberOffset(32),
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1352 false,
1353 0,
1354 0,
1355 graph_->GetDexFile(),
1356 0);
1357 HInstruction* goto_right = new (GetAllocator()) HGoto();
1358 call_right->AsInvoke()->SetRawInputAt(0, new_inst);
1359 right->AddInstruction(write_right);
1360 right->AddInstruction(call_right);
1361 right->AddInstruction(goto_right);
1362
1363 HInstruction* read_final = new (GetAllocator()) HInstanceFieldGet(new_inst,
1364 nullptr,
1365 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]1366 MemberOffset(32),
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1367 false,
1368 0,
1369 0,
1370 graph_->GetDexFile(),
1371 0);
1372 exit->AddInstruction(read_final);
1373
1374 ScopedArenaAllocator allocator(graph_->GetArenaStack());
Nicolas Geoffray47ac5312021-01-22 08:41:08 +0000[diff] [blame]1375 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/true);
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1376 lsa.Run();
1377
1378 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
1379 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
1380 const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
1381
1382 ASSERT_FALSE(esg->IsValid());
1383 ASSERT_FALSE(IsValidSubgraph(esg));
1384 std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
1385 esg->ReachableBlocks().end());
1386
1387 ASSERT_EQ(contents.size(), 0u);
1388 ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
1389 ASSERT_TRUE(contents.find(blks.Get("right")) == contents.end());
1390 ASSERT_TRUE(contents.find(blks.Get("entry")) == contents.end());
1391 ASSERT_TRUE(contents.find(blks.Get("exit")) == contents.end());
1392}
1393
1394// // ENTRY
1395// obj = new Obj();
1396// obj.foo = 0;
1397// // EXIT
1398// return obj;
1399TEST_F(LoadStoreAnalysisTest, TotalEscape2) {
1400 AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", { { "entry", "exit" } }));
1401 HBasicBlock* entry = blks.Get("entry");
1402 HBasicBlock* exit = blks.Get("exit");
1403
1404 HInstruction* c0 = graph_->GetIntConstant(0);
1405 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
1406 dex::TypeIndex(10),
1407 graph_->GetDexFile(),
1408 ScopedNullHandle<mirror::Class>(),
1409 false,
1410 0,
1411 false);
1412 HInstruction* new_inst =
1413 new (GetAllocator()) HNewInstance(cls,
1414 0,
1415 dex::TypeIndex(10),
1416 graph_->GetDexFile(),
1417 false,
1418 QuickEntrypointEnum::kQuickAllocObjectInitialized);
1419
1420 HInstruction* write_start = new (GetAllocator()) HInstanceFieldSet(new_inst,
1421 c0,
1422 nullptr,
1423 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]1424 MemberOffset(32),
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1425 false,
1426 0,
1427 0,
1428 graph_->GetDexFile(),
1429 0);
1430 HInstruction* goto_inst = new (GetAllocator()) HGoto();
1431 entry->AddInstruction(cls);
1432 entry->AddInstruction(new_inst);
1433 entry->AddInstruction(write_start);
1434 entry->AddInstruction(goto_inst);
1435
1436 HInstruction* return_final = new (GetAllocator()) HReturn(new_inst);
1437 exit->AddInstruction(return_final);
1438
1439 ScopedArenaAllocator allocator(graph_->GetArenaStack());
Nicolas Geoffray47ac5312021-01-22 08:41:08 +0000[diff] [blame]1440 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/true);
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1441 lsa.Run();
1442
1443 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
1444 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
1445 const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
1446
1447 ASSERT_FALSE(esg->IsValid());
1448 ASSERT_FALSE(IsValidSubgraph(esg));
1449 std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
1450 esg->ReachableBlocks().end());
1451
1452 ASSERT_EQ(contents.size(), 0u);
1453 ASSERT_TRUE(contents.find(blks.Get("entry")) == contents.end());
1454 ASSERT_TRUE(contents.find(blks.Get("exit")) == contents.end());
1455}
1456
1457// // ENTRY
1458// obj = new Obj();
1459// if (parameter_value) {
1460// // HIGH_LEFT
1461// call_func(obj);
1462// } else {
1463// // HIGH_RIGHT
1464// obj.f0 = 1;
1465// }
1466// // MID
1467// obj.f0 *= 2;
1468// if (parameter_value2) {
1469// // LOW_LEFT
1470// call_func(obj);
1471// } else {
1472// // LOW_RIGHT
1473// obj.f0 = 1;
1474// }
1475// // EXIT
1476// obj.f0
1477TEST_F(LoadStoreAnalysisTest, DoubleDiamondEscape) {
1478 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
1479 "exit",
1480 { { "entry", "high_left" },
1481 { "entry", "high_right" },
1482 { "low_left", "exit" },
1483 { "low_right", "exit" },
1484 { "high_right", "mid" },
1485 { "high_left", "mid" },
1486 { "mid", "low_left" },
1487 { "mid", "low_right" } }));
1488 HBasicBlock* entry = blks.Get("entry");
1489 HBasicBlock* high_left = blks.Get("high_left");
1490 HBasicBlock* high_right = blks.Get("high_right");
1491 HBasicBlock* mid = blks.Get("mid");
1492 HBasicBlock* low_left = blks.Get("low_left");
1493 HBasicBlock* low_right = blks.Get("low_right");
1494 HBasicBlock* exit = blks.Get("exit");
1495
1496 HInstruction* bool_value1 = new (GetAllocator())
1497 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
1498 HInstruction* bool_value2 = new (GetAllocator())
1499 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 2, DataType::Type::kBool);
1500 HInstruction* c0 = graph_->GetIntConstant(0);
1501 HInstruction* c2 = graph_->GetIntConstant(2);
1502 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
1503 dex::TypeIndex(10),
1504 graph_->GetDexFile(),
1505 ScopedNullHandle<mirror::Class>(),
1506 false,
1507 0,
1508 false);
1509 HInstruction* new_inst =
1510 new (GetAllocator()) HNewInstance(cls,
1511 0,
1512 dex::TypeIndex(10),
1513 graph_->GetDexFile(),
1514 false,
1515 QuickEntrypointEnum::kQuickAllocObjectInitialized);
1516 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value1);
1517 entry->AddInstruction(bool_value1);
1518 entry->AddInstruction(bool_value2);
1519 entry->AddInstruction(cls);
1520 entry->AddInstruction(new_inst);
1521 entry->AddInstruction(if_inst);
1522
1523 HInstruction* call_left = new (GetAllocator())
1524 HInvokeStaticOrDirect(GetAllocator(),
1525 1,
1526 DataType::Type::kVoid,
1527 0,
1528 { nullptr, 0 },
1529 nullptr,
1530 {},
1531 InvokeType::kStatic,
1532 { nullptr, 0 },
1533 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1534 HInstruction* goto_left = new (GetAllocator()) HGoto();
1535 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
1536 high_left->AddInstruction(call_left);
1537 high_left->AddInstruction(goto_left);
1538
1539 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
1540 c0,
1541 nullptr,
1542 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]1543 MemberOffset(32),
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1544 false,
1545 0,
1546 0,
1547 graph_->GetDexFile(),
1548 0);
1549 HInstruction* goto_right = new (GetAllocator()) HGoto();
1550 high_right->AddInstruction(write_right);
1551 high_right->AddInstruction(goto_right);
1552
1553 HInstruction* read_mid = new (GetAllocator()) HInstanceFieldGet(new_inst,
1554 nullptr,
1555 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]1556 MemberOffset(32),
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1557 false,
1558 0,
1559 0,
1560 graph_->GetDexFile(),
1561 0);
1562 HInstruction* mul_mid = new (GetAllocator()) HMul(DataType::Type::kInt32, read_mid, c2);
1563 HInstruction* write_mid = new (GetAllocator()) HInstanceFieldSet(new_inst,
1564 mul_mid,
1565 nullptr,
1566 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]1567 MemberOffset(32),
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1568 false,
1569 0,
1570 0,
1571 graph_->GetDexFile(),
1572 0);
1573 HInstruction* if_mid = new (GetAllocator()) HIf(bool_value2);
1574 mid->AddInstruction(read_mid);
1575 mid->AddInstruction(mul_mid);
1576 mid->AddInstruction(write_mid);
1577 mid->AddInstruction(if_mid);
1578
1579 HInstruction* call_low_left = new (GetAllocator())
1580 HInvokeStaticOrDirect(GetAllocator(),
1581 1,
1582 DataType::Type::kVoid,
1583 0,
1584 { nullptr, 0 },
1585 nullptr,
1586 {},
1587 InvokeType::kStatic,
1588 { nullptr, 0 },
1589 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1590 HInstruction* goto_low_left = new (GetAllocator()) HGoto();
1591 call_low_left->AsInvoke()->SetRawInputAt(0, new_inst);
1592 low_left->AddInstruction(call_low_left);
1593 low_left->AddInstruction(goto_low_left);
1594
1595 HInstruction* write_low_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
1596 c0,
1597 nullptr,
1598 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]1599 MemberOffset(32),
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1600 false,
1601 0,
1602 0,
1603 graph_->GetDexFile(),
1604 0);
1605 HInstruction* goto_low_right = new (GetAllocator()) HGoto();
1606 low_right->AddInstruction(write_low_right);
1607 low_right->AddInstruction(goto_low_right);
1608
1609 HInstruction* read_final = new (GetAllocator()) HInstanceFieldGet(new_inst,
1610 nullptr,
1611 DataType::Type::kInt32,
Alex Lightb171bc42021-01-22 06:43:28 -0800[diff] [blame^]1612 MemberOffset(32),
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1613 false,
1614 0,
1615 0,
1616 graph_->GetDexFile(),
1617 0);
1618 exit->AddInstruction(read_final);
1619
1620 ScopedArenaAllocator allocator(graph_->GetArenaStack());
Nicolas Geoffray47ac5312021-01-22 08:41:08 +0000[diff] [blame]1621 LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/true);
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1622 lsa.Run();
1623
1624 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
1625 ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
1626 const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
1627
1628 ASSERT_FALSE(esg->IsValid());
1629 ASSERT_FALSE(IsValidSubgraph(esg));
1630 std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
1631 esg->ReachableBlocks().end());
1632
1633 ASSERT_EQ(contents.size(), 0u);
1634}
1635
xueliang.zhongc239a2b2017-04-27 15:31:37 +0100[diff] [blame]1636} // namespace art