Index: llvm/include/llvm/Analysis/LoopInfo.h =================================================================== --- llvm/include/llvm/Analysis/LoopInfo.h +++ llvm/include/llvm/Analysis/LoopInfo.h @@ -570,9 +570,9 @@ bool getIncomingAndBackEdge(BasicBlock *&Incoming, BasicBlock *&Backedge) const; - /// Below are some utilities to get loop bounds and induction variable, and - /// check if a given phinode is an auxiliary induction variable, as well as - /// checking if the loop is canonical. + /// Below are some utilities to get the loop guard, loop bounds and induction + /// variable, and to check if a given phinode is an auxiliary induction + /// variable, if the loop is guarded, and if the loop is canonical. /// /// Here is an example: /// \code @@ -604,6 +604,9 @@ /// /// - getInductionVariable --> i_1 /// - isAuxiliaryInductionVariable(x) --> true if x == i_1 + /// - getLoopGuardBranch() + /// --> `if (guardcmp) goto preheader; else goto afterloop` + /// - isGuarded() --> true /// - isCanonical --> false struct LoopBounds { /// Return the LoopBounds object if @@ -725,6 +728,31 @@ bool isAuxiliaryInductionVariable(PHINode &AuxIndVar, ScalarEvolution &SE) const; + /// Return the loop guard branch, if it exists. + /// + /// This currently only works on simplified loop, as it requires a preheader + /// and a latch to identify the guard. It will work on loops of the form: + /// \code + /// GuardBB: + /// br cond1, Preheader, ExitSucc <== GuardBranch + /// Preheader: + /// br Header + /// Header: + /// ... + /// br Latch + /// Latch: + /// br cond2, Header, ExitBlock + /// ExitBlock: + /// br ExitSucc + /// ExitSucc: + /// \endcode + BranchInst *getLoopGuardBranch() const; + + /// Return true iff the loop is + /// - in simplify rotated form, and + /// - guarded by a loop guard branch. + bool isGuarded() const { return (getLoopGuardBranch() != nullptr); } + /// Return true if the loop induction variable starts at zero and increments /// by one each time through the loop. bool isCanonical(ScalarEvolution &SE) const; Index: llvm/lib/Analysis/LoopInfo.cpp =================================================================== --- llvm/lib/Analysis/LoopInfo.cpp +++ llvm/lib/Analysis/LoopInfo.cpp @@ -359,6 +359,39 @@ return SE.isLoopInvariant(IndDesc.getStep(), this); } +BranchInst *Loop::getLoopGuardBranch() const { + assert(isLoopSimplifyForm() && "Only valid for loop in simplify form"); + BasicBlock *Preheader = getLoopPreheader(); + BasicBlock *Latch = getLoopLatch(); + assert(Preheader && Latch && + "Expecting a loop with valid preheader and latch"); + assert(isLoopExiting(Latch) && "Only valid for rotated loop"); + + Instruction *LatchTI = Latch->getTerminator(); + if (!LatchTI || LatchTI->getNumSuccessors() != 2) + return nullptr; + + BasicBlock *ExitFromLatch = (LatchTI->getSuccessor(0) == getHeader()) + ? LatchTI->getSuccessor(1) + : LatchTI->getSuccessor(0); + BasicBlock *ExitFromLatchSucc = ExitFromLatch->getUniqueSuccessor(); + if (!ExitFromLatchSucc) + return nullptr; + + BasicBlock *GuardBB = Preheader->getUniquePredecessor(); + if (!GuardBB) + return nullptr; + + BranchInst *GuardBI = dyn_cast_or_null(GuardBB->getTerminator()); + if (!GuardBI || GuardBI->getNumSuccessors() != 2) + return nullptr; + + BasicBlock *GuardOtherSucc = (GuardBI->getSuccessor(0) == Preheader) + ? GuardBI->getSuccessor(1) + : GuardBI->getSuccessor(0); + return (GuardOtherSucc == ExitFromLatchSucc) ? GuardBI : nullptr; +} + bool Loop::isCanonical(ScalarEvolution &SE) const { InductionDescriptor IndDesc; if (!getInductionDescriptor(SE, IndDesc)) Index: llvm/unittests/Analysis/LoopInfoTest.cpp =================================================================== --- llvm/unittests/Analysis/LoopInfoTest.cpp +++ llvm/unittests/Analysis/LoopInfoTest.cpp @@ -8,7 +8,6 @@ #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/AssumptionCache.h" -#include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/AsmParser/Parser.h" @@ -33,9 +32,7 @@ /// Build the loop info and scalar evolution for the function and run the Test. static void runWithLoopInfoPlus( Module &M, StringRef FuncName, - function_ref - Test) { + function_ref Test) { auto *F = M.getFunction(FuncName); ASSERT_NE(F, nullptr) << "Could not find " << FuncName; @@ -45,9 +42,7 @@ DominatorTree DT(*F); LoopInfo LI(DT); ScalarEvolution SE(*F, TLI, AC, DT, LI); - - PostDominatorTree PDT(*F); - Test(*F, LI, SE, PDT); + Test(*F, LI, SE); } static std::unique_ptr makeLLVMModule(LLVMContext &Context, @@ -263,9 +258,10 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, - PostDominatorTree &PDT) { + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { Function::iterator FI = F.begin(); + BasicBlock *Entry = &*(FI); + BranchInst *Guard = dyn_cast(Entry->getTerminator()); // First two basic block are entry and for.preheader - skip them. ++FI; BasicBlock *Header = &*(++FI); @@ -287,6 +283,8 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(), Guard); + EXPECT_TRUE(L->isGuarded()); }); } @@ -318,9 +316,10 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, - PostDominatorTree &PDT) { + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { Function::iterator FI = F.begin(); + BasicBlock *Entry = &*(FI); + BranchInst *Guard = dyn_cast(Entry->getTerminator()); // First two basic block are entry and for.preheader - skip them. ++FI; BasicBlock *Header = &*(++FI); @@ -342,6 +341,8 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(), Guard); + EXPECT_TRUE(L->isGuarded()); }); } @@ -373,9 +374,10 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, - PostDominatorTree &PDT) { + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { Function::iterator FI = F.begin(); + BasicBlock *Entry = &*(FI); + BranchInst *Guard = dyn_cast(Entry->getTerminator()); // First two basic block are entry and for.preheader - skip them. ++FI; BasicBlock *Header = &*(++FI); @@ -397,6 +399,8 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(), Guard); + EXPECT_TRUE(L->isGuarded()); }); } @@ -428,9 +432,10 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, - PostDominatorTree &PDT) { + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { Function::iterator FI = F.begin(); + BasicBlock *Entry = &*(FI); + BranchInst *Guard = dyn_cast(Entry->getTerminator()); // First two basic block are entry and for.preheader - skip them. ++FI; BasicBlock *Header = &*(++FI); @@ -452,6 +457,8 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(), Guard); + EXPECT_TRUE(L->isGuarded()); }); } @@ -483,9 +490,10 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, - PostDominatorTree &PDT) { + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { Function::iterator FI = F.begin(); + BasicBlock *Entry = &*(FI); + BranchInst *Guard = dyn_cast(Entry->getTerminator()); // First two basic block are entry and for.preheader - skip them. ++FI; BasicBlock *Header = &*(++FI); @@ -507,6 +515,8 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(), Guard); + EXPECT_TRUE(L->isGuarded()); }); } @@ -539,9 +549,10 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, - PostDominatorTree &PDT) { + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { Function::iterator FI = F.begin(); + BasicBlock *Entry = &*(FI); + BranchInst *Guard = dyn_cast(Entry->getTerminator()); // First two basic block are entry and for.preheader - skip them. ++FI; BasicBlock *Header = &*(++FI); @@ -563,6 +574,8 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(), Guard); + EXPECT_TRUE(L->isGuarded()); }); } @@ -594,9 +607,10 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, - PostDominatorTree &PDT) { + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { Function::iterator FI = F.begin(); + BasicBlock *Entry = &*(FI); + BranchInst *Guard = dyn_cast(Entry->getTerminator()); // First two basic block are entry and for.preheader - skip them. ++FI; BasicBlock *Header = &*(++FI); @@ -615,6 +629,8 @@ EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Unknown); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(), Guard); + EXPECT_TRUE(L->isGuarded()); }); } @@ -646,9 +662,10 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, - PostDominatorTree &PDT) { + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { Function::iterator FI = F.begin(); + BasicBlock *Entry = &*(FI); + BranchInst *Guard = dyn_cast(Entry->getTerminator()); // First two basic block are entry and for.preheader - skip them. ++FI; BasicBlock *Header = &*(++FI); @@ -670,6 +687,8 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(), Guard); + EXPECT_TRUE(L->isGuarded()); }); } @@ -701,9 +720,10 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, - PostDominatorTree &PDT) { + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { Function::iterator FI = F.begin(); + BasicBlock *Entry = &*(FI); + BranchInst *Guard = dyn_cast(Entry->getTerminator()); // First two basic block are entry and for.preheader - skip them. ++FI; BasicBlock *Header = &*(++FI); @@ -725,6 +745,8 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Decreasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(), Guard); + EXPECT_TRUE(L->isGuarded()); }); } @@ -754,32 +776,35 @@ LLVMContext Context; std::unique_ptr M = makeLLVMModule(Context, ModuleStr); - runWithLoopInfoPlus(*M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, - PostDominatorTree &PDT) { - Function::iterator FI = F.begin(); - // First two basic block are entry and for.preheader - // - skip them. - ++FI; - BasicBlock *Header = &*(++FI); - assert(Header->getName() == "for.body"); - Loop *L = LI.getLoopFor(Header); - EXPECT_NE(L, nullptr); - - Optional Bounds = L->getBounds(SE); - EXPECT_NE(Bounds, None); - ConstantInt *InitialIVValue = - dyn_cast(&Bounds->getInitialIVValue()); - EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); - EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); - EXPECT_EQ(Bounds->getStepValue()->getName(), "step"); - EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); - EXPECT_EQ(Bounds->getCanonicalPredicate(), - ICmpInst::BAD_ICMP_PREDICATE); - EXPECT_EQ(Bounds->getDirection(), - Loop::LoopBounds::Direction::Unknown); - EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); - }); + runWithLoopInfoPlus( + *M, "foo", + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + Function::iterator FI = F.begin(); + BasicBlock *Entry = &*(FI); + BranchInst *Guard = dyn_cast(Entry->getTerminator()); + // First two basic block are entry and for.preheader + // - skip them. + ++FI; + BasicBlock *Header = &*(++FI); + assert(Header->getName() == "for.body"); + Loop *L = LI.getLoopFor(Header); + EXPECT_NE(L, nullptr); + + Optional Bounds = L->getBounds(SE); + EXPECT_NE(Bounds, None); + ConstantInt *InitialIVValue = + dyn_cast(&Bounds->getInitialIVValue()); + EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); + EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); + EXPECT_EQ(Bounds->getStepValue()->getName(), "step"); + EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); + EXPECT_EQ(Bounds->getCanonicalPredicate(), + ICmpInst::BAD_ICMP_PREDICATE); + EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Unknown); + EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(), Guard); + EXPECT_TRUE(L->isGuarded()); + }); } TEST(LoopInfoTest, ZextIndVar) { @@ -813,9 +838,10 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, - PostDominatorTree &PDT) { + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { Function::iterator FI = F.begin(); + BasicBlock *Entry = &*(FI); + BranchInst *Guard = dyn_cast(Entry->getTerminator()); // First two basic block are entry and for.preheader - skip them. ++FI; BasicBlock *Header = &*(++FI); @@ -837,6 +863,8 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "indvars.iv"); + EXPECT_EQ(L->getLoopGuardBranch(), Guard); + EXPECT_TRUE(L->isGuarded()); }); } @@ -865,8 +893,7 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, - PostDominatorTree &PDT) { + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { Function::iterator FI = F.begin(); // First basic block is entry - skip it. BasicBlock *Header = &*(++FI); @@ -888,6 +915,8 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(), nullptr); + EXPECT_FALSE(L->isGuarded()); }); } @@ -918,9 +947,10 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, - PostDominatorTree &PDT) { + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { Function::iterator FI = F.begin(); + BasicBlock *Entry = &*(FI); + BranchInst *Guard = dyn_cast(Entry->getTerminator()); // First two basic block are entry and for.preheader - skip them. ++FI; BasicBlock *Header = &*(++FI); @@ -942,6 +972,8 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(), Guard); + EXPECT_TRUE(L->isGuarded()); }); } @@ -984,13 +1016,15 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, - PostDominatorTree &PDT) { + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { Function::iterator FI = F.begin(); + BasicBlock *Entry = &*(FI); + BranchInst *OuterGuard = dyn_cast(Entry->getTerminator()); // First two basic block are entry and for.outer.preheader - skip them. ++FI; BasicBlock *Header = &*(++FI); assert(Header->getName() == "for.outer"); + BranchInst *InnerGuard = dyn_cast(Header->getTerminator()); Loop *L = LI.getLoopFor(Header); EXPECT_NE(L, nullptr); @@ -1008,6 +1042,8 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "j"); + EXPECT_EQ(L->getLoopGuardBranch(), OuterGuard); + EXPECT_TRUE(L->isGuarded()); // Next two basic blocks are for.outer and for.inner.preheader - skip // them. @@ -1030,6 +1066,8 @@ EXPECT_EQ(InnerBounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(), InnerGuard); + EXPECT_TRUE(L->isGuarded()); }); } @@ -1070,9 +1108,10 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, - PostDominatorTree &PDT) { + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { Function::iterator FI = F.begin(); + BasicBlock *Entry = &*(FI); + BranchInst *Guard = dyn_cast(Entry->getTerminator()); // First two basic block are entry and for.preheader - skip them. ++FI; BasicBlock *Header = &*(++FI); @@ -1108,6 +1147,8 @@ PHINode &Instruction_mulopcode = cast(*(++II)); EXPECT_FALSE( L->isAuxiliaryInductionVariable(Instruction_mulopcode, SE)); + EXPECT_EQ(L->getLoopGuardBranch(), Guard); + EXPECT_TRUE(L->isGuarded()); }); }