[InstCombine] Optimize always overflowing signed saturating add/sub

[nikic]

Summary

Based on the overflow direction information added in D62463, we can now fold always overflowing signed saturating add/sub to signed min/max.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2073–2074 ↗

(On Diff #201738)

Can you use APSInt::getMinValue(BitWidth, !SI->isSigned()) instead?

2079–2080 ↗

(On Diff #201738)

Same

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2073–2074 ↗

(On Diff #201738)

It works, but I'm wondering whether it's okay to use APSInt for this purpose. It looks like APSInt is used heavily by clang, but the only uses in the LLVM middle end are for interfacing with the convertToInteger() APFloat API.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2073–2074 ↗

(On Diff #201738)

If it's not ok to use it for this purpose then i, too, would like to know about that :)

[nikic]

Use APSInt to construct signed/unsigned min/max.

[craig.topper]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2074 ↗

(On Diff #201950)

What's really happening on this line? APSInt::getMinValue returns an APSInt object which is larger than an APInt object. Does this create an APSInt and then copy the APInt part of that out into a separate APInt? Or does the APInt portion get moved?

[lebedev.ri]

LGTM, thank you!
(There seems to be a lot of constant folds missing)

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2074 ↗

(On Diff #201950)

My C++ foo is pretty weak, so I stepped through this in gdb... It takes the APInt(APInt &&) move constructor.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2074 ↗

(On Diff #201950)

https://godbolt.org/z/kNAaNg

llvm/trunk/lib/Transforms/InstCombine/InstCombineCalls.cpp

 //===- InstCombineCalls.cpp -----------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the visitCall, visitInvoke, and visitCallBr functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InstCombineInternal.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APInt.h"
+#include "llvm/ADT/APSInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Analysis/AssumptionCache.h"
Instruction *InstCombiner::visitCallInst(CallInst &CI) {
   case Intrinsic::uadd_sat:
   case Intrinsic::sadd_sat:
     if (Instruction *I = canonicalizeConstantArg0ToArg1(CI))
       return I;
     LLVM_FALLTHROUGH;
   case Intrinsic::usub_sat:
   case Intrinsic::ssub_sat: {
     SaturatingInst *SI = cast<SaturatingInst>(II);
+    Type *Ty = SI->getType();
     Value *Arg0 = SI->getLHS();
     Value *Arg1 = SI->getRHS();
 
     // Make use of known overflow information.
     OverflowResult OR = computeOverflow(SI->getBinaryOp(), SI->isSigned(),
                                         Arg0, Arg1, SI);
     switch (OR) {
       case OverflowResult::MayOverflow:
         break;
       case OverflowResult::NeverOverflows:
         if (SI->isSigned())
           return BinaryOperator::CreateNSW(SI->getBinaryOp(), Arg0, Arg1);
         else
           return BinaryOperator::CreateNUW(SI->getBinaryOp(), Arg0, Arg1);
-      case OverflowResult::AlwaysOverflowsLow:
-        if (SI->isSigned()) break; // TODO: Support signed.
-        return replaceInstUsesWith(*SI,
-                                   ConstantInt::getNullValue(II->getType()));
-      case OverflowResult::AlwaysOverflowsHigh:
-        if (SI->isSigned()) break; // TODO: Support signed.
-        return replaceInstUsesWith(*SI,
-                                   ConstantInt::getAllOnesValue(II->getType()));
+      case OverflowResult::AlwaysOverflowsLow: {
+        unsigned BitWidth = Ty->getScalarSizeInBits();
+        APInt Min = APSInt::getMinValue(BitWidth, !SI->isSigned());
+        return replaceInstUsesWith(*SI, ConstantInt::get(Ty, Min));
+      }
+      case OverflowResult::AlwaysOverflowsHigh: {
+        unsigned BitWidth = Ty->getScalarSizeInBits();
+        APInt Max = APSInt::getMaxValue(BitWidth, !SI->isSigned());
+        return replaceInstUsesWith(*SI, ConstantInt::get(Ty, Max));
+      }
     }
 
     // ssub.sat(X, C) -> sadd.sat(X, -C) if C != MIN
     Constant *C;
     if (IID == Intrinsic::ssub_sat && match(Arg1, m_Constant(C)) &&
         C->isNotMinSignedValue()) {
       Value *NegVal = ConstantExpr::getNeg(C);
       return replaceInstUsesWith(

llvm/trunk/test/Transforms/InstCombine/saturating-add-sub.ll

 ;
   %a_neg = or <2 x i8> %a, <i8 -128, i8 -128>
   %r = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> %a_neg, <2 x i8> <i8 -10, i8 -20>)
   ret <2 x i8> %r
 }
 
 define i8 @test_scalar_sadd_always_overflows_low(i8 %a) {
 ; CHECK-LABEL: @test_scalar_sadd_always_overflows_low(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[A:%.*]], -120
-; CHECK-NEXT:    [[MIN:%.*]] = select i1 [[CMP]], i8 [[A]], i8 -120
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[MIN]], i8 -10)
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 -128
 ;
   %cmp = icmp slt i8 %a, -120
   %min = select i1 %cmp, i8 %a, i8 -120
   %r = call i8 @llvm.sadd.sat.i8(i8 %min, i8 -10)
   ret i8 %r
 }
 
 define i8 @test_scalar_sadd_always_overflows_high(i8 %a) {
 ; CHECK-LABEL: @test_scalar_sadd_always_overflows_high(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[A:%.*]], 120
-; CHECK-NEXT:    [[MAX:%.*]] = select i1 [[CMP]], i8 [[A]], i8 120
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[MAX]], i8 10)
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 127
 ;
   %cmp = icmp sgt i8 %a, 120
   %max = select i1 %cmp, i8 %a, i8 120
   %r = call i8 @llvm.sadd.sat.i8(i8 %max, i8 10)
   ret i8 %r
 }
 
 ; While this is a no-overflow condition, the nuw flag gets lost due to

 ;
   %a_neg = or <2 x i8> %a, <i8 -128, i8 -128>
   %r = call <2 x i8> @llvm.ssub.sat.v2i8(<2 x i8> %a_neg, <2 x i8> <i8 10, i8 20>)
   ret <2 x i8> %r
 }
 
 define i8 @test_scalar_ssub_always_overflows_low(i8 %a) {
 ; CHECK-LABEL: @test_scalar_ssub_always_overflows_low(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[A:%.*]], 120
-; CHECK-NEXT:    [[MAX:%.*]] = select i1 [[CMP]], i8 [[A]], i8 120
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.ssub.sat.i8(i8 -10, i8 [[MAX]])
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 -128
 ;
   %cmp = icmp sgt i8 %a, 120
   %max = select i1 %cmp, i8 %a, i8 120
   %r = call i8 @llvm.ssub.sat.i8(i8 -10, i8 %max)
   ret i8 %r
 }
 
 define i8 @test_scalar_ssub_always_overflows_high(i8 %a) {
 ; CHECK-LABEL: @test_scalar_ssub_always_overflows_high(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[A:%.*]], -120
-; CHECK-NEXT:    [[MIN:%.*]] = select i1 [[CMP]], i8 [[A]], i8 -120
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.ssub.sat.i8(i8 10, i8 [[MIN]])
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 127
 ;
   %cmp = icmp slt i8 %a, -120
   %min = select i1 %cmp, i8 %a, i8 -120
   %r = call i8 @llvm.ssub.sat.i8(i8 10, i8 %min)
   ret i8 %r
 }
 
 define i8 @test_scalar_usub_add_nuw_no_ov(i8 %a) {