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, Context);
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 LLVMContext Context;
116 std::unique_ptr<Module> M;
117 Instruction *A, *B;
118 };
119
120 }
121
TEST_F(IsPotentiallyReachableTest,SameBlockNoPath)122 TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) {
123 ParseAssembly(
124 "define void @test() {\n"
125 "entry:\n"
126 " bitcast i8 undef to i8\n"
127 " %B = bitcast i8 undef to i8\n"
128 " bitcast i8 undef to i8\n"
129 " bitcast i8 undef to i8\n"
130 " %A = bitcast i8 undef to i8\n"
131 " ret void\n"
132 "}\n");
133 ExpectPath(false);
134 }
135
TEST_F(IsPotentiallyReachableTest,SameBlockPath)136 TEST_F(IsPotentiallyReachableTest, SameBlockPath) {
137 ParseAssembly(
138 "define void @test() {\n"
139 "entry:\n"
140 " %A = bitcast i8 undef to i8\n"
141 " bitcast i8 undef to i8\n"
142 " bitcast i8 undef to i8\n"
143 " %B = bitcast i8 undef to i8\n"
144 " ret void\n"
145 "}\n");
146 ExpectPath(true);
147 }
148
TEST_F(IsPotentiallyReachableTest,SameBlockNoLoop)149 TEST_F(IsPotentiallyReachableTest, SameBlockNoLoop) {
150 ParseAssembly(
151 "define void @test() {\n"
152 "entry:\n"
153 " br label %middle\n"
154 "middle:\n"
155 " %B = bitcast i8 undef to i8\n"
156 " bitcast i8 undef to i8\n"
157 " bitcast i8 undef to i8\n"
158 " %A = bitcast i8 undef to i8\n"
159 " br label %nextblock\n"
160 "nextblock:\n"
161 " ret void\n"
162 "}\n");
163 ExpectPath(false);
164 }
165
TEST_F(IsPotentiallyReachableTest,StraightNoPath)166 TEST_F(IsPotentiallyReachableTest, StraightNoPath) {
167 ParseAssembly(
168 "define void @test() {\n"
169 "entry:\n"
170 " %B = bitcast i8 undef to i8\n"
171 " br label %exit\n"
172 "exit:\n"
173 " %A = bitcast i8 undef to i8\n"
174 " ret void\n"
175 "}");
176 ExpectPath(false);
177 }
178
TEST_F(IsPotentiallyReachableTest,StraightPath)179 TEST_F(IsPotentiallyReachableTest, StraightPath) {
180 ParseAssembly(
181 "define void @test() {\n"
182 "entry:\n"
183 " %A = bitcast i8 undef to i8\n"
184 " br label %exit\n"
185 "exit:\n"
186 " %B = bitcast i8 undef to i8\n"
187 " ret void\n"
188 "}");
189 ExpectPath(true);
190 }
191
TEST_F(IsPotentiallyReachableTest,DestUnreachable)192 TEST_F(IsPotentiallyReachableTest, DestUnreachable) {
193 ParseAssembly(
194 "define void @test() {\n"
195 "entry:\n"
196 " br label %midblock\n"
197 "midblock:\n"
198 " %A = bitcast i8 undef to i8\n"
199 " ret void\n"
200 "unreachable:\n"
201 " %B = bitcast i8 undef to i8\n"
202 " br label %midblock\n"
203 "}");
204 ExpectPath(false);
205 }
206
TEST_F(IsPotentiallyReachableTest,BranchToReturn)207 TEST_F(IsPotentiallyReachableTest, BranchToReturn) {
208 ParseAssembly(
209 "define void @test(i1 %x) {\n"
210 "entry:\n"
211 " %A = bitcast i8 undef to i8\n"
212 " br i1 %x, label %block1, label %block2\n"
213 "block1:\n"
214 " ret void\n"
215 "block2:\n"
216 " %B = bitcast i8 undef to i8\n"
217 " ret void\n"
218 "}");
219 ExpectPath(true);
220 }
221
TEST_F(IsPotentiallyReachableTest,SimpleLoop1)222 TEST_F(IsPotentiallyReachableTest, SimpleLoop1) {
223 ParseAssembly(
224 "declare i1 @switch()\n"
225 "\n"
226 "define void @test() {\n"
227 "entry:\n"
228 " br label %loop\n"
229 "loop:\n"
230 " %B = bitcast i8 undef to i8\n"
231 " %A = bitcast i8 undef to i8\n"
232 " %x = call i1 @switch()\n"
233 " br i1 %x, label %loop, label %exit\n"
234 "exit:\n"
235 " ret void\n"
236 "}");
237 ExpectPath(true);
238 }
239
TEST_F(IsPotentiallyReachableTest,SimpleLoop2)240 TEST_F(IsPotentiallyReachableTest, SimpleLoop2) {
241 ParseAssembly(
242 "declare i1 @switch()\n"
243 "\n"
244 "define void @test() {\n"
245 "entry:\n"
246 " %B = bitcast i8 undef to i8\n"
247 " br label %loop\n"
248 "loop:\n"
249 " %A = bitcast i8 undef to i8\n"
250 " %x = call i1 @switch()\n"
251 " br i1 %x, label %loop, label %exit\n"
252 "exit:\n"
253 " ret void\n"
254 "}");
255 ExpectPath(false);
256 }
257
TEST_F(IsPotentiallyReachableTest,SimpleLoop3)258 TEST_F(IsPotentiallyReachableTest, SimpleLoop3) {
259 ParseAssembly(
260 "declare i1 @switch()\n"
261 "\n"
262 "define void @test() {\n"
263 "entry:\n"
264 " br label %loop\n"
265 "loop:\n"
266 " %B = bitcast i8 undef to i8\n"
267 " %x = call i1 @switch()\n"
268 " br i1 %x, label %loop, label %exit\n"
269 "exit:\n"
270 " %A = bitcast i8 undef to i8\n"
271 " ret void\n"
272 "}");
273 ExpectPath(false);
274 }
275
276
TEST_F(IsPotentiallyReachableTest,OneLoopAfterTheOther1)277 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) {
278 ParseAssembly(
279 "declare i1 @switch()\n"
280 "\n"
281 "define void @test() {\n"
282 "entry:\n"
283 " br label %loop1\n"
284 "loop1:\n"
285 " %A = bitcast i8 undef to i8\n"
286 " %x = call i1 @switch()\n"
287 " br i1 %x, label %loop1, label %loop1exit\n"
288 "loop1exit:\n"
289 " br label %loop2\n"
290 "loop2:\n"
291 " %B = bitcast i8 undef to i8\n"
292 " %y = call i1 @switch()\n"
293 " br i1 %x, label %loop2, label %loop2exit\n"
294 "loop2exit:"
295 " ret void\n"
296 "}");
297 ExpectPath(true);
298 }
299
TEST_F(IsPotentiallyReachableTest,OneLoopAfterTheOther2)300 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) {
301 ParseAssembly(
302 "declare i1 @switch()\n"
303 "\n"
304 "define void @test() {\n"
305 "entry:\n"
306 " br label %loop1\n"
307 "loop1:\n"
308 " %B = bitcast i8 undef to i8\n"
309 " %x = call i1 @switch()\n"
310 " br i1 %x, label %loop1, label %loop1exit\n"
311 "loop1exit:\n"
312 " br label %loop2\n"
313 "loop2:\n"
314 " %A = bitcast i8 undef to i8\n"
315 " %y = call i1 @switch()\n"
316 " br i1 %x, label %loop2, label %loop2exit\n"
317 "loop2exit:"
318 " ret void\n"
319 "}");
320 ExpectPath(false);
321 }
322
TEST_F(IsPotentiallyReachableTest,OneLoopAfterTheOtherInsideAThirdLoop)323 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) {
324 ParseAssembly(
325 "declare i1 @switch()\n"
326 "\n"
327 "define void @test() {\n"
328 "entry:\n"
329 " br label %outerloop3\n"
330 "outerloop3:\n"
331 " br label %innerloop1\n"
332 "innerloop1:\n"
333 " %B = bitcast i8 undef to i8\n"
334 " %x = call i1 @switch()\n"
335 " br i1 %x, label %innerloop1, label %innerloop1exit\n"
336 "innerloop1exit:\n"
337 " br label %innerloop2\n"
338 "innerloop2:\n"
339 " %A = bitcast i8 undef to i8\n"
340 " %y = call i1 @switch()\n"
341 " br i1 %x, label %innerloop2, label %innerloop2exit\n"
342 "innerloop2exit:"
343 " ;; In outer loop3 now.\n"
344 " %z = call i1 @switch()\n"
345 " br i1 %z, label %outerloop3, label %exit\n"
346 "exit:\n"
347 " ret void\n"
348 "}");
349 ExpectPath(true);
350 }
351
352 static const char *BranchInsideLoopIR =
353 "declare i1 @switch()\n"
354 "\n"
355 "define void @test() {\n"
356 "entry:\n"
357 " br label %loop\n"
358 "loop:\n"
359 " %x = call i1 @switch()\n"
360 " br i1 %x, label %nextloopblock, label %exit\n"
361 "nextloopblock:\n"
362 " %y = call i1 @switch()\n"
363 " br i1 %y, label %left, label %right\n"
364 "left:\n"
365 " %A = bitcast i8 undef to i8\n"
366 " br label %loop\n"
367 "right:\n"
368 " %B = bitcast i8 undef to i8\n"
369 " br label %loop\n"
370 "exit:\n"
371 " ret void\n"
372 "}";
373
TEST_F(IsPotentiallyReachableTest,BranchInsideLoop)374 TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) {
375 ParseAssembly(BranchInsideLoopIR);
376 ExpectPath(true);
377 }
378
TEST_F(IsPotentiallyReachableTest,ModifyTest)379 TEST_F(IsPotentiallyReachableTest, ModifyTest) {
380 ParseAssembly(BranchInsideLoopIR);
381
382 succ_iterator S = succ_begin(&*++M->getFunction("test")->begin());
383 BasicBlock *OldBB = S[0];
384 S[0] = S[1];
385 ExpectPath(false);
386 S[0] = OldBB;
387 ExpectPath(true);
388 }
389