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, StraightNoPath) { 151 ParseAssembly( 152 "define void @test() {\n" 153 "entry:\n" 154 " %B = bitcast i8 undef to i8\n" 155 " br label %exit\n" 156 "exit:\n" 157 " %A = bitcast i8 undef to i8\n" 158 " ret void\n" 159 "}"); 160 ExpectPath(false); 161 } 162 163 TEST_F(IsPotentiallyReachableTest, StraightPath) { 164 ParseAssembly( 165 "define void @test() {\n" 166 "entry:\n" 167 " %A = bitcast i8 undef to i8\n" 168 " br label %exit\n" 169 "exit:\n" 170 " %B = bitcast i8 undef to i8\n" 171 " ret void\n" 172 "}"); 173 ExpectPath(true); 174 } 175 176 TEST_F(IsPotentiallyReachableTest, DestUnreachable) { 177 ParseAssembly( 178 "define void @test() {\n" 179 "entry:\n" 180 " br label %midblock\n" 181 "midblock:\n" 182 " %A = bitcast i8 undef to i8\n" 183 " ret void\n" 184 "unreachable:\n" 185 " %B = bitcast i8 undef to i8\n" 186 " br label %midblock\n" 187 "}"); 188 ExpectPath(false); 189 } 190 191 TEST_F(IsPotentiallyReachableTest, BranchToReturn) { 192 ParseAssembly( 193 "define void @test(i1 %x) {\n" 194 "entry:\n" 195 " %A = bitcast i8 undef to i8\n" 196 " br i1 %x, label %block1, label %block2\n" 197 "block1:\n" 198 " ret void\n" 199 "block2:\n" 200 " %B = bitcast i8 undef to i8\n" 201 " ret void\n" 202 "}"); 203 ExpectPath(true); 204 } 205 206 TEST_F(IsPotentiallyReachableTest, SimpleLoop1) { 207 ParseAssembly( 208 "declare i1 @switch()\n" 209 "\n" 210 "define void @test() {\n" 211 "entry:\n" 212 " br label %loop\n" 213 "loop:\n" 214 " %B = bitcast i8 undef to i8\n" 215 " %A = bitcast i8 undef to i8\n" 216 " %x = call i1 @switch()\n" 217 " br i1 %x, label %loop, label %exit\n" 218 "exit:\n" 219 " ret void\n" 220 "}"); 221 ExpectPath(true); 222 } 223 224 TEST_F(IsPotentiallyReachableTest, SimpleLoop2) { 225 ParseAssembly( 226 "declare i1 @switch()\n" 227 "\n" 228 "define void @test() {\n" 229 "entry:\n" 230 " %B = bitcast i8 undef to i8\n" 231 " br label %loop\n" 232 "loop:\n" 233 " %A = bitcast i8 undef to i8\n" 234 " %x = call i1 @switch()\n" 235 " br i1 %x, label %loop, label %exit\n" 236 "exit:\n" 237 " ret void\n" 238 "}"); 239 ExpectPath(false); 240 } 241 242 TEST_F(IsPotentiallyReachableTest, SimpleLoop3) { 243 ParseAssembly( 244 "declare i1 @switch()\n" 245 "\n" 246 "define void @test() {\n" 247 "entry:\n" 248 " br label %loop\n" 249 "loop:\n" 250 " %B = 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 " %A = bitcast i8 undef to i8\n" 255 " ret void\n" 256 "}"); 257 ExpectPath(false); 258 } 259 260 261 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) { 262 ParseAssembly( 263 "declare i1 @switch()\n" 264 "\n" 265 "define void @test() {\n" 266 "entry:\n" 267 " br label %loop1\n" 268 "loop1:\n" 269 " %A = bitcast i8 undef to i8\n" 270 " %x = call i1 @switch()\n" 271 " br i1 %x, label %loop1, label %loop1exit\n" 272 "loop1exit:\n" 273 " br label %loop2\n" 274 "loop2:\n" 275 " %B = bitcast i8 undef to i8\n" 276 " %y = call i1 @switch()\n" 277 " br i1 %x, label %loop2, label %loop2exit\n" 278 "loop2exit:" 279 " ret void\n" 280 "}"); 281 ExpectPath(true); 282 } 283 284 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) { 285 ParseAssembly( 286 "declare i1 @switch()\n" 287 "\n" 288 "define void @test() {\n" 289 "entry:\n" 290 " br label %loop1\n" 291 "loop1:\n" 292 " %B = bitcast i8 undef to i8\n" 293 " %x = call i1 @switch()\n" 294 " br i1 %x, label %loop1, label %loop1exit\n" 295 "loop1exit:\n" 296 " br label %loop2\n" 297 "loop2:\n" 298 " %A = bitcast i8 undef to i8\n" 299 " %y = call i1 @switch()\n" 300 " br i1 %x, label %loop2, label %loop2exit\n" 301 "loop2exit:" 302 " ret void\n" 303 "}"); 304 ExpectPath(false); 305 } 306 307 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) { 308 ParseAssembly( 309 "declare i1 @switch()\n" 310 "\n" 311 "define void @test() {\n" 312 "entry:\n" 313 " br label %outerloop3\n" 314 "outerloop3:\n" 315 " br label %innerloop1\n" 316 "innerloop1:\n" 317 " %B = bitcast i8 undef to i8\n" 318 " %x = call i1 @switch()\n" 319 " br i1 %x, label %innerloop1, label %innerloop1exit\n" 320 "innerloop1exit:\n" 321 " br label %innerloop2\n" 322 "innerloop2:\n" 323 " %A = bitcast i8 undef to i8\n" 324 " %y = call i1 @switch()\n" 325 " br i1 %x, label %innerloop2, label %innerloop2exit\n" 326 "innerloop2exit:" 327 " ;; In outer loop3 now.\n" 328 " %z = call i1 @switch()\n" 329 " br i1 %z, label %outerloop3, label %exit\n" 330 "exit:\n" 331 " ret void\n" 332 "}"); 333 ExpectPath(true); 334 } 335 336 TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) { 337 ParseAssembly( 338 "declare i1 @switch()\n" 339 "\n" 340 "define void @test() {\n" 341 "entry:\n" 342 " br label %loop\n" 343 "loop:\n" 344 " %x = call i1 @switch()\n" 345 " br i1 %x, label %nextloopblock, label %exit\n" 346 "nextloopblock:\n" 347 " %y = call i1 @switch()\n" 348 " br i1 %y, label %left, label %right\n" 349 "left:\n" 350 " %A = bitcast i8 undef to i8\n" 351 " br label %loop\n" 352 "right:\n" 353 " %B = bitcast i8 undef to i8\n" 354 " br label %loop\n" 355 "exit:\n" 356 " ret void\n" 357 "}"); 358 ExpectPath(true); 359 } 360
