1 //===- CFGTest.cpp - CFG tests --------------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include "llvm/Analysis/CFG.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/Module.h" 18 #include "llvm/Pass.h" 19 #include "llvm/IR/LegacyPassManager.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, getGlobalContext()); 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(os.str().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 63 void ExpectPath(bool ExpectedResult) { 64 static char ID; 65 class IsPotentiallyReachableTestPass : public FunctionPass { 66 public: 67 IsPotentiallyReachableTestPass(bool ExpectedResult, 68 Instruction *A, Instruction *B) 69 : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B) {} 70 71 static int initialize() { 72 PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass", 73 "", &ID, nullptr, true, true); 74 PassRegistry::getPassRegistry()->registerPass(*PI, false); 75 initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry()); 76 initializeDominatorTreeWrapperPassPass( 77 *PassRegistry::getPassRegistry()); 78 return 0; 79 } 80 81 void getAnalysisUsage(AnalysisUsage &AU) const override { 82 AU.setPreservesAll(); 83 AU.addRequired<LoopInfoWrapperPass>(); 84 AU.addRequired<DominatorTreeWrapperPass>(); 85 } 86 87 bool runOnFunction(Function &F) override { 88 if (!F.hasName() || F.getName() != "test") 89 return false; 90 91 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 92 DominatorTree *DT = 93 &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 94 EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, nullptr), 95 ExpectedResult); 96 EXPECT_EQ(isPotentiallyReachable(A, B, DT, nullptr), ExpectedResult); 97 EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, LI), ExpectedResult); 98 EXPECT_EQ(isPotentiallyReachable(A, B, DT, LI), ExpectedResult); 99 return false; 100 } 101 bool ExpectedResult; 102 Instruction *A, *B; 103 }; 104 105 static int initialize = IsPotentiallyReachableTestPass::initialize(); 106 (void)initialize; 107 108 IsPotentiallyReachableTestPass *P = 109 new IsPotentiallyReachableTestPass(ExpectedResult, A, B); 110 legacy::PassManager PM; 111 PM.add(P); 112 PM.run(*M); 113 } 114 115 std::unique_ptr<Module> M; 116 Instruction *A, *B; 117 }; 118 119 } 120 121 TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) { 122 ParseAssembly( 123 "define void @test() {\n" 124 "entry:\n" 125 " bitcast i8 undef to i8\n" 126 " %B = bitcast i8 undef to i8\n" 127 " bitcast i8 undef to i8\n" 128 " bitcast i8 undef to i8\n" 129 " %A = bitcast i8 undef to i8\n" 130 " ret void\n" 131 "}\n"); 132 ExpectPath(false); 133 } 134 135 TEST_F(IsPotentiallyReachableTest, SameBlockPath) { 136 ParseAssembly( 137 "define void @test() {\n" 138 "entry:\n" 139 " %A = bitcast i8 undef to i8\n" 140 " bitcast i8 undef to i8\n" 141 " bitcast i8 undef to i8\n" 142 " %B = bitcast i8 undef to i8\n" 143 " ret void\n" 144 "}\n"); 145 ExpectPath(true); 146 } 147 148 TEST_F(IsPotentiallyReachableTest, SameBlockNoLoop) { 149 ParseAssembly( 150 "define void @test() {\n" 151 "entry:\n" 152 " br label %middle\n" 153 "middle:\n" 154 " %B = bitcast i8 undef to i8\n" 155 " bitcast i8 undef to i8\n" 156 " bitcast i8 undef to i8\n" 157 " %A = bitcast i8 undef to i8\n" 158 " br label %nextblock\n" 159 "nextblock:\n" 160 " ret void\n" 161 "}\n"); 162 ExpectPath(false); 163 } 164 165 TEST_F(IsPotentiallyReachableTest, StraightNoPath) { 166 ParseAssembly( 167 "define void @test() {\n" 168 "entry:\n" 169 " %B = bitcast i8 undef to i8\n" 170 " br label %exit\n" 171 "exit:\n" 172 " %A = bitcast i8 undef to i8\n" 173 " ret void\n" 174 "}"); 175 ExpectPath(false); 176 } 177 178 TEST_F(IsPotentiallyReachableTest, StraightPath) { 179 ParseAssembly( 180 "define void @test() {\n" 181 "entry:\n" 182 " %A = bitcast i8 undef to i8\n" 183 " br label %exit\n" 184 "exit:\n" 185 " %B = bitcast i8 undef to i8\n" 186 " ret void\n" 187 "}"); 188 ExpectPath(true); 189 } 190 191 TEST_F(IsPotentiallyReachableTest, DestUnreachable) { 192 ParseAssembly( 193 "define void @test() {\n" 194 "entry:\n" 195 " br label %midblock\n" 196 "midblock:\n" 197 " %A = bitcast i8 undef to i8\n" 198 " ret void\n" 199 "unreachable:\n" 200 " %B = bitcast i8 undef to i8\n" 201 " br label %midblock\n" 202 "}"); 203 ExpectPath(false); 204 } 205 206 TEST_F(IsPotentiallyReachableTest, BranchToReturn) { 207 ParseAssembly( 208 "define void @test(i1 %x) {\n" 209 "entry:\n" 210 " %A = bitcast i8 undef to i8\n" 211 " br i1 %x, label %block1, label %block2\n" 212 "block1:\n" 213 " ret void\n" 214 "block2:\n" 215 " %B = bitcast i8 undef to i8\n" 216 " ret void\n" 217 "}"); 218 ExpectPath(true); 219 } 220 221 TEST_F(IsPotentiallyReachableTest, SimpleLoop1) { 222 ParseAssembly( 223 "declare i1 @switch()\n" 224 "\n" 225 "define void @test() {\n" 226 "entry:\n" 227 " br label %loop\n" 228 "loop:\n" 229 " %B = bitcast i8 undef to i8\n" 230 " %A = bitcast i8 undef to i8\n" 231 " %x = call i1 @switch()\n" 232 " br i1 %x, label %loop, label %exit\n" 233 "exit:\n" 234 " ret void\n" 235 "}"); 236 ExpectPath(true); 237 } 238 239 TEST_F(IsPotentiallyReachableTest, SimpleLoop2) { 240 ParseAssembly( 241 "declare i1 @switch()\n" 242 "\n" 243 "define void @test() {\n" 244 "entry:\n" 245 " %B = bitcast i8 undef to i8\n" 246 " br label %loop\n" 247 "loop:\n" 248 " %A = bitcast i8 undef to i8\n" 249 " %x = call i1 @switch()\n" 250 " br i1 %x, label %loop, label %exit\n" 251 "exit:\n" 252 " ret void\n" 253 "}"); 254 ExpectPath(false); 255 } 256 257 TEST_F(IsPotentiallyReachableTest, SimpleLoop3) { 258 ParseAssembly( 259 "declare i1 @switch()\n" 260 "\n" 261 "define void @test() {\n" 262 "entry:\n" 263 " br label %loop\n" 264 "loop:\n" 265 " %B = bitcast i8 undef to i8\n" 266 " %x = call i1 @switch()\n" 267 " br i1 %x, label %loop, label %exit\n" 268 "exit:\n" 269 " %A = bitcast i8 undef to i8\n" 270 " ret void\n" 271 "}"); 272 ExpectPath(false); 273 } 274 275 276 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) { 277 ParseAssembly( 278 "declare i1 @switch()\n" 279 "\n" 280 "define void @test() {\n" 281 "entry:\n" 282 " br label %loop1\n" 283 "loop1:\n" 284 " %A = bitcast i8 undef to i8\n" 285 " %x = call i1 @switch()\n" 286 " br i1 %x, label %loop1, label %loop1exit\n" 287 "loop1exit:\n" 288 " br label %loop2\n" 289 "loop2:\n" 290 " %B = bitcast i8 undef to i8\n" 291 " %y = call i1 @switch()\n" 292 " br i1 %x, label %loop2, label %loop2exit\n" 293 "loop2exit:" 294 " ret void\n" 295 "}"); 296 ExpectPath(true); 297 } 298 299 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) { 300 ParseAssembly( 301 "declare i1 @switch()\n" 302 "\n" 303 "define void @test() {\n" 304 "entry:\n" 305 " br label %loop1\n" 306 "loop1:\n" 307 " %B = bitcast i8 undef to i8\n" 308 " %x = call i1 @switch()\n" 309 " br i1 %x, label %loop1, label %loop1exit\n" 310 "loop1exit:\n" 311 " br label %loop2\n" 312 "loop2:\n" 313 " %A = bitcast i8 undef to i8\n" 314 " %y = call i1 @switch()\n" 315 " br i1 %x, label %loop2, label %loop2exit\n" 316 "loop2exit:" 317 " ret void\n" 318 "}"); 319 ExpectPath(false); 320 } 321 322 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) { 323 ParseAssembly( 324 "declare i1 @switch()\n" 325 "\n" 326 "define void @test() {\n" 327 "entry:\n" 328 " br label %outerloop3\n" 329 "outerloop3:\n" 330 " br label %innerloop1\n" 331 "innerloop1:\n" 332 " %B = bitcast i8 undef to i8\n" 333 " %x = call i1 @switch()\n" 334 " br i1 %x, label %innerloop1, label %innerloop1exit\n" 335 "innerloop1exit:\n" 336 " br label %innerloop2\n" 337 "innerloop2:\n" 338 " %A = bitcast i8 undef to i8\n" 339 " %y = call i1 @switch()\n" 340 " br i1 %x, label %innerloop2, label %innerloop2exit\n" 341 "innerloop2exit:" 342 " ;; In outer loop3 now.\n" 343 " %z = call i1 @switch()\n" 344 " br i1 %z, label %outerloop3, label %exit\n" 345 "exit:\n" 346 " ret void\n" 347 "}"); 348 ExpectPath(true); 349 } 350 351 static const char *BranchInsideLoopIR = 352 "declare i1 @switch()\n" 353 "\n" 354 "define void @test() {\n" 355 "entry:\n" 356 " br label %loop\n" 357 "loop:\n" 358 " %x = call i1 @switch()\n" 359 " br i1 %x, label %nextloopblock, label %exit\n" 360 "nextloopblock:\n" 361 " %y = call i1 @switch()\n" 362 " br i1 %y, label %left, label %right\n" 363 "left:\n" 364 " %A = bitcast i8 undef to i8\n" 365 " br label %loop\n" 366 "right:\n" 367 " %B = bitcast i8 undef to i8\n" 368 " br label %loop\n" 369 "exit:\n" 370 " ret void\n" 371 "}"; 372 373 TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) { 374 ParseAssembly(BranchInsideLoopIR); 375 ExpectPath(true); 376 } 377 378 TEST_F(IsPotentiallyReachableTest, ModifyTest) { 379 ParseAssembly(BranchInsideLoopIR); 380 381 succ_iterator S = succ_begin(++M->getFunction("test")->begin()); 382 BasicBlock *OldBB = S[0]; 383 S[0] = S[1]; 384 ExpectPath(false); 385 S[0] = OldBB; 386 ExpectPath(true); 387 } 388
