Index: lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -1330,6 +1330,59 @@
   return nullptr;
 }
 
+static bool canInvertUsesOf(Value *V, InstCombiner &IC) {
+  // Handle trivial case.
+  if (V->hasOneUse())
+    return true;
+
+  // Bail out early for vector types, the code generator doesn't
+  // handle them well yet.
+  if (V->getType()->isVectorTy())
+    return false;
+
+  // Compares can be inverted if some of their uses are being modified to use
+  // the ~V.
+  if (!isa<CmpInst>(V) && !isa<BinaryOperator>(V))
+    return false;
+
+  // If `V` is of the form `A + Constant` then `-1 - V` can be folded into `(-1
+  // - Constant) - A` if we are willing to invert some of the uses.
+  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V)) {
+    // Must be an 'add' or a 'sub'.
+    if (BO->getOpcode() != Instruction::Add &&
+        BO->getOpcode() != Instruction::Sub)
+      return false;
+    // Atleast one operand must be a constant.
+    if (!isa<Constant>(BO->getOperand(0)) && !isa<Constant>(BO->getOperand(1)))
+      return false;
+  }
+
+  // Add subset of local users that can be inverted to a worklist.
+  // Bail out early if it is not safe to invert.
+  SmallVector<Instruction *, 4> UserInsts;
+  auto *Inst = cast<Instruction>(V);
+  for (auto *U : V->users()) {
+    if (!U->hasOneUse())
+      return false;
+    if (dyn_castNotVal(U->user_back())) {
+      auto *UI = dyn_cast<Instruction>(U);
+      if (UI && (UI->getParent() == Inst->getParent()))
+        UserInsts.push_back(UI);
+    }
+  }
+
+  if (UserInsts.empty())
+    return false;
+
+  for (auto *InvertedUse : UserInsts) {
+    Instruction *NewI = Inst->clone();
+    NewI->setName(Inst->getName() + ".invert");
+    IC.InsertNewInstBefore(NewI, *Inst);
+    InvertedUse->replaceUsesOfWith(Inst, NewI);
+  }
+  return true;
+}
+
 Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
@@ -2506,9 +2559,9 @@
         // ~(X & Y) --> (~X | ~Y) - De Morgan's Law
         // ~(X | Y) === (~X & ~Y) - De Morgan's Law
         if (IsFreeToInvert(Op0I->getOperand(0),
-                           Op0I->getOperand(0)->hasOneUse()) &&
+                           canInvertUsesOf(Op0I->getOperand(0), *this)) &&
             IsFreeToInvert(Op0I->getOperand(1),
-                           Op0I->getOperand(1)->hasOneUse())) {
+                           canInvertUsesOf(Op0I->getOperand(1), *this))) {
           Value *NotX =
             Builder->CreateNot(Op0I->getOperand(0), "notlhs");
           Value *NotY =
Index: test/Transforms/InstCombine/not2.ll
===================================================================
--- /dev/null
+++ test/Transforms/InstCombine/not2.ll
@@ -0,0 +1,111 @@
+; RUN: opt < %s -instcombine -S | FileCheck %s
+; CHECK-NOT: xor
+
+define void @test1(i32 %A, i32 %B, i32 %C) {
+entry:
+  %cmp = icmp sgt i32 %A, 0
+  %cmp1 = icmp sgt i32 %B, 0
+  %0 = and i1 %cmp, %cmp1
+  %lnot = xor i1 %0, true
+  %conv = zext i1 %lnot to i32
+  %cmp2 = icmp sgt i32 %C, 0
+  %1 = and i1 %cmp2, %cmp1
+  %lnot6 = xor i1 %1, true
+  %conv7 = zext i1 %lnot6 to i32
+  call void @foo(i32 %conv, i32 %conv7)
+  ret void
+}
+
+define void @test2(i32 %A, i32 %B, i32 %C) {
+entry:
+  %cmp = icmp sgt i32 %A, 0
+  %cmp1 = icmp sgt i32 %B, 0
+  %0 = and i1 %cmp, %cmp1
+  %lnot = xor i1 %0, true
+  %conv = zext i1 %lnot to i32
+  %cmp4 = icmp sgt i32 %C, 0
+  %1 = and i1 %cmp, %cmp4
+  %lnot6 = xor i1 %1, true
+  %conv7 = zext i1 %lnot6 to i32
+  call void @foo(i32 %conv, i32 %conv7)
+  ret void
+}
+
+define void @test3(i32 %A, i32 %B, i32 %C) {
+entry:
+  %cmp = icmp sgt i32 %A, 0
+  %cmp1 = icmp sgt i32 %B, 0
+  %0 = and i1 %cmp, %cmp1
+  %lnot = xor i1 %0, true
+  %conv = zext i1 %lnot to i32
+  %cmp4 = icmp sgt i32 %C, 0
+  %1 = and i1 %cmp, %cmp4
+  %lnot6 = xor i1 %1, true
+  %conv7 = zext i1 %lnot6 to i32
+  %2 = and i1 %cmp1, %cmp4
+  %lnot12 = xor i1 %2, true
+  %conv13 = zext i1 %lnot12 to i32
+  call void @bar(i32 %conv, i32 %conv7, i32 %conv13)
+  ret void
+}
+
+define void @test4(i32 %A, i32 %B, i32 %C) {
+entry:
+  %cmp = icmp sgt i32 %A, 0
+  %cmp1 = icmp sgt i32 %B, 0
+  %0 = and i1 %cmp, %cmp1
+  %lnot = xor i1 %0, true
+  %conv = zext i1 %lnot to i32
+  %cmp4 = icmp sgt i32 %C, 0
+  %1 = and i1 %cmp, %cmp4
+  %lnot6 = xor i1 %1, true
+  %conv7 = zext i1 %lnot6 to i32
+  %2 = and i1 %cmp1, %cmp4
+  %conv12 = zext i1 %2 to i32
+  call void @bar(i32 %conv, i32 %conv7, i32 %conv12)
+  ret void
+}
+
+define void @test5(i32 %A, i32 %B, i32 %C) {
+entry:
+  %cmp = icmp sgt i32 %A, 0
+  %cmp1 = icmp sgt i32 %B, 0
+  %0 = and i1 %cmp, %cmp1
+  %lnot = xor i1 %0, true
+  %conv = zext i1 %lnot to i32
+  %cmp4 = icmp sgt i32 %C, 0
+  %1 = and i1 %cmp, %cmp4
+  %lnot6 = xor i1 %1, true
+  %conv7 = zext i1 %lnot6 to i32
+  %cmp8 = icmp slt i32 %B, 1
+  %cmp10 = icmp slt i32 %C, 1
+  %2 = and i1 %cmp8, %cmp10
+  %conv12 = zext i1 %2 to i32
+  call void @bar(i32 %conv, i32 %conv7, i32 %conv12)
+  ret void
+}
+
+define void @test6(i32 %A, i32 %B, i32 %C, i32 %D) {
+entry:
+  %cmp = icmp sgt i32 %A, 0
+  %cmp1 = icmp sgt i32 %B, 0
+  %0 = and i1 %cmp, %cmp1
+  %lnot = xor i1 %0, true
+  %conv = zext i1 %lnot to i32
+  %cmp4 = icmp sgt i32 %C, 0
+  %1 = and i1 %cmp, %cmp4
+  %lnot6 = xor i1 %1, true
+  %conv7 = zext i1 %lnot6 to i32
+  %cmp10 = icmp sgt i32 %D, 0
+  %2 = and i1 %cmp, %cmp10
+  %conv12 = zext i1 %2 to i32
+  %3 = and i1 %cmp1, %cmp4
+  %lnot17 = xor i1 %3, true
+  %conv18 = zext i1 %lnot17 to i32
+  call void @baz(i32 %conv, i32 %conv7, i32 %conv12, i32 %conv18)
+  ret void
+}
+
+declare void @foo(i32, i32)
+declare void @bar(i32, i32, i32)
+declare void @baz(i32, i32, i32, i32)