[SCEV] Enhance SCEVFindUnsafe for division

[mkazantsev]

Summary

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

[sanjoy]

test/Transforms/IndVarSimplify/udiv.ll

172

Put something else instead of undef here for completeness, loading from undef is UB.

[mkazantsev]

test/Transforms/IndVarSimplify/udiv.ll

172

Ok, will do before checking in.

[eastig]

Hi,
This patch caused SingleSource/Benchmarks/Shootout/shootout-sieve regression on Arm public bots:

http://lnt.llvm.org/db_default/v4/nts/76950 13.43%
http://lnt.llvm.org/db_default/v4/nts/77068 10.61%

The affected pass is LSR.
I'll provide more data shortly.

Thanks,
Evgeny Astigeevich
The ARM Compiler Optimization team leader

[eastig]

The benchmark source file: http://www.llvm.org/viewvc/llvm-project/test-suite/trunk/SingleSource/Benchmarks/Shootout/sieve.c?view=markup

[eastig]

I attached

comp.good.log14 KBDownload

comp.bad.log15 KBDownload

Comparing them I can see a number of operations in a loop is increased.

Compiler options:
clang -c -S --target=aarch64-linux-gnueabi -DNDEBUG -O3 -DNDEBUG -mcpu=cortex-a57 -fomit-frame-pointer sieve.c

[mkazantsev]

Reverted as https://reviews.llvm.org/rL316739. I will try to understand what happens.

[mkazantsev]

Hi Evgeny!

I see the difference before the LSR: for the last loop, in the *** IR Dump Before Loop Strength Reduction *** section we have two more Phis. It has two more Phis and more instructions in body (with repeating pattern). Most likely it is unrolling changed the number of unrolled iterations.

For first two loops, in one case it just changed iteration space from 0->len to len->0 which shouldn't have significant performance impact; in another case nothing changed but variable name.

So I believe that problem dwells before LSR, most likely in unrolling.

[eastig]

Hi Max,

Thank you for initial investigation. I'll try to debug the unrolling.

Thanks,
Evgeny

[eastig]

test.ll9 KBDownload

test.good.ll10 KBDownload

test.bad.ll11 KBDownload

Hi Max,

I did some debugging. It's definitely LSR. Compare test.good.ll and test.bad.ll produced from test.ll with

opt -loop-reduce -S -o - test.ll

Thanks,
Evgeny

lib/Analysis/ScalarEvolutionExpander.cpp

 // UDiv expressions. We don't know if the UDiv is derived from an IR divide
 // instruction, but the important thing is that we prove the denominator is
 // nonzero before expansion.
 //
 // IVUsers already checks that IV-derived expressions are safe. So this check is
 // 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
 // applicable. Expanding a nested recurrence outside a loop requires computing
 // binomial coefficients. This could be done, but the recurrence has to be in a
 // perfectly reduced form, which can't be guaranteed.
 struct SCEVFindUnsafe {
   ScalarEvolution &SE;
   bool IsUnsafe;
 
   SCEVFindUnsafe(ScalarEvolution &se): SE(se), IsUnsafe(false) {}
 
   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;
         return false;
       }
     }
     return true;
   }

test/Transforms/IndVarSimplify/udiv.ll

 
 declare i32 @atoi(i8* nocapture) nounwind readonly
 
 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
   %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
   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
 }
+
+; 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) nounwind {
+entry:
+  %denom = load i64, i64* undef, 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}