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/ADT/OwningPtr.h"
12 #include "llvm/Analysis/LoopInfo.h"
13 #include "llvm/AsmParser/Parser.h"
14 #include "llvm/IR/Dominators.h"
15 #include "llvm/IR/Function.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/InstIterator.h"
22 #include "llvm/Support/SourceMgr.h"
23 #include "gtest/gtest.h"
29 // This fixture assists in running the isPotentiallyReachable utility four ways
30 // and ensuring it produces the correct answer each time.
31 class IsPotentiallyReachableTest : public testing::Test {
33 void ParseAssembly(const char *Assembly) {
34 M.reset(new Module("Module", getGlobalContext()));
37 bool Parsed = ParseAssemblyString(Assembly, M.get(),
38 Error, M->getContext()) == M.get();
41 raw_string_ostream os(errMsg);
45 // A failure here means that the test itself is buggy.
46 report_fatal_error(os.str().c_str());
49 Function *F = M->getFunction("test");
51 report_fatal_error("Test must have a function named @test");
54 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
56 if (I->getName() == "A")
58 else if (I->getName() == "B")
63 report_fatal_error("@test must have an instruction %A");
65 report_fatal_error("@test must have an instruction %B");
68 void ExpectPath(bool ExpectedResult) {
70 class IsPotentiallyReachableTestPass : public FunctionPass {
72 IsPotentiallyReachableTestPass(bool ExpectedResult,
73 Instruction *A, Instruction *B)
74 : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B) {}
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 initializeDominatorTreeWrapperPassPass(
82 *PassRegistry::getPassRegistry());
86 void getAnalysisUsage(AnalysisUsage &AU) const {
88 AU.addRequired<LoopInfo>();
89 AU.addRequired<DominatorTreeWrapperPass>();
92 bool runOnFunction(Function &F) {
93 if (!F.hasName() || F.getName() != "test")
96 LoopInfo *LI = &getAnalysis<LoopInfo>();
98 &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
99 EXPECT_EQ(isPotentiallyReachable(A, B, 0, 0), ExpectedResult);
100 EXPECT_EQ(isPotentiallyReachable(A, B, DT, 0), ExpectedResult);
101 EXPECT_EQ(isPotentiallyReachable(A, B, 0, LI), ExpectedResult);
102 EXPECT_EQ(isPotentiallyReachable(A, B, DT, LI), ExpectedResult);
109 static int initialize = IsPotentiallyReachableTestPass::initialize();
112 IsPotentiallyReachableTestPass *P =
113 new IsPotentiallyReachableTestPass(ExpectedResult, A, B);
125 TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) {
127 "define void @test() {\n"
129 " bitcast i8 undef to i8\n"
130 " %B = bitcast i8 undef to i8\n"
131 " bitcast i8 undef to i8\n"
132 " bitcast i8 undef to i8\n"
133 " %A = bitcast i8 undef to i8\n"
139 TEST_F(IsPotentiallyReachableTest, SameBlockPath) {
141 "define void @test() {\n"
143 " %A = bitcast i8 undef to i8\n"
144 " bitcast i8 undef to i8\n"
145 " bitcast i8 undef to i8\n"
146 " %B = bitcast i8 undef to i8\n"
152 TEST_F(IsPotentiallyReachableTest, SameBlockNoLoop) {
154 "define void @test() {\n"
156 " br label %middle\n"
158 " %B = bitcast i8 undef to i8\n"
159 " bitcast i8 undef to i8\n"
160 " bitcast i8 undef to i8\n"
161 " %A = bitcast i8 undef to i8\n"
162 " br label %nextblock\n"
169 TEST_F(IsPotentiallyReachableTest, StraightNoPath) {
171 "define void @test() {\n"
173 " %B = bitcast i8 undef to i8\n"
176 " %A = bitcast i8 undef to i8\n"
182 TEST_F(IsPotentiallyReachableTest, StraightPath) {
184 "define void @test() {\n"
186 " %A = bitcast i8 undef to i8\n"
189 " %B = bitcast i8 undef to i8\n"
195 TEST_F(IsPotentiallyReachableTest, DestUnreachable) {
197 "define void @test() {\n"
199 " br label %midblock\n"
201 " %A = bitcast i8 undef to i8\n"
204 " %B = bitcast i8 undef to i8\n"
205 " br label %midblock\n"
210 TEST_F(IsPotentiallyReachableTest, BranchToReturn) {
212 "define void @test(i1 %x) {\n"
214 " %A = bitcast i8 undef to i8\n"
215 " br i1 %x, label %block1, label %block2\n"
219 " %B = bitcast i8 undef to i8\n"
225 TEST_F(IsPotentiallyReachableTest, SimpleLoop1) {
227 "declare i1 @switch()\n"
229 "define void @test() {\n"
233 " %B = bitcast i8 undef to i8\n"
234 " %A = bitcast i8 undef to i8\n"
235 " %x = call i1 @switch()\n"
236 " br i1 %x, label %loop, label %exit\n"
243 TEST_F(IsPotentiallyReachableTest, SimpleLoop2) {
245 "declare i1 @switch()\n"
247 "define void @test() {\n"
249 " %B = bitcast i8 undef to i8\n"
252 " %A = bitcast i8 undef to i8\n"
253 " %x = call i1 @switch()\n"
254 " br i1 %x, label %loop, label %exit\n"
261 TEST_F(IsPotentiallyReachableTest, SimpleLoop3) {
263 "declare i1 @switch()\n"
265 "define void @test() {\n"
269 " %B = bitcast i8 undef to i8\n"
270 " %x = call i1 @switch()\n"
271 " br i1 %x, label %loop, label %exit\n"
273 " %A = bitcast i8 undef to i8\n"
280 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) {
282 "declare i1 @switch()\n"
284 "define void @test() {\n"
288 " %A = bitcast i8 undef to i8\n"
289 " %x = call i1 @switch()\n"
290 " br i1 %x, label %loop1, label %loop1exit\n"
294 " %B = bitcast i8 undef to i8\n"
295 " %y = call i1 @switch()\n"
296 " br i1 %x, label %loop2, label %loop2exit\n"
303 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) {
305 "declare i1 @switch()\n"
307 "define void @test() {\n"
311 " %B = bitcast i8 undef to i8\n"
312 " %x = call i1 @switch()\n"
313 " br i1 %x, label %loop1, label %loop1exit\n"
317 " %A = bitcast i8 undef to i8\n"
318 " %y = call i1 @switch()\n"
319 " br i1 %x, label %loop2, label %loop2exit\n"
326 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) {
328 "declare i1 @switch()\n"
330 "define void @test() {\n"
332 " br label %outerloop3\n"
334 " br label %innerloop1\n"
336 " %B = bitcast i8 undef to i8\n"
337 " %x = call i1 @switch()\n"
338 " br i1 %x, label %innerloop1, label %innerloop1exit\n"
340 " br label %innerloop2\n"
342 " %A = bitcast i8 undef to i8\n"
343 " %y = call i1 @switch()\n"
344 " br i1 %x, label %innerloop2, label %innerloop2exit\n"
346 " ;; In outer loop3 now.\n"
347 " %z = call i1 @switch()\n"
348 " br i1 %z, label %outerloop3, label %exit\n"
355 static const char *BranchInsideLoopIR =
356 "declare i1 @switch()\n"
358 "define void @test() {\n"
362 " %x = call i1 @switch()\n"
363 " br i1 %x, label %nextloopblock, label %exit\n"
365 " %y = call i1 @switch()\n"
366 " br i1 %y, label %left, label %right\n"
368 " %A = bitcast i8 undef to i8\n"
371 " %B = bitcast i8 undef to i8\n"
377 TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) {
378 ParseAssembly(BranchInsideLoopIR);
382 TEST_F(IsPotentiallyReachableTest, ModifyTest) {
383 ParseAssembly(BranchInsideLoopIR);
385 succ_iterator S = succ_begin(++M->getFunction("test")->begin());
386 BasicBlock *OldBB = S[0];