[CVP] Simplify non-overflowing saturating add/sub

[nikic]

Summary

If we can determine that a saturating add/sub will not overflow based on range analysis, convert it into a simple binary operation. This is a sibling transform to the existing with.overflow handling.

[lebedev.ri]

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

444

Why not add a new statistic
"Number of saturating arithmetics converted to normal arithmetics"
?

[nikic]

Use separate statistic.

[lebedev.ri]

Looks good

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

414–431

Hm, is this not preserving debugloc?

418

holding

[nikic]

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

414–431

This does preserve debugloc. In this case it's handled by the IRBuilder API. (The overflows.ll test also does a debugify check.)

[nikic]

Reverted in rL362254 due to assertion failure in clang tests.

[nikic]

Check for integer type before trying to simplify, as LVI does not support vectors of integers. Also fix this for the with.overflow case -- we've recently started accepting vector args for those as well, but it looks like nobody ever ran the vector version through -O1 :)

[lebedev.ri]

(can you please commit @llvm.uadd.with.overflow.v2i32 + fix; the @llvm.uadd.sat.v2i8 test; and the patch as three separate commits?)
Hmm, right, not sure how this should work for vectors, especially non-splat ones. Treat each line separately?

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

414–431

Great, thanks for checking!

418

err, right, folding (:

llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll

834

Hmm, great catch!
I guess saturating vectors are rare since nobody hit this yet?

[nikic]

llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll

834

Assuming you meant vector overflow here, then yes: This is only supported since recently -- more or less a side effect of having to deal with vector addo/subo in SDAG for saturating math expansion, so might as well allow in IR. But looks like nobody has actually used this yet, otherwise they would have definitely run into this issue :)

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

 STATISTIC(NumCmps,      "Number of comparisons propagated");
 STATISTIC(NumReturns,   "Number of return values propagated");
 STATISTIC(NumDeadCases, "Number of switch cases removed");
 STATISTIC(NumSDivs,     "Number of sdiv converted to udiv");
 STATISTIC(NumUDivs,     "Number of udivs whose width was decreased");
 STATISTIC(NumAShrs,     "Number of ashr converted to lshr");
 STATISTIC(NumSRems,     "Number of srem converted to urem");
 STATISTIC(NumOverflows, "Number of overflow checks removed");
+STATISTIC(NumSaturating,
+    "Number of saturating arithmetics converted to normal arithmetics");
 
 static cl::opt<bool> DontAddNoWrapFlags("cvp-dont-add-nowrap-flags", cl::init(true));
 
 namespace {
 
   class CorrelatedValuePropagation : public FunctionPass {
   public:
     static char ID;
ConstantRange LRange = LVI->getConstantRange(
       BO->getLHS(), BO->getParent(), BO);
   ConstantRange RRange = LVI->getConstantRange(
       BO->getRHS(), BO->getParent(), BO);
   ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
       BO->getBinaryOp(), RRange, BO->getNoWrapKind());
   return NWRegion.contains(LRange);
 }
 
 static void processOverflowIntrinsic(WithOverflowInst *WO) {
   IRBuilder<> B(WO);
   Value *NewOp = B.CreateBinOp(
       WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), WO->getName());
-  // Constant-holing could have happened.
+  // Constant-folding could have happened.
   if (auto *Inst = dyn_cast<Instruction>(NewOp)) {
     if (WO->isSigned())
       Inst->setHasNoSignedWrap();
     else
       Inst->setHasNoUnsignedWrap();
   }
 
   Value *NewI = B.CreateInsertValue(UndefValue::get(WO->getType()), NewOp, 0);
   NewI = B.CreateInsertValue(NewI, ConstantInt::getFalse(WO->getContext()), 1);
   WO->replaceAllUsesWith(NewI);
   WO->eraseFromParent();
   ++NumOverflows;
 }
 
+static void processSaturatingInst(SaturatingInst *SI) {
+  BinaryOperator *BinOp = BinaryOperator::Create(
+      SI->getBinaryOp(), SI->getLHS(), SI->getRHS(), SI->getName(), SI);
+  BinOp->setDebugLoc(SI->getDebugLoc());
+  if (SI->isSigned())
+    BinOp->setHasNoSignedWrap();
+  else
+    BinOp->setHasNoUnsignedWrap();
+
+  SI->replaceAllUsesWith(BinOp);
+  SI->eraseFromParent();
+  ++NumSaturating;
+}
+
 /// Infer nonnull attributes for the arguments at the specified callsite.
 static bool processCallSite(CallSite CS, LazyValueInfo *LVI) {
   SmallVector<unsigned, 4> ArgNos;
   unsigned ArgNo = 0;
 
   if (auto *WO = dyn_cast<WithOverflowInst>(CS.getInstruction())) {
-    if (willNotOverflow(WO, LVI)) {
+    if (WO->getLHS()->getType()->isIntegerTy() && willNotOverflow(WO, LVI)) {
       processOverflowIntrinsic(WO);
       return true;
     }
   }
 
+  if (auto *SI = dyn_cast<SaturatingInst>(CS.getInstruction())) {
+    if (SI->getType()->isIntegerTy() && willNotOverflow(SI, LVI)) {
+      processSaturatingInst(SI);
+      return true;
+    }
+  }
+
   // Deopt bundle operands are intended to capture state with minimal
   // perturbance of the code otherwise.  If we can find a constant value for
   // any such operand and remove a use of the original value, that's
   // desireable since it may allow further optimization of that value (e.g. via
   // single use rules in instcombine).  Since deopt uses tend to,
   // idiomatically, appear along rare conditional paths, it's reasonable likely
   // we may have a conditional fact with which LVI can fold.   
   if (auto DeoptBundle = CS.getOperandBundle(LLVMContext::OB_deopt)) {

llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll

 declare { i32, i1 } @llvm.uadd.with.overflow.i32(i32, i32)
 
 declare { i32, i1 } @llvm.usub.with.overflow.i32(i32, i32)
 
 declare { i32, i1 } @llvm.umul.with.overflow.i32(i32, i32)
 
 declare { i8, i1 } @llvm.umul.with.overflow.i8(i8, i8)
 
+declare { <2 x i32>, <2 x i1> } @llvm.uadd.with.overflow.v2i32(<2 x i32>, <2 x i32>)
+
 declare i8 @llvm.uadd.sat.i8(i8, i8)
 declare i8 @llvm.sadd.sat.i8(i8, i8)
 declare i8 @llvm.usub.sat.i8(i8, i8)
 declare i8 @llvm.ssub.sat.i8(i8, i8)
+declare <2 x i8> @llvm.uadd.sat.v2i8(<2 x i8>, <2 x i8>)
 
 declare void @llvm.trap()
 
 
 define i32 @signed_add(i32 %x, i32 %y) {
 ; CHECK-LABEL: @signed_add(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[Y:%.*]], 0

 define i8 @uadd_sat_no_overflow(i8 %x) {
 ; CHECK-LABEL: @uadd_sat_no_overflow(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[X:%.*]], 100
 ; CHECK-NEXT:    br i1 [[CMP]], label [[TRAP:%.*]], label [[CONT:%.*]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont:
-; CHECK-NEXT:    [[RES:%.*]] = call i8 @llvm.uadd.sat.i8(i8 [[X]], i8 100)
-; CHECK-NEXT:    ret i8 [[RES]]
+; CHECK-NEXT:    [[RES1:%.*]] = add nuw i8 [[X]], 100
+; CHECK-NEXT:    ret i8 [[RES1]]
 ;
   %cmp = icmp ugt i8 %x, 100
   br i1 %cmp, label %trap, label %cont
 
 trap:
   call void @llvm.trap()
   unreachable
 
 cont:
   %res = call i8 @llvm.uadd.sat.i8(i8 %x, i8 100)
   ret i8 %res
 }
 
 define i8 @sadd_sat_no_overflow(i8 %x) {
 ; CHECK-LABEL: @sadd_sat_no_overflow(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[X:%.*]], 100
 ; CHECK-NEXT:    br i1 [[CMP]], label [[TRAP:%.*]], label [[CONT:%.*]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont:
-; CHECK-NEXT:    [[RES:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[X]], i8 20)
-; CHECK-NEXT:    ret i8 [[RES]]
+; CHECK-NEXT:    [[RES1:%.*]] = add nsw i8 [[X]], 20
+; CHECK-NEXT:    ret i8 [[RES1]]
 ;
   %cmp = icmp sgt i8 %x, 100
   br i1 %cmp, label %trap, label %cont
 
 trap:
   call void @llvm.trap()
   unreachable
 
 cont:
   %res = call i8 @llvm.sadd.sat.i8(i8 %x, i8 20)
   ret i8 %res
 }
 
 define i8 @usub_sat_no_overflow(i8 %x) {
 ; CHECK-LABEL: @usub_sat_no_overflow(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[X:%.*]], 100
 ; CHECK-NEXT:    br i1 [[CMP]], label [[TRAP:%.*]], label [[CONT:%.*]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont:
-; CHECK-NEXT:    [[RES:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[X]], i8 100)
-; CHECK-NEXT:    ret i8 [[RES]]
+; CHECK-NEXT:    [[RES1:%.*]] = sub nuw i8 [[X]], 100
+; CHECK-NEXT:    ret i8 [[RES1]]
 ;
   %cmp = icmp ult i8 %x, 100
   br i1 %cmp, label %trap, label %cont
 
 trap:
   call void @llvm.trap()
   unreachable
 
 cont:
   %res = call i8 @llvm.usub.sat.i8(i8 %x, i8 100)
   ret i8 %res
 }
 
 define i8 @ssub_sat_no_overflow(i8 %x) {
 ; CHECK-LABEL: @ssub_sat_no_overflow(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[X:%.*]], -100
 ; CHECK-NEXT:    br i1 [[CMP]], label [[TRAP:%.*]], label [[CONT:%.*]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont:
-; CHECK-NEXT:    [[RES:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[X]], i8 20)
-; CHECK-NEXT:    ret i8 [[RES]]
+; CHECK-NEXT:    [[RES1:%.*]] = sub nsw i8 [[X]], 20
+; CHECK-NEXT:    ret i8 [[RES1]]
 ;
   %cmp = icmp slt i8 %x, -100
   br i1 %cmp, label %trap, label %cont
 
 trap:
   call void @llvm.trap()
   unreachable
 
 cont:
   %res = call i8 @llvm.ssub.sat.i8(i8 %x, i8 20)
   ret i8 %res
 }
+
+define { <2 x i32>, <2 x i1> } @uaddo_vec(<2 x i32> %a) {
+; CHECK-LABEL: @uaddo_vec(
+; CHECK-NEXT:    [[ADD:%.*]] = call { <2 x i32>, <2 x i1> } @llvm.uadd.with.overflow.v2i32(<2 x i32> [[A:%.*]], <2 x i32> <i32 1, i32 1>)
+; CHECK-NEXT:    ret { <2 x i32>, <2 x i1> } [[ADD]]
+;
+  %add = call { <2 x i32>, <2 x i1> } @llvm.uadd.with.overflow.v2i32(<2 x i32> %a, <2 x i32> <i32 1, i32 1>)
+  ret { <2 x i32>, <2 x i1> } %add
+}
+
+define <2 x i8> @uadd_sat_vec(<2 x i8> %a) {
+; CHECK-LABEL: @uadd_sat_vec(
+; CHECK-NEXT:    [[ADD:%.*]] = call <2 x i8> @llvm.uadd.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 1, i8 1>)
+; CHECK-NEXT:    ret <2 x i8> [[ADD]]
+;
+  %add = call <2 x i8> @llvm.uadd.sat.v2i8(<2 x i8> %a, <2 x i8> <i8 1, i8 1>)
+  ret <2 x i8> %add
+}