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