1 | //===- CFGTest.cpp - CFG tests --------------------------------------------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | |
9 | #include "llvm/Analysis/CFG.h" |
10 | #include "llvm/ADT/SmallPtrSet.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/LegacyPassManager.h" |
18 | #include "llvm/IR/Module.h" |
19 | #include "llvm/InitializePasses.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: |
32 | void ParseAssembly(const char *Assembly) { |
33 | SMDiagnostic Error; |
34 | M = parseAssemblyString(AsmString: Assembly, Err&: Error, Context); |
35 | |
36 | std::string errMsg; |
37 | raw_string_ostream os(errMsg); |
38 | Error.print(ProgName: "" , S&: os); |
39 | |
40 | // A failure here means that the test itself is buggy. |
41 | if (!M) |
42 | report_fatal_error(reason: os.str().c_str()); |
43 | |
44 | Function *F = M->getFunction(Name: "test" ); |
45 | if (F == nullptr) |
46 | report_fatal_error(reason: "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(reason: "@test must have an instruction %A" ); |
59 | if (B == nullptr) |
60 | report_fatal_error(reason: "@test must have an instruction %B" ); |
61 | |
62 | assert(ExclusionSet.empty()); |
63 | for (auto I = F->begin(), E = F->end(); I != E; ++I) { |
64 | if (I->hasName() && I->getName().starts_with(Prefix: "excluded" )) |
65 | ExclusionSet.insert(Ptr: &*I); |
66 | } |
67 | } |
68 | |
69 | void ExpectPath(bool ExpectedResult) { |
70 | static char ID; |
71 | class IsPotentiallyReachableTestPass : public FunctionPass { |
72 | public: |
73 | IsPotentiallyReachableTestPass(bool ExpectedResult, Instruction *A, |
74 | Instruction *B, |
75 | SmallPtrSet<BasicBlock *, 4> ExclusionSet) |
76 | : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B), |
77 | ExclusionSet(ExclusionSet) {} |
78 | |
79 | static int initialize() { |
80 | PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass" , "" , |
81 | &ID, nullptr, true, true); |
82 | PassRegistry::getPassRegistry()->registerPass(PI: *PI, ShouldFree: true); |
83 | initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry()); |
84 | initializeDominatorTreeWrapperPassPass( |
85 | *PassRegistry::getPassRegistry()); |
86 | return 0; |
87 | } |
88 | |
89 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
90 | AU.setPreservesAll(); |
91 | AU.addRequired<LoopInfoWrapperPass>(); |
92 | AU.addRequired<DominatorTreeWrapperPass>(); |
93 | } |
94 | |
95 | bool runOnFunction(Function &F) override { |
96 | if (!F.hasName() || F.getName() != "test" ) |
97 | return false; |
98 | |
99 | LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
100 | DominatorTree *DT = |
101 | &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
102 | EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, nullptr, nullptr), |
103 | ExpectedResult); |
104 | EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, DT, nullptr), |
105 | ExpectedResult); |
106 | EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, nullptr, LI), |
107 | ExpectedResult); |
108 | EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, DT, LI), |
109 | ExpectedResult); |
110 | return false; |
111 | } |
112 | bool ExpectedResult; |
113 | Instruction *A, *B; |
114 | SmallPtrSet<BasicBlock *, 4> ExclusionSet; |
115 | }; |
116 | |
117 | static int initialize = IsPotentiallyReachableTestPass::initialize(); |
118 | (void)initialize; |
119 | |
120 | IsPotentiallyReachableTestPass *P = |
121 | new IsPotentiallyReachableTestPass(ExpectedResult, A, B, ExclusionSet); |
122 | legacy::PassManager PM; |
123 | PM.add(P); |
124 | PM.run(M&: *M); |
125 | } |
126 | |
127 | LLVMContext Context; |
128 | std::unique_ptr<Module> M; |
129 | Instruction *A, *B; |
130 | SmallPtrSet<BasicBlock *, 4> ExclusionSet; |
131 | }; |
132 | |
133 | } |
134 | |
135 | TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) { |
136 | ParseAssembly( |
137 | Assembly: "define void @test() {\n" |
138 | "entry:\n" |
139 | " bitcast i8 undef to i8\n" |
140 | " %B = bitcast i8 undef to i8\n" |
141 | " bitcast i8 undef to i8\n" |
142 | " bitcast i8 undef to i8\n" |
143 | " %A = bitcast i8 undef to i8\n" |
144 | " ret void\n" |
145 | "}\n" ); |
146 | ExpectPath(ExpectedResult: false); |
147 | } |
148 | |
149 | TEST_F(IsPotentiallyReachableTest, SameBlockPath) { |
150 | ParseAssembly( |
151 | Assembly: "define void @test() {\n" |
152 | "entry:\n" |
153 | " %A = bitcast i8 undef to i8\n" |
154 | " bitcast i8 undef to i8\n" |
155 | " bitcast i8 undef to i8\n" |
156 | " %B = bitcast i8 undef to i8\n" |
157 | " ret void\n" |
158 | "}\n" ); |
159 | ExpectPath(ExpectedResult: true); |
160 | } |
161 | |
162 | TEST_F(IsPotentiallyReachableTest, SameBlockNoLoop) { |
163 | ParseAssembly( |
164 | Assembly: "define void @test() {\n" |
165 | "entry:\n" |
166 | " br label %middle\n" |
167 | "middle:\n" |
168 | " %B = bitcast i8 undef to i8\n" |
169 | " bitcast i8 undef to i8\n" |
170 | " bitcast i8 undef to i8\n" |
171 | " %A = bitcast i8 undef to i8\n" |
172 | " br label %nextblock\n" |
173 | "nextblock:\n" |
174 | " ret void\n" |
175 | "}\n" ); |
176 | ExpectPath(ExpectedResult: false); |
177 | } |
178 | |
179 | TEST_F(IsPotentiallyReachableTest, StraightNoPath) { |
180 | ParseAssembly( |
181 | Assembly: "define void @test() {\n" |
182 | "entry:\n" |
183 | " %B = bitcast i8 undef to i8\n" |
184 | " br label %exit\n" |
185 | "exit:\n" |
186 | " %A = bitcast i8 undef to i8\n" |
187 | " ret void\n" |
188 | "}" ); |
189 | ExpectPath(ExpectedResult: false); |
190 | } |
191 | |
192 | TEST_F(IsPotentiallyReachableTest, StraightPath) { |
193 | ParseAssembly( |
194 | Assembly: "define void @test() {\n" |
195 | "entry:\n" |
196 | " %A = bitcast i8 undef to i8\n" |
197 | " br label %exit\n" |
198 | "exit:\n" |
199 | " %B = bitcast i8 undef to i8\n" |
200 | " ret void\n" |
201 | "}" ); |
202 | ExpectPath(ExpectedResult: true); |
203 | } |
204 | |
205 | TEST_F(IsPotentiallyReachableTest, DestUnreachable) { |
206 | ParseAssembly( |
207 | Assembly: "define void @test() {\n" |
208 | "entry:\n" |
209 | " br label %midblock\n" |
210 | "midblock:\n" |
211 | " %A = bitcast i8 undef to i8\n" |
212 | " ret void\n" |
213 | "unreachable:\n" |
214 | " %B = bitcast i8 undef to i8\n" |
215 | " br label %midblock\n" |
216 | "}" ); |
217 | ExpectPath(ExpectedResult: false); |
218 | } |
219 | |
220 | TEST_F(IsPotentiallyReachableTest, BranchToReturn) { |
221 | ParseAssembly( |
222 | Assembly: "define void @test(i1 %x) {\n" |
223 | "entry:\n" |
224 | " %A = bitcast i8 undef to i8\n" |
225 | " br i1 %x, label %block1, label %block2\n" |
226 | "block1:\n" |
227 | " ret void\n" |
228 | "block2:\n" |
229 | " %B = bitcast i8 undef to i8\n" |
230 | " ret void\n" |
231 | "}" ); |
232 | ExpectPath(ExpectedResult: true); |
233 | } |
234 | |
235 | TEST_F(IsPotentiallyReachableTest, SimpleLoop1) { |
236 | ParseAssembly( |
237 | Assembly: "declare i1 @switch()\n" |
238 | "\n" |
239 | "define void @test() {\n" |
240 | "entry:\n" |
241 | " br label %loop\n" |
242 | "loop:\n" |
243 | " %B = bitcast i8 undef to i8\n" |
244 | " %A = bitcast i8 undef to i8\n" |
245 | " %x = call i1 @switch()\n" |
246 | " br i1 %x, label %loop, label %exit\n" |
247 | "exit:\n" |
248 | " ret void\n" |
249 | "}" ); |
250 | ExpectPath(ExpectedResult: true); |
251 | } |
252 | |
253 | TEST_F(IsPotentiallyReachableTest, SimpleLoop2) { |
254 | ParseAssembly( |
255 | Assembly: "declare i1 @switch()\n" |
256 | "\n" |
257 | "define void @test() {\n" |
258 | "entry:\n" |
259 | " %B = bitcast i8 undef to i8\n" |
260 | " br label %loop\n" |
261 | "loop:\n" |
262 | " %A = bitcast i8 undef to i8\n" |
263 | " %x = call i1 @switch()\n" |
264 | " br i1 %x, label %loop, label %exit\n" |
265 | "exit:\n" |
266 | " ret void\n" |
267 | "}" ); |
268 | ExpectPath(ExpectedResult: false); |
269 | } |
270 | |
271 | TEST_F(IsPotentiallyReachableTest, SimpleLoop3) { |
272 | ParseAssembly( |
273 | Assembly: "declare i1 @switch()\n" |
274 | "\n" |
275 | "define void @test() {\n" |
276 | "entry:\n" |
277 | " br label %loop\n" |
278 | "loop:\n" |
279 | " %B = bitcast i8 undef to i8\n" |
280 | " %x = call i1 @switch()\n" |
281 | " br i1 %x, label %loop, label %exit\n" |
282 | "exit:\n" |
283 | " %A = bitcast i8 undef to i8\n" |
284 | " ret void\n" |
285 | "}" ); |
286 | ExpectPath(ExpectedResult: false); |
287 | } |
288 | |
289 | |
290 | TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) { |
291 | ParseAssembly( |
292 | Assembly: "declare i1 @switch()\n" |
293 | "\n" |
294 | "define void @test() {\n" |
295 | "entry:\n" |
296 | " br label %loop1\n" |
297 | "loop1:\n" |
298 | " %A = bitcast i8 undef to i8\n" |
299 | " %x = call i1 @switch()\n" |
300 | " br i1 %x, label %loop1, label %loop1exit\n" |
301 | "loop1exit:\n" |
302 | " br label %loop2\n" |
303 | "loop2:\n" |
304 | " %B = bitcast i8 undef to i8\n" |
305 | " %y = call i1 @switch()\n" |
306 | " br i1 %x, label %loop2, label %loop2exit\n" |
307 | "loop2exit:" |
308 | " ret void\n" |
309 | "}" ); |
310 | ExpectPath(ExpectedResult: true); |
311 | } |
312 | |
313 | TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) { |
314 | ParseAssembly( |
315 | Assembly: "declare i1 @switch()\n" |
316 | "\n" |
317 | "define void @test() {\n" |
318 | "entry:\n" |
319 | " br label %loop1\n" |
320 | "loop1:\n" |
321 | " %B = bitcast i8 undef to i8\n" |
322 | " %x = call i1 @switch()\n" |
323 | " br i1 %x, label %loop1, label %loop1exit\n" |
324 | "loop1exit:\n" |
325 | " br label %loop2\n" |
326 | "loop2:\n" |
327 | " %A = bitcast i8 undef to i8\n" |
328 | " %y = call i1 @switch()\n" |
329 | " br i1 %x, label %loop2, label %loop2exit\n" |
330 | "loop2exit:" |
331 | " ret void\n" |
332 | "}" ); |
333 | ExpectPath(ExpectedResult: false); |
334 | } |
335 | |
336 | TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) { |
337 | ParseAssembly( |
338 | Assembly: "declare i1 @switch()\n" |
339 | "\n" |
340 | "define void @test() {\n" |
341 | "entry:\n" |
342 | " br label %outerloop3\n" |
343 | "outerloop3:\n" |
344 | " br label %innerloop1\n" |
345 | "innerloop1:\n" |
346 | " %B = bitcast i8 undef to i8\n" |
347 | " %x = call i1 @switch()\n" |
348 | " br i1 %x, label %innerloop1, label %innerloop1exit\n" |
349 | "innerloop1exit:\n" |
350 | " br label %innerloop2\n" |
351 | "innerloop2:\n" |
352 | " %A = bitcast i8 undef to i8\n" |
353 | " %y = call i1 @switch()\n" |
354 | " br i1 %x, label %innerloop2, label %innerloop2exit\n" |
355 | "innerloop2exit:" |
356 | " ;; In outer loop3 now.\n" |
357 | " %z = call i1 @switch()\n" |
358 | " br i1 %z, label %outerloop3, label %exit\n" |
359 | "exit:\n" |
360 | " ret void\n" |
361 | "}" ); |
362 | ExpectPath(ExpectedResult: true); |
363 | } |
364 | |
365 | static const char *BranchInsideLoopIR = |
366 | "declare i1 @switch()\n" |
367 | "\n" |
368 | "define void @test() {\n" |
369 | "entry:\n" |
370 | " br label %loop\n" |
371 | "loop:\n" |
372 | " %x = call i1 @switch()\n" |
373 | " br i1 %x, label %nextloopblock, label %exit\n" |
374 | "nextloopblock:\n" |
375 | " %y = call i1 @switch()\n" |
376 | " br i1 %y, label %left, label %right\n" |
377 | "left:\n" |
378 | " %A = bitcast i8 undef to i8\n" |
379 | " br label %loop\n" |
380 | "right:\n" |
381 | " %B = bitcast i8 undef to i8\n" |
382 | " br label %loop\n" |
383 | "exit:\n" |
384 | " ret void\n" |
385 | "}" ; |
386 | |
387 | TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) { |
388 | ParseAssembly(Assembly: BranchInsideLoopIR); |
389 | ExpectPath(ExpectedResult: true); |
390 | } |
391 | |
392 | TEST_F(IsPotentiallyReachableTest, ModifyTest) { |
393 | ParseAssembly(Assembly: BranchInsideLoopIR); |
394 | |
395 | succ_iterator S = succ_begin(BB: &*++M->getFunction(Name: "test" )->begin()); |
396 | BasicBlock *OldBB = S[0]; |
397 | S[0] = S[1]; |
398 | ExpectPath(ExpectedResult: false); |
399 | S[0] = OldBB; |
400 | ExpectPath(ExpectedResult: true); |
401 | } |
402 | |
403 | TEST_F(IsPotentiallyReachableTest, UnreachableFromEntryTest) { |
404 | ParseAssembly(Assembly: "define void @test() {\n" |
405 | "entry:\n" |
406 | " %A = bitcast i8 undef to i8\n" |
407 | " ret void\n" |
408 | "not.reachable:\n" |
409 | " %B = bitcast i8 undef to i8\n" |
410 | " ret void\n" |
411 | "}" ); |
412 | ExpectPath(ExpectedResult: false); |
413 | } |
414 | |
415 | TEST_F(IsPotentiallyReachableTest, UnreachableBlocksTest1) { |
416 | ParseAssembly(Assembly: "define void @test() {\n" |
417 | "entry:\n" |
418 | " ret void\n" |
419 | "not.reachable.1:\n" |
420 | " %A = bitcast i8 undef to i8\n" |
421 | " br label %not.reachable.2\n" |
422 | "not.reachable.2:\n" |
423 | " %B = bitcast i8 undef to i8\n" |
424 | " ret void\n" |
425 | "}" ); |
426 | ExpectPath(ExpectedResult: true); |
427 | } |
428 | |
429 | TEST_F(IsPotentiallyReachableTest, UnreachableBlocksTest2) { |
430 | ParseAssembly(Assembly: "define void @test() {\n" |
431 | "entry:\n" |
432 | " ret void\n" |
433 | "not.reachable.1:\n" |
434 | " %B = bitcast i8 undef to i8\n" |
435 | " br label %not.reachable.2\n" |
436 | "not.reachable.2:\n" |
437 | " %A = bitcast i8 undef to i8\n" |
438 | " ret void\n" |
439 | "}" ); |
440 | ExpectPath(ExpectedResult: false); |
441 | } |
442 | |
443 | TEST_F(IsPotentiallyReachableTest, SimpleExclusionTest) { |
444 | ParseAssembly(Assembly: "define void @test() {\n" |
445 | "entry:\n" |
446 | " %A = bitcast i8 undef to i8\n" |
447 | " br label %excluded\n" |
448 | "excluded:\n" |
449 | " br label %exit\n" |
450 | "exit:\n" |
451 | " %B = bitcast i8 undef to i8\n" |
452 | " ret void\n" |
453 | "}" ); |
454 | ExpectPath(ExpectedResult: false); |
455 | } |
456 | |
457 | TEST_F(IsPotentiallyReachableTest, DiamondExcludedTest) { |
458 | ParseAssembly(Assembly: "declare i1 @switch()\n" |
459 | "\n" |
460 | "define void @test() {\n" |
461 | "entry:\n" |
462 | " %x = call i1 @switch()\n" |
463 | " %A = bitcast i8 undef to i8\n" |
464 | " br i1 %x, label %excluded.1, label %excluded.2\n" |
465 | "excluded.1:\n" |
466 | " br label %exit\n" |
467 | "excluded.2:\n" |
468 | " br label %exit\n" |
469 | "exit:\n" |
470 | " %B = bitcast i8 undef to i8\n" |
471 | " ret void\n" |
472 | "}" ); |
473 | ExpectPath(ExpectedResult: false); |
474 | } |
475 | |
476 | TEST_F(IsPotentiallyReachableTest, DiamondOneSideExcludedTest) { |
477 | ParseAssembly(Assembly: "declare i1 @switch()\n" |
478 | "\n" |
479 | "define void @test() {\n" |
480 | "entry:\n" |
481 | " %x = call i1 @switch()\n" |
482 | " %A = bitcast i8 undef to i8\n" |
483 | " br i1 %x, label %excluded, label %diamond\n" |
484 | "excluded:\n" |
485 | " br label %exit\n" |
486 | "diamond:\n" |
487 | " br label %exit\n" |
488 | "exit:\n" |
489 | " %B = bitcast i8 undef to i8\n" |
490 | " ret void\n" |
491 | "}" ); |
492 | ExpectPath(ExpectedResult: true); |
493 | } |
494 | |
495 | TEST_F(IsPotentiallyReachableTest, UnreachableToReachable) { |
496 | ParseAssembly(Assembly: "define void @test() {\n" |
497 | "entry:\n" |
498 | " br label %exit\n" |
499 | "unreachableblock:\n" |
500 | " %A = bitcast i8 undef to i8\n" |
501 | " br label %exit\n" |
502 | "exit:\n" |
503 | " %B = bitcast i8 undef to i8\n" |
504 | " ret void\n" |
505 | "}" ); |
506 | ExpectPath(ExpectedResult: true); |
507 | } |
508 | |