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

[jgalenson]

Summary

This adds logic to CVP to remove some overflow checks. It uses LVI to remove operations with at least one constant. Specifically, this can remove many overflow intrinsics immediately following an overflow check in the source code, such as:

if (x < INT_MAX)

... x + 1 ...

[jgalenson]

Bugfix.

[sanjoy]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

350 ↗

(On Diff #121768)

This case should be getting constant folded. If it isn't, that's an InstCombine bug. Once you remove this, you can just directly have the second switch.

355 ↗

(On Diff #121768)

We should be canonicalizing commutative ops so that if there is a constant operand it is the RHS (if not, that's again an instcombine bugs).

376 ↗

(On Diff #121768)

Can you avoid doing this stuff by hand by using the LazyValueInfo::getConstantRange and the ConstantRange::makeGuaranteedNoWrapRegion APIs?

[jgalenson]

Thanks for the comments. As you suggested, I removed the unnecessary checks.

The new API is indeed cleaner, but it only works for addition. Modifying it to support other operations might be useful, bit I figured that could be a separate commit if necessary.

[sanjoy]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

329 ↗

(On Diff #121966)

I'd call this willNotOverflow instead, since that's what this is computing.

382 ↗

(On Diff #121966)

I'd avoid adding this kind of logic here. Instead I think the right factoring is to start off by doing what ConstantRange lets us do today (i.e. sadd and uadd) and then improving ConstantRange to handle the subtraction (and other) cases you're interested in. Putting this logic in ConstantRange will make it more likely that the code is re-used (besides making it easier to test).

[jgalenson]

I've done the rename, although I'll note that I slightly prefer the old name since it makes it obvious that the function only applies to overflow intrinsics, not any intrinsic.

As for changing ConstantRange, as I said before, I agree that should be done, but it seems to me like it should be done in a separate commit. Once we have that, we should add a processSub (like processAdd), and we should add multiplication and division in all the places, but keeping focused commits seems like a better strategy to me.

[sanjoy]

In D39483#919529, @jgalenson wrote:

I've done the rename, although I'll note that I slightly prefer the old name since it makes it obvious that the function only applies to overflow intrinsics, not any intrinsic.

If you think the previous name was better I'm ok with that.

As for changing ConstantRange, as I said before, I agree that should be done, but it seems to me like it should be done in a separate commit. Once we have that, we should add a processSub (like processAdd), and we should add multiplication and division in all the places, but keeping focused commits seems like a better strategy to me.

I'm not suggesting you change ConstantRange in this commit (that indeed is not a great idea). I'm suggesting that instead of adding a bunch of logic here only to move it to ConstantRange in a later commit, how about:

• Commit0: Only process uadd and sadd in CVP with ConstantRange::makeGuaranteedNoWrapRegion.
• Commit1: Teach makeGuaranteedNoWrapRegion about usub and ssub
• Commit2: Use Commit1 to process ssub and usub in CVP
• ...

If anything, the sequence above will make the commits even more focussed. I hope I made sense.

[jgalenson]

If you think the previous name was better I'm ok with that.

I don't have a strong preference, so I'll keep yours.

I'm not suggesting you change ConstantRange in this commit (that indeed is not a great idea). I'm suggesting that instead of adding a bunch of logic here only to move it to ConstantRange in a later commit, how about:

• Commit0: Only process uadd and sadd in CVP with ConstantRange::makeGuaranteedNoWrapRegion.
• Commit1: Teach makeGuaranteedNoWrapRegion about usub and ssub
• Commit2: Use Commit1 to process ssub and usub in CVP
• ...

If anything, the sequence above will make the commits even more focussed. I hope I made sense.

Ah, sorry, I misunderstood you. Looks like we agree. :) I'll do that.

By the way, I would also like to get this code to handle non-constant arithmetic for cases such as:

if (x >= y)

.. x - y ...

But that's even harder, so I'll leave it for later.

[sanjoy]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

333 ↗

(On Diff #122112)

I don't think you need this either -- you can just directly go to the switch below.

337 ↗

(On Diff #122112)

How about calling this NoWrapOnAddition ?

351 ↗

(On Diff #122112)

You don't need these anymore.

364 ↗

(On Diff #122112)

process is too vague -- how about eraseOverflowIntrinsic?

test/Transforms/CorrelatedValuePropagation/overflows.ll

183 ↗

(On Diff #122112)

Typical idiom is to use CHECK-LABEL for the function name, as:

; CHECK-LABEL: @unsigned_add_r1(
; CHECK-NOT: ...

[jgalenson]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

364 ↗

(On Diff #122112)

I actually think process is better here because it mirrors all the other functions in this file (processCallSite, processSRem, etc).

[jgalenson]

I suppose I could pull this lambda out into a static function....

[jgalenson]

Added a statistic.

[sanjoy]

LGTM

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

359 ↗

(On Diff #122340)

Super-minor nit: s/Illegal/Unexpected/

[jgalenson]

Thanks! Could you commit this for me?

I'll make that nit change in the follow-up commit that handles sub.

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

 #include "llvm/IR/Constant.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"

 STATISTIC(NumSelects,   "Number of selects propagated");
 STATISTIC(NumMemAccess, "Number of memory access targets propagated");
 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(NumAShrs,     "Number of ashr converted to lshr");
 STATISTIC(NumSRems,     "Number of srem converted to urem");
+STATISTIC(NumOverflows, "Number of overflow checks removed");
 
 static cl::opt<bool> DontProcessAdds("cvp-dont-process-adds", cl::init(true));
 
 namespace {
 
   class CorrelatedValuePropagation : public FunctionPass {
   public:
     static char ID;
static bool processSwitch(SwitchInst *SI, LazyValueInfo *LVI) {
   if (Changed)
     // If the switch has been simplified to the point where it can be replaced
     // by a branch then do so now.
     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) {
+    ConstantRange RRange = LVI->getConstantRange(RHS, II->getParent(), II);
+    ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
+        BinaryOperator::Add, RRange, NoWrapKind);
+    // As an optimization, do not compute LRange if we do not need it.
+    if (NWRegion.isEmptySet())
+      return false;
+    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);
+  case Intrinsic::sadd_with_overflow:
+    return NoWrapOnAddition(II->getOperand(0), II->getOperand(1),
+                            OBO::NoSignedWrap);
+  }
+  return false;
+}
+
+static void processOverflowIntrinsic(IntrinsicInst *II) {
+  Value *NewOp = nullptr;
+  switch (II->getIntrinsicID()) {
+  default:
+    llvm_unreachable("Illegal instruction.");
+  case Intrinsic::uadd_with_overflow:
+  case Intrinsic::sadd_with_overflow:
+    NewOp = BinaryOperator::CreateAdd(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 (willNotOverflow(II, LVI)) {
+      processOverflowIntrinsic(II);
+      return true;
+    }
+  }
+
   for (Value *V : CS.args()) {
     PointerType *Type = dyn_cast<PointerType>(V->getType());
     // Try to mark pointer typed parameters as non-null.  We skip the
     // relatively expensive analysis for constants which are obviously either
     // null or non-null to start with.
     if (Type && !CS.paramHasAttr(ArgNo, Attribute::NonNull) &&
         !isa<Constant>(V) && 
         LVI->getPredicateAt(ICmpInst::ICMP_EQ, V,

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: @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
+  br i1 %1, label %trap, label %cont
+
+trap:                                             ; preds = %land.lhs.true, %land.lhs.true3, %cond.false
+  tail call void @llvm.trap()
+  unreachable
+
+cont:                                             ; preds = %land.lhs.true
+  %2 = extractvalue { i32, i1 } %0, 0
+  %cmp1 = icmp slt i32 %2, %x
+  br i1 %cmp1, label %cond.end, label %cond.false
+
+lor.lhs.false:                                    ; preds = %entry
+  %cmp2 = icmp slt i32 %y, 0
+  br i1 %cmp2, label %land.lhs.true3, label %cond.false
+
+land.lhs.true3:                                   ; preds = %lor.lhs.false
+  %3 = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 -2147483648, i32 %y)
+  %4 = extractvalue { i32, i1 } %3, 1
+  br i1 %4, label %trap, label %cont4
+
+cont4:                                            ; preds = %land.lhs.true3
+  %5 = extractvalue { i32, i1 } %3, 0
+  %cmp5 = icmp sgt i32 %5, %x
+  br i1 %cmp5, label %cond.end, label %cond.false
+
+cond.false:                                       ; preds = %cont, %cont4, %lor.lhs.false
+  %6 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %x, i32 %y)
+  %7 = extractvalue { i32, i1 } %6, 0
+  %8 = extractvalue { i32, i1 } %6, 1
+  br i1 %8, label %trap, label %cond.end
+
+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: @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()
+  unreachable
+
+cont:                                             ; preds = %entry
+  %2 = extractvalue { i32, i1 } %0, 0
+  %cmp1 = icmp ult i32 %2, %x
+  br i1 %cmp1, label %cond.end, label %cond.false
+
+cond.false:                                       ; preds = %cont
+  %3 = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %x, i32 %y)
+  %4 = extractvalue { i32, i1 } %3, 0
+  %5 = extractvalue { i32, i1 } %3, 1
+  br i1 %5, label %trap, label %cond.end
+
+cond.end:                                         ; preds = %cond.false, %cont
+  %cond = phi i32 [ 0, %cont ], [ %4, %cond.false ]
+  ret i32 %cond
+}
+
+define i32 @signed_sub(i32 %x, i32 %y) {
+; CHECK-LABEL: @signed_sub(
+; CHECK-NOT: @llvm.sadd.with.overflow.i32
+; CHECK: @llvm.ssub.with.overflow.i32
+entry:
+  %cmp = icmp slt 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.sadd.with.overflow.i32(i32 %y, i32 2147483647)
+  %1 = extractvalue { i32, i1 } %0, 1
+  br i1 %1, label %trap, label %cont
+
+trap:                                             ; preds = %land.lhs.true, %land.lhs.true3, %cond.false
+  tail call void @llvm.trap()
+  unreachable
+
+cont:                                             ; preds = %land.lhs.true
+  %2 = extractvalue { i32, i1 } %0, 0
+  %cmp1 = icmp slt i32 %2, %x
+  br i1 %cmp1, label %cond.end, label %cond.false
+
+lor.lhs.false:                                    ; preds = %entry
+  %cmp2 = icmp eq i32 %y, 0
+  br i1 %cmp2, label %cond.false, label %land.lhs.true3
+
+land.lhs.true3:                                   ; preds = %lor.lhs.false
+  %3 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %y, i32 -2147483648)
+  %4 = extractvalue { i32, i1 } %3, 1
+  br i1 %4, label %trap, label %cont4
+
+cont4:                                            ; preds = %land.lhs.true3
+  %5 = extractvalue { i32, i1 } %3, 0
+  %cmp5 = icmp sgt i32 %5, %x
+  br i1 %cmp5, label %cond.end, label %cond.false
+
+cond.false:                                       ; preds = %lor.lhs.false, %cont, %cont4
+  %6 = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %x, i32 %y)
+  %7 = extractvalue { i32, i1 } %6, 0
+  %8 = extractvalue { i32, i1 } %6, 1
+  br i1 %8, label %trap, label %cond.end
+
+cond.end:                                         ; preds = %cond.false, %cont, %cont4
+  %cond = phi i32 [ 0, %cont4 ], [ 0, %cont ], [ %7, %cond.false ]
+  ret i32 %cond
+}
+
+define i32 @unsigned_sub(i32 %x, i32 %y) {
+; CHECK-LABEL: @unsigned_sub(
+; CHECK: @llvm.usub.with.overflow.i32
+entry:
+  %cmp = icmp ult i32 %x, %y
+  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 %y)
+  %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 @signed_add_r1(i32 %x) {
+; CHECK-LABEL: @signed_add_r1(
+; CHECK-NOT: @llvm.sadd.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.sadd.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_add_r1(i32 %x) {
+; CHECK-LABEL: @unsigned_add_r1(
+; CHECK-NOT: @llvm.uadd.with.overflow.i32
+entry:
+  %cmp = icmp eq i32 %x, -1
+  br i1 %cmp, label %cond.end, label %cond.false
+
+cond.false:                                       ; preds = %entry
+  %0 = tail call { i32, i1 } @llvm.uadd.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 @signed_sub_r1(i32 %x) {
+; CHECK-LABEL: @signed_sub_r1(
+; CHECK: @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
+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
+  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 @signed_add_rn1(i32 %x) {
+; CHECK-LABEL: @signed_add_rn1(
+; CHECK-NOT: @llvm.sadd.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.sadd.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 @signed_sub_rn1(i32 %x) {
+; CHECK-LABEL: @signed_sub_rn1(
+; CHECK: @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
+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
+  %i.addr.04 = phi i32 [ %2, %cont ], [ %i, %while.body.preheader ]
+  %call = tail call i32 @bar(i32 %i.addr.04)
+  %0 = tail call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %i.addr.04, i32 1)
+  %1 = extractvalue { i32, i1 } %0, 1
+  br i1 %1, label %trap, label %cont
+
+trap:                                             ; preds = %while.body
+  tail call void @llvm.trap()
+  unreachable
+
+cont:                                             ; preds = %while.body
+  %2 = extractvalue { i32, i1 } %0, 0
+  %cmp = icmp eq i32 %2, 0
+  br i1 %cmp, label %while.end, label %while.body
+
+while.end:                                        ; preds = %cont, %entry
+  ret void
+}
+
+define void @intrinsic_into_phi(i32 %n) {
+; CHECK-LABEL: @intrinsic_into_phi(
+; CHECK: @llvm.sadd.with.overflow.i32
+; CHECK-NOT: @llvm.sadd.with.overflow.i32
+entry:
+  br label %cont
+
+for.cond:                                         ; preds = %while.end
+  %0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %.lcssa, i32 1)
+  %1 = extractvalue { i32, i1 } %0, 1
+  br i1 %1, label %trap, label %cont
+
+trap:                                             ; preds = %for.cond, %while.body
+  tail call void @llvm.trap()
+  unreachable
+
+cont:                                             ; preds = %entry, %for.cond
+  %2 = phi { i32, i1 } [ zeroinitializer, %entry ], [ %0, %for.cond ]
+  %3 = extractvalue { i32, i1 } %2, 0
+  %call9 = tail call i32 @bar(i32 %3)
+  %tobool10 = icmp eq i32 %call9, 0
+  br i1 %tobool10, label %while.end, label %while.body.preheader
+
+while.body.preheader:                             ; preds = %cont
+  br label %while.body
+
+while.cond:                                       ; preds = %while.body
+  %4 = extractvalue { i32, i1 } %6, 0
+  %call = tail call i32 @bar(i32 %4)
+  %tobool = icmp eq i32 %call, 0
+  br i1 %tobool, label %while.end, label %while.body
+
+while.body:                                       ; preds = %while.body.preheader, %while.cond
+  %5 = phi i32 [ %4, %while.cond ], [ %3, %while.body.preheader ]
+  %6 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %5, i32 1)
+  %7 = extractvalue { i32, i1 } %6, 1
+  br i1 %7, label %trap, label %while.cond
+
+while.end:                                        ; preds = %while.cond, %cont
+  %.lcssa = phi i32 [ %3, %cont ], [ %4, %while.cond ]
+  %cmp = icmp slt i32 %.lcssa, %n
+  br i1 %cmp, label %for.cond, label %cleanup2
+
+cleanup2:                                         ; preds = %while.end
+  ret void
+}