1 /*
2 * Copyright (C) 2025 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 "prepare_for_register_allocation.h"
18
19 #include <gtest/gtest.h>
20
21 #include "base/macros.h"
22 #include "optimizing_unit_test.h"
23
24 namespace art HIDDEN {
25
26 class PrepareForRegisterAllocationTest
27 : public CommonCompilerTest, public OptimizingUnitTestHelper {
28 protected:
RunPass()29 void RunPass() {
30 graph_->BuildDominatorTree();
31 PrepareForRegisterAllocation(graph_, *compiler_options_).Run();
32 }
33 };
34
TEST_F(PrepareForRegisterAllocationTest,MergeConditionToSelect)35 TEST_F(PrepareForRegisterAllocationTest, MergeConditionToSelect) {
36 HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid();
37
38 HInstruction* param = MakeParam(DataType::Type::kInt32);
39 HInstruction* zero_const = graph_->GetIntConstant(0);
40 HCondition* condition = MakeCondition(ret, kCondLT, param, zero_const);
41 HSelect* select = MakeSelect(ret, condition, zero_const, param);
42
43 RunPass();
44
45 ASSERT_TRUE(condition->IsEmittedAtUseSite());
46 ASSERT_EQ(condition->GetNext(), select);
47 }
48
TEST_F(PrepareForRegisterAllocationTest,MergeConditionToDeoptimize)49 TEST_F(PrepareForRegisterAllocationTest, MergeConditionToDeoptimize) {
50 HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid();
51
52 HInstruction* param = MakeParam(DataType::Type::kInt32);
53 HInstruction* zero_const = graph_->GetIntConstant(0);
54 HCondition* condition = MakeCondition(ret, kCondLT, param, zero_const);
55 HDeoptimize* deopt = new (GetAllocator()) HDeoptimize(
56 GetAllocator(), condition, DeoptimizationKind::kAotInlineCache, /*dex_pc=*/ 0u);
57 AddOrInsertInstruction(ret, deopt);
58
59 RunPass();
60
61 ASSERT_TRUE(condition->IsEmittedAtUseSite());
62 ASSERT_EQ(condition->GetNext(), deopt);
63 }
64
TEST_F(PrepareForRegisterAllocationTest,MergeConditionToIf)65 TEST_F(PrepareForRegisterAllocationTest, MergeConditionToIf) {
66 HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid();
67 auto [start, left, right] = CreateDiamondPattern(ret);
68
69 HInstruction* param = MakeParam(DataType::Type::kInt32);
70 HInstruction* zero_const = graph_->GetIntConstant(0);
71 HCondition* condition = MakeCondition(start, kCondLT, param, zero_const);
72 HIf* start_if = MakeIf(start, condition);
73
74 RunPass();
75
76 ASSERT_TRUE(condition->IsEmittedAtUseSite());
77 ASSERT_EQ(condition->GetNext(), start_if);
78 }
79
TEST_F(PrepareForRegisterAllocationTest,MergeConditionToIfWithMove)80 TEST_F(PrepareForRegisterAllocationTest, MergeConditionToIfWithMove) {
81 HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid();
82 auto [start, left, right] = CreateDiamondPattern(ret);
83
84 HInstruction* param = MakeParam(DataType::Type::kInt32);
85 HInstruction* zero_const = graph_->GetIntConstant(0);
86 HCondition* condition = MakeCondition(start, kCondLT, param, zero_const);
87 HInstruction* add = MakeBinOp<HAdd>(start, DataType::Type::kInt32, param, param);
88 HIf* start_if = MakeIf(start, condition);
89
90 ASSERT_EQ(condition->GetNext(), add);
91 ASSERT_EQ(add->GetNext(), start_if);
92
93 RunPass();
94
95 ASSERT_TRUE(condition->IsEmittedAtUseSite());
96 ASSERT_EQ(add->GetNext(), condition);
97 ASSERT_EQ(condition->GetNext(), start_if);
98 }
99
TEST_F(PrepareForRegisterAllocationTest,MergeConditionToIfWithMoveFromPredecessor)100 TEST_F(PrepareForRegisterAllocationTest, MergeConditionToIfWithMoveFromPredecessor) {
101 HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid();
102 auto [start, left, right_end] = CreateDiamondPattern(ret);
103 auto [right_start, right_left, right_right] = CreateDiamondPattern(right_end);
104
105 HInstruction* cond_param = MakeParam(DataType::Type::kBool);
106 HInstruction* param = MakeParam(DataType::Type::kInt32);
107 HInstruction* zero_const = graph_->GetIntConstant(0);
108 HCondition* condition = MakeCondition(start, kCondLT, param, zero_const);
109 MakeIf(start, cond_param);
110 // Note: The condition for this `HIf` is in the predecessor block.
111 HIf* right_start_if = MakeIf(right_start, condition);
112
113 ASSERT_NE(condition->GetBlock(), right_start_if->GetBlock());
114
115 RunPass();
116
117 ASSERT_TRUE(condition->IsEmittedAtUseSite());
118 ASSERT_EQ(condition->GetBlock(), right_start_if->GetBlock());
119 ASSERT_EQ(condition->GetNext(), right_start_if);
120 }
121
TEST_F(PrepareForRegisterAllocationTest,MergeConditionPreventedByOtherUse)122 TEST_F(PrepareForRegisterAllocationTest, MergeConditionPreventedByOtherUse) {
123 HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid();
124 auto [start, left, right] = CreateDiamondPattern(ret);
125
126 HInstruction* param = MakeParam(DataType::Type::kInt32);
127 HInstruction* zero_const = graph_->GetIntConstant(0);
128 HCondition* condition = MakeCondition(start, kCondLT, param, zero_const);
129 HIf* start_if = MakeIf(start, condition);
130
131 // Other use.
132 MakeBinOp<HAdd>(ret, DataType::Type::kInt32, param, condition);
133
134 RunPass();
135
136 ASSERT_TRUE(!condition->IsEmittedAtUseSite());
137 ASSERT_EQ(condition->GetNext(), start_if);
138 }
139
TEST_F(PrepareForRegisterAllocationTest,MergeConditionPreventedByEnvUse)140 TEST_F(PrepareForRegisterAllocationTest, MergeConditionPreventedByEnvUse) {
141 HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid();
142 auto [start, left, right] = CreateDiamondPattern(ret);
143
144 HInstruction* param = MakeParam(DataType::Type::kInt32);
145 HInstruction* zero_const = graph_->GetIntConstant(0);
146 HCondition* condition = MakeCondition(start, kCondLT, param, zero_const);
147 HIf* start_if = MakeIf(start, condition);
148
149 // Environment use.
150 MakeInvokeStatic(ret, DataType::Type::kVoid, /*args=*/ {}, /*env=*/ {condition});
151
152 RunPass();
153
154 ASSERT_TRUE(!condition->IsEmittedAtUseSite());
155 ASSERT_EQ(condition->GetNext(), start_if);
156 }
157
TEST_F(PrepareForRegisterAllocationTest,MergeConditionPrevented_RefNoEnvInBlock)158 TEST_F(PrepareForRegisterAllocationTest, MergeConditionPrevented_RefNoEnvInBlock) {
159 ScopedObjectAccess soa(Thread::Current());
160 VariableSizedHandleScope vshs(soa.Self());
161 HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid(&vshs);
162 auto [start, left, right_end] = CreateDiamondPattern(ret);
163 auto [right_start, right_left, right_right] = CreateDiamondPattern(right_end);
164
165 HInstruction* cond_param = MakeParam(DataType::Type::kBool);
166 HInstruction* param = MakeParam(DataType::Type::kReference);
167 HInstruction* null_const = graph_->GetNullConstant();
168 HCondition* condition = MakeCondition(start, kCondEQ, param, null_const);
169 MakeIf(start, cond_param);
170 // Note: The condition for this `HIf` is in the predecessor block.
171 HIf* right_start_if = MakeIf(right_start, condition);
172
173 RunPass();
174
175 ASSERT_TRUE(!condition->IsEmittedAtUseSite());
176 ASSERT_NE(condition->GetBlock(), right_start_if->GetBlock()); // Not moved to the `HIf`.
177 }
178
TEST_F(PrepareForRegisterAllocationTest,MergeCondition_RefsInEnv)179 TEST_F(PrepareForRegisterAllocationTest, MergeCondition_RefsInEnv) {
180 ScopedObjectAccess soa(Thread::Current());
181 VariableSizedHandleScope vshs(soa.Self());
182 HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid(&vshs);
183 auto [start, left, right_end] = CreateDiamondPattern(ret);
184
185 HInstruction* param1 = MakeParam(DataType::Type::kReference);
186 HInstruction* param2 = MakeParam(DataType::Type::kReference);
187 HCondition* condition = MakeCondition(start, kCondEQ, param1, param2);
188
189 // This invoke's environment already contains `param1` and `param2`, so reordering
190 // the `condition` after the invoke would not extend their lifetime for the purpose of GC.
191 HInvoke* invoke =
192 MakeInvokeStatic(start, DataType::Type::kVoid, /*args=*/ {}, /*env=*/ {param1, param2});
193
194 HIf* start_if = MakeIf(start, condition);
195
196 ASSERT_EQ(condition->GetNext(), invoke);
197 ASSERT_EQ(invoke->GetNext(), start_if);
198
199 RunPass();
200
201 ASSERT_TRUE(condition->IsEmittedAtUseSite());
202 ASSERT_EQ(invoke->GetNext(), condition);
203 ASSERT_EQ(condition->GetNext(), start_if);
204 }
205
TEST_F(PrepareForRegisterAllocationTest,MergeCondition_RefLhsInEnv)206 TEST_F(PrepareForRegisterAllocationTest, MergeCondition_RefLhsInEnv) {
207 ScopedObjectAccess soa(Thread::Current());
208 VariableSizedHandleScope vshs(soa.Self());
209 HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid(&vshs);
210 auto [start, left, right_end] = CreateDiamondPattern(ret);
211
212 HInstruction* param = MakeParam(DataType::Type::kReference);
213 HInstruction* null_const = graph_->GetNullConstant();
214 HCondition* condition = MakeCondition(start, kCondEQ, param, null_const);
215
216 // This invoke's environment already contains `param`, so reordering the `condition`
217 // after the invoke would not extend its lifetime for the purpose of GC.
218 HInvoke* invoke = MakeInvokeStatic(start, DataType::Type::kVoid, /*args=*/ {}, /*env=*/ {param});
219
220 HIf* start_if = MakeIf(start, condition);
221
222 ASSERT_EQ(condition->GetNext(), invoke);
223 ASSERT_EQ(invoke->GetNext(), start_if);
224
225 RunPass();
226
227 ASSERT_TRUE(condition->IsEmittedAtUseSite());
228 ASSERT_EQ(invoke->GetNext(), condition);
229 ASSERT_EQ(condition->GetNext(), start_if);
230 }
231
TEST_F(PrepareForRegisterAllocationTest,MergeCondition_RefRhsInEnv)232 TEST_F(PrepareForRegisterAllocationTest, MergeCondition_RefRhsInEnv) {
233 ScopedObjectAccess soa(Thread::Current());
234 VariableSizedHandleScope vshs(soa.Self());
235 HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid(&vshs);
236 auto [start, left, right_end] = CreateDiamondPattern(ret);
237
238 HInstruction* param = MakeParam(DataType::Type::kReference);
239 HInstruction* null_const = graph_->GetNullConstant();
240 HCondition* condition = MakeCondition(start, kCondEQ, null_const, param);
241
242 // This invoke's environment already contains `param`, so reordering the `condition`
243 // after the invoke would not extend its lifetime for the purpose of GC.
244 HInvoke* invoke = MakeInvokeStatic(start, DataType::Type::kVoid, /*args=*/ {}, /*env=*/ {param});
245
246 HIf* start_if = MakeIf(start, condition);
247
248 ASSERT_EQ(condition->GetNext(), invoke);
249 ASSERT_EQ(invoke->GetNext(), start_if);
250
251 RunPass();
252
253 ASSERT_TRUE(condition->IsEmittedAtUseSite());
254 ASSERT_EQ(invoke->GetNext(), condition);
255 ASSERT_EQ(condition->GetNext(), start_if);
256 }
257
TEST_F(PrepareForRegisterAllocationTest,MergeConditionPrevented_RefLhsNotInEnv)258 TEST_F(PrepareForRegisterAllocationTest, MergeConditionPrevented_RefLhsNotInEnv) {
259 ScopedObjectAccess soa(Thread::Current());
260 VariableSizedHandleScope vshs(soa.Self());
261 HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid(&vshs);
262 auto [start, left, right_end] = CreateDiamondPattern(ret);
263
264 HInstruction* param1 = MakeParam(DataType::Type::kReference);
265 HInstruction* param2 = MakeParam(DataType::Type::kReference);
266 HCondition* condition = MakeCondition(start, kCondEQ, param1, param2);
267
268 // This invoke's environment does not contain `param1`, so reordering the `condition`
269 // after the invoke would need to extend the lifetime of `param1` for the purpose of GC.
270 // We do not want to extend lifetime of references, therefore the optimization is skipped.
271 HInvoke* invoke = MakeInvokeStatic(start, DataType::Type::kVoid, /*args=*/ {}, /*env=*/ {param2});
272
273 HIf* start_if = MakeIf(start, condition);
274
275 ASSERT_EQ(condition->GetNext(), invoke);
276 ASSERT_EQ(invoke->GetNext(), start_if);
277
278 RunPass();
279
280 ASSERT_TRUE(!condition->IsEmittedAtUseSite());
281 ASSERT_EQ(condition->GetNext(), invoke);
282 ASSERT_EQ(invoke->GetNext(), start_if);
283 }
284
TEST_F(PrepareForRegisterAllocationTest,MergeConditionPrevented_RefRhsNotInEnv)285 TEST_F(PrepareForRegisterAllocationTest, MergeConditionPrevented_RefRhsNotInEnv) {
286 ScopedObjectAccess soa(Thread::Current());
287 VariableSizedHandleScope vshs(soa.Self());
288 HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid(&vshs);
289 auto [start, left, right_end] = CreateDiamondPattern(ret);
290
291 HInstruction* param1 = MakeParam(DataType::Type::kReference);
292 HInstruction* param2 = MakeParam(DataType::Type::kReference);
293 HCondition* condition = MakeCondition(start, kCondEQ, param1, param2);
294
295 // This invoke's environment does not contain `param2`, so reordering the `condition`
296 // after the invoke would need to extend the lifetime of `param2` for the purpose of GC.
297 // We do not want to extend lifetime of references, therefore the optimization is skipped.
298 HInvoke* invoke = MakeInvokeStatic(start, DataType::Type::kVoid, /*args=*/ {}, /*env=*/ {param1});
299
300 HIf* start_if = MakeIf(start, condition);
301
302 ASSERT_EQ(condition->GetNext(), invoke);
303 ASSERT_EQ(invoke->GetNext(), start_if);
304
305 RunPass();
306
307 ASSERT_TRUE(!condition->IsEmittedAtUseSite());
308 ASSERT_EQ(condition->GetNext(), invoke);
309 ASSERT_EQ(invoke->GetNext(), start_if);
310 }
311
312 } // namespace art
313