Index: include/llvm/Analysis/ScalarEvolution.h =================================================================== --- include/llvm/Analysis/ScalarEvolution.h +++ include/llvm/Analysis/ScalarEvolution.h @@ -754,6 +754,9 @@ /// getMaxBackedgeTakenCount or zero. bool isBackedgeTakenCountMaxOrZero(const Loop *L); + /// Evaluate compare to a constant node for special patterns. + const SCEV *evaluateCompare(ICmpInst *IC); + /// Return true if the specified loop has an analyzable loop-invariant /// backedge-taken count. bool hasLoopInvariantBackedgeTakenCount(const Loop *L); @@ -1378,6 +1381,7 @@ /// Helper function called from createNodeForPHI. const SCEV *createAddRecFromPHI(PHINode *PN); + /// A helper function for createAddRecFromPHI to handle simple cases. const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV, Value *StartValueV); Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -4080,6 +4080,55 @@ bool Valid = true; }; +class SCEVCmpEvaluator : public SCEVRewriteVisitor { +public: + SCEVCmpEvaluator(const Loop *L, ScalarEvolution &SE) + : SCEVRewriteVisitor(SE), L(L) {} + + static const SCEV *rewrite(const SCEV *S, const Loop *L, + ScalarEvolution &SE) { + SCEVCmpEvaluator Rewriter(L, SE); + const SCEV *Result = Rewriter.visit(S); + return Rewriter.isModified() ? Result : SE.getCouldNotCompute(); + } + + const SCEV *visitUnknown(const SCEVUnknown *Expr) { + const SCEV * Result = Expr; + bool InvariantF = SE.isLoopInvariant(Expr, L); + + if (!InvariantF && Expr->getValue() && isa(Expr->getValue())) { + Instruction *I = dyn_cast(Expr->getValue()); + switch (I->getOpcode()) { + case Instruction::Select: { + const SCEV *ICmpSE = + SE.evaluateCompare(cast(I->getOperand(0))); + if (ICmpSE->getSCEVType() == scConstant) { + bool IsOne = dyn_cast(ICmpSE)->getValue()->isOne(); + Value *TrueVal = I->getOperand(1); + Value *FalseVal = I->getOperand(2); + Result = SE.getSCEV(IsOne ? TrueVal : FalseVal); + } + } break; + case Instruction::ICmp: { + const SCEV *ICmpSE = SE.evaluateCompare(cast(I)); + if (dyn_cast(ICmpSE)) + Result = ICmpSE; + } break; + default: + break; + } + } + Modified |= Result != Expr ? true : false; + return Result; + } + + bool isModified() { return Modified; } + +private: + const Loop *L; + bool Modified = false; +}; + class SCEVShiftRewriter : public SCEVRewriteVisitor { public: SCEVShiftRewriter(const Loop *L, ScalarEvolution &SE) @@ -4738,6 +4787,18 @@ // If the value coming around the backedge is an add with the symbolic // value we just inserted, then we found a simple induction variable! if (const SCEVAddExpr *Add = dyn_cast(BEValue)) { + + // Recompute BEValue as it may have conditional operations + // in evolution chain. + const SCEV *Accum = nullptr; + const SCEV *ModifiAdd = SCEVCmpEvaluator::rewrite(Add, L, *this); + if (ModifiAdd != getCouldNotCompute()) { + if (isa(ModifiAdd)) + Add = dyn_cast(ModifiAdd); + else + Accum = ModifiAdd; + } + // If there is a single occurrence of the symbolic value, replace it // with a recurrence. unsigned FoundIndex = Add->getNumOperands(); @@ -4754,60 +4815,60 @@ for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i) if (i != FoundIndex) Ops.push_back(Add->getOperand(i)); - const SCEV *Accum = getAddExpr(Ops); + Accum = getAddExpr(Ops); + } - // This is not a valid addrec if the step amount is varying each - // loop iteration, but is not itself an addrec in this loop. - if (isLoopInvariant(Accum, L) || - (isa(Accum) && - cast(Accum)->getLoop() == L)) { - SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; + // This is not a valid addrec if the step amount is varying each + // loop iteration, but is not itself an addrec in this loop. + if (Accum && (isLoopInvariant(Accum, L) || + (isa(Accum) && + cast(Accum)->getLoop() == L))) { + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; - if (auto BO = MatchBinaryOp(BEValueV, DT)) { - if (BO->Opcode == Instruction::Add && BO->LHS == PN) { - if (BO->IsNUW) - Flags = setFlags(Flags, SCEV::FlagNUW); - if (BO->IsNSW) - Flags = setFlags(Flags, SCEV::FlagNSW); - } - } else if (GEPOperator *GEP = dyn_cast(BEValueV)) { - // If the increment is an inbounds GEP, then we know the address - // space cannot be wrapped around. We cannot make any guarantee - // about signed or unsigned overflow because pointers are - // unsigned but we may have a negative index from the base - // pointer. We can guarantee that no unsigned wrap occurs if the - // indices form a positive value. - if (GEP->isInBounds() && GEP->getOperand(0) == PN) { - Flags = setFlags(Flags, SCEV::FlagNW); + if (auto BO = MatchBinaryOp(BEValueV, DT)) { + if (BO->Opcode == Instruction::Add && BO->LHS == PN) { + if (BO->IsNUW) + Flags = setFlags(Flags, SCEV::FlagNUW); + if (BO->IsNSW) + Flags = setFlags(Flags, SCEV::FlagNSW); + } + } else if (GEPOperator *GEP = dyn_cast(BEValueV)) { + // If the increment is an inbounds GEP, then we know the address + // space cannot be wrapped around. We cannot make any guarantee + // about signed or unsigned overflow because pointers are + // unsigned but we may have a negative index from the base + // pointer. We can guarantee that no unsigned wrap occurs if the + // indices form a positive value. + if (GEP->isInBounds() && GEP->getOperand(0) == PN) { + Flags = setFlags(Flags, SCEV::FlagNW); - const SCEV *Ptr = getSCEV(GEP->getPointerOperand()); - if (isKnownPositive(getMinusSCEV(getSCEV(GEP), Ptr))) - Flags = setFlags(Flags, SCEV::FlagNUW); - } - - // We cannot transfer nuw and nsw flags from subtraction - // operations -- sub nuw X, Y is not the same as add nuw X, -Y - // for instance. + const SCEV *Ptr = getSCEV(GEP->getPointerOperand()); + if (isKnownPositive(getMinusSCEV(getSCEV(GEP), Ptr))) + Flags = setFlags(Flags, SCEV::FlagNUW); } - const SCEV *StartVal = getSCEV(StartValueV); - const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags); - - // Okay, for the entire analysis of this edge we assumed the PHI - // to be symbolic. We now need to go back and purge all of the - // entries for the scalars that use the symbolic expression. - forgetSymbolicName(PN, SymbolicName); - ValueExprMap[SCEVCallbackVH(PN, this)] = PHISCEV; - - // We can add Flags to the post-inc expression only if we - // know that it is *undefined behavior* for BEValueV to - // overflow. - if (auto *BEInst = dyn_cast(BEValueV)) - if (isLoopInvariant(Accum, L) && isAddRecNeverPoison(BEInst, L)) - (void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags); - - return PHISCEV; + // We cannot transfer nuw and nsw flags from subtraction + // operations -- sub nuw X, Y is not the same as add nuw X, -Y + // for instance. } + + const SCEV *StartVal = getSCEV(StartValueV); + const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags); + + // Okay, for the entire analysis of this edge we assumed the PHI + // to be symbolic. We now need to go back and purge all of the + // entries for the scalars that use the symbolic expression. + forgetSymbolicName(PN, SymbolicName); + ValueExprMap[SCEVCallbackVH(PN, this)] = PHISCEV; + + // We can add Flags to the post-inc expression only if we + // know that it is *undefined behavior* for BEValueV to + // overflow. + if (auto *BEInst = dyn_cast(BEValueV)) + if (isLoopInvariant(Accum, L) && isAddRecNeverPoison(BEInst, L)) + (void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags); + + return PHISCEV; } } else { // Otherwise, this could be a loop like this: @@ -6443,6 +6504,30 @@ } } + +const SCEV *ScalarEvolution::evaluateCompare(ICmpInst *IC) { + BasicBlock *Latch = nullptr; + const Loop *L = LI.getLoopFor(IC->getParent()); + + // If compare instruction is same or inverse of the compare in the + // branch of the loop latch, then return a constant evolution + // node. This shall facilitate computations of loop exit counts + // in cases where compare appears in the evolution chain of induction + // variables. + if (L && (Latch = L->getLoopLatch())) { + BranchInst *BI = dyn_cast(Latch->getTerminator()); + if (BI && BI->isConditional() && BI->getCondition() == IC) { + if (BI->getSuccessor(0) != L->getHeader()) + return getZero(Type::getInt1Ty(getContext())); + else + return getOne(Type::getInt1Ty(getContext())); + } + } + + return getUnknown(IC); +} + + void ScalarEvolution::forgetValue(Value *V) { Instruction *I = dyn_cast(V); if (!I) return; Index: lib/Transforms/Scalar/LoopStrengthReduce.cpp =================================================================== --- lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -2969,8 +2969,11 @@ // Ignore users that are part of a SCEV expression. This way we only // consider leaf IV Users. This effectively rediscovers a portion of // IVUsers analysis but in program order this time. - if (SE.isSCEVable(I.getType()) && !isa(SE.getSCEV(&I))) - continue; + if (SE.isSCEVable(I.getType())) { + const SCEV *SI = SE.getSCEV(&I); + if (!isa(SI) && !isa(SI)) + continue; + } // Remove this instruction from any NearUsers set it may be in. for (unsigned ChainIdx = 0, NChains = IVChainVec.size(); Index: test/Analysis/ScalarEvolution/pr34538.ll =================================================================== --- /dev/null +++ test/Analysis/ScalarEvolution/pr34538.ll @@ -0,0 +1,19 @@ +; RUN: opt -S -scalar-evolution -loop-deletion -simplifycfg -analyze < %s | FileCheck %s --check-prefix=CHECK-ANALYSIS + +define i32 @foo() local_unnamed_addr #0 { +; CHECK-ANALYSIS: Loop %do.body: backedge-taken count is 10000 +; CHECK-ANALYSIS: Loop %do.body: max backedge-taken count is 10000 +; CHECK-ANALYSIS: Loop %do.body: Predicated backedge-taken count is 10000 +entry: + br label %do.body + +do.body: ; preds = %do.body, %entry + %start.0 = phi i32 [ 0, %entry ], [ %inc.start.0, %do.body ] + %cmp = icmp slt i32 %start.0, 10000 + %inc = zext i1 %cmp to i32 + %inc.start.0 = add nsw i32 %start.0, %inc + br i1 %cmp, label %do.body, label %do.end + +do.end: ; preds = %do.body + ret i32 0 +} Index: test/Analysis/ScalarEvolution/select.ll =================================================================== --- /dev/null +++ test/Analysis/ScalarEvolution/select.ll @@ -0,0 +1,19 @@ +; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s --check-prefix=CHECK-ANALYSIS + +define i32 @foo() { +entry: + br label %do.body + +do.body: ; preds = %do.body, %entry + %start.0 = phi i32 [ 0, %entry ], [ %inc.start.0, %do.body ] + %cmp = icmp slt i32 %start.0, 10000 + %select_ext = select i1 %cmp, i32 2 , i32 1 + %inc.start.0 = add nsw i32 %start.0, %select_ext + br i1 %cmp, label %do.body, label %do.end + +do.end: ; preds = %do.body + ret i32 0 +; CHECK-ANALYSIS: Loop %do.body: backedge-taken count is 5000 +; CHECK-ANALYSIS: Loop %do.body: max backedge-taken count is 5000 +; CHECK-ANALYSIS: Loop %do.body: Predicated backedge-taken count is 5000 +}