[AArch64] Generate a BFI/BFXIL from 'or (and X, MaskImm), OrImm' iff the value being inserted only sets known zero bits.

[mcrosier]

Summary

This combine transforms things like

and     w8, w0, #0xfffffff0
movz    w9, #5
orr             w0, w8, w9

to

movz    w8, #5
bfxil   w0, w8, #0, #4

The combine is tuned to make sure we always reduce the number of instructions. We avoid churning code for what is expected to be performance neutral changes (e.g., converted AND+OR to OR+BFI).

Please take a look,
Chad

[mcrosier]

Rebase patch and fix a few spelling errors.

[mcrosier]

Rebase

[gberry]

lib/Target/AArch64/AArch64ISelDAGToDAG.cpp

2019

NotKnownZero might be a clearer name for this, or just get rid of it and use ~KnownZeroBits instead.

2023

I think this is too conservative. It should be okay to have bits that are 1 in the OrImm that are not KnownZero, since you know they will be 1 in the final result. E.g. (or (and x, 0xfffffff0), 0xf5). Essentially the known bits in the final result are KnownZero | OrImm.

Actually, maybe none of the above matters since the IR seems to be canonicalized in this case to widen the and mask to cover all of the 1 bits in the or mask as well.

test/CodeGen/AArch64/bitfield-insert.ll

381

You might want to change the hard-coded x8/w8 to a regex in these tests to make them a little less brittle w.r.t. future changes.

449

requires -> require

[mcrosier]

Address Geoff's feedback.

[mcrosier]

lib/Target/AArch64/AArch64ISelDAGToDAG.cpp

2023

I agree this may be conservative, but I'm going to defer this improvement for the moment.

[jmolloy]

LGTM!

lib/Target/AArch64/AArch64ISelDAGToDAG.cpp

 
 static bool isShiftedMask(uint64_t Mask, EVT VT) {
   assert(VT == MVT::i32 || VT == MVT::i64);
   if (VT == MVT::i32)
     return isShiftedMask_32(Mask);
   return isShiftedMask_64(Mask);
 }
 
+// Generate a BFI/BFXIL from 'or (and X, MaskImm), OrImm' iff the value being
+// inserted only sets known zero bits.
+static bool tryBitfieldInsertOpFromOrAndImm(SDNode *N, SelectionDAG *CurDAG) {
+  assert(N->getOpcode() == ISD::OR && "Expect a OR operation");
+
+  EVT VT = N->getValueType(0);
+  if (VT != MVT::i32 && VT != MVT::i64)
+    return false;
+
+  unsigned BitWidth = VT.getSizeInBits();
+
+  uint64_t OrImm;
+  if (!isOpcWithIntImmediate(N, ISD::OR, OrImm))
+    return false;
+
+  // Skip this transformation if the ORR immediate can be encoded in the ORR.
+  // Otherwise, we'll trade an AND+ORR for ORR+BFI/BFXIL, which is most likely
+  // performance neutral.
+  if (AArch64_AM::isLogicalImmediate(OrImm, BitWidth))
+    return false;
+
+  uint64_t MaskImm;
+  SDValue And = N->getOperand(0);
+  // Must be a single use AND with an immediate operand.
+  if (!And.hasOneUse() ||
+      !isOpcWithIntImmediate(And.getNode(), ISD::AND, MaskImm))
+    return false;
+
+  // Compute the Known Zero for the AND as this allows us to catch more general
+  // cases than just looking for AND with imm.
+  APInt KnownZero, KnownOne;
+  CurDAG->computeKnownBits(And, KnownZero, KnownOne);
+
+  // Non-zero in the sense that they're not provably zero, which is the key
+  // point if we want to use this value.
+  uint64_t NonZeroBits = (~KnownZero).getZExtValue();
+
+  // The bits being inserted must only set those bits that are known to be zero
+  // and the bits to be inserted must be a shifted mask.
+  if ((OrImm & NonZeroBits) != 0 || !isShiftedMask(~NonZeroBits, VT))
+    return false;
+
+  // BFI/BFXIL dst, src, #lsb, #width.
+  int LSB = countTrailingOnes(NonZeroBits);
+  int Width = BitWidth - APInt(BitWidth, NonZeroBits).countPopulation();
+
+  // BFI/BFXIL is an alias of BFM, so translate to BFM operands.
+  unsigned ImmR = (BitWidth - LSB) % BitWidth;
+  unsigned ImmS = Width - 1;
+
+  // If we're creating a BFI instruction avoid cases where we need more
+  // instructions to materialize the BFI constant as compared to the original
+  // ORR.  A BFXIL will use the same constant as the original ORR, so the code
+  // should be no worse in this case.
+  bool IsBFI = LSB != 0;
+  uint64_t BFIImm = OrImm >> LSB;
+  if (IsBFI && !AArch64_AM::isLogicalImmediate(BFIImm, BitWidth)) {
+    // We have a BFI instruction and we know the constant can't be materialized
+    // with a ORR-immediate with the zero register.
+    unsigned OrChunks = 0, BFIChunks = 0;
+    for (unsigned Shift = 0; Shift < BitWidth; Shift += 16) {
+      if (((OrImm >> Shift) & 0xFFFF) != 0)
+        ++OrChunks;
+      if (((BFIImm >> Shift) & 0xFFFF) != 0)
+        ++BFIChunks;
+    }
+    if (BFIChunks > OrChunks)
+      return false;
+  }
+
+  // Materialize the constant to be inserted.
+  SDLoc DL(N);
+  unsigned MOVIOpc = VT == MVT::i32 ? AArch64::MOVi32imm : AArch64::MOVi64imm;
+  SDNode *MOVI = CurDAG->getMachineNode(
+      MOVIOpc, DL, VT, CurDAG->getTargetConstant(BFIImm, DL, VT));
+
+  // Create the BFI/BFXIL instruction.
+  SDValue Ops[] = {And.getOperand(0), SDValue(MOVI, 0),
+                   CurDAG->getTargetConstant(ImmR, DL, VT),
+                   CurDAG->getTargetConstant(ImmS, DL, VT)};
+  unsigned Opc = (VT == MVT::i32) ? AArch64::BFMWri : AArch64::BFMXri;
+  CurDAG->SelectNodeTo(N, Opc, VT, Ops);
+  return true;
+}
+
 static bool tryBitfieldInsertOpFromOr(SDNode *N, const APInt &UsefulBits,
                                       SelectionDAG *CurDAG) {
   assert(N->getOpcode() == ISD::OR && "Expect a OR operation");
 
   EVT VT = N->getValueType(0);
   if (VT != MVT::i32 && VT != MVT::i64)
     return false;
 
if (And0.hasOneUse() && And1.hasOneUse() &&
     // Create the BFXIL instruction.
     SDValue Ops[] = {Dst, SDValue(LSR, 0),
                      CurDAG->getTargetConstant(ImmR, DL, VT),
                      CurDAG->getTargetConstant(ImmS, DL, VT)};
     unsigned Opc = (VT == MVT::i32) ? AArch64::BFMWri : AArch64::BFMXri;
     CurDAG->SelectNodeTo(N, Opc, VT, Ops);
     return true;
   }
-
   return false;
 }
 
 bool AArch64DAGToDAGISel::tryBitfieldInsertOp(SDNode *N) {
   if (N->getOpcode() != ISD::OR)
     return false;
 
   APInt NUsefulBits;
   getUsefulBits(SDValue(N, 0), NUsefulBits);
 
   // If all bits are not useful, just return UNDEF.
   if (!NUsefulBits) {
     CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF, N->getValueType(0));
     return true;
   }
 
-  return tryBitfieldInsertOpFromOr(N, NUsefulBits, CurDAG);
+  if (tryBitfieldInsertOpFromOr(N, NUsefulBits, CurDAG))
+    return true;
+
+  return tryBitfieldInsertOpFromOrAndImm(N, CurDAG);
 }
 
 /// SelectBitfieldInsertInZeroOp - Match a UBFIZ instruction that is the
 /// equivalent of a left shift by a constant amount followed by an and masking
 /// out a contiguous set of bits.
 bool AArch64DAGToDAGISel::tryBitfieldInsertInZeroOp(SDNode *N) {
   if (N->getOpcode() != ISD::AND)
     return false;

test/CodeGen/AArch64/bitfield-insert.ll

 define i32 @test_or_and_and5(i32 %a, i32 %b, i32* %ptr) {
 entry:
   %and = and i32 %b, 65520
   store i32 %and, i32* %ptr, align 4
   %and1 = and i32 %a, -65521
   %or = or i32 %and, %and1
   ret i32 %or
 }
+
+; CHECK-LABEL: @test1
+; CHECK: movz w8, #5
+; CHECK: bfxil w0, w8, #0, #4
+define i32 @test1(i32 %a) {
+  %1 = and i32 %a, -16 ; 0xfffffff0
+  %2 = or i32 %1, 5    ; 0x00000005
+  ret i32 %2
+}
+
+; CHECK-LABEL: @test2
+; CHECK: movz w8, #10
+; CHECK: bfi w0, w8, #22, #4
+define i32 @test2(i32 %a) {
+  %1 = and i32 %a, -62914561 ; 0xfc3fffff
+  %2 = or i32 %1, 41943040   ; 0x06400000
+  ret i32 %2
+}
+
+; CHECK-LABEL: @test3
+; CHECK: movz x8, #5
+; CHECK: bfxil x0, x8, #0, #3
+define i64 @test3(i64 %a) {
+  %1 = and i64 %a, -8 ; 0xfffffffffffffff8
+  %2 = or i64 %1, 5   ; 0x0000000000000005
+  ret i64 %2
+}
+
+; CHECK-LABEL: @test4
+; CHECK: movz x8, #9
+; CHECK: bfi x0, x8, #1, #7
+define i64 @test4(i64 %a) {
+  %1 = and i64 %a, -255 ; 0xffffffffffffff01
+  %2 = or i64 %1,  18   ; 0x0000000000000012
+  ret i64 %2
+}
+
+; Don't generate BFI/BFXIL if the immediate can be encoded in the ORR.
+; CHECK-LABEL: @test5
+; CHECK: and w8, w0, #0xfffffff0
+; CHECK: orr w0, w8, #0x6
+define i32 @test5(i32 %a) {
+  %1 = and i32 %a, 4294967280 ; 0xfffffff0
+  %2 = or i32 %1, 6           ; 0x00000006
+  ret i32 %2
+}
+
+; BFXIL will use the same constant as the ORR, so we don't care how the constant
+; is materialized (it's an equal cost either way).
+; CHECK-LABEL: @test6
+; CHECK: movz w8, #11, lsl #16
+; CHECK: movk w8, #23250
+; CHECK: bfxil w0, w8, #0, #20
+define i32 @test6(i32 %a) {
+  %1 = and i32 %a, 4293918720 ; 0xfff00000
+  %2 = or i32 %1, 744146      ; 0x000b5ad2
+  ret i32 %2
+}
+
+; BFIs that require the same number of instruction to materialize the constant
+; as the original ORR are okay.
+; CHECK-LABEL: @test7
+define i32 @test7(i32 %a) {
+  %1 = and i32 %a, 4293918721 ; 0xfff00001
+  %2 = or i32 %1, 744146      ; 0x000b5ad2
+  ret i32 %2
+}
+
+; BFIs that requires more instructions to materialize the constant as compared
+; to the original ORR are not okay.  In this case we would be replacing the
+; 'and' with a 'movk', which would decrease ILP while using the same number of
+; instructions.
+; CHECK: @test8
+; CHECK: movz x9, #36694, lsl #32
+; CHECK: and x8, x0, #0xff000000000000ff
+; CHECK: movk x9, #31059, lsl #16
+; CHECK: orr x0, x8, x9
+define i64 @test8(i64 %a) {
+  %1 = and i64 %a, -72057594037927681 ; 0xff000000000000ff
+  %2 = or i64 %1, 157601565442048     ; 0x00008f5679530000
+  ret i64 %2
+}