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,27 @@
     return SelectInst::Create(Cmp, Neg, A);
   }
 
+  // Now that we know we have failed to fold this `sub a, b`, iff `a != 0`,
+  // let's see if it's worth exploding it into `add a, (sub 0, b)`.
+  // It is worth doing if the negation can be sunk into `b`.
+  if (!match(Op0, m_Zero()) && isFreeToNegate(Op1)) {
+    // While this does temporairly increase instruction count, we have ensured
+    // that this `neg` will get absorbed into Op1, so this is ok.
+    Instruction *NegOp1 =
+        BinaryOperator::CreateNeg(Op1, Op1->getName() + ".neg");
+    Instruction *NewAdd = BinaryOperator::CreateAdd(NegOp1, Op0);
+    // Normally, the `neg` would have been added to InstCombine's WorkList
+    // first, and then the `add`. So we'd first revisit `add`, but we just made
+    // it so that one of the `add`s operands is `neg`, so it would hoist that
+    // `neg` and recreate subtraction, and we'll endlessly loop...
+    // Instead, let's manually first add the `add` and *then* `neg`, this way
+    // we will first visit the `neg`, and go on folding it into it's operand.
+    Worklist.Add(NewAdd);
+    Worklist.Add(NegOp1);
+    Builder.Insert(NegOp1);
+    return NewAdd;
+  }
+
   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
@@ -199,6 +199,61 @@
   return true; // Can freely invert all users!
 }
 
+/// Return true if the specified value is free to negate (subtract from 0).
+/// This happens in cases where the 0 can be eliminated.
+/// For instructions, this is limited to single-use instructions.
+/// The analysis is recursive.
+static inline bool isFreeToNegate(Value *V, unsigned Depth = 0) {
+  // -(-(X)) -> X.
+  if (match(V, m_Neg(m_Value())))
+    return true;
+
+  // Constants can be considered to be negated values.
+  if (match(V, m_AnyIntegralConstant()))
+    return true;
+
+  // Rest of the checking is recursive, so time to pessimistically bailout.
+  if (Depth > 6)
+    return false;
+
+  // If we have a non-instruction, and it's not a constant, then give up.
+  if (!isa<Instruction>(V))
+    return false;
+  // The instruction-in-question must be one-use.
+  if (!V->hasOneUse())
+    return false;
+
+  auto *I = cast<Instruction>(V);
+  switch (I->getOpcode()) {
+  case Instruction::Select:
+    // `select` is negatible if both hands of select are negatible.
+    return isFreeToNegate(I->getOperand(1), Depth + 1) &&
+           isFreeToNegate(I->getOperand(2), Depth + 1);
+  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 not.
+    return false;
+  case Instruction::Shl:
+    // `shl` is negatible if the first operand is negatible.
+    return isFreeToNegate(I->getOperand(0), Depth + 1);
+  case Instruction::Sub:
+    // `sub` is always negatible.
+    return true;
+  case Instruction::Add:
+    // `add` is negatible if both of it's operands are negatible.
+    return isFreeToNegate(I->getOperand(0), Depth + 1) &&
+           isFreeToNegate(I->getOperand(1), Depth + 1);
+  case Instruction::Mul:
+    // `mul` is negatible one of it's operands is negatible.
+    return isFreeToNegate(I->getOperand(0), Depth + 1) ||
+           isFreeToNegate(I->getOperand(1), Depth + 1);
+  default:
+    return false; // Don't know, likely not negatible for free.
+  }
+
+  return false;
+}
+
 /// Some binary operators require special handling to avoid poison and undefined
 /// behavior. If a constant vector has undef elements, replace those undefs with
 /// identity constants if possible because those are always safe to execute.
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:    [[T0_OP:%.*]] = shl i8 -1, [[Z:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[Y:%.*]], i8 0, i8 [[T0_OP]]
+; CHECK-NEXT:    [[T2:%.*]] = add i8 [[TMP1]], [[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
+}