1 //===- CFGTest.cpp - CFG tests --------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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/PassManager.h"
20 #include "llvm/Support/ErrorHandling.h"
21 #include "llvm/Support/SourceMgr.h"
22 #include "gtest/gtest.h"
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 {
32 void ParseAssembly(const char *Assembly) {
33 M.reset(new Module("Module", getGlobalContext()));
36 bool Parsed = ParseAssemblyString(Assembly, M.get(),
37 Error, M->getContext()) == M.get();
40 raw_string_ostream os(errMsg);
44 // A failure here means that the test itself is buggy.
45 report_fatal_error(os.str().c_str());
48 Function *F = M->getFunction("test");
50 report_fatal_error("Test must have a function named @test");
53 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
55 if (I->getName() == "A")
57 else if (I->getName() == "B")
62 report_fatal_error("@test must have an instruction %A");
64 report_fatal_error("@test must have an instruction %B");
67 void ExpectPath(bool ExpectedResult) {
69 class IsPotentiallyReachableTestPass : public FunctionPass {
71 IsPotentiallyReachableTestPass(bool ExpectedResult,
72 Instruction *A, Instruction *B)
73 : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B) {}
75 static int initialize() {
76 PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass",
77 "", &ID, 0, true, true);
78 PassRegistry::getPassRegistry()->registerPass(*PI, false);
79 initializeLoopInfoPass(*PassRegistry::getPassRegistry());
80 initializeDominatorTreeWrapperPassPass(
81 *PassRegistry::getPassRegistry());
85 void getAnalysisUsage(AnalysisUsage &AU) const {
87 AU.addRequired<LoopInfo>();
88 AU.addRequired<DominatorTreeWrapperPass>();
91 bool runOnFunction(Function &F) {
92 if (!F.hasName() || F.getName() != "test")
95 LoopInfo *LI = &getAnalysis<LoopInfo>();
97 &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
98 EXPECT_EQ(isPotentiallyReachable(A, B, 0, 0), ExpectedResult);
99 EXPECT_EQ(isPotentiallyReachable(A, B, DT, 0), ExpectedResult);
100 EXPECT_EQ(isPotentiallyReachable(A, B, 0, LI), ExpectedResult);
101 EXPECT_EQ(isPotentiallyReachable(A, B, DT, LI), ExpectedResult);
108 static int initialize = IsPotentiallyReachableTestPass::initialize();
111 IsPotentiallyReachableTestPass *P =
112 new IsPotentiallyReachableTestPass(ExpectedResult, A, B);
118 std::unique_ptr<Module> M;
124 TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) {
126 "define void @test() {\n"
128 " bitcast i8 undef to i8\n"
129 " %B = bitcast i8 undef to i8\n"
130 " bitcast i8 undef to i8\n"
131 " bitcast i8 undef to i8\n"
132 " %A = bitcast i8 undef to i8\n"
138 TEST_F(IsPotentiallyReachableTest, SameBlockPath) {
140 "define void @test() {\n"
142 " %A = bitcast i8 undef to i8\n"
143 " bitcast i8 undef to i8\n"
144 " bitcast i8 undef to i8\n"
145 " %B = bitcast i8 undef to i8\n"
151 TEST_F(IsPotentiallyReachableTest, SameBlockNoLoop) {
153 "define void @test() {\n"
155 " br label %middle\n"
157 " %B = bitcast i8 undef to i8\n"
158 " bitcast i8 undef to i8\n"
159 " bitcast i8 undef to i8\n"
160 " %A = bitcast i8 undef to i8\n"
161 " br label %nextblock\n"
168 TEST_F(IsPotentiallyReachableTest, StraightNoPath) {
170 "define void @test() {\n"
172 " %B = bitcast i8 undef to i8\n"
175 " %A = bitcast i8 undef to i8\n"
181 TEST_F(IsPotentiallyReachableTest, StraightPath) {
183 "define void @test() {\n"
185 " %A = bitcast i8 undef to i8\n"
188 " %B = bitcast i8 undef to i8\n"
194 TEST_F(IsPotentiallyReachableTest, DestUnreachable) {
196 "define void @test() {\n"
198 " br label %midblock\n"
200 " %A = bitcast i8 undef to i8\n"
203 " %B = bitcast i8 undef to i8\n"
204 " br label %midblock\n"
209 TEST_F(IsPotentiallyReachableTest, BranchToReturn) {
211 "define void @test(i1 %x) {\n"
213 " %A = bitcast i8 undef to i8\n"
214 " br i1 %x, label %block1, label %block2\n"
218 " %B = bitcast i8 undef to i8\n"
224 TEST_F(IsPotentiallyReachableTest, SimpleLoop1) {
226 "declare i1 @switch()\n"
228 "define void @test() {\n"
232 " %B = bitcast i8 undef to i8\n"
233 " %A = bitcast i8 undef to i8\n"
234 " %x = call i1 @switch()\n"
235 " br i1 %x, label %loop, label %exit\n"
242 TEST_F(IsPotentiallyReachableTest, SimpleLoop2) {
244 "declare i1 @switch()\n"
246 "define void @test() {\n"
248 " %B = bitcast i8 undef to i8\n"
251 " %A = bitcast i8 undef to i8\n"
252 " %x = call i1 @switch()\n"
253 " br i1 %x, label %loop, label %exit\n"
260 TEST_F(IsPotentiallyReachableTest, SimpleLoop3) {
262 "declare i1 @switch()\n"
264 "define void @test() {\n"
268 " %B = bitcast i8 undef to i8\n"
269 " %x = call i1 @switch()\n"
270 " br i1 %x, label %loop, label %exit\n"
272 " %A = bitcast i8 undef to i8\n"
279 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) {
281 "declare i1 @switch()\n"
283 "define void @test() {\n"
287 " %A = bitcast i8 undef to i8\n"
288 " %x = call i1 @switch()\n"
289 " br i1 %x, label %loop1, label %loop1exit\n"
293 " %B = bitcast i8 undef to i8\n"
294 " %y = call i1 @switch()\n"
295 " br i1 %x, label %loop2, label %loop2exit\n"
302 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) {
304 "declare i1 @switch()\n"
306 "define void @test() {\n"
310 " %B = bitcast i8 undef to i8\n"
311 " %x = call i1 @switch()\n"
312 " br i1 %x, label %loop1, label %loop1exit\n"
316 " %A = bitcast i8 undef to i8\n"
317 " %y = call i1 @switch()\n"
318 " br i1 %x, label %loop2, label %loop2exit\n"
325 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) {
327 "declare i1 @switch()\n"
329 "define void @test() {\n"
331 " br label %outerloop3\n"
333 " br label %innerloop1\n"
335 " %B = bitcast i8 undef to i8\n"
336 " %x = call i1 @switch()\n"
337 " br i1 %x, label %innerloop1, label %innerloop1exit\n"
339 " br label %innerloop2\n"
341 " %A = bitcast i8 undef to i8\n"
342 " %y = call i1 @switch()\n"
343 " br i1 %x, label %innerloop2, label %innerloop2exit\n"
345 " ;; In outer loop3 now.\n"
346 " %z = call i1 @switch()\n"
347 " br i1 %z, label %outerloop3, label %exit\n"
354 static const char *BranchInsideLoopIR =
355 "declare i1 @switch()\n"
357 "define void @test() {\n"
361 " %x = call i1 @switch()\n"
362 " br i1 %x, label %nextloopblock, label %exit\n"
364 " %y = call i1 @switch()\n"
365 " br i1 %y, label %left, label %right\n"
367 " %A = bitcast i8 undef to i8\n"
370 " %B = bitcast i8 undef to i8\n"
376 TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) {
377 ParseAssembly(BranchInsideLoopIR);
381 TEST_F(IsPotentiallyReachableTest, ModifyTest) {
382 ParseAssembly(BranchInsideLoopIR);
384 succ_iterator S = succ_begin(++M->getFunction("test")->begin());
385 BasicBlock *OldBB = S[0];