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, 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(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 LLVMContext Context; 116 std::unique_ptr<Module> M; 117 Instruction *A, *B; 118 }; 119 120 } 121 122 TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) { 123 ParseAssembly( 124 "define void @test() {\n" 125 "entry:\n" 126 " bitcast i8 undef to i8\n" 127 " %B = bitcast i8 undef to i8\n" 128 " bitcast i8 undef to i8\n" 129 " bitcast i8 undef to i8\n" 130 " %A = bitcast i8 undef to i8\n" 131 " ret void\n" 132 "}\n"); 133 ExpectPath(false); 134 } 135 136 TEST_F(IsPotentiallyReachableTest, SameBlockPath) { 137 ParseAssembly( 138 "define void @test() {\n" 139 "entry:\n" 140 " %A = bitcast i8 undef to i8\n" 141 " bitcast i8 undef to i8\n" 142 " bitcast i8 undef to i8\n" 143 " %B = bitcast i8 undef to i8\n" 144 " ret void\n" 145 "}\n"); 146 ExpectPath(true); 147 } 148 149 TEST_F(IsPotentiallyReachableTest, SameBlockNoLoop) { 150 ParseAssembly( 151 "define void @test() {\n" 152 "entry:\n" 153 " br label %middle\n" 154 "middle:\n" 155 " %B = bitcast i8 undef to i8\n" 156 " bitcast i8 undef to i8\n" 157 " bitcast i8 undef to i8\n" 158 " %A = bitcast i8 undef to i8\n" 159 " br label %nextblock\n" 160 "nextblock:\n" 161 " ret void\n" 162 "}\n"); 163 ExpectPath(false); 164 } 165 166 TEST_F(IsPotentiallyReachableTest, StraightNoPath) { 167 ParseAssembly( 168 "define void @test() {\n" 169 "entry:\n" 170 " %B = bitcast i8 undef to i8\n" 171 " br label %exit\n" 172 "exit:\n" 173 " %A = bitcast i8 undef to i8\n" 174 " ret void\n" 175 "}"); 176 ExpectPath(false); 177 } 178 179 TEST_F(IsPotentiallyReachableTest, StraightPath) { 180 ParseAssembly( 181 "define void @test() {\n" 182 "entry:\n" 183 " %A = bitcast i8 undef to i8\n" 184 " br label %exit\n" 185 "exit:\n" 186 " %B = bitcast i8 undef to i8\n" 187 " ret void\n" 188 "}"); 189 ExpectPath(true); 190 } 191 192 TEST_F(IsPotentiallyReachableTest, DestUnreachable) { 193 ParseAssembly( 194 "define void @test() {\n" 195 "entry:\n" 196 " br label %midblock\n" 197 "midblock:\n" 198 " %A = bitcast i8 undef to i8\n" 199 " ret void\n" 200 "unreachable:\n" 201 " %B = bitcast i8 undef to i8\n" 202 " br label %midblock\n" 203 "}"); 204 ExpectPath(false); 205 } 206 207 TEST_F(IsPotentiallyReachableTest, BranchToReturn) { 208 ParseAssembly( 209 "define void @test(i1 %x) {\n" 210 "entry:\n" 211 " %A = bitcast i8 undef to i8\n" 212 " br i1 %x, label %block1, label %block2\n" 213 "block1:\n" 214 " ret void\n" 215 "block2:\n" 216 " %B = bitcast i8 undef to i8\n" 217 " ret void\n" 218 "}"); 219 ExpectPath(true); 220 } 221 222 TEST_F(IsPotentiallyReachableTest, SimpleLoop1) { 223 ParseAssembly( 224 "declare i1 @switch()\n" 225 "\n" 226 "define void @test() {\n" 227 "entry:\n" 228 " br label %loop\n" 229 "loop:\n" 230 " %B = bitcast i8 undef to i8\n" 231 " %A = bitcast i8 undef to i8\n" 232 " %x = call i1 @switch()\n" 233 " br i1 %x, label %loop, label %exit\n" 234 "exit:\n" 235 " ret void\n" 236 "}"); 237 ExpectPath(true); 238 } 239 240 TEST_F(IsPotentiallyReachableTest, SimpleLoop2) { 241 ParseAssembly( 242 "declare i1 @switch()\n" 243 "\n" 244 "define void @test() {\n" 245 "entry:\n" 246 " %B = bitcast i8 undef to i8\n" 247 " br label %loop\n" 248 "loop:\n" 249 " %A = bitcast i8 undef to i8\n" 250 " %x = call i1 @switch()\n" 251 " br i1 %x, label %loop, label %exit\n" 252 "exit:\n" 253 " ret void\n" 254 "}"); 255 ExpectPath(false); 256 } 257 258 TEST_F(IsPotentiallyReachableTest, SimpleLoop3) { 259 ParseAssembly( 260 "declare i1 @switch()\n" 261 "\n" 262 "define void @test() {\n" 263 "entry:\n" 264 " br label %loop\n" 265 "loop:\n" 266 " %B = bitcast i8 undef to i8\n" 267 " %x = call i1 @switch()\n" 268 " br i1 %x, label %loop, label %exit\n" 269 "exit:\n" 270 " %A = bitcast i8 undef to i8\n" 271 " ret void\n" 272 "}"); 273 ExpectPath(false); 274 } 275 276 277 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) { 278 ParseAssembly( 279 "declare i1 @switch()\n" 280 "\n" 281 "define void @test() {\n" 282 "entry:\n" 283 " br label %loop1\n" 284 "loop1:\n" 285 " %A = bitcast i8 undef to i8\n" 286 " %x = call i1 @switch()\n" 287 " br i1 %x, label %loop1, label %loop1exit\n" 288 "loop1exit:\n" 289 " br label %loop2\n" 290 "loop2:\n" 291 " %B = bitcast i8 undef to i8\n" 292 " %y = call i1 @switch()\n" 293 " br i1 %x, label %loop2, label %loop2exit\n" 294 "loop2exit:" 295 " ret void\n" 296 "}"); 297 ExpectPath(true); 298 } 299 300 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) { 301 ParseAssembly( 302 "declare i1 @switch()\n" 303 "\n" 304 "define void @test() {\n" 305 "entry:\n" 306 " br label %loop1\n" 307 "loop1:\n" 308 " %B = bitcast i8 undef to i8\n" 309 " %x = call i1 @switch()\n" 310 " br i1 %x, label %loop1, label %loop1exit\n" 311 "loop1exit:\n" 312 " br label %loop2\n" 313 "loop2:\n" 314 " %A = bitcast i8 undef to i8\n" 315 " %y = call i1 @switch()\n" 316 " br i1 %x, label %loop2, label %loop2exit\n" 317 "loop2exit:" 318 " ret void\n" 319 "}"); 320 ExpectPath(false); 321 } 322 323 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) { 324 ParseAssembly( 325 "declare i1 @switch()\n" 326 "\n" 327 "define void @test() {\n" 328 "entry:\n" 329 " br label %outerloop3\n" 330 "outerloop3:\n" 331 " br label %innerloop1\n" 332 "innerloop1:\n" 333 " %B = bitcast i8 undef to i8\n" 334 " %x = call i1 @switch()\n" 335 " br i1 %x, label %innerloop1, label %innerloop1exit\n" 336 "innerloop1exit:\n" 337 " br label %innerloop2\n" 338 "innerloop2:\n" 339 " %A = bitcast i8 undef to i8\n" 340 " %y = call i1 @switch()\n" 341 " br i1 %x, label %innerloop2, label %innerloop2exit\n" 342 "innerloop2exit:" 343 " ;; In outer loop3 now.\n" 344 " %z = call i1 @switch()\n" 345 " br i1 %z, label %outerloop3, label %exit\n" 346 "exit:\n" 347 " ret void\n" 348 "}"); 349 ExpectPath(true); 350 } 351 352 static const char *BranchInsideLoopIR = 353 "declare i1 @switch()\n" 354 "\n" 355 "define void @test() {\n" 356 "entry:\n" 357 " br label %loop\n" 358 "loop:\n" 359 " %x = call i1 @switch()\n" 360 " br i1 %x, label %nextloopblock, label %exit\n" 361 "nextloopblock:\n" 362 " %y = call i1 @switch()\n" 363 " br i1 %y, label %left, label %right\n" 364 "left:\n" 365 " %A = bitcast i8 undef to i8\n" 366 " br label %loop\n" 367 "right:\n" 368 " %B = bitcast i8 undef to i8\n" 369 " br label %loop\n" 370 "exit:\n" 371 " ret void\n" 372 "}"; 373 374 TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) { 375 ParseAssembly(BranchInsideLoopIR); 376 ExpectPath(true); 377 } 378 379 TEST_F(IsPotentiallyReachableTest, ModifyTest) { 380 ParseAssembly(BranchInsideLoopIR); 381 382 succ_iterator S = succ_begin(&*++M->getFunction("test")->begin()); 383 BasicBlock *OldBB = S[0]; 384 S[0] = S[1]; 385 ExpectPath(false); 386 S[0] = OldBB; 387 ExpectPath(true); 388 } 389
