diff --git a/llvm/lib/Transforms/InstCombine/CMakeLists.txt b/llvm/lib/Transforms/InstCombine/CMakeLists.txt
--- a/llvm/lib/Transforms/InstCombine/CMakeLists.txt
+++ b/llvm/lib/Transforms/InstCombine/CMakeLists.txt
@@ -12,6 +12,7 @@
   InstCombineCompares.cpp
   InstCombineLoadStoreAlloca.cpp
   InstCombineMulDivRem.cpp
+  InstCombineNegator.cpp
   InstCombinePHI.cpp
   InstCombineSelect.cpp
   InstCombineShifts.cpp
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
--- a/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
@@ -1900,6 +1900,12 @@
     return SelectInst::Create(Cmp, Neg, A);
   }
 
+  // Now that we know we have failed to fold this `sub a, b`, let's try to
+  // interpret `sub a, b` as `add a, (sub 0, b)`, and let's try to sink
+  // `(sub 0, b)` into b itself.
+  if (Value *NegOp1 = Negator::Negate(Op1, *this))
+    return BinaryOperator::CreateAdd(NegOp1, Op0);
+
   if (Instruction *Ext = narrowMathIfNoOverflow(I))
     return Ext;
 
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
--- a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
+++ b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
@@ -952,6 +952,63 @@
   Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
 };
 
+namespace {
+
+// As a default, let's assume that we want to be somewhat aggressive,
+// and attemt to traverse up to 16 layers in attempt to sink negation.
+static constexpr unsigned NegatorDefaultMaxDepth = 16;
+
+// Let's guesstimate that most often we will negate less than 8 layers of
+// binops (i.e. 2^8 == 256 instructions).
+static constexpr unsigned NegatorMaxNewNodesSSO = 256;
+
+/// Provides an 'InsertHelper' that calls a user-provided callback, but unlike
+/// the usual IRBuilderCallbackInserter does NOT perform the default insertion.
+class IRBuilderCallbackNoInsert {
+  std::function<void(Instruction *)> Callback;
+
+public:
+  IRBuilderCallbackNoInsert(std::function<void(Instruction *)> Callback)
+      : Callback(std::move(Callback)) {}
+
+protected:
+  void InsertHelper(Instruction *I, const Twine &Name, BasicBlock *BB,
+                    BasicBlock::iterator InsertPt) const {
+    Callback(I);
+  }
+};
+
+} // namespace
+
+class Negator final {
+  /// Top-to-bottom, def-to-use negated instruction tree we produced.
+  SmallVector<Instruction *, NegatorMaxNewNodesSSO> NewInstructions;
+
+  using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackNoInsert>;
+  BuilderTy Builder;
+
+  Negator(LLVMContext &C, const DataLayout &DL);
+
+  using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/,
+                           Value * /*NegatedRoot*/>;
+
+  LLVM_NODISCARD Value *visit(Value *V, unsigned Depth);
+
+  /// Recurse depth-first and attempt to sink the negation.
+  /// FIXME: use worklist?
+  LLVM_NODISCARD Optional<Result> run(Value *Root);
+
+  Negator(const Negator &) = delete;
+  Negator(Negator &&) = delete;
+  Negator &operator=(const Negator &) = delete;
+  Negator &operator=(Negator &&) = delete;
+
+public:
+  /// Attempt to negate \p Root. Retuns nullptr if negation can't be performed,
+  /// otherwise returns negated value.
+  LLVM_NODISCARD static Value *Negate(Value *Root, InstCombiner &IC);
+};
+
 } // end namespace llvm
 
 #undef DEBUG_TYPE
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp b/llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp
new file mode 100644
--- /dev/null
+++ b/llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp
@@ -0,0 +1,217 @@
+//===- InstCombineAddSub.cpp ------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements propagation of negation into expressions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "InstCombineInternal.h"
+#include "llvm/ADT/APFloat.h"
+#include "llvm/ADT/APInt.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/Constant.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/InstrTypes.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Operator.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Support/AlignOf.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/KnownBits.h"
+#include <cassert>
+#include <deque>
+#include <utility>
+
+using namespace llvm;
+
+#define DEBUG_TYPE "instcombine"
+
+STATISTIC(NegatorTotalNegationsAttempted,
+          "Negator: Numer of negations attempted to be sinked.");
+STATISTIC(NegatorNumTreesNegated,
+          "Negator: Number of negations successfully sinked.");
+STATISTIC(NegatorMaxDepthVisited, "Negator: Maximal traversal depth ever "
+                                  "reached while attempting to sink negation.");
+STATISTIC(NegatorDepthLimitReached, "Negator: How many times did the traversal "
+                                    "depth limit was reached during sinking.");
+STATISTIC(NegatorTotalValuesVisited, "Negator: Total number of values visited "
+                                     "during attempts to sink negation.");
+STATISTIC(NegatorNumInstructionsCreatedTotal,
+          "Negator: Number of new negated instructions created, total");
+STATISTIC(NegatorNumInstructionsNegatedSuccess,
+          "Negator: Number of new negated instructions created in successful "
+          "negation sinking attempts");
+
+static cl::opt<bool>
+    NegatorEnabled("instcombine-negator-enabled", cl::init(true),
+                   cl::desc("Should we attempt to sink negations?"));
+
+static cl::opt<unsigned>
+    NegatorMaxDepth("instcombine-negator-max-depth",
+                    cl::init(NegatorDefaultMaxDepth),
+                    cl::desc("What is the maximal lookup depth when trying to "
+                             "check for viability of negation sinking."));
+
+Negator::Negator(LLVMContext &C, const DataLayout &DL)
+    : Builder(C, TargetFolder(DL),
+              IRBuilderCallbackNoInsert([&](Instruction *I) {
+                ++NegatorNumInstructionsCreatedTotal;
+                NewInstructions.push_back(I);
+              })) {}
+
+// FIXME: can this be reworked into a worklist-based algorithm while preserving
+// the depth-first, early bailout traversal?
+LLVM_NODISCARD Value *Negator::visit(Value *V, unsigned Depth) {
+  NegatorMaxDepthVisited.updateMax(Depth);
+  ++NegatorTotalValuesVisited;
+
+  Value *X;
+
+  // -(-(X)) -> X.
+  if (match(V, m_Neg(m_Value(X))))
+    return X;
+
+  // Integral constants can be freely negated.
+  if (match(V, m_AnyIntegralConstant()))
+    return ConstantExpr::getNeg(cast<Constant>(V), /*HasNUW=*/false,
+                                /*HasNSW=*/false);
+
+  // If we have a non-instruction, or it has other usese, then give up.
+  if (!isa<Instruction>(V) || !V->hasOneUse())
+    return nullptr;
+
+  auto *I = cast<Instruction>(V);
+
+  // Preserve debug info!
+  Builder.SetCurrentDebugLocation(I->getDebugLoc());
+
+  // In some cases we can give the answer without further recursion.
+  switch (I->getOpcode()) {
+  case Instruction::PHI:
+    // `phi` is negatible if all the incoming values are negatible. We'd need to
+    // ensure that we won't deadloop (pr12338.ll), so let's bother not for now.
+    return nullptr;
+  case Instruction::Sub:
+    // `sub` is always negatible.
+    return Builder.CreateSub(I->getOperand(1), I->getOperand(0),
+                             I->getName() + ".neg");
+  default:
+    break; // Other instructions require recursive reasoning.
+  }
+
+  // Rest of the logic is recursive, so if it's time to give up then it's time.
+  if (Depth > NegatorMaxDepth) {
+    LLVM_DEBUG(dbgs() << "Negator: reached maximal allowed traversal depth in "
+                      << *V << ".  Giving up.\n");
+    ++NegatorDepthLimitReached;
+    return nullptr;
+  }
+
+  switch (I->getOpcode()) {
+  case Instruction::Select: {
+    // `select` is negatible if both hands of `select` are negatible.
+    Value *NegOp1 = visit(I->getOperand(1), Depth + 1);
+    if (!NegOp1) // Early return.
+      return nullptr;
+    Value *NegOp2 = visit(I->getOperand(2), Depth + 1);
+    if (!NegOp2)
+      return nullptr;
+    // Do preserve the metadata!
+    return Builder.CreateSelect(I->getOperand(0), NegOp1, NegOp2,
+                                I->getName() + ".neg", /*MDFrom=*/I);
+  }
+  case Instruction::Shl: {
+    // `shl` is negatible if the first operand is negatible.
+    Value *NegOp0 = visit(I->getOperand(0), Depth + 1);
+    if (!NegOp0) // Early return.
+      return nullptr;
+    return Builder.CreateShl(NegOp0, I->getOperand(1), I->getName() + ".neg");
+  }
+  case Instruction::Add: {
+    // `add` is negatible if both of it's operands are negatible.
+    Value *NegOp0 = visit(I->getOperand(0), Depth + 1);
+    if (!NegOp0) // Early return.
+      return nullptr;
+    Value *NegOp1 = visit(I->getOperand(1), Depth + 1);
+    if (!NegOp1)
+      return nullptr;
+    return Builder.CreateAdd(NegOp0, NegOp1, I->getName() + ".neg");
+  }
+  case Instruction::Mul: {
+    // `mul` is negatible one of it's operands is negatible.
+    Value *NegatedOp, *OtherOp;
+    if (Value *NegOp0 = visit(I->getOperand(0), Depth + 1)) {
+      NegatedOp = NegOp0;
+      OtherOp = I->getOperand(1);
+    } else if (Value *NegOp1 = visit(I->getOperand(1), Depth + 1)) {
+      NegatedOp = NegOp1;
+      OtherOp = I->getOperand(0);
+    } else // Can't negate either of them.
+      return nullptr;
+    return Builder.CreateMul(NegatedOp, OtherOp, I->getName() + ".neg");
+  }
+  default:
+    return nullptr; // Don't know, likely not negatible for free.
+  }
+
+  llvm_unreachable("Can't get here. We always return from switch.");
+};
+
+LLVM_NODISCARD Optional<Negator::Result> Negator::run(Value *Root) {
+  Value *Negated = visit(Root, /*Depth=*/0);
+  if (!Negated)
+    return llvm::None;
+  return std::make_pair(ArrayRef<Instruction *>(NewInstructions), Negated);
+};
+
+LLVM_NODISCARD Value *Negator::Negate(Value *Root, InstCombiner &IC) {
+  ++NegatorTotalNegationsAttempted;
+  LLVM_DEBUG(dbgs() << "Negator: attempting to sink negation into " << *Root
+                    << "\n");
+
+  if (!NegatorEnabled)
+    return nullptr;
+
+  Negator N(Root->getContext(), IC.getDataLayout());
+  Optional<Result> Res = N.run(Root);
+  if (!Res) // Negation failed.
+    return nullptr;
+
+  LLVM_DEBUG(dbgs() << "Negator: successfully sunk negation into " << *Root
+                    << "\n         NEW: " << *Res->second << "\n");
+  ++NegatorNumTreesNegated;
+
+  // We must temporairly unset the 'current' DebugLoc of the InstCombine's
+  // IRBuilder so that it won't override the DebugLoc's we have already kept
+  // from the original instructions.
+  InstCombiner::BuilderTy::InsertPointGuard Guard(IC.Builder);
+  IC.Builder.SetCurrentDebugLocation(DebugLoc());
+
+  // We must propagate newly-created instructions into the InstCombine's
+  // IRBuilder so that they will finally be inserted into the basic block,
+  // and into the InstCombine's worklist so it can attempt to combine them.
+  LLVM_DEBUG(dbgs() << "Negator: Propagating " << Res->first.size()
+                    << " instrs to InstCombine\n");
+
+  // They are in def-use order, so nothing fancy, just insert them in order.
+  llvm::for_each(Res->first, [&](Instruction *I) {
+    ++NegatorNumInstructionsNegatedSuccess;
+    IC.Builder.Insert(I);
+  });
+
+  // And return the new root.
+  return Res->second;
+};
diff --git a/llvm/test/Transforms/InstCombine/mul.ll b/llvm/test/Transforms/InstCombine/mul.ll
--- a/llvm/test/Transforms/InstCombine/mul.ll
+++ b/llvm/test/Transforms/InstCombine/mul.ll
@@ -456,10 +456,9 @@
 
 define i32 @test_mul_canonicalize_op1(i32 %x, i32 %z) {
 ; CHECK-LABEL: @test_mul_canonicalize_op1(
-; CHECK-NEXT:    [[Y:%.*]] = mul i32 [[Z:%.*]], 3
-; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[Y]], [[X:%.*]]
-; CHECK-NEXT:    [[MUL:%.*]] = sub i32 0, [[TMP1]]
-; CHECK-NEXT:    ret i32 [[MUL]]
+; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[Z:%.*]], -3
+; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP1]], [[X:%.*]]
+; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %y = mul i32 %z, 3
   %neg = sub i32 0, %x
diff --git a/llvm/test/Transforms/InstCombine/sub-of-negatible.ll b/llvm/test/Transforms/InstCombine/sub-of-negatible.ll
--- a/llvm/test/Transforms/InstCombine/sub-of-negatible.ll
+++ b/llvm/test/Transforms/InstCombine/sub-of-negatible.ll
@@ -30,8 +30,8 @@
 ; Shift-left can be negated if all uses can be updated
 define i8 @t2(i8 %x, i8 %y) {
 ; CHECK-LABEL: @t2(
-; CHECK-NEXT:    [[T0:%.*]] = shl i8 -42, [[Y:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = sub i8 [[X:%.*]], [[T0]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 42, [[Y:%.*]]
+; CHECK-NEXT:    [[T1:%.*]] = add i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[T1]]
 ;
   %t0 = shl i8 -42, %y
@@ -54,8 +54,8 @@
 ; CHECK-LABEL: @t3(
 ; CHECK-NEXT:    [[T0:%.*]] = sub i8 0, [[Z:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = shl i8 [[T0]], [[Y:%.*]]
-; CHECK-NEXT:    [[T2:%.*]] = sub i8 [[X:%.*]], [[T1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 [[Z]], [[Y:%.*]]
+; CHECK-NEXT:    [[T2:%.*]] = add i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[T2]]
 ;
   %t0 = sub i8 0, %z
@@ -84,8 +84,8 @@
 ; Select can be negated if all it's operands can be negated and all the users of select can be updated
 define i8 @t4(i8 %x, i1 %y) {
 ; CHECK-LABEL: @t4(
-; CHECK-NEXT:    [[T0:%.*]] = select i1 [[Y:%.*]], i8 -42, i8 44
-; CHECK-NEXT:    [[T1:%.*]] = sub i8 [[X:%.*]], [[T0]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[Y:%.*]], i8 42, i8 -44
+; CHECK-NEXT:    [[T1:%.*]] = add i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[T1]]
 ;
   %t0 = select i1 %y, i8 -42, i8 44
@@ -118,8 +118,8 @@
 ; CHECK-LABEL: @t6(
 ; CHECK-NEXT:    [[T0:%.*]] = sub i8 0, [[Z:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = select i1 [[Y:%.*]], i8 -42, i8 [[T0]]
-; CHECK-NEXT:    [[T2:%.*]] = sub i8 [[X:%.*]], [[T1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[Y:%.*]], i8 42, i8 [[Z]]
+; CHECK-NEXT:    [[T2:%.*]] = add i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[T2]]
 ;
   %t0 = sub i8 0, %z
@@ -130,9 +130,9 @@
 }
 define i8 @t7(i8 %x, i1 %y, i8 %z) {
 ; CHECK-LABEL: @t7(
-; CHECK-NEXT:    [[T0:%.*]] = shl i8 1, [[Z:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = select i1 [[Y:%.*]], i8 0, i8 [[T0]]
-; CHECK-NEXT:    [[T2:%.*]] = sub i8 [[X:%.*]], [[T1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 -1, [[Z:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[Y:%.*]], i8 0, i8 [[TMP1]]
+; CHECK-NEXT:    [[T2:%.*]] = add i8 [[TMP2]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[T2]]
 ;
   %t0 = shl i8 1, %z
@@ -156,50 +156,27 @@
 }
 
 ; Subtraction can be negated if the first operand can be negated
-; x - (y - z) -> x - y + z -> x + (-y) + z
-define i8 @t9(i8 %x, i8 %y, i8 %z) {
+; x - (y - z) -> x - y + z -> x + (z - y)
+define i8 @t9(i8 %x, i8 %y) {
 ; CHECK-LABEL: @t9(
-; CHECK-NEXT:    [[T0:%.*]] = sub i8 0, [[Z:%.*]]
-; CHECK-NEXT:    call void @use8(i8 [[T0]])
-; CHECK-NEXT:    [[T11:%.*]] = add i8 [[Y:%.*]], [[Z]]
-; CHECK-NEXT:    [[T2:%.*]] = add i8 [[T11]], [[X:%.*]]
-; CHECK-NEXT:    ret i8 [[T2]]
+; CHECK-NEXT:    [[T01:%.*]] = sub i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    ret i8 [[T01]]
 ;
-  %t0 = sub i8 0, %z
-  call void @use8(i8 %t0)
-  %t1 = sub i8 %t0, %y
-  %t2 = sub i8 %x, %t1
-  ret i8 %t2
+  %t0 = sub i8 %y, %x
+  %t1 = sub i8 0, %t0
+  ret i8 %t1
 }
 define i8 @n10(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @n10(
-; CHECK-NEXT:    [[T0:%.*]] = sub i8 0, [[Z:%.*]]
+; CHECK-NEXT:    [[T0:%.*]] = sub i8 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = sub i8 [[T0]], [[Y:%.*]]
-; CHECK-NEXT:    call void @use8(i8 [[T1]])
-; CHECK-NEXT:    [[T2:%.*]] = sub i8 [[X:%.*]], [[T1]]
-; CHECK-NEXT:    ret i8 [[T2]]
+; CHECK-NEXT:    [[T1:%.*]] = sub i8 0, [[T0]]
+; CHECK-NEXT:    ret i8 [[T1]]
 ;
-  %t0 = sub i8 0, %z
+  %t0 = sub i8 %y, %x
   call void @use8(i8 %t0)
-  %t1 = sub i8 %t0, %y
-  call void @use8(i8 %t1)
-  %t2 = sub i8 %x, %t1
-  ret i8 %t2
-}
-define i8 @n11(i8 %x, i8 %y, i8 %z) {
-; CHECK-LABEL: @n11(
-; CHECK-NEXT:    [[T0:%.*]] = sub i8 0, [[Z:%.*]]
-; CHECK-NEXT:    call void @use8(i8 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = add i8 [[Y:%.*]], [[Z]]
-; CHECK-NEXT:    [[T2:%.*]] = sub i8 [[X:%.*]], [[T1]]
-; CHECK-NEXT:    ret i8 [[T2]]
-;
-  %t0 = sub i8 0, %z
-  call void @use8(i8 %t0)
-  %t1 = sub i8 %y, %t0
-  %t2 = sub i8 %x, %t1
-  ret i8 %t2
+  %t1 = sub i8 0, %t0
+  ret i8 %t1
 }
 
 ; Addition can be negated if both operands can be negated
@@ -290,3 +267,83 @@
   %t2 = sub i8 %x, %t1
   ret i8 %t2
 }
+
+; Phi can be negated if all incoming values can be negated
+define i8 @t16(i1 %c, i8 %x) {
+; CHECK-LABEL: @t16(
+; CHECK-NEXT:  begin:
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK:       else:
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    [[Z:%.*]] = phi i8 [ [[X:%.*]], [[THEN]] ], [ 42, [[ELSE]] ]
+; CHECK-NEXT:    ret i8 [[Z]]
+;
+begin:
+  br i1 %c, label %then, label %else
+then:
+  %y = sub i8 0, %x
+  br label %end
+else:
+  br label %end
+end:
+  %z = phi i8 [ %y, %then], [ -42, %else ]
+  %n = sub i8 0, %z
+  ret i8 %n
+}
+define i8 @n17(i1 %c, i8 %x) {
+; CHECK-LABEL: @n17(
+; CHECK-NEXT:  begin:
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[Y:%.*]] = sub i8 0, [[X:%.*]]
+; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK:       else:
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    [[Z:%.*]] = phi i8 [ [[Y]], [[THEN]] ], [ -42, [[ELSE]] ]
+; CHECK-NEXT:    call void @use8(i8 [[Z]])
+; CHECK-NEXT:    [[N:%.*]] = sub i8 0, [[Z]]
+; CHECK-NEXT:    ret i8 [[N]]
+;
+begin:
+  br i1 %c, label %then, label %else
+then:
+  %y = sub i8 0, %x
+  br label %end
+else:
+  br label %end
+end:
+  %z = phi i8 [ %y, %then], [ -42, %else ]
+  call void @use8(i8 %z)
+  %n = sub i8 0, %z
+  ret i8 %n
+}
+define i8 @n19(i1 %c, i8 %x, i8 %y) {
+; CHECK-LABEL: @n19(
+; CHECK-NEXT:  begin:
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[Z:%.*]] = sub i8 0, [[X:%.*]]
+; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK:       else:
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    [[R:%.*]] = phi i8 [ [[Z]], [[THEN]] ], [ [[Y:%.*]], [[ELSE]] ]
+; CHECK-NEXT:    [[N:%.*]] = sub i8 0, [[R]]
+; CHECK-NEXT:    ret i8 [[N]]
+;
+begin:
+  br i1 %c, label %then, label %else
+then:
+  %z = sub i8 0, %x
+  br label %end
+else:
+  br label %end
+end:
+  %r = phi i8 [ %z, %then], [ %y, %else ]
+  %n = sub i8 0, %r
+  ret i8 %n
+}