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