[InstCombine] don't use DeMorgan's Law on integer constants

[spatel]

Summary

This is the fold that causes the infinite loop in BoringSSL (https://github.com/google/boringssl/blob/master/crypto/cipher/e_rc2.c) when we fix instcombine demanded bits to prefer 'not' ops as in D32255.

There are 2 or 3 problems with dyn_castNotVal, and I don't think we can reinstate D32255 until dyn_castNotVal is completely eliminated:

1. As shown here, it transforms 'not' into random xor. This transform is harmful to SCEV and codegen because 'not' can often be folded while random xor cannot.
2. It does not transform vector constants. This is actually a good thing, but if you don't believe the above argument, then we shouldn't have excluded vectors.
3. It tries to avoid transforming not(not(X)). That's nice, but it doesn't match the greedy nature of instcombine. If we DeMorganize a pattern that has an extra 'not' in it:

~(~(~X) & Y) --> (~X | ~Y)
That's just another case of DeMorgan, so we should trust that we'll get that too:
(~X | ~ Y) --> ~(X & Y)

[efriedma]

Your reasoning makes sense.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2441

Do we need to check the number of uses for the inner operations?

[spatel]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2441

Good point - I'll add some tests so we can see what that trade-off looks like.

[spatel]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2441

I made a separate patch to answer this part since it exists independently of this change:
D32703

[spatel]

Patch updated:
We added a one-use check in D32703, so keep that in the translation to the 'match' patterns.

[efriedma]

LGTM.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombiner::visitXor(BinaryOperator &I) {
   // See if we can simplify any instructions used by the instruction whose sole
   // purpose is to compute bits we don't care about.
   if (SimplifyDemandedInstructionBits(I))
     return &I;
 
   if (Value *V = SimplifyBSwap(I))
     return replaceInstUsesWith(I, V);
 
+  // Apply DeMorgan's Law for 'nand' / 'nor' logic with an inverted operand.
+  Value *X, *Y;
+
+  // We must eliminate the and/or (one-use) for these transforms to not increase
+  // the instruction count.
+  // ~(~X & Y) --> (X | ~Y)
+  // ~(Y & ~X) --> (X | ~Y)
+  if (match(&I, m_Not(m_OneUse(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_OneUse(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) {
-      // 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
+      // Apply DeMorgan's Law when inverts are free:
+      // ~(X & Y) --> (~X | ~Y)
+      // ~(X | Y) --> (~X & ~Y)
       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");
         Value *NotY = Builder->CreateNot(NotOp->getOperand(1), "notrhs");
         if (NotOp->getOpcode() == Instruction::And)
           return BinaryOperator::CreateOr(NotX, NotY);

test/Transforms/InstCombine/assume2.ll

;
   %cmp = icmp eq i32 %and, 5
   tail call void @llvm.assume(i1 %cmp)
   %and1 = and i32 %a, 7
   ret i32 %and1
 }
 
 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
 ;
   %and = and i32 %a, 15
   %nand = xor i32 %and, -1
   %cmp = icmp eq i32 %nand, 4294967285
   tail call void @llvm.assume(i1 %cmp)
   %and1 = and i32 %a, 7
;
   %cmp = icmp eq i32 %v, 4294967285
   tail call void @llvm.assume(i1 %cmp)
   %and1 = and i32 %a, 7
   ret i32 %and1
 }
 
 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
 ;
   %v = or i32 %a, 4294967280
   %nv = xor i32 %v, -1
   %cmp = icmp eq i32 %nv, 5
   tail call void @llvm.assume(i1 %cmp)
   %and1 = and i32 %a, 7

test/Transforms/InstCombine/demorgan.ll

;
   %c = or i8 %nota, %B
   %use2c = mul i8 %c, 23
   %notc = xor i8 %c, -1
   %r1 = sdiv i8 %notc, %use2c
   %r2 = sdiv i8 %r1, %use2b
   ret i8 %r2
 }
 
-; FIXME: Do not apply DeMorgan's Law to constants. We prefer 'not' ops.
+; 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
   %and1 = xor i32 %and, -1
   ret i32 %and1
 }
 
-; FIXME: Do not apply DeMorgan's Law to constants. We prefer 'not' ops.
+; 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
   %and1 = xor i32 %and, -1
   ret i32 %and1
 }
 
 ; PR22723: Recognize DeMorgan's Laws when obfuscated by zexts.