[AArch64] Fix a corner case in BitFeild select

[weimingz]

Summary

When not useful bits, BitWidth becomes 0 and APInt will not be happy.

See https://llvm.org/bugs/show_bug.cgi?id=25571

We can just mark the operand as IMPLICIT_DEF is none bits of it is used.

[mgrang]

Please fix the typo in the commit title:

BitFeild ==> BitField

lib/Target/AArch64/AArch64ISelDAGToDAG.cpp

1699

Comments should begin with an uppercase letter.

1700

Can we change this to if (!BitWidth) ?

test/CodeGen/AArch64/bitfield-pr25571.ll

2 ↗

(On Diff #40593)

Space between ;RUN

[jmolloy]

This LGTM, Thanks!

lib/Target/AArch64/AArch64ISelDAGToDAG.cpp

1700

I don't agree with this, BitWidth is an integer, not a boolean. "== 0" expresses the intent better than !.

[gberry]

Hi Weiming,

I think your fix is correct, but if fixed differently it may lead to better code being generated. The reason isBitfieldDstMask ends up with a BitWidth of 0 is because isBitfieldInsertOpFromOr has computed that the Or node in question has 0 UsefulBits, which if I understand correctly, means it is dead and could be replaced with an UNDEF node, allowing the instructions feeding to potentially be removed.

[weimingz]

lib/Target/AArch64/AArch64ISelDAGToDAG.cpp

2065

HI Geoff,

The NumberOfIgnoredHighBits is used here to check if we can remove the AND.
The current function
static bool isBitfieldInsertOpFromOr(SDNode *N, unsigned &Opc, SDValue &Dst,

SDValue &Src, unsigned &ImmR,
unsigned &ImmS, SelectionDAG *CurDAG)

always expects a BFM op if it returns true.

I tried putting code like
if (NumberOfIgnoredHighBits == 32) {

  Src = Dst;
}

But it doest make much difference.
mov w8, w0
bfi w8, w8, #8, #24
mov w9, w0
bfi w9, w8, #8, #24
mov w8, w0
bfi w8, w9, #8, #24
bfi w0, w8, #8, #24
lsl w0, w0, #8

[gberry]

lib/Target/AArch64/AArch64ISelDAGToDAG.cpp

2065

I was thinking something more like the following diff, which will eliminate a mov and a bfi from the final code. It seems like if we're already computing the bit-liveness of the 'Or' we should take advantage of it. I'd like to hear someone else's opinion on whether it is worth the effort (since we clearly haven't seen many cases that would hit this or they would have crashed).

@@ -1974,7 +1974,8 @@ static bool isBitfieldPositioningOp(SelectionDAG *CurDAG, SDValue Op,
// f = Opc Opd0, Opd1, LSB, MSB ; where Opc is a BFM, LSB = imm, and MSB = imm2
static bool isBitfieldInsertOpFromOr(SDNode *N, unsigned &Opc, SDValue &Dst,

SDValue &Src, unsigned &ImmR,

• unsigned &ImmS, SelectionDAG *CurDAG) {

+ unsigned &ImmS, SelectionDAG *CurDAG,
+ const APInt &UsefulBits) {

assert(N->getOpcode() == ISD::OR && "Expect a OR operation");
 
// Set Opc

@@ -1988,9 +1989,6 @@ 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();

@@ -2083,11 +2081,17 @@ SDNode *AArch64DAGToDAGISel::SelectBitfieldInsertOp(SDNode *N) {

unsigned Opc;
unsigned LSB, MSB;
SDValue Opd0, Opd1;

+ EVT VT = N->getValueType(0);

• if (!isBitfieldInsertOpFromOr(N, Opc, Opd0, Opd1, LSB, MSB, CurDAG))

+ APInt NUsefulBits;
+ getUsefulBits(SDValue(N, 0), NUsefulBits);
+ if (!NUsefulBits)
+ return CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF, VT);
+
+ if (!isBitfieldInsertOpFromOr(N, Opc, Opd0, Opd1, LSB, MSB, CurDAG,
+ NUsefulBits))

return nullptr;

• EVT VT = N->getValueType(0); SDLoc dl(N); SDValue Ops[] = { Opd0, Opd1,

test/CodeGen/AArch64/bitfield-pr25571.ll

4 ↗

(On Diff #40593)

You can get rid of the datalayout and triple lines (just pass the triple via a -mtriple= command line flag on the run line). You may also want to consider adding this test to another pre-existing test file (perhaps bitfield-insert.ll?).

7 ↗

(On Diff #40593)

Add a ':' after test to avoid false matches.

11 ↗

(On Diff #40593)

Maybe check for an lsl at the end as well?

12 ↗

(On Diff #40593)

This comment should be: 0 0 0 A

[weimingz]

Hi Geoff,

Very appreciate! I think you're right. And it can save a BFI instruction.

[gberry]

This change looks good to me (but that's not too suprising, since it's pretty much the change I suggested). I would like to hear from Tim or James on whether they think this small added code complexity is worth it (as opposed to just going with the original fix).

[jmolloy]

This still looks OK to me.

lib/Target/AArch64/AArch64ISelDAGToDAG.cpp

 /// this asks whether DstMask zeroes precisely those bits that will be set by
 /// the other half.
 static bool isBitfieldDstMask(uint64_t DstMask, APInt BitsToBeInserted,
                               unsigned NumberOfIgnoredHighBits, EVT VT) {
   assert((VT == MVT::i32 || VT == MVT::i64) &&
          "i32 or i64 mask type expected!");
   unsigned BitWidth = VT.getSizeInBits() - NumberOfIgnoredHighBits;
 
   APInt SignificantDstMask = APInt(BitWidth, DstMask);
   APInt SignificantBitsToBeInserted = BitsToBeInserted.zextOrTrunc(BitWidth);
 
   return (SignificantDstMask & SignificantBitsToBeInserted) == 0 &&
          (SignificantDstMask | SignificantBitsToBeInserted).isAllOnesValue();
 }
 
 // Look for bits that will be useful for later uses.
 // A bit is consider useless as soon as it is dropped and never used
 // before it as been dropped.

 // d = e & mask2 ; where mask is a binary sequence of 1..10..0 and
 //                 countTrailingZeros(mask2) == imm2 - imm + 1
 // f = d | c
 // if yes, given reference arguments will be update so that one can replace
 // the OR instruction with:
 // f = Opc Opd0, Opd1, LSB, MSB ; where Opc is a BFM, LSB = imm, and MSB = imm2
 static bool isBitfieldInsertOpFromOr(SDNode *N, unsigned &Opc, SDValue &Dst,
                                      SDValue &Src, unsigned &ImmR,
-                                     unsigned &ImmS, SelectionDAG *CurDAG) {
+                                     unsigned &ImmS, const APInt &UsefulBits,
+                                     SelectionDAG *CurDAG) {
   assert(N->getOpcode() == ISD::OR && "Expect a OR operation");
 
   // Set Opc
   EVT VT = N->getValueType(0);
   if (VT == MVT::i32)
     Opc = AArch64::BFMWri;
   else if (VT == MVT::i64)
     Opc = AArch64::BFMXri;
   else
     return false;
 
   // 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 all combinations of operand order and values of
   // BiggerPattern, i.e.
   //     Opd0, Opd1, BiggerPattern=false
   //     Opd1, Opd0, BiggerPattern=false
for (int I = 0; I < 4; ++I) {
     if ((BitsToBeInserted & ~KnownZero) != 0)
       continue;
 
     // Set the first operand
     uint64_t Imm;
     if (isOpcWithIntImmediate(OrOpd1, ISD::AND, Imm) &&
         isBitfieldDstMask(Imm, BitsToBeInserted, NumberOfIgnoredHighBits, VT))
       // In that case, we can eliminate the AND
       Dst = OrOpd1->getOperand(0);
     else
       // Maybe the AND has been removed by simplify-demanded-bits
       // or is useful because it discards more bits
       Dst = OrOpd1Val;
 
     // both parts match
     return true;
   }
 
   return false;
 }
 
 SDNode *AArch64DAGToDAGISel::SelectBitfieldInsertOp(SDNode *N) {
   if (N->getOpcode() != ISD::OR)
     return nullptr;
 
   unsigned Opc;
   unsigned LSB, MSB;
   SDValue Opd0, Opd1;
+  EVT VT = N->getValueType(0);
+  APInt NUsefulBits;
+  getUsefulBits(SDValue(N, 0), NUsefulBits);
+
+  // If all bits are not useful, just return UNDEF.
+  if (!NUsefulBits)
+    return CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF, VT);
 
-  if (!isBitfieldInsertOpFromOr(N, Opc, Opd0, Opd1, LSB, MSB, CurDAG))
+  if (!isBitfieldInsertOpFromOr(N, Opc, Opd0, Opd1, LSB, MSB, NUsefulBits,
+                                CurDAG))
     return nullptr;
 
-  EVT VT = N->getValueType(0);
   SDLoc dl(N);
   SDValue Ops[] = { Opd0,
                     Opd1,
                     CurDAG->getTargetConstant(LSB, dl, VT),
                     CurDAG->getTargetConstant(MSB, dl, VT) };
   return CurDAG->SelectNodeTo(N, Opc, VT, Ops);
 }
 

test/CodeGen/AArch64/bitfield-insert.ll

; CHECK-LABEL: test_32bit_opnd1_better:
 
   %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
 }
+
+; Tests when all the bits from one operand are not useful
+define i32 @test_nouseful_bits(i8 %a, i32 %b) {
+; CHECK-LABEL: test_nouseful_bits:
+; CHECK: bfi
+; CHECK: bfi
+; CHECK: bfi
+; CHECK-NOT: bfi
+; CHECK-NOT: or
+; CHECK: lsl
+  %conv = zext i8 %a to i32     ;   0  0  0  A
+  %shl = shl i32 %b, 8          ;   B2 B1 B0 0
+  %or = or i32 %conv, %shl      ;   B2 B1 B0 A
+  %shl.1 = shl i32 %or, 8       ;   B1 B0 A 0
+  %or.1 = or i32 %conv, %shl.1  ;   B1 B0 A A
+  %shl.2 = shl i32 %or.1, 8     ;   B0 A A 0
+  %or.2 = or i32 %conv, %shl.2  ;   B0 A A A
+  %shl.3 = shl i32 %or.2, 8     ;   A A A 0
+  %or.3 = or i32 %conv, %shl.3  ;   A A A A
+  %shl.4 = shl i32 %or.3, 8     ;   A A A 0
+  ret i32 %shl.4
+}