Index: include/llvm/Analysis/ScalarEvolution.h =================================================================== --- include/llvm/Analysis/ScalarEvolution.h +++ include/llvm/Analysis/ScalarEvolution.h @@ -1378,6 +1378,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,80 @@ bool Valid = true; }; +/// This class evaluates the compare condition by matching it against the +/// condition of loop latch. If there is a match we assume a true value +/// for the condition while building SCEV nodes. +class SCEVBackedgeConditionFolder + : public SCEVRewriteVisitor { +public: + SCEVBackedgeConditionFolder(const Loop *L, ScalarEvolution &SE) + : SCEVRewriteVisitor(SE), L(L) { + if (BasicBlock *Latch = L->getLoopLatch()) { + BranchInst *BI = dyn_cast(Latch->getTerminator()); + if (BI && BI->isConditional()) { + BackedgeCond = BI->getCondition(); + IsPositiveBackedgeCond = BI->getSuccessor(0) == L->getHeader(); + } + } + } + + static const SCEV *rewrite(const SCEV *S, const Loop *L, + ScalarEvolution &SE) { + SCEVBackedgeConditionFolder Rewriter(L, SE); + return Rewriter.visit(S); + } + + const SCEV *visitUnknown(const SCEVUnknown *Expr) { + const SCEV *Result = Expr; + bool InvariantF = SE.isLoopInvariant(Expr, L); + + if (!InvariantF) { + Instruction *I = cast(Expr->getValue()); + switch (I->getOpcode()) { + case Instruction::Select: { + const SCEV *CondSE = compareWithBackedgeCondition(I->getOperand(0)); + if (isa(CondSE)) { + bool IsOne = cast(CondSE)->getValue()->isOne(); + Value *TrueVal = I->getOperand(1); + Value *FalseVal = I->getOperand(2); + Result = SE.getSCEV(IsOne ? TrueVal : FalseVal); + } + break; + } + default: { + const SCEV *ICmpSE = compareWithBackedgeCondition(I); + if (isa(ICmpSE)) + Result = ICmpSE; + break; + } + } + } + return Result; + } + +private: + const Loop *L; + Value *BackedgeCond = nullptr; + + // Set to true if loop back is on positive branch condition. + bool IsPositiveBackedgeCond; + + const SCEV * compareWithBackedgeCondition(Value *IC); +}; + +const SCEV * +SCEVBackedgeConditionFolder::compareWithBackedgeCondition(Value *IC) { + + // If value matches the backedge condition for loop latch, + // then return a constant evolution node based on loopback + // branch taken. + if (BackedgeCond == IC) + return IsPositiveBackedgeCond + ? SE.getOne(Type::getInt1Ty(SE.getContext())) + : SE.getZero(Type::getInt1Ty(SE.getContext())); + return SE.getUnknown(IC); +} + class SCEVShiftRewriter : public SCEVRewriteVisitor { public: SCEVShiftRewriter(const Loop *L, ScalarEvolution &SE) @@ -4753,7 +4827,8 @@ SmallVector Ops; for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i) if (i != FoundIndex) - Ops.push_back(Add->getOperand(i)); + Ops.push_back(SCEVBackedgeConditionFolder::rewrite(Add->getOperand(i), + L, *this)); const SCEV *Accum = getAddExpr(Ops); // This is not a valid addrec if the step amount is varying each @@ -4779,33 +4854,33 @@ // 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 *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; } } @@ -6443,6 +6518,8 @@ } } + + 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 @@ -2970,7 +2970,7 @@ // 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; + 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,39 @@ +; RUN: opt -scalar-evolution -loop-deletion -simplifycfg -analyze < %s | FileCheck %s --check-prefix=CHECK-ANALYSIS-1 +; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s --check-prefix=CHECK-ANALYSIS-2 + +define i32 @pr34538() local_unnamed_addr #0 { +; CHECK-ANALYSIS-1: Loop %do.body: backedge-taken count is 10000 +; CHECK-ANALYSIS-1: Loop %do.body: max backedge-taken count is 10000 +; CHECK-ANALYSIS-1: 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 +} + + +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-2: Loop %do.body: backedge-taken count is 5000 +; CHECK-ANALYSIS-2: Loop %do.body: max backedge-taken count is 5000 +; CHECK-ANALYSIS-2: Loop %do.body: Predicated backedge-taken count is 5000 +}