From 2d0896c1cb90243f12df698e84458016c0c121dc Mon Sep 17 00:00:00 2001 From: Whitney Tsang Date: Wed, 5 Jun 2019 20:42:47 +0000 Subject: [LOOPINFO] Extend Loop object to add utilities to get the loop bounds, step, and loop induction variable. Summary: This PR extends the loop object with more utilities to get loop bounds, step, and loop induction variable. There already exists passes which try to obtain the loop induction variable in their own pass, e.g. loop interchange. It would be useful to have a common area to get these information. /// Example: /// for (int i = lb; i < ub; i+=step) /// /// --- pseudo LLVMIR --- /// beforeloop: /// guardcmp = (lb < ub) /// if (guardcmp) goto preheader; else goto afterloop /// preheader: /// loop: /// i1 = phi[{lb, preheader}, {i2, latch}] /// /// i2 = i1 + step /// latch: /// cmp = (i2 < ub) /// if (cmp) goto loop /// exit: /// afterloop: /// /// getBounds /// getInitialIVValue --> lb /// getStepInst --> i2 = i1 + step /// getStepValue --> step /// getFinalIVValue --> ub /// getCanonicalPredicate --> '<' /// getDirection --> Increasing /// getInductionVariable --> i1 /// getAuxiliaryInductionVariable --> {i1} /// isCanonical --> false Reviewers: kbarton, hfinkel, dmgreen, Meinersbur, jdoerfert, syzaara, fhahn Reviewed By: kbarton Subscribers: tvvikram, bmahjour, etiotto, fhahn, jsji, hiraditya, llvm-commits Tag: LLVM Differential Revision: https://reviews.llvm.org/D60565 llvm-svn: 362644 --- llvm/lib/Analysis/LoopInfo.cpp | 214 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 214 insertions(+) (limited to 'llvm/lib/Analysis/LoopInfo.cpp') diff --git a/llvm/lib/Analysis/LoopInfo.cpp b/llvm/lib/Analysis/LoopInfo.cpp index aa933d98f24..00dbe30c2b3 100644 --- a/llvm/lib/Analysis/LoopInfo.cpp +++ b/llvm/lib/Analysis/LoopInfo.cpp @@ -17,10 +17,12 @@ #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/ScopeExit.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/IVDescriptors.h" #include "llvm/Analysis/LoopInfoImpl.h" #include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/MemorySSAUpdater.h" +#include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/Config/llvm-config.h" #include "llvm/IR/CFG.h" @@ -164,6 +166,218 @@ PHINode *Loop::getCanonicalInductionVariable() const { return nullptr; } +/// Get the latch condition instruction. +static ICmpInst *getLatchCmpInst(const Loop &L) { + if (BasicBlock *Latch = L.getLoopLatch()) + if (BranchInst *BI = dyn_cast_or_null(Latch->getTerminator())) + if (BI->isConditional()) + return dyn_cast(BI->getCondition()); + + return nullptr; +} + +/// Return the final value of the loop induction variable if found. +static Value *findFinalIVValue(const Loop &L, const PHINode &IndVar, + const Instruction &StepInst) { + ICmpInst *LatchCmpInst = getLatchCmpInst(L); + if (!LatchCmpInst) + return nullptr; + + Value *Op0 = LatchCmpInst->getOperand(0); + Value *Op1 = LatchCmpInst->getOperand(1); + if (Op0 == &IndVar || Op0 == &StepInst) + return Op1; + + if (Op1 == &IndVar || Op1 == &StepInst) + return Op0; + + return nullptr; +} + +Optional Loop::LoopBounds::getBounds(const Loop &L, + PHINode &IndVar, + ScalarEvolution &SE) { + InductionDescriptor IndDesc; + if (!InductionDescriptor::isInductionPHI(&IndVar, &L, &SE, IndDesc)) + return None; + + Value *InitialIVValue = IndDesc.getStartValue(); + Instruction *StepInst = IndDesc.getInductionBinOp(); + if (!InitialIVValue || !StepInst) + return None; + + const SCEV *Step = IndDesc.getStep(); + Value *StepInstOp1 = StepInst->getOperand(1); + Value *StepInstOp0 = StepInst->getOperand(0); + Value *StepValue = nullptr; + if (SE.getSCEV(StepInstOp1) == Step) + StepValue = StepInstOp1; + else if (SE.getSCEV(StepInstOp0) == Step) + StepValue = StepInstOp0; + + Value *FinalIVValue = findFinalIVValue(L, IndVar, *StepInst); + if (!FinalIVValue) + return None; + + return LoopBounds(L, *InitialIVValue, *StepInst, StepValue, *FinalIVValue, + SE); +} + +using Direction = Loop::LoopBounds::Direction; + +ICmpInst::Predicate Loop::LoopBounds::getCanonicalPredicate() const { + BasicBlock *Latch = L.getLoopLatch(); + assert(Latch && "Expecting valid latch"); + + BranchInst *BI = dyn_cast_or_null(Latch->getTerminator()); + assert(BI && BI->isConditional() && "Expecting conditional latch branch"); + + ICmpInst *LatchCmpInst = dyn_cast(BI->getCondition()); + assert(LatchCmpInst && + "Expecting the latch compare instruction to be a CmpInst"); + + // Need to inverse the predicate when first successor is not the loop + // header + ICmpInst::Predicate Pred = (BI->getSuccessor(0) == L.getHeader()) + ? LatchCmpInst->getPredicate() + : LatchCmpInst->getInversePredicate(); + + if (LatchCmpInst->getOperand(0) == &getFinalIVValue()) + Pred = ICmpInst::getSwappedPredicate(Pred); + + // Need to flip strictness of the predicate when the latch compare instruction + // is not using StepInst + if (LatchCmpInst->getOperand(0) == &getStepInst() || + LatchCmpInst->getOperand(1) == &getStepInst()) + return Pred; + + // Cannot flip strictness of NE and EQ + if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ) + return ICmpInst::getFlippedStrictnessPredicate(Pred); + + Direction D = getDirection(); + if (D == Direction::Increasing) + return ICmpInst::ICMP_SLT; + + if (D == Direction::Decreasing) + return ICmpInst::ICMP_SGT; + + // If cannot determine the direction, then unable to find the canonical + // predicate + return ICmpInst::BAD_ICMP_PREDICATE; +} + +Direction Loop::LoopBounds::getDirection() const { + if (const SCEVAddRecExpr *StepAddRecExpr = + dyn_cast(SE.getSCEV(&getStepInst()))) + if (const SCEV *StepRecur = StepAddRecExpr->getStepRecurrence(SE)) { + if (SE.isKnownPositive(StepRecur)) + return Direction::Increasing; + if (SE.isKnownNegative(StepRecur)) + return Direction::Decreasing; + } + + return Direction::Unknown; +} + +Optional Loop::getBounds(ScalarEvolution &SE) const { + if (PHINode *IndVar = getInductionVariable(SE)) + return LoopBounds::getBounds(*this, *IndVar, SE); + + return None; +} + +PHINode *Loop::getInductionVariable(ScalarEvolution &SE) const { + if (!isLoopSimplifyForm()) + return nullptr; + + BasicBlock *Header = getHeader(); + assert(Header && "Expected a valid loop header"); + ICmpInst *CmpInst = getLatchCmpInst(*this); + if (!CmpInst) + return nullptr; + + Instruction *LatchCmpOp0 = dyn_cast(CmpInst->getOperand(0)); + Instruction *LatchCmpOp1 = dyn_cast(CmpInst->getOperand(1)); + + for (PHINode &IndVar : Header->phis()) { + InductionDescriptor IndDesc; + if (!InductionDescriptor::isInductionPHI(&IndVar, this, &SE, IndDesc)) + continue; + + Instruction *StepInst = IndDesc.getInductionBinOp(); + + // case 1: + // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}] + // StepInst = IndVar + step + // cmp = StepInst < FinalValue + if (StepInst == LatchCmpOp0 || StepInst == LatchCmpOp1) + return &IndVar; + + // case 2: + // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}] + // StepInst = IndVar + step + // cmp = IndVar < FinalValue + if (&IndVar == LatchCmpOp0 || &IndVar == LatchCmpOp1) + return &IndVar; + } + + return nullptr; +} + +bool Loop::getInductionDescriptor(ScalarEvolution &SE, + InductionDescriptor &IndDesc) const { + if (PHINode *IndVar = getInductionVariable(SE)) + return InductionDescriptor::isInductionPHI(IndVar, this, &SE, IndDesc); + + return false; +} + +bool Loop::isAuxiliaryInductionVariable(PHINode &AuxIndVar, + ScalarEvolution &SE) const { + // Located in the loop header + BasicBlock *Header = getHeader(); + if (AuxIndVar.getParent() != Header) + return false; + + // No uses outside of the loop + for (User *U : AuxIndVar.users()) + if (const Instruction *I = dyn_cast(U)) + if (!contains(I)) + return false; + + InductionDescriptor IndDesc; + if (!InductionDescriptor::isInductionPHI(&AuxIndVar, this, &SE, IndDesc)) + return false; + + // The step instruction opcode should be add or sub. + if (IndDesc.getInductionOpcode() != Instruction::Add && + IndDesc.getInductionOpcode() != Instruction::Sub) + return false; + + // Incremented by a loop invariant step for each loop iteration + return SE.isLoopInvariant(IndDesc.getStep(), this); +} + +bool Loop::isCanonical(ScalarEvolution &SE) const { + InductionDescriptor IndDesc; + if (!getInductionDescriptor(SE, IndDesc)) + return false; + + ConstantInt *Init = dyn_cast_or_null(IndDesc.getStartValue()); + if (!Init || !Init->isZero()) + return false; + + if (IndDesc.getInductionOpcode() != Instruction::Add) + return false; + + ConstantInt *Step = IndDesc.getConstIntStepValue(); + if (!Step || !Step->isOne()) + return false; + + return true; +} + // Check that 'BB' doesn't have any uses outside of the 'L' static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB, DominatorTree &DT) { -- cgit v1.2.3