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 "android-base/stringprintf.h" 18 19 #include "base/arena_allocator.h" 20 #include "builder.h" 21 #include "dex/dex_file.h" 22 #include "dex/dex_instruction.h" 23 #include "nodes.h" 24 #include "optimizing_unit_test.h" 25 #include "pretty_printer.h" 26 #include "ssa_builder.h" 27 28 #include "gtest/gtest.h" 29 30 namespace art { 31 32 class SsaTest : public OptimizingUnitTest { 33 protected: 34 void TestCode(const std::vector<uint16_t>& data, const char* expected); 35 }; 36 37 class SsaPrettyPrinter : public HPrettyPrinter { 38 public: 39 explicit SsaPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") {} 40 41 void PrintInt(int value) OVERRIDE { 42 str_ += android::base::StringPrintf("%d", value); 43 } 44 45 void PrintString(const char* value) OVERRIDE { 46 str_ += value; 47 } 48 49 void PrintNewLine() OVERRIDE { 50 str_ += '\n'; 51 } 52 53 void Clear() { str_.clear(); } 54 55 std::string str() const { return str_; } 56 57 void VisitIntConstant(HIntConstant* constant) OVERRIDE { 58 PrintPreInstruction(constant); 59 str_ += constant->DebugName(); 60 str_ += " "; 61 PrintInt(constant->GetValue()); 62 PrintPostInstruction(constant); 63 } 64 65 private: 66 std::string str_; 67 68 DISALLOW_COPY_AND_ASSIGN(SsaPrettyPrinter); 69 }; 70 71 static void ReNumberInstructions(HGraph* graph) { 72 int id = 0; 73 for (HBasicBlock* block : graph->GetBlocks()) { 74 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 75 it.Current()->SetId(id++); 76 } 77 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 78 it.Current()->SetId(id++); 79 } 80 } 81 } 82 83 void SsaTest::TestCode(const std::vector<uint16_t>& data, const char* expected) { 84 HGraph* graph = CreateCFG(data); 85 // Suspend checks implementation may change in the future, and this test relies 86 // on how instructions are ordered. 87 RemoveSuspendChecks(graph); 88 ReNumberInstructions(graph); 89 90 // Test that phis had their type set. 91 for (HBasicBlock* block : graph->GetBlocks()) { 92 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 93 ASSERT_NE(it.Current()->GetType(), DataType::Type::kVoid); 94 } 95 } 96 97 SsaPrettyPrinter printer(graph); 98 printer.VisitInsertionOrder(); 99 100 ASSERT_STREQ(expected, printer.str().c_str()); 101 } 102 103 TEST_F(SsaTest, CFG1) { 104 // Test that we get rid of loads and stores. 105 const char* expected = 106 "BasicBlock 0, succ: 1\n" 107 " 0: IntConstant 0 [2, 2]\n" 108 " 1: Goto\n" 109 "BasicBlock 1, pred: 0, succ: 5, 2\n" 110 " 2: Equal(0, 0) [3]\n" 111 " 3: If(2)\n" 112 "BasicBlock 2, pred: 1, succ: 3\n" 113 " 4: Goto\n" 114 "BasicBlock 3, pred: 5, 2, succ: 4\n" 115 " 5: ReturnVoid\n" 116 "BasicBlock 4, pred: 3\n" 117 " 6: Exit\n" 118 // Synthesized block to avoid critical edge. 119 "BasicBlock 5, pred: 1, succ: 3\n" 120 " 7: Goto\n"; 121 122 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( 123 Instruction::CONST_4 | 0 | 0, 124 Instruction::IF_EQ, 3, 125 Instruction::GOTO | 0x100, 126 Instruction::RETURN_VOID); 127 128 TestCode(data, expected); 129 } 130 131 TEST_F(SsaTest, CFG2) { 132 // Test that we create a phi for the join block of an if control flow instruction 133 // when there is only code in the else branch. 134 const char* expected = 135 "BasicBlock 0, succ: 1\n" 136 " 0: IntConstant 0 [6, 3, 3]\n" 137 " 1: IntConstant 4 [6]\n" 138 " 2: Goto\n" 139 "BasicBlock 1, pred: 0, succ: 5, 2\n" 140 " 3: Equal(0, 0) [4]\n" 141 " 4: If(3)\n" 142 "BasicBlock 2, pred: 1, succ: 3\n" 143 " 5: Goto\n" 144 "BasicBlock 3, pred: 5, 2, succ: 4\n" 145 " 6: Phi(0, 1) [7]\n" 146 " 7: Return(6)\n" 147 "BasicBlock 4, pred: 3\n" 148 " 8: Exit\n" 149 // Synthesized block to avoid critical edge. 150 "BasicBlock 5, pred: 1, succ: 3\n" 151 " 9: Goto\n"; 152 153 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( 154 Instruction::CONST_4 | 0 | 0, 155 Instruction::IF_EQ, 3, 156 Instruction::CONST_4 | 4 << 12 | 0, 157 Instruction::RETURN | 0 << 8); 158 159 TestCode(data, expected); 160 } 161 162 TEST_F(SsaTest, CFG3) { 163 // Test that we create a phi for the join block of an if control flow instruction 164 // when both branches update a local. 165 const char* expected = 166 "BasicBlock 0, succ: 1\n" 167 " 0: IntConstant 0 [4, 4]\n" 168 " 1: IntConstant 5 [8]\n" 169 " 2: IntConstant 4 [8]\n" 170 " 3: Goto\n" 171 "BasicBlock 1, pred: 0, succ: 3, 2\n" 172 " 4: Equal(0, 0) [5]\n" 173 " 5: If(4)\n" 174 "BasicBlock 2, pred: 1, succ: 4\n" 175 " 6: Goto\n" 176 "BasicBlock 3, pred: 1, succ: 4\n" 177 " 7: Goto\n" 178 "BasicBlock 4, pred: 2, 3, succ: 5\n" 179 " 8: Phi(2, 1) [9]\n" 180 " 9: Return(8)\n" 181 "BasicBlock 5, pred: 4\n" 182 " 10: Exit\n"; 183 184 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( 185 Instruction::CONST_4 | 0 | 0, 186 Instruction::IF_EQ, 4, 187 Instruction::CONST_4 | 4 << 12 | 0, 188 Instruction::GOTO | 0x200, 189 Instruction::CONST_4 | 5 << 12 | 0, 190 Instruction::RETURN | 0 << 8); 191 192 TestCode(data, expected); 193 } 194 195 TEST_F(SsaTest, Loop1) { 196 // Test that we create a phi for an initialized local at entry of a loop. 197 const char* expected = 198 "BasicBlock 0, succ: 1\n" 199 " 0: IntConstant 0 [6, 3, 3]\n" 200 " 1: IntConstant 4 [6]\n" 201 " 2: Goto\n" 202 "BasicBlock 1, pred: 0, succ: 4, 2\n" 203 " 3: Equal(0, 0) [4]\n" 204 " 4: If(3)\n" 205 "BasicBlock 2, pred: 1, succ: 3\n" 206 " 5: Goto\n" 207 "BasicBlock 3, pred: 2, 4, succ: 5\n" 208 " 6: Phi(1, 0) [9]\n" 209 " 7: Goto\n" 210 "BasicBlock 4, pred: 1, succ: 3\n" 211 " 8: Goto\n" 212 "BasicBlock 5, pred: 3, succ: 6\n" 213 " 9: Return(6)\n" 214 "BasicBlock 6, pred: 5\n" 215 " 10: Exit\n"; 216 217 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( 218 Instruction::CONST_4 | 0 | 0, 219 Instruction::IF_EQ, 4, 220 Instruction::CONST_4 | 4 << 12 | 0, 221 Instruction::GOTO | 0x200, 222 Instruction::GOTO | 0xFF00, 223 Instruction::RETURN | 0 << 8); 224 225 TestCode(data, expected); 226 } 227 228 TEST_F(SsaTest, Loop2) { 229 // Simple loop with one preheader and one back edge. 230 const char* expected = 231 "BasicBlock 0, succ: 1\n" 232 " 0: IntConstant 0 [4]\n" 233 " 1: IntConstant 4 [4]\n" 234 " 2: Goto\n" 235 "BasicBlock 1, pred: 0, succ: 2\n" 236 " 3: Goto\n" 237 "BasicBlock 2, pred: 1, 3, succ: 4, 3\n" 238 " 4: Phi(0, 1) [5, 5]\n" 239 " 5: Equal(4, 4) [6]\n" 240 " 6: If(5)\n" 241 "BasicBlock 3, pred: 2, succ: 2\n" 242 " 7: Goto\n" 243 "BasicBlock 4, pred: 2, succ: 5\n" 244 " 8: ReturnVoid\n" 245 "BasicBlock 5, pred: 4\n" 246 " 9: Exit\n"; 247 248 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( 249 Instruction::CONST_4 | 0 | 0, 250 Instruction::IF_EQ, 4, 251 Instruction::CONST_4 | 4 << 12 | 0, 252 Instruction::GOTO | 0xFD00, 253 Instruction::RETURN_VOID); 254 255 TestCode(data, expected); 256 } 257 258 TEST_F(SsaTest, Loop3) { 259 // Test that a local not yet defined at the entry of a loop is handled properly. 260 const char* expected = 261 "BasicBlock 0, succ: 1\n" 262 " 0: IntConstant 0 [5]\n" 263 " 1: IntConstant 5 [9]\n" 264 " 2: IntConstant 4 [5]\n" 265 " 3: Goto\n" 266 "BasicBlock 1, pred: 0, succ: 2\n" 267 " 4: Goto\n" 268 "BasicBlock 2, pred: 1, 3, succ: 4, 3\n" 269 " 5: Phi(0, 2) [6, 6]\n" 270 " 6: Equal(5, 5) [7]\n" 271 " 7: If(6)\n" 272 "BasicBlock 3, pred: 2, succ: 2\n" 273 " 8: Goto\n" 274 "BasicBlock 4, pred: 2, succ: 5\n" 275 " 9: Return(1)\n" 276 "BasicBlock 5, pred: 4\n" 277 " 10: Exit\n"; 278 279 const std::vector<uint16_t> data = TWO_REGISTERS_CODE_ITEM( 280 Instruction::CONST_4 | 0 | 0, 281 Instruction::IF_EQ, 4, 282 Instruction::CONST_4 | 4 << 12 | 0, 283 Instruction::GOTO | 0xFD00, 284 Instruction::CONST_4 | 5 << 12 | 1 << 8, 285 Instruction::RETURN | 1 << 8); 286 287 TestCode(data, expected); 288 } 289 290 TEST_F(SsaTest, Loop4) { 291 // Make sure we support a preheader of a loop not being the first predecessor 292 // in the predecessor list of the header. 293 const char* expected = 294 "BasicBlock 0, succ: 1\n" 295 " 0: IntConstant 0 [4]\n" 296 " 1: IntConstant 4 [4]\n" 297 " 2: Goto\n" 298 "BasicBlock 1, pred: 0, succ: 4\n" 299 " 3: Goto\n" 300 "BasicBlock 2, pred: 4, 3, succ: 5, 3\n" 301 " 4: Phi(0, 1) [9, 5, 5]\n" 302 " 5: Equal(4, 4) [6]\n" 303 " 6: If(5)\n" 304 "BasicBlock 3, pred: 2, succ: 2\n" 305 " 7: Goto\n" 306 "BasicBlock 4, pred: 1, succ: 2\n" 307 " 8: Goto\n" 308 "BasicBlock 5, pred: 2, succ: 6\n" 309 " 9: Return(4)\n" 310 "BasicBlock 6, pred: 5\n" 311 " 10: Exit\n"; 312 313 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( 314 Instruction::CONST_4 | 0 | 0, 315 Instruction::GOTO | 0x500, 316 Instruction::IF_EQ, 5, 317 Instruction::CONST_4 | 4 << 12 | 0, 318 Instruction::GOTO | 0xFD00, 319 Instruction::GOTO | 0xFC00, 320 Instruction::RETURN | 0 << 8); 321 322 TestCode(data, expected); 323 } 324 325 TEST_F(SsaTest, Loop5) { 326 // Make sure we create a preheader of a loop when a header originally has two 327 // incoming blocks and one back edge. 328 const char* expected = 329 "BasicBlock 0, succ: 1\n" 330 " 0: IntConstant 0 [4, 4]\n" 331 " 1: IntConstant 5 [13]\n" 332 " 2: IntConstant 4 [13]\n" 333 " 3: Goto\n" 334 "BasicBlock 1, pred: 0, succ: 3, 2\n" 335 " 4: Equal(0, 0) [5]\n" 336 " 5: If(4)\n" 337 "BasicBlock 2, pred: 1, succ: 8\n" 338 " 6: Goto\n" 339 "BasicBlock 3, pred: 1, succ: 8\n" 340 " 7: Goto\n" 341 "BasicBlock 4, pred: 8, 5, succ: 6, 5\n" 342 " 8: Equal(13, 13) [9]\n" 343 " 9: If(8)\n" 344 "BasicBlock 5, pred: 4, succ: 4\n" 345 " 10: Goto\n" 346 "BasicBlock 6, pred: 4, succ: 7\n" 347 " 11: Return(13)\n" 348 "BasicBlock 7, pred: 6\n" 349 " 12: Exit\n" 350 "BasicBlock 8, pred: 2, 3, succ: 4\n" 351 " 13: Phi(2, 1) [11, 8, 8]\n" 352 " 14: Goto\n"; 353 354 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( 355 Instruction::CONST_4 | 0 | 0, 356 Instruction::IF_EQ, 4, 357 Instruction::CONST_4 | 4 << 12 | 0, 358 Instruction::GOTO | 0x200, 359 Instruction::CONST_4 | 5 << 12 | 0, 360 Instruction::IF_EQ, 3, 361 Instruction::GOTO | 0xFE00, 362 Instruction::RETURN | 0 << 8); 363 364 TestCode(data, expected); 365 } 366 367 TEST_F(SsaTest, Loop6) { 368 // Test a loop with one preheader and two back edges (e.g. continue). 369 const char* expected = 370 "BasicBlock 0, succ: 1\n" 371 " 0: IntConstant 0 [5]\n" 372 " 1: IntConstant 4 [5, 8, 8]\n" 373 " 2: IntConstant 5 [5]\n" 374 " 3: Goto\n" 375 "BasicBlock 1, pred: 0, succ: 2\n" 376 " 4: Goto\n" 377 "BasicBlock 2, pred: 1, 4, 5, succ: 6, 3\n" 378 " 5: Phi(0, 2, 1) [12, 6, 6]\n" 379 " 6: Equal(5, 5) [7]\n" 380 " 7: If(6)\n" 381 "BasicBlock 3, pred: 2, succ: 5, 4\n" 382 " 8: Equal(1, 1) [9]\n" 383 " 9: If(8)\n" 384 "BasicBlock 4, pred: 3, succ: 2\n" 385 " 10: Goto\n" 386 "BasicBlock 5, pred: 3, succ: 2\n" 387 " 11: Goto\n" 388 "BasicBlock 6, pred: 2, succ: 7\n" 389 " 12: Return(5)\n" 390 "BasicBlock 7, pred: 6\n" 391 " 13: Exit\n"; 392 393 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( 394 Instruction::CONST_4 | 0 | 0, 395 Instruction::IF_EQ, 8, 396 Instruction::CONST_4 | 4 << 12 | 0, 397 Instruction::IF_EQ, 4, 398 Instruction::CONST_4 | 5 << 12 | 0, 399 Instruction::GOTO | 0xFA00, 400 Instruction::GOTO | 0xF900, 401 Instruction::RETURN | 0 << 8); 402 403 TestCode(data, expected); 404 } 405 406 TEST_F(SsaTest, Loop7) { 407 // Test a loop with one preheader, one back edge, and two exit edges (e.g. break). 408 const char* expected = 409 "BasicBlock 0, succ: 1\n" 410 " 0: IntConstant 0 [5]\n" 411 " 1: IntConstant 4 [5, 8, 8]\n" 412 " 2: IntConstant 5 [12]\n" 413 " 3: Goto\n" 414 "BasicBlock 1, pred: 0, succ: 2\n" 415 " 4: Goto\n" 416 "BasicBlock 2, pred: 1, 5, succ: 8, 3\n" 417 " 5: Phi(0, 1) [12, 6, 6]\n" 418 " 6: Equal(5, 5) [7]\n" 419 " 7: If(6)\n" 420 "BasicBlock 3, pred: 2, succ: 5, 4\n" 421 " 8: Equal(1, 1) [9]\n" 422 " 9: If(8)\n" 423 "BasicBlock 4, pred: 3, succ: 6\n" 424 " 10: Goto\n" 425 "BasicBlock 5, pred: 3, succ: 2\n" 426 " 11: Goto\n" 427 "BasicBlock 6, pred: 8, 4, succ: 7\n" 428 " 12: Phi(5, 2) [13]\n" 429 " 13: Return(12)\n" 430 "BasicBlock 7, pred: 6\n" 431 " 14: Exit\n" 432 "BasicBlock 8, pred: 2, succ: 6\n" 433 " 15: Goto\n"; 434 435 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( 436 Instruction::CONST_4 | 0 | 0, 437 Instruction::IF_EQ, 8, 438 Instruction::CONST_4 | 4 << 12 | 0, 439 Instruction::IF_EQ, 4, 440 Instruction::CONST_4 | 5 << 12 | 0, 441 Instruction::GOTO | 0x0200, 442 Instruction::GOTO | 0xF900, 443 Instruction::RETURN | 0 << 8); 444 445 TestCode(data, expected); 446 } 447 448 TEST_F(SsaTest, DeadLocal) { 449 // Test that we correctly handle a local not being used. 450 const char* expected = 451 "BasicBlock 0, succ: 1\n" 452 " 0: IntConstant 0\n" 453 " 1: Goto\n" 454 "BasicBlock 1, pred: 0, succ: 2\n" 455 " 2: ReturnVoid\n" 456 "BasicBlock 2, pred: 1\n" 457 " 3: Exit\n"; 458 459 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( 460 Instruction::CONST_4 | 0 | 0, 461 Instruction::RETURN_VOID); 462 463 TestCode(data, expected); 464 } 465 466 TEST_F(SsaTest, LocalInIf) { 467 // Test that we do not create a phi in the join block when one predecessor 468 // does not update the local. 469 const char* expected = 470 "BasicBlock 0, succ: 1\n" 471 " 0: IntConstant 0 [3, 3]\n" 472 " 1: IntConstant 4\n" 473 " 2: Goto\n" 474 "BasicBlock 1, pred: 0, succ: 5, 2\n" 475 " 3: Equal(0, 0) [4]\n" 476 " 4: If(3)\n" 477 "BasicBlock 2, pred: 1, succ: 3\n" 478 " 5: Goto\n" 479 "BasicBlock 3, pred: 5, 2, succ: 4\n" 480 " 6: ReturnVoid\n" 481 "BasicBlock 4, pred: 3\n" 482 " 7: Exit\n" 483 // Synthesized block to avoid critical edge. 484 "BasicBlock 5, pred: 1, succ: 3\n" 485 " 8: Goto\n"; 486 487 const std::vector<uint16_t> data = TWO_REGISTERS_CODE_ITEM( 488 Instruction::CONST_4 | 0 | 0, 489 Instruction::IF_EQ, 3, 490 Instruction::CONST_4 | 4 << 12 | 1 << 8, 491 Instruction::RETURN_VOID); 492 493 TestCode(data, expected); 494 } 495 496 TEST_F(SsaTest, MultiplePredecessors) { 497 // Test that we do not create a phi when one predecessor 498 // does not update the local. 499 const char* expected = 500 "BasicBlock 0, succ: 1\n" 501 " 0: IntConstant 0 [4, 4, 8, 8, 6, 6, 2, 2]\n" 502 " 1: Goto\n" 503 "BasicBlock 1, pred: 0, succ: 3, 2\n" 504 " 2: Equal(0, 0) [3]\n" 505 " 3: If(2)\n" 506 "BasicBlock 2, pred: 1, succ: 5\n" 507 " 4: Add(0, 0)\n" 508 " 5: Goto\n" 509 "BasicBlock 3, pred: 1, succ: 7, 4\n" 510 " 6: Equal(0, 0) [7]\n" 511 " 7: If(6)\n" 512 "BasicBlock 4, pred: 3, succ: 5\n" 513 " 8: Add(0, 0)\n" 514 " 9: Goto\n" 515 // This block should not get a phi for local 1. 516 "BasicBlock 5, pred: 2, 7, 4, succ: 6\n" 517 " 10: ReturnVoid\n" 518 "BasicBlock 6, pred: 5\n" 519 " 11: Exit\n" 520 "BasicBlock 7, pred: 3, succ: 5\n" 521 " 12: Goto\n"; 522 523 const std::vector<uint16_t> data = TWO_REGISTERS_CODE_ITEM( 524 Instruction::CONST_4 | 0 | 0, 525 Instruction::IF_EQ, 5, 526 Instruction::ADD_INT_LIT8 | 1 << 8, 0 << 8, 527 Instruction::GOTO | 0x0500, 528 Instruction::IF_EQ, 4, 529 Instruction::ADD_INT_LIT8 | 1 << 8, 0 << 8, 530 Instruction::RETURN_VOID); 531 532 TestCode(data, expected); 533 } 534 535 } // namespace art 536
