[CVP] Remove some {s|u}sub.with.overflow checks.

[jgalenson]

Summary

This uses ConstantRange::makeGuaranteedNoWrapRegion's newly-added handling for subtraction to allow CVP to remove some subtraction overflow checks.

[sanjoy]

lgtm

llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

if (Changed)
     ConstantFoldTerminator(BB);
 
   return Changed;
 }
 
 // See if we can prove that the given overflow intrinsic will not overflow.
 static bool willNotOverflow(IntrinsicInst *II, LazyValueInfo *LVI) {
   using OBO = OverflowingBinaryOperator;
-  auto NoWrapOnAddition = [&] (Value *LHS, Value *RHS, unsigned NoWrapKind) {
+  auto NoWrap = [&] (Instruction::BinaryOps BinOp, unsigned NoWrapKind) {
+    Value *RHS = II->getOperand(1);
     ConstantRange RRange = LVI->getConstantRange(RHS, II->getParent(), II);
     ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
-        BinaryOperator::Add, RRange, NoWrapKind);
+        BinOp, RRange, NoWrapKind);
     // As an optimization, do not compute LRange if we do not need it.
     if (NWRegion.isEmptySet())
       return false;
+    Value *LHS = II->getOperand(0);
     ConstantRange LRange = LVI->getConstantRange(LHS, II->getParent(), II);
     return NWRegion.contains(LRange);
   };
   switch (II->getIntrinsicID()) {
   default:
     break;
   case Intrinsic::uadd_with_overflow:
-    return NoWrapOnAddition(II->getOperand(0), II->getOperand(1),
-                            OBO::NoUnsignedWrap);
+    return NoWrap(Instruction::Add, OBO::NoUnsignedWrap);
   case Intrinsic::sadd_with_overflow:
-    return NoWrapOnAddition(II->getOperand(0), II->getOperand(1),
-                            OBO::NoSignedWrap);
+    return NoWrap(Instruction::Add, OBO::NoSignedWrap);
+  case Intrinsic::usub_with_overflow:
+    return NoWrap(Instruction::Sub, OBO::NoUnsignedWrap);
+  case Intrinsic::ssub_with_overflow:
+    return NoWrap(Instruction::Sub, OBO::NoSignedWrap);
   }
   return false;
 }
 
 static void processOverflowIntrinsic(IntrinsicInst *II) {
   Value *NewOp = nullptr;
   switch (II->getIntrinsicID()) {
   default:
-    llvm_unreachable("Illegal instruction.");
+    llvm_unreachable("Unexpected instruction.");
   case Intrinsic::uadd_with_overflow:
   case Intrinsic::sadd_with_overflow:
     NewOp = BinaryOperator::CreateAdd(II->getOperand(0), II->getOperand(1),
                                       II->getName(), II);
     break;
+  case Intrinsic::usub_with_overflow:
+  case Intrinsic::ssub_with_overflow:
+    NewOp = BinaryOperator::CreateSub(II->getOperand(0), II->getOperand(1),
+                                      II->getName(), II);
+    break;
   }
   ++NumOverflows;
   IRBuilder<> B(II);
   Value *NewI = B.CreateInsertValue(UndefValue::get(II->getType()), NewOp, 0);
   NewI = B.CreateInsertValue(NewI, ConstantInt::getFalse(II->getContext()), 1);
   II->replaceAllUsesWith(NewI);
   II->eraseFromParent();
 }
 
 /// 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 (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
+  if (auto *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
     if (willNotOverflow(II, LVI)) {
       processOverflowIntrinsic(II);
       return true;
     }
   }
 
   for (Value *V : CS.args()) {
     PointerType *Type = dyn_cast<PointerType>(V->getType());

llvm/trunk/test/Transforms/CorrelatedValuePropagation/overflows.ll

 ; RUN: opt -S -correlated-propagation < %s | FileCheck %s
 
 declare { i32, i1 } @llvm.sadd.with.overflow.i32(i32, i32)
 
 declare { i32, i1 } @llvm.ssub.with.overflow.i32(i32, i32)
 
 declare { i32, i1 } @llvm.uadd.with.overflow.i32(i32, i32)
 
 declare { i32, i1 } @llvm.usub.with.overflow.i32(i32, i32)
 
 declare void @llvm.trap()
 
 
 define i32 @signed_add(i32 %x, i32 %y) {
 ; CHECK-LABEL: @signed_add(
-; CHECK: @llvm.ssub.with.overflow.i32
-; CHECK: @llvm.ssub.with.overflow.i32
+; CHECK-NOT: @llvm.ssub.with.overflow.i32
 ; CHECK: @llvm.sadd.with.overflow.i32
 entry:
   %cmp = icmp sgt i32 %y, 0
   br i1 %cmp, label %land.lhs.true, label %lor.lhs.false
 
 land.lhs.true:                                    ; preds = %entry
   %0 = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 2147483647, i32 %y)
   %1 = extractvalue { i32, i1 } %0, 1

 
 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: @llvm.usub.with.overflow.i32
+; CHECK-NOT: @llvm.usub.with.overflow.i32
 ; CHECK: @llvm.uadd.with.overflow.i32
 entry:
   %0 = tail call { i32, i1 } @llvm.usub.with.overflow.i32(i32 -1, i32 %y)
   %1 = extractvalue { i32, i1 } %0, 1
   br i1 %1, label %trap, label %cont
 
 trap:                                             ; preds = %cond.false, %entry
   tail call void @llvm.trap()

 
 cond.end:                                         ; preds = %cond.false, %entry
   %cond = phi i32 [ 0, %entry ], [ %1, %cond.false ]
   ret i32 %cond
 }
 
 define i32 @signed_sub_r1(i32 %x) {
 ; CHECK-LABEL: @signed_sub_r1(
-; CHECK: @llvm.ssub.with.overflow.i32
+; CHECK-NOT: @llvm.ssub.with.overflow.i32
 entry:
   %cmp = icmp eq i32 %x, -2147483648
   br i1 %cmp, label %cond.end, label %cond.false
 
 cond.false:                                       ; preds = %entry
   %0 = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %x, i32 1)
   %1 = extractvalue { i32, i1 } %0, 0
   %2 = extractvalue { i32, i1 } %0, 1
   br i1 %2, label %trap, label %cond.end
 
 trap:                                             ; preds = %cond.false
   tail call void @llvm.trap()
   unreachable
 
 cond.end:                                         ; preds = %cond.false, %entry
   %cond = phi i32 [ 0, %entry ], [ %1, %cond.false ]
   ret i32 %cond
 }
 
 define i32 @unsigned_sub_r1(i32 %x) {
 ; CHECK-LABEL: @unsigned_sub_r1(
-; CHECK: @llvm.usub.with.overflow.i32
+; CHECK-NOT: @llvm.usub.with.overflow.i32
 entry:
   %cmp = icmp eq i32 %x, 0
   br i1 %cmp, label %cond.end, label %cond.false
 
 cond.false:                                       ; preds = %entry
   %0 = tail call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %x, i32 1)
   %1 = extractvalue { i32, i1 } %0, 0
   %2 = extractvalue { i32, i1 } %0, 1

 
 cond.end:                                         ; preds = %cond.false, %entry
   %cond = phi i32 [ 0, %entry ], [ %1, %cond.false ]
   ret i32 %cond
 }
 
 define i32 @signed_sub_rn1(i32 %x) {
 ; CHECK-LABEL: @signed_sub_rn1(
-; CHECK: @llvm.ssub.with.overflow.i32
+; CHECK-NOT: @llvm.ssub.with.overflow.i32
 entry:
   %cmp = icmp eq i32 %x, 2147483647
   br i1 %cmp, label %cond.end, label %cond.false
 
 cond.false:                                       ; preds = %entry
   %0 = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %x, i32 -1)
   %1 = extractvalue { i32, i1 } %0, 0
   %2 = extractvalue { i32, i1 } %0, 1
   br i1 %2, label %trap, label %cond.end
 
 trap:                                             ; preds = %cond.false
   tail call void @llvm.trap()
   unreachable
 
 cond.end:                                         ; preds = %cond.false, %entry
   %cond = phi i32 [ 0, %entry ], [ %1, %cond.false ]
   ret i32 %cond
 }
 
 declare i32 @bar(i32)
 
 define void @unsigned_loop(i32 %i) {
 ; CHECK-LABEL: @unsigned_loop(
-; CHECK: @llvm.usub.with.overflow.i32
+; CHECK-NOT: @llvm.usub.with.overflow.i32
 entry:
   %cmp3 = icmp eq i32 %i, 0
   br i1 %cmp3, label %while.end, label %while.body.preheader
 
 while.body.preheader:                             ; preds = %entry
   br label %while.body
 
 while.body:                                       ; preds = %while.body.preheader, %cont