Index: lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -2452,6 +2452,26 @@
   return nullptr;
 }
 
+// Transform
+//   ~(x ^ y)
+// into:
+//   (~x) ^ y
+// or into
+//   x ^ (~y)
+static Instruction *sinkNotIntoXor(BinaryOperator &I,
+                                   InstCombiner::BuilderTy &Builder) {
+  Value *X, *Y;
+  if (!match(&I, m_Not(m_OneUse(m_Xor(m_Value(X), m_Value(Y))))))
+    return nullptr;
+
+  // If X is not free to invert, but Y is, then swap them.
+  if (!IsFreeToInvert(X, X->hasOneUse()) && IsFreeToInvert(Y, Y->hasOneUse()))
+    std::swap(X, Y);
+
+  Value *NotX = Builder.CreateNot(X, X->getName() + ".not");
+  return BinaryOperator::CreateXor(NotX, Y, I.getName() + ".demorgan");
+}
+
 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
 // here. We should standardize that construct where it is needed or choose some
 // other way to ensure that commutated variants of patterns are not missed.
@@ -2777,5 +2797,8 @@
     }
   }
 
+  if (Instruction *NewXor = sinkNotIntoXor(I, Builder))
+    return NewXor;
+
   return nullptr;
 }
Index: test/Transforms/InstCombine/and-or-not.ll
===================================================================
--- test/Transforms/InstCombine/and-or-not.ll
+++ test/Transforms/InstCombine/and-or-not.ll
@@ -80,8 +80,8 @@
 ; CHECK-LABEL: @and_to_nxor1(
 ; CHECK-NEXT:    [[A:%.*]] = fptosi float [[FA:%.*]] to i32
 ; CHECK-NEXT:    [[B:%.*]] = fptosi float [[FB:%.*]] to i32
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[B]]
-; CHECK-NEXT:    [[AND:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[A_NOT:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[AND:%.*]] = xor i32 [[A_NOT]], [[B]]
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %a = fptosi float %fa to i32
@@ -100,8 +100,8 @@
 ; CHECK-LABEL: @and_to_nxor2(
 ; CHECK-NEXT:    [[A:%.*]] = fptosi float [[FA:%.*]] to i32
 ; CHECK-NEXT:    [[B:%.*]] = fptosi float [[FB:%.*]] to i32
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[B]]
-; CHECK-NEXT:    [[AND:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[A_NOT:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[AND:%.*]] = xor i32 [[A_NOT]], [[B]]
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %a = fptosi float %fa to i32
@@ -120,8 +120,8 @@
 ; CHECK-LABEL: @and_to_nxor3(
 ; CHECK-NEXT:    [[A:%.*]] = fptosi float [[FA:%.*]] to i32
 ; CHECK-NEXT:    [[B:%.*]] = fptosi float [[FB:%.*]] to i32
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[A]]
-; CHECK-NEXT:    [[AND:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[B_NOT:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[AND:%.*]] = xor i32 [[B_NOT]], [[A]]
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %a = fptosi float %fa to i32
@@ -140,8 +140,8 @@
 ; CHECK-LABEL: @and_to_nxor4(
 ; CHECK-NEXT:    [[A:%.*]] = fptosi float [[FA:%.*]] to i32
 ; CHECK-NEXT:    [[B:%.*]] = fptosi float [[FB:%.*]] to i32
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[A]]
-; CHECK-NEXT:    [[AND:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[B_NOT:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[AND:%.*]] = xor i32 [[B_NOT]], [[A]]
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %a = fptosi float %fa to i32
@@ -234,8 +234,8 @@
 
 define i32 @or_to_nxor1(i32 %a, i32 %b) {
 ; CHECK-LABEL: @or_to_nxor1(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[A_NOT:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[OR2:%.*]] = xor i32 [[A_NOT]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[OR2]]
 ;
   %and = and i32 %a, %b
@@ -249,8 +249,8 @@
 
 define i32 @or_to_nxor2(i32 %a, i32 %b) {
 ; CHECK-LABEL: @or_to_nxor2(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[A_NOT:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[OR2:%.*]] = xor i32 [[A_NOT]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[OR2]]
 ;
   %and = and i32 %a, %b
@@ -264,8 +264,8 @@
 
 define i32 @or_to_nxor3(i32 %a, i32 %b) {
 ; CHECK-LABEL: @or_to_nxor3(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[A_NOT:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[OR2:%.*]] = xor i32 [[A_NOT]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[OR2]]
 ;
   %and = and i32 %a, %b
@@ -279,8 +279,8 @@
 
 define i32 @or_to_nxor4(i32 %a, i32 %b) {
 ; CHECK-LABEL: @or_to_nxor4(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[B_NOT:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[OR2:%.*]] = xor i32 [[B_NOT]], [[A:%.*]]
 ; CHECK-NEXT:    ret i32 [[OR2]]
 ;
   %and = and i32 %b, %a
@@ -570,8 +570,8 @@
 ; CHECK-LABEL: @xor_to_xnor1(
 ; CHECK-NEXT:    [[A:%.*]] = fptosi float [[FA:%.*]] to i32
 ; CHECK-NEXT:    [[B:%.*]] = fptosi float [[FB:%.*]] to i32
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[B]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[A_NOT:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[A_NOT]], [[B]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %a = fptosi float %fa to i32
@@ -589,8 +589,8 @@
 ; CHECK-LABEL: @xor_to_xnor2(
 ; CHECK-NEXT:    [[A:%.*]] = fptosi float [[FA:%.*]] to i32
 ; CHECK-NEXT:    [[B:%.*]] = fptosi float [[FB:%.*]] to i32
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[B]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[A_NOT:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[A_NOT]], [[B]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %a = fptosi float %fa to i32
@@ -608,8 +608,8 @@
 ; CHECK-LABEL: @xor_to_xnor3(
 ; CHECK-NEXT:    [[A:%.*]] = fptosi float [[FA:%.*]] to i32
 ; CHECK-NEXT:    [[B:%.*]] = fptosi float [[FB:%.*]] to i32
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[B]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[A_NOT:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[A_NOT]], [[B]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %a = fptosi float %fa to i32
@@ -627,8 +627,8 @@
 ; CHECK-LABEL: @xor_to_xnor4(
 ; CHECK-NEXT:    [[A:%.*]] = fptosi float [[FA:%.*]] to i32
 ; CHECK-NEXT:    [[B:%.*]] = fptosi float [[FB:%.*]] to i32
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[A]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[B_NOT:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[B_NOT]], [[A]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %a = fptosi float %fa to i32
Index: test/Transforms/InstCombine/demorgan-sink-not-into-xor.ll
===================================================================
--- test/Transforms/InstCombine/demorgan-sink-not-into-xor.ll
+++ test/Transforms/InstCombine/demorgan-sink-not-into-xor.ll
@@ -20,8 +20,8 @@
 ; Just fold it into the first operand.
 define i32 @positive(i32 %x, i32 %y) {
 ; CHECK-LABEL: @positive(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[X_NOT:%.*]] = xor i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[X_NOT]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %tmp1 = xor i32 %x, %y
@@ -37,9 +37,8 @@
 define i1 @positive_easyinvert(i8 %y) {
 ; CHECK-LABEL: @positive_easyinvert(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i1 @gen1()
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i8 [[Y:%.*]], 0
-; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP3]], true
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i8 [[Y:%.*]], -1
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i1 [[TMP4]]
 ;
   %tmp1 = call i1 @gen1()
@@ -55,8 +54,8 @@
 
 define <2 x i32> @positive_vec(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @positive_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i32> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = xor <2 x i32> [[TMP1]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[X_NOT:%.*]] = xor <2 x i32> [[X:%.*]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[TMP2:%.*]] = xor <2 x i32> [[X_NOT]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i32> [[TMP2]]
 ;
   %tmp1 = xor <2 x i32> %x, %y
@@ -66,8 +65,8 @@
 
 define <3 x i32> @positive_vec_undef(<3 x i32> %x, <3 x i32> %y) {
 ; CHECK-LABEL: @positive_vec_undef(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor <3 x i32> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = xor <3 x i32> [[TMP1]], <i32 -1, i32 undef, i32 -1>
+; CHECK-NEXT:    [[X_NOT:%.*]] = xor <3 x i32> [[X:%.*]], <i32 -1, i32 -1, i32 -1>
+; CHECK-NEXT:    [[TMP2:%.*]] = xor <3 x i32> [[X_NOT]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <3 x i32> [[TMP2]]
 ;
   %tmp1 = xor <3 x i32> %x, %y
@@ -105,8 +104,8 @@
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i1 @gen1()
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i8 [[Y:%.*]], 0
 ; CHECK-NEXT:    call void @use1(i1 [[TMP2]])
-; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP3]], true
+; CHECK-NEXT:    [[TMP1_NOT:%.*]] = xor i1 [[TMP1]], true
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP2]], [[TMP1_NOT]]
 ; CHECK-NEXT:    ret i1 [[TMP4]]
 ;
   %tmp1 = call i1 @gen1()
Index: test/Transforms/InstCombine/or-xor.ll
===================================================================
--- test/Transforms/InstCombine/or-xor.ll
+++ test/Transforms/InstCombine/or-xor.ll
@@ -358,8 +358,8 @@
 ; ((x | y) ^ (~x | ~y)) -> ~(x ^ y)
 define i32 @test19(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test19(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[X_NOT:%.*]] = xor i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[X_NOT]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %noty = xor i32 %y, -1
@@ -373,8 +373,8 @@
 ; ((x | y) ^ (~y | ~x)) -> ~(x ^ y)
 define i32 @test20(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test20(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[X_NOT:%.*]] = xor i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[X_NOT]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %noty = xor i32 %y, -1
@@ -388,8 +388,8 @@
 ; ((~x | ~y) ^ (x | y)) -> ~(x ^ y)
 define i32 @test21(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test21(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[X_NOT:%.*]] = xor i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[X_NOT]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %noty = xor i32 %y, -1
@@ -403,8 +403,8 @@
 ; ((~x | ~y) ^ (y | x)) -> ~(x ^ y)
 define i32 @test22(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test22(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[Y_NOT:%.*]] = xor i32 [[Y:%.*]], -1
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y_NOT]], [[X:%.*]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %noty = xor i32 %y, -1
Index: test/Transforms/InstCombine/set.ll
===================================================================
--- test/Transforms/InstCombine/set.ll
+++ test/Transforms/InstCombine/set.ll
@@ -130,8 +130,8 @@
 
 define i1 @test14(i1 %A, i1 %B) {
 ; CHECK-LABEL: @test14(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[C:%.*]] = xor i1 [[TMP1]], true
+; CHECK-NEXT:    [[A_NOT:%.*]] = xor i1 [[A:%.*]], true
+; CHECK-NEXT:    [[C:%.*]] = xor i1 [[A_NOT]], [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %C = icmp eq i1 %A, %B
@@ -140,8 +140,8 @@
 
 define <3 x i1> @test14vec(<3 x i1> %A, <3 x i1> %B) {
 ; CHECK-LABEL: @test14vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor <3 x i1> [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[C:%.*]] = xor <3 x i1> [[TMP1]], <i1 true, i1 true, i1 true>
+; CHECK-NEXT:    [[A_NOT:%.*]] = xor <3 x i1> [[A:%.*]], <i1 true, i1 true, i1 true>
+; CHECK-NEXT:    [[C:%.*]] = xor <3 x i1> [[A_NOT]], [[B:%.*]]
 ; CHECK-NEXT:    ret <3 x i1> [[C]]
 ;
   %C = icmp eq <3 x i1> %A, %B
@@ -261,8 +261,8 @@
 
 define i1 @test19(i1 %A, i1 %B) {
 ; CHECK-LABEL: @test19(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[C:%.*]] = xor i1 [[TMP1]], true
+; CHECK-NEXT:    [[A_NOT:%.*]] = xor i1 [[A:%.*]], true
+; CHECK-NEXT:    [[C:%.*]] = xor i1 [[A_NOT]], [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %a = zext i1 %A to i32