150
|
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(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 assert(ExclusionSet.empty());
|
|
63 for (auto I = F->begin(), E = F->end(); I != E; ++I) {
|
|
64 if (I->hasName() && I->getName().startswith("excluded"))
|
|
65 ExclusionSet.insert(&*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, false);
|
|
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);
|
|
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 "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(false);
|
|
147 }
|
|
148
|
|
149 TEST_F(IsPotentiallyReachableTest, SameBlockPath) {
|
|
150 ParseAssembly(
|
|
151 "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(true);
|
|
160 }
|
|
161
|
|
162 TEST_F(IsPotentiallyReachableTest, SameBlockNoLoop) {
|
|
163 ParseAssembly(
|
|
164 "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(false);
|
|
177 }
|
|
178
|
|
179 TEST_F(IsPotentiallyReachableTest, StraightNoPath) {
|
|
180 ParseAssembly(
|
|
181 "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(false);
|
|
190 }
|
|
191
|
|
192 TEST_F(IsPotentiallyReachableTest, StraightPath) {
|
|
193 ParseAssembly(
|
|
194 "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(true);
|
|
203 }
|
|
204
|
|
205 TEST_F(IsPotentiallyReachableTest, DestUnreachable) {
|
|
206 ParseAssembly(
|
|
207 "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(false);
|
|
218 }
|
|
219
|
|
220 TEST_F(IsPotentiallyReachableTest, BranchToReturn) {
|
|
221 ParseAssembly(
|
|
222 "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(true);
|
|
233 }
|
|
234
|
|
235 TEST_F(IsPotentiallyReachableTest, SimpleLoop1) {
|
|
236 ParseAssembly(
|
|
237 "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(true);
|
|
251 }
|
|
252
|
|
253 TEST_F(IsPotentiallyReachableTest, SimpleLoop2) {
|
|
254 ParseAssembly(
|
|
255 "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(false);
|
|
269 }
|
|
270
|
|
271 TEST_F(IsPotentiallyReachableTest, SimpleLoop3) {
|
|
272 ParseAssembly(
|
|
273 "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(false);
|
|
287 }
|
|
288
|
|
289
|
|
290 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) {
|
|
291 ParseAssembly(
|
|
292 "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(true);
|
|
311 }
|
|
312
|
|
313 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) {
|
|
314 ParseAssembly(
|
|
315 "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(false);
|
|
334 }
|
|
335
|
|
336 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) {
|
|
337 ParseAssembly(
|
|
338 "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(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(BranchInsideLoopIR);
|
|
389 ExpectPath(true);
|
|
390 }
|
|
391
|
|
392 TEST_F(IsPotentiallyReachableTest, ModifyTest) {
|
|
393 ParseAssembly(BranchInsideLoopIR);
|
|
394
|
|
395 succ_iterator S = succ_begin(&*++M->getFunction("test")->begin());
|
|
396 BasicBlock *OldBB = S[0];
|
|
397 S[0] = S[1];
|
|
398 ExpectPath(false);
|
|
399 S[0] = OldBB;
|
|
400 ExpectPath(true);
|
|
401 }
|
|
402
|
|
403 TEST_F(IsPotentiallyReachableTest, UnreachableFromEntryTest) {
|
|
404 ParseAssembly("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(false);
|
|
413 }
|
|
414
|
|
415 TEST_F(IsPotentiallyReachableTest, UnreachableBlocksTest1) {
|
|
416 ParseAssembly("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(true);
|
|
427 }
|
|
428
|
|
429 TEST_F(IsPotentiallyReachableTest, UnreachableBlocksTest2) {
|
|
430 ParseAssembly("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(false);
|
|
441 }
|
|
442
|
|
443 TEST_F(IsPotentiallyReachableTest, SimpleExclusionTest) {
|
|
444 ParseAssembly("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(false);
|
|
455 }
|
|
456
|
|
457 TEST_F(IsPotentiallyReachableTest, DiamondExcludedTest) {
|
|
458 ParseAssembly("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(false);
|
|
474 }
|
|
475
|
|
476 TEST_F(IsPotentiallyReachableTest, DiamondOneSideExcludedTest) {
|
|
477 ParseAssembly("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(true);
|
|
493 }
|
|
494
|
|
495 TEST_F(IsPotentiallyReachableTest, UnreachableToReachable) {
|
|
496 ParseAssembly("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(true);
|
|
507 }
|