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/IR/LegacyPassManager.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) {
34 M = parseAssemblyString(Assembly, Error, getGlobalContext());
37 raw_string_ostream os(errMsg);
40 // A failure here means that the test itself is buggy.
42 report_fatal_error(os.str().c_str());
44 Function *F = M->getFunction("test");
46 report_fatal_error("Test must have a function named @test");
49 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
51 if (I->getName() == "A")
53 else if (I->getName() == "B")
58 report_fatal_error("@test must have an instruction %A");
60 report_fatal_error("@test must have an instruction %B");
63 void ExpectPath(bool ExpectedResult) {
65 class IsPotentiallyReachableTestPass : public FunctionPass {
67 IsPotentiallyReachableTestPass(bool ExpectedResult,
68 Instruction *A, Instruction *B)
69 : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B) {}
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());
81 void getAnalysisUsage(AnalysisUsage &AU) const override {
83 AU.addRequired<LoopInfoWrapperPass>();
84 AU.addRequired<DominatorTreeWrapperPass>();
87 bool runOnFunction(Function &F) override {
88 if (!F.hasName() || F.getName() != "test")
91 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
93 &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
94 EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, nullptr),
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);
105 static int initialize = IsPotentiallyReachableTestPass::initialize();
108 IsPotentiallyReachableTestPass *P =
109 new IsPotentiallyReachableTestPass(ExpectedResult, A, B);
110 legacy::PassManager PM;
115 std::unique_ptr<Module> M;
121 TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) {
123 "define void @test() {\n"
125 " bitcast i8 undef to i8\n"
126 " %B = bitcast i8 undef to i8\n"
127 " bitcast i8 undef to i8\n"
128 " bitcast i8 undef to i8\n"
129 " %A = bitcast i8 undef to i8\n"
135 TEST_F(IsPotentiallyReachableTest, SameBlockPath) {
137 "define void @test() {\n"
139 " %A = bitcast i8 undef to i8\n"
140 " bitcast i8 undef to i8\n"
141 " bitcast i8 undef to i8\n"
142 " %B = bitcast i8 undef to i8\n"
148 TEST_F(IsPotentiallyReachableTest, SameBlockNoLoop) {
150 "define void @test() {\n"
152 " br label %middle\n"
154 " %B = bitcast i8 undef to i8\n"
155 " bitcast i8 undef to i8\n"
156 " bitcast i8 undef to i8\n"
157 " %A = bitcast i8 undef to i8\n"
158 " br label %nextblock\n"
165 TEST_F(IsPotentiallyReachableTest, StraightNoPath) {
167 "define void @test() {\n"
169 " %B = bitcast i8 undef to i8\n"
172 " %A = bitcast i8 undef to i8\n"
178 TEST_F(IsPotentiallyReachableTest, StraightPath) {
180 "define void @test() {\n"
182 " %A = bitcast i8 undef to i8\n"
185 " %B = bitcast i8 undef to i8\n"
191 TEST_F(IsPotentiallyReachableTest, DestUnreachable) {
193 "define void @test() {\n"
195 " br label %midblock\n"
197 " %A = bitcast i8 undef to i8\n"
200 " %B = bitcast i8 undef to i8\n"
201 " br label %midblock\n"
206 TEST_F(IsPotentiallyReachableTest, BranchToReturn) {
208 "define void @test(i1 %x) {\n"
210 " %A = bitcast i8 undef to i8\n"
211 " br i1 %x, label %block1, label %block2\n"
215 " %B = bitcast i8 undef to i8\n"
221 TEST_F(IsPotentiallyReachableTest, SimpleLoop1) {
223 "declare i1 @switch()\n"
225 "define void @test() {\n"
229 " %B = bitcast i8 undef to i8\n"
230 " %A = bitcast i8 undef to i8\n"
231 " %x = call i1 @switch()\n"
232 " br i1 %x, label %loop, label %exit\n"
239 TEST_F(IsPotentiallyReachableTest, SimpleLoop2) {
241 "declare i1 @switch()\n"
243 "define void @test() {\n"
245 " %B = bitcast i8 undef to i8\n"
248 " %A = bitcast i8 undef to i8\n"
249 " %x = call i1 @switch()\n"
250 " br i1 %x, label %loop, label %exit\n"
257 TEST_F(IsPotentiallyReachableTest, SimpleLoop3) {
259 "declare i1 @switch()\n"
261 "define void @test() {\n"
265 " %B = bitcast i8 undef to i8\n"
266 " %x = call i1 @switch()\n"
267 " br i1 %x, label %loop, label %exit\n"
269 " %A = bitcast i8 undef to i8\n"
276 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) {
278 "declare i1 @switch()\n"
280 "define void @test() {\n"
284 " %A = bitcast i8 undef to i8\n"
285 " %x = call i1 @switch()\n"
286 " br i1 %x, label %loop1, label %loop1exit\n"
290 " %B = bitcast i8 undef to i8\n"
291 " %y = call i1 @switch()\n"
292 " br i1 %x, label %loop2, label %loop2exit\n"
299 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) {
301 "declare i1 @switch()\n"
303 "define void @test() {\n"
307 " %B = bitcast i8 undef to i8\n"
308 " %x = call i1 @switch()\n"
309 " br i1 %x, label %loop1, label %loop1exit\n"
313 " %A = bitcast i8 undef to i8\n"
314 " %y = call i1 @switch()\n"
315 " br i1 %x, label %loop2, label %loop2exit\n"
322 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) {
324 "declare i1 @switch()\n"
326 "define void @test() {\n"
328 " br label %outerloop3\n"
330 " br label %innerloop1\n"
332 " %B = bitcast i8 undef to i8\n"
333 " %x = call i1 @switch()\n"
334 " br i1 %x, label %innerloop1, label %innerloop1exit\n"
336 " br label %innerloop2\n"
338 " %A = bitcast i8 undef to i8\n"
339 " %y = call i1 @switch()\n"
340 " br i1 %x, label %innerloop2, label %innerloop2exit\n"
342 " ;; In outer loop3 now.\n"
343 " %z = call i1 @switch()\n"
344 " br i1 %z, label %outerloop3, label %exit\n"
351 static const char *BranchInsideLoopIR =
352 "declare i1 @switch()\n"
354 "define void @test() {\n"
358 " %x = call i1 @switch()\n"
359 " br i1 %x, label %nextloopblock, label %exit\n"
361 " %y = call i1 @switch()\n"
362 " br i1 %y, label %left, label %right\n"
364 " %A = bitcast i8 undef to i8\n"
367 " %B = bitcast i8 undef to i8\n"
373 TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) {
374 ParseAssembly(BranchInsideLoopIR);
378 TEST_F(IsPotentiallyReachableTest, ModifyTest) {
379 ParseAssembly(BranchInsideLoopIR);
381 succ_iterator S = succ_begin(++M->getFunction("test")->begin());
382 BasicBlock *OldBB = S[0];