[SCEV] Add URem support to SCEV

In LLVM IR the following code:

    %r = urem <ty> %t, %b

is equivalent to

    %q = udiv <ty> %t, %b
    %s = mul <ty> nuw %q, %b
    %r = sub <ty> nuw %t, %q ; (t / b) * b + (t % b) = t

As UDiv, Mul and Sub are already supported by SCEV, URem can be implemented
with minimal effort using that relation:

    %r --> (-%b * (%t /u %b)) + %t

We implement two special cases:

  - if %b is 1, the result is always 0
  - if %b is a power-of-two, we produce a zext/trunc based expression instead

That is, the following code:

    %r = urem i32 %t, 65536

Produces:

    %r --> (zext i16 (trunc i32 %a to i16) to i32)

Note that while this helps get a tighter bound on the range analysis and the
known-bits analysis, this exposes some normalization shortcoming of SCEVs:

    %div = udim i32 %a, 65536
    %mul = mul i32 %div, 65536
    %rem = urem i32 %a, 65536
    %add = add i32 %mul, %rem

Will usually not be reduced.

llvm-svn: 312329

2 files changed, 55 insertions, 0 deletions

diff --git a/llvm/test/Analysis/ScalarEvolution/flattened-0.ll b/llvm/test/Analysis/ScalarEvolution/flattened-0.ll
new file mode 100644
index 00000000000..e6614ffd646
--- /dev/null
+++ b/llvm/test/Analysis/ScalarEvolution/flattened-0.ll
@@ -0,0 +1,22 @@
+; RUN: opt < %s -scalar-evolution -analyze | FileCheck %s
+
+define void @foo([7 x i8]* %a) {
+; CHECK-LABEL: @foo
+entry:
+	br label %bb
+
+bb:
+	%idx = phi i64 [ 0, %entry ], [ %idx.incr, %bb ]
+	%i = udiv i64 %idx, 7
+	%j = urem i64 %idx, 7
+	%a.ptr = getelementptr [7 x i8], [7 x i8]* %a, i64 %i, i64 %j
+; CHECK: %a.ptr = getelementptr [7 x i8], [7 x i8]* %a, i64 %i, i64 %j
+; CHECK-NEXT: -->  {%a,+,1}<nw><%bb>
+	%val = load i8, i8* %a.ptr
+	%idx.incr = add i64 %idx, 1
+	%test = icmp ne i64 %idx.incr, 35
+	br i1 %test, label %bb, label %exit
+
+exit:
+	ret void
+}
diff --git a/llvm/test/Analysis/ScalarEvolution/urem-0.ll b/llvm/test/Analysis/ScalarEvolution/urem-0.ll
new file mode 100644
index 00000000000..a53f75b86fa
--- /dev/null
+++ b/llvm/test/Analysis/ScalarEvolution/urem-0.ll
@@ -0,0 +1,33 @@
+; RUN: opt < %s -scalar-evolution -analyze | FileCheck %s
+
+define i8 @foo(i8 %a) {
+; CHECK-LABEL: @foo
+        %t0 = urem i8 %a, 27
+; CHECK: %t0 = urem i8 %a, 27
+; CHECK-NEXT: -->  ((-27 * (%a /u 27)) + %a)
+        ret i8 %t0
+}
+
+define i8 @bar(i8 %a) {
+; CHECK-LABEL: @bar
+        %t1 = urem i8 %a, 1
+; CHECK: %t1 = urem i8 %a, 1
+; CHECK-NEXT: -->  0
+        ret i8 %t1
+}
+
+define i8 @baz(i8 %a) {
+; CHECK-LABEL: @baz
+        %t2 = urem i8 %a, 32
+; CHECK: %t2 = urem i8 %a, 32
+; CHECK-NEXT: -->  (zext i5 (trunc i8 %a to i5) to i8)
+        ret i8 %t2
+}
+
+define i8 @qux(i8 %a) {
+; CHECK-LABEL: @qux
+        %t3 = urem i8 %a, 2
+; CHECK: %t3 = urem i8 %a, 2
+; CHECK-NEXT: -->  (zext i1 (trunc i8 %a to i1) to i8)
+        ret i8 %t3
+}