From 10faa1b2111896f8ad51a20364e897b33534f95a Mon Sep 17 00:00:00 2001
From: Nadav Rotem <nrotem@apple.com>
Date: Tue, 3 Mar 2015 21:39:02 +0000
Subject: [PATCH] Teach ComputeNumSignBits about signed divisions.

http://reviews.llvm.org/D8028
rdar://20023136



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@231140 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/ValueTracking.cpp            | 17 +++++++++++++++++
 test/Transforms/InstCombine/intrinsics.ll | 23 +++++++++++++++++++++++
 2 files changed, 40 insertions(+)

diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp
index 0458d284eb4..d5202664ae5 100644
--- a/lib/Analysis/ValueTracking.cpp
+++ b/lib/Analysis/ValueTracking.cpp
@@ -1723,6 +1723,23 @@ unsigned ComputeNumSignBits(Value *V, const DataLayout *TD,
     Tmp = TyBits - U->getOperand(0)->getType()->getScalarSizeInBits();
     return ComputeNumSignBits(U->getOperand(0), TD, Depth+1, Q) + Tmp;
 
+  case Instruction::SDiv:
+    const APInt *Denominator;
+    // sdiv X, C -> adds log(C) sign bits.
+    if (match(U->getOperand(1), m_APInt(Denominator))) {
+
+      // Ignore non-positive denominator.
+      if (!Denominator->isStrictlyPositive())
+        break;
+
+      // Calculate the incoming numerator bits.
+      unsigned NumBits = ComputeNumSignBits(U->getOperand(0), TD, Depth+1, Q);
+
+      // Add floor(log(C)) bits to the numerator bits.
+      return std::min(TyBits, NumBits + Denominator->logBase2());
+    }
+    break;
+
   case Instruction::AShr: {
     Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1, Q);
     // ashr X, C   -> adds C sign bits.  Vectors too.
diff --git a/test/Transforms/InstCombine/intrinsics.ll b/test/Transforms/InstCombine/intrinsics.ll
index 2791adf8feb..cfdda9405a8 100644
--- a/test/Transforms/InstCombine/intrinsics.ll
+++ b/test/Transforms/InstCombine/intrinsics.ll
@@ -363,3 +363,26 @@ define i32 @cttz_select(i32 %Value) nounwind {
 ; CHECK-NEXT: call i32 @llvm.cttz.i32(i32 %Value, i1 false)
 ; CHECK-NEXT: ret i32
 }
+
+; CHECK-LABEL: @overflow_div_add(
+; CHECK: ret i1 false
+define i1 @overflow_div_add(i32 %v1, i32 %v2) nounwind {
+entry:
+  %div = sdiv i32 %v1, 2
+  %t = call %ov.result.32 @llvm.sadd.with.overflow.i32(i32 %div, i32 1)
+  %obit = extractvalue %ov.result.32 %t, 1
+  ret i1 %obit
+}
+
+; CHECK-LABEL: @overflow_div_sub(
+; CHECK: ret i1 false
+define i1 @overflow_div_sub(i32 %v1, i32 %v2) nounwind {
+entry:
+  ; Check cases where the known sign bits are larger than the word size.
+  %a = ashr i32 %v1, 18
+  %div = sdiv i32 %a, 65536
+  %t = call %ov.result.32 @llvm.ssub.with.overflow.i32(i32 %div, i32 1)
+  %obit = extractvalue %ov.result.32 %t, 1
+  ret i1 %obit
+}
+
-- 
2.34.1