1 /*
2 * Copyright (C) 2018 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 "control_flow_simplifier.h"
18
19 #include "base/arena_allocator.h"
20 #include "base/macros.h"
21 #include "builder.h"
22 #include "nodes.h"
23 #include "optimizing_unit_test.h"
24 #include "side_effects_analysis.h"
25
26 namespace art HIDDEN {
27
28 class ControlFlowSimplifierTest : public OptimizingUnitTest {
29 protected:
ConstructBasicGraphForSelect(HBasicBlock * return_block,HInstruction * instr)30 HPhi* ConstructBasicGraphForSelect(HBasicBlock* return_block, HInstruction* instr) {
31 HParameterValue* bool_param = MakeParam(DataType::Type::kBool);
32 HIntConstant* const1 = graph_->GetIntConstant(1);
33
34 auto [if_block, then_block, else_block] = CreateDiamondPattern(return_block, bool_param);
35
36 AddOrInsertInstruction(then_block, instr);
37 HPhi* phi = MakePhi(return_block, {instr, const1});
38 return phi;
39 }
40
CheckGraphAndTryControlFlowSimplifier()41 bool CheckGraphAndTryControlFlowSimplifier() {
42 graph_->BuildDominatorTree();
43 EXPECT_TRUE(CheckGraph());
44
45 SideEffectsAnalysis side_effects(graph_);
46 side_effects.Run();
47 return HControlFlowSimplifier(graph_, /*handles*/ nullptr, /*stats*/ nullptr).Run();
48 }
49 };
50
51 // HDivZeroCheck might throw and should not be hoisted from the conditional to an unconditional.
TEST_F(ControlFlowSimplifierTest,testZeroCheckPreventsSelect)52 TEST_F(ControlFlowSimplifierTest, testZeroCheckPreventsSelect) {
53 HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
54 HParameterValue* param = MakeParam(DataType::Type::kInt32);
55 HDivZeroCheck* instr = new (GetAllocator()) HDivZeroCheck(param, 0);
56 HPhi* phi = ConstructBasicGraphForSelect(return_block, instr);
57
58 ManuallyBuildEnvFor(instr, {param, graph_->GetIntConstant(1)});
59
60 EXPECT_FALSE(CheckGraphAndTryControlFlowSimplifier());
61 EXPECT_INS_RETAINED(phi);
62 }
63
64 // Test that ControlFlowSimplifier succeeds with HAdd.
TEST_F(ControlFlowSimplifierTest,testSelectWithAdd)65 TEST_F(ControlFlowSimplifierTest, testSelectWithAdd) {
66 HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
67 HParameterValue* param = MakeParam(DataType::Type::kInt32);
68 HAdd* instr = new (GetAllocator()) HAdd(DataType::Type::kInt32, param, param, /*dex_pc=*/ 0);
69 HPhi* phi = ConstructBasicGraphForSelect(return_block, instr);
70 EXPECT_TRUE(CheckGraphAndTryControlFlowSimplifier());
71 EXPECT_INS_REMOVED(phi);
72 }
73
74 // Test that ControlFlowSimplifier succeeds if there is an additional `HPhi` with identical inputs.
TEST_F(ControlFlowSimplifierTest,testSelectWithAddAndExtraPhi)75 TEST_F(ControlFlowSimplifierTest, testSelectWithAddAndExtraPhi) {
76 // Create a graph with three blocks merging to the `return_block`.
77 HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
78 HParameterValue* bool_param1 = MakeParam(DataType::Type::kBool);
79 HParameterValue* bool_param2 = MakeParam(DataType::Type::kBool);
80 HParameterValue* param = MakeParam(DataType::Type::kInt32);
81 HInstruction* const0 = graph_->GetIntConstant(0);
82 auto [if_block1, left, mid] = CreateDiamondPattern(return_block, bool_param1);
83 HBasicBlock* if_block2 = AddNewBlock();
84 if_block1->ReplaceSuccessor(mid, if_block2);
85 HBasicBlock* right = AddNewBlock();
86 if_block2->AddSuccessor(mid);
87 if_block2->AddSuccessor(right);
88 HIf* if2 = MakeIf(if_block2, bool_param2);
89 right->AddSuccessor(return_block);
90 MakeGoto(right);
91 ASSERT_TRUE(PredecessorsEqual(return_block, {left, mid, right}));
92 HAdd* add = MakeBinOp<HAdd>(right, DataType::Type::kInt32, param, param);
93 HPhi* phi1 = MakePhi(return_block, {param, param, add});
94 HPhi* phi2 = MakePhi(return_block, {param, const0, const0});
95
96 // Prevent second `HSelect` match. Do not rely on the "instructions per branch" limit.
97 MakeInvokeStatic(left, DataType::Type::kVoid, {}, {});
98
99 EXPECT_TRUE(CheckGraphAndTryControlFlowSimplifier());
100
101 ASSERT_BLOCK_RETAINED(left);
102 ASSERT_BLOCK_REMOVED(mid);
103 ASSERT_BLOCK_REMOVED(right);
104 HInstruction* select = if2->GetPrevious(); // `HSelect` is inserted before `HIf`.
105 ASSERT_TRUE(select->IsSelect());
106 ASSERT_INS_RETAINED(phi1);
107 ASSERT_TRUE(InputsEqual(phi1, {param, select}));
108 ASSERT_INS_RETAINED(phi2);
109 ASSERT_TRUE(InputsEqual(phi2, {param, const0}));
110 }
111
112 // Test `HSelect` optimization in an irreducible loop.
TEST_F(ControlFlowSimplifierTest,testSelectInIrreducibleLoop)113 TEST_F(ControlFlowSimplifierTest, testSelectInIrreducibleLoop) {
114 HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
115 auto [split, left_header, right_header, body] = CreateIrreducibleLoop(return_block);
116
117 HParameterValue* split_param = MakeParam(DataType::Type::kBool);
118 HParameterValue* bool_param = MakeParam(DataType::Type::kBool);
119 HParameterValue* n_param = MakeParam(DataType::Type::kInt32);
120
121 MakeIf(split, split_param);
122
123 HInstruction* const0 = graph_->GetIntConstant(0);
124 HInstruction* const1 = graph_->GetIntConstant(1);
125 auto [left_phi, right_phi, add] =
126 MakeLinearIrreducibleLoopVar(left_header, right_header, body, const1, const0, const1);
127 HCondition* condition = MakeCondition(left_header, kCondGE, left_phi, n_param);
128 MakeIf(left_header, condition);
129
130 auto [if_block, then_block, else_block] = CreateDiamondPattern(body, bool_param);
131 HPhi* phi = MakePhi(body, {const1, const0});
132
133 EXPECT_TRUE(CheckGraphAndTryControlFlowSimplifier());
134 HLoopInformation* loop_info = left_header->GetLoopInformation();
135 ASSERT_TRUE(loop_info != nullptr);
136 ASSERT_TRUE(loop_info->IsIrreducible());
137
138 EXPECT_INS_REMOVED(phi);
139 ASSERT_TRUE(if_block->GetFirstInstruction()->IsSelect());
140
141 ASSERT_EQ(if_block, add->GetBlock()); // Moved when merging blocks.
142
143 for (HBasicBlock* removed_block : {then_block, else_block, body}) {
144 ASSERT_BLOCK_REMOVED(removed_block);
145 uint32_t removed_block_id = removed_block->GetBlockId();
146 ASSERT_FALSE(loop_info->GetBlocks().IsBitSet(removed_block_id)) << removed_block_id;
147 }
148 }
149
150 } // namespace art
151