[SCEV] Handling for ICmp occuring in the evolution chain.
Summary:
If a 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.
Will fix PR 34538
Reviewers: sanjoy, hfinkel, junryoungju
Reviewed By: sanjoy, junryoungju
Subscribers: javed.absar, llvm-commits
Differential Revision: https://reviews.llvm.org/D38494
llvm-svn: 318050
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index d48e8a5..7795a33 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -4080,6 +4080,85 @@
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<SCEVBackedgeConditionFolder> {
+public:
+ static const SCEV *rewrite(const SCEV *S, const Loop *L,
+ ScalarEvolution &SE) {
+ bool IsPosBECond;
+ Value *BECond = nullptr;
+ if (BasicBlock *Latch = L->getLoopLatch()) {
+ BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
+ if (BI && BI->isConditional() &&
+ BI->getSuccessor(0) != BI->getSuccessor(1)) {
+ BECond = BI->getCondition();
+ IsPosBECond = BI->getSuccessor(0) == L->getHeader();
+ } else {
+ return S;
+ }
+ }
+ SCEVBackedgeConditionFolder Rewriter(L, BECond, IsPosBECond, 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<Instruction>(Expr->getValue());
+ switch (I->getOpcode()) {
+ case Instruction::Select: {
+ SelectInst *SI = cast<SelectInst>(I);
+ Optional<const SCEV *> Res =
+ compareWithBackedgeCondition(SI->getCondition());
+ if (Res.hasValue()) {
+ bool IsOne = cast<SCEVConstant>(Res.getValue())->getValue()->isOne();
+ Result = SE.getSCEV(IsOne ? SI->getTrueValue() : SI->getFalseValue());
+ }
+ break;
+ }
+ default: {
+ Optional<const SCEV *> Res = compareWithBackedgeCondition(I);
+ if (Res.hasValue())
+ Result = Res.getValue();
+ break;
+ }
+ }
+ }
+ return Result;
+ }
+
+private:
+ explicit SCEVBackedgeConditionFolder(const Loop *L, Value *BECond,
+ bool IsPosBECond, ScalarEvolution &SE)
+ : SCEVRewriteVisitor(SE), L(L), BackedgeCond(BECond),
+ IsPositiveBECond(IsPosBECond) {}
+
+ Optional<const SCEV *> compareWithBackedgeCondition(Value *IC);
+
+ const Loop *L;
+ /// Loop back condition.
+ Value *BackedgeCond = nullptr;
+ /// Set to true if loop back is on positive branch condition.
+ bool IsPositiveBECond;
+};
+
+Optional<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 IsPositiveBECond ? SE.getOne(Type::getInt1Ty(SE.getContext()))
+ : SE.getZero(Type::getInt1Ty(SE.getContext()));
+ return None;
+}
+
class SCEVShiftRewriter : public SCEVRewriteVisitor<SCEVShiftRewriter> {
public:
SCEVShiftRewriter(const Loop *L, ScalarEvolution &SE)
@@ -4753,7 +4832,8 @@
SmallVector<const SCEV *, 8> 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 +4859,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<Instruction>(BEValueV))
if (isLoopInvariant(Accum, L) && isAddRecNeverPoison(BEInst, L))
(void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags);
-
+
return PHISCEV;
}
}