[AArch64] Improved bitfield instruction selection.

[gberry]

Summary

For bitfield insert OR matching, check both operands for larger pattern
first before checking for smaller pattern.

Add pattern for unsigned bitfield insert-in-zero done with SHL+AND.

Resolves PR21631.

[jmolloy]

Hi Geoff,

Thanks for working on this. I have some comments below.

Cheers,

James

lib/Target/AArch64/AArch64ISelDAGToDAG.cpp

1924

This is called from 3 places after your patch. 2 of them explicitly set BiggerPattern.

It would make sense to remove the default from this parameter and just set it in the last callsite. This would also allow you to put the output MaskWidth at the end of the argument list.

1964

The code here appears to contradict the comment - which is correct?

2004–2019

Please use a capital for induction variables. I is normal.

2006

I now understand what's going on here after some grepping and grokking, but this comment wasn't as helpful as it could have been. My understanding is:

There are situations where both isBitfieldExtractOp(A, B, true) and isBitfieldExtractOp(B, A, false) match. The latter should give better results.

Perhaps expanding a bit more in that comment would ease understanding?

Also, please capitalize first letters of sentences and end with a full stop (and spell out "operand" in full).

2110

This isn't a particularly useful comment.

2120

"Op0" would be more in keeping with the rest of LLVM.

2126

A comment here explaining what the immediate values are and why would be useful.

[gberry]

Update to address comments from James Molloy

[gberry]

James, thanks for the comments. I've added a new revision which should hopefully address all of them.

[jmolloy]

LGTM, thanks!

lib/Target/AArch64/AArch64ISelDAGToDAG.cpp

public:
 
   SDNode *SelectStore(SDNode *N, unsigned NumVecs, unsigned Opc);
   SDNode *SelectPostStore(SDNode *N, unsigned NumVecs, unsigned Opc);
   SDNode *SelectStoreLane(SDNode *N, unsigned NumVecs, unsigned Opc);
   SDNode *SelectPostStoreLane(SDNode *N, unsigned NumVecs, unsigned Opc);
 
   SDNode *SelectBitfieldExtractOp(SDNode *N);
   SDNode *SelectBitfieldInsertOp(SDNode *N);
+  SDNode *SelectBitfieldInsertInZeroOp(SDNode *N);
 
   SDNode *SelectLIBM(SDNode *N);
   SDNode *SelectFPConvertWithRound(SDNode *N);
 
   SDNode *SelectReadRegister(SDNode *N);
   SDNode *SelectWriteRegister(SDNode *N);
 
 // Include the pieces autogenerated from the target description.
static SDValue getLeftShift(SelectionDAG *CurDAG, SDValue Op, int ShlAmount) {
   }
 
   return SDValue(ShiftNode, 0);
 }
 
 /// Does this tree qualify as an attempt to move a bitfield into position,
 /// essentially "(and (shl VAL, N), Mask)".
 static bool isBitfieldPositioningOp(SelectionDAG *CurDAG, SDValue Op,
+                                    bool BiggerPattern,
                                     SDValue &Src, int &ShiftAmount,
                                     int &MaskWidth) {
   EVT VT = Op.getValueType();
   unsigned BitWidth = VT.getSizeInBits();
   (void)BitWidth;
   assert(BitWidth == 32 || BitWidth == 64);
 
   APInt KnownZero, KnownOne;
   CurDAG->computeKnownBits(Op, 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();
 
   // Discard a constant AND mask if present. It's safe because the node will
   // already have been factored into the computeKnownBits calculation above.
   uint64_t AndImm;
   if (isOpcWithIntImmediate(Op.getNode(), ISD::AND, AndImm)) {
     assert((~APInt(BitWidth, AndImm) & ~KnownZero) == 0);
     Op = Op.getOperand(0);
   }
 
+  // Don't match if the SHL has more than one use, since then we'll end up
+  // generating SHL+UBFIZ instead of just keeping SHL+AND.
+  if (!BiggerPattern && !Op.hasOneUse())
+    return false;
+
   uint64_t ShlImm;
   if (!isOpcWithIntImmediate(Op.getNode(), ISD::SHL, ShlImm))
     return false;
   Op = Op.getOperand(0);
 
   if (!isShiftedMask_64(NonZeroBits))
     return false;
 
   ShiftAmount = countTrailingZeros(NonZeroBits);
   MaskWidth = countTrailingOnes(NonZeroBits >> ShiftAmount);
 
   // BFI encompasses sufficiently many nodes that it's worth inserting an extra
   // LSL/LSR if the mask in NonZeroBits doesn't quite match up with the ISD::SHL
-  // amount.
+  // amount.  BiggerPattern is true when this pattern is being matched for BFI,
+  // BiggerPattern is false when this pattern is being matched for UBFIZ, in
+  // which case it is not profitable to insert an extra shift.
+  if (ShlImm - ShiftAmount != 0 && !BiggerPattern)
+    return false;
   Src = getLeftShift(CurDAG, Op, ShlImm - ShiftAmount);
 
   return true;
 }
 
 // Given a OR operation, check if we have the following pattern
 // ubfm c, b, imm, imm2 (or something that does the same jobs, see
 //                       isBitfieldExtractOp)
static bool isBitfieldInsertOpFromOr(SDNode *N, unsigned &Opc, SDValue &Dst,
   // Because of simplify-demanded-bits in DAGCombine, involved masks may not
   // have the expected shape. Try to undo that.
   APInt UsefulBits;
   getUsefulBits(SDValue(N, 0), UsefulBits);
 
   unsigned NumberOfIgnoredLowBits = UsefulBits.countTrailingZeros();
   unsigned NumberOfIgnoredHighBits = UsefulBits.countLeadingZeros();
 
-  // OR is commutative, check both possibilities (does llvm provide a
-  // way to do that directely, e.g., via code matcher?)
-  SDValue OrOpd1Val = N->getOperand(1);
-  SDNode *OrOpd0 = N->getOperand(0).getNode();
-  SDNode *OrOpd1 = N->getOperand(1).getNode();
-  for (int i = 0; i < 2;
-       ++i, std::swap(OrOpd0, OrOpd1), OrOpd1Val = N->getOperand(0)) {
+  // OR is commutative, check all combinations of operand order and values of
+  // BiggerPattern, i.e.
+  //     Opd0, Opd1, BiggerPattern=false
+  //     Opd1, Opd0, BiggerPattern=false
+  //     Opd0, Opd1, BiggerPattern=true
+  //     Opd1, Opd0, BiggerPattern=true
+  // Several of these combinations may match, so check with BiggerPattern=false
+  // first since that will produce better results by matching more instructions
+  // and/or inserting fewer extra instructions.
+  for (int I = 0; I < 4; ++I) {
+
+    bool BiggerPattern = I / 2;
+    SDNode *OrOpd0 = N->getOperand(I % 2).getNode();
+    SDValue OrOpd1Val = N->getOperand((I + 1) % 2);
+    SDNode *OrOpd1 = OrOpd1Val.getNode();
+
     unsigned BFXOpc;
     int DstLSB, Width;
     if (isBitfieldExtractOp(CurDAG, OrOpd0, BFXOpc, Src, ImmR, ImmS,
-                            NumberOfIgnoredLowBits, true)) {
+                            NumberOfIgnoredLowBits, BiggerPattern)) {
       // Check that the returned opcode is compatible with the pattern,
       // i.e., same type and zero extended (U and not S)
       if ((BFXOpc != AArch64::UBFMXri && VT == MVT::i64) ||
           (BFXOpc != AArch64::UBFMWri && VT == MVT::i32))
         continue;
 
       // Compute the width of the bitfield insertion
       DstLSB = 0;
       Width = ImmS - ImmR + 1;
       // FIXME: This constraint is to catch bitfield insertion we may
       // want to widen the pattern if we want to grab general bitfied
       // move case
       if (Width <= 0)
         continue;
 
       // If the mask on the insertee is correct, we have a BFXIL operation. We
       // can share the ImmR and ImmS values from the already-computed UBFM.
-    } else if (isBitfieldPositioningOp(CurDAG, SDValue(OrOpd0, 0), Src,
-                                       DstLSB, Width)) {
+    } else if (isBitfieldPositioningOp(CurDAG, SDValue(OrOpd0, 0),
+                                       BiggerPattern,
+                                       Src, DstLSB, Width)) {
       ImmR = (VT.getSizeInBits() - DstLSB) % VT.getSizeInBits();
       ImmS = Width - 1;
     } else
       continue;
 
     // Check the second part of the pattern
     EVT VT = OrOpd1->getValueType(0);
     assert((VT == MVT::i32 || VT == MVT::i64) && "unexpected OR operand");
SDNode *AArch64DAGToDAGISel::SelectBitfieldInsertOp(SDNode *N) {
   SDLoc dl(N);
   SDValue Ops[] = { Opd0,
                     Opd1,
                     CurDAG->getTargetConstant(LSB, dl, VT),
                     CurDAG->getTargetConstant(MSB, dl, VT) };
   return CurDAG->SelectNodeTo(N, Opc, VT, Ops);
 }
 
+/// 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.
+SDNode *AArch64DAGToDAGISel::SelectBitfieldInsertInZeroOp(SDNode *N) {
+  if (N->getOpcode() != ISD::AND)
+    return nullptr;
+
+  EVT VT = N->getValueType(0);
+  unsigned Opc;
+  if (VT == MVT::i32)
+    Opc = AArch64::UBFMWri;
+  else if (VT == MVT::i64)
+    Opc = AArch64::UBFMXri;
+  else
+    return nullptr;
+
+  SDValue Op0;
+  int DstLSB, Width;
+  if (!isBitfieldPositioningOp(CurDAG, SDValue(N, 0), /*BiggerPattern=*/false,
+                               Op0, DstLSB, Width))
+    return nullptr;
+
+  // ImmR is the rotate right amount.
+  unsigned ImmR = (VT.getSizeInBits() - DstLSB) % VT.getSizeInBits();
+  // ImmS is the most significant bit of the source to be moved.
+  unsigned ImmS = Width - 1;
+
+  SDLoc DL(N);
+  SDValue Ops[] = {Op0, CurDAG->getTargetConstant(ImmR, DL, VT),
+                   CurDAG->getTargetConstant(ImmS, DL, VT)};
+  return CurDAG->SelectNodeTo(N, Opc, VT, Ops);
+}
+
 /// GenerateInexactFlagIfNeeded - Insert FRINTX instruction to generate inexact
 /// signal on round-to-integer operations if needed. C11 leaves it
 /// implementation-defined whether these operations trigger an inexact
 /// exception. IEEE says they don't.  Unfortunately, Darwin decided they do so
 /// we sometimes have to insert a special instruction just to set the right bit
 /// in FPSR.
 SDNode *AArch64DAGToDAGISel::GenerateInexactFlagIfNeeded(const SDValue &In,
                                                          unsigned InTyVariant,
case ISD::LOAD: {
     break;
   }
 
   case ISD::SRL:
   case ISD::AND:
   case ISD::SRA:
     if (SDNode *I = SelectBitfieldExtractOp(Node))
       return I;
+    if (SDNode *I = SelectBitfieldInsertInZeroOp(Node))
+      return I;
     break;
 
   case ISD::OR:
     if (SDNode *I = SelectBitfieldInsertOp(Node))
       return I;
     break;
 
   case ISD::EXTRACT_VECTOR_ELT: {

test/CodeGen/AArch64/bitfield-insert.ll

; CHECK-LABEL: test_32bit_with_shr:
 
   %combined = or i32 %oldval_keep, %newval_masked
   store volatile i32 %combined, i32* %existing
 ; CHECK: lsr [[BIT:w[0-9]+]], {{w[0-9]+}}, #14
 ; CHECK: bfi {{w[0-9]+}}, [[BIT]], #26, #5
 
   ret void
 }
+
+; Bitfield insert where the second or operand is a better match to be folded into the BFM
+define void @test_32bit_opnd1_better(i32* %existing, i32* %new) {
+; CHECK-LABEL: test_32bit_opnd1_better:
+
+  %oldval = load volatile i32, i32* %existing
+  %oldval_keep = and i32 %oldval, 65535 ; 0x0000ffff
+
+  %newval = load i32, i32* %new
+  %newval_shifted = shl i32 %newval, 16
+  %newval_masked = and i32 %newval_shifted, 16711680 ; 0x00ff0000
+
+  %combined = or i32 %oldval_keep, %newval_masked
+  store volatile i32 %combined, i32* %existing
+; CHECK: and [[BIT:w[0-9]+]], {{w[0-9]+}}, #0xffff
+; CHECK: bfi [[BIT]], {{w[0-9]+}}, #16, #8
+
+  ret void
+}

test/CodeGen/AArch64/xbfiz.ll

 
 define i32 @ubfiz32(i32 %v) {
 ; CHECK-LABEL: ubfiz32:
 ; CHECK: ubfiz  w0, w0, #6, #24
   %shl = shl i32 %v, 8
   %shr = lshr i32 %shl, 2
   ret i32 %shr
 }
+
+define i64 @ubfiz64and(i64 %v) {
+; CHECK-LABEL: ubfiz64and:
+; CHECK: ubfiz  x0, x0, #36, #11
+  %shl = shl i64 %v, 36
+  %and = and i64 %shl, 140668768878592
+  ret i64 %and
+}
+
+define i32 @ubfiz32and(i32 %v) {
+; CHECK-LABEL: ubfiz32and:
+; CHECK: ubfiz  w0, w0, #6, #24
+  %shl = shl i32 %v, 6
+  %and = and i32 %shl, 1073741760
+  ret i32 %and
+}
+
+; Check that we don't generate a ubfiz if the lsl has more than one
+; use, since we'd just be replacing an and with a ubfiz.
+define i32 @noubfiz32(i32 %v) {
+; CHECK-LABEL: noubfiz32:
+; CHECK: lsl  w[[REG1:[0-9]+]], w0, #6
+; CHECK: and  w[[REG2:[0-9]+]], w[[REG1]], #0x3fffffc0
+; CHECK: add  w0, w[[REG1]], w[[REG2]]
+; CHECK: ret
+  %shl = shl i32 %v, 6
+  %and = and i32 %shl, 1073741760
+  %add = add i32 %shl, %and
+  ret i32 %add
+}