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 #include "dead_code_elimination.h"
21 #include "driver/compiler_options.h"
22 #include "graph_checker.h"
23 #include "optimizing_unit_test.h"
24 #include "pretty_printer.h"
25
26 #include "gtest/gtest.h"
27
28 namespace art {
29
30 /**
31 * Fixture class for the constant folding and dce tests.
32 */
33 class ConstantFoldingTest : public OptimizingUnitTest {
34 public:
ConstantFoldingTest()35 ConstantFoldingTest() : graph_(nullptr) { }
36
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)37 void TestCode(const std::vector<uint16_t>& data,
38 const std::string& expected_before,
39 const std::string& expected_after_cf,
40 const std::string& expected_after_dce,
41 const std::function<void(HGraph*)>& check_after_cf,
42 DataType::Type return_type = DataType::Type::kInt32) {
43 graph_ = CreateCFG(data, return_type);
44 TestCodeOnReadyGraph(expected_before,
45 expected_after_cf,
46 expected_after_dce,
47 check_after_cf);
48 }
49
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)50 void TestCodeOnReadyGraph(const std::string& expected_before,
51 const std::string& expected_after_cf,
52 const std::string& expected_after_dce,
53 const std::function<void(HGraph*)>& check_after_cf) {
54 ASSERT_NE(graph_, nullptr);
55
56 StringPrettyPrinter printer_before(graph_);
57 printer_before.VisitInsertionOrder();
58 std::string actual_before = printer_before.str();
59 EXPECT_EQ(expected_before, actual_before);
60
61 HConstantFolding(graph_, "constant_folding").Run();
62 GraphChecker graph_checker_cf(graph_);
63 graph_checker_cf.Run();
64 ASSERT_TRUE(graph_checker_cf.IsValid());
65
66 StringPrettyPrinter printer_after_cf(graph_);
67 printer_after_cf.VisitInsertionOrder();
68 std::string actual_after_cf = printer_after_cf.str();
69 EXPECT_EQ(expected_after_cf, actual_after_cf);
70
71 check_after_cf(graph_);
72
73 HDeadCodeElimination(graph_, /* stats= */ nullptr, "dead_code_elimination").Run();
74 GraphChecker graph_checker_dce(graph_);
75 graph_checker_dce.Run();
76 ASSERT_TRUE(graph_checker_dce.IsValid());
77
78 StringPrettyPrinter printer_after_dce(graph_);
79 printer_after_dce.VisitInsertionOrder();
80 std::string actual_after_dce = printer_after_dce.str();
81 EXPECT_EQ(expected_after_dce, actual_after_dce);
82 }
83
84 HGraph* graph_;
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 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 graph_ = CreateGraph();
737 HBasicBlock* entry_block = new (GetAllocator()) HBasicBlock(graph_);
738 graph_->AddBlock(entry_block);
739 graph_->SetEntryBlock(entry_block);
740 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_);
741 graph_->AddBlock(block);
742 HBasicBlock* exit_block = new (GetAllocator()) HBasicBlock(graph_);
743 graph_->AddBlock(exit_block);
744 graph_->SetExitBlock(exit_block);
745 entry_block->AddSuccessor(block);
746 block->AddSuccessor(exit_block);
747
748 // Make various unsigned comparisons with zero against a parameter.
749 HInstruction* parameter = new (GetAllocator()) HParameterValue(
750 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kInt32, true);
751 entry_block->AddInstruction(parameter);
752 entry_block->AddInstruction(new (GetAllocator()) HGoto());
753
754 HInstruction* zero = graph_->GetIntConstant(0);
755
756 HInstruction* last;
757 block->AddInstruction(last = new (GetAllocator()) HAbove(zero, parameter));
758 block->AddInstruction(new (GetAllocator()) HSelect(last, parameter, parameter, 0));
759 block->AddInstruction(last = new (GetAllocator()) HAbove(parameter, zero));
760 block->AddInstruction(new (GetAllocator()) HSelect(last, parameter, parameter, 0));
761 block->AddInstruction(last = new (GetAllocator()) HAboveOrEqual(zero, parameter));
762 block->AddInstruction(new (GetAllocator()) HSelect(last, parameter, parameter, 0));
763 block->AddInstruction(last = new (GetAllocator()) HAboveOrEqual(parameter, zero));
764 block->AddInstruction(new (GetAllocator()) HSelect(last, parameter, parameter, 0));
765 block->AddInstruction(last = new (GetAllocator()) HBelow(zero, parameter));
766 block->AddInstruction(new (GetAllocator()) HSelect(last, parameter, parameter, 0));
767 block->AddInstruction(last = new (GetAllocator()) HBelow(parameter, zero));
768 block->AddInstruction(new (GetAllocator()) HSelect(last, parameter, parameter, 0));
769 block->AddInstruction(last = new (GetAllocator()) HBelowOrEqual(zero, parameter));
770 block->AddInstruction(new (GetAllocator()) HSelect(last, parameter, parameter, 0));
771 block->AddInstruction(last = new (GetAllocator()) HBelowOrEqual(parameter, zero));
772 block->AddInstruction(new (GetAllocator()) HSelect(last, parameter, parameter, 0));
773 block->AddInstruction(new (GetAllocator()) HReturn(zero));
774
775 exit_block->AddInstruction(new (GetAllocator()) HExit());
776
777 graph_->BuildDominatorTree();
778
779 const std::string expected_before =
780 "BasicBlock 0, succ: 1\n"
781 " 0: ParameterValue [18, 18, 17, 16, 16, 15, 14, 14, 13, 12, 12, 11, 10, 10, 9, "
782 "8, 8, 7, 6, 6, 5, 4, 4, 3]\n"
783 " 2: IntConstant [19, 17, 15, 13, 11, 9, 7, 5, 3]\n"
784 " 1: Goto 1\n"
785 "BasicBlock 1, pred: 0, succ: 2\n"
786 " 3: Above(2, 0) [4]\n"
787 " 4: Select(0, 0, 3)\n"
788 " 5: Above(0, 2) [6]\n"
789 " 6: Select(0, 0, 5)\n"
790 " 7: AboveOrEqual(2, 0) [8]\n"
791 " 8: Select(0, 0, 7)\n"
792 " 9: AboveOrEqual(0, 2) [10]\n"
793 " 10: Select(0, 0, 9)\n"
794 " 11: Below(2, 0) [12]\n"
795 " 12: Select(0, 0, 11)\n"
796 " 13: Below(0, 2) [14]\n"
797 " 14: Select(0, 0, 13)\n"
798 " 15: BelowOrEqual(2, 0) [16]\n"
799 " 16: Select(0, 0, 15)\n"
800 " 17: BelowOrEqual(0, 2) [18]\n"
801 " 18: Select(0, 0, 17)\n"
802 " 19: Return(2)\n"
803 "BasicBlock 2, pred: 1\n"
804 " 20: Exit\n";
805
806 const std::string expected_after_cf =
807 "BasicBlock 0, succ: 1\n"
808 " 0: ParameterValue [18, 18, 17, 16, 16, 14, 14, 12, 12, 11, 10, 10, "
809 "8, 8, 7, 6, 6, 5, 4, 4]\n"
810 " 2: IntConstant [14, 4, 19, 17, 11, 7, 5]\n"
811 " 21: IntConstant [16, 10]\n"
812 " 1: Goto 1\n"
813 "BasicBlock 1, pred: 0, succ: 2\n"
814 " 4: Select(0, 0, 2)\n"
815 " 5: Above(0, 2) [6]\n"
816 " 6: Select(0, 0, 5)\n"
817 " 7: AboveOrEqual(2, 0) [8]\n"
818 " 8: Select(0, 0, 7)\n"
819 " 10: Select(0, 0, 21)\n"
820 " 11: Below(2, 0) [12]\n"
821 " 12: Select(0, 0, 11)\n"
822 " 14: Select(0, 0, 2)\n"
823 " 16: Select(0, 0, 21)\n"
824 " 17: BelowOrEqual(0, 2) [18]\n"
825 " 18: Select(0, 0, 17)\n"
826 " 19: Return(2)\n"
827 "BasicBlock 2, pred: 1\n"
828 " 20: Exit\n";
829
830 const std::string expected_after_dce =
831 "BasicBlock 0, succ: 1\n"
832 " 0: ParameterValue\n"
833 " 2: IntConstant [19]\n"
834 " 1: Goto 1\n"
835 "BasicBlock 1, pred: 0, succ: 2\n"
836 " 19: Return(2)\n"
837 "BasicBlock 2, pred: 1\n"
838 " 20: Exit\n";
839
840 auto check_after_cf = [](HGraph* graph) {
841 CHECK(graph != nullptr);
842 };
843
844 TestCodeOnReadyGraph(expected_before,
845 expected_after_cf,
846 expected_after_dce,
847 check_after_cf);
848 }
849
850 } // namespace art
851