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