[SelectionDAG] Add pattern to haveNoCommonBitsSet.

[OmerAviram]

Summary

Correctly identify the following pattern, which has no common bits: (X & ~M) op (Y & M).

[lebedev.ri]

Tests?

[OmerAviram]

Added ll test for X86 Target.
prior to the patch, the ir included an or instruction:

; CHECK-NEXT:    andl %esi, %edx
; CHECK-NEXT:    notl %esi
; CHECK-NEXT:    andl %edi, %esi
; CHECK-NEXT:    orl %edx, %esi
; CHECK-NEXT:    leal 1(%rsi), %eax

After the patch, the or instruction can be combined into an add, since the operands have no common bits.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

4550

Maybe better to pull this into haveNoCommonBitsSet as lambda?

4562

You need to try and ensure we have test coverage for all of these permutations.

llvm/test/CodeGen/X86/or-lea.ll

154

Once you have more test coverage, we should add these tests to trunk with current codegen so you can rebase and the patch shows the diff.

[OmerAviram]

Added tests for the different pattern permutations as a separate patch (https://reviews.llvm.org/D114078) and rebased on it.

[OmerAviram]

Updated diff with i32 and i64 tests.

[RKSimon]

Please can you rebase - I've added BMI test coverage as well which might affect some tests

[spatel]

Do we expect all vector types/targets to bypass this in some way? If yes, it's worth adding a comment to the patch description and/or code. If no, can we find a test that shows an asm difference?

[OmerAviram]

In D113970#3151343, @spatel wrote:

Do we expect all vector types/targets to bypass this in some way? If yes, it's worth adding a comment to the patch description and/or code. If no, can we find a test that shows an asm difference?

What exactly do you mean by bypass it? This addition to haveNoCommonBitsSet works for vector types as well. Do you mean add another lit test for vector types?

[spatel]

In D113970#3151642, @OmerAviram wrote:

In D113970#3151343, @spatel wrote:

Do we expect all vector types/targets to bypass this in some way? If yes, it's worth adding a comment to the patch description and/or code. If no, can we find a test that shows an asm difference?

What exactly do you mean by bypass it? This addition to haveNoCommonBitsSet works for vector types as well. Do you mean add another lit test for vector types?

I mean are there TLI hooks (for example hasAndNot) or other transforms that will trigger before or after this such that vector instructions are never affected?
It sounds like the answer is 'no'. Therefore, yes we should have another lit test with vector types, so we can see the difference from this patch.

[OmerAviram]

Added tests for vector types.

[spatel]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

4558

I prefer that we not reuse/shadow the variable names in here.
How about matching the variable names to the code comment, so something like this:

auto MatchNoCommonBitsPattern = [&](SDValue NotM, SDValue And) {
  if (isBitwiseNot(NotM, true)) {
    SDValue M = NotM->getOperand(0);

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

4562

(style) Remove the unnecessary brackets

[spatel]

LGTM - will wait at least a day to commit in case there's any other feedback.

[OmerAviram]

In D113970#3158588, @spatel wrote:

LGTM - will wait at least a day to commit in case there's any other feedback.

Thanks, Could you please commit on my behalf?

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
   if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
     if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
       if (CA->isZero() && CB->isZero()) return true;
 
   // Otherwise they may not be equal.
   return false;
 }
 
+static bool matchNoCommonBitsPattern(SDValue A, SDValue B) {
+  if (isBitwiseNot(A, true)) {
+    SDValue NotOperand = A->getOperand(0);
+    assert(B->getOpcode() == ISD::AND && "Expected AND opcode!");
+    if (NotOperand == B->getOperand(0) || NotOperand == B->getOperand(1))
+      return true;
+  }
+  return false;
+}
+
 // FIXME: unify with llvm::haveNoCommonBitsSet.
-// FIXME: could also handle masked merge pattern (X & ~M) op (Y & M)
 bool SelectionDAG::haveNoCommonBitsSet(SDValue A, SDValue B) const {
   assert(A.getValueType() == B.getValueType() &&
          "Values must have the same type");
+  // Match masked merge pattern (X & ~M) op (Y & M)
+  if (A->getOpcode() == ISD::AND && B->getOpcode() == ISD::AND) {
+    if (matchNoCommonBitsPattern(A->getOperand(0), B) ||
+        matchNoCommonBitsPattern(A->getOperand(1), B) ||
+        matchNoCommonBitsPattern(B->getOperand(0), A) ||
+        matchNoCommonBitsPattern(B->getOperand(1), A))
+      return true;
+  }
   return KnownBits::haveNoCommonBitsSet(computeKnownBits(A),
                                         computeKnownBits(B));
 }
 
 static SDValue FoldSTEP_VECTOR(const SDLoc &DL, EVT VT, SDValue Step,
                                SelectionDAG &DAG) {
   if (cast<ConstantSDNode>(Step)->isZero())
     return DAG.getConstant(0, DL, VT);

llvm/test/CodeGen/X86/or-lea.ll

 ; CHECK-NEXT:    retq
 
   %shl = shl i64 %x, 1
   %and = and i64 %y, 1
   %or = or i64 %and, %shl
   ret i64 %or
 }
 
+; In the following pattern, lhs and rhs of the or instruction have no common bits.
+
+define i16 @or_and_not_and(i16 %x, i16 %y, i16 %z) {
+; CHECK-LABEL: or_and_not_and:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    # kill: def $edx killed $edx def $rdx
+; CHECK-NEXT:    # kill: def $esi killed $esi def $rsi
+; CHECK-NEXT:    andl %esi, %edx
+; CHECK-NEXT:    notl %esi
+; CHECK-NEXT:    andl %edi, %esi
+; CHECK-NEXT:    leal 1(%rdx,%rsi), %eax
+; CHECK-NEXT:    # kill: def $ax killed $ax killed $eax
+; CHECK-NEXT:    retq
+entry:
+  %and1 = and i16 %z, %y
+  %xor = xor i16 %y, -1
+  %and2 = and i16 %x, %xor
+  %or = or i16 %and1, %and2
+  %inc = add i16 %or, 1
+  ret i16 %inc
+}