Index: llvm/include/llvm/Analysis/LoopInfo.h =================================================================== --- llvm/include/llvm/Analysis/LoopInfo.h +++ llvm/include/llvm/Analysis/LoopInfo.h @@ -56,6 +56,7 @@ class Loop; class MDNode; class PHINode; +class ScalarEvolution; class raw_ostream; template class DominatorTreeBase; template class LoopInfoBase; @@ -407,6 +408,14 @@ /// Verify loop structure of this loop and all nested loops. void verifyLoopNest(DenseSet *Loops) const; + /// Derived classes can override this method using static template + /// polymorphism. + BranchInst *getGuard(ScalarEvolution *SE = nullptr) const { return nullptr; } + + /// Derived classes can override this method using static template + /// polymorphism. + PHINode *getInductionVariable() const { return nullptr; } + /// Returns true if the loop is annotated parallel. /// /// Derived classes can override this method using static template @@ -526,6 +535,111 @@ bool getIncomingAndBackEdge(BasicBlock *&Incoming, BasicBlock *&Backedge) const; + /// 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 + /// getGuard --> if (guardcmp) goto loop; else goto afterloop + /// getInductionVariable --> i1 + /// getAuxiliaryInductionVariable --> {i1} + /// isCanonical --> false + struct LoopBounds { + /// LoopBounds can only be created if an induction variable can be + /// identified. + LoopBounds(const Loop &Loop, Value &I, Instruction &S, ICmpInst &C) + : L(Loop), Init(I), StepInst(S), CmpInst(C) {} + /// Get the initial value of the loop induction variable. + Value &getInitialIVValue() const { return Init; } + /// Get the instruction which update the loop induction variable. + Instruction &getStepInst() const { return StepInst; } + /// Get the step that the loop induction variable get updated for each loop + /// iteration. + Value &getStepValue() const { return *StepInst.getOperand(1); } + /// Get the final value of the loop induction variable. + Value &getFinalIVValue() const { return *CmpInst.getOperand(1); } + /// Return the predicate for the latch comparison when + /// - the first successor of the latch branch is the loop header + /// - the LHS of the latch comparison is StepInst + 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: + /// Get the direction of the loop using loop bounds. This only works for + /// constant bounds. + Direction getDirectionFromConstantBounds() const; + + const Loop &L; + // the initial value of the loop induction variable + Value &Init; + // the instruction which update the induction variable + Instruction &StepInst; + // the latch condition instruction + ICmpInst &CmpInst; + }; + + /// Return the struct LoopBounds collected if all struct members are found, + /// else return nullptr. + std::unique_ptr getBounds(ScalarEvolution *SE = nullptr) 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 loop initial value satisfy the latch + /// condition + BranchInst *getGuard(ScalarEvolution *SE = nullptr) 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 = nullptr, + bool CheckStepInvariant = false) const; + + /// Return true if the given PHINode \p AuxIndVar is + /// - in 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, + ScalarEvolution *SE = nullptr) const; + + /// Return true if the induction variable starts at 0 and increments by one + /// each time through the loop. + bool isCanonical(ScalarEvolution *SE = nullptr) const; + /// Return true if the Loop is in LCSSA form. bool isLCSSAForm(DominatorTree &DT) const; Index: llvm/lib/Analysis/LoopInfo.cpp =================================================================== --- llvm/lib/Analysis/LoopInfo.cpp +++ llvm/lib/Analysis/LoopInfo.cpp @@ -17,8 +17,10 @@ #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/ScopeExit.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopInfoImpl.h" #include "llvm/Analysis/LoopIterator.h" +#include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/Config/llvm-config.h" #include "llvm/IR/CFG.h" @@ -158,6 +160,481 @@ return nullptr; } +/// Return true if V1 and V2 have the same value +static bool isEqual(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 +static bool diffOne(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(); +} + +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()) + ? CmpInst.getPredicate() + : CmpInst.getInversePredicate(); + + // Need to flip strictness of the predicate when the LHS is not the + // StepInst + if (CmpInst.getOperand(0) != &StepInst) { + // Cannot flip strictness of NE and EQ + if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ) + return ICmpInst::getFlippedStrictnessPredicate(Pred); + Direction D = getDirectionFromConstantBounds(); + 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::getDirectionFromConstantBounds() const { + // Strip all ZExtInst or SExtInst from V + auto stripExt = [](Value *V) { + while (V && (isa(V) || isa(V))) + V = cast(V)->getOperand(0); + return V; + }; + + Instruction &StepInst = getStepInst(); + ConstantInt *Step = dyn_cast(stripExt(&getStepValue())); + if (Step) { + if (Step->isNegative()) { + // i += negative --> i -= positive --> Decreasing + if (StepInst.getOpcode() == Instruction::Add) + return Direction::Decreasing; + // i -= negative --> i += positive --> Increasing + if (StepInst.getOpcode() == Instruction::Sub) + return Direction::Increasing; + } else { + // i += positive --> Increasing + if (StepInst.getOpcode() == Instruction::Add) + return Direction::Increasing; + // i -= positive --> Decreasing + if (StepInst.getOpcode() == Instruction::Sub) + return Direction::Decreasing; + } + } + + ConstantInt *Initial = dyn_cast(stripExt(&getInitialIVValue())); + ConstantInt *Final = dyn_cast(stripExt(&getFinalIVValue())); + if (Initial && Final) { + // initial_value <= final_value --> Increasing + if (Initial->getSExtValue() <= Final->getSExtValue()) + return Direction::Increasing; + // initial_value > final_value --> Decreasing + else + return Direction::Decreasing; + } + + if (Step && Initial) { + if (StepInst.getOpcode() == Instruction::Mul) { + // positive_integer *= positive_integer --> Increasing + if (!Step->isNegative() && !Initial->isNegative()) + return Direction::Increasing; + // negative_integer *= positive_integer --> Decreasing + if (!Step->isNegative() && Initial->isNegative()) + return Direction::Decreasing; + // positive_integer *= negative_integer + // --> alternate positive and negative + // negative_integer *= negative_integer + // --> alternate positive and negative + } else if (StepInst.getOpcode() == Instruction::SDiv) { + // positive_integer /= positive_integer --> Decreasing + if (!Step->isNegative() && !Initial->isNegative()) + return Direction::Decreasing; + // negative_integer /= positive_integer --> Increasing + if (!Step->isNegative() && Initial->isNegative()) + return Direction::Increasing; + // positive_integer /= negative_integer + // --> alternate positive and negative + // negative_integer /= negative_integer + // --> alternate positive and negative + } else if (StepInst.getOpcode() == Instruction::UDiv) { + // positive_integer /= positive_integer --> Decreasing + return Direction::Decreasing; + } + } + + return Direction::Unknown; +} + +Direction Loop::LoopBounds::getDirection() const { + // Use getUnsignedPredicate to eliminate the number of cases needed. + switch (ICmpInst::getUnsignedPredicate(getCanonicalPredicate())) { + // i > FinalValue --> Decreasing + case ICmpInst::ICMP_UGT: + case ICmpInst::ICMP_UGE: + return Direction::Decreasing; + // i < FinalValue --> Increasing + case ICmpInst::ICMP_ULT: + case ICmpInst::ICMP_ULE: + return Direction::Increasing; + case ICmpInst::ICMP_EQ: + case ICmpInst::ICMP_NE: + break; + default: + assert(false && "Unexpected predicate"); + } + + // Try to find the direction using loop bounds. This only works for + // constant bounds. + return getDirectionFromConstantBounds(); +} + +/// Get loop initial value +static Value *getInit(const Loop &L, const PHINode &IndVar) { + BasicBlock *Preheader = L.getLoopPreheader(); + assert(Preheader && "Expecting valid preheader"); + + return IndVar.getIncomingValueForBlock(Preheader); +} + +/// Get the instruction which update the induction variable +static Instruction *getStepInst(const Loop &L, const PHINode &IndVar, + ScalarEvolution *SE = nullptr) { + BasicBlock *Latch = L.getLoopLatch(); + assert(Latch && "Expecting valid latch"); + + Instruction *StepInst = + dyn_cast(IndVar.getIncomingValueForBlock(Latch)); + if (!StepInst) + return nullptr; + + assert( + SE && + isEqual(*StepInst->getOperand(0), const_cast(IndVar), *SE) && + "Expecting the first operand of the step instruction to be the induction " + "variable"); + + return StepInst; +} + +/// Get the latch condition instruction +static ICmpInst *getCmpInst(const Loop &L) { + BasicBlock *Latch = L.getLoopLatch(); + assert(Latch && "Expecting valid latch"); + + BranchInst *BI = dyn_cast(Latch->getTerminator()); + if (!BI || !BI->isConditional()) + return nullptr; + + ICmpInst *CI = dyn_cast(BI->getCondition()); + if (!CI) + return nullptr; + + // First operand of CI should be the StepInst + if (isa(CI->getOperand(0))) + return CI; + + return nullptr; +} + +std::unique_ptr Loop::getBounds(ScalarEvolution *SE) const { + PHINode *IndVar = getInductionVariable(SE); + if (!IndVar) + return nullptr; + + if (Value *Init = getInit(*this, *IndVar)) + if (Instruction *StepInst = getStepInst(*this, *IndVar, SE)) + if (ICmpInst *CmpInst = getCmpInst(*this)) + return std::unique_ptr( + new LoopBounds(*this, *Init, *StepInst, *CmpInst)); + + return nullptr; +} + +/// Return the closest conditional branch before loop L, where +/// one successor dominates the loop preheader, +/// and a loop exit block dominates the other successor. +/// Example: +/// 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: +/// 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(); + BranchInst *GuardBI = dyn_cast(GuardBB->getTerminator()); + if (!GuardBB || !GuardBI) + return nullptr; + + // Search backward from preheader to find a basic block which has conditional + // branch. Notice that loop preheader branch is definitely not conditional. + BasicBlock *Succ = + nullptr; // The successor of GuardBB which 'flows' into the loop preheader + SmallPtrSet Visited; + do { + Succ = GuardBB; + GuardBB = GuardBB->getSinglePredecessor(); + if (!GuardBB) + return nullptr; + + // A Visited set is needed to records blocks already visited, to avoid + // infinite loop when ExitBlock single successor loops back to itself. + if (Visited.count(GuardBB) != 0) + return nullptr; + + Visited.insert(GuardBB); + 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 single successor loops back to itself. + SmallPtrSet Visited; + while (ExitBlock && ExitBlock != SkipToBlock && + Visited.count(ExitBlock) == 0) { + Visited.insert(ExitBlock); + ExitBlock = ExitBlock->getSingleSuccessor(); + } + 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 std::unique_ptr 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 (SE && isEqual(*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 (SE && !isEqual(*GuardInitialValue, LatchInitialValue, *SE)) + return nullptr; + + if (SE && isEqual(*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' iff 'lb <= ub + 1' and 'ub > lb' iff 'ub >= lb - 1'. + if ((GuardPred == ICmpInst::ICMP_SLE && LatchPred == ICmpInst::ICMP_SLT && + SE && diffOne(LatchFinalValue, *GuardFinalValue, *SE)) || + (GuardPred == ICmpInst::ICMP_SGE && LatchPred == ICmpInst::ICMP_SGT && + SE && diffOne(*GuardFinalValue, LatchFinalValue, *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 = getCmpInst(*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 (BasicBlock::iterator I = Header->begin(); isa(I); ++I) { + PHINode *PN = cast(I); + Value *IncomingValue = PN->getIncomingValueForBlock(Latch); + assert(IncomingValue && "Expecting valid incoming value from latch"); + if (StepInst == IncomingValue) { + IndVar = PN; + break; + } + } + if (IndVar && SE && isEqual(*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::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 (auto U : AuxIndVar.users()) + if (auto I = dyn_cast(U)) + if (!contains(I)) + return false; + + // incremented by a loop invariant step fpr 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 { + const std::unique_ptr Bound = getBounds(SE); + if (!Bound) + return false; + + ConstantInt *Init = dyn_cast(&Bound->getInitialIVValue()); + if (!Init || !Init->isZero()) + return false; + + if (Bound->getStepInst().getOpcode() != Instruction::Add) + return false; + + ConstantInt *Step = dyn_cast(&Bound->getStepValue()); + 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,477 @@ 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)); + }); +}