[InstSimplify] Simplify saturating add/sub + icmp

[nikic]

Summary

If a saturating add/sub has one constant operand, then we can determine the possible range of outputs it can produce, and simplify an icmp comparison based on that.

I'm implementing this in InstSimplify, with a similar approach to already existing code for binary operators. I previously started out by adding support for this to ConstantRange, which would be able to handle more general cases, but I couldn't figure out which pass would be responsible for the actual simplification.

Ref: https://github.com/rust-lang/rust/issues/44500

[spatel]

The more general transforms (changing the icmp predicate and/or constant operand of the icmp) should be handled under InstCombiner::visitICmpInst().
This is a cheap analysis, so it's probably best to have this part in InstSimplify regardless of what we add to InstCombine.

The logic looks good, but see inline for an improvement related to canonical form.

lib/Analysis/InstructionSimplify.cpp

2668–2669

Assuming canonical IR isn't a valid assumption for InstSimplify because InstSimplify is used as an analysis independently of InstCombine. Even when InstSimplify is called from within InstCombine, it would theoretically be more efficient to handle non-canonical simplifications before doing other transforms in InstCombine.

Do we "internally canonicalize" a constant operand for uadd/sadd to operand 1 here in InstSimplify? If not, we might want to do that too. Also if the existing code for binops doesn't do that, it's probably worth a TODO comment.

In all cases, it's worth varying at least some of the regression tests to prove that we have those non-canonical patterns covered.

[nikic]

Add handling for intrinsics in non-canonical form.

[nikic]

lib/Analysis/InstructionSimplify.cpp

2668–2669

I've implemented handling for the non-canonical forms. Regarding doing canonicalization in InstSimplify, I think it only does this if the simplify operation itself takes the instruction in unpacked form (such as SimplifyBinOp which has Opcode+LHS+RHS), not when working on explicit instructions. I'm assuming that swapping operands of actual instruction is not allowed inside InstSimplify.

[spatel]

lib/Analysis/InstructionSimplify.cpp

2681–2682

What happens if C is the signed min value here?

define i1 @ssub_icmp_op1_is_min_val(i8 %a) {
  %b = call i8 @llvm.ssub.sat.i8(i8 %a, i8 -128)
  %c = icmp sle i8 %b, -118
  ret i1 %c
}

[nikic]

lib/Analysis/InstructionSimplify.cpp

2681–2682

This will fold to ret i1 false. The computed range here is [0, SINT_MAX]. The last test is intended to check this case.

[spatel]

LGTM

lib/Analysis/InstructionSimplify.cpp

2681–2682

Ah, sorry I missed that test.

It's not obvious to me that the result of:

%b = call i8 @llvm.ssub.sat.i8(i8 0, i8 -128)

is "127".

Is that worth noting here or in the LangRef?

[nikic]

lib/Analysis/InstructionSimplify.cpp

2681–2682

If the semantics aren't clear, it would be good to clarify in LangRef. However, right now I'm not sure I understand where the ambiguity lies. What result would you expect for this operation?

[spatel]

lib/Analysis/InstructionSimplify.cpp

2681–2682

It's probably ok to disregard me on this; I don't have much experience actually using saturating math.
I was imagining that (0 ssub -128) could be interpreted as (0 sadd -(-128)) and the negation of the signed min val just returns the signed min val again...but that wouldn't be very useful, and if all hardware agrees that the result is calculated as shown here, then it's fine.

lib/Analysis/InstructionSimplify.cpp

if (match(BO.getOperand(1), m_APInt(C)))
       Upper = *C;
     break;
 
   default:
     break;
   }
 }
 
+/// Some intrinsics with a constant operand have an easy-to-compute range of
+/// outputs. This can be used to fold a comparison to always true or always
+/// false.
+static void setLimitsForIntrinsic(IntrinsicInst &II, APInt &Lower,
+                                  APInt &Upper) {
+  unsigned Width = Lower.getBitWidth();
+  const APInt *C;
+  switch (II.getIntrinsicID()) {
+  case Intrinsic::uadd_sat:
+    // uadd.sat(x, C) produces [C, UINT_MAX].
+    if (match(II.getOperand(1), m_APInt(C)))
+      Lower = *C;
+    break;
+  case Intrinsic::sadd_sat:
+    if (match(II.getOperand(1), m_APInt(C))) {
+      if (C->isNegative()) {
+        // sadd.sat(x, -C) produces [SINT_MIN, SINT_MAX - C].
+        Lower = APInt::getSignedMinValue(Width);
+        Upper = APInt::getSignedMaxValue(Width) + *C + 1;
+      } else {
+        // sadd.sat(x, +C) produces [SINT_MIN + C, SINT_MAX].
+        Lower = APInt::getSignedMinValue(Width) + *C;
+        Upper = APInt::getSignedMaxValue(Width) + 1;
+      }
+    }
+    break;
+  case Intrinsic::usub_sat:
+    // usub.sat(x, C) produces [0, UINT_MAX - C].
+    if (match(II.getOperand(1), m_APInt(C)))
+      Upper = APInt::getMaxValue(Width) - *C + 1;
+    // usub.sat(C, x) produces [0, C].
+    else if (match(II.getOperand(0), m_APInt(C)))
+      Upper = *C + 1;
+    break;
+  case Intrinsic::ssub_sat:
+    // ssub.sat(x, C) is canonicalized to sadd.sat(x, -C) by instcombine, so
+    // no need to check for it here.
+    if (match(II.getOperand(0), m_APInt(C))) {
+      if (C->isNegative()) {
+        // ssub.sat(-C, x) produces [SINT_MIN, -SINT_MIN - C].
+        Lower = APInt::getSignedMinValue(Width);
+        Upper = *C - APInt::getSignedMinValue(Width) + 1;
+      } else {
+        // ssub.sat(+C, x) produces [-SINT_MAX + C, SINT_MAX].
+        Lower = *C - APInt::getSignedMaxValue(Width);
+        Upper = APInt::getSignedMaxValue(Width) + 1;
+      }
+    }
+  default:
+    break;
+  }
+}
+
 static Value *simplifyICmpWithConstant(CmpInst::Predicate Pred, Value *LHS,
                                        Value *RHS, const InstrInfoQuery &IIQ) {
   Type *ITy = GetCompareTy(RHS); // The return type.
 
   Value *X;
   // Sign-bit checks can be optimized to true/false after unsigned
   // floating-point casts:
   // icmp slt (bitcast (uitofp X)),  0 --> false
if (RHS_CR.isFullSet())
     return ConstantInt::getTrue(ITy);
 
   // Find the range of possible values for binary operators.
   unsigned Width = C->getBitWidth();
   APInt Lower = APInt(Width, 0);
   APInt Upper = APInt(Width, 0);
   if (auto *BO = dyn_cast<BinaryOperator>(LHS))
     setLimitsForBinOp(*BO, Lower, Upper, IIQ);
+  else if (auto *II = dyn_cast<IntrinsicInst>(LHS))
+    setLimitsForIntrinsic(*II, Lower, Upper);
 
   ConstantRange LHS_CR =
       Lower != Upper ? ConstantRange(Lower, Upper) : ConstantRange(Width, true);
 
   if (auto *I = dyn_cast<Instruction>(LHS))
     if (auto *Ranges = IIQ.getMetadata(I, LLVMContext::MD_range))
       LHS_CR = LHS_CR.intersectWith(getConstantRangeFromMetadata(*Ranges));
 

test/Transforms/InstSimplify/saturating-add-sub.ll

 ; CHECK-NEXT:    ret <2 x i8> zeroinitializer
 ;
   %y6v = call <2 x i8> @llvm.ssub.sat.v2i8(<2 x i8> %a, <2 x i8> %a)
   ret <2 x i8> %y6v
 }
 
 define i1 @uadd_icmp_known(i8 %a) {
 ; CHECK-LABEL: @uadd_icmp_known(
-; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.uadd.sat.i8(i8 [[A:%.*]], i8 10)
-; CHECK-NEXT:    [[C:%.*]] = icmp uge i8 [[B]], 10
-; CHECK-NEXT:    ret i1 [[C]]
+; CHECK-NEXT:    ret i1 true
 ;
   %b = call i8 @llvm.uadd.sat.i8(i8 %a, i8 10)
   %c = icmp uge i8 %b, 10
   ret i1 %c
 }
 
 define i1 @uadd_icmp_unknown(i8 %a) {
 ; CHECK-LABEL: @uadd_icmp_unknown(
 ; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.uadd.sat.i8(i8 [[A:%.*]], i8 10)
 ; CHECK-NEXT:    [[C:%.*]] = icmp ugt i8 [[B]], 10
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %b = call i8 @llvm.uadd.sat.i8(i8 %a, i8 10)
   %c = icmp ugt i8 %b, 10
   ret i1 %c
 }
 
 define i1 @sadd_icmp_pos_known(i8 %a) {
 ; CHECK-LABEL: @sadd_icmp_pos_known(
-; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[A:%.*]], i8 10)
-; CHECK-NEXT:    [[C:%.*]] = icmp sge i8 [[B]], -118
-; CHECK-NEXT:    ret i1 [[C]]
+; CHECK-NEXT:    ret i1 true
 ;
   %b = call i8 @llvm.sadd.sat.i8(i8 %a, i8 10)
   %c = icmp sge i8 %b, -118
   ret i1 %c
 }
 
 define i1 @sadd_icmp_pos_unknown(i8 %a) {
 ; CHECK-LABEL: @sadd_icmp_pos_unknown(
 ; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[A:%.*]], i8 10)
 ; CHECK-NEXT:    [[C:%.*]] = icmp sgt i8 [[B]], -118
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %b = call i8 @llvm.sadd.sat.i8(i8 %a, i8 10)
   %c = icmp sgt i8 %b, -118
   ret i1 %c
 }
 
 define i1 @sadd_icmp_neg_known(i8 %a) {
 ; CHECK-LABEL: @sadd_icmp_neg_known(
-; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[A:%.*]], i8 -10)
-; CHECK-NEXT:    [[C:%.*]] = icmp sle i8 [[B]], 117
-; CHECK-NEXT:    ret i1 [[C]]
+; CHECK-NEXT:    ret i1 true
 ;
   %b = call i8 @llvm.sadd.sat.i8(i8 %a, i8 -10)
   %c = icmp sle i8 %b, 117
   ret i1 %c
 }
 
 define i1 @sadd_icmp_neg_unknown(i8 %a) {
 ; CHECK-LABEL: @sadd_icmp_neg_unknown(
 ; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[A:%.*]], i8 -10)
 ; CHECK-NEXT:    [[C:%.*]] = icmp slt i8 [[B]], 117
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %b = call i8 @llvm.sadd.sat.i8(i8 %a, i8 -10)
   %c = icmp slt i8 %b, 117
   ret i1 %c
 }
 
 define i1 @usub_icmp_op0_known(i8 %a) {
 ; CHECK-LABEL: @usub_icmp_op0_known(
-; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.usub.sat.i8(i8 10, i8 [[A:%.*]])
-; CHECK-NEXT:    [[C:%.*]] = icmp ule i8 [[B]], 10
-; CHECK-NEXT:    ret i1 [[C]]
+; CHECK-NEXT:    ret i1 true
 ;
   %b = call i8 @llvm.usub.sat.i8(i8 10, i8 %a)
   %c = icmp ule i8 %b, 10
   ret i1 %c
 }
 
 define i1 @usub_icmp_op0_unknown(i8 %a) {
 ; CHECK-LABEL: @usub_icmp_op0_unknown(
 ; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.usub.sat.i8(i8 10, i8 [[A:%.*]])
 ; CHECK-NEXT:    [[C:%.*]] = icmp ult i8 [[B]], 10
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %b = call i8 @llvm.usub.sat.i8(i8 10, i8 %a)
   %c = icmp ult i8 %b, 10
   ret i1 %c
 }
 
 define i1 @usub_icmp_op1_known(i8 %a) {
 ; CHECK-LABEL: @usub_icmp_op1_known(
-; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[A:%.*]], i8 10)
-; CHECK-NEXT:    [[C:%.*]] = icmp ule i8 [[B]], -11
-; CHECK-NEXT:    ret i1 [[C]]
+; CHECK-NEXT:    ret i1 true
 ;
   %b = call i8 @llvm.usub.sat.i8(i8 %a, i8 10)
   %c = icmp ule i8 %b, 245
   ret i1 %c
 }
 
 define i1 @usub_icmp_op1_unknown(i8 %a) {
 ; CHECK-LABEL: @usub_icmp_op1_unknown(
 ; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[A:%.*]], i8 10)
 ; CHECK-NEXT:    [[C:%.*]] = icmp ult i8 [[B]], -11
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %b = call i8 @llvm.usub.sat.i8(i8 %a, i8 10)
   %c = icmp ult i8 %b, 245
   ret i1 %c
 }
 
 define i1 @ssub_icmp_op0_pos_known(i8 %a) {
 ; CHECK-LABEL: @ssub_icmp_op0_pos_known(
-; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.ssub.sat.i8(i8 10, i8 [[A:%.*]])
-; CHECK-NEXT:    [[C:%.*]] = icmp sge i8 [[B]], -117
-; CHECK-NEXT:    ret i1 [[C]]
+; CHECK-NEXT:    ret i1 true
 ;
   %b = call i8 @llvm.ssub.sat.i8(i8 10, i8 %a)
   %c = icmp sge i8 %b, -117
   ret i1 %c
 }
 
 define i1 @ssub_icmp_op0_pos_unknown(i8 %a) {
 ; CHECK-LABEL: @ssub_icmp_op0_pos_unknown(
 ; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.ssub.sat.i8(i8 10, i8 [[A:%.*]])
 ; CHECK-NEXT:    [[C:%.*]] = icmp sgt i8 [[B]], -117
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %b = call i8 @llvm.ssub.sat.i8(i8 10, i8 %a)
   %c = icmp sgt i8 %b, -117
   ret i1 %c
 }
 
 define i1 @ssub_icmp_op0_neg_known(i8 %a) {
 ; CHECK-LABEL: @ssub_icmp_op0_neg_known(
-; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.ssub.sat.i8(i8 -10, i8 [[A:%.*]])
-; CHECK-NEXT:    [[C:%.*]] = icmp sle i8 [[B]], 118
-; CHECK-NEXT:    ret i1 [[C]]
+; CHECK-NEXT:    ret i1 true
 ;
   %b = call i8 @llvm.ssub.sat.i8(i8 -10, i8 %a)
   %c = icmp sle i8 %b, 118
   ret i1 %c
 }
 
 define i1 @ssub_icmp_op0_neg_unknown(i8 %a) {
 ; CHECK-LABEL: @ssub_icmp_op0_neg_unknown(
 ; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.ssub.sat.i8(i8 -10, i8 [[A:%.*]])
 ; CHECK-NEXT:    [[C:%.*]] = icmp slt i8 [[B]], 118
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %b = call i8 @llvm.ssub.sat.i8(i8 -10, i8 %a)
   %c = icmp slt i8 %b, 118
   ret i1 %c
 }
 
 ; Peculiar case: ssub.sat(0, x) is never signed min.
 define i1 @ssub_icmp_op0_zero(i8 %a) {
 ; CHECK-LABEL: @ssub_icmp_op0_zero(
-; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.ssub.sat.i8(i8 0, i8 [[A:%.*]])
-; CHECK-NEXT:    [[C:%.*]] = icmp ne i8 [[B]], -128
-; CHECK-NEXT:    ret i1 [[C]]
+; CHECK-NEXT:    ret i1 true
 ;
   %b = call i8 @llvm.ssub.sat.i8(i8 0, i8 %a)
   %c = icmp ne i8 %b, -128
   ret i1 %c
 }