[AArch64] Optimize patterns where AND's on same operand with multiple masks can be combined.

[bipmis]

Summary

The patch simplifies some of the patterns as below

or(or(and(a, mask1), and(b, mask)), and(a, mask2)) -> or(and(a, mask1|mask2), and(b, mask))

or(or(or(x, and(a,mask1)), and(b,mask)), and(a,mask2)) -> or(or(x, and(a,mask1|mask2)), and(b,mask))

The simplifications allows for generation of single instruction like rev16 on AArch64 when there is a code pattern which does a half word byte swaps on a 64 bit.

[RKSimon]

Are these patterns actually appearing in the DAG?

[bipmis]

Yes for some of the examples provided, the pattern is actually seen in the DAG.

[RKSimon]

can you start by committing the tests to trunk with current codegen and then rebase the patch to show the codegen diff please?

[bipmis]

The patch has been rebased after committing the tests.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6942

This all feels likes it should be performed a lot more generally in a lot less code tbh - you're adding a lot of code just to hit a couple of patterns.

[bipmis]

Adding additional simple tests to show simple scenarios where this optimization will be useful.

Also reduced the code needed to implement it. There are some some additional code sections to maintain the natural ordering of the operands. Also all possible operand ordering has been handled. This is to target a generic implementation.

[bipmis]

An alternate implementation with InstCombine IR Pass is at https://reviews.llvm.org/D124119.

[RKSimon]

@bipmis Whats the plan for this patch? Can the IR pattern appear in DAG or will D124119 handle it in InstCombine?

[bipmis]

@RKSimon The InstCombine patch D124119 can now handle this and the pattern should not appear in the DAG. We can abandon this review. Thanks.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

private:
     SDValue buildSqrtEstimateImpl(SDValue Op, SDNodeFlags Flags, bool Recip);
     SDValue buildSqrtNROneConst(SDValue Arg, SDValue Est, unsigned Iterations,
                                 SDNodeFlags Flags, bool Reciprocal);
     SDValue buildSqrtNRTwoConst(SDValue Arg, SDValue Est, unsigned Iterations,
                                 SDNodeFlags Flags, bool Reciprocal);
     SDValue MatchBSwapHWordLow(SDNode *N, SDValue N0, SDValue N1,
                                bool DemandHighBits = true);
     SDValue MatchBSwapHWord(SDNode *N, SDValue N0, SDValue N1);
+    SDValue tryCombineHWordByteSwaps(SDNode *N);
     SDValue MatchRotatePosNeg(SDValue Shifted, SDValue Pos, SDValue Neg,
                               SDValue InnerPos, SDValue InnerNeg, bool HasPos,
                               unsigned PosOpcode, unsigned NegOpcode,
                               const SDLoc &DL);
     SDValue MatchFunnelPosNeg(SDValue N0, SDValue N1, SDValue Pos, SDValue Neg,
                               SDValue InnerPos, SDValue InnerNeg, bool HasPos,
                               unsigned PosOpcode, unsigned NegOpcode,
                               const SDLoc &DL);
if (N0.getOpcode() == ISD::AND &&
     SDValue X = DAG.getNode(ISD::OR, SDLoc(N0), VT,
                             N0.getOperand(1), N1.getOperand(1));
     return DAG.getNode(ISD::AND, DL, VT, N0.getOperand(0), X);
   }
 
   return SDValue();
 }
 
+static SDValue matchTwoLevelOrAnd(SelectionDAG &DAG, SDNode *N, SDValue N0,
+                                  EVT VT) {
+  // Confirm N opcode is an OR
+  if (N->getOpcode() != ISD::OR)
+    return SDValue();
+
+  SDValue OuterAnd, Inner, Outer;
+
+  // Confirm one operand of N is a OR and other an AND
+  //  or(or(),and)
+  if (N->getOperand(0).getOpcode() == ISD::OR &&
+      N->getOperand(1).getOpcode() == ISD::AND)
+    OuterAnd = N->getOperand(1);
+  // or(and,or())
+  else if (N->getOperand(1).getOpcode() == ISD::OR &&
+           N->getOperand(0).getOpcode() == ISD::AND)
+    OuterAnd = N->getOperand(0);
+  else
+    return SDValue();
+
+  // Check N0 has one operand AND and its first argument matches the AND operand
+  // of N.
+  int pos;
+  // or(or(anda, x), anda) -> or(anda, x)
+  // or(anda, or(anda , x)) -> or(anda, x)
+  if (N0.getOperand(0).getOpcode() == ISD::AND &&
+      N0.getOperand(0).getOperand(0) == OuterAnd.getOperand(0))
+    pos = 0;
+  // or(or(x, anda), anda) -> or(x, anda)
+  // or(anda, or(x, anda)) -> or(x, anda)
+  else if (N0.getOperand(1).getOpcode() == ISD::AND &&
+           N0.getOperand(1).getOperand(0) == OuterAnd.getOperand(0))
+    pos = 1;
+  else
+    return SDValue();
+
+  // Combine masks
+  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(OuterAnd.getOperand(1));
+  if (!N1C)
+    return SDValue();
+  unsigned long long Mask = N1C->getZExtValue();
+  N1C = dyn_cast<ConstantSDNode>(N0.getOperand(pos).getOperand(1));
+  if (!N1C)
+    return SDValue();
+  Mask = Mask | N1C->getZExtValue();
+  SDLoc DL(N);
+
+  Inner = DAG.getNode(ISD::AND, DL, VT, OuterAnd.getOperand(0),
+                      DAG.getConstant((uint64_t)Mask, DL, VT));
+
+  if (pos == 0)
+    Outer = DAG.getNode(ISD::OR, DL, VT, Inner, N0.getOperand(1));
+  else
+    Outer = DAG.getNode(ISD::OR, DL, VT, N0.getOperand(0), Inner);
+  return Outer;
+}
+
+static SDValue matchThreeLevelOrAnd(SelectionDAG &DAG, SDNode *N, SDValue N0,
+                                    SDValue N1, EVT VT) {
+  // Confirm N opcode is an OR
+  if (N->getOpcode() != ISD::OR)
+    return SDValue();
+
+  SDValue OuterAnd, Inner, Outer;
+
+  // Confirm one operand of N is a OR and other an AND
+  //  or(or(),and)
+  if (N->getOperand(0).getOpcode() == ISD::OR &&
+      N->getOperand(1).getOpcode() == ISD::AND)
+    OuterAnd = N->getOperand(1);
+  // or(and,or())
+  else if (N->getOperand(1).getOpcode() == ISD::OR &&
+           N->getOperand(0).getOpcode() == ISD::AND)
+    OuterAnd = N->getOperand(0);
+  else
+    return SDValue();
+
+  // Check N0 has one operand OR and check its position.
+  int pos0;
+  // or(or(or(),x),and)
+  // or(and,or(or(),x))
+  if (N0.getOperand(0).getOpcode() == ISD::OR)
+    pos0 = 0;
+  // or(or(x,or()),and)
+  // or(and,or(x,or()))
+  else if (N0.getOperand(1).getOpcode() == ISD::OR)
+    pos0 = 1;
+  else
+    return SDValue();
+
+  // Check N1 has one operand AND and its first argument matches the AND operand
+  // of N.
+  int pos;
+  // or(or(or(anda,y),x),anda) -> or(or(anda,y),x)
+  // or(anda,or(or(anda,y),x)) -> or(or(anda,y),x)
+  // or(or(x,or(anda,y)),anda) -> or(x,or(anda,y)
+  // or(anda,or(x,or(anda,y)))  -> or(x,or(anda,y)
+  if (N1.getOperand(0).getOpcode() == ISD::AND &&
+      N1.getOperand(0).getOperand(0) == OuterAnd.getOperand(0))
+    pos = 0;
+  // or(or(or(y,anda),x),anda) -> or(or(y,anda),x)
+  // or(anda,or(or(y,anda),x)) -> or(or(y,anda),x)
+  // or(or(x,or(y,anda)),anda) -> or(x,or(y,anda)
+  // or(anda,or(x,or(y,anda)))  -> or(x,or(y,anda)
+  else if (N1.getOperand(1).getOpcode() == ISD::AND &&
+           N1.getOperand(1).getOperand(0) == OuterAnd.getOperand(0))
+    pos = 1;
+  else
+    return SDValue();
+
+  // Combine masks
+  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(OuterAnd.getOperand(1));
+  if (!N1C)
+    return SDValue();
+  unsigned long long Mask = N1C->getZExtValue();
+  N1C = dyn_cast<ConstantSDNode>(N1.getOperand(pos).getOperand(1));
+  if (!N1C)
+    return SDValue();
+  Mask = Mask | N1C->getZExtValue();
+  SDLoc DL(N);
+
+  // Construct DAG
+  Inner = DAG.getNode(ISD::AND, DL, VT, OuterAnd.getOperand(0),
+                      DAG.getConstant((uint64_t)Mask, DL, VT));
+  if (pos == 0)
+    Outer = DAG.getNode(ISD::OR, DL, VT, Inner, N1.getOperand(1));
+  else
+    Outer = DAG.getNode(ISD::OR, DL, VT, N1.getOperand(0), Inner);
+
+  if (pos0 == 0)
+    Outer = DAG.getNode(ISD::OR, DL, VT, Outer, N0.getOperand(1));
+  else
+    Outer = DAG.getNode(ISD::OR, DL, VT, N0.getOperand(0), Outer);
+  return Outer;
+}
+
+SDValue DAGCombiner::tryCombineHWordByteSwaps(SDNode *N) {
+
+  if (!LegalOperations)
+    return SDValue();
+
+  EVT VT = N->getValueType(0);
+  if (VT != MVT::i64)
+    return SDValue();
+  SDValue N0, N1;
+
+  if (N->getOpcode() != ISD::OR)
+    return SDValue();
+
+  if (N->getOperand(0).getOpcode() == ISD::OR)
+    N0 = N->getOperand(0);
+  else if (N->getOperand(1).getOpcode() == ISD::OR)
+    N0 = N->getOperand(1);
+  else
+    return SDValue();
+
+  if (N0.getOperand(0).getOpcode() == ISD::OR)
+    N1 = N0.getOperand(0);
+  else if (N0.getOperand(1).getOpcode() == ISD::OR)
+    N1 = N0.getOperand(1);
+  else
+    // Check if it is two level
+    return matchTwoLevelOrAnd(DAG, N, N0, VT);
+
+  // Check if it is three level
+  return matchThreeLevelOrAnd(DAG, N, N0, N1, VT);
+}
+
 /// OR combines for which the commuted variant will be tried as well.
 static SDValue visitORCommutative(
     SelectionDAG &DAG, SDValue N0, SDValue N1, SDNode *N) {
   EVT VT = N0.getValueType();
   if (N0.getOpcode() == ISD::AND) {
     // fold (or (and X, (xor Y, -1)), Y) -> (or X, Y)
     if (isBitwiseNot(N0.getOperand(1)) && N0.getOperand(1).getOperand(0) == N1)
       return DAG.getNode(ISD::OR, SDLoc(N), VT, N0.getOperand(0), N1);
if (SDValue Combined = combineCarryDiamond(DAG, TLI, N0, N1, N))
     return Combined;
 
   // Recognize halfword bswaps as (bswap + rotl 16) or (bswap + shl 16)
   if (SDValue BSwap = MatchBSwapHWord(N, N0, N1))
     return BSwap;
   if (SDValue BSwap = MatchBSwapHWordLow(N, N0, N1))
     return BSwap;
 
+  // Simplify halfword bswaps in 64bit.
+  if (SDValue Combined = tryCombineHWordByteSwaps(N))
+    return Combined;
+
   // reassociate or
   if (SDValue ROR = reassociateOps(ISD::OR, SDLoc(N), N0, N1, N->getFlags()))
     return ROR;
 
   // Canonicalize (or (and X, c1), c2) -> (and (or X, c2), c1|c2)
   // iff (c1 & c2) != 0 or c1/c2 are undef.
   auto MatchIntersect = [](ConstantSDNode *C1, ConstantSDNode *C2) {
     return !C1 || !C2 || C1->getAPIntValue().intersects(C2->getAPIntValue());

llvm/test/CodeGen/AArch64/arm64-rev.ll

entry:
   %4 = or i64 %1, %3
   ret i64 %4
 }
 
 ; Optimize pattern with multiple and/or to a simple pattern which can enable generation of rev16.
 define i64 @test_rev16_x_hwbyteswaps_complex1(i64 %a) nounwind {
 ; CHECK-LABEL: test_rev16_x_hwbyteswaps_complex1:
 ; CHECK:       // %bb.0: // %entry
-; CHECK-NEXT:    lsr x8, x0, #48
-; CHECK-NEXT:    lsr x9, x0, #8
-; CHECK-NEXT:    lsr x10, x0, #32
-; CHECK-NEXT:    and x11, x9, #0xff000000000000
-; CHECK-NEXT:    lsr x12, x0, #16
-; CHECK-NEXT:    bfi x11, x8, #56, #8
-; CHECK-NEXT:    and x8, x9, #0xff00000000
-; CHECK-NEXT:    orr x8, x11, x8
-; CHECK-NEXT:    and x9, x9, #0xff0000
-; CHECK-NEXT:    bfi x8, x10, #40, #8
-; CHECK-NEXT:    orr x8, x8, x9
-; CHECK-NEXT:    ubfiz x9, x0, #8, #8
-; CHECK-NEXT:    bfi x8, x12, #24, #8
-; CHECK-NEXT:    bfxil x8, x0, #8, #8
-; CHECK-NEXT:    orr x0, x8, x9
+; CHECK-NEXT:    rev16 x0, x0
 ; CHECK-NEXT:    ret
 ;
 ; GISEL-LABEL: test_rev16_x_hwbyteswaps_complex1:
 ; GISEL:       // %bb.0: // %entry
 ; GISEL-NEXT:    lsr x8, x0, #8
 ; GISEL-NEXT:    lsl x9, x0, #8
 ; GISEL-NEXT:    and x10, x8, #0xff000000000000
 ; GISEL-NEXT:    and x11, x9, #0xff00000000000000
entry:
   %15 = and i64 %2, 65280
   %16 = or i64 %14, %15
   ret i64 %16
 }
 
 define i64 @test_rev16_x_hwbyteswaps_complex2(i64 %a) nounwind {
 ; CHECK-LABEL: test_rev16_x_hwbyteswaps_complex2:
 ; CHECK:       // %bb.0: // %entry
-; CHECK-NEXT:    lsr x9, x0, #48
-; CHECK-NEXT:    lsr x10, x0, #32
-; CHECK-NEXT:    lsr x8, x0, #8
-; CHECK-NEXT:    lsr x11, x0, #16
-; CHECK-NEXT:    and x8, x8, #0xff00ff00ff00ff
-; CHECK-NEXT:    bfi x8, x9, #56, #8
-; CHECK-NEXT:    bfi x8, x10, #40, #8
-; CHECK-NEXT:    bfi x8, x11, #24, #8
-; CHECK-NEXT:    bfi x8, x0, #8, #8
-; CHECK-NEXT:    mov x0, x8
+; CHECK-NEXT:    rev16 x0, x0
 ; CHECK-NEXT:    ret
 ;
 ; GISEL-LABEL: test_rev16_x_hwbyteswaps_complex2:
 ; GISEL:       // %bb.0: // %entry
 ; GISEL-NEXT:    lsr x8, x0, #8
 ; GISEL-NEXT:    lsl x10, x0, #8
 ; GISEL-NEXT:    and x9, x8, #0xff000000000000
 ; GISEL-NEXT:    and x11, x8, #0xff00000000
entry:
   %16 = or i64 %14, %15
   ret i64 %16
 }
 
 ; Optimize pattern with multiple and/or to a simple pattern which can enable generation of rev16.
 define i64 @test_rev16_x_hwbyteswaps_complex3(i64 %a) nounwind {
 ; CHECK-LABEL: test_rev16_x_hwbyteswaps_complex3:
 ; CHECK:       // %bb.0: // %entry
-; CHECK-NEXT:    lsr x8, x0, #48
-; CHECK-NEXT:    lsr x9, x0, #8
-; CHECK-NEXT:    lsr x10, x0, #32
-; CHECK-NEXT:    and x11, x9, #0xff000000000000
-; CHECK-NEXT:    lsr x12, x0, #16
-; CHECK-NEXT:    bfi x11, x8, #56, #8
-; CHECK-NEXT:    and x8, x9, #0xff00000000
-; CHECK-NEXT:    orr x8, x8, x11
-; CHECK-NEXT:    and x9, x9, #0xff0000
-; CHECK-NEXT:    bfi x8, x10, #40, #8
-; CHECK-NEXT:    orr x8, x9, x8
-; CHECK-NEXT:    ubfiz x9, x0, #8, #8
-; CHECK-NEXT:    bfi x8, x12, #24, #8
-; CHECK-NEXT:    bfxil x8, x0, #8, #8
-; CHECK-NEXT:    orr x0, x9, x8
+; CHECK-NEXT:    rev16 x0, x0
 ; CHECK-NEXT:    ret
 ;
 ; GISEL-LABEL: test_rev16_x_hwbyteswaps_complex3:
 ; GISEL:       // %bb.0: // %entry
 ; GISEL-NEXT:    lsr x8, x0, #8
 ; GISEL-NEXT:    lsl x9, x0, #8
 ; GISEL-NEXT:    and x10, x8, #0xff000000000000
 ; GISEL-NEXT:    and x11, x9, #0xff00000000000000