[CVP] When proving that @llvm.with.overflow()/@llvm.sat() don't overflow, also try to prove other no-wrap

[lebedev.ri]

Summary

CVP, unlike InstCombine, does not run till exaustion.
It only does a single pass.

When dealing with those special binops, if we prove that they can
safely be demoted into their usual binop form,
we do set the no-wrap we deduced. But when dealing with usual binops,
we try to deduce both no-wraps.

So if we convert e.g. @llvm.uadd.with.overflow() to add nuw,
we won't attempt to check whether it can be add nuw nsw.

This patch proposes to call processBinOp() on newly-created binop.

[lebedev.ri]

Typos

[nikic]

LGTM, we already do the same for div/rem.

[lebedev.ri]

In D69183#1714898, @nikic wrote:

LGTM

Thank you for the review.
I think i'll try to add no-wrap deduction for mul here next.

we already do the same for div/rem.

Ah, indeed, good point.

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

if (NewNUW) {
     ++OpcNW;
     ++NumNUW;
     ++OpcNUW;
     if (Inst)
       Inst->setHasNoUnsignedWrap();
   }
 }
 
+static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI);
+
 // Rewrite this with.overflow intrinsic as non-overflowing.
-static void processOverflowIntrinsic(WithOverflowInst *WO) {
+static void processOverflowIntrinsic(WithOverflowInst *WO, LazyValueInfo *LVI) {
   IRBuilder<> B(WO);
   Instruction::BinaryOps Opcode = WO->getBinaryOp();
   bool NSW = WO->isSigned();
   bool NUW = !WO->isSigned();
 
   Value *NewOp =
       B.CreateBinOp(Opcode, WO->getLHS(), WO->getRHS(), WO->getName());
   setDeducedOverflowingFlags(NewOp, Opcode, NSW, NUW);
 
   StructType *ST = cast<StructType>(WO->getType());
   Constant *Struct = ConstantStruct::get(ST,
       { UndefValue::get(ST->getElementType(0)),
         ConstantInt::getFalse(ST->getElementType(1)) });
   Value *NewI = B.CreateInsertValue(Struct, NewOp, 0);
   WO->replaceAllUsesWith(NewI);
   WO->eraseFromParent();
   ++NumOverflows;
+
+  // See if we can infer the other no-wrap too.
+  if (auto *BO = dyn_cast<BinaryOperator>(NewOp))
+    processBinOp(BO, LVI);
 }
 
-static void processSaturatingInst(SaturatingInst *SI) {
+static void processSaturatingInst(SaturatingInst *SI, LazyValueInfo *LVI) {
   Instruction::BinaryOps Opcode = SI->getBinaryOp();
   bool NSW = SI->isSigned();
   bool NUW = !SI->isSigned();
   BinaryOperator *BinOp = BinaryOperator::Create(
       Opcode, SI->getLHS(), SI->getRHS(), SI->getName(), SI);
   BinOp->setDebugLoc(SI->getDebugLoc());
   setDeducedOverflowingFlags(BinOp, Opcode, NSW, NUW);
 
   SI->replaceAllUsesWith(BinOp);
   SI->eraseFromParent();
   ++NumSaturating;
+
+  // See if we can infer the other no-wrap too.
+  if (auto *BO = dyn_cast<BinaryOperator>(BinOp))
+    processBinOp(BO, LVI);
 }
 
 /// 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 (WO->getLHS()->getType()->isIntegerTy() && willNotOverflow(WO, LVI)) {
-      processOverflowIntrinsic(WO);
+      processOverflowIntrinsic(WO, LVI);
       return true;
     }
   }
 
   if (auto *SI = dyn_cast<SaturatingInst>(CS.getInstruction())) {
     if (SI->getType()->isIntegerTy() && willNotOverflow(SI, LVI)) {
-      processSaturatingInst(SI);
+      processSaturatingInst(SI, LVI);
       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

llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll

 
 
 define i32 @signed_add(i32 %x, i32 %y) {
 ; CHECK-LABEL: @signed_add(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[Y:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LAND_LHS_TRUE:%.*]], label [[LOR_LHS_FALSE:%.*]]
 ; CHECK:       land.lhs.true:
-; CHECK-NEXT:    [[TMP0:%.*]] = sub nsw i32 2147483647, [[Y]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub nuw nsw i32 2147483647, [[Y]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[TMP0]], 0
 ; CHECK-NEXT:    [[TMP2:%.*]] = extractvalue { i32, i1 } [[TMP1]], 1
 ; CHECK-NEXT:    br i1 [[TMP2]], label [[TRAP:%.*]], label [[CONT:%.*]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    tail call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont:
 ; CHECK-NEXT:    [[TMP3:%.*]] = extractvalue { i32, i1 } [[TMP1]], 0

 cond.end:                                         ; preds = %cond.false, %cont, %cont4
   %cond = phi i32 [ 0, %cont4 ], [ 0, %cont ], [ %7, %cond.false ]
   ret i32 %cond
 }
 
 define i32 @unsigned_add(i32 %x, i32 %y) {
 ; CHECK-LABEL: @unsigned_add(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = sub nuw i32 -1, [[Y:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub nuw nsw i32 -1, [[Y:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[TMP0]], 0
 ; CHECK-NEXT:    [[TMP2:%.*]] = extractvalue { i32, i1 } [[TMP1]], 1
 ; CHECK-NEXT:    br i1 [[TMP2]], label [[TRAP:%.*]], label [[CONT:%.*]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    tail call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont:
 ; CHECK-NEXT:    [[TMP3:%.*]] = extractvalue { i32, i1 } [[TMP1]], 0

 ; CHECK:       cont:
 ; CHECK-NEXT:    [[TMP3:%.*]] = extractvalue { i32, i1 } [[TMP1]], 0
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[TMP3]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP1]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
 ; CHECK:       lor.lhs.false:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[Y]], 0
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[COND_FALSE]], label [[LAND_LHS_TRUE3:%.*]]
 ; CHECK:       land.lhs.true3:
-; CHECK-NEXT:    [[TMP4:%.*]] = add nsw i32 [[Y]], -2147483648
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i32 [[Y]], -2147483648
 ; CHECK-NEXT:    [[TMP5:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[TMP4]], 0
 ; CHECK-NEXT:    [[TMP6:%.*]] = extractvalue { i32, i1 } [[TMP5]], 1
 ; CHECK-NEXT:    br i1 [[TMP6]], label [[TRAP]], label [[CONT4:%.*]]
 ; CHECK:       cont4:
 ; CHECK-NEXT:    [[TMP7:%.*]] = extractvalue { i32, i1 } [[TMP5]], 0
 ; CHECK-NEXT:    [[CMP5:%.*]] = icmp sgt i32 [[TMP7]], [[X]]
 ; CHECK-NEXT:    br i1 [[CMP5]], label [[COND_END]], label [[COND_FALSE]]
 ; CHECK:       cond.false:

 }
 
 define i32 @unsigned_mul(i32 %x) {
 ; CHECK-LABEL: @unsigned_mul(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[X:%.*]], 10000
 ; CHECK-NEXT:    br i1 [[CMP]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
 ; CHECK:       cond.false:
-; CHECK-NEXT:    [[MULO1:%.*]] = mul nuw i32 [[X]], 100
+; CHECK-NEXT:    [[MULO1:%.*]] = mul nuw nsw i32 [[X]], 100
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[MULO1]], 0
 ; CHECK-NEXT:    [[RES:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i32, i1 } [[TMP0]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[TRAP:%.*]], label [[COND_END]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    tail call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cond.end:

 define i8 @uadd_sat_no_overflow(i8 %x) {
 ; CHECK-LABEL: @uadd_sat_no_overflow(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[X:%.*]], 27
 ; CHECK-NEXT:    br i1 [[CMP]], label [[TRAP:%.*]], label [[CONT:%.*]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont:
-; CHECK-NEXT:    [[RES1:%.*]] = add nuw i8 [[X]], 100
+; CHECK-NEXT:    [[RES1:%.*]] = add nuw nsw i8 [[X]], 100
 ; CHECK-NEXT:    ret i8 [[RES1]]
 ;
   %cmp = icmp ugt i8 %x, 27
   br i1 %cmp, label %trap, label %cont
 
 trap:
   call void @llvm.trap()
   unreachable

 define i8 @sadd_sat_no_overflow(i8 %x) {
 ; CHECK-LABEL: @sadd_sat_no_overflow(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[X:%.*]], 107
 ; CHECK-NEXT:    br i1 [[CMP]], label [[TRAP:%.*]], label [[CONT:%.*]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont:
-; CHECK-NEXT:    [[RES1:%.*]] = add nsw i8 [[X]], 20
+; CHECK-NEXT:    [[RES1:%.*]] = add nuw nsw i8 [[X]], 20
 ; CHECK-NEXT:    ret i8 [[RES1]]
 ;
   %cmp = icmp ugt i8 %x, 107
   br i1 %cmp, label %trap, label %cont
 
 trap:
   call void @llvm.trap()
   unreachable

 define i8 @usub_sat_no_overflow(i8 %x) {
 ; CHECK-LABEL: @usub_sat_no_overflow(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[X:%.*]], -28
 ; CHECK-NEXT:    br i1 [[CMP]], label [[TRAP:%.*]], label [[CONT:%.*]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont:
-; CHECK-NEXT:    [[RES1:%.*]] = sub nuw i8 [[X]], 100
+; CHECK-NEXT:    [[RES1:%.*]] = sub nuw nsw i8 [[X]], 100
 ; CHECK-NEXT:    ret i8 [[RES1]]
 ;
   %cmp = icmp ult i8 %x, 228
   br i1 %cmp, label %trap, label %cont
 
 trap:
   call void @llvm.trap()
   unreachable

 define i8 @ssub_sat_no_overflow(i8 %x) {
 ; CHECK-LABEL: @ssub_sat_no_overflow(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[X:%.*]], -108
 ; CHECK-NEXT:    br i1 [[CMP]], label [[TRAP:%.*]], label [[CONT:%.*]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont:
-; CHECK-NEXT:    [[RES1:%.*]] = sub nsw i8 [[X]], 20
+; CHECK-NEXT:    [[RES1:%.*]] = sub nuw nsw i8 [[X]], 20
 ; CHECK-NEXT:    ret i8 [[RES1]]
 ;
   %cmp = icmp ult i8 %x, 148
   br i1 %cmp, label %trap, label %cont
 
 trap:
   call void @llvm.trap()
   unreachable

 ; CHECK-LABEL: @uadd_and_cmp(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i32 [[X:%.*]], 10
 ; CHECK-NEXT:    br i1 [[CMP1]], label [[CONT1:%.*]], label [[OUT:%.*]]
 ; CHECK:       cont1:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y:%.*]], 10
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
-; CHECK-NEXT:    [[RES1:%.*]] = add nuw i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[RES1:%.*]] = add nuw nsw i32 [[X]], [[Y]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[RES1]], 0
 ; CHECK-NEXT:    [[ADD:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
 ; CHECK:       cont3:
 ; CHECK-NEXT:    br label [[OUT]]
 ; CHECK:       out:
 ; CHECK-NEXT:    ret i1 true
 ;

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i32 [[X:%.*]], 10
 ; CHECK-NEXT:    br i1 [[CMP1]], label [[CONT1:%.*]], label [[OUT:%.*]]
 ; CHECK:       cont1:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y:%.*]], 10
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
 ; CHECK-NEXT:    [[OFFSET:%.*]] = add nuw nsw i32 [[X]], 9
-; CHECK-NEXT:    [[RES1:%.*]] = sub nsw i32 [[OFFSET]], [[Y]]
+; CHECK-NEXT:    [[RES1:%.*]] = sub nuw nsw i32 [[OFFSET]], [[Y]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[RES1]], 0
 ; CHECK-NEXT:    [[SUB:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
 ; CHECK:       cont3:
 ; CHECK-NEXT:    br label [[OUT]]
 ; CHECK:       out:
 ; CHECK-NEXT:    ret i1 true
 ;

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i32 [[X:%.*]], 10
 ; CHECK-NEXT:    br i1 [[CMP1]], label [[CONT1:%.*]], label [[OUT:%.*]]
 ; CHECK:       cont1:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y:%.*]], 10
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
 ; CHECK-NEXT:    [[OFFSET:%.*]] = add nuw nsw i32 [[X]], 9
-; CHECK-NEXT:    [[RES1:%.*]] = sub nuw i32 [[OFFSET]], [[Y]]
+; CHECK-NEXT:    [[RES1:%.*]] = sub nuw nsw i32 [[OFFSET]], [[Y]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[RES1]], 0
 ; CHECK-NEXT:    [[SUB:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
 ; CHECK:       cont3:
 ; CHECK-NEXT:    br label [[OUT]]
 ; CHECK:       out:
 ; CHECK-NEXT:    ret i1 true
 ;

 ; CHECK-LABEL: @umul_and_cmp(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i32 [[X:%.*]], 100
 ; CHECK-NEXT:    br i1 [[CMP1]], label [[CONT1:%.*]], label [[OUT:%.*]]
 ; CHECK:       cont1:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y:%.*]], 100
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
-; CHECK-NEXT:    [[RES1:%.*]] = mul nuw i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[RES1:%.*]] = mul nuw nsw i32 [[X]], [[Y]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[RES1]], 0
 ; CHECK-NEXT:    [[MUL:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
 ; CHECK:       cont3:
 ; CHECK-NEXT:    br label [[OUT]]
 ; CHECK:       out:
 ; CHECK-NEXT:    ret i1 true
 ;