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/PassManager.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:
ParseAssembly(const char * Assembly)32 void ParseAssembly(const char *Assembly) {
33 M.reset(new Module("Module", getGlobalContext()));
34
35 SMDiagnostic Error;
36 bool Parsed = ParseAssemblyString(Assembly, M.get(),
37 Error, M->getContext()) == M.get();
38
39 std::string errMsg;
40 raw_string_ostream os(errMsg);
41 Error.print("", os);
42
43 if (!Parsed) {
44 // A failure here means that the test itself is buggy.
45 report_fatal_error(os.str().c_str());
46 }
47
48 Function *F = M->getFunction("test");
49 if (F == nullptr)
50 report_fatal_error("Test must have a function named @test");
51
52 A = B = nullptr;
53 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
54 if (I->hasName()) {
55 if (I->getName() == "A")
56 A = &*I;
57 else if (I->getName() == "B")
58 B = &*I;
59 }
60 }
61 if (A == nullptr)
62 report_fatal_error("@test must have an instruction %A");
63 if (B == nullptr)
64 report_fatal_error("@test must have an instruction %B");
65 }
66
ExpectPath(bool ExpectedResult)67 void ExpectPath(bool ExpectedResult) {
68 static char ID;
69 class IsPotentiallyReachableTestPass : public FunctionPass {
70 public:
71 IsPotentiallyReachableTestPass(bool ExpectedResult,
72 Instruction *A, Instruction *B)
73 : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B) {}
74
75 static int initialize() {
76 PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass",
77 "", &ID, nullptr, true, true);
78 PassRegistry::getPassRegistry()->registerPass(*PI, false);
79 initializeLoopInfoPass(*PassRegistry::getPassRegistry());
80 initializeDominatorTreeWrapperPassPass(
81 *PassRegistry::getPassRegistry());
82 return 0;
83 }
84
85 void getAnalysisUsage(AnalysisUsage &AU) const {
86 AU.setPreservesAll();
87 AU.addRequired<LoopInfo>();
88 AU.addRequired<DominatorTreeWrapperPass>();
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 =
97 &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
98 EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, nullptr),
99 ExpectedResult);
100 EXPECT_EQ(isPotentiallyReachable(A, B, DT, nullptr), ExpectedResult);
101 EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, 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 std::unique_ptr<Module> M;
120 Instruction *A, *B;
121 };
122
123 }
124
TEST_F(IsPotentiallyReachableTest,SameBlockNoPath)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
TEST_F(IsPotentiallyReachableTest,SameBlockPath)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
TEST_F(IsPotentiallyReachableTest,SameBlockNoLoop)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
TEST_F(IsPotentiallyReachableTest,StraightNoPath)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
TEST_F(IsPotentiallyReachableTest,StraightPath)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
TEST_F(IsPotentiallyReachableTest,DestUnreachable)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
TEST_F(IsPotentiallyReachableTest,BranchToReturn)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
TEST_F(IsPotentiallyReachableTest,SimpleLoop1)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
TEST_F(IsPotentiallyReachableTest,SimpleLoop2)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
TEST_F(IsPotentiallyReachableTest,SimpleLoop3)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
TEST_F(IsPotentiallyReachableTest,OneLoopAfterTheOther1)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
TEST_F(IsPotentiallyReachableTest,OneLoopAfterTheOther2)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
TEST_F(IsPotentiallyReachableTest,OneLoopAfterTheOtherInsideAThirdLoop)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
TEST_F(IsPotentiallyReachableTest,BranchInsideLoop)377 TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) {
378 ParseAssembly(BranchInsideLoopIR);
379 ExpectPath(true);
380 }
381
TEST_F(IsPotentiallyReachableTest,ModifyTest)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