From 1add46ddfa38f23669cb02de342fdb59a8709245 Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Sun, 22 May 2011 18:18:41 +0000
Subject: [PATCH] Carve out a place in instcombine to put transformations which
 work knowing that their result is non-zero.  Implement an example
 optimization (PR9814), which allows us to transform:   A / ((1 << B) >>u 2)
 into:   A >>u (B-2)

which we compile into:

_divu3:                                 ## @divu3
	leal	-2(%rsi), %ecx
	shrl	%cl, %edi
	movl	%edi, %eax
	ret

instead of:

_divu3:                                 ## @divu3
	movb	%sil, %cl
	movl	$1, %esi
	shll	%cl, %esi
	shrl	$2, %esi
	movl	%edi, %eax
	xorl	%edx, %edx
	divl	%esi, %eax
	ret



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131860 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../InstCombine/InstCombineMulDivRem.cpp      | 37 +++++++++++++++++++
 test/Transforms/InstCombine/div.ll            | 14 +++++++
 2 files changed, 51 insertions(+)

diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
index c4dee6a6f00..c96741aacd2 100644
--- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
+++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
@@ -19,6 +19,31 @@
 using namespace llvm;
 using namespace PatternMatch;
 
+
+/// simplifyValueKnownNonZero - The specific integer value is used in a context
+/// where it is known to be non-zero.  If this allows us to simplify the
+/// computation, do so and return the new operand, otherwise return null.
+static Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC) {
+  // If V has multiple uses, then we would have to do more analysis to determine
+  // if this is safe.  For example, the use could be in dynamically unreached
+  // code.
+  if (!V->hasOneUse()) return 0;
+  
+  // ((1 << A) >>u B) --> (1 << (A-B))
+  // Because V cannot be zero, we know that B is less than A.
+  Value *A = 0, *B = 0; ConstantInt *One = 0;
+  if (match(V, m_LShr(m_OneUse(m_Shl(m_ConstantInt(One), m_Value(A))),
+                      m_Value(B))) &&
+      // The "1" can be any value known to be a power of 2.
+      One->getValue().isPowerOf2()) {
+    A = IC.Builder->CreateSub(A, B, "tmp");
+    return IC.Builder->CreateShl(One, A);
+  }
+  
+  return 0;
+}
+
+
 /// MultiplyOverflows - True if the multiply can not be expressed in an int
 /// this size.
 static bool MultiplyOverflows(ConstantInt *C1, ConstantInt *C2, bool sign) {
@@ -293,6 +318,12 @@ bool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) {
 Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
+  // The RHS is known non-zero.
+  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) {
+    I.setOperand(1, V);
+    return &I;
+  }
+  
   // Handle cases involving: [su]div X, (select Cond, Y, Z)
   // This does not apply for fdiv.
   if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
@@ -499,6 +530,12 @@ Instruction *InstCombiner::visitFDiv(BinaryOperator &I) {
 Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
+  // The RHS is known non-zero.
+  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) {
+    I.setOperand(1, V);
+    return &I;
+  }
+
   // Handle cases involving: rem X, (select Cond, Y, Z)
   if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
     return &I;
diff --git a/test/Transforms/InstCombine/div.ll b/test/Transforms/InstCombine/div.ll
index 2e24f19dce4..8a0897b972d 100644
--- a/test/Transforms/InstCombine/div.ll
+++ b/test/Transforms/InstCombine/div.ll
@@ -118,3 +118,17 @@ define i32 @test14(i8 %x) nounwind {
 ; CHECK: @test14
 ; CHECK-NEXT: ret i32 0
 }
+
+; PR9814
+define i32 @test15(i32 %a, i32 %b) nounwind {
+  %shl = shl i32 1, %b
+  %div = lshr i32 %shl, 2
+  %div2 = udiv i32 %a, %div
+  ret i32 %div2
+; CHECK: @test15
+; CHECK-NEXT: add i32 %b, -2
+; CHECK-NEXT: lshr i32 %a, 
+; CHECK-NEXT: ret i32
+}
+
+
-- 
2.34.1