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, nullptr, 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, nullptr, nullptr),
100 EXPECT_EQ(isPotentiallyReachable(A, B, DT, nullptr), ExpectedResult);
101 EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, 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);
119 std::unique_ptr<Module> M;
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];