[DAGCombiner][X86] Prevent unfoldMaskedMerge from creating an AND with two inverted inputs.

[craig.topper]

Summary

It's possible that the mask is already a NOT. At least if InstCombine
hasn't canonicalized the input. In that case we will form an ANDN with
X instead of with Y. So we don't need to worry about Y being a constant.

If M is a bitwise not, we do need to worry about X being a constant so
we handle that case now.

This fixes a size regression found when trying to enable this combine
for RISCV in D113937.

[jrtc27]

Regarding the comment about X: yes, that's wanted. Here's the test:

define i32 @foo(i32 %y, i32 %mask) {  
  %notmask = xor i32 %mask, -1
  %n0 = xor i32 42, %y
  %n1 = and i32 %n0, %notmask
  %r = xor i32 %n1, %y
  ret i32 %r
}

which (still) gives:

movl    %esi, %eax
andl    %esi, %edi
notl    %eax
andl    $42, %eax
orl     %edi, %eax

but with the below patch (didn't fully deal with the comments before the if, though I did update the function header comment which is currently out of sync in this patch):

--- a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -7784,9 +7784,12 @@ SDValue DAGCombiner::MatchLoadCombine(SDNode *N) {
 //    |  D  |
 // Into:
 //   (x & m) | (y & ~m)
-// If y is a constant, and the 'andn' does not work with immediates,
-// we unfold into a different pattern:
+// If y is a constant, m is not a 'not', and the 'andn' does not work with
+// immediates, we unfold into a different pattern:
 //   ~(~x & m) & (m | y)
+// If x is a constant, m is a 'not', and the 'andn' does not work with
+// immediates, we unfold into a different pattern:
+//   (x | ~m) & ~(~m & ~y)
 // NOTE: we don't unfold the pattern if 'xor' is actually a 'not', because at
 //       the very least that breaks andnpd / andnps patterns, and because those
 //       patterns are simplified in IR and shouldn't be created in the DAG
@@ -7842,7 +7845,7 @@ SDValue DAGCombiner::unfoldMaskedMerge(SDNode *N) {
   SDLoc DL(N);
 
   // If Y is a constant, check that 'andn' works with immediates.
-  if (!TLI.hasAndNot(Y)) {
+  if (!TLI.hasAndNot(Y) && !isBitwiseNot(M)) {
     assert(TLI.hasAndNot(X) && "Only mask is a variable? Unreachable.");
     // If not, we need to do a bit more work to make sure andn is still used.
     SDValue NotX = DAG.getNOT(DL, X, VT);
@@ -7852,6 +7855,17 @@ SDValue DAGCombiner::unfoldMaskedMerge(SDNode *N) {
     return DAG.getNode(ISD::AND, DL, VT, NotLHS, RHS);
   }
 
+  if (!TLI.hasAndNot(X) && isBitwiseNot(M)) {
+    assert(TLI.hasAndNot(Y) && "Only mask is a variable? Unreachable.");
+    // If not, we need to do a bit more work to make sure andn is still used.
+    SDValue NotM = DAG.getNOT(DL, M, VT);
+    SDValue LHS = DAG.getNode(ISD::OR, DL, VT, X, NotM);
+    SDValue NotY = DAG.getNOT(DL, Y, VT);
+    SDValue RHS = DAG.getNode(ISD::AND, DL, VT, NotM, NotY);
+    SDValue NotRHS = DAG.getNOT(DL, RHS, VT);
+    return DAG.getNode(ISD::AND, DL, VT, LHS, NotRHS);
+  }
+
   SDValue LHS = DAG.getNode(ISD::AND, DL, VT, X, M);
   SDValue NotM = DAG.getNOT(DL, M, VT);
   SDValue RHS = DAG.getNode(ISD::AND, DL, VT, Y, NotM);

(which I think is correct...) gives:

andnl   %esi, %edi, %eax
orl     $42, %esi
andnl   %esi, %eax, %eax

No other file in llvm/test/CodeGen/X86 seems to be affected, though I haven't checked other targets.

[jrtc27]

Oh, my test is just in_constant_42_vary_invmask (well, I dropped the unused argument), which is also exactly where we see the other code size regression on RISC-V.

[craig.topper]

Handle the case where M is a not and X is a constant.

[jrtc27]

Comment just before the function needs updating to both add the additional restriction on the existing case and document the new one, as in my patch, otherwise looks fine

[craig.topper]

Update comment

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

 
 // If the target has andn, bsl, or a similar bit-select instruction,
 // we want to unfold masked merge, with canonical pattern of:
 //   |        A  |  |B|
 //   ((x ^ y) & m) ^ y
 //    |  D  |
 // Into:
 //   (x & m) | (y & ~m)
-// If y is a constant, and the 'andn' does not work with immediates,
-// we unfold into a different pattern:
+// If y is a constant, m is not a 'not', and the 'andn' does not work with
+// immediates, we unfold into a different pattern:
 //   ~(~x & m) & (m | y)
+// If x is a constant, m is a 'not', and the 'andn' does not work with
+// immediates, we unfold into a different pattern:
+//   (x | ~m) & ~(~m & ~y)
 // NOTE: we don't unfold the pattern if 'xor' is actually a 'not', because at
 //       the very least that breaks andnpd / andnps patterns, and because those
 //       patterns are simplified in IR and shouldn't be created in the DAG
 SDValue DAGCombiner::unfoldMaskedMerge(SDNode *N) {
   assert(N->getOpcode() == ISD::XOR);
 
   // Don't touch 'not' (i.e. where y = -1).
   if (isAllOnesOrAllOnesSplat(N->getOperand(1)))
if (isa<ConstantSDNode>(M.getNode()))
     return SDValue();
 
   // We can transform if the target has AndNot
   if (!TLI.hasAndNot(M))
     return SDValue();
 
   SDLoc DL(N);
 
-  // If Y is a constant, check that 'andn' works with immediates.
-  if (!TLI.hasAndNot(Y)) {
+  // If Y is a constant, check that 'andn' works with immediates. Unless M is
+  // a bitwise not that would already allow ANDN to be used.
+  if (!TLI.hasAndNot(Y) && !isBitwiseNot(M)) {
     assert(TLI.hasAndNot(X) && "Only mask is a variable? Unreachable.");
     // If not, we need to do a bit more work to make sure andn is still used.
     SDValue NotX = DAG.getNOT(DL, X, VT);
     SDValue LHS = DAG.getNode(ISD::AND, DL, VT, NotX, M);
     SDValue NotLHS = DAG.getNOT(DL, LHS, VT);
     SDValue RHS = DAG.getNode(ISD::OR, DL, VT, M, Y);
     return DAG.getNode(ISD::AND, DL, VT, NotLHS, RHS);
   }
 
+  // If X is a constant and M is a bitwise not, check that 'andn' works with
+  // immediates.
+  if (!TLI.hasAndNot(X) && isBitwiseNot(M)) {
+    assert(TLI.hasAndNot(Y) && "Only mask is a variable? Unreachable.");
+    // If not, we need to do a bit more work to make sure andn is still used.
+    SDValue NotM = M.getOperand(0);
+    SDValue LHS = DAG.getNode(ISD::OR, DL, VT, X, NotM);
+    SDValue NotY = DAG.getNOT(DL, Y, VT);
+    SDValue RHS = DAG.getNode(ISD::AND, DL, VT, NotM, NotY);
+    SDValue NotRHS = DAG.getNOT(DL, RHS, VT);
+    return DAG.getNode(ISD::AND, DL, VT, LHS, NotRHS);
+  }
+
   SDValue LHS = DAG.getNode(ISD::AND, DL, VT, X, M);
   SDValue NotM = DAG.getNOT(DL, M, VT);
   SDValue RHS = DAG.getNode(ISD::AND, DL, VT, Y, NotM);
 
   return DAG.getNode(ISD::OR, DL, VT, LHS, RHS);
 }
 
 SDValue DAGCombiner::visitXOR(SDNode *N) {

llvm/test/CodeGen/X86/unfold-masked-merge-scalar-variablemask.ll

 ; CHECK-NOBMI-NEXT:    notl %edx
 ; CHECK-NOBMI-NEXT:    xorl $42, %eax
 ; CHECK-NOBMI-NEXT:    andl %edx, %eax
 ; CHECK-NOBMI-NEXT:    xorl $42, %eax
 ; CHECK-NOBMI-NEXT:    retq
 ;
 ; CHECK-BMI-LABEL: in_constant_varx_42_invmask:
 ; CHECK-BMI:       # %bb.0:
-; CHECK-BMI-NEXT:    notl %edx
-; CHECK-BMI-NEXT:    andnl %edx, %edi, %eax
-; CHECK-BMI-NEXT:    orl $42, %edx
-; CHECK-BMI-NEXT:    andnl %edx, %eax, %eax
+; CHECK-BMI-NEXT:    andnl %edi, %edx, %eax
+; CHECK-BMI-NEXT:    andl $42, %edx
+; CHECK-BMI-NEXT:    orl %edx, %eax
 ; CHECK-BMI-NEXT:    retq
   %notmask = xor i32 %mask, -1
   %n0 = xor i32 %x, 42 ; %x
   %n1 = and i32 %n0, %notmask
   %r = xor i32 %n1, 42
   ret i32 %r
 }
 define i32 @out_constant_mone_vary(i32 %x, i32 %y, i32 %mask) {

 ; CHECK-NOBMI-NEXT:    movl %esi, %eax
 ; CHECK-NOBMI-NEXT:    xorl $42, %eax
 ; CHECK-NOBMI-NEXT:    andl %edx, %eax
 ; CHECK-NOBMI-NEXT:    xorl %esi, %eax
 ; CHECK-NOBMI-NEXT:    retq
 ;
 ; CHECK-BMI-LABEL: in_constant_42_vary_invmask:
 ; CHECK-BMI:       # %bb.0:
-; CHECK-BMI-NEXT:    movl %edx, %eax
-; CHECK-BMI-NEXT:    andl %edx, %esi
-; CHECK-BMI-NEXT:    notl %eax
-; CHECK-BMI-NEXT:    andl $42, %eax
-; CHECK-BMI-NEXT:    orl %esi, %eax
+; CHECK-BMI-NEXT:    andnl %edx, %esi, %eax
+; CHECK-BMI-NEXT:    orl $42, %edx
+; CHECK-BMI-NEXT:    andnl %edx, %eax, %eax
 ; CHECK-BMI-NEXT:    retq
   %notmask = xor i32 %mask, -1
   %n0 = xor i32 42, %y ; %x
   %n1 = and i32 %n0, %notmask
   %r = xor i32 %n1, %y
   ret i32 %r
 }
 ; ============================================================================ ;