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