[SCEV] Enhance SCEVFindUnsafe for division

This patch allows SCEVFindUnsafe algorithm to tread division by any non-positive
value as safe. Previously, it could only recognize non-zero constants.

Differential Revision: https://reviews.llvm.org/D39228


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@316568 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 40 insertions, 10 deletions

diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index 47bdac00ae1..964a79803fa 100644
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -2250,10 +2250,6 @@ namespace {
 // only needed when the expression includes some subexpression that is not IV
 // derived.
 //
-// Currently, we only allow division by a nonzero constant here. If this is
-// inadequate, we could easily allow division by SCEVUnknown by using
-// ValueTracking to check isKnownNonZero().
-//
 // We cannot generally expand recurrences unless the step dominates the loop
 // header. The expander handles the special case of affine recurrences by
 // scaling the recurrence outside the loop, but this technique isn't generally
@@ -2268,13 +2264,11 @@ struct SCEVFindUnsafe {
 
   bool follow(const SCEV *S) {
     if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
-      const SCEVConstant *SC = dyn_cast<SCEVConstant>(D->getRHS());
-      if (!SC || SC->getValue()->isZero()) {
+      if (!SE.isKnownNonZero(D->getRHS())) {
         IsUnsafe = true;
         return false;
       }
-    }
-    if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
+    } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
       const SCEV *Step = AR->getStepRecurrence(SE);
       if (!AR->isAffine() && !SE.dominates(Step, AR->getLoop()->getHeader())) {
         IsUnsafe = true;
diff --git a/test/Transforms/IndVarSimplify/udiv.ll b/test/Transforms/IndVarSimplify/udiv.ll
index b3f2c2a6a66..0f9a54e8c4f 100644
--- a/test/Transforms/IndVarSimplify/udiv.ll
+++ b/test/Transforms/IndVarSimplify/udiv.ll
@@ -130,11 +130,11 @@ declare i32 @printf(i8* nocapture, ...) nounwind
 ; IndVars doesn't emit a udiv in for.body.preheader since SCEVExpander::expand will
 ; find out there's already a udiv in the original code.
 
-; CHECK-LABEL: @foo(
+; CHECK-LABEL: @foo_01(
 ; CHECK: for.body.preheader:
 ; CHECK-NOT: udiv
 
-define void @foo(double* %p, i64 %n) nounwind {
+define void @foo_01(double* %p, i64 %n) nounwind {
 entry:
   %div0 = udiv i64 %n, 7                          ; <i64> [#uses=1]
   %div1 = add i64 %div0, 1
@@ -160,3 +160,39 @@ for.end.loopexit:                                 ; preds = %for.body
 for.end:                                          ; preds = %for.end.loopexit, %entry
   ret void
 }
+
+; Same as foo_01, but we divide by non-constant value.
+
+; CHECK-LABEL: @foo_02(
+; CHECK: for.body.preheader:
+; CHECK-NOT: udiv
+
+define void @foo_02(double* %p, i64 %n, i64* %lp) nounwind {
+entry:
+  %denom = load i64, i64* %lp, align 4, !range !0
+  %div0 = udiv i64 %n, %denom                          ; <i64> [#uses=1]
+  %div1 = add i64 %div0, 1
+  %cmp2 = icmp ult i64 0, %div1                   ; <i1> [#uses=1]
+  br i1 %cmp2, label %for.body.preheader, label %for.end
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %i.03 = phi i64 [ %inc, %for.body ], [ 0, %for.body.preheader ] ; <i64> [#uses=2]
+  %arrayidx = getelementptr inbounds double, double* %p, i64 %i.03 ; <double*> [#uses=1]
+  store double 0.000000e+00, double* %arrayidx
+  %inc = add i64 %i.03, 1                         ; <i64> [#uses=2]
+  %divx = udiv i64 %n, %denom                           ; <i64> [#uses=1]
+  %div = add i64 %divx, 1
+  %cmp = icmp ult i64 %inc, %div                  ; <i1> [#uses=1]
+  br i1 %cmp, label %for.body, label %for.end.loopexit
+
+for.end.loopexit:                                 ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.end.loopexit, %entry
+  ret void
+}
+
+!0 = !{i64 1, i64 10}