Add an InstCombine transform to recognize instances of manual overflow-safe addition

(performing the addition in a wider type and explicitly checking for overflow), and
fold them down to intrinsics.  This currently only supports signed-addition, but could
be generalized if someone works out the magic constant formulas for other operations.

Fixes <rdar://problem/8558713>.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121905 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 92 insertions, 0 deletions

diff --git a/lib/Transforms/InstCombine/InstCombineCompares.cpp b/lib/Transforms/InstCombine/InstCombineCompares.cpp
index d2841af8bc..0e711a1949 100644
--- a/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ b/lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -1657,6 +1657,71 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
     Value *A = 0, *B = 0;
     
+    // Match the following pattern, which is a common idiom when writing
+    // overflow-safe integer arithmetic function.  The source performs an
+    // addition in wider type, and explicitly checks for overflow using
+    // comparisons against INT_MIN and INT_MAX.  Simplify this by using the
+    // sadd_with_overflow intrinsic.
+    // FIXME: This could probably be generalized to handle other overflow-safe
+    // operations if we worked out the formulas to compute the appropriate 
+    // magic constants.
+    // 
+    // INT64 : a, b, sum = a + b
+    // if sum < INT32_MIN || sum > INT_MAX then
+    //   ...
+    // else
+    //   ...
+    {
+    ConstantInt *CI2;
+    
+    // I = icmp ugt (add (add A B) CI2) CI
+    if (I.getPredicate() == ICmpInst::ICMP_UGT &&
+        match(Op0, m_Add(m_Add(m_Value(A), m_Value(B)),
+                   m_ConstantInt(CI2)))) {
+      const IntegerType *WideType = cast<IntegerType>(CI->getType());
+      unsigned WideWidth = WideType->getBitWidth();
+      unsigned NarrowWidth = WideWidth / 2;
+      const IntegerType *NarrowType =
+        IntegerType::get(CI->getContext(), NarrowWidth);
+      
+      // NarrowAllOnes and NarrowSignBit are the magic constants used to
+      // perform an overflow check in the wider type: 0x00..00FF..FF and
+      // 0x00..0010..00 respectively, where the highest set bit in each is
+      // what would be the sign bit in the narrower type.
+      ConstantInt *NarrowAllOnes = cast<ConstantInt>(ConstantInt::get(WideType,
+        APInt::getAllOnesValue(NarrowWidth).zext(WideWidth)));
+      APInt SignBit(WideWidth, 0);
+      SignBit.setBit(NarrowWidth-1);
+      ConstantInt *NarrowSignBit =
+       cast<ConstantInt>(ConstantInt::get(WideType, SignBit));
+      
+      if (CI == NarrowAllOnes && CI2 == NarrowSignBit) {
+        Module *M = I.getParent()->getParent()->getParent();
+        
+        const Type *IntrinsicType = NarrowType;
+        Value *F = Intrinsic::getDeclaration(M, Intrinsic::sadd_with_overflow,
+          &IntrinsicType, 1);
+        
+        // If the pattern matches, truncate the inputs to the narrower type and
+        // use the sadd_with_overflow intrinsic to efficiently compute both the
+        // result and the overflow bit.
+        Value *TruncA = Builder->CreateTrunc(A, NarrowType, A->getName());
+        Value *TruncB = Builder->CreateTrunc(B, NarrowType, B->getName());
+        CallInst *Call = Builder->CreateCall2(F, TruncA, TruncB);
+        Value *Add = Builder->CreateExtractValue(Call, 0);
+        Value *ZExt = Builder->CreateZExt(Add, WideType);
+        
+        // The inner add was the result of the narrow add, zero extended to the
+        // wider type.  Replace it with the result computed by the intrinsic.
+        Instruction *OrigAdd =
+          cast<Instruction>(cast<Instruction>(I.getOperand(0))->getOperand(0));
+        OrigAdd->replaceAllUsesWith(ZExt);
+        
+        return ExtractValueInst::Create(Call, 1);
+      }
+    }
+    }
+    
     // (icmp ne/eq (sub A B) 0) -> (icmp ne/eq A, B)
     if (I.isEquality() && CI->isZero() &&
         match(Op0, m_Sub(m_Value(A), m_Value(B)))) {
diff --git a/test/Transforms/InstCombine/overflow.ll b/test/Transforms/InstCombine/overflow.ll
new file mode 100644
index 0000000000..f3f8ca3d61
--- /dev/null
+++ b/test/Transforms/InstCombine/overflow.ll
@@ -0,0 +1,27 @@
+; RUN: opt -S -instcombine < %s | FileCheck %s
+; <rdar://problem/8558713>
+
+; CHECK: @test1
+define i32 @test1(i32 %a, i32 %b) nounwind ssp {
+entry:
+; CHECK-NOT: sext
+  %conv = sext i32 %a to i64
+  %conv2 = sext i32 %b to i64
+  %add = add nsw i64 %conv2, %conv
+  %add.off = add i64 %add, 2147483648
+; CHECK: llvm.sadd.with.overflow
+  %0 = icmp ugt i64 %add.off, 4294967295
+  br i1 %0, label %if.then, label %if.end
+
+if.then:
+  %call = tail call i32 (...)* @throwAnExceptionOrWhatever() nounwind
+  br label %if.end
+
+if.end:
+; CHECK-NOT: trunc
+  %conv9 = trunc i64 %add to i32
+; CHECK: ret i32
+  ret i32 %conv9
+}
+
+declare i32 @throwAnExceptionOrWhatever(...)