[AArch64] Optimise bitreverse lowering in ISel

[Rin]

Summary

Some Code Generation optimisation for lowering bit reverse in ISel. It uses vrev32 and vrev64 to optimise the lowering of bit reverse in the cases when VT is v4i32 and v2i64.

[SjoerdMeijer]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

6870

Perhaps an assert here for VT == MVT::v4i32 || VT == MVT::v2i64.

6871

How about these SVE checks, do we need tests for that?

6874

Nit: /*OverrideNEON=*/true ?

And we don't need the curly brackets for this if.

6881

then this can be an else.

6883

Wanted add a nit about Bitreverse -> BitReverse, but perhaps we don't need it:

return DAG.getNode(AArch64ISD::NVCAST, DL, VT,
                   DAG.getNode(ISD::BITREVERSE, DL, MVT::v16i8, REVB));

[dmgreen]

Can we add v2i32 and maybe v1i64 handling too?

[Rin]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

6871

I think those are already tested for. That's just old code for the SVE case that I put here to make sure I don't change anything for SVE

[Rin]

Add optimisation for v2i32 and v1i64 bitreverse lowering and respond to review comments

[Rin]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

6874

Should I get rid of the

/*OverrideNEON=*/true

above in LowerCTTZ as well?

6881

changed it to switch statements

[dmgreen]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

6874

I think he meant to add /*OverrideNEON=*/, as it makes the code easier to read.

6875

If we have the unreachable below, we probably don't need the assert as well.

6886

As the code in each of these case blocks are very similar, is it worth having the switch just set some variables (BitReverseType and RevOpcode), and having the actual code shared below the switch?

[Rin]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

6874

Oh, I misunderstood, I'll add it back in

6875

I'll get rid of it

6886

Okay, I'll take care of that then.

[Rin]

Address review comments

[dmgreen]

Thanks. LGTM.

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

6887

You can probably remove some of this extra whitespace.

[DavidSpickett]

Since this change LLVM :: Analysis/CostModel/AArch64/bitreverse.ll is failing.

https://lab.llvm.org/buildbot/#/builders/43/builds/6828/steps/5/logs/FAIL__LLVM__bitreverse_ll

In case it's not just a forgotten test (didn't fail in buildkite which is odd), you can find the config used here https://lab.llvm.org/buildbot/#/builders/43/builds/6828/steps/3/logs/stdio.

[Rin]

In D103105#2793401, @DavidSpickett wrote:

Since this change LLVM :: Analysis/CostModel/AArch64/bitreverse.ll is failing.

https://lab.llvm.org/buildbot/#/builders/43/builds/6828/steps/5/logs/FAIL__LLVM__bitreverse_ll

In case it's not just a forgotten test (didn't fail in buildkite which is odd), you can find the config used here https://lab.llvm.org/buildbot/#/builders/43/builds/6828/steps/3/logs/stdio.

Sorry about that. This new test wasn't caught and I am working on updating it right now to add a fix.

[thakis]

If it takes a while to fix, can we revert this in the meantime to get the bots back to green?

[Rin]

In D103105#2793540, @thakis wrote:

If it takes a while to fix, can we revert this in the meantime to get the bots back to green?

it doesn't take much at all, just retesting now to make sure everything is fine so no need to revert.

[Rin]

In D103105#2793401, @DavidSpickett wrote:

Since this change LLVM :: Analysis/CostModel/AArch64/bitreverse.ll is failing.

https://lab.llvm.org/buildbot/#/builders/43/builds/6828/steps/5/logs/FAIL__LLVM__bitreverse_ll

In case it's not just a forgotten test (didn't fail in buildkite which is odd), you can find the config used here https://lab.llvm.org/buildbot/#/builders/43/builds/6828/steps/3/logs/stdio.

Should be fixed now

[DavidSpickett]

Back to green https://lab.llvm.org/buildbot/#/builders/43/builds/6834, thanks!

[Rin]

In D103105#2793600, @DavidSpickett wrote:

Back to green https://lab.llvm.org/buildbot/#/builders/43/builds/6834, thanks!

No worries. Sorry about the failures earlier :)

llvm/lib/Target/AArch64/AArch64ISelLowering.h

private:
   SDValue LowerINSERT_SUBVECTOR(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerDIV(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerMUL(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerVectorSRA_SRL_SHL(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerShiftParts(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerVSETCC(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerCTPOP(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerCTTZ(SDValue Op, SelectionDAG &DAG) const;
+  SDValue LowerBitreverse(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerFCOPYSIGN(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerFP_EXTEND(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerFP_ROUND(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerVectorFP_TO_INT(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerFP_TO_INT(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerFP_TO_INT_SAT(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerINT_TO_FP(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerVectorINT_TO_FP(SDValue Op, SelectionDAG &DAG) const;

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

if (Subtarget->hasFullFP16()) {
       setOperationPromotedToType(ISD::SINT_TO_FP, MVT::v8i16, MVT::v8i32);
       setOperationPromotedToType(ISD::UINT_TO_FP, MVT::v8i16, MVT::v8i32);
     }
 
     setOperationAction(ISD::CTLZ,       MVT::v1i64, Expand);
     setOperationAction(ISD::CTLZ,       MVT::v2i64, Expand);
     setOperationAction(ISD::BITREVERSE, MVT::v8i8, Legal);
     setOperationAction(ISD::BITREVERSE, MVT::v16i8, Legal);
+    setOperationAction(ISD::BITREVERSE, MVT::v2i32, Custom);
+    setOperationAction(ISD::BITREVERSE, MVT::v4i32, Custom);
+    setOperationAction(ISD::BITREVERSE, MVT::v1i64, Custom);
+    setOperationAction(ISD::BITREVERSE, MVT::v2i64, Custom);
 
     // AArch64 doesn't have MUL.2d:
     setOperationAction(ISD::MUL, MVT::v2i64, Expand);
     // Custom handling for some quad-vector types to detect MULL.
     setOperationAction(ISD::MUL, MVT::v8i16, Custom);
     setOperationAction(ISD::MUL, MVT::v4i32, Custom);
     setOperationAction(ISD::MUL, MVT::v2i64, Custom);
 
case ISD::FMINIMUM:
     return LowerToPredicatedOp(Op, DAG, AArch64ISD::FMIN_PRED);
   case ISD::FMINNUM:
     return LowerToPredicatedOp(Op, DAG, AArch64ISD::FMINNM_PRED);
   case ISD::VSELECT:
     return LowerFixedLengthVectorSelectToSVE(Op, DAG);
   case ISD::ABS:
     return LowerABS(Op, DAG);
   case ISD::BITREVERSE:
-    return LowerToPredicatedOp(Op, DAG, AArch64ISD::BITREVERSE_MERGE_PASSTHRU,
-                               /*OverrideNEON=*/true);
+    return LowerBitreverse(Op, DAG);
   case ISD::BSWAP:
     return LowerToPredicatedOp(Op, DAG, AArch64ISD::BSWAP_MERGE_PASSTHRU);
   case ISD::CTLZ:
     return LowerToPredicatedOp(Op, DAG, AArch64ISD::CTLZ_MERGE_PASSTHRU,
                                /*OverrideNEON=*/true);
   case ISD::CTTZ:
     return LowerCTTZ(Op, DAG);
   }
SDValue AArch64TargetLowering::LowerCTTZ(SDValue Op, SelectionDAG &DAG) const {
   assert(VT.isScalableVector() ||
          useSVEForFixedLengthVectorVT(VT, /*OverrideNEON=*/true));
 
   SDLoc DL(Op);
   SDValue RBIT = DAG.getNode(ISD::BITREVERSE, DL, VT, Op.getOperand(0));
   return DAG.getNode(ISD::CTLZ, DL, VT, RBIT);
 }
 
+SDValue AArch64TargetLowering::LowerBitreverse(SDValue Op,
+                                               SelectionDAG &DAG) const {
+  EVT VT = Op.getValueType();
+
+  if (VT.isScalableVector() || useSVEForFixedLengthVectorVT(VT, true))
+    return LowerToPredicatedOp(Op, DAG, AArch64ISD::BITREVERSE_MERGE_PASSTHRU,
+                               true);
+
+  assert(VT == MVT::v2i32 || VT == MVT::v4i32 || VT == MVT::v1i64 ||
+         VT == MVT::v2i64);
+
+  SDLoc DL(Op);
+  SDValue REVB;
+
+  switch (VT.getSimpleVT().SimpleTy) {
+  default:
+    llvm_unreachable("Invalid type for bitreverse!");
+
+  case MVT::v2i32: {
+    REVB = DAG.getNode(AArch64ISD::REV32, DL, MVT::v8i8, Op.getOperand(0));
+
+    return DAG.getNode(AArch64ISD::NVCAST, DL, VT,
+                       DAG.getNode(ISD::BITREVERSE, DL, MVT::v8i8, REVB));
+  }
+
+  case MVT::v4i32: {
+    REVB = DAG.getNode(AArch64ISD::REV32, DL, MVT::v16i8, Op.getOperand(0));
+
+    return DAG.getNode(AArch64ISD::NVCAST, DL, VT,
+                       DAG.getNode(ISD::BITREVERSE, DL, MVT::v16i8, REVB));
+  }
+
+  case MVT::v1i64: {
+    REVB = DAG.getNode(AArch64ISD::REV64, DL, MVT::v8i8, Op.getOperand(0));
+
+    return DAG.getNode(AArch64ISD::NVCAST, DL, VT,
+                       DAG.getNode(ISD::BITREVERSE, DL, MVT::v8i8, REVB));
+  }
+
+  case MVT::v2i64: {
+    REVB = DAG.getNode(AArch64ISD::REV64, DL, MVT::v16i8, Op.getOperand(0));
+
+    return DAG.getNode(AArch64ISD::NVCAST, DL, VT,
+                       DAG.getNode(ISD::BITREVERSE, DL, MVT::v16i8, REVB));
+  }
+  }
+}
+
 SDValue AArch64TargetLowering::LowerSETCC(SDValue Op, SelectionDAG &DAG) const {
 
   if (Op.getValueType().isVector())
     return LowerVSETCC(Op, DAG);
 
   bool IsStrict = Op->isStrictFPOpcode();
   bool IsSignaling = Op.getOpcode() == ISD::STRICT_FSETCCS;
   unsigned OpNo = IsStrict ? 1 : 0;

llvm/test/CodeGen/AArch64/bitreverse.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=aarch64-eabi %s -o - | FileCheck %s
 
 ; These tests just check that the plumbing is in place for @llvm.bitreverse.
 
 declare <2 x i16> @llvm.bitreverse.v2i16(<2 x i16>) readnone
 
 define <2 x i16> @f(<2 x i16> %a) {
 ; CHECK-LABEL: f:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    // kill: def $d0 killed $d0 def $q0
-; CHECK-NEXT:    fmov w8, s0
-; CHECK-NEXT:    rbit w8, w8
-; CHECK-NEXT:    mov w9, v0.s[1]
-; CHECK-NEXT:    fmov s0, w8
-; CHECK-NEXT:    rbit w8, w9
-; CHECK-NEXT:    mov v0.s[1], w8
+; CHECK-NEXT:    rev32 v0.8b, v0.8b
+; CHECK-NEXT:    rbit v0.8b, v0.8b
 ; CHECK-NEXT:    ushr v0.2s, v0.2s, #16
 ; CHECK-NEXT:    ret
   %b = call <2 x i16> @llvm.bitreverse.v2i16(<2 x i16> %a)
   ret <2 x i16> %b
 }
 
 declare i8 @llvm.bitreverse.i8(i8) readnone
 
; CHECK-NEXT:    ret
   ret <8 x i16> %b
 }
 
 declare <2 x i32> @llvm.bitreverse.v2i32(<2 x i32>) readnone
 
 define <2 x i32> @g_vec_2x32(<2 x i32> %a) {
 ; CHECK-LABEL: g_vec_2x32:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    // kill: def $d0 killed $d0 def $q0
-; CHECK-NEXT:    fmov w8, s0
-; CHECK-NEXT:    rbit w8, w8
-; CHECK-NEXT:    mov w9, v0.s[1]
-; CHECK-NEXT:    fmov s0, w8
-; CHECK-NEXT:    rbit w8, w9
-; CHECK-NEXT:    mov v0.s[1], w8
-; CHECK-NEXT:    // kill: def $d0 killed $d0 killed $q0
+; CHECK-NEXT:    rev32 v0.8b, v0.8b
+; CHECK-NEXT:    rbit v0.8b, v0.8b
 ; CHECK-NEXT:    ret
 
   %b = call <2 x i32> @llvm.bitreverse.v2i32(<2 x i32> %a)
   ret <2 x i32> %b
 }
 
 declare <4 x i32> @llvm.bitreverse.v4i32(<4 x i32>) readnone
 
 define <4 x i32> @g_vec_4x32(<4 x i32> %a) {
 ; CHECK-LABEL: g_vec_4x32:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    fmov w10, s0
-; CHECK-NEXT:    mov w8, v0.s[1]
-; CHECK-NEXT:    rbit w10, w10
-; CHECK-NEXT:    mov w9, v0.s[2]
-; CHECK-NEXT:    mov w11, v0.s[3]
-; CHECK-NEXT:    fmov s0, w10
-; CHECK-NEXT:    rbit w8, w8
-; CHECK-NEXT:    rbit w9, w9
-; CHECK-NEXT:    mov v0.s[1], w8
-; CHECK-NEXT:    mov v0.s[2], w9
-; CHECK-NEXT:    rbit w8, w11
-; CHECK-NEXT:    mov v0.s[3], w8
+; CHECK-NEXT:    rev32 v0.16b, v0.16b
+; CHECK-NEXT:    rbit v0.16b, v0.16b
 ; CHECK-NEXT:    ret
   %b = call <4 x i32> @llvm.bitreverse.v4i32(<4 x i32> %a)
   ret <4 x i32> %b
 }
 
 declare <1 x i64> @llvm.bitreverse.v1i64(<1 x i64>) readnone
 
 define <1 x i64> @g_vec_1x64(<1 x i64> %a) {
 ; CHECK-LABEL: g_vec_1x64:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    // kill: def $d0 killed $d0 def $q0
-; CHECK-NEXT:    fmov x8, d0
-; CHECK-NEXT:    rbit x8, x8
-; CHECK-NEXT:    fmov d0, x8
+; CHECK-NEXT:    rev64 v0.8b, v0.8b
+; CHECK-NEXT:    rbit v0.8b, v0.8b
 ; CHECK-NEXT:    ret
   %b = call <1 x i64> @llvm.bitreverse.v1i64(<1 x i64> %a)
   ret <1 x i64> %b
 }
 
 declare <2 x i64> @llvm.bitreverse.v2i64(<2 x i64>) readnone
 
 define <2 x i64> @g_vec_2x64(<2 x i64> %a) {
 ; CHECK-LABEL: g_vec_2x64:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    fmov x8, d0
-; CHECK-NEXT:    rbit x8, x8
-; CHECK-NEXT:    mov x9, v0.d[1]
-; CHECK-NEXT:    fmov d0, x8
-; CHECK-NEXT:    rbit x8, x9
-; CHECK-NEXT:    mov v0.d[1], x8
+; CHECK-NEXT:    rev64 v0.16b, v0.16b
+; CHECK-NEXT:    rbit v0.16b, v0.16b
 ; CHECK-NEXT:    ret
   %b = call <2 x i64> @llvm.bitreverse.v2i64(<2 x i64> %a)
   ret <2 x i64> %b
 }

llvm/test/CodeGen/AArch64/neon_rbit.ll

; CHECK-NEXT:    ret
   ret <8 x i16> %tmp3
 }
 
 declare <2 x i32> @llvm.aarch64.neon.rbit.v2i32(<2 x i32>) nounwind readnone
 
 define <2 x i32> @rbit_2x32(<2 x i32> %A) {
 ; CHECK-LABEL: rbit_2x32:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    // kill: def $d0 killed $d0 def $q0
-; CHECK-NEXT:    fmov w8, s0
-; CHECK-NEXT:    rbit w8, w8
-; CHECK-NEXT:    mov w9, v0.s[1]
-; CHECK-NEXT:    fmov s0, w8
-; CHECK-NEXT:    rbit w8, w9
-; CHECK-NEXT:    mov v0.s[1], w8
-; CHECK-NEXT:    // kill: def $d0 killed $d0 killed $q0
+; CHECK-NEXT:    rev32 v0.8b, v0.8b
+; CHECK-NEXT:    rbit v0.8b, v0.8b
 ; CHECK-NEXT:    ret
   %tmp3 = call <2 x i32> @llvm.aarch64.neon.rbit.v2i32(<2 x i32> %A)
   ret <2 x i32> %tmp3
 }
 
 declare <4 x i32> @llvm.aarch64.neon.rbit.v4i32(<4 x i32>) nounwind readnone
 
 define <4 x i32> @rbit_4x32(<4 x i32> %A) {
 ; CHECK-LABEL: rbit_4x32:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    fmov w10, s0
-; CHECK-NEXT:    mov w8, v0.s[1]
-; CHECK-NEXT:    rbit w10, w10
-; CHECK-NEXT:    mov w9, v0.s[2]
-; CHECK-NEXT:    mov w11, v0.s[3]
-; CHECK-NEXT:    fmov s0, w10
-; CHECK-NEXT:    rbit w8, w8
-; CHECK-NEXT:    rbit w9, w9
-; CHECK-NEXT:    mov v0.s[1], w8
-; CHECK-NEXT:    mov v0.s[2], w9
-; CHECK-NEXT:    rbit w8, w11
-; CHECK-NEXT:    mov v0.s[3], w8
+; CHECK-NEXT:    rev32 v0.16b, v0.16b
+; CHECK-NEXT:    rbit v0.16b, v0.16b
 ; CHECK-NEXT:    ret
   %tmp3 = call <4 x i32> @llvm.aarch64.neon.rbit.v4i32(<4 x i32> %A)
   ret <4 x i32> %tmp3
 }
 
 declare <1 x i64> @llvm.aarch64.neon.rbit.v1i64(<1 x i64>) readnone
 
 define <1 x i64> @rbit_1x64(<1 x i64> %A) {
 ; CHECK-LABEL: rbit_1x64:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    // kill: def $d0 killed $d0 def $q0
-; CHECK-NEXT:    fmov x8, d0
-; CHECK-NEXT:    rbit x8, x8
-; CHECK-NEXT:    fmov d0, x8
+; CHECK-NEXT:    rev64 v0.8b, v0.8b
+; CHECK-NEXT:    rbit v0.8b, v0.8b
 ; CHECK-NEXT:    ret
   %tmp3 = call <1 x i64> @llvm.aarch64.neon.rbit.v1i64(<1 x i64> %A)
   ret <1 x i64> %tmp3
 }
 
 declare <2 x i64> @llvm.aarch64.neon.rbit.v2i64(<2 x i64>) readnone
 
 define <2 x i64> @rbit_2x64(<2 x i64> %A) {
 ; CHECK-LABEL: rbit_2x64:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    fmov x8, d0
-; CHECK-NEXT:    rbit x8, x8
-; CHECK-NEXT:    mov x9, v0.d[1]
-; CHECK-NEXT:    fmov d0, x8
-; CHECK-NEXT:    rbit x8, x9
-; CHECK-NEXT:    mov v0.d[1], x8
+; CHECK-NEXT:    rev64 v0.16b, v0.16b
+; CHECK-NEXT:    rbit v0.16b, v0.16b
 ; CHECK-NEXT:    ret
   %tmp3 = call <2 x i64> @llvm.aarch64.neon.rbit.v2i64(<2 x i64> %A)
   ret <2 x i64> %tmp3
 }