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 "base/stringprintf.h" 18 #include "builder.h" 19 #include "dex_file.h" 20 #include "dex_instruction.h" 21 #include "nodes.h" 22 #include "optimizing_unit_test.h" 23 #include "pretty_printer.h" 24 #include "ssa_builder.h" 25 #include "utils/arena_allocator.h" 26 27 #include "gtest/gtest.h" 28 29 namespace art { 30 31 class SsaPrettyPrinter : public HPrettyPrinter { 32 public: 33 explicit SsaPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") {} 34 35 virtual void PrintInt(int value) { 36 str_ += StringPrintf("%d", value); 37 } 38 39 virtual void PrintString(const char* value) { 40 str_ += value; 41 } 42 43 virtual void PrintNewLine() { 44 str_ += '\n'; 45 } 46 47 void Clear() { str_.clear(); } 48 49 std::string str() const { return str_; } 50 51 virtual void VisitIntConstant(HIntConstant* constant) { 52 PrintPreInstruction(constant); 53 str_ += constant->DebugName(); 54 str_ += " "; 55 PrintInt(constant->GetValue()); 56 PrintPostInstruction(constant); 57 } 58 59 private: 60 std::string str_; 61 62 DISALLOW_COPY_AND_ASSIGN(SsaPrettyPrinter); 63 }; 64 65 static void ReNumberInstructions(HGraph* graph) { 66 int id = 0; 67 for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) { 68 HBasicBlock* block = graph->GetBlocks().Get(i); 69 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 70 it.Current()->SetId(id++); 71 } 72 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 73 it.Current()->SetId(id++); 74 } 75 } 76 } 77 78 static void TestCode(const uint16_t* data, const char* expected) { 79 ArenaPool pool; 80 ArenaAllocator allocator(&pool); 81 HGraphBuilder builder(&allocator); 82 const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data); 83 HGraph* graph = builder.BuildGraph(*item); 84 ASSERT_NE(graph, nullptr); 85 86 graph->BuildDominatorTree(); 87 graph->TransformToSSA(); 88 ReNumberInstructions(graph); 89 90 // Test that phis had their type set. 91 for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) { 92 for (HInstructionIterator it(graph->GetBlocks().Get(i)->GetPhis()); !it.Done(); it.Advance()) { 93 ASSERT_NE(it.Current()->GetType(), Primitive::kPrimVoid); 94 } 95 } 96 97 SsaPrettyPrinter printer(graph); 98 printer.VisitInsertionOrder(); 99 100 ASSERT_STREQ(expected, printer.str().c_str()); 101 } 102 103 TEST(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: 2, 5, 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 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(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: 2, 5, succ: 4\n" 145 " 6: Phi(1, 0) [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 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(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 4 [8]\n" 169 " 2: IntConstant 5 [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(1, 2) [9]\n" 180 " 9: Return(8)\n" 181 "BasicBlock 5, pred: 4\n" 182 " 10: Exit\n"; 183 184 const 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(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, 4, 2, 2]\n" 200 " 1: Goto\n" 201 "BasicBlock 1, pred: 0, succ: 5, 6\n" 202 " 2: Equal(0, 0) [3]\n" 203 " 3: If(2)\n" 204 "BasicBlock 2, pred: 3, 6, succ: 3\n" 205 " 4: Phi(6, 0) [6]\n" 206 " 5: Goto\n" 207 "BasicBlock 3, pred: 2, 5, succ: 2\n" 208 " 6: Phi(4, 0) [4]\n" 209 " 7: Goto\n" 210 "BasicBlock 4\n" 211 // Synthesized blocks to avoid critical edge. 212 "BasicBlock 5, pred: 1, succ: 3\n" 213 " 8: Goto\n" 214 "BasicBlock 6, pred: 1, succ: 2\n" 215 " 9: Goto\n"; 216 217 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 218 Instruction::CONST_4 | 0 | 0, 219 Instruction::IF_EQ, 3, 220 Instruction::GOTO | 0x100, 221 Instruction::GOTO | 0xFF00); 222 223 TestCode(data, expected); 224 } 225 226 TEST(SsaTest, Loop2) { 227 // Simple loop with one preheader and one back edge. 228 const char* expected = 229 "BasicBlock 0, succ: 1\n" 230 " 0: IntConstant 0 [4]\n" 231 " 1: IntConstant 4 [4]\n" 232 " 2: Goto\n" 233 "BasicBlock 1, pred: 0, succ: 2\n" 234 " 3: Goto\n" 235 "BasicBlock 2, pred: 1, 3, succ: 4, 3\n" 236 " 4: Phi(0, 1) [5, 5]\n" 237 " 5: Equal(4, 4) [6]\n" 238 " 6: If(5)\n" 239 "BasicBlock 3, pred: 2, succ: 2\n" 240 " 7: Goto\n" 241 "BasicBlock 4, pred: 2, succ: 5\n" 242 " 8: ReturnVoid\n" 243 "BasicBlock 5, pred: 4\n" 244 " 9: Exit\n"; 245 246 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 247 Instruction::CONST_4 | 0 | 0, 248 Instruction::IF_EQ, 4, 249 Instruction::CONST_4 | 4 << 12 | 0, 250 Instruction::GOTO | 0xFD00, 251 Instruction::RETURN_VOID); 252 253 TestCode(data, expected); 254 } 255 256 TEST(SsaTest, Loop3) { 257 // Test that a local not yet defined at the entry of a loop is handled properly. 258 const char* expected = 259 "BasicBlock 0, succ: 1\n" 260 " 0: IntConstant 0 [5]\n" 261 " 1: IntConstant 4 [5]\n" 262 " 2: IntConstant 5 [9]\n" 263 " 3: Goto\n" 264 "BasicBlock 1, pred: 0, succ: 2\n" 265 " 4: Goto\n" 266 "BasicBlock 2, pred: 1, 3, succ: 4, 3\n" 267 " 5: Phi(0, 1) [6, 6]\n" 268 " 6: Equal(5, 5) [7]\n" 269 " 7: If(6)\n" 270 "BasicBlock 3, pred: 2, succ: 2\n" 271 " 8: Goto\n" 272 "BasicBlock 4, pred: 2, succ: 5\n" 273 " 9: Return(2)\n" 274 "BasicBlock 5, pred: 4\n" 275 " 10: Exit\n"; 276 277 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( 278 Instruction::CONST_4 | 0 | 0, 279 Instruction::IF_EQ, 4, 280 Instruction::CONST_4 | 4 << 12 | 0, 281 Instruction::GOTO | 0xFD00, 282 Instruction::CONST_4 | 5 << 12 | 1 << 8, 283 Instruction::RETURN | 1 << 8); 284 285 TestCode(data, expected); 286 } 287 288 TEST(SsaTest, Loop4) { 289 // Make sure we support a preheader of a loop not being the first predecessor 290 // in the predecessor list of the header. 291 const char* expected = 292 "BasicBlock 0, succ: 1\n" 293 " 0: IntConstant 0 [4]\n" 294 " 1: IntConstant 4 [4]\n" 295 " 2: Goto\n" 296 "BasicBlock 1, pred: 0, succ: 4\n" 297 " 3: Goto\n" 298 "BasicBlock 2, pred: 3, 4, succ: 5, 3\n" 299 " 4: Phi(1, 0) [9, 5, 5]\n" 300 " 5: Equal(4, 4) [6]\n" 301 " 6: If(5)\n" 302 "BasicBlock 3, pred: 2, succ: 2\n" 303 " 7: Goto\n" 304 "BasicBlock 4, pred: 1, succ: 2\n" 305 " 8: Goto\n" 306 "BasicBlock 5, pred: 2, succ: 6\n" 307 " 9: Return(4)\n" 308 "BasicBlock 6, pred: 5\n" 309 " 10: Exit\n"; 310 311 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 312 Instruction::CONST_4 | 0 | 0, 313 Instruction::GOTO | 0x500, 314 Instruction::IF_EQ, 5, 315 Instruction::CONST_4 | 4 << 12 | 0, 316 Instruction::GOTO | 0xFD00, 317 Instruction::GOTO | 0xFC00, 318 Instruction::RETURN | 0 << 8); 319 320 TestCode(data, expected); 321 } 322 323 TEST(SsaTest, Loop5) { 324 // Make sure we create a preheader of a loop when a header originally has two 325 // incoming blocks and one back edge. 326 const char* expected = 327 "BasicBlock 0, succ: 1\n" 328 " 0: IntConstant 0 [4, 4]\n" 329 " 1: IntConstant 4 [14]\n" 330 " 2: IntConstant 5 [14]\n" 331 " 3: Goto\n" 332 "BasicBlock 1, pred: 0, succ: 3, 2\n" 333 " 4: Equal(0, 0) [5]\n" 334 " 5: If(4)\n" 335 "BasicBlock 2, pred: 1, succ: 8\n" 336 " 6: Goto\n" 337 "BasicBlock 3, pred: 1, succ: 8\n" 338 " 7: Goto\n" 339 "BasicBlock 4, pred: 5, 8, succ: 6, 5\n" 340 " 8: Phi(8, 14) [8, 12, 9, 9]\n" 341 " 9: Equal(8, 8) [10]\n" 342 " 10: If(9)\n" 343 "BasicBlock 5, pred: 4, succ: 4\n" 344 " 11: Goto\n" 345 "BasicBlock 6, pred: 4, succ: 7\n" 346 " 12: Return(8)\n" 347 "BasicBlock 7, pred: 6\n" 348 " 13: Exit\n" 349 "BasicBlock 8, pred: 2, 3, succ: 4\n" 350 " 14: Phi(1, 2) [8]\n" 351 " 15: 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(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 [14, 8, 8]\n" 372 " 2: IntConstant 5 [14]\n" 373 " 3: Goto\n" 374 "BasicBlock 1, pred: 0, succ: 2\n" 375 " 4: Goto\n" 376 "BasicBlock 2, pred: 1, 8, succ: 6, 3\n" 377 " 5: Phi(0, 14) [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: 8\n" 384 " 10: Goto\n" 385 "BasicBlock 5, pred: 3, succ: 8\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 // Synthesized single back edge of loop. 392 "BasicBlock 8, pred: 5, 4, succ: 2\n" 393 " 14: Phi(1, 2) [5]\n" 394 " 15: Goto\n"; 395 396 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 397 Instruction::CONST_4 | 0 | 0, 398 Instruction::IF_EQ, 8, 399 Instruction::CONST_4 | 4 << 12 | 0, 400 Instruction::IF_EQ, 4, 401 Instruction::CONST_4 | 5 << 12 | 0, 402 Instruction::GOTO | 0xFA00, 403 Instruction::GOTO | 0xF900, 404 Instruction::RETURN | 0 << 8); 405 406 TestCode(data, expected); 407 } 408 409 TEST(SsaTest, Loop7) { 410 // Test a loop with one preheader, one back edge, and two exit edges (e.g. break). 411 const char* expected = 412 "BasicBlock 0, succ: 1\n" 413 " 0: IntConstant 0 [5]\n" 414 " 1: IntConstant 4 [5, 8, 8]\n" 415 " 2: IntConstant 5 [12]\n" 416 " 3: Goto\n" 417 "BasicBlock 1, pred: 0, succ: 2\n" 418 " 4: Goto\n" 419 "BasicBlock 2, pred: 1, 5, succ: 8, 3\n" 420 " 5: Phi(0, 1) [12, 6, 6]\n" 421 " 6: Equal(5, 5) [7]\n" 422 " 7: If(6)\n" 423 "BasicBlock 3, pred: 2, succ: 5, 4\n" 424 " 8: Equal(1, 1) [9]\n" 425 " 9: If(8)\n" 426 "BasicBlock 4, pred: 3, succ: 6\n" 427 " 10: Goto\n" 428 "BasicBlock 5, pred: 3, succ: 2\n" 429 " 11: Goto\n" 430 "BasicBlock 6, pred: 4, 8, succ: 7\n" 431 " 12: Phi(2, 5) [13]\n" 432 " 13: Return(12)\n" 433 "BasicBlock 7, pred: 6\n" 434 " 14: Exit\n" 435 "BasicBlock 8, pred: 2, succ: 6\n" 436 " 15: Goto\n"; 437 438 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 439 Instruction::CONST_4 | 0 | 0, 440 Instruction::IF_EQ, 8, 441 Instruction::CONST_4 | 4 << 12 | 0, 442 Instruction::IF_EQ, 4, 443 Instruction::CONST_4 | 5 << 12 | 0, 444 Instruction::GOTO | 0x0200, 445 Instruction::GOTO | 0xF900, 446 Instruction::RETURN | 0 << 8); 447 448 TestCode(data, expected); 449 } 450 451 TEST(SsaTest, DeadLocal) { 452 // Test that we correctly handle a local not being used. 453 const char* expected = 454 "BasicBlock 0, succ: 1\n" 455 " 0: IntConstant 0\n" 456 " 1: Goto\n" 457 "BasicBlock 1, pred: 0, succ: 2\n" 458 " 2: ReturnVoid\n" 459 "BasicBlock 2, pred: 1\n" 460 " 3: Exit\n"; 461 462 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 463 Instruction::CONST_4 | 0 | 0, 464 Instruction::RETURN_VOID); 465 466 TestCode(data, expected); 467 } 468 469 TEST(SsaTest, LocalInIf) { 470 // Test that we do not create a phi in the join block when one predecessor 471 // does not update the local. 472 const char* expected = 473 "BasicBlock 0, succ: 1\n" 474 " 0: IntConstant 0 [3, 3]\n" 475 " 1: IntConstant 4\n" 476 " 2: Goto\n" 477 "BasicBlock 1, pred: 0, succ: 5, 2\n" 478 " 3: Equal(0, 0) [4]\n" 479 " 4: If(3)\n" 480 "BasicBlock 2, pred: 1, succ: 3\n" 481 " 5: Goto\n" 482 "BasicBlock 3, pred: 2, 5, succ: 4\n" 483 " 6: ReturnVoid\n" 484 "BasicBlock 4, pred: 3\n" 485 " 7: Exit\n" 486 // Synthesized block to avoid critical edge. 487 "BasicBlock 5, pred: 1, succ: 3\n" 488 " 8: Goto\n"; 489 490 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( 491 Instruction::CONST_4 | 0 | 0, 492 Instruction::IF_EQ, 3, 493 Instruction::CONST_4 | 4 << 12 | 1 << 8, 494 Instruction::RETURN_VOID); 495 496 TestCode(data, expected); 497 } 498 499 TEST(SsaTest, MultiplePredecessors) { 500 // Test that we do not create a phi when one predecessor 501 // does not update the local. 502 const char* expected = 503 "BasicBlock 0, succ: 1\n" 504 " 0: IntConstant 0 [4, 8, 6, 6, 2, 2, 8, 4]\n" 505 " 1: Goto\n" 506 "BasicBlock 1, pred: 0, succ: 3, 2\n" 507 " 2: Equal(0, 0) [3]\n" 508 " 3: If(2)\n" 509 "BasicBlock 2, pred: 1, succ: 5\n" 510 " 4: Add(0, 0)\n" 511 " 5: Goto\n" 512 "BasicBlock 3, pred: 1, succ: 7, 4\n" 513 " 6: Equal(0, 0) [7]\n" 514 " 7: If(6)\n" 515 "BasicBlock 4, pred: 3, succ: 5\n" 516 " 8: Add(0, 0)\n" 517 " 9: Goto\n" 518 // This block should not get a phi for local 1. 519 "BasicBlock 5, pred: 2, 4, 7, succ: 6\n" 520 " 10: ReturnVoid\n" 521 "BasicBlock 6, pred: 5\n" 522 " 11: Exit\n" 523 "BasicBlock 7, pred: 3, succ: 5\n" 524 " 12: Goto\n"; 525 526 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( 527 Instruction::CONST_4 | 0 | 0, 528 Instruction::IF_EQ, 5, 529 Instruction::ADD_INT_LIT8 | 1 << 8, 0 << 8, 530 Instruction::GOTO | 0x0500, 531 Instruction::IF_EQ, 4, 532 Instruction::ADD_INT_LIT8 | 1 << 8, 0 << 8, 533 Instruction::RETURN_VOID); 534 535 TestCode(data, expected); 536 } 537 538 } // namespace art 539