1 /*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "reference_type_propagation.h"
18
19 #include <random>
20
21 #include "base/arena_allocator.h"
22 #include "base/macros.h"
23 #include "base/transform_array_ref.h"
24 #include "base/transform_iterator.h"
25 #include "builder.h"
26 #include "nodes.h"
27 #include "object_lock.h"
28 #include "optimizing_unit_test.h"
29
30 namespace art HIDDEN {
31
32 // TODO It would be good to use the following but there is a miniscule amount of
33 // chance for flakiness so we'll just use a set seed instead.
34 constexpr bool kUseTrueRandomness = false;
35
36 /**
37 * Fixture class for unit testing the ReferenceTypePropagation phase. Used to verify the
38 * functionality of methods and situations that are hard to set up with checker tests.
39 */
40 template<typename SuperTest>
41 class ReferenceTypePropagationTestBase : public SuperTest, public OptimizingUnitTestHelper {
42 public:
ReferenceTypePropagationTestBase()43 ReferenceTypePropagationTestBase() : graph_(nullptr), propagation_(nullptr) {
44 this->use_boot_image_ = true; // Make the Runtime creation cheaper.
45 }
46
~ReferenceTypePropagationTestBase()47 ~ReferenceTypePropagationTestBase() { }
48
SetupPropagation(VariableSizedHandleScope * handles)49 void SetupPropagation(VariableSizedHandleScope* handles) {
50 graph_ = CreateGraph(handles);
51 propagation_ = new (GetAllocator())
52 ReferenceTypePropagation(graph_, Handle<mirror::DexCache>(), true, "test_prop");
53 }
54
55 // Relay method to merge type in reference type propagation.
MergeTypes(const ReferenceTypeInfo & a,const ReferenceTypeInfo & b)56 ReferenceTypeInfo MergeTypes(const ReferenceTypeInfo& a,
57 const ReferenceTypeInfo& b) REQUIRES_SHARED(Locks::mutator_lock_) {
58 return propagation_->MergeTypes(a, b, graph_->GetHandleCache());
59 }
60
61 // Helper method to construct an invalid type.
InvalidType()62 ReferenceTypeInfo InvalidType() {
63 return ReferenceTypeInfo::CreateInvalid();
64 }
65
66 // Helper method to construct the Object type.
ObjectType(bool is_exact=true)67 ReferenceTypeInfo ObjectType(bool is_exact = true) REQUIRES_SHARED(Locks::mutator_lock_) {
68 return ReferenceTypeInfo::Create(graph_->GetHandleCache()->GetObjectClassHandle(), is_exact);
69 }
70
71 // Helper method to construct the String type.
StringType(bool is_exact=true)72 ReferenceTypeInfo StringType(bool is_exact = true) REQUIRES_SHARED(Locks::mutator_lock_) {
73 return ReferenceTypeInfo::Create(graph_->GetHandleCache()->GetStringClassHandle(), is_exact);
74 }
75
76 // General building fields.
77 HGraph* graph_;
78
79 ReferenceTypePropagation* propagation_;
80 };
81
82 class ReferenceTypePropagationTest : public ReferenceTypePropagationTestBase<CommonCompilerTest> {};
83
84 enum class ShuffleOrder {
85 kTopological,
86 kReverseTopological,
87 kAlmostTopological,
88 kTrueRandom,
89 kRandomSetSeed,
90
91 kRandom = kUseTrueRandomness ? kTrueRandom : kRandomSetSeed,
92 };
93
operator <<(std::ostream & os,ShuffleOrder so)94 std::ostream& operator<<(std::ostream& os, ShuffleOrder so) {
95 switch (so) {
96 case ShuffleOrder::kAlmostTopological:
97 return os << "AlmostTopological";
98 case ShuffleOrder::kReverseTopological:
99 return os << "ReverseTopological";
100 case ShuffleOrder::kTopological:
101 return os << "Topological";
102 case ShuffleOrder::kTrueRandom:
103 return os << "TrueRandom";
104 case ShuffleOrder::kRandomSetSeed:
105 return os << "RandomSetSeed";
106 }
107 }
108
109 template <typename Param>
110 class ParamReferenceTypePropagationTest
111 : public ReferenceTypePropagationTestBase<CommonCompilerTestWithParam<Param>> {
112 public:
113 void MutateList(std::vector<HInstruction*>& lst, ShuffleOrder type);
114 };
115
116 class NonLoopReferenceTypePropagationTestGroup
117 : public ParamReferenceTypePropagationTest<ShuffleOrder> {
118 public:
119 template <typename Func>
120 void RunVisitListTest(Func mutator);
121 };
122
123 enum class InitialNullState {
124 kAllNull,
125 kAllNonNull,
126 kHalfNull,
127 kTrueRandom,
128 kRandomSetSeed,
129
130 kRandom = kUseTrueRandomness ? kTrueRandom : kRandomSetSeed,
131 };
132
operator <<(std::ostream & os,InitialNullState ni)133 std::ostream& operator<<(std::ostream& os, InitialNullState ni) {
134 switch (ni) {
135 case InitialNullState::kAllNull:
136 return os << "AllNull";
137 case InitialNullState::kAllNonNull:
138 return os << "AllNonNull";
139 case InitialNullState::kHalfNull:
140 return os << "HalfNull";
141 case InitialNullState::kTrueRandom:
142 return os << "TrueRandom";
143 case InitialNullState::kRandomSetSeed:
144 return os << "RandomSetSeed";
145 }
146 }
147
148 struct LoopOptions {
149 public:
150 using GtestParam = std::tuple<ShuffleOrder, ssize_t, size_t, InitialNullState>;
LoopOptionsart::LoopOptions151 explicit LoopOptions(GtestParam in) {
152 std::tie(shuffle_, null_insertion_, null_phi_arg_, initial_null_state_) = in;
153 }
154
155 ShuffleOrder shuffle_;
156 // Where in the list of phis we put the null. -1 if don't insert
157 ssize_t null_insertion_;
158 // Where in the phi arg-list we put the null.
159 size_t null_phi_arg_;
160 // What to set the initial null-state of all the phis to.
161 InitialNullState initial_null_state_;
162 };
163
164 class LoopReferenceTypePropagationTestGroup
165 : public ParamReferenceTypePropagationTest<LoopOptions::GtestParam> {
166 public:
167 template <typename Func>
168 void RunVisitListTest(Func mutator);
169 };
170
171 //
172 // The actual ReferenceTypePropgation unit tests.
173 //
174
TEST_F(ReferenceTypePropagationTest,ProperSetup)175 TEST_F(ReferenceTypePropagationTest, ProperSetup) {
176 ScopedObjectAccess soa(Thread::Current());
177 VariableSizedHandleScope handles(soa.Self());
178 SetupPropagation(&handles);
179
180 EXPECT_TRUE(propagation_ != nullptr);
181 EXPECT_TRUE(graph_->GetInexactObjectRti().IsEqual(ObjectType(false)));
182 }
183
TEST_F(ReferenceTypePropagationTest,MergeInvalidTypes)184 TEST_F(ReferenceTypePropagationTest, MergeInvalidTypes) {
185 ScopedObjectAccess soa(Thread::Current());
186 VariableSizedHandleScope handles(soa.Self());
187 SetupPropagation(&handles);
188
189 // Two invalid types.
190 ReferenceTypeInfo t1(MergeTypes(InvalidType(), InvalidType()));
191 EXPECT_FALSE(t1.IsValid());
192 EXPECT_FALSE(t1.IsExact());
193 EXPECT_TRUE(t1.IsEqual(InvalidType()));
194
195 // Valid type on right.
196 ReferenceTypeInfo t2(MergeTypes(InvalidType(), ObjectType()));
197 EXPECT_TRUE(t2.IsValid());
198 EXPECT_TRUE(t2.IsExact());
199 EXPECT_TRUE(t2.IsEqual(ObjectType()));
200 ReferenceTypeInfo t3(MergeTypes(InvalidType(), StringType()));
201 EXPECT_TRUE(t3.IsValid());
202 EXPECT_TRUE(t3.IsExact());
203 EXPECT_TRUE(t3.IsEqual(StringType()));
204
205 // Valid type on left.
206 ReferenceTypeInfo t4(MergeTypes(ObjectType(), InvalidType()));
207 EXPECT_TRUE(t4.IsValid());
208 EXPECT_TRUE(t4.IsExact());
209 EXPECT_TRUE(t4.IsEqual(ObjectType()));
210 ReferenceTypeInfo t5(MergeTypes(StringType(), InvalidType()));
211 EXPECT_TRUE(t5.IsValid());
212 EXPECT_TRUE(t5.IsExact());
213 EXPECT_TRUE(t5.IsEqual(StringType()));
214 }
215
TEST_F(ReferenceTypePropagationTest,MergeValidTypes)216 TEST_F(ReferenceTypePropagationTest, MergeValidTypes) {
217 ScopedObjectAccess soa(Thread::Current());
218 VariableSizedHandleScope handles(soa.Self());
219 SetupPropagation(&handles);
220
221 // Same types.
222 ReferenceTypeInfo t1(MergeTypes(ObjectType(), ObjectType()));
223 EXPECT_TRUE(t1.IsValid());
224 EXPECT_TRUE(t1.IsExact());
225 EXPECT_TRUE(t1.IsEqual(ObjectType()));
226 ReferenceTypeInfo t2(MergeTypes(StringType(), StringType()));
227 EXPECT_TRUE(t2.IsValid());
228 EXPECT_TRUE(t2.IsExact());
229 EXPECT_TRUE(t2.IsEqual(StringType()));
230
231 // Left is super class of right.
232 ReferenceTypeInfo t3(MergeTypes(ObjectType(), StringType()));
233 EXPECT_TRUE(t3.IsValid());
234 EXPECT_FALSE(t3.IsExact());
235 EXPECT_TRUE(t3.IsEqual(ObjectType(false)));
236
237 // Right is super class of left.
238 ReferenceTypeInfo t4(MergeTypes(StringType(), ObjectType()));
239 EXPECT_TRUE(t4.IsValid());
240 EXPECT_FALSE(t4.IsExact());
241 EXPECT_TRUE(t4.IsEqual(ObjectType(false)));
242
243 // Same types, but one or both are inexact.
244 ReferenceTypeInfo t5(MergeTypes(ObjectType(false), ObjectType()));
245 EXPECT_TRUE(t5.IsValid());
246 EXPECT_FALSE(t5.IsExact());
247 EXPECT_TRUE(t5.IsEqual(ObjectType(false)));
248 ReferenceTypeInfo t6(MergeTypes(ObjectType(), ObjectType(false)));
249 EXPECT_TRUE(t6.IsValid());
250 EXPECT_FALSE(t6.IsExact());
251 EXPECT_TRUE(t6.IsEqual(ObjectType(false)));
252 ReferenceTypeInfo t7(MergeTypes(ObjectType(false), ObjectType(false)));
253 EXPECT_TRUE(t7.IsValid());
254 EXPECT_FALSE(t7.IsExact());
255 EXPECT_TRUE(t7.IsEqual(ObjectType(false)));
256 }
257
258 // This generates a large graph with a ton of phis including loop-phis. It then
259 // calls the 'mutator' function with the list of all the phis and a CanBeNull
260 // instruction and then tries to propagate the types. mutator should reorder the
261 // list in some way and modify some phis in whatever way it wants. We verify
262 // everything worked by making sure every phi has valid type information.
263 template <typename Func>
RunVisitListTest(Func mutator)264 void LoopReferenceTypePropagationTestGroup::RunVisitListTest(Func mutator) {
265 ScopedObjectAccess soa(Thread::Current());
266 VariableSizedHandleScope handles(soa.Self());
267 SetupPropagation(&handles);
268 // Make a well-connected graph with a lot of edges.
269 constexpr size_t kNumBlocks = 100;
270 constexpr size_t kTestMaxSuccessors = 3;
271 std::vector<std::string> mid_blocks;
272 for (auto i : Range(kNumBlocks)) {
273 std::ostringstream oss;
274 oss << "blk" << i;
275 mid_blocks.push_back(oss.str());
276 }
277 // Create the edge list.
278 std::vector<AdjacencyListGraph::Edge> edges;
279 for (auto cur : Range(kNumBlocks)) {
280 for (auto nxt : Range(cur + 1, std::min(cur + 1 + kTestMaxSuccessors, kNumBlocks))) {
281 edges.emplace_back(mid_blocks[cur], mid_blocks[nxt]);
282 }
283 }
284 // Add a loop.
285 edges.emplace_back("start", mid_blocks.front());
286 edges.emplace_back(mid_blocks.back(), mid_blocks.front());
287 edges.emplace_back(mid_blocks.front(), "exit");
288
289 AdjacencyListGraph alg(graph_, GetAllocator(), "start", "exit", edges);
290 std::unordered_map<HBasicBlock*, HInstruction*> single_value;
291 HInstruction* maybe_null_val = new (GetAllocator())
292 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kReference);
293 ASSERT_TRUE(maybe_null_val->CanBeNull());
294 // Setup the entry-block with the type to be propagated.
295 HInstruction* cls =
296 new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
297 dex::TypeIndex(10),
298 graph_->GetDexFile(),
299 graph_->GetHandleCache()->GetObjectClassHandle(),
300 false,
301 0,
302 false);
303 HInstruction* new_inst =
304 new (GetAllocator()) HNewInstance(cls,
305 0,
306 dex::TypeIndex(10),
307 graph_->GetDexFile(),
308 false,
309 QuickEntrypointEnum::kQuickAllocObjectInitialized);
310 single_value[alg.Get(mid_blocks.front())] = new_inst;
311 HBasicBlock* start = alg.Get("start");
312 start->AddInstruction(maybe_null_val);
313 start->AddInstruction(cls);
314 start->AddInstruction(new_inst);
315 new_inst->SetReferenceTypeInfo(ObjectType(true));
316 maybe_null_val->SetReferenceTypeInfo(ObjectType(true));
317 single_value[start] = new_inst;
318
319 // Setup all the other blocks with a single PHI
320 auto range = MakeIterationRange(mid_blocks);
321 auto succ_blocks = MakeTransformRange(range, [&](const auto& sv) { return alg.Get(sv); });
322 for (HBasicBlock* blk : succ_blocks) {
323 HPhi* phi_inst = new (GetAllocator()) HPhi(
324 GetAllocator(), kNoRegNumber, blk->GetPredecessors().size(), DataType::Type::kReference);
325 single_value[blk] = phi_inst;
326 }
327 for (HBasicBlock* blk : succ_blocks) {
328 HInstruction* my_val = single_value[blk];
329 for (const auto& [pred, index] : ZipCount(MakeIterationRange(blk->GetPredecessors()))) {
330 CHECK(single_value[pred] != nullptr) << pred->GetBlockId() << " " << alg.GetName(pred);
331 my_val->SetRawInputAt(index, single_value[pred]);
332 }
333 }
334 for (HBasicBlock* blk : succ_blocks) {
335 CHECK(single_value[blk]->IsPhi()) << blk->GetBlockId();
336 blk->AddPhi(single_value[blk]->AsPhi());
337 }
338 auto vals = MakeTransformRange(succ_blocks, [&](HBasicBlock* blk) {
339 DCHECK(single_value[blk]->IsPhi());
340 return single_value[blk];
341 });
342 std::vector<HInstruction*> ins(vals.begin(), vals.end());
343 CHECK(std::none_of(ins.begin(), ins.end(), [](auto x) { return x == nullptr; }));
344 mutator(ins, maybe_null_val);
345 propagation_->Visit(ArrayRef<HInstruction* const>(ins));
346 bool is_nullable = !maybe_null_val->GetUses().empty();
347 for (auto [blk, i] : single_value) {
348 if (blk == start) {
349 continue;
350 }
351 EXPECT_TRUE(i->GetReferenceTypeInfo().IsValid())
352 << i->GetId() << " blk: " << alg.GetName(i->GetBlock());
353 if (is_nullable) {
354 EXPECT_TRUE(i->CanBeNull());
355 } else {
356 EXPECT_FALSE(i->CanBeNull());
357 }
358 }
359 }
360
361 // This generates a large graph with a ton of phis. It then calls the 'mutator'
362 // function with the list of all the phis and then tries to propagate the types.
363 // mutator should reorder the list in some way. We verify everything worked by
364 // making sure every phi has valid type information.
365 template <typename Func>
RunVisitListTest(Func mutator)366 void NonLoopReferenceTypePropagationTestGroup::RunVisitListTest(Func mutator) {
367 ScopedObjectAccess soa(Thread::Current());
368 VariableSizedHandleScope handles(soa.Self());
369 SetupPropagation(&handles);
370 // Make a well-connected graph with a lot of edges.
371 constexpr size_t kNumBlocks = 5000;
372 constexpr size_t kTestMaxSuccessors = 2;
373 std::vector<std::string> mid_blocks;
374 for (auto i : Range(kNumBlocks)) {
375 std::ostringstream oss;
376 oss << "blk" << i;
377 mid_blocks.push_back(oss.str());
378 }
379 // Create the edge list.
380 std::vector<AdjacencyListGraph::Edge> edges;
381 for (auto cur : Range(kNumBlocks)) {
382 for (auto nxt : Range(cur + 1, std::min(cur + 1 + kTestMaxSuccessors, kNumBlocks))) {
383 edges.emplace_back(mid_blocks[cur], mid_blocks[nxt]);
384 }
385 }
386 AdjacencyListGraph alg(graph_, GetAllocator(), mid_blocks.front(), mid_blocks.back(), edges);
387 std::unordered_map<HBasicBlock*, HInstruction*> single_value;
388 // Setup the entry-block with the type to be propagated.
389 HInstruction* cls =
390 new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
391 dex::TypeIndex(10),
392 graph_->GetDexFile(),
393 graph_->GetHandleCache()->GetObjectClassHandle(),
394 false,
395 0,
396 false);
397 HInstruction* new_inst =
398 new (GetAllocator()) HNewInstance(cls,
399 0,
400 dex::TypeIndex(10),
401 graph_->GetDexFile(),
402 false,
403 QuickEntrypointEnum::kQuickAllocObjectInitialized);
404 single_value[alg.Get(mid_blocks.front())] = new_inst;
405 HBasicBlock* start = alg.Get(mid_blocks.front());
406 start->AddInstruction(cls);
407 start->AddInstruction(new_inst);
408 new_inst->SetReferenceTypeInfo(ObjectType(true));
409
410 // Setup all the other blocks with a single PHI
411 auto succ_blk_names = MakeIterationRange(mid_blocks.begin() + 1, mid_blocks.end());
412 auto succ_blocks =
413 MakeTransformRange(succ_blk_names, [&](const auto& sv) { return alg.Get(sv); });
414 for (HBasicBlock* blk : succ_blocks) {
415 HPhi* phi_inst = new (GetAllocator()) HPhi(
416 GetAllocator(), kNoRegNumber, blk->GetPredecessors().size(), DataType::Type::kReference);
417 single_value[blk] = phi_inst;
418 }
419 for (HBasicBlock* blk : succ_blocks) {
420 HInstruction* my_val = single_value[blk];
421 for (const auto& [pred, index] : ZipCount(MakeIterationRange(blk->GetPredecessors()))) {
422 my_val->SetRawInputAt(index, single_value[pred]);
423 }
424 blk->AddPhi(my_val->AsPhi());
425 }
426 auto vals = MakeTransformRange(succ_blocks, [&](HBasicBlock* blk) { return single_value[blk]; });
427 std::vector<HInstruction*> ins(vals.begin(), vals.end());
428 mutator(ins);
429 propagation_->Visit(ArrayRef<HInstruction* const>(ins));
430 for (auto [blk, i] : single_value) {
431 if (blk == start) {
432 continue;
433 }
434 EXPECT_TRUE(i->GetReferenceTypeInfo().IsValid())
435 << i->GetId() << " blk: " << alg.GetName(i->GetBlock());
436 }
437 }
438
439 template <typename Param>
MutateList(std::vector<HInstruction * > & lst,ShuffleOrder type)440 void ParamReferenceTypePropagationTest<Param>::MutateList(std::vector<HInstruction*>& lst,
441 ShuffleOrder type) {
442 DCHECK(std::none_of(lst.begin(), lst.end(), [](auto* i) { return i == nullptr; }));
443 std::default_random_engine g(type != ShuffleOrder::kTrueRandom ? 42 : std::rand());
444 switch (type) {
445 case ShuffleOrder::kTopological: {
446 // Input is topologically sorted due to the way we create the phis.
447 break;
448 }
449 case ShuffleOrder::kReverseTopological: {
450 std::reverse(lst.begin(), lst.end());
451 break;
452 }
453 case ShuffleOrder::kAlmostTopological: {
454 std::swap(lst.front(), lst.back());
455 break;
456 }
457 case ShuffleOrder::kRandomSetSeed:
458 case ShuffleOrder::kTrueRandom: {
459 std::shuffle(lst.begin(), lst.end(), g);
460 break;
461 }
462 }
463 }
464
TEST_P(LoopReferenceTypePropagationTestGroup,RunVisitTest)465 TEST_P(LoopReferenceTypePropagationTestGroup, RunVisitTest) {
466 LoopOptions lo(GetParam());
467 std::default_random_engine g(
468 lo.initial_null_state_ != InitialNullState::kTrueRandom ? 42 : std::rand());
469 std::uniform_int_distribution<int> uid(0, 1);
470 RunVisitListTest([&](std::vector<HInstruction*>& lst, HInstruction* null_input) {
471 auto pred_null = false;
472 auto next_null = [&]() {
473 switch (lo.initial_null_state_) {
474 case InitialNullState::kAllNonNull:
475 return false;
476 case InitialNullState::kAllNull:
477 return true;
478 case InitialNullState::kHalfNull:
479 pred_null = !pred_null;
480 return pred_null;
481 case InitialNullState::kRandomSetSeed:
482 case InitialNullState::kTrueRandom:
483 return uid(g) > 0;
484 }
485 };
486 HPhi* nulled_phi = lo.null_insertion_ >= 0 ? lst[lo.null_insertion_]->AsPhi() : nullptr;
487 if (nulled_phi != nullptr) {
488 nulled_phi->ReplaceInput(null_input, lo.null_phi_arg_);
489 }
490 MutateList(lst, lo.shuffle_);
491 std::for_each(lst.begin(), lst.end(), [&](HInstruction* ins) {
492 ins->AsPhi()->SetCanBeNull(next_null());
493 });
494 });
495 }
496
497 INSTANTIATE_TEST_SUITE_P(ReferenceTypePropagationTest,
498 LoopReferenceTypePropagationTestGroup,
499 testing::Combine(testing::Values(ShuffleOrder::kAlmostTopological,
500 ShuffleOrder::kReverseTopological,
501 ShuffleOrder::kTopological,
502 ShuffleOrder::kRandom),
503 testing::Values(-1, 10, 40),
504 testing::Values(0, 1),
505 testing::Values(InitialNullState::kAllNonNull,
506 InitialNullState::kAllNull,
507 InitialNullState::kHalfNull,
508 InitialNullState::kRandom)));
509
TEST_P(NonLoopReferenceTypePropagationTestGroup,RunVisitTest)510 TEST_P(NonLoopReferenceTypePropagationTestGroup, RunVisitTest) {
511 RunVisitListTest([&](std::vector<HInstruction*>& lst) { MutateList(lst, GetParam()); });
512 }
513
514 INSTANTIATE_TEST_SUITE_P(ReferenceTypePropagationTest,
515 NonLoopReferenceTypePropagationTestGroup,
516 testing::Values(ShuffleOrder::kAlmostTopological,
517 ShuffleOrder::kReverseTopological,
518 ShuffleOrder::kTopological,
519 ShuffleOrder::kRandom));
520
521 } // namespace art
522