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:
ParseAssembly(const char * Assembly)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
ExpectPath(bool ExpectedResult)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
TEST_F(IsPotentiallyReachableTest,SameBlockNoPath)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
TEST_F(IsPotentiallyReachableTest,SameBlockPath)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
TEST_F(IsPotentiallyReachableTest,StraightNoPath)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
TEST_F(IsPotentiallyReachableTest,StraightPath)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
TEST_F(IsPotentiallyReachableTest,DestUnreachable)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
TEST_F(IsPotentiallyReachableTest,BranchToReturn)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
TEST_F(IsPotentiallyReachableTest,SimpleLoop1)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
TEST_F(IsPotentiallyReachableTest,SimpleLoop2)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
TEST_F(IsPotentiallyReachableTest,SimpleLoop3)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
TEST_F(IsPotentiallyReachableTest,OneLoopAfterTheOther1)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
TEST_F(IsPotentiallyReachableTest,OneLoopAfterTheOther2)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
TEST_F(IsPotentiallyReachableTest,OneLoopAfterTheOtherInsideAThirdLoop)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
TEST_F(IsPotentiallyReachableTest,BranchInsideLoop)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