[LoongArch] Add codegen support for bitreverse

[SixWeining]

llvm/lib/Target/LoongArch/LoongArchISelLowering.cpp

77

How about leave it to legal and use bitrev.4b+srli.w/d. I'm not sure which is fast and better.

llvm/test/CodeGen/LoongArch/bitreverse.ll

2

Nit: had better use --.

[SixWeining]

llvm/lib/Target/LoongArch/LoongArchISelLowering.cpp

77

Sorry, I mean bitrev.w/d+srli.w/d.

[xen0n]

Prefer simple shifts over byteswapping for bitreverse.i16, per @SixWeining's suggestion

[xen0n]

Implement bswap+bitreverse combining.

[xen0n]

Use double dashes for the mtriple option of llc.

[xen0n]

micro-manipulation of comment wording

[xen0n]

whoops forgot this line, change to use the exact same wording as in the .td file

[xen0n]

Oh well. BITREV_I8 and BITREV_4B are actually the same. But it's 2AM now so let me finish tweaking this later.

[xen0n]

remove redundant code

[SixWeining]

LGTM except some nits.

llvm/lib/Target/LoongArch/LoongArchISelLowering.cpp

81

Legal is default. So we can omit it. And then we can omit the braces after if and before else since the body is simple. See the coding standard.

Same as below.

793

Indent.

798

Inline one-time used variable, per @MaskRay's suggestions previously.

[xen0n]

llvm/lib/Target/LoongArch/LoongArchISelLowering.cpp

81

Unfortunately this seems not to be the case. If I remove both Legal setting then the operation gets expanded instead. See lib/CodeGen/TargetLoweringBase.cpp:839, it defaults to Expand.

[xen0n]

address @SixWeining's review comments, also use consistent signature for performBITREV_WCombine

[SixWeining]

LGTM. Thanks!

llvm/lib/Target/LoongArch/LoongArchISelLowering.cpp

81

Oh. My bad. :)

llvm/lib/Target/LoongArch/LoongArchISelLowering.h

enum NodeType : unsigned {
   MOVGR2FR_W_LA64,
   MOVFR2GR_S_LA64,
 
   FTINT,
 
   BSTRINS,
   BSTRPICK,
 
-  // Byte swapping operations
+  // Byte swapping and bit reversing operations
   REVB_2H,
   REVB_2W,
+  BITREV_I8,
+  BITREV_I16,
+  BITREV_I32,
 };
 } // end namespace LoongArchISD
 
 class LoongArchTargetLowering : public TargetLowering {
   const LoongArchSubtarget &Subtarget;
 
 public:
   explicit LoongArchTargetLowering(const TargetMachine &TM,

llvm/lib/Target/LoongArch/LoongArchISelLowering.cpp

LoongArchTargetLowering::LoongArchTargetLowering(const TargetMachine &TM,
   // LA32 does not have REVB.2W and REVB.D due to the 64-bit operands, and
   // the narrower REVB.W does not exist. But LA32 does have REVB.2H, so i16
   // and i32 could still be byte-swapped relatively cheaply.
   setOperationAction(ISD::BSWAP, MVT::i16, Custom);
   if (Subtarget.is64Bit()) {
     setOperationAction(ISD::BSWAP, MVT::i32, Custom);
   }
 
+  setOperationAction(ISD::BITREVERSE, MVT::i8, Custom);
+  setOperationAction(ISD::BITREVERSE, MVT::i16, Custom);
+  if (Subtarget.is64Bit()) {
+    setOperationAction(ISD::BITREVERSE, MVT::i32, Custom);
+    setOperationAction(ISD::BITREVERSE, MVT::i64, Legal);
+  } else {
+    setOperationAction(ISD::BITREVERSE, MVT::i32, Legal);
+  }
+
   static const ISD::CondCode FPCCToExpand[] = {ISD::SETOGT, ISD::SETOGE,
                                                ISD::SETUGT, ISD::SETUGE};
 
   if (Subtarget.hasBasicF()) {
     setCondCodeAction(FPCCToExpand, MVT::f32, Expand);
     setOperationAction(ISD::SELECT_CC, MVT::f32, Expand);
   }
   if (Subtarget.hasBasicD()) {
case 32:
       // Only LA64 will get to here due to the size mismatch between VT and
       // GRLenVT, LA32 lowering is directly defined in LoongArchInstrInfo.
       Tmp = DAG.getNode(LoongArchISD::REVB_2W, DL, GRLenVT, NewSrc);
       break;
     }
     Results.push_back(DAG.getNode(ISD::TRUNCATE, DL, VT, Tmp));
     break;
   }
+  case ISD::BITREVERSE: {
+    SDValue Src = N->getOperand(0);
+    EVT VT = N->getValueType(0);
+    assert((VT == MVT::i8 || VT == MVT::i16 ||
+            (VT == MVT::i32 && Subtarget.is64Bit())) &&
+           "Unexpected custom legalization");
+    MVT GRLenVT = Subtarget.getGRLenVT();
+    SDValue NewSrc = DAG.getNode(ISD::ANY_EXTEND, DL, GRLenVT, Src);
+    SDValue Tmp;
+    switch (VT.getSizeInBits()) {
+    default:
+      llvm_unreachable("Unexpected operand width");
+    case 8:
+      Tmp = DAG.getNode(LoongArchISD::BITREV_I8, DL, GRLenVT, NewSrc);
+      break;
+    case 16:
+      Tmp = DAG.getNode(LoongArchISD::BITREV_I16, DL, GRLenVT, NewSrc);
+      break;
+    case 32:
+      Tmp = DAG.getNode(LoongArchISD::BITREV_I32, DL, GRLenVT, NewSrc);
+      break;
+    }
+    Results.push_back(DAG.getNode(ISD::TRUNCATE, DL, VT, Tmp));
+    break;
+  }
   }
 }
 
 static SDValue performANDCombine(SDNode *N, SelectionDAG &DAG,
                                  TargetLowering::DAGCombinerInfo &DCI,
                                  const LoongArchSubtarget &Subtarget) {
   if (DCI.isBeforeLegalizeOps())
     return SDValue();
if (!SwapAndRetried) {
     goto Retry2;
   }
 
   return SDValue();
 }
 
 SDValue LoongArchTargetLowering::PerformDAGCombine(SDNode *N,
                                                    DAGCombinerInfo &DCI) const {
   SelectionDAG &DAG = DCI.DAG;
   switch (N->getOpcode()) {
   default:
     break;
   case ISD::AND:
     return performANDCombine(N, DAG, DCI, Subtarget);
   case ISD::OR:
     return performORCombine(N, DAG, DCI, Subtarget);
   case ISD::SRL:
     return performSRLCombine(N, DAG, DCI, Subtarget);
   }
   return SDValue();
 }
 
case LoongArchISD::node:                                                     \
     NODE_NAME_CASE(SRL_W)
     NODE_NAME_CASE(BSTRINS)
     NODE_NAME_CASE(BSTRPICK)
     NODE_NAME_CASE(MOVGR2FR_W_LA64)
     NODE_NAME_CASE(MOVFR2GR_S_LA64)
     NODE_NAME_CASE(FTINT)
     NODE_NAME_CASE(REVB_2H)
     NODE_NAME_CASE(REVB_2W)
+    NODE_NAME_CASE(BITREV_I8)
+    NODE_NAME_CASE(BITREV_I16)
+    NODE_NAME_CASE(BITREV_I32)
   }
 #undef NODE_NAME_CASE
   return nullptr;
 }
 
 //===----------------------------------------------------------------------===//
 //                     Calling Convention Implementation
 //===----------------------------------------------------------------------===//

llvm/lib/Target/LoongArch/LoongArchInstrInfo.td

 def loongarch_sra_w : SDNode<"LoongArchISD::SRA_W", SDT_LoongArchIntBinOpW>;
 def loongarch_srl_w : SDNode<"LoongArchISD::SRL_W", SDT_LoongArchIntBinOpW>;
 def loongarch_bstrins
     : SDNode<"LoongArchISD::BSTRINS", SDT_LoongArchBStrIns>;
 def loongarch_bstrpick
     : SDNode<"LoongArchISD::BSTRPICK", SDT_LoongArchBStrPick>;
 def loongarch_revb_2h : SDNode<"LoongArchISD::REVB_2H", SDTUnaryOp>;
 def loongarch_revb_2w : SDNode<"LoongArchISD::REVB_2W", SDTUnaryOp>;
+def loongarch_bitrev_i8 : SDNode<"LoongArchISD::BITREV_I8", SDTUnaryOp>;
+def loongarch_bitrev_i16 : SDNode<"LoongArchISD::BITREV_I16", SDTUnaryOp>;
+def loongarch_bitrev_i32 : SDNode<"LoongArchISD::BITREV_I32", SDTUnaryOp>;
 
 //===----------------------------------------------------------------------===//
 // Operand and SDNode transformation definitions.
 //===----------------------------------------------------------------------===//
 
 class ImmAsmOperand<string prefix, int width, string suffix>
     : AsmOperandClass {
   let Name = prefix # "Imm" # width # suffix;

 
 let Predicates = [IsLA64] in {
 def : Pat<(loongarch_bstrins GPR:$rd, GPR:$rj, uimm6:$msbd, uimm6:$lsbd),
           (BSTRINS_D GPR:$rd, GPR:$rj, uimm6:$msbd, uimm6:$lsbd)>;
 def : Pat<(loongarch_bstrpick GPR:$rj, uimm6:$msbd, uimm6:$lsbd),
           (BSTRPICK_D GPR:$rj, uimm6:$msbd, uimm6:$lsbd)>;
 } // Predicates = [IsLA64]
 
-/// Byte-swapping
+/// Byte-swapping and bit-reversing
 
 def : Pat<(loongarch_revb_2h GPR:$rj), (REVB_2H GPR:$rj)>;
+def : Pat<(loongarch_bitrev_i8 GPR:$rj), (BITREV_4B GPR:$rj)>;
+def : Pat<(loongarch_bitrev_i16 GPR:$rj), (REVB_2H (BITREV_4B GPR:$rj))>;
 
 let Predicates = [IsLA32] in {
 def : Pat<(bswap GPR:$rj), (ROTRI_W (REVB_2H GPR:$rj), 16)>;
+def : Pat<(bitreverse GPR:$rj), (BITREV_W GPR:$rj)>;
 } // Predicates = [IsLA32]
 
 let Predicates = [IsLA64] in {
 def : Pat<(loongarch_revb_2w GPR:$rj), (REVB_2W GPR:$rj)>;
 def : Pat<(bswap GPR:$rj), (REVB_D GPR:$rj)>;
+def : Pat<(loongarch_bitrev_i32 GPR:$rj), (BITREV_W GPR:$rj)>;
+def : Pat<(bitreverse GPR:$rj), (BITREV_D GPR:$rj)>;
 } // Predicates = [IsLA64]
 
 /// Loads
 
 multiclass LdPat<PatFrag LoadOp, LAInst Inst, ValueType vt = GRLenVT> {
   def : Pat<(vt (LoadOp BaseAddr:$rj)), (Inst BaseAddr:$rj, 0)>;
   def : Pat<(vt (LoadOp (AddLike BaseAddr:$rj, simm12:$imm12))),
             (Inst BaseAddr:$rj, simm12:$imm12)>;

llvm/test/CodeGen/LoongArch/bitreverse.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=loongarch32 --verify-machineinstrs < %s \
+; RUN:   | FileCheck %s --check-prefix=LA32
+; RUN: llc -mtriple=loongarch64 --verify-machineinstrs < %s \
+; RUN:   | FileCheck %s --check-prefix=LA64
+
+declare i7 @llvm.bitreverse.i7(i7)
+declare i8 @llvm.bitreverse.i8(i8)
+declare i16 @llvm.bitreverse.i16(i16)
+declare i24 @llvm.bitreverse.i24(i24)
+declare i32 @llvm.bitreverse.i32(i32)
+declare i48 @llvm.bitreverse.i48(i48)
+declare i64 @llvm.bitreverse.i64(i64)
+declare i77 @llvm.bitreverse.i77(i77)
+declare i128 @llvm.bitreverse.i128(i128)
+
+define i8 @test_bitreverse_i8(i8 %a) nounwind {
+; LA32-LABEL: test_bitreverse_i8:
+; LA32:       # %bb.0:
+; LA32-NEXT:    bitrev.4b $a0, $a0
+; LA32-NEXT:    jirl $zero, $ra, 0
+;
+; LA64-LABEL: test_bitreverse_i8:
+; LA64:       # %bb.0:
+; LA64-NEXT:    bitrev.4b $a0, $a0
+; LA64-NEXT:    jirl $zero, $ra, 0
+  %tmp = call i8 @llvm.bitreverse.i8(i8 %a)
+  ret i8 %tmp
+}
+
+define i16 @test_bitreverse_i16(i16 %a) nounwind {
+; LA32-LABEL: test_bitreverse_i16:
+; LA32:       # %bb.0:
+; LA32-NEXT:    bitrev.4b $a0, $a0
+; LA32-NEXT:    revb.2h $a0, $a0
+; LA32-NEXT:    jirl $zero, $ra, 0
+;
+; LA64-LABEL: test_bitreverse_i16:
+; LA64:       # %bb.0:
+; LA64-NEXT:    bitrev.4b $a0, $a0
+; LA64-NEXT:    revb.2h $a0, $a0
+; LA64-NEXT:    jirl $zero, $ra, 0
+  %tmp = call i16 @llvm.bitreverse.i16(i16 %a)
+  ret i16 %tmp
+}
+
+define i32 @test_bitreverse_i32(i32 %a) nounwind {
+; LA32-LABEL: test_bitreverse_i32:
+; LA32:       # %bb.0:
+; LA32-NEXT:    bitrev.w $a0, $a0
+; LA32-NEXT:    jirl $zero, $ra, 0
+;
+; LA64-LABEL: test_bitreverse_i32:
+; LA64:       # %bb.0:
+; LA64-NEXT:    bitrev.w $a0, $a0
+; LA64-NEXT:    jirl $zero, $ra, 0
+  %tmp = call i32 @llvm.bitreverse.i32(i32 %a)
+  ret i32 %tmp
+}
+
+define i64 @test_bitreverse_i64(i64 %a) nounwind {
+; LA32-LABEL: test_bitreverse_i64:
+; LA32:       # %bb.0:
+; LA32-NEXT:    bitrev.w $a2, $a1
+; LA32-NEXT:    bitrev.w $a1, $a0
+; LA32-NEXT:    move $a0, $a2
+; LA32-NEXT:    jirl $zero, $ra, 0
+;
+; LA64-LABEL: test_bitreverse_i64:
+; LA64:       # %bb.0:
+; LA64-NEXT:    bitrev.d $a0, $a0
+; LA64-NEXT:    jirl $zero, $ra, 0
+  %tmp = call i64 @llvm.bitreverse.i64(i64 %a)
+  ret i64 %tmp
+}
+
+;; Bitreverse on non-native integer widths.
+
+define i7 @test_bitreverse_i7(i7 %a) nounwind {
+; LA32-LABEL: test_bitreverse_i7:
+; LA32:       # %bb.0:
+; LA32-NEXT:    bitrev.w $a0, $a0
+; LA32-NEXT:    srli.w $a0, $a0, 25
+; LA32-NEXT:    jirl $zero, $ra, 0
+;
+; LA64-LABEL: test_bitreverse_i7:
+; LA64:       # %bb.0:
+; LA64-NEXT:    bitrev.d $a0, $a0
+; LA64-NEXT:    srli.d $a0, $a0, 57
+; LA64-NEXT:    jirl $zero, $ra, 0
+  %tmp = call i7 @llvm.bitreverse.i7(i7 %a)
+  ret i7 %tmp
+}
+
+define i24 @test_bitreverse_i24(i24 %a) nounwind {
+; LA32-LABEL: test_bitreverse_i24:
+; LA32:       # %bb.0:
+; LA32-NEXT:    bitrev.w $a0, $a0
+; LA32-NEXT:    srli.w $a0, $a0, 8
+; LA32-NEXT:    jirl $zero, $ra, 0
+;
+; LA64-LABEL: test_bitreverse_i24:
+; LA64:       # %bb.0:
+; LA64-NEXT:    bitrev.d $a0, $a0
+; LA64-NEXT:    srli.d $a0, $a0, 40
+; LA64-NEXT:    jirl $zero, $ra, 0
+  %tmp = call i24 @llvm.bitreverse.i24(i24 %a)
+  ret i24 %tmp
+}
+
+define i48 @test_bitreverse_i48(i48 %a) nounwind {
+; LA32-LABEL: test_bitreverse_i48:
+; LA32:       # %bb.0:
+; LA32-NEXT:    bitrev.w $a1, $a1
+; LA32-NEXT:    srli.w $a1, $a1, 16
+; LA32-NEXT:    bitrev.w $a2, $a0
+; LA32-NEXT:    slli.w $a0, $a2, 16
+; LA32-NEXT:    or $a0, $a1, $a0
+; LA32-NEXT:    srli.w $a1, $a2, 16
+; LA32-NEXT:    jirl $zero, $ra, 0
+;
+; LA64-LABEL: test_bitreverse_i48:
+; LA64:       # %bb.0:
+; LA64-NEXT:    bitrev.d $a0, $a0
+; LA64-NEXT:    srli.d $a0, $a0, 16
+; LA64-NEXT:    jirl $zero, $ra, 0
+  %tmp = call i48 @llvm.bitreverse.i48(i48 %a)
+  ret i48 %tmp
+}
+
+define i77 @test_bitreverse_i77(i77 %a) nounwind {
+; LA32-LABEL: test_bitreverse_i77:
+; LA32:       # %bb.0:
+; LA32-NEXT:    ld.w $a2, $a1, 0
+; LA32-NEXT:    bitrev.w $a2, $a2
+; LA32-NEXT:    ld.w $a3, $a1, 4
+; LA32-NEXT:    bitrev.w $a3, $a3
+; LA32-NEXT:    srli.w $a4, $a3, 19
+; LA32-NEXT:    slli.w $a5, $a2, 13
+; LA32-NEXT:    or $a4, $a5, $a4
+; LA32-NEXT:    srli.w $a2, $a2, 19
+; LA32-NEXT:    st.h $a2, $a0, 8
+; LA32-NEXT:    st.w $a4, $a0, 4
+; LA32-NEXT:    slli.w $a2, $a3, 13
+; LA32-NEXT:    ld.w $a1, $a1, 8
+; LA32-NEXT:    bitrev.w $a1, $a1
+; LA32-NEXT:    srli.w $a1, $a1, 19
+; LA32-NEXT:    or $a1, $a1, $a2
+; LA32-NEXT:    st.w $a1, $a0, 0
+; LA32-NEXT:    jirl $zero, $ra, 0
+;
+; LA64-LABEL: test_bitreverse_i77:
+; LA64:       # %bb.0:
+; LA64-NEXT:    bitrev.d $a1, $a1
+; LA64-NEXT:    srli.d $a1, $a1, 51
+; LA64-NEXT:    bitrev.d $a2, $a0
+; LA64-NEXT:    slli.d $a0, $a2, 13
+; LA64-NEXT:    or $a0, $a1, $a0
+; LA64-NEXT:    srli.d $a1, $a2, 51
+; LA64-NEXT:    jirl $zero, $ra, 0
+  %tmp = call i77 @llvm.bitreverse.i77(i77 %a)
+  ret i77 %tmp
+}
+
+define i128 @test_bitreverse_i128(i128 %a) nounwind {
+; LA32-LABEL: test_bitreverse_i128:
+; LA32:       # %bb.0:
+; LA32-NEXT:    ld.w $a2, $a1, 0
+; LA32-NEXT:    bitrev.w $a2, $a2
+; LA32-NEXT:    st.w $a2, $a0, 12
+; LA32-NEXT:    ld.w $a2, $a1, 4
+; LA32-NEXT:    bitrev.w $a2, $a2
+; LA32-NEXT:    st.w $a2, $a0, 8
+; LA32-NEXT:    ld.w $a2, $a1, 8
+; LA32-NEXT:    bitrev.w $a2, $a2
+; LA32-NEXT:    st.w $a2, $a0, 4
+; LA32-NEXT:    ld.w $a1, $a1, 12
+; LA32-NEXT:    bitrev.w $a1, $a1
+; LA32-NEXT:    st.w $a1, $a0, 0
+; LA32-NEXT:    jirl $zero, $ra, 0
+;
+; LA64-LABEL: test_bitreverse_i128:
+; LA64:       # %bb.0:
+; LA64-NEXT:    bitrev.d $a2, $a1
+; LA64-NEXT:    bitrev.d $a1, $a0
+; LA64-NEXT:    move $a0, $a2
+; LA64-NEXT:    jirl $zero, $ra, 0
+  %tmp = call i128 @llvm.bitreverse.i128(i128 %a)
+  ret i128 %tmp
+}