[InstCombine] check one-use before applying DeMorgan nor/nand folds

[spatel]

Summary

Splitting this off from D32665 to make sure I've thought it about correctly.

If we have:
~(~X & Y), it only makes sense to transform it to (X | ~Y) when we do not need the intermediate (~X & Y) value. In that case, we would need an extra instruction to generate ~Y + 'or' (as shown in the test changes).

It's ok if we have multiple uses of ~X or Y, however. In those cases, we won't reduce the instruction count or critical path, but we might improve throughput because we can generate ~X and ~Y in parallel. Whether that actually makes perf sense or not for a target is something we can't answer in IR.

[efriedma]

LGTM.

llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombiner::visitXor(BinaryOperator &I) {
   if (Value *V = SimplifyBSwap(I))
     return replaceInstUsesWith(I, V);
 
   // 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) {
+      // 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
       // ~(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())) {
         Value *NotX = Builder->CreateNot(NotOp->getOperand(0), "notlhs");

llvm/trunk/test/Transforms/InstCombine/demorgan.ll

 
 ; ~(~A | B) --> (A & ~B) - what if we use one of the intermediate results?
 
 define i8 @demorgan_nor_use2c(i8 %A, i8 %B) {
 ; CHECK-LABEL: @demorgan_nor_use2c(
 ; 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]]
 ;
   %nota = xor i8 %A, -1
   %c = or i8 %nota, %B
   %use2c = mul i8 %c, 23
   %notc = xor i8 %c, -1
   %r = sdiv i8 %notc, %use2c

 ; ~(~A | B) --> (A & ~B) - what if we use two of the intermediate results?
 
 define i8 @demorgan_nor_use2ac(i8 %A, i8 %B) {
 ; CHECK-LABEL: @demorgan_nor_use2ac(
 ; CHECK-NEXT:    [[NOTA:%.*]] = xor i8 %A, -1
 ; 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]]
 ;
   %nota = xor i8 %A, -1
   %use2a = mul i8 %nota, 17
   %c = or i8 %nota, %B
   %use2c = mul i8 %c, 23
   %notc = xor i8 %c, -1
   %r1 = sdiv i8 %notc, %use2c
   %r2 = sdiv i8 %r1, %use2a
   ret i8 %r2
 }
 
 ; ~(~A | B) --> (A & ~B) - what if we use two of the intermediate results?
 
 define i8 @demorgan_nor_use2bc(i8 %A, i8 %B) {
 ; CHECK-LABEL: @demorgan_nor_use2bc(
 ; CHECK-NEXT:    [[USE2B:%.*]] = mul i8 %B, 23
 ; 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]]
 ;
   %use2b = mul i8 %B, 23
   %nota = xor i8 %A, -1
   %c = or i8 %nota, %B
   %use2c = mul i8 %c, 23