[AArch64] Fold lsr+bfi in tryBitfieldInsertOpFromOr

[bcl5980]

Summary

In tryBitfieldInsertOpFromOr, if the new created LSR Node's source is LSR with Imm shift, try to fold them into one LSR.

Fix https://github.com/llvm/llvm-project/issues/54696

[bcl5980]

If we have better solution on IR or SelectionDAG I will abandon the patch

[efriedma]

It looks like the lsr+bfi is coming out of tryBitfieldInsertOpFromOr in AArch64ISelDAGToDAG.cpp. I see two possible alternatives:

1. Enhance tryBitfieldInsertOpFromOr to detect when it's shifting a shift.
2. Form the BFM op as a DAGCombine, instead of waiting for isel.

This MI peephole seems unlikely to be useful outside of this one case, so I think I'd prefer to fix the existing logic.

[benshi001]

I would prefer AArch64 specific DAGCombine.

[bcl5980]

In D122915#3424047, @benshi001 wrote:

I would prefer AArch64 specific DAGCombine.

In D122915#3423539, @efriedma wrote:

2. Form the BFM op as a DAGCombine, instead of waiting for isel.

For now test case's selection DAG before instruction select is:

t0: ch = EntryToken
t2: i32,ch = CopyFromReg t0, Register:i32 %0
      t7: i32 = srl t2, Constant:i64<16>
    t9: i32 = and t7, Constant:i32<240>
    t4: i32 = and t2, Constant:i32<-241>
  t10: i32 = or t9, t4
t12: ch,glue = CopyToReg t0, Register:i32 $w0, t10
t13: ch = AArch64ISD::RET_FLAG t12, Register:i32 $w0, t12:1

Do you mean we add a new AArch64ISD like AArch64ISD::BFM, then form AArch64ISD::BFM in performOrCombine ?

[bcl5980]

Fix #54696 in tryBitfieldInsertOpFromOr

[bcl5980]

In D122915#3423539, @efriedma wrote:

It looks like the lsr+bfi is coming out of tryBitfieldInsertOpFromOr in AArch64ISelDAGToDAG.cpp. I see two possible alternatives:

1. Enhance tryBitfieldInsertOpFromOr to detect when it's shifting a shift.
2. Form the BFM op as a DAGCombine, instead of waiting for isel.

This MI peephole seems unlikely to be useful outside of this one case, so I think I'd prefer to fix the existing logic.

@efriedma is the new patch match solution 1?
And if possible can you help to explain solution 2?
I'm a beginner on llvm so it will be grateful if you can tell me the detail solution.

[efriedma]

Yes, this is my "solution 1". "Solution 2" would be defining AArch64ISD::BFM, and moving all the code from tryBitfieldInsertOpFromOr into a DAGCombine. The advantage of that is that we can perform general DAGCombine optimizations afterwards, not just this specific one. The disadvantage is that you have to be careful not to block other optimizations. (And it's more work to modify the current code.)

@benshi001 any further thoughts?

[bcl5980]

In D122915#3431002, @efriedma wrote:

Yes, this is my "solution 1". "Solution 2" would be defining AArch64ISD::BFM, and moving all the code from tryBitfieldInsertOpFromOr into a DAGCombine. The advantage of that is that we can perform general DAGCombine optimizations afterwards, not just this specific one. The disadvantage is that you have to be careful not to block other optimizations. (And it's more work to modify the current code.)

Thanks for the detail explaination.

[bcl5980]

I have no commit access so can someone help me to check in the code ?
name: chenglin.bi
email: [e-mail]

[benshi001]

https://github.com/llvm/llvm-project/commit/87f0d55304a27ce0f6178eed65d8dad49b5dcfd9

You need to add your working email to your github account, to show your commit properly.

[bcl5980]

In D122915#3432859, @benshi001 wrote:

https://github.com/llvm/llvm-project/commit/87f0d55304a27ce0f6178eed65d8dad49b5dcfd9

You need to add your working email to your github account, to show your commit properly.

Thanks for mentioning it

llvm/lib/Target/AArch64/AArch64ISelDAGToDAG.cpp

if (And0.hasOneUse() && And1.hasOneUse() &&
     SDValue Dst = And0->getOperand(0);
     unsigned LSB = countTrailingZeros(Mask1Imm);
     int Width = BitWidth - APInt(BitWidth, Mask0Imm).countPopulation();
 
     // The BFXIL inserts the low-order bits from a source register, so right
     // shift the needed bits into place.
     SDLoc DL(N);
     unsigned ShiftOpc = (VT == MVT::i32) ? AArch64::UBFMWri : AArch64::UBFMXri;
+    uint64_t LsrImm = LSB;
+    if (Src->hasOneUse() &&
+        isOpcWithIntImmediate(Src.getNode(), ISD::SRL, LsrImm) &&
+        (LsrImm + LSB) < BitWidth) {
+      Src = Src->getOperand(0);
+      LsrImm += LSB;
+    }
+
     SDNode *LSR = CurDAG->getMachineNode(
-        ShiftOpc, DL, VT, Src, CurDAG->getTargetConstant(LSB, DL, VT),
+        ShiftOpc, DL, VT, Src, CurDAG->getTargetConstant(LsrImm, DL, VT),
         CurDAG->getTargetConstant(BitWidth - 1, DL, VT));
 
     // BFXIL is an alias of BFM, so translate to BFM operands.
     unsigned ImmR = (BitWidth - LSB) % BitWidth;
     unsigned ImmS = Width - 1;
 
     // Create the BFXIL instruction.
     SDValue Ops[] = {Dst, SDValue(LSR, 0),

llvm/test/CodeGen/AArch64/aarch64-lsr-bfi.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=aarch64-none-linux-gnu < %s -o -| FileCheck %s
+
+define i32 @lsr_bfi(i32 %a) {
+; CHECK-LABEL: lsr_bfi:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    lsr w8, w0, #20
+; CHECK-NEXT:    bfi w0, w8, #4, #4
+; CHECK-NEXT:    ret
+  %and1 = and i32 %a, -241
+  %1 = lshr i32 %a, 16
+  %shl = and i32 %1, 240
+  %or = or i32 %shl, %and1
+  ret i32 %or
+}
+
+define i32 @negative_lsr_bfi0(i32 %a) {
+; CHECK-LABEL: negative_lsr_bfi0:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    and w0, w0, #0xffffff0f
+; CHECK-NEXT:    ret
+  %and1 = and i32 %a, -241
+  %1 = lshr i32 %a, 28
+  %shl = and i32 %1, 240
+  %or = or i32 %shl, %and1
+  ret i32 %or
+}
+
+define i32 @negative_lsr_bfi1(i32 %a) {
+; CHECK-LABEL: negative_lsr_bfi1:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    lsr w8, w0, #16
+; CHECK-NEXT:    lsr w9, w8, #4
+; CHECK-NEXT:    bfi w0, w9, #4, #4
+; CHECK-NEXT:    add w0, w0, w8
+; CHECK-NEXT:    ret
+  %and1 = and i32 %a, -241
+  %1 = lshr i32 %a, 16
+  %shl = and i32 %1, 240
+  %or = or i32 %shl, %and1
+  %add = add i32 %or, %1
+  ret i32 %add
+}
+
+define i64 @lsr_bfix(i64 %a) {
+; CHECK-LABEL: lsr_bfix:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    lsr x8, x0, #20
+; CHECK-NEXT:    bfi x0, x8, #4, #4
+; CHECK-NEXT:    ret
+  %and1 = and i64 %a, -241
+  %1 = lshr i64 %a, 16
+  %shl = and i64 %1, 240
+  %or = or i64 %shl, %and1
+  ret i64 %or
+}
+
+define i64 @negative_lsr_bfix0(i64 %a) {
+; CHECK-LABEL: negative_lsr_bfix0:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    and x0, x0, #0xffffffffffffff0f
+; CHECK-NEXT:    ret
+  %and1 = and i64 %a, -241
+  %1 = lshr i64 %a, 60
+  %shl = and i64 %1, 240
+  %or = or i64 %shl, %and1
+  ret i64 %or
+}
+
+define i64 @negative_lsr_bfix1(i64 %a) {
+; CHECK-LABEL: negative_lsr_bfix1:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    lsr x8, x0, #16
+; CHECK-NEXT:    lsr x9, x8, #4
+; CHECK-NEXT:    bfi x0, x9, #4, #4
+; CHECK-NEXT:    add x0, x0, x8
+; CHECK-NEXT:    ret
+  %and1 = and i64 %a, -241
+  %1 = lshr i64 %a, 16
+  %shl = and i64 %1, 240
+  %or = or i64 %shl, %and1
+  %add = add i64 %or, %1
+  ret i64 %add
+}