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 30namespace art { 31 32/** 33 * Fixture class for the constant folding and dce tests. 34 */ 35class ConstantFoldingTest : public CommonCompilerTest { 36 public: 37 ConstantFoldingTest() : pool_(), allocator_(&pool_) { 38 graph_ = CreateGraph(&allocator_); 39 } 40 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 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 54 void TestCodeOnReadyGraph(const std::string& expected_before, 55 const std::string& expected_after_cf, 56 const std::string& expected_after_dce, 57 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_).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_).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 */ 106TEST_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 */ 162TEST_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 */ 225TEST_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 */ 290TEST_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 */ 375TEST_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 */ 438TEST_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 */ 502TEST_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 */ 575TEST_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 */ 678TEST_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 */ 744TEST_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(), 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