Index: llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -2438,16 +2438,20 @@
   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);
+      // We must eliminate the and/or for this transform to not increase the
+      // instruction count.
+      if (NotOp->hasOneUse()) {
+        // ~(~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
Index: llvm/trunk/test/Transforms/InstCombine/demorgan.ll
===================================================================
--- llvm/trunk/test/Transforms/InstCombine/demorgan.ll
+++ llvm/trunk/test/Transforms/InstCombine/demorgan.ll
@@ -286,8 +286,7 @@
 ; CHECK-NEXT:    [[NOTA:%.*]] = xor i8 %A, -1
 ; CHECK-NEXT:    [[C:%.*]] = or i8 [[NOTA]], %B
 ; CHECK-NEXT:    [[USE2C:%.*]] = mul i8 [[C]], 23
-; CHECK-NEXT:    [[B_NOT:%.*]] = xor i8 %B, -1
-; CHECK-NEXT:    [[NOTC:%.*]] = and i8 [[B_NOT]], %A
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i8 [[C]], -1
 ; CHECK-NEXT:    [[R:%.*]] = sdiv i8 [[NOTC]], [[USE2C]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
@@ -330,8 +329,7 @@
 ; CHECK-NEXT:    [[USE2A:%.*]] = mul i8 [[NOTA]], 17
 ; CHECK-NEXT:    [[C:%.*]] = or i8 [[NOTA]], %B
 ; CHECK-NEXT:    [[USE2C:%.*]] = mul i8 [[C]], 23
-; CHECK-NEXT:    [[B_NOT:%.*]] = xor i8 %B, -1
-; CHECK-NEXT:    [[NOTC:%.*]] = and i8 [[B_NOT]], %A
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i8 [[C]], -1
 ; CHECK-NEXT:    [[R1:%.*]] = sdiv i8 [[NOTC]], [[USE2C]]
 ; CHECK-NEXT:    [[R2:%.*]] = sdiv i8 [[R1]], [[USE2A]]
 ; CHECK-NEXT:    ret i8 [[R2]]
@@ -354,8 +352,7 @@
 ; CHECK-NEXT:    [[NOTA:%.*]] = xor i8 %A, -1
 ; CHECK-NEXT:    [[C:%.*]] = or i8 [[NOTA]], %B
 ; CHECK-NEXT:    [[USE2C:%.*]] = mul i8 [[C]], 23
-; CHECK-NEXT:    [[B_NOT:%.*]] = xor i8 %B, -1
-; CHECK-NEXT:    [[NOTC:%.*]] = and i8 [[B_NOT]], %A
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i8 [[C]], -1
 ; CHECK-NEXT:    [[R1:%.*]] = sdiv i8 [[NOTC]], [[USE2C]]
 ; CHECK-NEXT:    [[R2:%.*]] = sdiv i8 [[R1]], [[USE2B]]
 ; CHECK-NEXT:    ret i8 [[R2]]