[LVI][CVP] Add support for saturating add/sub

[nikic]

Summary

Adds support for the uadd.sat family of intrinsics in LVI, based on ConstantRange methods from D60946.

[lebedev.ri]

Still not any more familiar with CVP, but this looks rather identical to the solveBlockValueOverflowIntrinsic() change, so LG.
Up to you if you want to wait for one more signoff (@spatel ?)

llvm/lib/Analysis/LazyValueInfo.cpp

1122

Have you considered adding a SaturatingInst base class, much like WithOverflowInst;
and/or saturatingBinaryOp, much like binaryOp, to ConstantRange?
I think that might potentially be a bit cleaner overall.
(Not for this patch)

[spatel]

LGTM

[nikic]

llvm/lib/Analysis/LazyValueInfo.cpp

1122

Yeah, that might make sense. Having it (possibly even a common base class with WithOverflowInst) would be useful to extend https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp#L402 to saturating math.

llvm/lib/Analysis/LazyValueInfo.cpp

bool solveBlockValueBinaryOpImpl(
       std::function<ConstantRange(const ConstantRange &,
                                   const ConstantRange &)> OpFn);
   bool solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BBI,
                                BasicBlock *BB);
   bool solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI,
                            BasicBlock *BB);
   bool solveBlockValueOverflowIntrinsic(
       ValueLatticeElement &BBLV, WithOverflowInst *WO, BasicBlock *BB);
+  bool solveBlockValueIntrinsic(ValueLatticeElement &BBLV, IntrinsicInst *II,
+                                BasicBlock *BB);
   void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
                                                      ValueLatticeElement &BBLV,
                                                      Instruction *BBI);
 
   void solve();
 
   public:
     /// This is the query interface to determine the lattice
if (BBI->getType()->isIntegerTy()) {
 
     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI))
       return solveBlockValueBinaryOp(Res, BO, BB);
 
     if (auto *EVI = dyn_cast<ExtractValueInst>(BBI))
       if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
         if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0)
           return solveBlockValueOverflowIntrinsic(Res, WO, BB);
+
+    if (auto *II = dyn_cast<IntrinsicInst>(BBI))
+      return solveBlockValueIntrinsic(Res, II, BB);
   }
 
   LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
                     << "' - unknown inst def found.\n");
   Res = getFromRangeMetadata(BBI);
   return true;
 }
 

 bool LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(
     ValueLatticeElement &BBLV, WithOverflowInst *WO, BasicBlock *BB) {
   return solveBlockValueBinaryOpImpl(BBLV, WO, BB,
       [WO](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.binaryOp(WO->getBinaryOp(), CR2);
       });
 }
 
+bool LazyValueInfoImpl::solveBlockValueIntrinsic(
+    ValueLatticeElement &BBLV, IntrinsicInst *II, BasicBlock *BB) {
+  switch (II->getIntrinsicID()) {
+  case Intrinsic::uadd_sat:
+    return solveBlockValueBinaryOpImpl(BBLV, II, BB,
+        [](const ConstantRange &CR1, const ConstantRange &CR2) {
+          return CR1.uadd_sat(CR2);
+        });
+  case Intrinsic::usub_sat:
+    return solveBlockValueBinaryOpImpl(BBLV, II, BB,
+        [](const ConstantRange &CR1, const ConstantRange &CR2) {
+          return CR1.usub_sat(CR2);
+        });
+  case Intrinsic::sadd_sat:
+    return solveBlockValueBinaryOpImpl(BBLV, II, BB,
+        [](const ConstantRange &CR1, const ConstantRange &CR2) {
+          return CR1.sadd_sat(CR2);
+        });
+  case Intrinsic::ssub_sat:
+    return solveBlockValueBinaryOpImpl(BBLV, II, BB,
+        [](const ConstantRange &CR1, const ConstantRange &CR2) {
+          return CR1.ssub_sat(CR2);
+        });
+  default:
+    LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
+                      << "' - overdefined (unknown intrinsic).\n");
+    BBLV = ValueLatticeElement::getOverdefined();
+    return true;
+  }
+}
+
 static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
                                                      bool isTrueDest) {
   Value *LHS = ICI->getOperand(0);
   Value *RHS = ICI->getOperand(1);
   CmpInst::Predicate Predicate = ICI->getPredicate();
 
   if (isa<Constant>(RHS)) {
     if (ICI->isEquality() && LHS == Val) {

llvm/test/Transforms/CorrelatedValuePropagation/basic.ll

 define i1 @uadd_sat_unknown(i32 %a) {
 ; CHECK-LABEL: @uadd_sat_unknown(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[VAL:%.*]] = call i32 @llvm.uadd.sat.i32(i32 [[A:%.*]], i32 100)
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp uge i32 [[VAL]], 100
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i32 [[VAL]], 100
 ; CHECK-NEXT:    br i1 undef, label [[EXIT1:%.*]], label [[EXIT2:%.*]]
 ; CHECK:       exit1:
-; CHECK-NEXT:    ret i1 [[CMP1]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       exit2:
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
 entry:
   %val = call i32 @llvm.uadd.sat.i32(i32 %a, i32 100)
   %cmp1 = icmp uge i32 %val, 100
   %cmp2 = icmp ugt i32 %val, 100
   br i1 undef, label %exit1, label %exit2
 exit1:
   ret i1 %cmp1
 exit2:
   ret i1 %cmp2
 }
 
 define i1 @usub_sat_unknown(i32 %a) {
 ; CHECK-LABEL: @usub_sat_unknown(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[VAL:%.*]] = call i32 @llvm.usub.sat.i32(i32 [[A:%.*]], i32 100)
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i32 [[VAL]], -101
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[VAL]], -101
 ; CHECK-NEXT:    br i1 undef, label [[EXIT1:%.*]], label [[EXIT2:%.*]]
 ; CHECK:       exit1:
-; CHECK-NEXT:    ret i1 [[CMP1]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       exit2:
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
 entry:
   %val = call i32 @llvm.usub.sat.i32(i32 %a, i32 100)
   %cmp1 = icmp ule i32 %val, 4294967195
   %cmp2 = icmp ult i32 %val, 4294967195
   br i1 undef, label %exit1, label %exit2
 exit1:
   ret i1 %cmp1
 exit2:
   ret i1 %cmp2
 }
 
 define i1 @sadd_sat_unknown(i32 %a) {
 ; CHECK-LABEL: @sadd_sat_unknown(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[VAL:%.*]] = call i32 @llvm.sadd.sat.i32(i32 [[A:%.*]], i32 100)
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sge i32 [[VAL]], -2147483548
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[VAL]], -2147483548
 ; CHECK-NEXT:    br i1 undef, label [[EXIT1:%.*]], label [[EXIT2:%.*]]
 ; CHECK:       exit1:
-; CHECK-NEXT:    ret i1 [[CMP1]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       exit2:
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
 entry:
   %val = call i32 @llvm.sadd.sat.i32(i32 %a, i32 100)
   %cmp1 = icmp sge i32 %val, -2147483548
   %cmp2 = icmp sgt i32 %val, -2147483548
   br i1 undef, label %exit1, label %exit2
 exit1:
   ret i1 %cmp1
 exit2:
   ret i1 %cmp2
 }
 
 define i1 @ssub_sat_unknown(i32 %a) {
 ; CHECK-LABEL: @ssub_sat_unknown(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[VAL:%.*]] = call i32 @llvm.ssub.sat.i32(i32 [[A:%.*]], i32 100)
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sle i32 [[VAL]], 2147483547
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[VAL]], 2147483547
 ; CHECK-NEXT:    br i1 undef, label [[EXIT1:%.*]], label [[EXIT2:%.*]]
 ; CHECK:       exit1:
-; CHECK-NEXT:    ret i1 [[CMP1]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       exit2:
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
 entry:
   %val = call i32 @llvm.ssub.sat.i32(i32 %a, i32 100)
   %cmp1 = icmp sle i32 %val, 2147483547
   %cmp2 = icmp slt i32 %val, 2147483547
   br i1 undef, label %exit1, label %exit2