1 /*
2 * Copyright (C) 2014 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 <functional>
18
19 #include "constant_folding.h"
20
21 #include "base/macros.h"
22 #include "dead_code_elimination.h"
23 #include "driver/compiler_options.h"
24 #include "graph_checker.h"
25 #include "optimizing_unit_test.h"
26 #include "pretty_printer.h"
27
28 #include "gtest/gtest.h"
29
30 namespace art HIDDEN {
31
32 /**
33 * Fixture class for the constant folding and dce tests.
34 */
35 class ConstantFoldingTest : public CommonCompilerTest, public OptimizingUnitTestHelper {
36 public:
ConstantFoldingTest()37 ConstantFoldingTest() { }
38
TestCode(const std::vector<uint16_t> & data,const std::string & expected_before,const std::string & expected_after_cf,const std::string & expected_after_dce,const std::function<void (HGraph *)> & check_after_cf,DataType::Type return_type=DataType::Type::kInt32)39 void TestCode(const std::vector<uint16_t>& data,
40 const std::string& expected_before,
41 const std::string& expected_after_cf,
42 const std::string& expected_after_dce,
43 const std::function<void(HGraph*)>& check_after_cf,
44 DataType::Type return_type = DataType::Type::kInt32) {
45 graph_ = CreateCFG(data, return_type);
46 TestCodeOnReadyGraph(expected_before,
47 expected_after_cf,
48 expected_after_dce,
49 check_after_cf);
50 }
51
TestCodeOnReadyGraph(const std::string & expected_before,const std::string & expected_after_cf,const std::string & expected_after_dce,const std::function<void (HGraph *)> & check_after_cf)52 void TestCodeOnReadyGraph(const std::string& expected_before,
53 const std::string& expected_after_cf,
54 const std::string& expected_after_dce,
55 const std::function<void(HGraph*)>& check_after_cf) {
56 ASSERT_NE(graph_, nullptr);
57
58 StringPrettyPrinter printer_before(graph_);
59 printer_before.VisitInsertionOrder();
60 std::string actual_before = printer_before.str();
61 EXPECT_EQ(expected_before, actual_before);
62
63 HConstantFolding(graph_, /* stats= */ nullptr, "constant_folding").Run();
64 GraphChecker graph_checker_cf(graph_);
65 graph_checker_cf.Run();
66 ASSERT_TRUE(graph_checker_cf.IsValid());
67
68 StringPrettyPrinter printer_after_cf(graph_);
69 printer_after_cf.VisitInsertionOrder();
70 std::string actual_after_cf = printer_after_cf.str();
71 EXPECT_EQ(expected_after_cf, actual_after_cf);
72
73 check_after_cf(graph_);
74
75 HDeadCodeElimination(graph_, /* stats= */ nullptr, "dead_code_elimination").Run();
76 GraphChecker graph_checker_dce(graph_);
77 graph_checker_dce.Run();
78 ASSERT_TRUE(graph_checker_dce.IsValid());
79
80 StringPrettyPrinter printer_after_dce(graph_);
81 printer_after_dce.VisitInsertionOrder();
82 std::string actual_after_dce = printer_after_dce.str();
83 EXPECT_EQ(expected_after_dce, actual_after_dce);
84 }
85 };
86
87 /**
88 * Tiny three-register program exercising int constant folding on negation.
89 *
90 * 16-bit
91 * offset
92 * ------
93 * v0 <- 1 0. const/4 v0, #+1
94 * v1 <- -v0 1. neg-int v1, v0
95 * return v1 2. return v1
96 */
TEST_F(ConstantFoldingTest,IntConstantFoldingNegation)97 TEST_F(ConstantFoldingTest, IntConstantFoldingNegation) {
98 const std::vector<uint16_t> data = TWO_REGISTERS_CODE_ITEM(
99 Instruction::CONST_4 | 0 << 8 | 1 << 12,
100 Instruction::NEG_INT | 1 << 8 | 0 << 12,
101 Instruction::RETURN | 1 << 8);
102
103 std::string expected_before =
104 "BasicBlock 0, succ: 1\n"
105 " 2: IntConstant [3]\n"
106 " 0: SuspendCheck\n"
107 " 1: Goto 1\n"
108 "BasicBlock 1, pred: 0, succ: 2\n"
109 " 3: Neg(2) [4]\n"
110 " 4: Return(3)\n"
111 "BasicBlock 2, pred: 1\n"
112 " 5: Exit\n";
113
114 // Expected difference after constant folding.
115 diff_t expected_cf_diff = {
116 { " 2: IntConstant [3]\n", " 2: IntConstant\n"
117 " 6: IntConstant [4]\n" },
118 { " 3: Neg(2) [4]\n", removed },
119 { " 4: Return(3)\n", " 4: Return(6)\n" }
120 };
121 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
122
123 // Check the value of the computed constant.
124 auto check_after_cf = [](HGraph* graph) {
125 HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
126 ASSERT_TRUE(inst->IsIntConstant());
127 ASSERT_EQ(inst->AsIntConstant()->GetValue(), -1);
128 };
129
130 // Expected difference after dead code elimination.
131 diff_t expected_dce_diff = {
132 { " 2: IntConstant\n", removed },
133 };
134 std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
135
136 TestCode(data,
137 expected_before,
138 expected_after_cf,
139 expected_after_dce,
140 check_after_cf);
141 }
142
143 /**
144 * Tiny three-register program exercising long constant folding on negation.
145 *
146 * 16-bit
147 * offset
148 * ------
149 * (v0, v1) <- 4294967296 0. const-wide v0 #+4294967296
150 * (v2, v3) <- -(v0, v1) 1. neg-long v2, v0
151 * return (v2, v3) 2. return-wide v2
152 */
TEST_F(ConstantFoldingTest,LongConstantFoldingNegation)153 TEST_F(ConstantFoldingTest, LongConstantFoldingNegation) {
154 const int64_t input = INT64_C(4294967296); // 2^32
155 const uint16_t word0 = Low16Bits(Low32Bits(input)); // LSW.
156 const uint16_t word1 = High16Bits(Low32Bits(input));
157 const uint16_t word2 = Low16Bits(High32Bits(input));
158 const uint16_t word3 = High16Bits(High32Bits(input)); // MSW.
159 const std::vector<uint16_t> data = FOUR_REGISTERS_CODE_ITEM(
160 Instruction::CONST_WIDE | 0 << 8, word0, word1, word2, word3,
161 Instruction::NEG_LONG | 2 << 8 | 0 << 12,
162 Instruction::RETURN_WIDE | 2 << 8);
163
164 std::string expected_before =
165 "BasicBlock 0, succ: 1\n"
166 " 2: LongConstant [3]\n"
167 " 0: SuspendCheck\n"
168 " 1: Goto 1\n"
169 "BasicBlock 1, pred: 0, succ: 2\n"
170 " 3: Neg(2) [4]\n"
171 " 4: Return(3)\n"
172 "BasicBlock 2, pred: 1\n"
173 " 5: Exit\n";
174
175 // Expected difference after constant folding.
176 diff_t expected_cf_diff = {
177 { " 2: LongConstant [3]\n", " 2: LongConstant\n"
178 " 6: LongConstant [4]\n" },
179 { " 3: Neg(2) [4]\n", removed },
180 { " 4: Return(3)\n", " 4: Return(6)\n" }
181 };
182 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
183
184 // Check the value of the computed constant.
185 auto check_after_cf = [](HGraph* graph) {
186 HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
187 ASSERT_TRUE(inst->IsLongConstant());
188 ASSERT_EQ(inst->AsLongConstant()->GetValue(), INT64_C(-4294967296));
189 };
190
191 // Expected difference after dead code elimination.
192 diff_t expected_dce_diff = {
193 { " 2: LongConstant\n", removed },
194 };
195 std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
196
197 TestCode(data,
198 expected_before,
199 expected_after_cf,
200 expected_after_dce,
201 check_after_cf,
202 DataType::Type::kInt64);
203 }
204
205 /**
206 * Tiny three-register program exercising int constant folding on addition.
207 *
208 * 16-bit
209 * offset
210 * ------
211 * v0 <- 1 0. const/4 v0, #+1
212 * v1 <- 2 1. const/4 v1, #+2
213 * v2 <- v0 + v1 2. add-int v2, v0, v1
214 * return v2 4. return v2
215 */
TEST_F(ConstantFoldingTest,IntConstantFoldingOnAddition1)216 TEST_F(ConstantFoldingTest, IntConstantFoldingOnAddition1) {
217 const std::vector<uint16_t> data = THREE_REGISTERS_CODE_ITEM(
218 Instruction::CONST_4 | 0 << 8 | 1 << 12,
219 Instruction::CONST_4 | 1 << 8 | 2 << 12,
220 Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
221 Instruction::RETURN | 2 << 8);
222
223 std::string expected_before =
224 "BasicBlock 0, succ: 1\n"
225 " 2: IntConstant [4]\n"
226 " 3: IntConstant [4]\n"
227 " 0: SuspendCheck\n"
228 " 1: Goto 1\n"
229 "BasicBlock 1, pred: 0, succ: 2\n"
230 " 4: Add(2, 3) [5]\n"
231 " 5: Return(4)\n"
232 "BasicBlock 2, pred: 1\n"
233 " 6: Exit\n";
234
235 // Expected difference after constant folding.
236 diff_t expected_cf_diff = {
237 { " 2: IntConstant [4]\n", " 2: IntConstant\n" },
238 { " 3: IntConstant [4]\n", " 3: IntConstant\n"
239 " 7: IntConstant [5]\n" },
240 { " 4: Add(2, 3) [5]\n", removed },
241 { " 5: Return(4)\n", " 5: Return(7)\n" }
242 };
243 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
244
245 // Check the value of the computed constant.
246 auto check_after_cf = [](HGraph* graph) {
247 HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
248 ASSERT_TRUE(inst->IsIntConstant());
249 ASSERT_EQ(inst->AsIntConstant()->GetValue(), 3);
250 };
251
252 // Expected difference after dead code elimination.
253 diff_t expected_dce_diff = {
254 { " 2: IntConstant\n", removed },
255 { " 3: IntConstant\n", removed }
256 };
257 std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
258
259 TestCode(data,
260 expected_before,
261 expected_after_cf,
262 expected_after_dce,
263 check_after_cf);
264 }
265
266 /**
267 * Small three-register program exercising int constant folding on addition.
268 *
269 * 16-bit
270 * offset
271 * ------
272 * v0 <- 1 0. const/4 v0, #+1
273 * v1 <- 2 1. const/4 v1, #+2
274 * v0 <- v0 + v1 2. add-int/2addr v0, v1
275 * v1 <- 4 3. const/4 v1, #+4
276 * v2 <- 5 4. const/4 v2, #+5
277 * v1 <- v1 + v2 5. add-int/2addr v1, v2
278 * v2 <- v0 + v1 6. add-int v2, v0, v1
279 * return v2 8. return v2
280 */
TEST_F(ConstantFoldingTest,IntConstantFoldingOnAddition2)281 TEST_F(ConstantFoldingTest, IntConstantFoldingOnAddition2) {
282 const std::vector<uint16_t> data = THREE_REGISTERS_CODE_ITEM(
283 Instruction::CONST_4 | 0 << 8 | 1 << 12,
284 Instruction::CONST_4 | 1 << 8 | 2 << 12,
285 Instruction::ADD_INT_2ADDR | 0 << 8 | 1 << 12,
286 Instruction::CONST_4 | 1 << 8 | 4 << 12,
287 Instruction::CONST_4 | 2 << 8 | 5 << 12,
288 Instruction::ADD_INT_2ADDR | 1 << 8 | 2 << 12,
289 Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
290 Instruction::RETURN | 2 << 8);
291
292 std::string expected_before =
293 "BasicBlock 0, succ: 1\n"
294 " 2: IntConstant [4]\n"
295 " 3: IntConstant [4]\n"
296 " 5: IntConstant [7]\n"
297 " 6: IntConstant [7]\n"
298 " 0: SuspendCheck\n"
299 " 1: Goto 1\n"
300 "BasicBlock 1, pred: 0, succ: 2\n"
301 " 4: Add(2, 3) [8]\n"
302 " 7: Add(5, 6) [8]\n"
303 " 8: Add(4, 7) [9]\n"
304 " 9: Return(8)\n"
305 "BasicBlock 2, pred: 1\n"
306 " 10: Exit\n";
307
308 // Expected difference after constant folding.
309 diff_t expected_cf_diff = {
310 { " 2: IntConstant [4]\n", " 2: IntConstant\n" },
311 { " 3: IntConstant [4]\n", " 3: IntConstant\n" },
312 { " 5: IntConstant [7]\n", " 5: IntConstant\n" },
313 { " 6: IntConstant [7]\n", " 6: IntConstant\n"
314 " 11: IntConstant\n"
315 " 12: IntConstant\n"
316 " 13: IntConstant [9]\n" },
317 { " 4: Add(2, 3) [8]\n", removed },
318 { " 7: Add(5, 6) [8]\n", removed },
319 { " 8: Add(4, 7) [9]\n", removed },
320 { " 9: Return(8)\n", " 9: Return(13)\n" }
321 };
322 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
323
324 // Check the values of the computed constants.
325 auto check_after_cf = [](HGraph* graph) {
326 HInstruction* inst1 = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
327 ASSERT_TRUE(inst1->IsIntConstant());
328 ASSERT_EQ(inst1->AsIntConstant()->GetValue(), 12);
329 HInstruction* inst2 = inst1->GetPrevious();
330 ASSERT_TRUE(inst2->IsIntConstant());
331 ASSERT_EQ(inst2->AsIntConstant()->GetValue(), 9);
332 HInstruction* inst3 = inst2->GetPrevious();
333 ASSERT_TRUE(inst3->IsIntConstant());
334 ASSERT_EQ(inst3->AsIntConstant()->GetValue(), 3);
335 };
336
337 // Expected difference after dead code elimination.
338 diff_t expected_dce_diff = {
339 { " 2: IntConstant\n", removed },
340 { " 3: IntConstant\n", removed },
341 { " 5: IntConstant\n", removed },
342 { " 6: IntConstant\n", removed },
343 { " 11: IntConstant\n", removed },
344 { " 12: IntConstant\n", removed }
345 };
346 std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
347
348 TestCode(data,
349 expected_before,
350 expected_after_cf,
351 expected_after_dce,
352 check_after_cf);
353 }
354
355 /**
356 * Tiny three-register program exercising int constant folding on subtraction.
357 *
358 * 16-bit
359 * offset
360 * ------
361 * v0 <- 3 0. const/4 v0, #+3
362 * v1 <- 2 1. const/4 v1, #+2
363 * v2 <- v0 - v1 2. sub-int v2, v0, v1
364 * return v2 4. return v2
365 */
TEST_F(ConstantFoldingTest,IntConstantFoldingOnSubtraction)366 TEST_F(ConstantFoldingTest, IntConstantFoldingOnSubtraction) {
367 const std::vector<uint16_t> data = THREE_REGISTERS_CODE_ITEM(
368 Instruction::CONST_4 | 0 << 8 | 3 << 12,
369 Instruction::CONST_4 | 1 << 8 | 2 << 12,
370 Instruction::SUB_INT | 2 << 8, 0 | 1 << 8,
371 Instruction::RETURN | 2 << 8);
372
373 std::string expected_before =
374 "BasicBlock 0, succ: 1\n"
375 " 2: IntConstant [4]\n"
376 " 3: IntConstant [4]\n"
377 " 0: SuspendCheck\n"
378 " 1: Goto 1\n"
379 "BasicBlock 1, pred: 0, succ: 2\n"
380 " 4: Sub(2, 3) [5]\n"
381 " 5: Return(4)\n"
382 "BasicBlock 2, pred: 1\n"
383 " 6: Exit\n";
384
385 // Expected difference after constant folding.
386 diff_t expected_cf_diff = {
387 { " 2: IntConstant [4]\n", " 2: IntConstant\n" },
388 { " 3: IntConstant [4]\n", " 3: IntConstant\n"
389 " 7: IntConstant [5]\n" },
390 { " 4: Sub(2, 3) [5]\n", removed },
391 { " 5: Return(4)\n", " 5: Return(7)\n" }
392 };
393 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
394
395 // Check the value of the computed constant.
396 auto check_after_cf = [](HGraph* graph) {
397 HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
398 ASSERT_TRUE(inst->IsIntConstant());
399 ASSERT_EQ(inst->AsIntConstant()->GetValue(), 1);
400 };
401
402 // Expected difference after dead code elimination.
403 diff_t expected_dce_diff = {
404 { " 2: IntConstant\n", removed },
405 { " 3: IntConstant\n", removed }
406 };
407 std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
408
409 TestCode(data,
410 expected_before,
411 expected_after_cf,
412 expected_after_dce,
413 check_after_cf);
414 }
415
416 /**
417 * Tiny three-register-pair program exercising long constant folding
418 * on addition.
419 *
420 * 16-bit
421 * offset
422 * ------
423 * (v0, v1) <- 1 0. const-wide/16 v0, #+1
424 * (v2, v3) <- 2 2. const-wide/16 v2, #+2
425 * (v4, v5) <-
426 * (v0, v1) + (v1, v2) 4. add-long v4, v0, v2
427 * return (v4, v5) 6. return-wide v4
428 */
TEST_F(ConstantFoldingTest,LongConstantFoldingOnAddition)429 TEST_F(ConstantFoldingTest, LongConstantFoldingOnAddition) {
430 const std::vector<uint16_t> data = SIX_REGISTERS_CODE_ITEM(
431 Instruction::CONST_WIDE_16 | 0 << 8, 1,
432 Instruction::CONST_WIDE_16 | 2 << 8, 2,
433 Instruction::ADD_LONG | 4 << 8, 0 | 2 << 8,
434 Instruction::RETURN_WIDE | 4 << 8);
435
436 std::string expected_before =
437 "BasicBlock 0, succ: 1\n"
438 " 2: LongConstant [4]\n"
439 " 3: LongConstant [4]\n"
440 " 0: SuspendCheck\n"
441 " 1: Goto 1\n"
442 "BasicBlock 1, pred: 0, succ: 2\n"
443 " 4: Add(2, 3) [5]\n"
444 " 5: Return(4)\n"
445 "BasicBlock 2, pred: 1\n"
446 " 6: Exit\n";
447
448 // Expected difference after constant folding.
449 diff_t expected_cf_diff = {
450 { " 2: LongConstant [4]\n", " 2: LongConstant\n" },
451 { " 3: LongConstant [4]\n", " 3: LongConstant\n"
452 " 7: LongConstant [5]\n" },
453 { " 4: Add(2, 3) [5]\n", removed },
454 { " 5: Return(4)\n", " 5: Return(7)\n" }
455 };
456 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
457
458 // Check the value of the computed constant.
459 auto check_after_cf = [](HGraph* graph) {
460 HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
461 ASSERT_TRUE(inst->IsLongConstant());
462 ASSERT_EQ(inst->AsLongConstant()->GetValue(), 3);
463 };
464
465 // Expected difference after dead code elimination.
466 diff_t expected_dce_diff = {
467 { " 2: LongConstant\n", removed },
468 { " 3: LongConstant\n", removed }
469 };
470 std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
471
472 TestCode(data,
473 expected_before,
474 expected_after_cf,
475 expected_after_dce,
476 check_after_cf,
477 DataType::Type::kInt64);
478 }
479
480 /**
481 * Tiny three-register-pair program exercising long constant folding
482 * on subtraction.
483 *
484 * 16-bit
485 * offset
486 * ------
487 * (v0, v1) <- 3 0. const-wide/16 v0, #+3
488 * (v2, v3) <- 2 2. const-wide/16 v2, #+2
489 * (v4, v5) <-
490 * (v0, v1) - (v1, v2) 4. sub-long v4, v0, v2
491 * return (v4, v5) 6. return-wide v4
492 */
TEST_F(ConstantFoldingTest,LongConstantFoldingOnSubtraction)493 TEST_F(ConstantFoldingTest, LongConstantFoldingOnSubtraction) {
494 const std::vector<uint16_t> data = SIX_REGISTERS_CODE_ITEM(
495 Instruction::CONST_WIDE_16 | 0 << 8, 3,
496 Instruction::CONST_WIDE_16 | 2 << 8, 2,
497 Instruction::SUB_LONG | 4 << 8, 0 | 2 << 8,
498 Instruction::RETURN_WIDE | 4 << 8);
499
500 std::string expected_before =
501 "BasicBlock 0, succ: 1\n"
502 " 2: LongConstant [4]\n"
503 " 3: LongConstant [4]\n"
504 " 0: SuspendCheck\n"
505 " 1: Goto 1\n"
506 "BasicBlock 1, pred: 0, succ: 2\n"
507 " 4: Sub(2, 3) [5]\n"
508 " 5: Return(4)\n"
509 "BasicBlock 2, pred: 1\n"
510 " 6: Exit\n";
511
512 // Expected difference after constant folding.
513 diff_t expected_cf_diff = {
514 { " 2: LongConstant [4]\n", " 2: LongConstant\n" },
515 { " 3: LongConstant [4]\n", " 3: LongConstant\n"
516 " 7: LongConstant [5]\n" },
517 { " 4: Sub(2, 3) [5]\n", removed },
518 { " 5: Return(4)\n", " 5: Return(7)\n" }
519 };
520 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
521
522 // Check the value of the computed constant.
523 auto check_after_cf = [](HGraph* graph) {
524 HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
525 ASSERT_TRUE(inst->IsLongConstant());
526 ASSERT_EQ(inst->AsLongConstant()->GetValue(), 1);
527 };
528
529 // Expected difference after dead code elimination.
530 diff_t expected_dce_diff = {
531 { " 2: LongConstant\n", removed },
532 { " 3: LongConstant\n", removed }
533 };
534 std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
535
536 TestCode(data,
537 expected_before,
538 expected_after_cf,
539 expected_after_dce,
540 check_after_cf,
541 DataType::Type::kInt64);
542 }
543
544 /**
545 * Three-register program with jumps leading to the creation of many
546 * blocks.
547 *
548 * The intent of this test is to ensure that all constant expressions
549 * are actually evaluated at compile-time, thanks to the reverse
550 * (forward) post-order traversal of the dominator tree.
551 *
552 * 16-bit
553 * offset
554 * ------
555 * v0 <- 1 0. const/4 v0, #+1
556 * v1 <- 2 1. const/4 v1, #+2
557 * v2 <- v0 + v1 2. add-int v2, v0, v1
558 * goto L2 4. goto +4
559 * L1: v1 <- v0 + 5 5. add-int/lit16 v1, v0, #+5
560 * goto L3 7. goto +4
561 * L2: v0 <- v2 + 4 8. add-int/lit16 v0, v2, #+4
562 * goto L1 10. goto +(-5)
563 * L3: v2 <- v1 + 8 11. add-int/lit16 v2, v1, #+8
564 * return v2 13. return v2
565 */
TEST_F(ConstantFoldingTest,IntConstantFoldingAndJumps)566 TEST_F(ConstantFoldingTest, IntConstantFoldingAndJumps) {
567 const std::vector<uint16_t> data = THREE_REGISTERS_CODE_ITEM(
568 Instruction::CONST_4 | 0 << 8 | 1 << 12,
569 Instruction::CONST_4 | 1 << 8 | 2 << 12,
570 Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
571 Instruction::GOTO | 4 << 8,
572 Instruction::ADD_INT_LIT16 | 1 << 8 | 0 << 12, 5,
573 Instruction::GOTO | 4 << 8,
574 Instruction::ADD_INT_LIT16 | 0 << 8 | 2 << 12, 4,
575 static_cast<uint16_t>(Instruction::GOTO | 0xFFFFFFFB << 8),
576 Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 8,
577 Instruction::RETURN | 2 << 8);
578
579 std::string expected_before =
580 "BasicBlock 0, succ: 1\n"
581 " 2: IntConstant [4]\n" // v0 <- 1
582 " 3: IntConstant [4]\n" // v1 <- 2
583 " 6: IntConstant [7]\n" // const 5
584 " 9: IntConstant [10]\n" // const 4
585 " 12: IntConstant [13]\n" // const 8
586 " 0: SuspendCheck\n"
587 " 1: Goto 1\n"
588 "BasicBlock 1, pred: 0, succ: 3\n"
589 " 4: Add(2, 3) [7]\n" // v2 <- v0 + v1 = 1 + 2 = 3
590 " 5: Goto 3\n" // goto L2
591 "BasicBlock 2, pred: 3, succ: 4\n" // L1:
592 " 10: Add(7, 9) [13]\n" // v1 <- v0 + 3 = 7 + 5 = 12
593 " 11: Goto 4\n" // goto L3
594 "BasicBlock 3, pred: 1, succ: 2\n" // L2:
595 " 7: Add(4, 6) [10]\n" // v0 <- v2 + 2 = 3 + 4 = 7
596 " 8: Goto 2\n" // goto L1
597 "BasicBlock 4, pred: 2, succ: 5\n" // L3:
598 " 13: Add(10, 12) [14]\n" // v2 <- v1 + 4 = 12 + 8 = 20
599 " 14: Return(13)\n" // return v2
600 "BasicBlock 5, pred: 4\n"
601 " 15: Exit\n";
602
603 // Expected difference after constant folding.
604 diff_t expected_cf_diff = {
605 { " 2: IntConstant [4]\n", " 2: IntConstant\n" },
606 { " 3: IntConstant [4]\n", " 3: IntConstant\n" },
607 { " 6: IntConstant [7]\n", " 6: IntConstant\n" },
608 { " 9: IntConstant [10]\n", " 9: IntConstant\n" },
609 { " 12: IntConstant [13]\n", " 12: IntConstant\n"
610 " 16: IntConstant\n"
611 " 17: IntConstant\n"
612 " 18: IntConstant\n"
613 " 19: IntConstant [14]\n" },
614 { " 4: Add(2, 3) [7]\n", removed },
615 { " 10: Add(7, 9) [13]\n", removed },
616 { " 7: Add(4, 6) [10]\n", removed },
617 { " 13: Add(10, 12) [14]\n", removed },
618 { " 14: Return(13)\n", " 14: Return(19)\n"}
619 };
620 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
621
622 // Check the values of the computed constants.
623 auto check_after_cf = [](HGraph* graph) {
624 HInstruction* inst1 = graph->GetBlocks()[4]->GetFirstInstruction()->InputAt(0);
625 ASSERT_TRUE(inst1->IsIntConstant());
626 ASSERT_EQ(inst1->AsIntConstant()->GetValue(), 20);
627 HInstruction* inst2 = inst1->GetPrevious();
628 ASSERT_TRUE(inst2->IsIntConstant());
629 ASSERT_EQ(inst2->AsIntConstant()->GetValue(), 12);
630 HInstruction* inst3 = inst2->GetPrevious();
631 ASSERT_TRUE(inst3->IsIntConstant());
632 ASSERT_EQ(inst3->AsIntConstant()->GetValue(), 7);
633 HInstruction* inst4 = inst3->GetPrevious();
634 ASSERT_TRUE(inst4->IsIntConstant());
635 ASSERT_EQ(inst4->AsIntConstant()->GetValue(), 3);
636 };
637
638 // Expected difference after dead code elimination.
639 std::string expected_after_dce =
640 "BasicBlock 0, succ: 1\n"
641 " 19: IntConstant [14]\n"
642 " 0: SuspendCheck\n"
643 " 1: Goto 1\n"
644 "BasicBlock 1, pred: 0, succ: 5\n"
645 " 14: Return(19)\n"
646 "BasicBlock 5, pred: 1\n"
647 " 15: Exit\n";
648
649 TestCode(data,
650 expected_before,
651 expected_after_cf,
652 expected_after_dce,
653 check_after_cf);
654 }
655
656 /**
657 * Three-register program with a constant (static) condition.
658 *
659 * 16-bit
660 * offset
661 * ------
662 * v1 <- 1 0. const/4 v1, #+1
663 * v0 <- 0 1. const/4 v0, #+0
664 * if v1 >= 0 goto L1 2. if-gez v1, +3
665 * v0 <- v1 4. move v0, v1
666 * L1: v2 <- v0 + v1 5. add-int v2, v0, v1
667 * return-void 7. return
668 */
TEST_F(ConstantFoldingTest,ConstantCondition)669 TEST_F(ConstantFoldingTest, ConstantCondition) {
670 const std::vector<uint16_t> data = THREE_REGISTERS_CODE_ITEM(
671 Instruction::CONST_4 | 1 << 8 | 1 << 12,
672 Instruction::CONST_4 | 0 << 8 | 0 << 12,
673 Instruction::IF_GEZ | 1 << 8, 3,
674 Instruction::MOVE | 0 << 8 | 1 << 12,
675 Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
676 Instruction::RETURN_VOID);
677
678 std::string expected_before =
679 "BasicBlock 0, succ: 1\n"
680 " 3: IntConstant [9, 8, 5]\n"
681 " 4: IntConstant [8, 5]\n"
682 " 1: SuspendCheck\n"
683 " 2: Goto 1\n"
684 "BasicBlock 1, pred: 0, succ: 5, 2\n"
685 " 5: GreaterThanOrEqual(3, 4) [6]\n"
686 " 6: If(5)\n"
687 "BasicBlock 2, pred: 1, succ: 3\n"
688 " 7: Goto 3\n"
689 "BasicBlock 3, pred: 5, 2, succ: 4\n"
690 " 8: Phi(4, 3) [9]\n"
691 " 9: Add(8, 3)\n"
692 " 10: ReturnVoid\n"
693 "BasicBlock 4, pred: 3\n"
694 " 11: Exit\n"
695 "BasicBlock 5, pred: 1, succ: 3\n"
696 " 0: Goto 3\n";
697
698 // Expected difference after constant folding.
699 diff_t expected_cf_diff = {
700 { " 3: IntConstant [9, 8, 5]\n", " 3: IntConstant [6, 9, 8]\n" },
701 { " 4: IntConstant [8, 5]\n", " 4: IntConstant [8]\n" },
702 { " 5: GreaterThanOrEqual(3, 4) [6]\n", removed },
703 { " 6: If(5)\n", " 6: If(3)\n" }
704 };
705 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
706
707 // Check the values of the computed constants.
708 auto check_after_cf = [](HGraph* graph) {
709 HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
710 ASSERT_TRUE(inst->IsIntConstant());
711 ASSERT_EQ(inst->AsIntConstant()->GetValue(), 1);
712 };
713
714 // Expected graph after dead code elimination.
715 std::string expected_after_dce =
716 "BasicBlock 0, succ: 1\n"
717 " 1: SuspendCheck\n"
718 " 2: Goto 1\n"
719 "BasicBlock 1, pred: 0, succ: 4\n"
720 " 10: ReturnVoid\n"
721 "BasicBlock 4, pred: 1\n"
722 " 11: Exit\n";
723
724 TestCode(data,
725 expected_before,
726 expected_after_cf,
727 expected_after_dce,
728 check_after_cf);
729 }
730
731 /**
732 * Unsigned comparisons with zero. Since these instructions are not present
733 * in the bytecode, we need to set up the graph explicitly.
734 */
TEST_F(ConstantFoldingTest,UnsignedComparisonsWithZero)735 TEST_F(ConstantFoldingTest, UnsignedComparisonsWithZero) {
736 HBasicBlock* block = InitEntryMainExitGraph();
737
738 // Make various unsigned comparisons with zero against a parameter.
739 HInstruction* parameter = MakeParam(DataType::Type::kInt32);
740 HInstruction* zero = graph_->GetIntConstant(0);
741
742 HInstruction* a1 = MakeCondition(block, kCondA, zero, parameter);
743 MakeSelect(block, a1, parameter, parameter);
744 HInstruction* a2 = MakeCondition(block, kCondA, parameter, zero);
745 MakeSelect(block, a2, parameter, parameter);
746 HInstruction* ae1 = MakeCondition(block, kCondAE, zero, parameter);
747 MakeSelect(block, ae1, parameter, parameter);
748 HInstruction* ae2 = MakeCondition(block, kCondAE, parameter, zero);
749 MakeSelect(block, ae2, parameter, parameter);
750 HInstruction* b1 = MakeCondition(block, kCondB, zero, parameter);
751 MakeSelect(block, b1, parameter, parameter);
752 HInstruction* b2 = MakeCondition(block, kCondB, parameter, zero);
753 MakeSelect(block, b2, parameter, parameter);
754 HInstruction* be1 = MakeCondition(block, kCondBE, zero, parameter);
755 MakeSelect(block, be1, parameter, parameter);
756 HInstruction* be2 = MakeCondition(block, kCondBE, parameter, zero);
757 MakeSelect(block, be2, parameter, parameter);
758 MakeReturn(block, zero);
759
760 graph_->BuildDominatorTree();
761
762 const std::string expected_before =
763 "BasicBlock 0, succ: 1\n"
764 " 2: ParameterValue [19, 19, 18, 17, 17, 16, 15, 15, 14, 13, 13, 12, 11, 11, 10, "
765 "9, 9, 8, 7, 7, 6, 5, 5, 4]\n"
766 " 3: IntConstant [20, 18, 16, 14, 12, 10, 8, 6, 4]\n"
767 " 0: Goto 1\n"
768 "BasicBlock 1, pred: 0, succ: 2\n"
769 " 4: Above(3, 2) [5]\n"
770 " 5: Select(2, 2, 4)\n"
771 " 6: Above(2, 3) [7]\n"
772 " 7: Select(2, 2, 6)\n"
773 " 8: AboveOrEqual(3, 2) [9]\n"
774 " 9: Select(2, 2, 8)\n"
775 " 10: AboveOrEqual(2, 3) [11]\n"
776 " 11: Select(2, 2, 10)\n"
777 " 12: Below(3, 2) [13]\n"
778 " 13: Select(2, 2, 12)\n"
779 " 14: Below(2, 3) [15]\n"
780 " 15: Select(2, 2, 14)\n"
781 " 16: BelowOrEqual(3, 2) [17]\n"
782 " 17: Select(2, 2, 16)\n"
783 " 18: BelowOrEqual(2, 3) [19]\n"
784 " 19: Select(2, 2, 18)\n"
785 " 20: Return(3)\n"
786 "BasicBlock 2, pred: 1\n"
787 " 1: Exit\n";
788
789 const std::string expected_after_cf =
790 "BasicBlock 0, succ: 1\n"
791 " 2: ParameterValue [19, 19, 18, 17, 17, 15, 15, 13, 13, 12, 11, 11, "
792 "9, 9, 8, 7, 7, 6, 5, 5]\n"
793 " 3: IntConstant [15, 5, 20, 18, 12, 8, 6]\n"
794 " 21: IntConstant [17, 11]\n"
795 " 0: Goto 1\n"
796 "BasicBlock 1, pred: 0, succ: 2\n"
797 " 5: Select(2, 2, 3)\n"
798 " 6: Above(2, 3) [7]\n"
799 " 7: Select(2, 2, 6)\n"
800 " 8: AboveOrEqual(3, 2) [9]\n"
801 " 9: Select(2, 2, 8)\n"
802 " 11: Select(2, 2, 21)\n"
803 " 12: Below(3, 2) [13]\n"
804 " 13: Select(2, 2, 12)\n"
805 " 15: Select(2, 2, 3)\n"
806 " 17: Select(2, 2, 21)\n"
807 " 18: BelowOrEqual(2, 3) [19]\n"
808 " 19: Select(2, 2, 18)\n"
809 " 20: Return(3)\n"
810 "BasicBlock 2, pred: 1\n"
811 " 1: Exit\n";
812
813 const std::string expected_after_dce =
814 "BasicBlock 0, succ: 1\n"
815 " 2: ParameterValue\n"
816 " 3: IntConstant [20]\n"
817 " 0: Goto 1\n"
818 "BasicBlock 1, pred: 0, succ: 2\n"
819 " 20: Return(3)\n"
820 "BasicBlock 2, pred: 1\n"
821 " 1: Exit\n";
822
823 auto check_after_cf = [](HGraph* graph) {
824 CHECK(graph != nullptr);
825 };
826
827 TestCodeOnReadyGraph(expected_before,
828 expected_after_cf,
829 expected_after_dce,
830 check_after_cf);
831 }
832
833 } // namespace art
834