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