Index: llvm/include/llvm/Analysis/IVDescriptors.h =================================================================== --- llvm/include/llvm/Analysis/IVDescriptors.h +++ llvm/include/llvm/Analysis/IVDescriptors.h @@ -315,12 +315,16 @@ /// not have the "fast-math" property. Such operation requires a relaxed FP /// mode. bool hasUnsafeAlgebra() { - return InductionBinOp && !cast(InductionBinOp)->isFast(); + return IK == IK_FpInduction && InductionBinOp && + !cast(InductionBinOp)->isFast(); } /// Returns induction operator that does not have "fast-math" property /// and requires FP unsafe mode. Instruction *getUnsafeAlgebraInst() { + if (IK != IK_FpInduction) + return nullptr; + if (!InductionBinOp || cast(InductionBinOp)->isFast()) return nullptr; return InductionBinOp; Index: llvm/include/llvm/Analysis/LoopInfo.h =================================================================== --- llvm/include/llvm/Analysis/LoopInfo.h +++ llvm/include/llvm/Analysis/LoopInfo.h @@ -54,8 +54,10 @@ class DominatorTree; class LoopInfo; class Loop; +class InductionDescriptor; class MDNode; class PHINode; +class ScalarEvolution; class raw_ostream; template class DominatorTreeBase; template class LoopInfoBase; @@ -407,6 +409,21 @@ /// Verify loop structure of this loop and all nested loops. void verifyLoopNest(DenseSet *Loops) const; + /// Returns the guard branch of the loop if found. + /// + /// Derived classes can override this method using static template + /// polymorphism. + BranchInst *getGuard(ScalarEvolution &SE) const { return nullptr; } + + /// Returns the induction variable of the loop if found. + /// + /// Derived classes can override this method using static template + /// polymorphism. + PHINode *getInductionVariable(ScalarEvolution &SE, + bool CheckStepInvariant = false) const { + return nullptr; + } + /// Returns true if the loop is annotated parallel. /// /// Derived classes can override this method using static template @@ -526,6 +543,156 @@ bool getIncomingAndBackEdge(BasicBlock *&Incoming, BasicBlock *&Backedge) const; + /// Below are some utilities to get loop bounds, guard branch, and induction + /// variable, and check if a given phinode is an auxiliary induction variable, + /// as well as checking if the loop is canonical. Here is an example: + /// \code + /// for (int i = lb; i < ub; i+=step) + /// + /// --- pseudo LLVMIR --- + /// beforeloop: + /// guardcmp = (lb < ub) + /// if (guardcmp) goto preheader; else goto afterloop + /// preheader: + /// loop: + /// i_1 = phi[{lb, preheader}, {i_2, latch}] + /// + /// i_2 = i_1 + step + /// latch: + /// cmp = (i_2 < ub) + /// if (cmp) goto loop + /// exit: + /// afterloop: + /// \endcode + /// + /// getBounds + /// getInitialIVValue --> lb + /// getStepInst --> i_2 = i_1 + step + /// getStepValue --> step + /// getFinalIVValue --> ub + /// getCanonicalPredicate --> '<' + /// getDirection --> Increasing + /// getGuard --> if (guardcmp) goto loop; else goto afterloop + /// getInductionVariable --> i_1 + /// isAuxiliaryInductionVariable(x) --> true if x == i_1 + /// isCanonical --> false + struct LoopBounds { + /// Return the LoopBounds object if + /// - the given \p IndVar is a induction variable + /// - the initial value of the induction variable can be found + /// - the step instruction of the induction variable can be found + /// - the latch compare instruction has the induction variable or the step + /// instruction as the first operand + /// Else None. + static Optional getBounds(const Loop &L, PHINode &IndVar, + ScalarEvolution &SE); + + /// Get the initial value of the loop induction variable. + Value &getInitialIVValue() const { return InitialIVValue; } + + /// Get the instruction that updates the loop induction variable. + Instruction &getStepInst() const { return StepInst; } + + /// Get the step that the loop induction variable gets updated by in each + /// loop iteration. + Value *getStepValue() const { return StepValue; } + + /// Get the final value of the loop induction variable. + Value &getFinalIVValue() const { return *LatchCmpInst.getOperand(1); } + + /// Return the predicate for the latch comparison when + /// - the first successor of the latch branch is the loop header + /// - the operand(0) of the latch comparison is StepInst + /// Example: + /// \code + /// loop.header: + /// %iv = phi [%initialiv, %loop.preheader], [%inc, %loop.header] + /// %inc = add %iv, %step + /// %cmp = slt %iv, %finaliv + /// br %cmp, %loop.exit, %loop.header + /// loop.exit: + /// \endcode + /// 1. The second successor of the latch branch is the loop header instead + /// of the first successor (slt -> sge) + /// 2. The operand(0) of the latch comparison (%cmp) is the IndVar (%iv) + /// instead of the StepInst (%inc) (sge -> sgt) + /// getCanonicalPredicate() --> sgt + ICmpInst::Predicate getCanonicalPredicate() const; + + /// An enum for the direction of the loop + /// for (int i = 0; i < ub; ++i) --> Increasing + /// for (int i = ub; i > 0; --i) --> Descresing + /// for (int i = x; i != y; i+=z) --> Unknown + enum class Direction { Increasing, Decreasing, Unknown }; + + /// Get the direction of the loop. + Direction getDirection() const; + + private: + LoopBounds(const Loop &Loop, Value &I, Instruction &SI, Value *SV, + ICmpInst &C, ScalarEvolution &SE) + : L(Loop), InitialIVValue(I), StepInst(SI), StepValue(SV), + LatchCmpInst(C), SE(SE) {} + + const Loop &L; + + // The initial value of the loop induction variable + Value &InitialIVValue; + + // The instruction that updates the induction variable + Instruction &StepInst; + + // The value that the loop induction variable gets updated by in each loop + // iteration + Value *StepValue; + + // The latch condition instruction + ICmpInst &LatchCmpInst; + + ScalarEvolution &SE; + }; + + /// Return the struct LoopBounds collected if all struct members are found, + /// else "None". + Optional getBounds(ScalarEvolution &SE) const; + + /// Return guard branch if exists, else return nullptr. + /// A branch instruction is considered as a guard if + /// - it is the closest conditional branch before the loop + /// - one successor dominates the loop preheader + /// - a loop exit block dominates the other successor + /// - the condition is to verify the loop initial induction variable value + /// satisfy the latch condition (i.e. the loop body should be executed at + /// least once) + BranchInst *getGuard(ScalarEvolution &SE) const; + + /// Return the loop induction variable if found, else return nullptr. + /// An instruction is considered as induction variable if + /// - it is a phi node in the loop header + /// - it is used in the LHS of the conditional branch in the loop latch + /// If CheckStepInvariant, only return the induction variable if Step is loop + /// invariant. + PHINode *getInductionVariable(ScalarEvolution &SE, + bool CheckStepInvariant = false) const; + + /// Get the loop induction descriptor for the loop induction variable. Return + /// true if the loop induction variable is found. + bool getInductionDescriptor(ScalarEvolution &SE, + InductionDescriptor &IndDesc) const; + + /// Return true if the given PHINode \p AuxIndVar is + /// - in the loop header + /// - not used outside of the loop + /// - incremented by a loop invariant step for each loop iteration + /// - step instruction opcode should be add or sub + /// Note: auxiliary induction variable is not required to be used in the + /// conditional branch in the loop latch. + bool isAuxiliaryInductionVariable(PHINode &AuxIndVar) const; + + /// Return true if the induction variable starts at 0 and increments by one + /// each time through the loop. + bool isCanonical(ScalarEvolution &SE) const; + /// Return true if the Loop is in LCSSA form. bool isLCSSAForm(DominatorTree &DT) const; Index: llvm/lib/Analysis/IVDescriptors.cpp =================================================================== --- llvm/lib/Analysis/IVDescriptors.cpp +++ llvm/lib/Analysis/IVDescriptors.cpp @@ -1053,6 +1053,8 @@ Value *StartValue = Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader()); + BinaryOperator *BOp = dyn_cast_or_null( + Phi->getIncomingValueForBlock(AR->getLoop()->getLoopLatch())); const SCEV *Step = AR->getStepRecurrence(*SE); // Calculate the pointer stride and check if it is consecutive. // The stride may be a constant or a loop invariant integer value. @@ -1061,7 +1063,7 @@ return false; if (PhiTy->isIntegerTy()) { - D = InductionDescriptor(StartValue, IK_IntInduction, Step, /*BOp=*/nullptr, + D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp, CastsToIgnore); return true; } @@ -1088,6 +1090,6 @@ return false; auto *StepValue = SE->getConstant(CV->getType(), CVSize / Size, true /* signed */); - D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue); + D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue, BOp); return true; } Index: llvm/lib/Analysis/LoopInfo.cpp =================================================================== --- llvm/lib/Analysis/LoopInfo.cpp +++ llvm/lib/Analysis/LoopInfo.cpp @@ -17,8 +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/InstructionSimplify.h" #include "llvm/Analysis/LoopInfoImpl.h" #include "llvm/Analysis/LoopIterator.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/Config/llvm-config.h" #include "llvm/IR/CFG.h" @@ -158,6 +162,429 @@ return nullptr; } +/// Return true if V1 and V2 have the same value ignoring bit width. +static bool isEqualIgnoreBitwidth(Value &V1, Value &V2, ScalarEvolution &SE) { + const SCEV *S1 = SE.getSCEV(&V1); + const SCEV *S2 = SE.getSCEV(&V2); + Type *WiderType = SE.getWiderType(S1->getType(), S2->getType()); + S1 = SE.getNoopOrAnyExtend(S1, WiderType); + S2 = SE.getNoopOrAnyExtend(S2, WiderType); + return SE.getMinusSCEV(S1, S2)->isZero(); +} + +/// Return true if V1 == V2 + 1 ignoring bit width. +static bool diffOneIgnoreBitwidth(Value &V1, Value &V2, ScalarEvolution &SE) { + const SCEV *S1 = SE.getSCEV(&V1); + const SCEV *S2 = SE.getSCEV(&V2); + Type *WiderType = SE.getWiderType(S1->getType(), S2->getType()); + S1 = SE.getNoopOrAnyExtend(S1, WiderType); + S2 = SE.getNoopOrAnyExtend(S2, WiderType); + return SE.getMinusSCEV(S1, S2)->isOne(); +} + +/// Get the latch condition instruction +static ICmpInst *getLatchCmpInst(const Loop &L) { + BasicBlock *Latch = L.getLoopLatch(); + if (!Latch) + return nullptr; + + BranchInst *BI = dyn_cast(Latch->getTerminator()); + if (!BI || !BI->isConditional()) + return nullptr; + + ICmpInst *CI = dyn_cast(BI->getCondition()); + if (!CI) + return nullptr; + + return nullptr; +} + +/// Return the latch compare instruction if it is normalized. A latch compare +/// instruction is consider as normalized if the first operand is either the +/// loop induction variable \p IndVar, or the loop step instruction \p StepInst. +static ICmpInst *getNormalizedLatchCmpInst(const Loop &L, const PHINode &IndVar, + const Instruction &StepInst) { + ICmpInst *LatchCmpInst = getLatchCmpInst(L); + if (!LatchCmpInst) + return nullptr; + + Value *Op0 = LatchCmpInst->getOperand(0); + if (!Op0) + return nullptr; + + if (Op0 == &IndVar) + return LatchCmpInst; + + if (Op0 == &StepInst) + return LatchCmpInst; + + 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; + + ICmpInst *LatchCmpInst = getNormalizedLatchCmpInst(L, IndVar, *StepInst); + if (!LatchCmpInst) + return None; + + return LoopBounds(L, *InitialIVValue, *StepInst, StepValue, *LatchCmpInst, + 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(Latch->getTerminator()); + assert(BI && BI->isConditional() && "Expecting conditional latch branch"); + + // 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(); + + // Need to flip strictness of the predicate when the LHS is not the + // StepInst + if (LatchCmpInst.getOperand(0) != &getStepInst()) { + // 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; + } + + return Pred; +} + +Direction Loop::LoopBounds::getDirection() const { + const SCEVAddRecExpr *StepAddRecExpr = + dyn_cast(SE.getSCEV(&getStepInst())); + + if (!StepAddRecExpr) + return Direction::Unknown; + + 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 { + PHINode *IndVar = getInductionVariable(SE); + if (!IndVar) + return None; + + return LoopBounds::getBounds(*this, *IndVar, SE); +} + +/// Return the closest conditional branch before loop L, if +/// one successor dominates the loop preheader, +/// and a loop exit block dominates the other successor. +/// Example: +/// \code +/// beforeloop: +/// guardcmp = (lb < ub) +/// if (guardcmp) goto preheader; else goto afterloop +/// preheader: +/// loop: +/// i_1 = phi[{lb, preheader}, {i_2, latch}] +/// +/// i_2 = i_1 + step +/// latch: +/// cmp = (i_2 < ub) +/// if (cmp) goto loop +/// exit: +/// afterloop: +/// \endcode +/// +/// getPotentialGuard --> if (guardcmp) goto preheader; else goto afterloop +/// GuardBB --> beforeloop, Succ --> preheader +/// SkipIndex --> 1, SkipToBlock --> afterloop +/// - beforeloop has two successor, preheader and afterloop +/// - preheader dominates preheader +/// - exit dominates afterloop +static BranchInst *getPotentialGuard(const Loop &L, + ICmpInst::Predicate &GuardPred) { + // Initialize GuardBB with the loop preheader and GuardBI with the branch in + // the loop preheader. + BasicBlock *GuardBB = L.getLoopPreheader(); + if (!GuardBB) + return nullptr; + + // Search backward from preheader to find a basic block which has conditional + // branch. Notice that loop preheader branch is definitely not conditional. + + // The successor of GuardBB which 'flows' into the loop preheader + BasicBlock *Succ = nullptr; + BranchInst *GuardBI = nullptr; + SmallPtrSet Visited; + do { + Succ = GuardBB; + GuardBB = GuardBB->getUniquePredecessor(); + if (!GuardBB) + return nullptr; + + // A Visited set is needed to records blocks already visited, to avoid + // infinite loop when GuardBB single successor loops back to itself. + if (!Visited.insert(GuardBB).second) + return nullptr; + + GuardBI = dyn_cast(GuardBB->getTerminator()); + } while (GuardBI && !GuardBI->isConditional()); + + if (!GuardBI || !GuardBI->isConditional()) + return nullptr; + + assert(GuardBI->getNumSuccessors() == 2 && + "Expecting potential guard branch instruction to have 2 successors"); + + // Now we have the first conditional branch before loop L, we need to check if + // the other successor 'flows' from a loop exit block, i.e. skipping the loop. + // Get the successor index of GuardBI which may skip the loop L, i.e. the + // index of the successor which is not Succ. + unsigned SkipIndex = (GuardBI->getSuccessor(0) == Succ) ? 1 : 0; + assert((SkipIndex == 1 || GuardBI->getSuccessor(1) == Succ) && + "Expecting one of GuardBI successor to be Succ"); + ICmpInst *Cond = dyn_cast(GuardBI->getCondition()); + if (!Cond) + return nullptr; + + GuardPred = + (SkipIndex == 1) ? Cond->getPredicate() : Cond->getInversePredicate(); + BasicBlock *SkipToBlock = GuardBI->getSuccessor(SkipIndex); + + SmallVector ExitBlocks; + L.getUniqueExitBlocks(ExitBlocks); + for (BasicBlock *ExitBlock : ExitBlocks) { + // A Visited set is needed to records blocks already visited, to avoid + // infinite loop when ExitBlock unique successor loops back to itself. + SmallPtrSet Visited; + while (ExitBlock && ExitBlock != SkipToBlock && + Visited.insert(ExitBlock).second) { + ExitBlock = ExitBlock->getUniqueSuccessor(); + } + if (ExitBlock == SkipToBlock) + return GuardBI; + } + + return nullptr; +} + +BranchInst *Loop::getGuard(ScalarEvolution &SE) const { + if (!isLoopSimplifyForm()) + return nullptr; + + ICmpInst::Predicate GuardPred; + BranchInst *Guard = getPotentialGuard(*this, GuardPred); + if (!Guard) + return nullptr; + + ICmpInst *Cond = dyn_cast(Guard->getCondition()); + if (!Cond) + return nullptr; + + const Optional Bound = getBounds(SE); + if (!Bound) + return nullptr; + + Value &LatchInitialValue = Bound->getInitialIVValue(); + Value &LatchFinalValue = Bound->getFinalIVValue(); + ICmpInst::Predicate LatchPred = Bound->getCanonicalPredicate(); + if (LatchPred == ICmpInst::BAD_ICMP_PREDICATE) + return nullptr; + + LatchPred = ICmpInst::getSignedPredicate(LatchPred); + + Value *GuardInitialValue = Cond->getOperand(0); + Value *GuardFinalValue = Cond->getOperand(1); + if (isEqualIgnoreBitwidth(*Cond->getOperand(1), LatchInitialValue, SE)) { + GuardPred = ICmpInst::getSwappedPredicate(GuardPred); + GuardInitialValue = Cond->getOperand(1); + GuardFinalValue = Cond->getOperand(0); + } + GuardPred = ICmpInst::getSignedPredicate(GuardPred); + + if (LatchPred != GuardPred && LatchPred == ICmpInst::ICMP_NE) { + if (Bound->getDirection() == LoopBounds::Direction::Increasing) + LatchPred = ICmpInst::ICMP_SLT; + else if (Bound->getDirection() == LoopBounds::Direction::Decreasing) + LatchPred = ICmpInst::ICMP_SGT; + } + + if (!isEqualIgnoreBitwidth(*GuardInitialValue, LatchInitialValue, SE)) + return nullptr; + + if (isEqualIgnoreBitwidth(*GuardFinalValue, LatchFinalValue, SE) && + GuardPred == LatchPred) + return Guard; + + // Instruction combine transforms '<=' and '>=' to '<' and '>' respectively, + // which may cause the GuardPred and LatchPred to be different. + // 'lb < ub + 1' iff 'lb <= ub' and 'ub > lb' iff 'ub >= lb + 1'. + if ((GuardPred == ICmpInst::ICMP_SLE && LatchPred == ICmpInst::ICMP_SLT && + diffOneIgnoreBitwidth(*GuardFinalValue, LatchFinalValue, SE)) || + (GuardPred == ICmpInst::ICMP_SGE && LatchPred == ICmpInst::ICMP_SGT && + diffOneIgnoreBitwidth(LatchFinalValue, *GuardFinalValue, SE))) + return Guard; + + return nullptr; +} + +PHINode *Loop::getInductionVariable(ScalarEvolution &SE, + bool CheckStepInvariant) const { + if (!isLoopSimplifyForm()) + return nullptr; + + BasicBlock *Header = getHeader(); + BasicBlock *Latch = getLoopLatch(); + ICmpInst *CmpInst = getLatchCmpInst(*this); + if (!CmpInst) + return nullptr; + + // the loop induction variable should not be loop invariant + if (isLoopInvariant(CmpInst->getOperand(0))) + return nullptr; + + // case 1: + // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}] + // StepInst = IndVar + step + // cmp = StepInst < FinalValue + Instruction *StepInst = dyn_cast(CmpInst->getOperand(0)); + assert(StepInst && + "Expecting the first operand of CmpInst is an instruction"); + + // Loop over all of the PHI nodes in loop header, store the PHI node that has + // incoming value from latch equals to the StepInst + PHINode *IndVar = nullptr; + for (PHINode &PN : Header->phis()) { + Value *IncomingValue = PN.getIncomingValueForBlock(Latch); + assert(IncomingValue && "Expecting valid incoming value from latch"); + if (StepInst == IncomingValue) { + IndVar = &PN; + break; + } + } + if (IndVar && isEqualIgnoreBitwidth(*StepInst->getOperand(0), *IndVar, SE)) + if (!CheckStepInvariant || isLoopInvariant(StepInst->getOperand(1))) + return IndVar; + + // case 2: + // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}] + // StepInst = IndVar + step + // cmp = IndVar < FinalValue + IndVar = dyn_cast(CmpInst->getOperand(0)); + if (!IndVar) + return nullptr; + + if (IndVar->getParent() != Header) + return nullptr; + + Value *IncomingValue = IndVar->getIncomingValueForBlock(Latch); + assert(IncomingValue && "Expecting valid incoming value from latch"); + StepInst = dyn_cast(IncomingValue); + if (StepInst && StepInst->getOperand(0) == IndVar) + if (!CheckStepInvariant || isLoopInvariant(StepInst->getOperand(1))) + return IndVar; + + return nullptr; +} + +bool Loop::getInductionDescriptor(ScalarEvolution &SE, + InductionDescriptor &IndDesc) const { + PHINode *IndVar = getInductionVariable(SE); + if (!IndVar) + return false; + + return InductionDescriptor::isInductionPHI(IndVar, this, &SE, IndDesc); +} + +bool Loop::isAuxiliaryInductionVariable(PHINode &AuxIndVar) 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; + + // incremented by a loop invariant step for each loop iteration + // and the step instruction opcode should be add or sub. + BasicBlock *Latch = getLoopLatch(); + if (!Latch) + return false; + + Instruction *StepInst = + dyn_cast(AuxIndVar.getIncomingValueForBlock(Latch)); + if (!StepInst || StepInst->getNumOperands() != 2 || + (StepInst->getOpcode() != Instruction::Add && + StepInst->getOpcode() != Instruction::Sub)) + return false; + + if (StepInst->getOperand(0) == &AuxIndVar) + if (isLoopInvariant(StepInst->getOperand(1))) + return true; + + if (StepInst->getOperand(1) == &AuxIndVar) + if (isLoopInvariant(StepInst->getOperand(0))) + return true; + + return false; +} + +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) { Index: llvm/lib/Transforms/Scalar/LoopInterchange.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -292,33 +292,6 @@ return LoopList; } -static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) { - PHINode *InnerIndexVar = L->getCanonicalInductionVariable(); - if (InnerIndexVar) - return InnerIndexVar; - if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr) - return nullptr; - for (BasicBlock::iterator I = L->getHeader()->begin(); isa(I); ++I) { - PHINode *PhiVar = cast(I); - Type *PhiTy = PhiVar->getType(); - if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() && - !PhiTy->isPointerTy()) - return nullptr; - const SCEVAddRecExpr *AddRec = - dyn_cast(SE->getSCEV(PhiVar)); - if (!AddRec || !AddRec->isAffine()) - continue; - const SCEV *Step = AddRec->getStepRecurrence(*SE); - if (!isa(Step)) - continue; - // Found the induction variable. - // FIXME: Handle loops with more than one induction variable. Note that, - // currently, legality makes sure we have only one induction variable. - return PhiVar; - } - return nullptr; -} - namespace { /// LoopInterchangeLegality checks if it is legal to interchange the loop. @@ -1227,7 +1200,7 @@ if (InnerLoop->getSubLoops().empty()) { BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); LLVM_DEBUG(dbgs() << "Calling Split Inner Loop\n"); - PHINode *InductionPHI = getInductionVariable(InnerLoop, SE); + PHINode *InductionPHI = InnerLoop->getInductionVariable(*SE); if (!InductionPHI) { LLVM_DEBUG(dbgs() << "Failed to find the point to split loop latch \n"); return false; Index: llvm/unittests/Analysis/LoopInfoTest.cpp =================================================================== --- llvm/unittests/Analysis/LoopInfoTest.cpp +++ llvm/unittests/Analysis/LoopInfoTest.cpp @@ -7,6 +7,9 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/AsmParser/Parser.h" #include "llvm/IR/Dominators.h" #include "llvm/Support/SourceMgr.h" @@ -26,6 +29,23 @@ Test(*F, LI); } +/// Build the loop info and scalar evolution for the function and run the Test. +static void runWithLoopInfoAndSE( + Module &M, StringRef FuncName, + function_ref Test) { + auto *F = M.getFunction(FuncName); + ASSERT_NE(F, nullptr) << "Could not find " << FuncName; + + TargetLibraryInfoImpl TLII; + TargetLibraryInfo TLI(TLII); + AssumptionCache AC(*F); + DominatorTree DT(*F); + LoopInfo LI(DT); + ScalarEvolution SE(*F, TLI, AC, DT, LI); + + Test(*F, LI, SE); +} + static std::unique_ptr makeLLVMModule(LLVMContext &Context, const char *ModuleStr) { SMDiagnostic Err; @@ -210,3 +230,478 @@ EXPECT_EQ(&L_0_1, ReverseSiblingPreorder[6]); EXPECT_EQ(&L_0_0, ReverseSiblingPreorder[7]); } + +TEST(LoopInfoTest, CanonicalLoop) { + const char *ModuleStr = + "define void @foo(i32* %A, i32 %ub) {\n" + "entry:\n" + " %guardcmp = icmp slt i32 0, %ub\n" + " br i1 %guardcmp, label %for.preheader, label %for.end\n" + "for.preheader:\n" + " br label %for.body\n" + "for.body:\n" + " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" + " %idxprom = sext i32 %i to i64\n" + " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" + " store i32 %i, i32* %arrayidx, align 4\n" + " %inc = add nsw i32 %i, 1\n" + " %cmp = icmp slt i32 %inc, %ub\n" + " br i1 %cmp, label %for.body, label %for.exit\n" + "for.exit:\n" + " br label %for.end\n" + "for.end:\n" + " ret void\n" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + + runWithLoopInfoAndSE( + *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + 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); + + EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry"); + EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + }); +} + +TEST(LoopInfoTest, LoopWithInverseGuardSuccs) { + const char *ModuleStr = + "define void @foo(i32* %A, i32 %ub) {\n" + "entry:\n" + " %guardcmp = icmp sge i32 0, %ub\n" + " br i1 %guardcmp, label %for.end, label %for.preheader\n" + "for.preheader:\n" + " br label %for.body\n" + "for.body:\n" + " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" + " %idxprom = sext i32 %i to i64\n" + " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" + " store i32 %i, i32* %arrayidx, align 4\n" + " %inc = add nsw i32 %i, 1\n" + " %cmp = icmp slt i32 %inc, %ub\n" + " br i1 %cmp, label %for.body, label %for.exit\n" + "for.exit:\n" + " br label %for.end\n" + "for.end:\n" + " ret void\n" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + + runWithLoopInfoAndSE( + *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + 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); + + EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry"); + EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + }); +} + +TEST(LoopInfoTest, LoopWithSwappedGuardCmp) { + const char *ModuleStr = + "define void @foo(i32* %A, i32 %ub) {\n" + "entry:\n" + " %guardcmp = icmp sgt i32 %ub, 0\n" + " br i1 %guardcmp, label %for.preheader, label %for.end\n" + "for.preheader:\n" + " br label %for.body\n" + "for.body:\n" + " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" + " %idxprom = sext i32 %i to i64\n" + " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" + " store i32 %i, i32* %arrayidx, align 4\n" + " %inc = add nsw i32 %i, 1\n" + " %cmp = icmp sge i32 %inc, %ub\n" + " br i1 %cmp, label %for.exit, label %for.body\n" + "for.exit:\n" + " br label %for.end\n" + "for.end:\n" + " ret void\n" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + + runWithLoopInfoAndSE( + *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + 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); + + EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry"); + EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + }); +} + +TEST(LoopInfoTest, LoopWithInverseLatchSuccs) { + const char *ModuleStr = + "define void @foo(i32* %A, i32 %ub) {\n" + "entry:\n" + " %guardcmp = icmp slt i32 0, %ub\n" + " br i1 %guardcmp, label %for.preheader, label %for.end\n" + "for.preheader:\n" + " br label %for.body\n" + "for.body:\n" + " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" + " %idxprom = sext i32 %i to i64\n" + " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" + " store i32 %i, i32* %arrayidx, align 4\n" + " %inc = add nsw i32 %i, 1\n" + " %cmp = icmp sge i32 %inc, %ub\n" + " br i1 %cmp, label %for.exit, label %for.body\n" + "for.exit:\n" + " br label %for.end\n" + "for.end:\n" + " ret void\n" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + + runWithLoopInfoAndSE( + *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + 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); + + EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry"); + EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + }); +} + +TEST(LoopInfoTest, LoopWithLatchCmpNE) { + const char *ModuleStr = + "define void @foo(i32* %A, i32 %ub) {\n" + "entry:\n" + " %guardcmp = icmp slt i32 0, %ub\n" + " br i1 %guardcmp, label %for.preheader, label %for.end\n" + "for.preheader:\n" + " br label %for.body\n" + "for.body:\n" + " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" + " %idxprom = sext i32 %i to i64\n" + " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" + " store i32 %i, i32* %arrayidx, align 4\n" + " %inc = add nsw i32 %i, 1\n" + " %cmp = icmp ne i32 %i, %ub\n" + " br i1 %cmp, label %for.body, label %for.exit\n" + "for.exit:\n" + " br label %for.end\n" + "for.end:\n" + " ret void\n" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + + runWithLoopInfoAndSE( + *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + 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); + + EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry"); + EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + }); +} + +TEST(LoopInfoTest, LoopNonConstantStep) { + const char *ModuleStr = + "define void @foo(i32* %A, i32 %ub, i32 %step) {\n" + "entry:\n" + " %guardcmp = icmp slt i32 0, %ub\n" + " br i1 %guardcmp, label %for.preheader, label %for.end\n" + "for.preheader:\n" + " br label %for.body\n" + "for.body:\n" + " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" + " %idxprom = zext i32 %i to i64\n" + " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" + " store i32 %i, i32* %arrayidx, align 4\n" + " %inc = add nsw i32 %i, %step\n" + " %cmp = icmp slt i32 %inc, %ub\n" + " br i1 %cmp, label %for.body, label %for.exit\n" + "for.exit:\n" + " br label %for.end\n" + "for.end:\n" + " ret void\n" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + + runWithLoopInfoAndSE( + *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + 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); + + EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry"); + EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + }); +} + +TEST(LoopInfoTest, LoopUnsignedBounds) { + const char *ModuleStr = + "define void @foo(i32* %A, i32 %ub) {\n" + "entry:\n" + " %guardcmp = icmp ult i32 0, %ub\n" + " br i1 %guardcmp, label %for.preheader, label %for.end\n" + "for.preheader:\n" + " br label %for.body\n" + "for.body:\n" + " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" + " %idxprom = zext i32 %i to i64\n" + " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" + " store i32 %i, i32* %arrayidx, align 4\n" + " %inc = add i32 %i, 1\n" + " %cmp = icmp ult i32 %inc, %ub\n" + " br i1 %cmp, label %for.body, label %for.exit\n" + "for.exit:\n" + " br label %for.end\n" + "for.end:\n" + " ret void\n" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + + runWithLoopInfoAndSE( + *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + 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); + + EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry"); + EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + }); +} + +TEST(LoopInfoTest, DecreasingLoop) { + const char *ModuleStr = + "define void @foo(i32* %A, i32 %ub) {\n" + "entry:\n" + " %guardcmp = icmp slt i32 0, %ub\n" + " br i1 %guardcmp, label %for.preheader, label %for.end\n" + "for.preheader:\n" + " br label %for.body\n" + "for.body:\n" + " %i = phi i32 [ %ub, %for.preheader ], [ %inc, %for.body ]\n" + " %idxprom = sext i32 %i to i64\n" + " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" + " store i32 %i, i32* %arrayidx, align 4\n" + " %inc = sub nsw i32 %i, 1\n" + " %cmp = icmp sgt i32 %inc, 0\n" + " br i1 %cmp, label %for.body, label %for.exit\n" + "for.exit:\n" + " br label %for.end\n" + "for.end:\n" + " ret void\n" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + + runWithLoopInfoAndSE( + *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + 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); + + EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry"); + EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + }); +} + +TEST(LoopInfoTest, CannotFindDirection) { + const char *ModuleStr = + "define void @foo(i32* %A, i32 %ub, i32 %step) {\n" + "entry:\n" + " %guardcmp = icmp slt i32 0, %ub\n" + " br i1 %guardcmp, label %for.preheader, label %for.end\n" + "for.preheader:\n" + " br label %for.body\n" + "for.body:\n" + " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" + " %idxprom = sext i32 %i to i64\n" + " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" + " store i32 %i, i32* %arrayidx, align 4\n" + " %inc = add nsw i32 %i, %step\n" + " %cmp = icmp ne i32 %i, %ub\n" + " br i1 %cmp, label %for.body, label %for.exit\n" + "for.exit:\n" + " br label %for.end\n" + "for.end:\n" + " ret void\n" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + + runWithLoopInfoAndSE(*M, "foo", + [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + 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); + + EXPECT_EQ(L->getGuard(SE), nullptr); + EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + }); +} + +TEST(LoopInfoTest, ZextIndVar) { + const char *ModuleStr = + "define void @foo(i32* %A, i32 %ub) {\n" + "entry:\n" + " %guardcmp = icmp slt i32 0, %ub\n" + " br i1 %guardcmp, label %for.preheader, label %for.end\n" + "for.preheader:\n" + " br label %for.body\n" + "for.body:\n" + " %indvars.iv = phi i64 [ 0, %for.preheader ], [ %indvars.iv.next, %for.body ]\n" + " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" + " %idxprom = sext i32 %i to i64\n" + " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" + " store i32 %i, i32* %arrayidx, align 4\n" + " %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1\n" + " %inc = add nsw i32 %i, 1\n" + " %wide.trip.count = zext i32 %ub to i64\n" + " %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count\n" + " br i1 %exitcond, label %for.body, label %for.exit\n" + "for.exit:\n" + " br label %for.end\n" + "for.end:\n" + " ret void\n" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + + runWithLoopInfoAndSE( + *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + 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); + + EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry"); + EXPECT_EQ(L->getInductionVariable(SE)->getName(), "indvars.iv"); + }); +} + +TEST(LoopInfoTest, AuxiliaryIV) { + const char *ModuleStr = + "define void @foo(i32* %A, i32 %ub) {\n" + "entry:\n" + " %guardcmp = icmp slt i32 0, %ub\n" + " br i1 %guardcmp, label %for.preheader, label %for.end\n" + "for.preheader:\n" + " br label %for.body\n" + "for.body:\n" + " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" + " %aux = phi i32 [ 0, %for.preheader ], [ %auxinc, %for.body ]\n" + " %loopvariant = phi i32 [ 0, %for.preheader ], [ %loopvariantinc, %for.body ]\n" + " %usedoutside = phi i32 [ 0, %for.preheader ], [ %usedoutsideinc, %for.body ]\n" + " %mulopcode = phi i32 [ 0, %for.preheader ], [ %mulopcodeinc, %for.body ]\n" + " %idxprom = sext i32 %i to i64\n" + " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" + " store i32 %i, i32* %arrayidx, align 4\n" + " %mulopcodeinc = mul nsw i32 %mulopcode, 5\n" + " %usedoutsideinc = add nsw i32 %usedoutside, 5\n" + " %loopvariantinc = add nsw i32 %loopvariant, %i\n" + " %auxinc = add nsw i32 %aux, 5\n" + " %inc = add nsw i32 %i, 1\n" + " %cmp = icmp slt i32 %inc, %ub\n" + " br i1 %cmp, label %for.body, label %for.exit\n" + "for.exit:\n" + " %lcssa = phi i32 [ %usedoutside, %for.body ]\n" + " br label %for.end\n" + "for.end:\n" + " ret void\n" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + + runWithLoopInfoAndSE( + *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + 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); + + EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry"); + EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); + BasicBlock::iterator II = Header->begin(); + PHINode &Instruction_i = cast(*(II)); + EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_i)); + PHINode &Instruction_aux = cast(*(++II)); + EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_aux)); + PHINode &Instruction_loopvariant = cast(*(++II)); + EXPECT_FALSE(L->isAuxiliaryInductionVariable(Instruction_loopvariant)); + PHINode &Instruction_usedoutside = cast(*(++II)); + EXPECT_FALSE(L->isAuxiliaryInductionVariable(Instruction_usedoutside)); + PHINode &Instruction_mulopcode = cast(*(++II)); + EXPECT_FALSE(L->isAuxiliaryInductionVariable(Instruction_mulopcode)); + }); +}