Index: lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -2433,29 +2433,34 @@
   if (Value *V = SimplifyBSwap(I))
     return replaceInstUsesWith(I, V);
 
+  // Apply DeMorgan's Law to eliminate a 'not' op.
+  Value *X, *Y;
+
+  // ~(~X & Y) --> (X | ~Y)
+  // ~(Y & ~X) --> (X | ~Y)
+  if (match(&I, m_Not(m_c_And(m_Not(m_Value(X)), m_Value(Y))))) {
+    Value *NotY = Builder->CreateNot(Y, Y->getName() + ".not");
+    return BinaryOperator::CreateOr(X, NotY);
+  }
+  // ~(~X | Y) --> (X & ~Y)
+  // ~(Y | ~X) --> (X & ~Y)
+  if (match(&I, m_Not(m_c_Or(m_Not(m_Value(X)), m_Value(Y))))) {
+    Value *NotY = Builder->CreateNot(Y, Y->getName() + ".not");
+    return BinaryOperator::CreateAnd(X, NotY);
+  }
+
   // Is this a 'not' (~) fed by a binary operator?
   BinaryOperator *NotOp;
   if (match(&I, m_Not(m_BinOp(NotOp)))) {
     if (NotOp->getOpcode() == Instruction::And ||
         NotOp->getOpcode() == Instruction::Or) {
-      // ~(~X & Y) --> (X | ~Y) - De Morgan's Law
-      // ~(~X | Y) === (X & ~Y) - De Morgan's Law
-      if (dyn_castNotVal(NotOp->getOperand(1)))
-        NotOp->swapOperands();
-      if (Value *Op0NotVal = dyn_castNotVal(NotOp->getOperand(0))) {
-        Value *NotY = Builder->CreateNot(
-            NotOp->getOperand(1), NotOp->getOperand(1)->getName() + ".not");
-        if (NotOp->getOpcode() == Instruction::And)
-          return BinaryOperator::CreateOr(Op0NotVal, NotY);
-        return BinaryOperator::CreateAnd(Op0NotVal, NotY);
-      }
-
-      // ~(X & Y) --> (~X | ~Y) - De Morgan's Law
-      // ~(X | Y) === (~X & ~Y) - De Morgan's Law
       if (IsFreeToInvert(NotOp->getOperand(0),
                          NotOp->getOperand(0)->hasOneUse()) &&
           IsFreeToInvert(NotOp->getOperand(1),
                          NotOp->getOperand(1)->hasOneUse())) {
+        // Apply DeMorgan's Law when inverts are free:
+        // ~(X & Y) --> (~X | ~Y)
+        // ~(X | Y) === (~X & ~Y)
         Value *NotX = Builder->CreateNot(NotOp->getOperand(0), "notlhs");
         Value *NotY = Builder->CreateNot(NotOp->getOperand(1), "notrhs");
         if (NotOp->getOpcode() == Instruction::And)
Index: test/Transforms/InstCombine/and-or.ll
===================================================================
--- test/Transforms/InstCombine/and-or.ll
+++ test/Transforms/InstCombine/and-or.ll
@@ -53,10 +53,12 @@
   ret i32 %tmp3
 }
 
+; Do not apply DeMorgan's Law to constants. We prefer 'not' ops.
+
 define i32 @demorganize_constant1(i32 %a) {
 ; CHECK-LABEL: @demorganize_constant1(
-; CHECK-NEXT:    [[A_NOT:%.*]] = or i32 %a, -16
-; CHECK-NEXT:    [[AND1:%.*]] = xor i32 [[A_NOT]], 15
+; CHECK-NEXT:    [[AND:%.*]] = and i32 %a, 15
+; CHECK-NEXT:    [[AND1:%.*]] = xor i32 [[AND]], -1
 ; CHECK-NEXT:    ret i32 [[AND1]]
 ;
   %and = and i32 %a, 15
@@ -64,10 +66,12 @@
   ret i32 %and1
 }
 
+; Do not apply DeMorgan's Law to constants. We prefer 'not' ops.
+
 define i32 @demorganize_constant2(i32 %a) {
 ; CHECK-LABEL: @demorganize_constant2(
-; CHECK-NEXT:    [[A_NOT:%.*]] = and i32 %a, -16
-; CHECK-NEXT:    [[AND1:%.*]] = xor i32 [[A_NOT]], -16
+; CHECK-NEXT:    [[AND:%.*]] = or i32 %a, 15
+; CHECK-NEXT:    [[AND1:%.*]] = xor i32 [[AND]], -1
 ; CHECK-NEXT:    ret i32 [[AND1]]
 ;
   %and = or i32 %a, 15
Index: test/Transforms/InstCombine/assume2.ll
===================================================================
--- test/Transforms/InstCombine/assume2.ll
+++ test/Transforms/InstCombine/assume2.ll
@@ -21,8 +21,8 @@
 
 define i32 @test2(i32 %a) #0 {
 ; CHECK-LABEL: @test2(
-; CHECK-NEXT:    [[A_NOT:%.*]] = or i32 [[A:%.*]], -16
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[A_NOT]], -6
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[A:%.*]], 15
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 10
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
 ; CHECK-NEXT:    ret i32 2
 ;
@@ -50,8 +50,8 @@
 
 define i32 @test4(i32 %a) #0 {
 ; CHECK-LABEL: @test4(
-; CHECK-NEXT:    [[A_NOT:%.*]] = and i32 [[A:%.*]], 15
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[A_NOT]], 10
+; CHECK-NEXT:    [[V:%.*]] = or i32 [[A:%.*]], -16
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[V]], -6
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
 ; CHECK-NEXT:    ret i32 2
 ;