From e0cfecf47d466b5776371526c27969e07177b839 Mon Sep 17 00:00:00 2001
From: Nick Lewycky <nicholas@mxc.ca>
Date: Mon, 18 Feb 2008 22:48:05 +0000
Subject: [PATCH] Correctly fold divide-by-constant, even when faced with
 overflow.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47287 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../Scalar/InstructionCombining.cpp           | 29 +++++++++++++++++--
 .../InstCombine/2008-02-16-SDivOverflow.ll    | 14 +++++++++
 .../InstCombine/2008-02-16-SDivOverflow2.ll   |  9 ++++++
 3 files changed, 50 insertions(+), 2 deletions(-)
 create mode 100644 test/Transforms/InstCombine/2008-02-16-SDivOverflow.ll
 create mode 100644 test/Transforms/InstCombine/2008-02-16-SDivOverflow2.ll

diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp
index f89d1f2aeee..5582f511340 100644
--- a/lib/Transforms/Scalar/InstructionCombining.cpp
+++ b/lib/Transforms/Scalar/InstructionCombining.cpp
@@ -605,6 +605,28 @@ static ConstantInt *Subtract(ConstantInt *C1, ConstantInt *C2) {
 static ConstantInt *Multiply(ConstantInt *C1, ConstantInt *C2) {
   return ConstantInt::get(C1->getValue() * C2->getValue());
 }
+/// MultiplyOverflows - True if the multiply can not be expressed in an int
+/// this size.
+static bool MultiplyOverflows(ConstantInt *C1, ConstantInt *C2, bool sign) {
+  uint32_t W = C1->getBitWidth();
+  APInt LHSExt = C1->getValue(), RHSExt = C2->getValue();
+  if (sign) {
+    LHSExt.sext(W * 2);
+    RHSExt.sext(W * 2);
+  } else {
+    LHSExt.zext(W * 2);
+    RHSExt.zext(W * 2);
+  }
+
+  APInt MulExt = LHSExt * RHSExt;
+
+  if (sign) {
+    APInt Min = APInt::getSignedMinValue(W).sext(W * 2);
+    APInt Max = APInt::getSignedMaxValue(W).sext(W * 2);
+    return MulExt.slt(Min) || MulExt.sgt(Max);
+  } else 
+    return MulExt.ugt(APInt::getLowBitsSet(W * 2, W));
+}
 
 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
 /// known to be either zero or one and return them in the KnownZero/KnownOne
@@ -2632,8 +2654,11 @@ Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) {
     if (Instruction *LHS = dyn_cast<Instruction>(Op0))
       if (Instruction::BinaryOps(LHS->getOpcode()) == I.getOpcode())
         if (ConstantInt *LHSRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) {
-          return BinaryOperator::create(I.getOpcode(), LHS->getOperand(0),
-                                        Multiply(RHS, LHSRHS));
+          if (MultiplyOverflows(RHS, LHSRHS, I.getOpcode()==Instruction::SDiv))
+            return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
+          else 
+            return BinaryOperator::create(I.getOpcode(), LHS->getOperand(0),
+                                          Multiply(RHS, LHSRHS));
         }
 
     if (!RHS->isZero()) { // avoid X udiv 0
diff --git a/test/Transforms/InstCombine/2008-02-16-SDivOverflow.ll b/test/Transforms/InstCombine/2008-02-16-SDivOverflow.ll
new file mode 100644
index 00000000000..cd61a10c5b8
--- /dev/null
+++ b/test/Transforms/InstCombine/2008-02-16-SDivOverflow.ll
@@ -0,0 +1,14 @@
+; RUN: llvm-as < %s | opt -instcombine | llvm-dis | grep {ret i.* 0} | count 2
+; PR2048
+
+define i32 @i(i32 %a) {
+  %tmp1 = sdiv i32 %a, -1431655765
+  %tmp2 = sdiv i32 %tmp1, 3
+  ret i32 %tmp2
+}
+
+define i8 @j(i8 %a) {
+  %tmp1 = sdiv i8 %a, 64
+  %tmp2 = sdiv i8 %tmp1, 3
+  ret i8 %tmp2
+}
diff --git a/test/Transforms/InstCombine/2008-02-16-SDivOverflow2.ll b/test/Transforms/InstCombine/2008-02-16-SDivOverflow2.ll
new file mode 100644
index 00000000000..0e260c465e3
--- /dev/null
+++ b/test/Transforms/InstCombine/2008-02-16-SDivOverflow2.ll
@@ -0,0 +1,9 @@
+; RUN: llvm-as < %s | opt -instcombine | llvm-dis | grep {sdiv i8 \%a, 9}
+; PR2048
+
+define i8 @i(i8 %a) {
+  %tmp1 = sdiv i8 %a, -3
+  %tmp2 = sdiv i8 %tmp1, -3
+  ret i8 %tmp2
+}
+
-- 
2.34.1