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
@@ -2009,6 +2009,12 @@
           canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))
     return V;
 
+  // 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
@@ -16,6 +16,7 @@
 #define LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/TargetFolder.h"
@@ -511,7 +512,7 @@
   Instruction *simplifyMaskedStore(IntrinsicInst &II);
   Instruction *simplifyMaskedGather(IntrinsicInst &II);
   Instruction *simplifyMaskedScatter(IntrinsicInst &II);
-  
+
   /// Transform (zext icmp) to bitwise / integer operations in order to
   /// eliminate it.
   ///
@@ -1000,6 +1001,52 @@
   Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
 };
 
+namespace {
+
+// As a default, let's assume that we want to be somewhat aggressive,
+// and attempt to traverse up to 32 layers in attempt to sink negation.
+static constexpr unsigned NegatorDefaultMaxDepth = 32;
+
+// Let's guesstimate that most often we will end up producing fairly small
+// number of new instructions.
+static constexpr unsigned NegatorMaxNewNodesSSO = 16;
+
+} // namespace
+
+class Negator final {
+  /// Top-to-bottom, def-to-use negated instruction tree we produced.
+  SmallVector<Instruction *, NegatorMaxNewNodesSSO> NewInstructions;
+
+  using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
+  BuilderTy Builder;
+
+  Negator(LLVMContext &C, const DataLayout &DL);
+
+#if LLVM_ENABLE_STATS
+  unsigned NumValuesVisitedInThisNegator = 0;
+  ~Negator();
+#endif
+
+  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,262 @@
+//===- InstCombineNegator.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 sinking of negation into expression trees,
+// as long as that can be done without increasing instruction count.
+//
+//===----------------------------------------------------------------------===//
+
+#include "InstCombineInternal.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/None.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/Analysis/TargetFolder.h"
+#include "llvm/IR/Constant.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DebugLoc.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/DebugCounter.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
+#include <functional>
+#include <utility>
+
+using namespace llvm;
+
+#define DEBUG_TYPE "instcombine"
+
+STATISTIC(NegatorTotalNegationsAttempted,
+          "Negator: Number 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(NegatorTimesDepthLimitReached,
+          "Negator: How many times did the traversal depth limit was reached "
+          "during sinking");
+STATISTIC(
+    NegatorNumValuesVisited,
+    "Negator: Total number of values visited during attempts to sink negation");
+STATISTIC(NegatorMaxTotalValuesVisited,
+          "Negator: Maximal number of values ever visited while attempting to "
+          "sink negation");
+STATISTIC(NegatorNumInstructionsCreatedTotal,
+          "Negator: Number of new negated instructions created, total");
+STATISTIC(NegatorMaxInstructionsCreated,
+          "Negator: Maximal number of new instructions created during negation "
+          "attempt");
+STATISTIC(NegatorNumInstructionsNegatedSuccess,
+          "Negator: Number of new negated instructions created in successful "
+          "negation sinking attempts");
+
+DEBUG_COUNTER(NegatorCounter, "instcombine-negator",
+              "Controls Negator transformations in InstCombine pass");
+
+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),
+              IRBuilderCallbackInserter([&](Instruction *I) {
+                ++NegatorNumInstructionsCreatedTotal;
+                NewInstructions.push_back(I);
+              })) {}
+
+#if LLVM_ENABLE_STATS
+Negator::~Negator() {
+  NegatorMaxTotalValuesVisited.updateMax(NumValuesVisitedInThisNegator);
+}
+#endif
+
+// 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);
+  ++NegatorNumValuesVisited;
+
+#if LLVM_ENABLE_STATS
+  ++NumValuesVisitedInThisNegator;
+#endif
+
+  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 uses, then give up.
+  if (!isa<Instruction>(V) || !V->hasOneUse())
+    return nullptr;
+
+  auto *I = cast<Instruction>(V);
+
+  // We must preserve the insertion point and debug info that is set in the
+  // builder at the time this function is called.
+  InstCombiner::BuilderTy::InsertPointGuard Guard(Builder);
+  // And since we are trying to negate instruction I, that tells us about the
+  // insertion point and the debug info that we need to keep.
+  Builder.SetInsertPoint(I);
+
+  // 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 not bother 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");
+    ++NegatorTimesDepthLimitReached;
+    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::Trunc: {
+    // `trunc` is negatible if its operand is negatible.
+    Value *NegOp = visit(I->getOperand(0), Depth + 1);
+    if (!NegOp) // Early return.
+      return nullptr;
+    return Builder.CreateTrunc(NegOp, I->getType(), I->getName() + ".neg");
+  }
+  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 its 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 if one of its 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) {
+    // We must cleanup newly-inserted instructions, to avoid any potential
+    // endless combine looping.
+    llvm::for_each(llvm::reverse(NewInstructions),
+                   [&](Instruction *I) { I->eraseFromParent(); });
+    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 || !DebugCounter::shouldExecute(NegatorCounter))
+    return nullptr;
+
+  Negator N(Root->getContext(), IC.getDataLayout());
+  Optional<Result> Res = N.run(Root);
+  if (!Res) { // Negation failed.
+    LLVM_DEBUG(dbgs() << "Negator: failed to sink negation into " << *Root
+                      << "\n");
+    return nullptr;
+  }
+
+  LLVM_DEBUG(dbgs() << "Negator: successfully sunk negation into " << *Root
+                    << "\n         NEW: " << *Res->second << "\n");
+  ++NegatorNumTreesNegated;
+
+  // We must temporarily unset the 'current' insertion point and DebugLoc of the
+  // InstCombine's IRBuilder so that it won't interfere with the ones we have
+  // already specified when producing negated instructions.
+  InstCombiner::BuilderTy::InsertPointGuard Guard(IC.Builder);
+  IC.Builder.ClearInsertionPoint();
+  IC.Builder.SetCurrentDebugLocation(DebugLoc());
+
+  // And finally, we must add newly-created instructions into the InstCombine's
+  // worklist (in a proper order!) so it can attempt to combine them.
+  LLVM_DEBUG(dbgs() << "Negator: Propagating " << Res->first.size()
+                    << " instrs to InstCombine\n");
+  NegatorMaxInstructionsCreated.updateMax(Res->first.size());
+  NegatorNumInstructionsNegatedSuccess += Res->first.size();
+
+  // They are in def-use order, so nothing fancy, just insert them in order.
+  llvm::for_each(Res->first, [&](Instruction *I) { 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
@@ -81,11 +81,11 @@
   ret i8 %t2
 }
 
-; Select can be negated if all it's operands can be negated and all the users of select can be updated
+; Select can be negated if all its 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
@@ -348,12 +348,12 @@
   ret i8 %n
 }
 
-; truncation can be negated if it's operand can be negated
+; truncation can be negated if its operand can be negated
 define i8 @t20(i8 %x, i16 %y) {
 ; CHECK-LABEL: @t20(
-; CHECK-NEXT:    [[T0:%.*]] = shl i16 -42, [[Y:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = trunc i16 [[T0]] to i8
-; CHECK-NEXT:    [[T2:%.*]] = sub i8 [[X:%.*]], [[T1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i16 42, [[Y:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = trunc i16 [[TMP1]] to i8
+; CHECK-NEXT:    [[T2:%.*]] = add i8 [[TMP2]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[T2]]
 ;
   %t0 = shl i16 -42, %y