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