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