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
TestCode(const uint16_t * data,const std::string & expected_before,const std::string & expected_after_cf,const std::string & expected_after_dce,std::function<void (HGraph *)> check_after_cf,Primitive::Type return_type=Primitive::kPrimInt)32 static void TestCode(const uint16_t* data,
33 const std::string& expected_before,
34 const std::string& expected_after_cf,
35 const std::string& expected_after_dce,
36 std::function<void(HGraph*)> check_after_cf,
37 Primitive::Type return_type = Primitive::kPrimInt) {
38 ArenaPool pool;
39 ArenaAllocator allocator(&pool);
40 HGraph* graph = CreateCFG(&allocator, data, return_type);
41 ASSERT_NE(graph, nullptr);
42
43 graph->TryBuildingSsa();
44
45 StringPrettyPrinter printer_before(graph);
46 printer_before.VisitInsertionOrder();
47 std::string actual_before = printer_before.str();
48 ASSERT_EQ(expected_before, actual_before);
49
50 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
51 X86InstructionSetFeatures::FromCppDefines());
52 x86::CodeGeneratorX86 codegenX86(graph, *features_x86.get(), CompilerOptions());
53 HConstantFolding(graph).Run();
54 SSAChecker ssa_checker_cf(&allocator, graph);
55 ssa_checker_cf.Run();
56 ASSERT_TRUE(ssa_checker_cf.IsValid());
57
58 StringPrettyPrinter printer_after_cf(graph);
59 printer_after_cf.VisitInsertionOrder();
60 std::string actual_after_cf = printer_after_cf.str();
61 ASSERT_EQ(expected_after_cf, actual_after_cf);
62
63 check_after_cf(graph);
64
65 HDeadCodeElimination(graph).Run();
66 SSAChecker ssa_checker_dce(&allocator, graph);
67 ssa_checker_dce.Run();
68 ASSERT_TRUE(ssa_checker_dce.IsValid());
69
70 StringPrettyPrinter printer_after_dce(graph);
71 printer_after_dce.VisitInsertionOrder();
72 std::string actual_after_dce = printer_after_dce.str();
73 ASSERT_EQ(expected_after_dce, actual_after_dce);
74 }
75
76
77 /**
78 * Tiny three-register program exercising int constant folding on negation.
79 *
80 * 16-bit
81 * offset
82 * ------
83 * v0 <- 1 0. const/4 v0, #+1
84 * v1 <- -v0 1. neg-int v0, v1
85 * return v1 2. return v1
86 */
TEST(ConstantFolding,IntConstantFoldingNegation)87 TEST(ConstantFolding, IntConstantFoldingNegation) {
88 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
89 Instruction::CONST_4 | 0 << 8 | 1 << 12,
90 Instruction::NEG_INT | 1 << 8 | 0 << 12,
91 Instruction::RETURN | 1 << 8);
92
93 std::string expected_before =
94 "BasicBlock 0, succ: 1\n"
95 " 2: IntConstant [5]\n"
96 " 10: SuspendCheck\n"
97 " 11: Goto 1\n"
98 "BasicBlock 1, pred: 0, succ: 2\n"
99 " 5: Neg(2) [8]\n"
100 " 8: Return(5)\n"
101 "BasicBlock 2, pred: 1\n"
102 " 9: Exit\n";
103
104 // Expected difference after constant folding.
105 diff_t expected_cf_diff = {
106 { " 2: IntConstant [5]\n", " 2: IntConstant\n" },
107 { " 10: SuspendCheck\n", " 10: SuspendCheck\n"
108 " 12: IntConstant [8]\n" },
109 { " 5: Neg(2) [8]\n", removed },
110 { " 8: Return(5)\n", " 8: Return(12)\n" }
111 };
112 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
113
114 // Check the value of the computed constant.
115 auto check_after_cf = [](HGraph* graph) {
116 HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
117 ASSERT_TRUE(inst->IsIntConstant());
118 ASSERT_EQ(inst->AsIntConstant()->GetValue(), -1);
119 };
120
121 // Expected difference after dead code elimination.
122 diff_t expected_dce_diff = {
123 { " 2: IntConstant\n", removed },
124 };
125 std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
126
127 TestCode(data,
128 expected_before,
129 expected_after_cf,
130 expected_after_dce,
131 check_after_cf);
132 }
133
134 /**
135 * Tiny three-register program exercising int constant folding on addition.
136 *
137 * 16-bit
138 * offset
139 * ------
140 * v0 <- 1 0. const/4 v0, #+1
141 * v1 <- 2 1. const/4 v1, #+2
142 * v2 <- v0 + v1 2. add-int v2, v0, v1
143 * return v2 4. return v2
144 */
TEST(ConstantFolding,IntConstantFoldingOnAddition1)145 TEST(ConstantFolding, IntConstantFoldingOnAddition1) {
146 const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
147 Instruction::CONST_4 | 0 << 8 | 1 << 12,
148 Instruction::CONST_4 | 1 << 8 | 2 << 12,
149 Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
150 Instruction::RETURN | 2 << 8);
151
152 std::string expected_before =
153 "BasicBlock 0, succ: 1\n"
154 " 3: IntConstant [9]\n"
155 " 5: IntConstant [9]\n"
156 " 14: SuspendCheck\n"
157 " 15: Goto 1\n"
158 "BasicBlock 1, pred: 0, succ: 2\n"
159 " 9: Add(3, 5) [12]\n"
160 " 12: Return(9)\n"
161 "BasicBlock 2, pred: 1\n"
162 " 13: Exit\n";
163
164 // Expected difference after constant folding.
165 diff_t expected_cf_diff = {
166 { " 3: IntConstant [9]\n", " 3: IntConstant\n" },
167 { " 5: IntConstant [9]\n", " 5: IntConstant\n" },
168 { " 14: SuspendCheck\n", " 14: SuspendCheck\n"
169 " 16: IntConstant [12]\n" },
170 { " 9: Add(3, 5) [12]\n", removed },
171 { " 12: Return(9)\n", " 12: Return(16)\n" }
172 };
173 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
174
175 // Check the value of the computed constant.
176 auto check_after_cf = [](HGraph* graph) {
177 HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
178 ASSERT_TRUE(inst->IsIntConstant());
179 ASSERT_EQ(inst->AsIntConstant()->GetValue(), 3);
180 };
181
182 // Expected difference after dead code elimination.
183 diff_t expected_dce_diff = {
184 { " 3: IntConstant\n", removed },
185 { " 5: IntConstant\n", removed }
186 };
187 std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
188
189 TestCode(data,
190 expected_before,
191 expected_after_cf,
192 expected_after_dce,
193 check_after_cf);
194 }
195
196 /**
197 * Small three-register program exercising int constant folding on addition.
198 *
199 * 16-bit
200 * offset
201 * ------
202 * v0 <- 1 0. const/4 v0, #+1
203 * v1 <- 2 1. const/4 v1, #+2
204 * v0 <- v0 + v1 2. add-int/2addr v0, v1
205 * v1 <- 4 3. const/4 v1, #+4
206 * v2 <- 5 4. const/4 v2, #+5
207 * v1 <- v1 + v2 5. add-int/2addr v1, v2
208 * v2 <- v0 + v1 6. add-int v2, v0, v1
209 * return v2 8. return v2
210 */
TEST(ConstantFolding,IntConstantFoldingOnAddition2)211 TEST(ConstantFolding, IntConstantFoldingOnAddition2) {
212 const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
213 Instruction::CONST_4 | 0 << 8 | 1 << 12,
214 Instruction::CONST_4 | 1 << 8 | 2 << 12,
215 Instruction::ADD_INT_2ADDR | 0 << 8 | 1 << 12,
216 Instruction::CONST_4 | 1 << 8 | 4 << 12,
217 Instruction::CONST_4 | 2 << 8 | 5 << 12,
218 Instruction::ADD_INT_2ADDR | 1 << 8 | 2 << 12,
219 Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
220 Instruction::RETURN | 2 << 8);
221
222 std::string expected_before =
223 "BasicBlock 0, succ: 1\n"
224 " 3: IntConstant [9]\n"
225 " 5: IntConstant [9]\n"
226 " 11: IntConstant [17]\n"
227 " 13: IntConstant [17]\n"
228 " 26: SuspendCheck\n"
229 " 27: Goto 1\n"
230 "BasicBlock 1, pred: 0, succ: 2\n"
231 " 9: Add(3, 5) [21]\n"
232 " 17: Add(11, 13) [21]\n"
233 " 21: Add(9, 17) [24]\n"
234 " 24: Return(21)\n"
235 "BasicBlock 2, pred: 1\n"
236 " 25: Exit\n";
237
238 // Expected difference after constant folding.
239 diff_t expected_cf_diff = {
240 { " 3: IntConstant [9]\n", " 3: IntConstant\n" },
241 { " 5: IntConstant [9]\n", " 5: IntConstant\n" },
242 { " 11: IntConstant [17]\n", " 11: IntConstant\n" },
243 { " 13: IntConstant [17]\n", " 13: IntConstant\n" },
244 { " 26: SuspendCheck\n", " 26: SuspendCheck\n"
245 " 28: IntConstant\n"
246 " 29: IntConstant\n"
247 " 30: IntConstant [24]\n" },
248 { " 9: Add(3, 5) [21]\n", removed },
249 { " 17: Add(11, 13) [21]\n", removed },
250 { " 21: Add(9, 17) [24]\n", removed },
251 { " 24: Return(21)\n", " 24: Return(30)\n" }
252 };
253 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
254
255 // Check the values of the computed constants.
256 auto check_after_cf = [](HGraph* graph) {
257 HInstruction* inst1 = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
258 ASSERT_TRUE(inst1->IsIntConstant());
259 ASSERT_EQ(inst1->AsIntConstant()->GetValue(), 12);
260 HInstruction* inst2 = inst1->GetPrevious();
261 ASSERT_TRUE(inst2->IsIntConstant());
262 ASSERT_EQ(inst2->AsIntConstant()->GetValue(), 9);
263 HInstruction* inst3 = inst2->GetPrevious();
264 ASSERT_TRUE(inst3->IsIntConstant());
265 ASSERT_EQ(inst3->AsIntConstant()->GetValue(), 3);
266 };
267
268 // Expected difference after dead code elimination.
269 diff_t expected_dce_diff = {
270 { " 3: IntConstant\n", removed },
271 { " 5: IntConstant\n", removed },
272 { " 11: IntConstant\n", removed },
273 { " 13: IntConstant\n", removed },
274 { " 28: IntConstant\n", removed },
275 { " 29: IntConstant\n", removed }
276 };
277 std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
278
279 TestCode(data,
280 expected_before,
281 expected_after_cf,
282 expected_after_dce,
283 check_after_cf);
284 }
285
286 /**
287 * Tiny three-register program exercising int constant folding on subtraction.
288 *
289 * 16-bit
290 * offset
291 * ------
292 * v0 <- 3 0. const/4 v0, #+3
293 * v1 <- 2 1. const/4 v1, #+2
294 * v2 <- v0 - v1 2. sub-int v2, v0, v1
295 * return v2 4. return v2
296 */
TEST(ConstantFolding,IntConstantFoldingOnSubtraction)297 TEST(ConstantFolding, IntConstantFoldingOnSubtraction) {
298 const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
299 Instruction::CONST_4 | 0 << 8 | 3 << 12,
300 Instruction::CONST_4 | 1 << 8 | 2 << 12,
301 Instruction::SUB_INT | 2 << 8, 0 | 1 << 8,
302 Instruction::RETURN | 2 << 8);
303
304 std::string expected_before =
305 "BasicBlock 0, succ: 1\n"
306 " 3: IntConstant [9]\n"
307 " 5: IntConstant [9]\n"
308 " 14: SuspendCheck\n"
309 " 15: Goto 1\n"
310 "BasicBlock 1, pred: 0, succ: 2\n"
311 " 9: Sub(3, 5) [12]\n"
312 " 12: Return(9)\n"
313 "BasicBlock 2, pred: 1\n"
314 " 13: Exit\n";
315
316 // Expected difference after constant folding.
317 diff_t expected_cf_diff = {
318 { " 3: IntConstant [9]\n", " 3: IntConstant\n" },
319 { " 5: IntConstant [9]\n", " 5: IntConstant\n" },
320 { " 14: SuspendCheck\n", " 14: SuspendCheck\n"
321 " 16: IntConstant [12]\n" },
322 { " 9: Sub(3, 5) [12]\n", removed },
323 { " 12: Return(9)\n", " 12: Return(16)\n" }
324 };
325 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
326
327 // Check the value of the computed constant.
328 auto check_after_cf = [](HGraph* graph) {
329 HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
330 ASSERT_TRUE(inst->IsIntConstant());
331 ASSERT_EQ(inst->AsIntConstant()->GetValue(), 1);
332 };
333
334 // Expected difference after dead code elimination.
335 diff_t expected_dce_diff = {
336 { " 3: IntConstant\n", removed },
337 { " 5: IntConstant\n", removed }
338 };
339 std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
340
341 TestCode(data,
342 expected_before,
343 expected_after_cf,
344 expected_after_dce,
345 check_after_cf);
346 }
347
348 /**
349 * Tiny three-register-pair program exercising long constant folding
350 * on addition.
351 *
352 * 16-bit
353 * offset
354 * ------
355 * (v0, v1) <- 1 0. const-wide/16 v0, #+1
356 * (v2, v3) <- 2 2. const-wide/16 v2, #+2
357 * (v4, v5) <-
358 * (v0, v1) + (v1, v2) 4. add-long v4, v0, v2
359 * return (v4, v5) 6. return-wide v4
360 */
TEST(ConstantFolding,LongConstantFoldingOnAddition)361 TEST(ConstantFolding, LongConstantFoldingOnAddition) {
362 const uint16_t data[] = SIX_REGISTERS_CODE_ITEM(
363 Instruction::CONST_WIDE_16 | 0 << 8, 1,
364 Instruction::CONST_WIDE_16 | 2 << 8, 2,
365 Instruction::ADD_LONG | 4 << 8, 0 | 2 << 8,
366 Instruction::RETURN_WIDE | 4 << 8);
367
368 std::string expected_before =
369 "BasicBlock 0, succ: 1\n"
370 " 6: LongConstant [12]\n"
371 " 8: LongConstant [12]\n"
372 " 17: SuspendCheck\n"
373 " 18: Goto 1\n"
374 "BasicBlock 1, pred: 0, succ: 2\n"
375 " 12: Add(6, 8) [15]\n"
376 " 15: Return(12)\n"
377 "BasicBlock 2, pred: 1\n"
378 " 16: Exit\n";
379
380 // Expected difference after constant folding.
381 diff_t expected_cf_diff = {
382 { " 6: LongConstant [12]\n", " 6: LongConstant\n" },
383 { " 8: LongConstant [12]\n", " 8: LongConstant\n" },
384 { " 17: SuspendCheck\n", " 17: SuspendCheck\n"
385 " 19: LongConstant [15]\n" },
386 { " 12: Add(6, 8) [15]\n", removed },
387 { " 15: Return(12)\n", " 15: Return(19)\n" }
388 };
389 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
390
391 // Check the value of the computed constant.
392 auto check_after_cf = [](HGraph* graph) {
393 HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
394 ASSERT_TRUE(inst->IsLongConstant());
395 ASSERT_EQ(inst->AsLongConstant()->GetValue(), 3);
396 };
397
398 // Expected difference after dead code elimination.
399 diff_t expected_dce_diff = {
400 { " 6: LongConstant\n", removed },
401 { " 8: LongConstant\n", removed }
402 };
403 std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
404
405 TestCode(data,
406 expected_before,
407 expected_after_cf,
408 expected_after_dce,
409 check_after_cf,
410 Primitive::kPrimLong);
411 }
412
413 /**
414 * Tiny three-register-pair program exercising long constant folding
415 * on subtraction.
416 *
417 * 16-bit
418 * offset
419 * ------
420 * (v0, v1) <- 3 0. const-wide/16 v0, #+3
421 * (v2, v3) <- 2 2. const-wide/16 v2, #+2
422 * (v4, v5) <-
423 * (v0, v1) - (v1, v2) 4. sub-long v4, v0, v2
424 * return (v4, v5) 6. return-wide v4
425 */
TEST(ConstantFolding,LongConstantFoldingOnSubtraction)426 TEST(ConstantFolding, LongConstantFoldingOnSubtraction) {
427 const uint16_t data[] = SIX_REGISTERS_CODE_ITEM(
428 Instruction::CONST_WIDE_16 | 0 << 8, 3,
429 Instruction::CONST_WIDE_16 | 2 << 8, 2,
430 Instruction::SUB_LONG | 4 << 8, 0 | 2 << 8,
431 Instruction::RETURN_WIDE | 4 << 8);
432
433 std::string expected_before =
434 "BasicBlock 0, succ: 1\n"
435 " 6: LongConstant [12]\n"
436 " 8: LongConstant [12]\n"
437 " 17: SuspendCheck\n"
438 " 18: Goto 1\n"
439 "BasicBlock 1, pred: 0, succ: 2\n"
440 " 12: Sub(6, 8) [15]\n"
441 " 15: Return(12)\n"
442 "BasicBlock 2, pred: 1\n"
443 " 16: Exit\n";
444
445 // Expected difference after constant folding.
446 diff_t expected_cf_diff = {
447 { " 6: LongConstant [12]\n", " 6: LongConstant\n" },
448 { " 8: LongConstant [12]\n", " 8: LongConstant\n" },
449 { " 17: SuspendCheck\n", " 17: SuspendCheck\n"
450 " 19: LongConstant [15]\n" },
451 { " 12: Sub(6, 8) [15]\n", removed },
452 { " 15: Return(12)\n", " 15: Return(19)\n" }
453 };
454 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
455
456 // Check the value of the computed constant.
457 auto check_after_cf = [](HGraph* graph) {
458 HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
459 ASSERT_TRUE(inst->IsLongConstant());
460 ASSERT_EQ(inst->AsLongConstant()->GetValue(), 1);
461 };
462
463 // Expected difference after dead code elimination.
464 diff_t expected_dce_diff = {
465 { " 6: LongConstant\n", removed },
466 { " 8: LongConstant\n", removed }
467 };
468 std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
469
470 TestCode(data,
471 expected_before,
472 expected_after_cf,
473 expected_after_dce,
474 check_after_cf,
475 Primitive::kPrimLong);
476 }
477
478 /**
479 * Three-register program with jumps leading to the creation of many
480 * blocks.
481 *
482 * The intent of this test is to ensure that all constant expressions
483 * are actually evaluated at compile-time, thanks to the reverse
484 * (forward) post-order traversal of the the dominator tree.
485 *
486 * 16-bit
487 * offset
488 * ------
489 * v0 <- 1 0. const/4 v0, #+1
490 * v1 <- 2 1. const/4 v1, #+2
491 * v2 <- v0 + v1 2. add-int v2, v0, v1
492 * goto L2 4. goto +4
493 * L1: v1 <- v0 + 5 5. add-int/lit16 v1, v0, #+5
494 * goto L3 7. goto +4
495 * L2: v0 <- v2 + 4 8. add-int/lit16 v0, v2, #+4
496 * goto L1 10. goto +(-5)
497 * L3: v2 <- v1 + 8 11. add-int/lit16 v2, v1, #+8
498 * return v2 13. return v2
499 */
TEST(ConstantFolding,IntConstantFoldingAndJumps)500 TEST(ConstantFolding, IntConstantFoldingAndJumps) {
501 const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
502 Instruction::CONST_4 | 0 << 8 | 1 << 12,
503 Instruction::CONST_4 | 1 << 8 | 2 << 12,
504 Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
505 Instruction::GOTO | 4 << 8,
506 Instruction::ADD_INT_LIT16 | 1 << 8 | 0 << 12, 5,
507 Instruction::GOTO | 4 << 8,
508 Instruction::ADD_INT_LIT16 | 0 << 8 | 2 << 12, 4,
509 static_cast<uint16_t>(Instruction::GOTO | -5 << 8),
510 Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 8,
511 Instruction::RETURN | 2 << 8);
512
513 std::string expected_before =
514 "BasicBlock 0, succ: 1\n"
515 " 3: IntConstant [9]\n" // v0 <- 1
516 " 5: IntConstant [9]\n" // v1 <- 2
517 " 13: IntConstant [14]\n" // const 5
518 " 18: IntConstant [19]\n" // const 4
519 " 24: IntConstant [25]\n" // const 8
520 " 30: SuspendCheck\n"
521 " 31: Goto 1\n"
522 "BasicBlock 1, pred: 0, succ: 3\n"
523 " 9: Add(3, 5) [19]\n" // v2 <- v0 + v1 = 1 + 2 = 3
524 " 11: Goto 3\n" // goto L2
525 "BasicBlock 2, pred: 3, succ: 4\n" // L1:
526 " 14: Add(19, 13) [25]\n" // v1 <- v0 + 3 = 7 + 5 = 12
527 " 16: Goto 4\n" // goto L3
528 "BasicBlock 3, pred: 1, succ: 2\n" // L2:
529 " 19: Add(9, 18) [14]\n" // v0 <- v2 + 2 = 3 + 4 = 7
530 " 21: SuspendCheck\n"
531 " 22: Goto 2\n" // goto L1
532 "BasicBlock 4, pred: 2, succ: 5\n" // L3:
533 " 25: Add(14, 24) [28]\n" // v2 <- v1 + 4 = 12 + 8 = 20
534 " 28: Return(25)\n" // return v2
535 "BasicBlock 5, pred: 4\n"
536 " 29: Exit\n";
537
538 // Expected difference after constant folding.
539 diff_t expected_cf_diff = {
540 { " 3: IntConstant [9]\n", " 3: IntConstant\n" },
541 { " 5: IntConstant [9]\n", " 5: IntConstant []\n" },
542 { " 13: IntConstant [14]\n", " 13: IntConstant\n" },
543 { " 18: IntConstant [19]\n", " 18: IntConstant\n" },
544 { " 24: IntConstant [25]\n", " 24: IntConstant\n" },
545 { " 30: SuspendCheck\n", " 30: SuspendCheck\n"
546 " 32: IntConstant []\n"
547 " 33: IntConstant []\n"
548 " 34: IntConstant\n"
549 " 35: IntConstant [28]\n" },
550 { " 9: Add(3, 5) [19]\n", removed },
551 { " 14: Add(19, 13) [25]\n", removed },
552 { " 19: Add(9, 18) [14]\n", removed },
553 { " 25: Add(14, 24) [28]\n", removed },
554 { " 28: Return(25)\n", " 28: Return(35)\n"}
555 };
556 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
557
558 // Check the values of the computed constants.
559 auto check_after_cf = [](HGraph* graph) {
560 HInstruction* inst1 = graph->GetBlock(4)->GetFirstInstruction()->InputAt(0);
561 ASSERT_TRUE(inst1->IsIntConstant());
562 ASSERT_EQ(inst1->AsIntConstant()->GetValue(), 20);
563 HInstruction* inst2 = inst1->GetPrevious();
564 ASSERT_TRUE(inst2->IsIntConstant());
565 ASSERT_EQ(inst2->AsIntConstant()->GetValue(), 12);
566 HInstruction* inst3 = inst2->GetPrevious();
567 ASSERT_TRUE(inst3->IsIntConstant());
568 ASSERT_EQ(inst3->AsIntConstant()->GetValue(), 7);
569 HInstruction* inst4 = inst3->GetPrevious();
570 ASSERT_TRUE(inst4->IsIntConstant());
571 ASSERT_EQ(inst4->AsIntConstant()->GetValue(), 3);
572 };
573
574 // Expected difference after dead code elimination.
575 std::string expected_after_dce =
576 "BasicBlock 0, succ: 1\n"
577 " 5: IntConstant []\n"
578 " 30: SuspendCheck\n"
579 " 32: IntConstant []\n"
580 " 33: IntConstant []\n"
581 " 35: IntConstant [28]\n"
582 " 31: Goto 1\n"
583 "BasicBlock 1, pred: 0, succ: 5\n"
584 " 21: SuspendCheck\n"
585 " 28: Return(35)\n"
586 "BasicBlock 5, pred: 1\n"
587 " 29: Exit\n";
588
589 TestCode(data,
590 expected_before,
591 expected_after_cf,
592 expected_after_dce,
593 check_after_cf);
594 }
595
596
597 /**
598 * Three-register program with a constant (static) condition.
599 *
600 * 16-bit
601 * offset
602 * ------
603 * v1 <- 1 0. const/4 v1, #+1
604 * v0 <- 0 1. const/4 v0, #+0
605 * if v1 >= 0 goto L1 2. if-gez v1, +3
606 * v0 <- v1 4. move v0, v1
607 * L1: v2 <- v0 + v1 5. add-int v2, v0, v1
608 * return-void 7. return
609 */
TEST(ConstantFolding,ConstantCondition)610 TEST(ConstantFolding, ConstantCondition) {
611 const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
612 Instruction::CONST_4 | 1 << 8 | 1 << 12,
613 Instruction::CONST_4 | 0 << 8 | 0 << 12,
614 Instruction::IF_GEZ | 1 << 8, 3,
615 Instruction::MOVE | 0 << 8 | 1 << 12,
616 Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
617 Instruction::RETURN_VOID);
618
619 std::string expected_before =
620 "BasicBlock 0, succ: 1\n"
621 " 3: IntConstant [15, 22, 8]\n"
622 " 5: IntConstant [22, 8]\n"
623 " 19: SuspendCheck\n"
624 " 20: Goto 1\n"
625 "BasicBlock 1, pred: 0, succ: 5, 2\n"
626 " 8: GreaterThanOrEqual(3, 5) [9]\n"
627 " 9: If(8)\n"
628 "BasicBlock 2, pred: 1, succ: 3\n"
629 " 12: Goto 3\n"
630 "BasicBlock 3, pred: 5, 2, succ: 4\n"
631 " 22: Phi(5, 3) [15]\n"
632 " 15: Add(22, 3)\n"
633 " 17: ReturnVoid\n"
634 "BasicBlock 4, pred: 3\n"
635 " 18: Exit\n"
636 "BasicBlock 5, pred: 1, succ: 3\n"
637 " 21: Goto 3\n";
638
639 // Expected difference after constant folding.
640 diff_t expected_cf_diff = {
641 { " 3: IntConstant [15, 22, 8]\n", " 3: IntConstant [9, 15, 22]\n" },
642 { " 5: IntConstant [22, 8]\n", " 5: IntConstant [22]\n" },
643 { " 8: GreaterThanOrEqual(3, 5) [9]\n", removed },
644 { " 9: If(8)\n", " 9: If(3)\n" }
645 };
646 std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
647
648 // Check the values of the computed constants.
649 auto check_after_cf = [](HGraph* graph) {
650 HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
651 ASSERT_TRUE(inst->IsIntConstant());
652 ASSERT_EQ(inst->AsIntConstant()->GetValue(), 1);
653 };
654
655 // Expected graph after dead code elimination.
656 std::string expected_after_dce =
657 "BasicBlock 0, succ: 1\n"
658 " 19: SuspendCheck\n"
659 " 20: Goto 1\n"
660 "BasicBlock 1, pred: 0, succ: 4\n"
661 " 17: ReturnVoid\n"
662 "BasicBlock 4, pred: 1\n"
663 " 18: Exit\n";
664
665 TestCode(data,
666 expected_before,
667 expected_after_cf,
668 expected_after_dce,
669 check_after_cf);
670 }
671
672 } // namespace art
673