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/ADT/OwningPtr.h"
12#include "llvm/Analysis/Dominators.h"
13#include "llvm/Analysis/LoopInfo.h"
14#include "llvm/Assembly/Parser.h"
15#include "llvm/IR/LLVMContext.h"
16#include "llvm/IR/Function.h"
17#include "llvm/IR/Module.h"
18#include "llvm/Support/ErrorHandling.h"
19#include "llvm/Support/InstIterator.h"
20#include "llvm/Support/SourceMgr.h"
21#include "llvm/Pass.h"
22#include "llvm/PassManager.h"
23#include "gtest/gtest.h"
24
25using namespace llvm;
26
27namespace {
28
29// This fixture assists in running the isPotentiallyReachable utility four ways
30// and ensuring it produces the correct answer each time.
31class IsPotentiallyReachableTest : public testing::Test {
32protected:
33  void ParseAssembly(const char *Assembly) {
34    M.reset(new Module("Module", getGlobalContext()));
35
36    SMDiagnostic Error;
37    bool Parsed = ParseAssemblyString(Assembly, M.get(),
38                                      Error, M->getContext()) == M.get();
39
40    std::string errMsg;
41    raw_string_ostream os(errMsg);
42    Error.print("", os);
43
44    if (!Parsed) {
45      // A failure here means that the test itself is buggy.
46      report_fatal_error(os.str().c_str());
47    }
48
49    Function *F = M->getFunction("test");
50    if (F == NULL)
51      report_fatal_error("Test must have a function named @test");
52
53    A = B = NULL;
54    for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
55      if (I->hasName()) {
56        if (I->getName() == "A")
57          A = &*I;
58        else if (I->getName() == "B")
59          B = &*I;
60      }
61    }
62    if (A == NULL)
63      report_fatal_error("@test must have an instruction %A");
64    if (B == NULL)
65      report_fatal_error("@test must have an instruction %B");
66  }
67
68  void ExpectPath(bool ExpectedResult) {
69    static char ID;
70    class IsPotentiallyReachableTestPass : public FunctionPass {
71     public:
72      IsPotentiallyReachableTestPass(bool ExpectedResult,
73                                     Instruction *A, Instruction *B)
74          : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B) {}
75
76      static int initialize() {
77        PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass",
78                                    "", &ID, 0, true, true);
79        PassRegistry::getPassRegistry()->registerPass(*PI, false);
80        initializeLoopInfoPass(*PassRegistry::getPassRegistry());
81        initializeDominatorTreePass(*PassRegistry::getPassRegistry());
82        return 0;
83      }
84
85      void getAnalysisUsage(AnalysisUsage &AU) const {
86        AU.setPreservesAll();
87        AU.addRequired<LoopInfo>();
88        AU.addRequired<DominatorTree>();
89      }
90
91      bool runOnFunction(Function &F) {
92        if (!F.hasName() || F.getName() != "test")
93          return false;
94
95        LoopInfo *LI = &getAnalysis<LoopInfo>();
96        DominatorTree *DT = &getAnalysis<DominatorTree>();
97        EXPECT_EQ(isPotentiallyReachable(A, B, 0, 0), ExpectedResult);
98        EXPECT_EQ(isPotentiallyReachable(A, B, DT, 0), ExpectedResult);
99        EXPECT_EQ(isPotentiallyReachable(A, B, 0, LI), ExpectedResult);
100        EXPECT_EQ(isPotentiallyReachable(A, B, DT, LI), ExpectedResult);
101        return false;
102      }
103      bool ExpectedResult;
104      Instruction *A, *B;
105    };
106
107    static int initialize = IsPotentiallyReachableTestPass::initialize();
108    (void)initialize;
109
110    IsPotentiallyReachableTestPass *P =
111        new IsPotentiallyReachableTestPass(ExpectedResult, A, B);
112    PassManager PM;
113    PM.add(P);
114    PM.run(*M);
115  }
116private:
117  OwningPtr<Module> M;
118  Instruction *A, *B;
119};
120
121}
122
123TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) {
124  ParseAssembly(
125      "define void @test() {\n"
126      "entry:\n"
127      "  bitcast i8 undef to i8\n"
128      "  %B = bitcast i8 undef to i8\n"
129      "  bitcast i8 undef to i8\n"
130      "  bitcast i8 undef to i8\n"
131      "  %A = bitcast i8 undef to i8\n"
132      "  ret void\n"
133      "}\n");
134  ExpectPath(false);
135}
136
137TEST_F(IsPotentiallyReachableTest, SameBlockPath) {
138  ParseAssembly(
139      "define void @test() {\n"
140      "entry:\n"
141      "  %A = bitcast i8 undef to i8\n"
142      "  bitcast i8 undef to i8\n"
143      "  bitcast i8 undef to i8\n"
144      "  %B = bitcast i8 undef to i8\n"
145      "  ret void\n"
146      "}\n");
147  ExpectPath(true);
148}
149
150TEST_F(IsPotentiallyReachableTest, StraightNoPath) {
151  ParseAssembly(
152      "define void @test() {\n"
153      "entry:\n"
154      "  %B = bitcast i8 undef to i8\n"
155      "  br label %exit\n"
156      "exit:\n"
157      "  %A = bitcast i8 undef to i8\n"
158      "  ret void\n"
159      "}");
160  ExpectPath(false);
161}
162
163TEST_F(IsPotentiallyReachableTest, StraightPath) {
164  ParseAssembly(
165      "define void @test() {\n"
166      "entry:\n"
167      "  %A = bitcast i8 undef to i8\n"
168      "  br label %exit\n"
169      "exit:\n"
170      "  %B = bitcast i8 undef to i8\n"
171      "  ret void\n"
172      "}");
173  ExpectPath(true);
174}
175
176TEST_F(IsPotentiallyReachableTest, DestUnreachable) {
177  ParseAssembly(
178      "define void @test() {\n"
179      "entry:\n"
180      "  br label %midblock\n"
181      "midblock:\n"
182      "  %A = bitcast i8 undef to i8\n"
183      "  ret void\n"
184      "unreachable:\n"
185      "  %B = bitcast i8 undef to i8\n"
186      "  br label %midblock\n"
187      "}");
188  ExpectPath(false);
189}
190
191TEST_F(IsPotentiallyReachableTest, BranchToReturn) {
192  ParseAssembly(
193      "define void @test(i1 %x) {\n"
194      "entry:\n"
195      "  %A = bitcast i8 undef to i8\n"
196      "  br i1 %x, label %block1, label %block2\n"
197      "block1:\n"
198      "  ret void\n"
199      "block2:\n"
200      "  %B = bitcast i8 undef to i8\n"
201      "  ret void\n"
202      "}");
203  ExpectPath(true);
204}
205
206TEST_F(IsPotentiallyReachableTest, SimpleLoop1) {
207  ParseAssembly(
208      "declare i1 @switch()\n"
209      "\n"
210      "define void @test() {\n"
211      "entry:\n"
212      "  br label %loop\n"
213      "loop:\n"
214      "  %B = bitcast i8 undef to i8\n"
215      "  %A = bitcast i8 undef to i8\n"
216      "  %x = call i1 @switch()\n"
217      "  br i1 %x, label %loop, label %exit\n"
218      "exit:\n"
219      "  ret void\n"
220      "}");
221  ExpectPath(true);
222}
223
224TEST_F(IsPotentiallyReachableTest, SimpleLoop2) {
225  ParseAssembly(
226      "declare i1 @switch()\n"
227      "\n"
228      "define void @test() {\n"
229      "entry:\n"
230      "  %B = bitcast i8 undef to i8\n"
231      "  br label %loop\n"
232      "loop:\n"
233      "  %A = bitcast i8 undef to i8\n"
234      "  %x = call i1 @switch()\n"
235      "  br i1 %x, label %loop, label %exit\n"
236      "exit:\n"
237      "  ret void\n"
238      "}");
239  ExpectPath(false);
240}
241
242TEST_F(IsPotentiallyReachableTest, SimpleLoop3) {
243  ParseAssembly(
244      "declare i1 @switch()\n"
245      "\n"
246      "define void @test() {\n"
247      "entry:\n"
248      "  br label %loop\n"
249      "loop:\n"
250      "  %B = bitcast i8 undef to i8\n"
251      "  %x = call i1 @switch()\n"
252      "  br i1 %x, label %loop, label %exit\n"
253      "exit:\n"
254      "  %A = bitcast i8 undef to i8\n"
255      "  ret void\n"
256      "}");
257  ExpectPath(false);
258}
259
260
261TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) {
262  ParseAssembly(
263      "declare i1 @switch()\n"
264      "\n"
265      "define void @test() {\n"
266      "entry:\n"
267      "  br label %loop1\n"
268      "loop1:\n"
269      "  %A = bitcast i8 undef to i8\n"
270      "  %x = call i1 @switch()\n"
271      "  br i1 %x, label %loop1, label %loop1exit\n"
272      "loop1exit:\n"
273      "  br label %loop2\n"
274      "loop2:\n"
275      "  %B = bitcast i8 undef to i8\n"
276      "  %y = call i1 @switch()\n"
277      "  br i1 %x, label %loop2, label %loop2exit\n"
278      "loop2exit:"
279      "  ret void\n"
280      "}");
281  ExpectPath(true);
282}
283
284TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) {
285  ParseAssembly(
286      "declare i1 @switch()\n"
287      "\n"
288      "define void @test() {\n"
289      "entry:\n"
290      "  br label %loop1\n"
291      "loop1:\n"
292      "  %B = bitcast i8 undef to i8\n"
293      "  %x = call i1 @switch()\n"
294      "  br i1 %x, label %loop1, label %loop1exit\n"
295      "loop1exit:\n"
296      "  br label %loop2\n"
297      "loop2:\n"
298      "  %A = bitcast i8 undef to i8\n"
299      "  %y = call i1 @switch()\n"
300      "  br i1 %x, label %loop2, label %loop2exit\n"
301      "loop2exit:"
302      "  ret void\n"
303      "}");
304  ExpectPath(false);
305}
306
307TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) {
308  ParseAssembly(
309      "declare i1 @switch()\n"
310      "\n"
311      "define void @test() {\n"
312      "entry:\n"
313      "  br label %outerloop3\n"
314      "outerloop3:\n"
315      "  br label %innerloop1\n"
316      "innerloop1:\n"
317      "  %B = bitcast i8 undef to i8\n"
318      "  %x = call i1 @switch()\n"
319      "  br i1 %x, label %innerloop1, label %innerloop1exit\n"
320      "innerloop1exit:\n"
321      "  br label %innerloop2\n"
322      "innerloop2:\n"
323      "  %A = bitcast i8 undef to i8\n"
324      "  %y = call i1 @switch()\n"
325      "  br i1 %x, label %innerloop2, label %innerloop2exit\n"
326      "innerloop2exit:"
327      "  ;; In outer loop3 now.\n"
328      "  %z = call i1 @switch()\n"
329      "  br i1 %z, label %outerloop3, label %exit\n"
330      "exit:\n"
331      "  ret void\n"
332      "}");
333  ExpectPath(true);
334}
335
336TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) {
337  ParseAssembly(
338      "declare i1 @switch()\n"
339      "\n"
340      "define void @test() {\n"
341      "entry:\n"
342      "  br label %loop\n"
343      "loop:\n"
344      "  %x = call i1 @switch()\n"
345      "  br i1 %x, label %nextloopblock, label %exit\n"
346      "nextloopblock:\n"
347      "  %y = call i1 @switch()\n"
348      "  br i1 %y, label %left, label %right\n"
349      "left:\n"
350      "  %A = bitcast i8 undef to i8\n"
351      "  br label %loop\n"
352      "right:\n"
353      "  %B = bitcast i8 undef to i8\n"
354      "  br label %loop\n"
355      "exit:\n"
356      "  ret void\n"
357      "}");
358  ExpectPath(true);
359}
360