1 /*
2 * Copyright (C) 2021 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 "instruction_simplifier.h"
18
19 #include <initializer_list>
20 #include <tuple>
21
22 #include "gtest/gtest.h"
23
24 #include "class_root-inl.h"
25 #include "nodes.h"
26 #include "optimizing/data_type.h"
27 #include "optimizing_unit_test.h"
28
29 namespace art {
30
31 namespace mirror {
32 class ClassExt;
33 class Throwable;
34 } // namespace mirror
35
36 template<typename SuperClass>
37 class InstructionSimplifierTestBase : public SuperClass, public OptimizingUnitTestHelper {
38 public:
SetUp()39 void SetUp() override {
40 SuperClass::SetUp();
41 gLogVerbosity.compiler = true;
42 }
43
TearDown()44 void TearDown() override {
45 SuperClass::TearDown();
46 gLogVerbosity.compiler = false;
47 }
48 };
49
50 class InstructionSimplifierTest : public InstructionSimplifierTestBase<CommonCompilerTest> {};
51
52 // Various configs we can use for testing. Currently used in PartialComparison tests.
53 enum class InstanceOfKind {
54 kSelf,
55 kUnrelatedLoaded,
56 kUnrelatedUnloaded,
57 kSupertype,
58 };
59
operator <<(std::ostream & os,const InstanceOfKind & comp)60 std::ostream& operator<<(std::ostream& os, const InstanceOfKind& comp) {
61 switch (comp) {
62 case InstanceOfKind::kSupertype:
63 return os << "kSupertype";
64 case InstanceOfKind::kSelf:
65 return os << "kSelf";
66 case InstanceOfKind::kUnrelatedLoaded:
67 return os << "kUnrelatedLoaded";
68 case InstanceOfKind::kUnrelatedUnloaded:
69 return os << "kUnrelatedUnloaded";
70 }
71 }
72
73 class InstanceOfInstructionSimplifierTestGroup
74 : public InstructionSimplifierTestBase<CommonCompilerTestWithParam<InstanceOfKind>> {
75 public:
GetConstantResult() const76 bool GetConstantResult() const {
77 switch (GetParam()) {
78 case InstanceOfKind::kSupertype:
79 case InstanceOfKind::kSelf:
80 return true;
81 case InstanceOfKind::kUnrelatedLoaded:
82 case InstanceOfKind::kUnrelatedUnloaded:
83 return false;
84 }
85 }
86
GetLoadClasses(VariableSizedHandleScope * vshs)87 std::pair<HLoadClass*, HLoadClass*> GetLoadClasses(VariableSizedHandleScope* vshs) {
88 InstanceOfKind kind = GetParam();
89 ScopedObjectAccess soa(Thread::Current());
90 // New inst always needs to have a valid rti since we dcheck that.
91 HLoadClass* new_inst = MakeClassLoad(
92 /* ti= */ std::nullopt, vshs->NewHandle<mirror::Class>(GetClassRoot<mirror::ClassExt>()));
93 new_inst->SetValidLoadedClassRTI();
94 if (kind == InstanceOfKind::kSelf) {
95 return {new_inst, new_inst};
96 }
97 if (kind == InstanceOfKind::kUnrelatedUnloaded) {
98 HLoadClass* target_class = MakeClassLoad();
99 EXPECT_FALSE(target_class->GetLoadedClassRTI().IsValid());
100 return {new_inst, target_class};
101 }
102 // Force both classes to be a real classes.
103 // For simplicity we use class-roots as the types. The new-inst will always
104 // be a ClassExt, unrelated-loaded will always be Throwable and super will
105 // always be Object
106 HLoadClass* target_class = MakeClassLoad(
107 /* ti= */ std::nullopt,
108 vshs->NewHandle<mirror::Class>(kind == InstanceOfKind::kSupertype ?
109 GetClassRoot<mirror::Object>() :
110 GetClassRoot<mirror::Throwable>()));
111 target_class->SetValidLoadedClassRTI();
112 EXPECT_TRUE(target_class->GetLoadedClassRTI().IsValid());
113 return {new_inst, target_class};
114 }
115 };
116
117 // // ENTRY
118 // switch (param) {
119 // case 1:
120 // obj1 = param2; break;
121 // case 2:
122 // obj1 = param3; break;
123 // default:
124 // obj2 = new Obj();
125 // }
126 // val_phi = PHI[3,4,10]
127 // target_phi = PHI[param2, param3, obj2]
128 // return PredFieldGet[val_phi, target_phi] => PredFieldGet[val_phi, target_phi]
TEST_F(InstructionSimplifierTest,SimplifyPredicatedFieldGetNoMerge)129 TEST_F(InstructionSimplifierTest, SimplifyPredicatedFieldGetNoMerge) {
130 ScopedObjectAccess soa(Thread::Current());
131 VariableSizedHandleScope vshs(soa.Self());
132 CreateGraph(&vshs);
133 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
134 "exit",
135 {{"entry", "case1"},
136 {"entry", "case2"},
137 {"entry", "case3"},
138 {"case1", "breturn"},
139 {"case2", "breturn"},
140 {"case3", "breturn"},
141 {"breturn", "exit"}}));
142 #define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
143 GET_BLOCK(entry);
144 GET_BLOCK(exit);
145 GET_BLOCK(case1);
146 GET_BLOCK(case2);
147 GET_BLOCK(case3);
148 GET_BLOCK(breturn);
149 #undef GET_BLOCK
150
151 HInstruction* bool_value = MakeParam(DataType::Type::kInt32);
152 HInstruction* obj1_param = MakeParam(DataType::Type::kReference);
153 HInstruction* obj2_param = MakeParam(DataType::Type::kReference);
154 HInstruction* c3 = graph_->GetIntConstant(3);
155 HInstruction* c4 = graph_->GetIntConstant(4);
156 HInstruction* c10 = graph_->GetIntConstant(10);
157
158 HInstruction* cls = MakeClassLoad();
159 HInstruction* switch_inst = new (GetAllocator()) HPackedSwitch(0, 2, bool_value);
160 entry->AddInstruction(cls);
161 entry->AddInstruction(switch_inst);
162 ManuallyBuildEnvFor(cls, {});
163
164 HInstruction* goto_c1 = new (GetAllocator()) HGoto();
165 case1->AddInstruction(goto_c1);
166
167 HInstruction* goto_c2 = new (GetAllocator()) HGoto();
168 case2->AddInstruction(goto_c2);
169
170 HInstruction* obj3 = MakeNewInstance(cls);
171 HInstruction* goto_c3 = new (GetAllocator()) HGoto();
172 case3->AddInstruction(obj3);
173 case3->AddInstruction(goto_c3);
174
175 HPhi* val_phi = MakePhi({c3, c4, c10});
176 HPhi* obj_phi = MakePhi({obj1_param, obj2_param, obj3});
177 HPredicatedInstanceFieldGet* read_end =
178 new (GetAllocator()) HPredicatedInstanceFieldGet(obj_phi,
179 nullptr,
180 val_phi,
181 val_phi->GetType(),
182 MemberOffset(10),
183 false,
184 42,
185 0,
186 graph_->GetDexFile(),
187 0);
188 HInstruction* return_exit = new (GetAllocator()) HReturn(read_end);
189 breturn->AddPhi(val_phi);
190 breturn->AddPhi(obj_phi);
191 breturn->AddInstruction(read_end);
192 breturn->AddInstruction(return_exit);
193
194 SetupExit(exit);
195
196 LOG(INFO) << "Pre simplification " << blks;
197 graph_->ClearDominanceInformation();
198 graph_->BuildDominatorTree();
199 InstructionSimplifier simp(graph_, /*codegen=*/nullptr);
200 simp.Run();
201
202 LOG(INFO) << "Post simplify " << blks;
203
204 EXPECT_INS_RETAINED(read_end);
205
206 EXPECT_INS_EQ(read_end->GetTarget(), obj_phi);
207 EXPECT_INS_EQ(read_end->GetDefaultValue(), val_phi);
208 }
209
210 // // ENTRY
211 // switch (param) {
212 // case 1:
213 // obj1 = param2; break;
214 // case 2:
215 // obj1 = param3; break;
216 // default:
217 // obj2 = new Obj();
218 // }
219 // val_phi = PHI[3,3,10]
220 // target_phi = PHI[param2, param3, obj2]
221 // return PredFieldGet[val_phi, target_phi] => PredFieldGet[3, target_phi]
TEST_F(InstructionSimplifierTest,SimplifyPredicatedFieldGetMerge)222 TEST_F(InstructionSimplifierTest, SimplifyPredicatedFieldGetMerge) {
223 ScopedObjectAccess soa(Thread::Current());
224 VariableSizedHandleScope vshs(soa.Self());
225 CreateGraph(&vshs);
226 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
227 "exit",
228 {{"entry", "case1"},
229 {"entry", "case2"},
230 {"entry", "case3"},
231 {"case1", "breturn"},
232 {"case2", "breturn"},
233 {"case3", "breturn"},
234 {"breturn", "exit"}}));
235 #define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
236 GET_BLOCK(entry);
237 GET_BLOCK(exit);
238 GET_BLOCK(case1);
239 GET_BLOCK(case2);
240 GET_BLOCK(case3);
241 GET_BLOCK(breturn);
242 #undef GET_BLOCK
243
244 HInstruction* bool_value = MakeParam(DataType::Type::kInt32);
245 HInstruction* obj1_param = MakeParam(DataType::Type::kReference);
246 HInstruction* obj2_param = MakeParam(DataType::Type::kReference);
247 HInstruction* c3 = graph_->GetIntConstant(3);
248 HInstruction* c10 = graph_->GetIntConstant(10);
249
250 HInstruction* cls = MakeClassLoad();
251 HInstruction* switch_inst = new (GetAllocator()) HPackedSwitch(0, 2, bool_value);
252 entry->AddInstruction(cls);
253 entry->AddInstruction(switch_inst);
254 ManuallyBuildEnvFor(cls, {});
255
256 HInstruction* goto_c1 = new (GetAllocator()) HGoto();
257 case1->AddInstruction(goto_c1);
258
259 HInstruction* goto_c2 = new (GetAllocator()) HGoto();
260 case2->AddInstruction(goto_c2);
261
262 HInstruction* obj3 = MakeNewInstance(cls);
263 HInstruction* goto_c3 = new (GetAllocator()) HGoto();
264 case3->AddInstruction(obj3);
265 case3->AddInstruction(goto_c3);
266
267 HPhi* val_phi = MakePhi({c3, c3, c10});
268 HPhi* obj_phi = MakePhi({obj1_param, obj2_param, obj3});
269 HPredicatedInstanceFieldGet* read_end =
270 new (GetAllocator()) HPredicatedInstanceFieldGet(obj_phi,
271 nullptr,
272 val_phi,
273 val_phi->GetType(),
274 MemberOffset(10),
275 false,
276 42,
277 0,
278 graph_->GetDexFile(),
279 0);
280 HInstruction* return_exit = new (GetAllocator()) HReturn(read_end);
281 breturn->AddPhi(val_phi);
282 breturn->AddPhi(obj_phi);
283 breturn->AddInstruction(read_end);
284 breturn->AddInstruction(return_exit);
285
286 SetupExit(exit);
287
288 LOG(INFO) << "Pre simplification " << blks;
289 graph_->ClearDominanceInformation();
290 graph_->BuildDominatorTree();
291 InstructionSimplifier simp(graph_, /*codegen=*/nullptr);
292 simp.Run();
293
294 LOG(INFO) << "Post simplify " << blks;
295
296 EXPECT_FALSE(obj3->CanBeNull());
297 EXPECT_INS_RETAINED(read_end);
298
299 EXPECT_INS_EQ(read_end->GetTarget(), obj_phi);
300 EXPECT_INS_EQ(read_end->GetDefaultValue(), c3);
301 }
302
303 // // ENTRY
304 // if (param) {
305 // obj1 = new Obj();
306 // } else {
307 // obj2 = new Obj();
308 // }
309 // val_phi = PHI[3,10]
310 // target_phi = PHI[obj1, obj2]
311 // return PredFieldGet[val_phi, target_phi] => FieldGet[target_phi]
TEST_F(InstructionSimplifierTest,SimplifyPredicatedFieldGetNoNull)312 TEST_F(InstructionSimplifierTest, SimplifyPredicatedFieldGetNoNull) {
313 ScopedObjectAccess soa(Thread::Current());
314 VariableSizedHandleScope vshs(soa.Self());
315 CreateGraph(&vshs);
316 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
317 "exit",
318 {{"entry", "left"},
319 {"entry", "right"},
320 {"left", "breturn"},
321 {"right", "breturn"},
322 {"breturn", "exit"}}));
323 #define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
324 GET_BLOCK(entry);
325 GET_BLOCK(exit);
326 GET_BLOCK(left);
327 GET_BLOCK(right);
328 GET_BLOCK(breturn);
329 #undef GET_BLOCK
330
331 HInstruction* bool_value = MakeParam(DataType::Type::kBool);
332 HInstruction* c3 = graph_->GetIntConstant(3);
333 HInstruction* c10 = graph_->GetIntConstant(10);
334
335 HInstruction* cls = MakeClassLoad();
336 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
337 entry->AddInstruction(cls);
338 entry->AddInstruction(if_inst);
339 ManuallyBuildEnvFor(cls, {});
340
341 HInstruction* obj1 = MakeNewInstance(cls);
342 HInstruction* goto_left = new (GetAllocator()) HGoto();
343 left->AddInstruction(obj1);
344 left->AddInstruction(goto_left);
345
346 HInstruction* obj2 = MakeNewInstance(cls);
347 HInstruction* goto_right = new (GetAllocator()) HGoto();
348 right->AddInstruction(obj2);
349 right->AddInstruction(goto_right);
350
351 HPhi* val_phi = MakePhi({c3, c10});
352 HPhi* obj_phi = MakePhi({obj1, obj2});
353 obj_phi->SetCanBeNull(false);
354 HInstruction* read_end = new (GetAllocator()) HPredicatedInstanceFieldGet(obj_phi,
355 nullptr,
356 val_phi,
357 val_phi->GetType(),
358 MemberOffset(10),
359 false,
360 42,
361 0,
362 graph_->GetDexFile(),
363 0);
364 HInstruction* return_exit = new (GetAllocator()) HReturn(read_end);
365 breturn->AddPhi(val_phi);
366 breturn->AddPhi(obj_phi);
367 breturn->AddInstruction(read_end);
368 breturn->AddInstruction(return_exit);
369
370 SetupExit(exit);
371
372 LOG(INFO) << "Pre simplification " << blks;
373 graph_->ClearDominanceInformation();
374 graph_->BuildDominatorTree();
375 InstructionSimplifier simp(graph_, /*codegen=*/nullptr);
376 simp.Run();
377
378 LOG(INFO) << "Post simplify " << blks;
379
380 EXPECT_FALSE(obj1->CanBeNull());
381 EXPECT_FALSE(obj2->CanBeNull());
382 EXPECT_INS_REMOVED(read_end);
383
384 HInstanceFieldGet* ifget = FindSingleInstruction<HInstanceFieldGet>(graph_, breturn);
385 ASSERT_NE(ifget, nullptr);
386 EXPECT_INS_EQ(ifget->InputAt(0), obj_phi);
387 }
388
389 // // ENTRY
390 // obj = new Obj();
391 // // Make sure this graph isn't broken
392 // if (obj instanceof <other>) {
393 // // LEFT
394 // } else {
395 // // RIGHT
396 // }
397 // EXIT
398 // return obj.field
TEST_P(InstanceOfInstructionSimplifierTestGroup,ExactClassInstanceOfOther)399 TEST_P(InstanceOfInstructionSimplifierTestGroup, ExactClassInstanceOfOther) {
400 ScopedObjectAccess soa(Thread::Current());
401 VariableSizedHandleScope vshs(soa.Self());
402 InitGraph(/*handles=*/&vshs);
403
404 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
405 "exit",
406 {{"entry", "left"},
407 {"entry", "right"},
408 {"left", "breturn"},
409 {"right", "breturn"},
410 {"breturn", "exit"}}));
411 #define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
412 GET_BLOCK(entry);
413 GET_BLOCK(exit);
414 GET_BLOCK(breturn);
415 GET_BLOCK(left);
416 GET_BLOCK(right);
417 #undef GET_BLOCK
418 EnsurePredecessorOrder(breturn, {left, right});
419 HInstruction* test_res = graph_->GetIntConstant(GetConstantResult() ? 1 : 0);
420
421 auto [new_inst_klass, target_klass] = GetLoadClasses(&vshs);
422 HInstruction* new_inst = MakeNewInstance(new_inst_klass);
423 new_inst->SetReferenceTypeInfo(
424 ReferenceTypeInfo::Create(new_inst_klass->GetClass(), /*is_exact=*/true));
425 HInstanceOf* instance_of = new (GetAllocator()) HInstanceOf(new_inst,
426 target_klass,
427 TypeCheckKind::kClassHierarchyCheck,
428 target_klass->GetClass(),
429 0u,
430 GetAllocator(),
431 nullptr,
432 nullptr);
433 if (target_klass->GetLoadedClassRTI().IsValid()) {
434 instance_of->SetValidTargetClassRTI();
435 }
436 HInstruction* if_inst = new (GetAllocator()) HIf(instance_of);
437 entry->AddInstruction(new_inst_klass);
438 if (new_inst_klass != target_klass) {
439 entry->AddInstruction(target_klass);
440 }
441 entry->AddInstruction(new_inst);
442 entry->AddInstruction(instance_of);
443 entry->AddInstruction(if_inst);
444 ManuallyBuildEnvFor(new_inst_klass, {});
445 if (new_inst_klass != target_klass) {
446 target_klass->CopyEnvironmentFrom(new_inst_klass->GetEnvironment());
447 }
448 new_inst->CopyEnvironmentFrom(new_inst_klass->GetEnvironment());
449
450 HInstruction* goto_left = new (GetAllocator()) HGoto();
451 left->AddInstruction(goto_left);
452
453 HInstruction* goto_right = new (GetAllocator()) HGoto();
454 right->AddInstruction(goto_right);
455
456 HInstruction* read_bottom = MakeIFieldGet(new_inst, DataType::Type::kInt32, MemberOffset(32));
457 HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
458 breturn->AddInstruction(read_bottom);
459 breturn->AddInstruction(return_exit);
460
461 SetupExit(exit);
462
463 // PerformLSE expects this to be empty.
464 graph_->ClearDominanceInformation();
465
466 LOG(INFO) << "Pre simplification " << blks;
467 graph_->ClearDominanceInformation();
468 graph_->BuildDominatorTree();
469 InstructionSimplifier simp(graph_, /*codegen=*/nullptr);
470 simp.Run();
471
472 LOG(INFO) << "Post simplify " << blks;
473
474 if (!GetConstantResult() || GetParam() == InstanceOfKind::kSelf) {
475 EXPECT_INS_RETAINED(target_klass);
476 } else {
477 EXPECT_INS_REMOVED(target_klass);
478 }
479 EXPECT_INS_REMOVED(instance_of);
480 EXPECT_INS_EQ(if_inst->InputAt(0), test_res);
481 }
482
483 // // ENTRY
484 // obj = new Obj();
485 // (<other>)obj;
486 // // Make sure this graph isn't broken
487 // EXIT
488 // return obj
TEST_P(InstanceOfInstructionSimplifierTestGroup,ExactClassCheckCastOther)489 TEST_P(InstanceOfInstructionSimplifierTestGroup, ExactClassCheckCastOther) {
490 ScopedObjectAccess soa(Thread::Current());
491 VariableSizedHandleScope vshs(soa.Self());
492 InitGraph(/*handles=*/&vshs);
493
494 AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", {{"entry", "exit"}}));
495 #define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
496 GET_BLOCK(entry);
497 GET_BLOCK(exit);
498 #undef GET_BLOCK
499
500 auto [new_inst_klass, target_klass] = GetLoadClasses(&vshs);
501 HInstruction* new_inst = MakeNewInstance(new_inst_klass);
502 new_inst->SetReferenceTypeInfo(
503 ReferenceTypeInfo::Create(new_inst_klass->GetClass(), /*is_exact=*/true));
504 HCheckCast* check_cast = new (GetAllocator()) HCheckCast(new_inst,
505 target_klass,
506 TypeCheckKind::kClassHierarchyCheck,
507 target_klass->GetClass(),
508 0u,
509 GetAllocator(),
510 nullptr,
511 nullptr);
512 if (target_klass->GetLoadedClassRTI().IsValid()) {
513 check_cast->SetValidTargetClassRTI();
514 }
515 HInstruction* entry_return = new (GetAllocator()) HReturn(new_inst);
516 entry->AddInstruction(new_inst_klass);
517 if (new_inst_klass != target_klass) {
518 entry->AddInstruction(target_klass);
519 }
520 entry->AddInstruction(new_inst);
521 entry->AddInstruction(check_cast);
522 entry->AddInstruction(entry_return);
523 ManuallyBuildEnvFor(new_inst_klass, {});
524 if (new_inst_klass != target_klass) {
525 target_klass->CopyEnvironmentFrom(new_inst_klass->GetEnvironment());
526 }
527 new_inst->CopyEnvironmentFrom(new_inst_klass->GetEnvironment());
528
529 SetupExit(exit);
530
531 // PerformLSE expects this to be empty.
532 graph_->ClearDominanceInformation();
533
534 LOG(INFO) << "Pre simplification " << blks;
535 graph_->ClearDominanceInformation();
536 graph_->BuildDominatorTree();
537 InstructionSimplifier simp(graph_, /*codegen=*/nullptr);
538 simp.Run();
539
540 LOG(INFO) << "Post simplify " << blks;
541
542 if (!GetConstantResult() || GetParam() == InstanceOfKind::kSelf) {
543 EXPECT_INS_RETAINED(target_klass);
544 } else {
545 EXPECT_INS_REMOVED(target_klass);
546 }
547 if (GetConstantResult()) {
548 EXPECT_INS_REMOVED(check_cast);
549 } else {
550 EXPECT_INS_RETAINED(check_cast);
551 }
552 }
553
554 INSTANTIATE_TEST_SUITE_P(InstructionSimplifierTest,
555 InstanceOfInstructionSimplifierTestGroup,
556 testing::Values(InstanceOfKind::kSelf,
557 InstanceOfKind::kUnrelatedLoaded,
558 InstanceOfKind::kUnrelatedUnloaded,
559 InstanceOfKind::kSupertype));
560
561 } // namespace art
562