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