Re-re-land: Teach CorrelatedValuePropagation to reduce the width of udiv/urem instructions.

Summary:
If the operands of a udiv/urem can be proved to fit within a smaller
power-of-two-sized type, reduce the width of the udiv/urem.

Backed out for causing performance regressions.  Re-landing
because we've determined that these regressions were noise.

Original Differential Revision: https://reviews.llvm.org/D44102

llvm-svn: 328096

2 files changed, 196 insertions, 0 deletions

diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/udiv.ll b/llvm/test/Transforms/CorrelatedValuePropagation/udiv.ll
new file mode 100644
index 00000000000..19078134e6f
--- /dev/null
+++ b/llvm/test/Transforms/CorrelatedValuePropagation/udiv.ll
@@ -0,0 +1,95 @@
+; RUN: opt < %s -correlated-propagation -S | FileCheck %s
+
+; CHECK-LABEL: @test_nop
+define void @test_nop(i32 %n) {
+; CHECK udiv i32 %n, 100
+  %div = udiv i32 %n, 100
+  ret void
+}
+
+; CHECK-LABEL: @test1(
+define void @test1(i32 %n) {
+entry:
+  %cmp = icmp ule i32 %n, 65535
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: udiv i16
+  %div = udiv i32 %n, 100
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test2(
+define void @test2(i32 %n) {
+entry:
+  %cmp = icmp ule i32 %n, 65536
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: udiv i32 %n, 100
+  %div = udiv i32 %n, 100
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test3(
+define void @test3(i32 %m, i32 %n) {
+entry:
+  %cmp1 = icmp ult i32 %m, 65535
+  %cmp2 = icmp ult i32 %n, 65535
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: udiv i16
+  %div = udiv i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test4(
+define void @test4(i32 %m, i32 %n) {
+entry:
+  %cmp1 = icmp ult i32 %m, 65535
+  %cmp2 = icmp ule i32 %n, 65536
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: udiv i32 %m, %n
+  %div = udiv i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test5
+define void @test5(i32 %n) {
+  %trunc = and i32 %n, 65535
+  ; CHECK: udiv i16
+  %div = udiv i32 %trunc, 42
+  ret void
+}
+
+; CHECK-LABEL: @test6
+define void @test6(i32 %n) {
+entry:
+  %cmp = icmp ule i32 %n, 255
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: udiv i8
+  %div = sdiv i32 %n, 100
+  br label %exit
+
+exit:
+  ret void
+}
diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/urem.ll b/llvm/test/Transforms/CorrelatedValuePropagation/urem.ll
new file mode 100644
index 00000000000..b01e9c5723e
--- /dev/null
+++ b/llvm/test/Transforms/CorrelatedValuePropagation/urem.ll
@@ -0,0 +1,101 @@
+; RUN: opt < %s -correlated-propagation -S | FileCheck %s
+
+; CHECK-LABEL: @test_nop
+define void @test_nop(i32 %n) {
+; CHECK udiv i32 %n, 100
+  %div = udiv i32 %n, 100
+  ret void
+}
+
+; CHECK-LABEL: @test1(
+define void @test1(i32 %n) {
+entry:
+  %cmp = icmp ule i32 %n, 65535
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: urem i16
+  %div = urem i32 %n, 100
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test2(
+define void @test2(i32 %n) {
+entry:
+  %cmp = icmp ule i32 %n, 65536
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: urem i32 %n, 100
+  %div = urem i32 %n, 100
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test3(
+define void @test3(i32 %m, i32 %n) {
+entry:
+  %cmp1 = icmp ult i32 %m, 65535
+  %cmp2 = icmp ult i32 %n, 65535
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: urem i16
+  %div = urem i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test4(
+define void @test4(i32 %m, i32 %n) {
+entry:
+  %cmp1 = icmp ult i32 %m, 65535
+  %cmp2 = icmp ule i32 %n, 65536
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: urem i32 %m, %n
+  %div = urem i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test5
+define void @test5(i32 %n) {
+  %trunc = and i32 %n, 63
+  ; CHECK: urem i8
+  %div = urem i32 %trunc, 42
+  ret void
+}
+
+; CHECK-LABEL: @test6
+define void @test6(i32 %n) {
+entry:
+  %cmp = icmp ule i32 %n, 255
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: urem i8
+  %div = srem i32 %n, 100
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @non_power_of_2
+define void @non_power_of_2(i24 %n) {
+  %div = urem i24 %n, 42
+  ret void
+}