Index: llvm/include/llvm/Analysis/LoopInfo.h =================================================================== --- llvm/include/llvm/Analysis/LoopInfo.h +++ llvm/include/llvm/Analysis/LoopInfo.h @@ -58,6 +58,7 @@ class MDNode; class MemorySSAUpdater; class PHINode; +class PostDominatorTree; class ScalarEvolution; class raw_ostream; template class DominatorTreeBase; @@ -565,9 +566,10 @@ 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 a given branch instruction is a loop guard, if the loop is + /// guarded, and if the loop is canonical. /// /// Here is an example: /// \code @@ -599,6 +601,11 @@ /// /// - getInductionVariable --> i_1 /// - isAuxiliaryInductionVariable(x) --> true if x == i_1 + /// - getLoopGuardBranch() + /// --> `if (guardcmp) goto preheader; else goto afterloop` + /// - isLoopGuardBranch(`if (guardcmp) goto preheader; else goto afterloop`) + /// --> true + /// - isGuarded() --> true /// - isCanonical --> false struct LoopBounds { /// Return the LoopBounds object if @@ -720,6 +727,21 @@ bool isAuxiliaryInductionVariable(PHINode &AuxIndVar, ScalarEvolution &SE) const; + /// Return the closest loop guard before the loop, by traversing up the + /// dominator tree. + BranchInst *getLoopGuardBranch(const DominatorTree &DT, + const PostDominatorTree &PDT) const; + + /// Return true iff one successor of the given branch instruction \p BI + /// dominates the loop header, and the other successor postdominates the loop + /// header, i.e. the branch instruction \p BI is a loop guard. + bool isLoopGuardBranch(const BranchInst &BI, const DominatorTree &DT, + const PostDominatorTree &PDT) const; + + /// Return true iff the loop is guarded by at least one loop guard branch. + bool isGuarded(const DominatorTree &DT, + const PostDominatorTree &PDT) const; + /// 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 @@ -22,6 +22,7 @@ #include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/MemorySSAUpdater.h" +#include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/Config/llvm-config.h" @@ -359,6 +360,44 @@ return SE.isLoopInvariant(IndDesc.getStep(), this); } +BranchInst *Loop::getLoopGuardBranch(const DominatorTree &DT, + const PostDominatorTree &PDT) const { + BasicBlock *Header = getHeader(); + assert(Header && "Expecting a valid loop header"); + + DomTreeNode *IDomNode = DT.getNode(Header)->getIDom(); + + while (IDomNode && IDomNode->getBlock()) { + BasicBlock *IDomBB = IDomNode->getBlock(); + if (BranchInst *BI = dyn_cast_or_null(IDomBB->getTerminator())) + if (isLoopGuardBranch(*BI, DT, PDT)) + return BI; + + IDomNode = IDomNode->getIDom(); + } + + return nullptr; +} + +bool Loop::isLoopGuardBranch(const BranchInst &BI, const DominatorTree &DT, + const PostDominatorTree &PDT) const { + if (!BI.isConditional()) + return false; + + assert(BI.getNumSuccessors() == 2 && "Expecting BI to have 2 successors"); + + BasicBlock *Succ0 = BI.getSuccessor(0); + BasicBlock *Succ1 = BI.getSuccessor(1); + BasicBlock *Header = getHeader(); + return (DT.dominates(Succ0, Header) && PDT.dominates(Succ1, Header)) || + (DT.dominates(Succ1, Header) && PDT.dominates(Succ0, Header)); +} + +bool Loop::isGuarded(const DominatorTree &DT, + const PostDominatorTree &PDT) const { + return (getLoopGuardBranch(DT, PDT) != 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 @@ -34,7 +34,7 @@ static void runWithLoopInfoPlus( Module &M, StringRef FuncName, function_ref + DominatorTree &DT, PostDominatorTree &PDT)> Test) { auto *F = M.getFunction(FuncName); ASSERT_NE(F, nullptr) << "Could not find " << FuncName; @@ -47,7 +47,7 @@ ScalarEvolution SE(*F, TLI, AC, DT, LI); PostDominatorTree PDT(*F); - Test(*F, LI, SE, PDT); + Test(*F, LI, SE, DT, PDT); } static std::unique_ptr makeLLVMModule(LLVMContext &Context, @@ -263,9 +263,11 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, PostDominatorTree &PDT) { 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 +289,9 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(DT, PDT), Guard); + EXPECT_TRUE(L->isLoopGuardBranch(*Guard, DT, PDT)); + EXPECT_TRUE(L->isGuarded(DT, PDT)); }); } @@ -318,9 +323,11 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, PostDominatorTree &PDT) { 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 +349,9 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(DT, PDT), Guard); + EXPECT_TRUE(L->isLoopGuardBranch(*Guard, DT, PDT)); + EXPECT_TRUE(L->isGuarded(DT, PDT)); }); } @@ -373,9 +383,11 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, PostDominatorTree &PDT) { 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 +409,9 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(DT, PDT), Guard); + EXPECT_TRUE(L->isLoopGuardBranch(*Guard, DT, PDT)); + EXPECT_TRUE(L->isGuarded(DT, PDT)); }); } @@ -428,9 +443,11 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, PostDominatorTree &PDT) { 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 +469,9 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(DT, PDT), Guard); + EXPECT_TRUE(L->isLoopGuardBranch(*Guard, DT, PDT)); + EXPECT_TRUE(L->isGuarded(DT, PDT)); }); } @@ -483,9 +503,11 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, PostDominatorTree &PDT) { 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 +529,9 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(DT, PDT), Guard); + EXPECT_TRUE(L->isLoopGuardBranch(*Guard, DT, PDT)); + EXPECT_TRUE(L->isGuarded(DT, PDT)); }); } @@ -539,9 +564,11 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, PostDominatorTree &PDT) { 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 +590,9 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(DT, PDT), Guard); + EXPECT_TRUE(L->isLoopGuardBranch(*Guard, DT, PDT)); + EXPECT_TRUE(L->isGuarded(DT, PDT)); }); } @@ -594,9 +624,11 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, PostDominatorTree &PDT) { 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 +647,9 @@ 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(DT, PDT), Guard); + EXPECT_TRUE(L->isLoopGuardBranch(*Guard, DT, PDT)); + EXPECT_TRUE(L->isGuarded(DT, PDT)); }); } @@ -646,9 +681,11 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, PostDominatorTree &PDT) { 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 +707,9 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(DT, PDT), Guard); + EXPECT_TRUE(L->isLoopGuardBranch(*Guard, DT, PDT)); + EXPECT_TRUE(L->isGuarded(DT, PDT)); }); } @@ -701,9 +741,11 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, PostDominatorTree &PDT) { 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 +767,9 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Decreasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(DT, PDT), Guard); + EXPECT_TRUE(L->isLoopGuardBranch(*Guard, DT, PDT)); + EXPECT_TRUE(L->isGuarded(DT, PDT)); }); } @@ -754,32 +799,37 @@ 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, DominatorTree &DT, + PostDominatorTree &PDT) { + 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(DT, PDT), Guard); + EXPECT_TRUE(L->isLoopGuardBranch(*Guard, DT, PDT)); + EXPECT_TRUE(L->isGuarded(DT, PDT)); + }); } TEST(LoopInfoTest, ZextIndVar) { @@ -813,9 +863,11 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, PostDominatorTree &PDT) { 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 +889,9 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "indvars.iv"); + EXPECT_EQ(L->getLoopGuardBranch(DT, PDT), Guard); + EXPECT_TRUE(L->isLoopGuardBranch(*Guard, DT, PDT)); + EXPECT_TRUE(L->isGuarded(DT, PDT)); }); } @@ -865,9 +920,11 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, PostDominatorTree &PDT) { Function::iterator FI = F.begin(); + BasicBlock *Entry = &*(FI); + BranchInst *NotGuard = dyn_cast(Entry->getTerminator()); // First basic block is entry - skip it. BasicBlock *Header = &*(++FI); assert(Header->getName() == "for.body"); @@ -888,6 +945,9 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(DT, PDT), nullptr); + EXPECT_FALSE(L->isLoopGuardBranch(*NotGuard, DT, PDT)); + EXPECT_FALSE(L->isGuarded(DT, PDT)); }); } @@ -918,9 +978,11 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, PostDominatorTree &PDT) { 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 +1004,9 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(DT, PDT), Guard); + EXPECT_TRUE(L->isLoopGuardBranch(*Guard, DT, PDT)); + EXPECT_TRUE(L->isGuarded(DT, PDT)); }); } @@ -984,13 +1049,16 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, PostDominatorTree &PDT) { 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 +1076,9 @@ EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "j"); + EXPECT_EQ(L->getLoopGuardBranch(DT, PDT), OuterGuard); + EXPECT_TRUE(L->isLoopGuardBranch(*OuterGuard, DT, PDT)); + EXPECT_TRUE(L->isGuarded(DT, PDT)); // Next two basic blocks are for.outer and for.inner.preheader - skip // them. @@ -1030,6 +1101,9 @@ EXPECT_EQ(InnerBounds->getDirection(), Loop::LoopBounds::Direction::Increasing); EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + EXPECT_EQ(L->getLoopGuardBranch(DT, PDT), InnerGuard); + EXPECT_TRUE(L->isLoopGuardBranch(*InnerGuard, DT, PDT)); + EXPECT_TRUE(L->isGuarded(DT, PDT)); }); } @@ -1070,9 +1144,11 @@ runWithLoopInfoPlus( *M, "foo", - [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, PostDominatorTree &PDT) { 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,5 +1184,8 @@ PHINode &Instruction_mulopcode = cast(*(++II)); EXPECT_FALSE( L->isAuxiliaryInductionVariable(Instruction_mulopcode, SE)); + EXPECT_EQ(L->getLoopGuardBranch(DT, PDT), Guard); + EXPECT_TRUE(L->isLoopGuardBranch(*Guard, DT, PDT)); + EXPECT_TRUE(L->isGuarded(DT, PDT)); }); }