1 //===- CFGTest.cpp - CFG tests --------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/Analysis/CFG.h" 10 #include "llvm/ADT/SmallPtrSet.h" 11 #include "llvm/Analysis/LoopInfo.h" 12 #include "llvm/AsmParser/Parser.h" 13 #include "llvm/IR/Dominators.h" 14 #include "llvm/IR/Function.h" 15 #include "llvm/IR/InstIterator.h" 16 #include "llvm/IR/LLVMContext.h" 17 #include "llvm/IR/LegacyPassManager.h" 18 #include "llvm/IR/Module.h" 19 #include "llvm/InitializePasses.h" 20 #include "llvm/Support/ErrorHandling.h" 21 #include "llvm/Support/SourceMgr.h" 22 #include "gtest/gtest.h" 23 24 using namespace llvm; 25 26 namespace { 27 28 // This fixture assists in running the isPotentiallyReachable utility four ways 29 // and ensuring it produces the correct answer each time. 30 class IsPotentiallyReachableTest : public testing::Test { 31 protected: 32 void ParseAssembly(const char *Assembly) { 33 SMDiagnostic Error; 34 M = parseAssemblyString(Assembly, Error, Context); 35 36 std::string errMsg; 37 raw_string_ostream os(errMsg); 38 Error.print("", os); 39 40 // A failure here means that the test itself is buggy. 41 if (!M) 42 report_fatal_error(errMsg.c_str()); 43 44 Function *F = M->getFunction("test"); 45 if (F == nullptr) 46 report_fatal_error("Test must have a function named @test"); 47 48 A = B = nullptr; 49 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { 50 if (I->hasName()) { 51 if (I->getName() == "A") 52 A = &*I; 53 else if (I->getName() == "B") 54 B = &*I; 55 } 56 } 57 if (A == nullptr) 58 report_fatal_error("@test must have an instruction %A"); 59 if (B == nullptr) 60 report_fatal_error("@test must have an instruction %B"); 61 62 assert(ExclusionSet.empty()); 63 for (auto I = F->begin(), E = F->end(); I != E; ++I) { 64 if (I->hasName() && I->getName().starts_with("excluded")) 65 ExclusionSet.insert(&*I); 66 } 67 } 68 69 void ExpectPath(bool ExpectedResult) { 70 static char ID; 71 class IsPotentiallyReachableTestPass : public FunctionPass { 72 public: 73 IsPotentiallyReachableTestPass(bool ExpectedResult, Instruction *A, 74 Instruction *B, 75 SmallPtrSet<BasicBlock *, 4> ExclusionSet) 76 : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B), 77 ExclusionSet(ExclusionSet) {} 78 79 static int initialize() { 80 PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass", "", 81 &ID, nullptr, true, true); 82 PassRegistry::getPassRegistry()->registerPass(*PI, true); 83 initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry()); 84 initializeDominatorTreeWrapperPassPass( 85 *PassRegistry::getPassRegistry()); 86 return 0; 87 } 88 89 void getAnalysisUsage(AnalysisUsage &AU) const override { 90 AU.setPreservesAll(); 91 AU.addRequired<LoopInfoWrapperPass>(); 92 AU.addRequired<DominatorTreeWrapperPass>(); 93 } 94 95 bool runOnFunction(Function &F) override { 96 if (!F.hasName() || F.getName() != "test") 97 return false; 98 99 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 100 DominatorTree *DT = 101 &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 102 EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, nullptr, nullptr), 103 ExpectedResult); 104 EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, DT, nullptr), 105 ExpectedResult); 106 EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, nullptr, LI), 107 ExpectedResult); 108 EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, DT, LI), 109 ExpectedResult); 110 return false; 111 } 112 bool ExpectedResult; 113 Instruction *A, *B; 114 SmallPtrSet<BasicBlock *, 4> ExclusionSet; 115 }; 116 117 static int initialize = IsPotentiallyReachableTestPass::initialize(); 118 (void)initialize; 119 120 IsPotentiallyReachableTestPass *P = 121 new IsPotentiallyReachableTestPass(ExpectedResult, A, B, ExclusionSet); 122 legacy::PassManager PM; 123 PM.add(P); 124 PM.run(*M); 125 } 126 127 LLVMContext Context; 128 std::unique_ptr<Module> M; 129 Instruction *A, *B; 130 SmallPtrSet<BasicBlock *, 4> ExclusionSet; 131 }; 132 133 } 134 135 TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) { 136 ParseAssembly( 137 "define void @test() {\n" 138 "entry:\n" 139 " bitcast i8 undef to i8\n" 140 " %B = bitcast i8 undef to i8\n" 141 " bitcast i8 undef to i8\n" 142 " bitcast i8 undef to i8\n" 143 " %A = bitcast i8 undef to i8\n" 144 " ret void\n" 145 "}\n"); 146 ExpectPath(false); 147 } 148 149 TEST_F(IsPotentiallyReachableTest, SameBlockPath) { 150 ParseAssembly( 151 "define void @test() {\n" 152 "entry:\n" 153 " %A = bitcast i8 undef to i8\n" 154 " bitcast i8 undef to i8\n" 155 " bitcast i8 undef to i8\n" 156 " %B = bitcast i8 undef to i8\n" 157 " ret void\n" 158 "}\n"); 159 ExpectPath(true); 160 } 161 162 TEST_F(IsPotentiallyReachableTest, SameBlockNoLoop) { 163 ParseAssembly( 164 "define void @test() {\n" 165 "entry:\n" 166 " br label %middle\n" 167 "middle:\n" 168 " %B = bitcast i8 undef to i8\n" 169 " bitcast i8 undef to i8\n" 170 " bitcast i8 undef to i8\n" 171 " %A = bitcast i8 undef to i8\n" 172 " br label %nextblock\n" 173 "nextblock:\n" 174 " ret void\n" 175 "}\n"); 176 ExpectPath(false); 177 } 178 179 TEST_F(IsPotentiallyReachableTest, StraightNoPath) { 180 ParseAssembly( 181 "define void @test() {\n" 182 "entry:\n" 183 " %B = bitcast i8 undef to i8\n" 184 " br label %exit\n" 185 "exit:\n" 186 " %A = bitcast i8 undef to i8\n" 187 " ret void\n" 188 "}"); 189 ExpectPath(false); 190 } 191 192 TEST_F(IsPotentiallyReachableTest, StraightPath) { 193 ParseAssembly( 194 "define void @test() {\n" 195 "entry:\n" 196 " %A = bitcast i8 undef to i8\n" 197 " br label %exit\n" 198 "exit:\n" 199 " %B = bitcast i8 undef to i8\n" 200 " ret void\n" 201 "}"); 202 ExpectPath(true); 203 } 204 205 TEST_F(IsPotentiallyReachableTest, DestUnreachable) { 206 ParseAssembly( 207 "define void @test() {\n" 208 "entry:\n" 209 " br label %midblock\n" 210 "midblock:\n" 211 " %A = bitcast i8 undef to i8\n" 212 " ret void\n" 213 "unreachable:\n" 214 " %B = bitcast i8 undef to i8\n" 215 " br label %midblock\n" 216 "}"); 217 ExpectPath(false); 218 } 219 220 TEST_F(IsPotentiallyReachableTest, BranchToReturn) { 221 ParseAssembly( 222 "define void @test(i1 %x) {\n" 223 "entry:\n" 224 " %A = bitcast i8 undef to i8\n" 225 " br i1 %x, label %block1, label %block2\n" 226 "block1:\n" 227 " ret void\n" 228 "block2:\n" 229 " %B = bitcast i8 undef to i8\n" 230 " ret void\n" 231 "}"); 232 ExpectPath(true); 233 } 234 235 TEST_F(IsPotentiallyReachableTest, SimpleLoop1) { 236 ParseAssembly( 237 "declare i1 @switch()\n" 238 "\n" 239 "define void @test() {\n" 240 "entry:\n" 241 " br label %loop\n" 242 "loop:\n" 243 " %B = bitcast i8 undef to i8\n" 244 " %A = bitcast i8 undef to i8\n" 245 " %x = call i1 @switch()\n" 246 " br i1 %x, label %loop, label %exit\n" 247 "exit:\n" 248 " ret void\n" 249 "}"); 250 ExpectPath(true); 251 } 252 253 TEST_F(IsPotentiallyReachableTest, SimpleLoop2) { 254 ParseAssembly( 255 "declare i1 @switch()\n" 256 "\n" 257 "define void @test() {\n" 258 "entry:\n" 259 " %B = bitcast i8 undef to i8\n" 260 " br label %loop\n" 261 "loop:\n" 262 " %A = bitcast i8 undef to i8\n" 263 " %x = call i1 @switch()\n" 264 " br i1 %x, label %loop, label %exit\n" 265 "exit:\n" 266 " ret void\n" 267 "}"); 268 ExpectPath(false); 269 } 270 271 TEST_F(IsPotentiallyReachableTest, SimpleLoop3) { 272 ParseAssembly( 273 "declare i1 @switch()\n" 274 "\n" 275 "define void @test() {\n" 276 "entry:\n" 277 " br label %loop\n" 278 "loop:\n" 279 " %B = bitcast i8 undef to i8\n" 280 " %x = call i1 @switch()\n" 281 " br i1 %x, label %loop, label %exit\n" 282 "exit:\n" 283 " %A = bitcast i8 undef to i8\n" 284 " ret void\n" 285 "}"); 286 ExpectPath(false); 287 } 288 289 290 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) { 291 ParseAssembly( 292 "declare i1 @switch()\n" 293 "\n" 294 "define void @test() {\n" 295 "entry:\n" 296 " br label %loop1\n" 297 "loop1:\n" 298 " %A = bitcast i8 undef to i8\n" 299 " %x = call i1 @switch()\n" 300 " br i1 %x, label %loop1, label %loop1exit\n" 301 "loop1exit:\n" 302 " br label %loop2\n" 303 "loop2:\n" 304 " %B = bitcast i8 undef to i8\n" 305 " %y = call i1 @switch()\n" 306 " br i1 %x, label %loop2, label %loop2exit\n" 307 "loop2exit:" 308 " ret void\n" 309 "}"); 310 ExpectPath(true); 311 } 312 313 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) { 314 ParseAssembly( 315 "declare i1 @switch()\n" 316 "\n" 317 "define void @test() {\n" 318 "entry:\n" 319 " br label %loop1\n" 320 "loop1:\n" 321 " %B = bitcast i8 undef to i8\n" 322 " %x = call i1 @switch()\n" 323 " br i1 %x, label %loop1, label %loop1exit\n" 324 "loop1exit:\n" 325 " br label %loop2\n" 326 "loop2:\n" 327 " %A = bitcast i8 undef to i8\n" 328 " %y = call i1 @switch()\n" 329 " br i1 %x, label %loop2, label %loop2exit\n" 330 "loop2exit:" 331 " ret void\n" 332 "}"); 333 ExpectPath(false); 334 } 335 336 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) { 337 ParseAssembly( 338 "declare i1 @switch()\n" 339 "\n" 340 "define void @test() {\n" 341 "entry:\n" 342 " br label %outerloop3\n" 343 "outerloop3:\n" 344 " br label %innerloop1\n" 345 "innerloop1:\n" 346 " %B = bitcast i8 undef to i8\n" 347 " %x = call i1 @switch()\n" 348 " br i1 %x, label %innerloop1, label %innerloop1exit\n" 349 "innerloop1exit:\n" 350 " br label %innerloop2\n" 351 "innerloop2:\n" 352 " %A = bitcast i8 undef to i8\n" 353 " %y = call i1 @switch()\n" 354 " br i1 %x, label %innerloop2, label %innerloop2exit\n" 355 "innerloop2exit:" 356 " ;; In outer loop3 now.\n" 357 " %z = call i1 @switch()\n" 358 " br i1 %z, label %outerloop3, label %exit\n" 359 "exit:\n" 360 " ret void\n" 361 "}"); 362 ExpectPath(true); 363 } 364 365 static const char *BranchInsideLoopIR = 366 "declare i1 @switch()\n" 367 "\n" 368 "define void @test() {\n" 369 "entry:\n" 370 " br label %loop\n" 371 "loop:\n" 372 " %x = call i1 @switch()\n" 373 " br i1 %x, label %nextloopblock, label %exit\n" 374 "nextloopblock:\n" 375 " %y = call i1 @switch()\n" 376 " br i1 %y, label %left, label %right\n" 377 "left:\n" 378 " %A = bitcast i8 undef to i8\n" 379 " br label %loop\n" 380 "right:\n" 381 " %B = bitcast i8 undef to i8\n" 382 " br label %loop\n" 383 "exit:\n" 384 " ret void\n" 385 "}"; 386 387 TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) { 388 ParseAssembly(BranchInsideLoopIR); 389 ExpectPath(true); 390 } 391 392 TEST_F(IsPotentiallyReachableTest, ModifyTest) { 393 ParseAssembly(BranchInsideLoopIR); 394 395 succ_iterator S = succ_begin(&*++M->getFunction("test")->begin()); 396 BasicBlock *OldBB = S[0]; 397 S[0] = S[1]; 398 ExpectPath(false); 399 S[0] = OldBB; 400 ExpectPath(true); 401 } 402 403 TEST_F(IsPotentiallyReachableTest, UnreachableFromEntryTest) { 404 ParseAssembly("define void @test() {\n" 405 "entry:\n" 406 " %A = bitcast i8 undef to i8\n" 407 " ret void\n" 408 "not.reachable:\n" 409 " %B = bitcast i8 undef to i8\n" 410 " ret void\n" 411 "}"); 412 ExpectPath(false); 413 } 414 415 TEST_F(IsPotentiallyReachableTest, UnreachableBlocksTest1) { 416 ParseAssembly("define void @test() {\n" 417 "entry:\n" 418 " ret void\n" 419 "not.reachable.1:\n" 420 " %A = bitcast i8 undef to i8\n" 421 " br label %not.reachable.2\n" 422 "not.reachable.2:\n" 423 " %B = bitcast i8 undef to i8\n" 424 " ret void\n" 425 "}"); 426 ExpectPath(true); 427 } 428 429 TEST_F(IsPotentiallyReachableTest, UnreachableBlocksTest2) { 430 ParseAssembly("define void @test() {\n" 431 "entry:\n" 432 " ret void\n" 433 "not.reachable.1:\n" 434 " %B = bitcast i8 undef to i8\n" 435 " br label %not.reachable.2\n" 436 "not.reachable.2:\n" 437 " %A = bitcast i8 undef to i8\n" 438 " ret void\n" 439 "}"); 440 ExpectPath(false); 441 } 442 443 TEST_F(IsPotentiallyReachableTest, SimpleExclusionTest) { 444 ParseAssembly("define void @test() {\n" 445 "entry:\n" 446 " %A = bitcast i8 undef to i8\n" 447 " br label %excluded\n" 448 "excluded:\n" 449 " br label %exit\n" 450 "exit:\n" 451 " %B = bitcast i8 undef to i8\n" 452 " ret void\n" 453 "}"); 454 ExpectPath(false); 455 } 456 457 TEST_F(IsPotentiallyReachableTest, DiamondExcludedTest) { 458 ParseAssembly("declare i1 @switch()\n" 459 "\n" 460 "define void @test() {\n" 461 "entry:\n" 462 " %x = call i1 @switch()\n" 463 " %A = bitcast i8 undef to i8\n" 464 " br i1 %x, label %excluded.1, label %excluded.2\n" 465 "excluded.1:\n" 466 " br label %exit\n" 467 "excluded.2:\n" 468 " br label %exit\n" 469 "exit:\n" 470 " %B = bitcast i8 undef to i8\n" 471 " ret void\n" 472 "}"); 473 ExpectPath(false); 474 } 475 476 TEST_F(IsPotentiallyReachableTest, DiamondOneSideExcludedTest) { 477 ParseAssembly("declare i1 @switch()\n" 478 "\n" 479 "define void @test() {\n" 480 "entry:\n" 481 " %x = call i1 @switch()\n" 482 " %A = bitcast i8 undef to i8\n" 483 " br i1 %x, label %excluded, label %diamond\n" 484 "excluded:\n" 485 " br label %exit\n" 486 "diamond:\n" 487 " br label %exit\n" 488 "exit:\n" 489 " %B = bitcast i8 undef to i8\n" 490 " ret void\n" 491 "}"); 492 ExpectPath(true); 493 } 494 495 TEST_F(IsPotentiallyReachableTest, UnreachableToReachable) { 496 ParseAssembly("define void @test() {\n" 497 "entry:\n" 498 " br label %exit\n" 499 "unreachableblock:\n" 500 " %A = bitcast i8 undef to i8\n" 501 " br label %exit\n" 502 "exit:\n" 503 " %B = bitcast i8 undef to i8\n" 504 " ret void\n" 505 "}"); 506 ExpectPath(true); 507 } 508