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
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(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
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
122TEST_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
136TEST_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
149TEST_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
166TEST_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
179TEST_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
192TEST_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
207TEST_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
222TEST_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
240TEST_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
258TEST_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
277TEST_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
300TEST_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
323TEST_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
352static 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
374TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) {
375  ParseAssembly(BranchInsideLoopIR);
376  ExpectPath(true);
377}
378
379TEST_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