181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky//===- CFGTest.cpp - CFG tests --------------------------------------------===// 281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// 381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// The LLVM Compiler Infrastructure 481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// 581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// This file is distributed under the University of Illinois Open Source 681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// License. See LICENSE.TXT for details. 781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// 881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky//===----------------------------------------------------------------------===// 981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 1081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#include "llvm/Analysis/CFG.h" 1181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#include "llvm/Analysis/LoopInfo.h" 1236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/AsmParser/Parser.h" 1336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 1481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#include "llvm/IR/Function.h" 1536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/InstIterator.h" 1636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/LLVMContext.h" 1781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#include "llvm/IR/Module.h" 1881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#include "llvm/Pass.h" 1981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#include "llvm/PassManager.h" 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/ErrorHandling.h" 2136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/SourceMgr.h" 2281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#include "gtest/gtest.h" 2381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 2481e480463d8bb57776d03cebfd083762909023f1Nick Lewyckyusing namespace llvm; 2581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 2681e480463d8bb57776d03cebfd083762909023f1Nick Lewyckynamespace { 2781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 2881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// This fixture assists in running the isPotentiallyReachable utility four ways 2981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// and ensuring it produces the correct answer each time. 3081e480463d8bb57776d03cebfd083762909023f1Nick Lewyckyclass IsPotentiallyReachableTest : public testing::Test { 3181e480463d8bb57776d03cebfd083762909023f1Nick Lewyckyprotected: 3281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky void ParseAssembly(const char *Assembly) { 3381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky M.reset(new Module("Module", getGlobalContext())); 3481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 3581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky SMDiagnostic Error; 3681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky bool Parsed = ParseAssemblyString(Assembly, M.get(), 3781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky Error, M->getContext()) == M.get(); 3881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 3981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky std::string errMsg; 4081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky raw_string_ostream os(errMsg); 4181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky Error.print("", os); 4281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 4381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky if (!Parsed) { 4481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky // A failure here means that the test itself is buggy. 4581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky report_fatal_error(os.str().c_str()); 4681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky } 4781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 4881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky Function *F = M->getFunction("test"); 49cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (F == nullptr) 5081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky report_fatal_error("Test must have a function named @test"); 5181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 52cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines A = B = nullptr; 5381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { 5481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky if (I->hasName()) { 5581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky if (I->getName() == "A") 5681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky A = &*I; 5781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky else if (I->getName() == "B") 5881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky B = &*I; 5981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky } 6081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky } 61cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (A == nullptr) 6281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky report_fatal_error("@test must have an instruction %A"); 63cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (B == nullptr) 6481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky report_fatal_error("@test must have an instruction %B"); 6581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky } 6681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 6781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky void ExpectPath(bool ExpectedResult) { 6881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky static char ID; 6981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky class IsPotentiallyReachableTestPass : public FunctionPass { 7081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky public: 7181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky IsPotentiallyReachableTestPass(bool ExpectedResult, 7281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky Instruction *A, Instruction *B) 7381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B) {} 7481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 7581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky static int initialize() { 7681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass", 77cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines "", &ID, nullptr, true, true); 7881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky PassRegistry::getPassRegistry()->registerPass(*PI, false); 7981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky initializeLoopInfoPass(*PassRegistry::getPassRegistry()); 8036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines initializeDominatorTreeWrapperPassPass( 8136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines *PassRegistry::getPassRegistry()); 8281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky return 0; 8381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky } 8481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 8581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky void getAnalysisUsage(AnalysisUsage &AU) const { 8681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky AU.setPreservesAll(); 8781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky AU.addRequired<LoopInfo>(); 8836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addRequired<DominatorTreeWrapperPass>(); 8981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky } 9081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 9181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky bool runOnFunction(Function &F) { 9281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky if (!F.hasName() || F.getName() != "test") 9381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky return false; 9481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 9581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky LoopInfo *LI = &getAnalysis<LoopInfo>(); 9636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree *DT = 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 98cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, nullptr), 99cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ExpectedResult); 100cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines EXPECT_EQ(isPotentiallyReachable(A, B, DT, nullptr), ExpectedResult); 101cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, LI), ExpectedResult); 10281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky EXPECT_EQ(isPotentiallyReachable(A, B, DT, LI), ExpectedResult); 10381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky return false; 10481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky } 10581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky bool ExpectedResult; 10681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky Instruction *A, *B; 10781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky }; 10881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 10981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky static int initialize = IsPotentiallyReachableTestPass::initialize(); 11081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky (void)initialize; 11181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 11281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky IsPotentiallyReachableTestPass *P = 11381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky new IsPotentiallyReachableTestPass(ExpectedResult, A, B); 11481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky PassManager PM; 11581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky PM.add(P); 11681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky PM.run(*M); 11781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky } 11836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 11936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::unique_ptr<Module> M; 12081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky Instruction *A, *B; 12181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky}; 12281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 12381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky} 12481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 12581e480463d8bb57776d03cebfd083762909023f1Nick LewyckyTEST_F(IsPotentiallyReachableTest, SameBlockNoPath) { 12681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ParseAssembly( 12781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "define void @test() {\n" 12881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "entry:\n" 12981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " bitcast i8 undef to i8\n" 13081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %B = bitcast i8 undef to i8\n" 13181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " bitcast i8 undef to i8\n" 13281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " bitcast i8 undef to i8\n" 13381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %A = bitcast i8 undef to i8\n" 13481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " ret void\n" 13581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "}\n"); 13681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ExpectPath(false); 13781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky} 13881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 13981e480463d8bb57776d03cebfd083762909023f1Nick LewyckyTEST_F(IsPotentiallyReachableTest, SameBlockPath) { 14081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ParseAssembly( 14181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "define void @test() {\n" 14281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "entry:\n" 14381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %A = bitcast i8 undef to i8\n" 14481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " bitcast i8 undef to i8\n" 14581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " bitcast i8 undef to i8\n" 14681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %B = bitcast i8 undef to i8\n" 14781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " ret void\n" 14881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "}\n"); 14981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ExpectPath(true); 15081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky} 15181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 15272dba254ae65b06062106910a70d46f21e19d55aNick LewyckyTEST_F(IsPotentiallyReachableTest, SameBlockNoLoop) { 15372dba254ae65b06062106910a70d46f21e19d55aNick Lewycky ParseAssembly( 15472dba254ae65b06062106910a70d46f21e19d55aNick Lewycky "define void @test() {\n" 15572dba254ae65b06062106910a70d46f21e19d55aNick Lewycky "entry:\n" 15672dba254ae65b06062106910a70d46f21e19d55aNick Lewycky " br label %middle\n" 15772dba254ae65b06062106910a70d46f21e19d55aNick Lewycky "middle:\n" 15872dba254ae65b06062106910a70d46f21e19d55aNick Lewycky " %B = bitcast i8 undef to i8\n" 15972dba254ae65b06062106910a70d46f21e19d55aNick Lewycky " bitcast i8 undef to i8\n" 16072dba254ae65b06062106910a70d46f21e19d55aNick Lewycky " bitcast i8 undef to i8\n" 16172dba254ae65b06062106910a70d46f21e19d55aNick Lewycky " %A = bitcast i8 undef to i8\n" 16272dba254ae65b06062106910a70d46f21e19d55aNick Lewycky " br label %nextblock\n" 16372dba254ae65b06062106910a70d46f21e19d55aNick Lewycky "nextblock:\n" 16472dba254ae65b06062106910a70d46f21e19d55aNick Lewycky " ret void\n" 16572dba254ae65b06062106910a70d46f21e19d55aNick Lewycky "}\n"); 16672dba254ae65b06062106910a70d46f21e19d55aNick Lewycky ExpectPath(false); 16772dba254ae65b06062106910a70d46f21e19d55aNick Lewycky} 16872dba254ae65b06062106910a70d46f21e19d55aNick Lewycky 16981e480463d8bb57776d03cebfd083762909023f1Nick LewyckyTEST_F(IsPotentiallyReachableTest, StraightNoPath) { 17081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ParseAssembly( 17181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "define void @test() {\n" 17281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "entry:\n" 17381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %B = bitcast i8 undef to i8\n" 17481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br label %exit\n" 17581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "exit:\n" 17681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %A = bitcast i8 undef to i8\n" 17781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " ret void\n" 17881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "}"); 17981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ExpectPath(false); 18081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky} 18181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 18281e480463d8bb57776d03cebfd083762909023f1Nick LewyckyTEST_F(IsPotentiallyReachableTest, StraightPath) { 18381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ParseAssembly( 18481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "define void @test() {\n" 18581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "entry:\n" 18681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %A = bitcast i8 undef to i8\n" 18781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br label %exit\n" 18881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "exit:\n" 18981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %B = bitcast i8 undef to i8\n" 19081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " ret void\n" 19181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "}"); 19281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ExpectPath(true); 19381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky} 19481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 19581e480463d8bb57776d03cebfd083762909023f1Nick LewyckyTEST_F(IsPotentiallyReachableTest, DestUnreachable) { 19681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ParseAssembly( 19781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "define void @test() {\n" 19881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "entry:\n" 19981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br label %midblock\n" 20081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "midblock:\n" 20181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %A = bitcast i8 undef to i8\n" 20281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " ret void\n" 20381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "unreachable:\n" 20481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %B = bitcast i8 undef to i8\n" 20581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br label %midblock\n" 20681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "}"); 20781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ExpectPath(false); 20881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky} 20981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 21081e480463d8bb57776d03cebfd083762909023f1Nick LewyckyTEST_F(IsPotentiallyReachableTest, BranchToReturn) { 21181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ParseAssembly( 21281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "define void @test(i1 %x) {\n" 21381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "entry:\n" 21481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %A = bitcast i8 undef to i8\n" 21581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br i1 %x, label %block1, label %block2\n" 21681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "block1:\n" 21781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " ret void\n" 21881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "block2:\n" 21981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %B = bitcast i8 undef to i8\n" 22081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " ret void\n" 22181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "}"); 22281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ExpectPath(true); 22381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky} 22481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 22581e480463d8bb57776d03cebfd083762909023f1Nick LewyckyTEST_F(IsPotentiallyReachableTest, SimpleLoop1) { 22681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ParseAssembly( 22781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "declare i1 @switch()\n" 22881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "\n" 22981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "define void @test() {\n" 23081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "entry:\n" 23181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br label %loop\n" 23281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "loop:\n" 23381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %B = bitcast i8 undef to i8\n" 23481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %A = bitcast i8 undef to i8\n" 23581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %x = call i1 @switch()\n" 23681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br i1 %x, label %loop, label %exit\n" 23781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "exit:\n" 23881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " ret void\n" 23981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "}"); 24081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ExpectPath(true); 24181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky} 24281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 24381e480463d8bb57776d03cebfd083762909023f1Nick LewyckyTEST_F(IsPotentiallyReachableTest, SimpleLoop2) { 24481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ParseAssembly( 24581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "declare i1 @switch()\n" 24681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "\n" 24781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "define void @test() {\n" 24881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "entry:\n" 24981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %B = bitcast i8 undef to i8\n" 25081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br label %loop\n" 25181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "loop:\n" 25281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %A = bitcast i8 undef to i8\n" 25381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %x = call i1 @switch()\n" 25481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br i1 %x, label %loop, label %exit\n" 25581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "exit:\n" 25681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " ret void\n" 25781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "}"); 25881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ExpectPath(false); 25981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky} 26081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 26181e480463d8bb57776d03cebfd083762909023f1Nick LewyckyTEST_F(IsPotentiallyReachableTest, SimpleLoop3) { 26281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ParseAssembly( 26381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "declare i1 @switch()\n" 26481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "\n" 26581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "define void @test() {\n" 26681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "entry:\n" 26781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br label %loop\n" 26881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "loop:\n" 26981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %B = bitcast i8 undef to i8\n" 27081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %x = call i1 @switch()\n" 27181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br i1 %x, label %loop, label %exit\n" 27281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "exit:\n" 27381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %A = bitcast i8 undef to i8\n" 27481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " ret void\n" 27581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "}"); 27681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ExpectPath(false); 27781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky} 27881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 27981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 28081e480463d8bb57776d03cebfd083762909023f1Nick LewyckyTEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) { 28181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ParseAssembly( 28281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "declare i1 @switch()\n" 28381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "\n" 28481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "define void @test() {\n" 28581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "entry:\n" 28681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br label %loop1\n" 28781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "loop1:\n" 28881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %A = bitcast i8 undef to i8\n" 28981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %x = call i1 @switch()\n" 29081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br i1 %x, label %loop1, label %loop1exit\n" 29181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "loop1exit:\n" 29281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br label %loop2\n" 29381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "loop2:\n" 29481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %B = bitcast i8 undef to i8\n" 29581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %y = call i1 @switch()\n" 29681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br i1 %x, label %loop2, label %loop2exit\n" 29781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "loop2exit:" 29881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " ret void\n" 29981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "}"); 30081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ExpectPath(true); 30181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky} 30281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 30381e480463d8bb57776d03cebfd083762909023f1Nick LewyckyTEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) { 30481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ParseAssembly( 30581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "declare i1 @switch()\n" 30681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "\n" 30781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "define void @test() {\n" 30881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "entry:\n" 30981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br label %loop1\n" 31081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "loop1:\n" 31181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %B = bitcast i8 undef to i8\n" 31281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %x = call i1 @switch()\n" 31381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br i1 %x, label %loop1, label %loop1exit\n" 31481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "loop1exit:\n" 31581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br label %loop2\n" 31681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "loop2:\n" 31781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %A = bitcast i8 undef to i8\n" 31881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %y = call i1 @switch()\n" 31981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br i1 %x, label %loop2, label %loop2exit\n" 32081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "loop2exit:" 32181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " ret void\n" 32281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "}"); 32381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ExpectPath(false); 32481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky} 32581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 32681e480463d8bb57776d03cebfd083762909023f1Nick LewyckyTEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) { 32781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ParseAssembly( 32881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "declare i1 @switch()\n" 32981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "\n" 33081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "define void @test() {\n" 33181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "entry:\n" 33281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br label %outerloop3\n" 33381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "outerloop3:\n" 33481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br label %innerloop1\n" 33581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "innerloop1:\n" 33681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %B = bitcast i8 undef to i8\n" 33781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %x = call i1 @switch()\n" 33881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br i1 %x, label %innerloop1, label %innerloop1exit\n" 33981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "innerloop1exit:\n" 34081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br label %innerloop2\n" 34181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "innerloop2:\n" 34281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %A = bitcast i8 undef to i8\n" 34381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %y = call i1 @switch()\n" 34481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br i1 %x, label %innerloop2, label %innerloop2exit\n" 34581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "innerloop2exit:" 34681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " ;; In outer loop3 now.\n" 34781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " %z = call i1 @switch()\n" 34881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " br i1 %z, label %outerloop3, label %exit\n" 34981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "exit:\n" 35081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky " ret void\n" 35181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky "}"); 35281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ExpectPath(true); 35381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky} 35481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 35536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic const char *BranchInsideLoopIR = 35636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "declare i1 @switch()\n" 35736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "\n" 35836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "define void @test() {\n" 35936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "entry:\n" 36036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines " br label %loop\n" 36136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "loop:\n" 36236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines " %x = call i1 @switch()\n" 36336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines " br i1 %x, label %nextloopblock, label %exit\n" 36436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "nextloopblock:\n" 36536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines " %y = call i1 @switch()\n" 36636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines " br i1 %y, label %left, label %right\n" 36736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "left:\n" 36836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines " %A = bitcast i8 undef to i8\n" 36936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines " br label %loop\n" 37036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "right:\n" 37136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines " %B = bitcast i8 undef to i8\n" 37236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines " br label %loop\n" 37336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "exit:\n" 37436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines " ret void\n" 37536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "}"; 37636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 37781e480463d8bb57776d03cebfd083762909023f1Nick LewyckyTEST_F(IsPotentiallyReachableTest, BranchInsideLoop) { 37836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ParseAssembly(BranchInsideLoopIR); 37936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExpectPath(true); 38036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 38136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 38236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesTEST_F(IsPotentiallyReachableTest, ModifyTest) { 38336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ParseAssembly(BranchInsideLoopIR); 38436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 38536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines succ_iterator S = succ_begin(++M->getFunction("test")->begin()); 38636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *OldBB = S[0]; 38736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines S[0] = S[1]; 38836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExpectPath(false); 38936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines S[0] = OldBB; 39081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky ExpectPath(true); 39181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky} 392