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
24using namespace llvm;
25
26namespace {
27
28// This fixture assists in running the isPotentiallyReachable utility four ways
29// and ensuring it produces the correct answer each time.
30class IsPotentiallyReachableTest : public testing::Test {
31protected:
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
135TEST_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
149TEST_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
162TEST_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
179TEST_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
192TEST_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
205TEST_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
220TEST_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
235TEST_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
253TEST_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
271TEST_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
290TEST_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
313TEST_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
336TEST_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
365static 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
387TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) {
388 ParseAssembly(Assembly: BranchInsideLoopIR);
389 ExpectPath(ExpectedResult: true);
390}
391
392TEST_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
403TEST_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
415TEST_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
429TEST_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
443TEST_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
457TEST_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
476TEST_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
495TEST_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

source code of llvm/unittests/Analysis/CFGTest.cpp