Constant folding and instcombine for saturating subs

[nikic]

Summary

This is a continuation of D54237 for the subtraction case. The following simplifications / folds have been implemented:

• Constant folding sat(C1 - C2) -> C3
• sat(X - 0) -> X
• sat(X - X) -> 0
• sat(X - undef) -> 0
• sat(undef - X) -> 0
• sat(0 usub X) -> 0
• sat(X usub MAX) -> 0
• sat(sat(X - C1) - C2) -> sat(X + C3) where legal
• sat(X1 - X2) -> sub nuw/nsw where possible

I've also changed the computeOverflowForUnsignedSub() implementation to return AlwaysOverflows results, for parity with the computeOverflowForUnsignedAdd() implementation. The results were weirdly asymmetric previously.

[nikic]

Simplify sat(X - undef) -> X for symmetry with the add simplification.

[nikic]

Rebase over APInt patch, implement new undef folds with zero result.

[RKSimon]

Please can you add vector constant folding tests + support?

[RKSimon]

LGTM - happy for vector support to be added as a follow up patch

[nikic]

Abandoning in favor of the patch series listed in https://reviews.llvm.org/D54237#1298642.

lib/Analysis/ConstantFolding.cpp

bool llvm::canConstantFoldCallTo(ImmutableCallSite CS, const Function *F) {
   case Intrinsic::sadd_with_overflow:
   case Intrinsic::uadd_with_overflow:
   case Intrinsic::ssub_with_overflow:
   case Intrinsic::usub_with_overflow:
   case Intrinsic::smul_with_overflow:
   case Intrinsic::umul_with_overflow:
   case Intrinsic::sadd_sat:
   case Intrinsic::uadd_sat:
+  case Intrinsic::ssub_sat:
+  case Intrinsic::usub_sat:
   case Intrinsic::convert_from_fp16:
   case Intrinsic::convert_to_fp16:
   case Intrinsic::bitreverse:
   case Intrinsic::x86_sse_cvtss2si:
   case Intrinsic::x86_sse_cvtss2si64:
   case Intrinsic::x86_sse_cvttss2si:
   case Intrinsic::x86_sse_cvttss2si64:
   case Intrinsic::x86_sse2_cvtsd2si:
if (auto *Op1 = dyn_cast<ConstantInt>(Operands[0])) {
             ConstantInt::get(Type::getInt1Ty(Ty->getContext()), Overflow)
           };
           return ConstantStruct::get(cast<StructType>(Ty), Ops);
         }
         case Intrinsic::uadd_sat:
           return ConstantInt::get(Ty, Op1->getValue().uadd_sat(Op2->getValue()));
         case Intrinsic::sadd_sat:
           return ConstantInt::get(Ty, Op1->getValue().sadd_sat(Op2->getValue()));
+        case Intrinsic::usub_sat:
+          return ConstantInt::get(Ty, Op1->getValue().usub_sat(Op2->getValue()));
+        case Intrinsic::ssub_sat:
+          return ConstantInt::get(Ty, Op1->getValue().ssub_sat(Op2->getValue()));
         case Intrinsic::cttz:
           if (Op2->isOne() && Op1->isZero()) // cttz(0, 1) is undef.
             return UndefValue::get(Ty);
           return ConstantInt::get(Ty, Op1->getValue().countTrailingZeros());
         case Intrinsic::ctlz:
           if (Op2->isOne() && Op1->isZero()) // ctlz(0, 1) is undef.
             return UndefValue::get(Ty);
           return ConstantInt::get(Ty, Op1->getValue().countLeadingZeros());

lib/Analysis/InstructionSimplify.cpp

static Value *simplifyBinaryIntrinsic(Function *F, Value *Op0, Value *Op1,
   case Intrinsic::sadd_sat:
     // X + 0 -> X, X + undef -> X
     if (match(Op1, m_Zero()) || match(Op1, m_Undef()))
       return Op0;
     // 0 + X -> X, undef + X -> X
     if (match(Op0, m_Zero()) || match(Op0, m_Undef()))
       return Op1;
     break;
+  case Intrinsic::usub_sat:
+    // sat(0 - X) -> 0, sat(X - MAX) -> 0
+    if (match(Op0, m_Zero()) || match(Op1, m_AllOnes()))
+      return Constant::getNullValue(ReturnType);
+    LLVM_FALLTHROUGH;
+  case Intrinsic::ssub_sat:
+    // X - X -> 0, X - undef -> 0, undef - X -> 0
+    if (Op0 == Op1 || match(Op0, m_Undef()) || match(Op1, m_Undef()))
+      return Constant::getNullValue(ReturnType);
+    // X - 0 -> X
+    if (match(Op1, m_Zero()))
+      return Op0;
+    break;
   case Intrinsic::load_relative:
     if (auto *C0 = dyn_cast<Constant>(Op0))
       if (auto *C1 = dyn_cast<Constant>(Op1))
         return SimplifyRelativeLoad(C0, C1, Q.DL);
     break;
   case Intrinsic::powi:
     if (auto *Power = dyn_cast<ConstantInt>(Op1)) {
       // powi(x, 0) -> 1.0

lib/Analysis/ValueTracking.cpp

OverflowResult llvm::computeOverflowForUnsignedAdd(
   KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT,
                                         nullptr, UseInstrInfo);
   if (LHSKnown.isNonNegative() || LHSKnown.isNegative()) {
     KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT,
                                           nullptr, UseInstrInfo);
 
     if (LHSKnown.isNegative() && RHSKnown.isNegative()) {
       // The sign bit is set in both cases: this MUST overflow.
-      // Create a simple add instruction, and insert it into the struct.
       return OverflowResult::AlwaysOverflows;
     }
 
     if (LHSKnown.isNonNegative() && RHSKnown.isNonNegative()) {
       // The sign bit is clear in both cases: this CANNOT overflow.
-      // Create a simple add instruction, and insert it into the struct.
       return OverflowResult::NeverOverflows;
     }
   }
 
   return OverflowResult::MayOverflow;
 }
 
 /// Return true if we can prove that adding the two values of the

 }
 
 OverflowResult llvm::computeOverflowForUnsignedSub(const Value *LHS,
                                                    const Value *RHS,
                                                    const DataLayout &DL,
                                                    AssumptionCache *AC,
                                                    const Instruction *CxtI,
                                                    const DominatorTree *DT) {
-  // If the LHS is negative and the RHS is non-negative, no unsigned wrap.
   KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT);
+  if (LHSKnown.isNonNegative() || LHSKnown.isNegative()) {
     KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT);
+
+    // If the LHS is negative and the RHS is non-negative, no unsigned wrap.
     if (LHSKnown.isNegative() && RHSKnown.isNonNegative())
       return OverflowResult::NeverOverflows;
 
+    // If the LHS is non-negative and the RHS negative, we always wrap.
+    if (LHSKnown.isNonNegative() && RHSKnown.isNegative())
+      return OverflowResult::AlwaysOverflows;
+  }
+
   return OverflowResult::MayOverflow;
 }
 
 OverflowResult llvm::computeOverflowForSignedSub(const Value *LHS,
                                                  const Value *RHS,
                                                  const DataLayout &DL,
                                                  AssumptionCache *AC,
                                                  const Instruction *CxtI,

lib/Transforms/InstCombine/InstCombineCalls.cpp

case Intrinsic::ssub_with_overflow: {
     if (OptimizeOverflowCheck(OCF, II->getArgOperand(0), II->getArgOperand(1),
                               *II, OperationResult, OverflowResult))
       return CreateOverflowTuple(II, OperationResult, OverflowResult);
 
     break;
   }
 
   case Intrinsic::uadd_sat:
-  case Intrinsic::sadd_sat: {
-    Value *Arg0 = II->getArgOperand(0);
-    Value *Arg1 = II->getArgOperand(1);
-    if (isa<Constant>(Arg0) && !isa<Constant>(Arg1)) {
+  case Intrinsic::sadd_sat:
+    if (isa<Constant>(II->getArgOperand(0)) &&
+        !isa<Constant>(II->getArgOperand(1))) {
       // Canonicalize constants into the RHS.
-      II->setArgOperand(0, Arg1);
-      II->setArgOperand(1, Arg0);
+      Value *LHS = II->getArgOperand(0);
+      II->setArgOperand(0, II->getArgOperand(1));
+      II->setArgOperand(1, LHS);
       return II;
     }
+    LLVM_FALLTHROUGH;
+  case Intrinsic::usub_sat:
+  case Intrinsic::ssub_sat: {
+    Value *Arg0 = II->getArgOperand(0);
+    Value *Arg1 = II->getArgOperand(1);
+    Intrinsic::ID IID = II->getIntrinsicID();
 
     // Make use of known overflow information.
-    bool IsUnsigned = II->getIntrinsicID() == Intrinsic::uadd_sat;
-    if (IsUnsigned) {
-      OverflowResult OR = computeOverflowForUnsignedAdd(Arg0, Arg1, II);
+    OverflowResult OR;
+    switch (IID) {
+      default: llvm_unreachable("Unexpected intrinsic!");
+      case Intrinsic::uadd_sat:
+        OR = computeOverflowForUnsignedAdd(Arg0, Arg1, II);
         if (OR == OverflowResult::NeverOverflows)
           return replaceInstUsesWith(*II, Builder.CreateNUWAdd(Arg0, Arg1));
-
         if (OR == OverflowResult::AlwaysOverflows)
           return replaceInstUsesWith(*II,
               ConstantInt::getAllOnesValue(II->getType()));
-    } else {
+        break;
+      case Intrinsic::usub_sat:
+        OR = computeOverflowForUnsignedSub(Arg0, Arg1, II);
+        if (OR == OverflowResult::NeverOverflows)
+          return replaceInstUsesWith(*II, Builder.CreateNUWSub(Arg0, Arg1));
+        if (OR == OverflowResult::AlwaysOverflows)
+          return replaceInstUsesWith(*II,
+              ConstantInt::getNullValue(II->getType()));
+        break;
+      case Intrinsic::sadd_sat:
         if (willNotOverflowSignedAdd(Arg0, Arg1, *II))
           return replaceInstUsesWith(*II, Builder.CreateNSWAdd(Arg0, Arg1));
+        break;
+      case Intrinsic::ssub_sat:
+        if (willNotOverflowSignedSub(Arg0, Arg1, *II))
+          return replaceInstUsesWith(*II, Builder.CreateNSWSub(Arg0, Arg1));
+        break;
     }
 
     // sat(sat(X + Val2) + Val) -> sat(X + (Val+Val2))
+    // sat(sat(X - Val2) - Val) -> sat(X - (Val+Val2))
     // if Val and Val2 have the same sign
     if (auto *Other = dyn_cast<IntrinsicInst>(Arg0)) {
       Value *X;
       const APInt *Val, *Val2;
       APInt NewVal;
+      bool IsUnsigned = IID == Intrinsic::uadd_sat
+                     || IID == Intrinsic::usub_sat;
       if (Other->getIntrinsicID() == II->getIntrinsicID() &&
           match(Arg1, m_APInt(Val)) &&
           match(Other->getArgOperand(0), m_Value(X)) &&
           match(Other->getArgOperand(1), m_APInt(Val2))) {
         if (IsUnsigned)
           NewVal = Val->uadd_sat(*Val2);
         else if (Val->isNonNegative() == Val2->isNonNegative()) {
           bool Overflow;

test/Transforms/InstCombine/saturating-sub.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+declare void @dummy(i8)
+declare i8 @llvm.usub.sat.i8(i8, i8)
+declare i8 @llvm.ssub.sat.i8(i8, i8)
+
+; Simple constant folding
+define void @test1() {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:    call void @dummy(i8 10)
+; CHECK-NEXT:    call void @dummy(i8 0)
+; CHECK-NEXT:    call void @dummy(i8 -30)
+; CHECK-NEXT:    call void @dummy(i8 127)
+; CHECK-NEXT:    call void @dummy(i8 -128)
+; CHECK-NEXT:    ret void
+;
+  %x1 = call i8 @llvm.usub.sat.i8(i8 20, i8 10)
+  call void @dummy(i8 %x1)
+  %x2 = call i8 @llvm.usub.sat.i8(i8 200, i8 250)
+  call void @dummy(i8 %x2)
+
+  %y1 = call i8 @llvm.ssub.sat.i8(i8 -10, i8 20)
+  call void @dummy(i8 %y1)
+  %y2 = call i8 @llvm.ssub.sat.i8(i8 120, i8 -10)
+  call void @dummy(i8 %y2)
+  %y3 = call i8 @llvm.ssub.sat.i8(i8 -120, i8 10)
+  call void @dummy(i8 %y3)
+
+  ret void
+}
+
+; Zero, max and undef folding
+define void @test2(i8 %a) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:    call void @dummy(i8 [[A:%.*]])
+; CHECK-NEXT:    call void @dummy(i8 0)
+; CHECK-NEXT:    call void @dummy(i8 0)
+; CHECK-NEXT:    call void @dummy(i8 0)
+; CHECK-NEXT:    call void @dummy(i8 0)
+; CHECK-NEXT:    call void @dummy(i8 0)
+; CHECK-NEXT:    call void @dummy(i8 [[A]])
+; CHECK-NEXT:    [[Y2:%.*]] = call i8 @llvm.ssub.sat.i8(i8 0, i8 [[A]])
+; CHECK-NEXT:    call void @dummy(i8 [[Y2]])
+; CHECK-NEXT:    [[Y3:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A]], i8 -1)
+; CHECK-NEXT:    call void @dummy(i8 [[Y3]])
+; CHECK-NEXT:    call void @dummy(i8 0)
+; CHECK-NEXT:    call void @dummy(i8 0)
+; CHECK-NEXT:    call void @dummy(i8 0)
+; CHECK-NEXT:    ret void
+;
+  %x1 = call i8 @llvm.usub.sat.i8(i8 %a, i8 0)
+  call void @dummy(i8 %x1)
+  %x2 = call i8 @llvm.usub.sat.i8(i8 0, i8 %a)
+  call void @dummy(i8 %x2)
+  %x3 = call i8 @llvm.usub.sat.i8(i8 %a, i8 255)
+  call void @dummy(i8 %x3)
+  %x4 = call i8 @llvm.usub.sat.i8(i8 %a, i8 undef)
+  call void @dummy(i8 %x4)
+  %x5 = call i8 @llvm.usub.sat.i8(i8 undef, i8 %a)
+  call void @dummy(i8 %x5)
+  %x6 = call i8 @llvm.usub.sat.i8(i8 %a, i8 %a)
+  call void @dummy(i8 %x6)
+
+  %y1 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 0)
+  call void @dummy(i8 %y1)
+  %y2 = call i8 @llvm.ssub.sat.i8(i8 0, i8 %a)
+  call void @dummy(i8 %y2)
+  %y3 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 255)
+  call void @dummy(i8 %y3)
+  %y4 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 undef)
+  call void @dummy(i8 %y4)
+  %y5 = call i8 @llvm.ssub.sat.i8(i8 undef, i8 %a)
+  call void @dummy(i8 %y5)
+  %y6 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 %a)
+  call void @dummy(i8 %y6)
+
+  ret void
+}
+
+; Folding of two saturating subs
+define void @test3(i8 %a) {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[A:%.*]], i8 30)
+; CHECK-NEXT:    call void @dummy(i8 [[TMP1]])
+; CHECK-NEXT:    call void @dummy(i8 0)
+; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A]], i8 30)
+; CHECK-NEXT:    call void @dummy(i8 [[TMP2]])
+; CHECK-NEXT:    [[TMP3:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A]], i8 -30)
+; CHECK-NEXT:    call void @dummy(i8 [[TMP3]])
+; CHECK-NEXT:    [[V1:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A]], i8 10)
+; CHECK-NEXT:    [[V2:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[V1]], i8 -20)
+; CHECK-NEXT:    call void @dummy(i8 [[V2]])
+; CHECK-NEXT:    [[W1:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A]], i8 100)
+; CHECK-NEXT:    [[W2:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[W1]], i8 100)
+; CHECK-NEXT:    call void @dummy(i8 [[W2]])
+; CHECK-NEXT:    ret void
+;
+  %x1 = call i8 @llvm.usub.sat.i8(i8 %a, i8 10)
+  %x2 = call i8 @llvm.usub.sat.i8(i8 %x1, i8 20)
+  call void @dummy(i8 %x2)
+
+  %y1 = call i8 @llvm.usub.sat.i8(i8 %a, i8 100)
+  %y2 = call i8 @llvm.usub.sat.i8(i8 %y1, i8 200)
+  call void @dummy(i8 %y2)
+
+  %z1 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 10)
+  %z2 = call i8 @llvm.ssub.sat.i8(i8 %z1, i8 20)
+  call void @dummy(i8 %z2)
+
+  %u1 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 -10)
+  %u2 = call i8 @llvm.ssub.sat.i8(i8 %u1, i8 -20)
+  call void @dummy(i8 %u2)
+
+  %v1 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 10)
+  %v2 = call i8 @llvm.ssub.sat.i8(i8 %v1, i8 -20)
+  call void @dummy(i8 %v2)
+
+  %w1 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 100)
+  %w2 = call i8 @llvm.ssub.sat.i8(i8 %w1, i8 100)
+  call void @dummy(i8 %w2)
+
+  ret void
+}
+
+; Use of known overflow/no-overflow information
+define void @test4(i8 %a) {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:    [[A_NEG:%.*]] = or i8 [[A:%.*]], -128
+; CHECK-NEXT:    [[A_NNEG:%.*]] = and i8 [[A]], 127
+; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[A_NEG]], -10
+; CHECK-NEXT:    call void @dummy(i8 [[TMP1]])
+; CHECK-NEXT:    call void @dummy(i8 0)
+; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i8 [[A_NEG]], 10
+; CHECK-NEXT:    call void @dummy(i8 [[TMP2]])
+; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i8 [[A_NNEG]], -10
+; CHECK-NEXT:    call void @dummy(i8 [[TMP3]])
+; CHECK-NEXT:    [[Y3:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A_NEG]], i8 10)
+; CHECK-NEXT:    call void @dummy(i8 [[Y3]])
+; CHECK-NEXT:    [[Y4:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A_NNEG]], i8 -10)
+; CHECK-NEXT:    call void @dummy(i8 [[Y4]])
+; CHECK-NEXT:    ret void
+;
+  %a_neg = or i8 %a, -128
+  %a_nneg = and i8 %a, 127
+
+  %x1 = call i8 @llvm.usub.sat.i8(i8 %a_neg, i8 10)
+  call void @dummy(i8 %x1)
+
+  %x2 = call i8 @llvm.usub.sat.i8(i8 %a_nneg, i8 -10)
+  call void @dummy(i8 %x2)
+
+  %y1 = call i8 @llvm.ssub.sat.i8(i8 %a_neg, i8 -10)
+  call void @dummy(i8 %y1)
+
+  %y2 = call i8 @llvm.ssub.sat.i8(i8 %a_nneg, i8 10)
+  call void @dummy(i8 %y2)
+
+  %y3 = call i8 @llvm.ssub.sat.i8(i8 %a_neg, i8 10)
+  call void @dummy(i8 %y3)
+
+  %y4 = call i8 @llvm.ssub.sat.i8(i8 %a_nneg, i8 -10)
+  call void @dummy(i8 %y4)
+
+  ret void
+}