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