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/LoopInfo.h"
13 #include "llvm/AsmParser/Parser.h"
14 #include "llvm/IR/Dominators.h"
15 #include "llvm/IR/Function.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/InstIterator.h"
22 #include "llvm/Support/SourceMgr.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         initializeDominatorTreeWrapperPassPass(
82             *PassRegistry::getPassRegistry());
83         return 0;
84       }
85 
86       void getAnalysisUsage(AnalysisUsage &AU) const {
87         AU.setPreservesAll();
88         AU.addRequired<LoopInfo>();
89         AU.addRequired<DominatorTreeWrapperPass>();
90       }
91 
92       bool runOnFunction(Function &F) {
93         if (!F.hasName() || F.getName() != "test")
94           return false;
95 
96         LoopInfo *LI = &getAnalysis<LoopInfo>();
97         DominatorTree *DT =
98             &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
99         EXPECT_EQ(isPotentiallyReachable(A, B, 0, 0), ExpectedResult);
100         EXPECT_EQ(isPotentiallyReachable(A, B, DT, 0), ExpectedResult);
101         EXPECT_EQ(isPotentiallyReachable(A, B, 0, 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   OwningPtr<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