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