InstCombine: Be more agressive optimizing 'udiv' instrs with 'select' denoms

Real world code sometimes has the denominator of a 'udiv' be a
'select'.  LLVM can handle such cases but only when the 'select'
operands are symmetric in structure (both select operands are a constant
power of two or a left shift, etc.).  This falls apart if we are dealt a
'udiv' where the code is not symetric or if the select operands lead us
to more select instructions.

Instead, we should treat the LHS and each select operand as a distinct
divide operation and try to optimize them independently.  If we can
to simplify each operation, then we can replace the 'udiv' with, say, a
'lshr' that has a new select with a bunch of new operands for the
select.

llvm-svn: 185257

1 files changed, 38 insertions, 0 deletions

diff --git a/llvm/test/Transforms/InstCombine/div-shift.ll b/llvm/test/Transforms/InstCombine/div-shift.ll
index e0372ebac18..46d0f9afd70 100644
--- a/llvm/test/Transforms/InstCombine/div-shift.ll
+++ b/llvm/test/Transforms/InstCombine/div-shift.ll
@@ -35,3 +35,41 @@ define i64 @t3(i64 %x, i32 %y) nounwind  {
   %3 = udiv i64 %x, %2
   ret i64 %3
 }
+
+define i32 @t4(i32 %x, i32 %y) nounwind {
+; CHECK: t4
+; CHECK-NOT: udiv
+; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 %y, 5
+; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i32 5, i32 %y
+; CHECK-NEXT: [[SHR:%.*]] = lshr i32 %x, [[SEL]]
+; CHECK-NEXT: ret i32 [[SHR]]
+  %1 = shl i32 1, %y
+  %2 = icmp ult i32 %1, 32
+  %3 = select i1 %2, i32 32, i32 %1
+  %4 = udiv i32 %x, %3
+  ret i32 %4
+}
+
+define i32 @t5(i1 %x, i1 %y, i32 %V) nounwind {
+; CHECK: t5
+; CHECK-NOT: udiv
+; CHECK-NEXT: [[SEL1:%.*]] = select i1 %x, i32 5, i32 6
+; CHECK-NEXT: [[SEL2:%.*]] = select i1 %y, i32 [[SEL1]], i32 %V
+; CHECK-NEXT: [[LSHR:%.*]] = lshr i32 %V, [[SEL2]]
+; CHECK-NEXT: ret i32 [[LSHR]]
+  %1 = shl i32 1, %V
+  %2 = select i1 %x, i32 32, i32 64
+  %3 = select i1 %y, i32 %2, i32 %1
+  %4 = udiv i32 %V, %3
+  ret i32 %4
+}
+
+define i32 @t6(i32 %x, i32 %z) nounwind{
+; CHECK: t6
+; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 %x, 0
+; CHECK-NOT: udiv i32 %z, %x
+  %x_is_zero = icmp eq i32 %x, 0
+  %divisor = select i1 %x_is_zero, i32 1, i32 %x
+  %y = udiv i32 %z, %divisor
+  ret i32 %y
+}