[SCEV] Improve Scalar Evolution's use of no {un,}signed wrap flags

[bsmith]

Summary

In a case where we have a no {un,}signed wrap flag on the increment of a loop and
RHS - Start is constant then we can avoid inserting a max operation between
the two, since we can statically determine which is greater.

This allows us to unroll loops such as:

void testcase3(int v) {
  for (int i=v; i<=v+1; ++i)
    f(i);
}

This patch implements this optimization.

[rengolin]

Hi Bradley,

Looks good, but I'm no expert in the scalar evolution, so I'll let others approve your patch.

cheers,
--renato

[hfinkel]

Please post patches will full context, see http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface for more information.

(also, adding Andy)

[bsmith]

Add context to patch. Apologies, I'd totally forgotten about doing this!

[aschwaighofer]

LGTM.

Thanks.

lib/Analysis/ScalarEvolution.cpp

6971

s/operaions/operation/

7052

s/operaions/operation/

[bsmith]

Committed as 220960, thanks!

[sanjoy]

Hi,

I've had to (effectively) revert this change in http://reviews.llvm.org/rL273079. I don't think it does the right thing in the test cases checked in with http://reviews.llvm.org/rL273079, please take a look.

lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
   // behaviors like the case of C language.
   if (!Stride->isOne() && doesIVOverflowOnLT(RHS, Stride, IsSigned, NoWrap))
     return getCouldNotCompute();
 
   ICmpInst::Predicate Cond = IsSigned ? ICmpInst::ICMP_SLT
                                       : ICmpInst::ICMP_ULT;
   const SCEV *Start = IV->getStart();
   const SCEV *End = RHS;
-  if (!isLoopEntryGuardedByCond(L, Cond, getMinusSCEV(Start, Stride), RHS))
+  if (!isLoopEntryGuardedByCond(L, Cond, getMinusSCEV(Start, Stride), RHS)) {
+    const SCEV *Diff = getMinusSCEV(RHS, Start);
+    // If we have NoWrap set, then we can assume that the increment won't
+    // overflow, in which case if RHS - Start is a constant, we don't need to
+    // do a max operaions since we can just figure it out statically
+    if (NoWrap && isa<SCEVConstant>(Diff)) {
+      APInt D = dyn_cast<const SCEVConstant>(Diff)->getValue()->getValue();
+      if (D.isNegative())
+        End = Start;
+    } else
       End = IsSigned ? getSMaxExpr(RHS, Start)
                      : getUMaxExpr(RHS, Start);
+  }
 
   const SCEV *BECount = computeBECount(getMinusSCEV(End, Start), Stride, false);
 
   APInt MinStart = IsSigned ? getSignedRange(Start).getSignedMin()
                             : getUnsignedRange(Start).getUnsignedMin();
 
   APInt MinStride = IsSigned ? getSignedRange(Stride).getSignedMin()
                              : getUnsignedRange(Stride).getUnsignedMin();
ScalarEvolution::HowManyGreaterThans(const SCEV *LHS, const SCEV *RHS,
   if (!Stride->isOne() && doesIVOverflowOnGT(RHS, Stride, IsSigned, NoWrap))
     return getCouldNotCompute();
 
   ICmpInst::Predicate Cond = IsSigned ? ICmpInst::ICMP_SGT
                                       : ICmpInst::ICMP_UGT;
 
   const SCEV *Start = IV->getStart();
   const SCEV *End = RHS;
-  if (!isLoopEntryGuardedByCond(L, Cond, getAddExpr(Start, Stride), RHS))
+  if (!isLoopEntryGuardedByCond(L, Cond, getAddExpr(Start, Stride), RHS)) {
+    const SCEV *Diff = getMinusSCEV(RHS, Start);
+    // If we have NoWrap set, then we can assume that the increment won't
+    // overflow, in which case if RHS - Start is a constant, we don't need to
+    // do a max operaions since we can just figure it out statically
+    if (NoWrap && isa<SCEVConstant>(Diff)) {
+      APInt D = dyn_cast<const SCEVConstant>(Diff)->getValue()->getValue();
+      if (!D.isNegative())
+        End = Start;
+    } else
       End = IsSigned ? getSMinExpr(RHS, Start)
                      : getUMinExpr(RHS, Start);
+  }
 
   const SCEV *BECount = computeBECount(getMinusSCEV(Start, End), Stride, false);
 
   APInt MaxStart = IsSigned ? getSignedRange(Start).getSignedMax()
                             : getUnsignedRange(Start).getUnsignedMax();
 
   APInt MinStride = IsSigned ? getSignedRange(Stride).getSignedMin()
                              : getUnsignedRange(Stride).getUnsignedMin();

test/Analysis/ScalarEvolution/nsw.ll

greater:
   %tmp2 = add nsw i32 %a, %b
   br label %exit
 
 exit:
   %result = phi i32 [ %a, %entry ], [ %tmp2, %greater ]
   ret i32 %result
 }
 
-; TODO: This could fold down to '1'
 ; CHECK-LABEL: PR12375
-; CHECK: -->  {(4 + %arg),+,4}<nuw><%bb1>    Exits: (4 + (4 * ((-1 + (-1 * %arg) + ((4 + %arg) umax (8 + %arg)<nsw>)) /u 4)) + %arg)
+; CHECK: -->  {(4 + %arg),+,4}<nuw><%bb1>    Exits: (8 + %arg)<nsw>
 define i32 @PR12375(i32* readnone %arg) {
 bb:
   %tmp = getelementptr inbounds i32* %arg, i64 2
   br label %bb1
 
 bb1:                                              ; preds = %bb1, %bb
   %tmp2 = phi i32* [ %arg, %bb ], [ %tmp5, %bb1 ]
   %tmp3 = phi i32 [ 0, %bb ], [ %tmp4, %bb1 ]
bb2:                                              ; preds = %bb2, %bb
   %tmp = phi i32* [ %arg, %bb ], [ %tmp4, %bb2 ]
   %tmp3 = icmp ult i32* %tmp, %arg1
   %tmp4 = getelementptr inbounds i32* %tmp, i64 1
   br i1 %tmp3, label %bb2, label %bb5
 
 bb5:                                              ; preds = %bb2
   ret void
 }
+
+declare void @f(i32)
+
+; CHECK-LABEL: nswnowrap
+; CHECK: --> {(1 + %v),+,1}<nsw><%for.body>   Exits: (2 + %v)
+define void @nswnowrap(i32 %v) {
+entry:
+  %add = add nsw i32 %v, 1
+  br label %for.body
+
+for.body:
+  %i.04 = phi i32 [ %v, %entry ], [ %inc, %for.body ]
+  %inc = add nsw i32 %i.04, 1
+  tail call void @f(i32 %i.04)
+  %cmp = icmp slt i32 %i.04, %add
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  ret void
+}

test/Transforms/LoopUnroll/nsw-tripcount.ll

+; RUN: opt -loop-unroll -S %s | FileCheck %s
+
+; extern void f(int);
+; void test1(int v) {
+;   for (int i=v; i<=v+1; ++i)
+;     f(i);
+; }
+;
+; We can use the nsw information to see that the tripcount will be 2, so the
+; loop should be unrolled as this is always beneficial
+
+declare void @f(i32)
+
+; CHECK-LABEL: @test1
+define void @test1(i32 %v) {
+entry:
+  %add = add nsw i32 %v, 1
+  br label %for.body
+
+for.body:
+  %i.04 = phi i32 [ %v, %entry ], [ %inc, %for.body ]
+  tail call void @f(i32 %i.04)
+  %inc = add nsw i32 %i.04, 1
+  %cmp = icmp slt i32 %i.04, %add
+  br i1 %cmp, label %for.body, label %for.end
+
+; CHECK: call void @f
+; CHECK-NOT: br i1
+; CHECK: call void @f
+for.end:
+  ret void
+}