[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

                                       : ICmpInst::ICMP_ULT;
   const SCEV *Start = IV->getStart();
   const SCEV *End = RHS;
-  if (!isLoopEntryGuardedByCond(L, Cond, getMinusSCEV(Start, Stride), RHS))
-    End = IsSigned ? getSMaxExpr(RHS, Start)
-                   : getUMaxExpr(RHS, Start);
+  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);
 

 
   const SCEV *Start = IV->getStart();
   const SCEV *End = RHS;
-  if (!isLoopEntryGuardedByCond(L, Cond, getAddExpr(Start, Stride), RHS))
-    End = IsSigned ? getSMinExpr(RHS, Start)
-                   : getUMinExpr(RHS, Start);
+  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);
 

test/Analysis/ScalarEvolution/nsw.ll

   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

 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
+}