Index: include/llvm/Analysis/ScalarEvolution.h =================================================================== --- include/llvm/Analysis/ScalarEvolution.h +++ include/llvm/Analysis/ScalarEvolution.h @@ -1399,6 +1399,8 @@ /// SCEV+Loop pair. const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L); + ConstantInt *computeICmpCondV(ICmpInst *ICI, const Loop* L); + /// This looks up computed SCEV values for all instructions that depend on /// the given instruction and removes them from the ValueExprMap map if they /// reference SymName. This is used during PHI resolution. Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -4688,6 +4688,31 @@ return PHISCEV; } +ConstantInt *ScalarEvolution::computeICmpCondV(ICmpInst *IC, const Loop* L) +{ + BasicBlock *Latch = nullptr; + + if (!L) + 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 ConstantInt::get(Type::getInt1Ty(getContext()), 0); + else + return ConstantInt::get(Type::getInt1Ty(getContext()), 1); + } + } + + return nullptr; +} + const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) { const Loop *L = LI.getLoopFor(PN->getParent()); if (!L || L->getHeader() != PN->getParent()) @@ -4756,6 +4781,17 @@ Ops.push_back(Add->getOperand(i)); const SCEV *Accum = getAddExpr(Ops); + // The Accum still can be varaiant. + // we should try re evolute Accum with under else if chain. + if (!isLoopInvariant(Accum, L)) + if (isa(Accum) || isa(Accum)) + { + eraseValueFromMap(PN); + ValueExprMap[SCEVCallbackVH(BEValueV, this)] = Accum; + + return createAddRecFromPHI(PN); + } + // 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) || @@ -4809,6 +4845,68 @@ return PHISCEV; } } + } else if (isa(BEValue) || isa(BEValue)) { + // Okay, now we are going to check that Loop's condition operand is increasing. + BranchInst *BR = dyn_cast(L->getLoopLatch()->getTerminator()); + + // If it has conditional branch. + if (BR && BR->isConditional()) { + ICmpInst *ICI = dyn_cast(BR->getCondition()); + + if (ConstantInt* CondV = computeICmpCondV(ICI, L)) { + bool isaTrueCond = CondV->isOne(); + + // Now we are checking that BEValueV is increasing ICI's operand. + Instruction *AddExpr = dyn_cast(BEValueV); + Value *LHS = ICI->getOperand(0); + Value *RHS = ICI->getOperand(1); + + // We are not finding a constant. we are finding expression that we increasing. + if (isa(RHS)) + std::swap(LHS, RHS); + + // It can be select instruction. + // that selected condition should same so we can analyze. + if (SelectInst *SI = dyn_cast(AddExpr)) + if (ICI == SI->getCondition()) { + if (isaTrueCond) + AddExpr = dyn_cast(SI->getTrueValue()); + else + AddExpr = dyn_cast(SI->getFalseValue()); + } + + // Check that we are increasing is ICI's operand. + // AddExpr's first operand is target. + if (AddExpr && AddExpr->getOperand(0) == RHS) { + // Yes its increasing ICI's operand. now we can assume that this loop can exit. + const SCEV* SCEVStart = getSCEV(StartValueV); + const SCEV* SCEVStep; + const SCEV* NewAddExpr; + + // AddExpr's operand can be constant. it means it probably not increasing constant 1 + // so we are going to just evolute constant variable. + if (Constant* ST = dyn_cast(AddExpr->getOperand(1))) + SCEVStep = getSCEV(ST); + else if (SelectInst *SI = dyn_cast(AddExpr->getOperand(1))) + SCEVStep = createNodeForSelectOrPHI(SI, CondV, SI->getTrueValue(), SI->getFalseValue()); + else + SCEVStep = getConstant(AddExpr->getType(), isaTrueCond); + + // Check that SCEVStep is evoluted as constant. + if (isa(SCEVStep)) { + NewAddExpr = getAddRecExpr(SCEVStart, SCEVStep, L, SCEV::FlagAnyWrap); + + forgetSymbolicName(PN, SymbolicName); + ValueExprMap[SCEVCallbackVH(PN, this)] = NewAddExpr; + + return NewAddExpr; + } + + // We need to wait for other passes to make this loop simpler. + // Or not, this cannot be evoluted. + } + } + } } else { // Otherwise, this could be a loop like this: // i = 0; for (j = 1; ..; ++j) { .... i = j; } @@ -4822,7 +4920,7 @@ const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *this); const SCEV *Start = SCEVInitRewriter::rewrite(Shifted, L, *this); if (Shifted != getCouldNotCompute() && - Start != getCouldNotCompute()) { + Start != getCouldNotCompute()) { const SCEV *StartVal = getSCEV(StartValueV); if (Start == StartVal) { // Okay, for the entire analysis of this edge we assumed the PHI @@ -5022,6 +5120,9 @@ if (!ICI) return getUnknown(I); + if (ConstantInt* ValueV = computeICmpCondV(ICI, nullptr)) + return getSCEV(ValueV->isOne() ? TrueVal : FalseVal); + Value *LHS = ICI->getOperand(0); Value *RHS = ICI->getOperand(1); Index: test/Analysis/ScalarEvolution/cond_1.ll =================================================================== --- /dev/null +++ test/Analysis/ScalarEvolution/cond_1.ll @@ -0,0 +1,20 @@ + +; 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 +} \ No newline at end of file Index: test/Analysis/ScalarEvolution/cond_2.ll =================================================================== --- /dev/null +++ test/Analysis/ScalarEvolution/cond_2.ll @@ -0,0 +1,20 @@ + +; 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 3 , 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 +} \ No newline at end of file Index: test/Analysis/ScalarEvolution/cond_3.ll =================================================================== --- /dev/null +++ test/Analysis/ScalarEvolution/cond_3.ll @@ -0,0 +1,21 @@ + +; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s --check-prefix=CHECK-ANALYSIS + +define i32 @foo() { + br label %do_start + +do_start: + %inc = phi i32 [ 0, %0 ], [ %add, %do_start ] + %cmp = icmp slt i32 %inc, 10000 + %add_cond = add nsw i32 %inc, 2 + %sel = select i1 %cmp, i32 %add_cond, i32 %inc + %add = add nsw i32 %sel, 1 + br i1 %cmp, label %do_start, label %do_end + +; CHECK-ANALYSIS: Loop %do_start: backedge-taken count is 3334 +; CHECK-ANALYSIS: Loop %do_start: max backedge-taken count is 3334 +; CHECK-ANALYSIS: Loop %do_start: Predicated backedge-taken count is 3334 + +do_end: + ret i32 0 +} \ No newline at end of file