[MIPS GlobalISel] Select bswap

[Petar.Avramovic]

Summary

G_BSWAP is generated from llvm.bswap.<type> intrinsics, clang genrates
these intrinsics from builtin_bswap32 and builtin_bswap64.
Add lower and narrowscalar for G_BSWAP.
Lower G_BSWAP on MIPS32, select G_BSWAP on MIPS32 revision 2 and later.

[atanasyan]

LGTM

llvm/include/llvm/CodeGen/GlobalISel/LegalizerHelper.h

public:
   LegalizeResult lowerFMinNumMaxNum(MachineInstr &MI);
   LegalizeResult lowerFMad(MachineInstr &MI);
   LegalizeResult lowerUnmergeValues(MachineInstr &MI);
   LegalizeResult lowerShuffleVector(MachineInstr &MI);
   LegalizeResult lowerDynStackAlloc(MachineInstr &MI);
   LegalizeResult lowerExtract(MachineInstr &MI);
   LegalizeResult lowerInsert(MachineInstr &MI);
   LegalizeResult lowerSADDO_SSUBO(MachineInstr &MI);
+  LegalizeResult lowerBswap(MachineInstr &MI);
 
 private:
   MachineRegisterInfo &MRI;
   const LegalizerInfo &LI;
   /// To keep track of changes made by the LegalizerHelper.
   GISelChangeObserver &Observer;
 };
 

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

case TargetOpcode::G_SEXT_INREG: {
     }
 
     // Gather the destination registers into the final destination.
     Register DstReg = MI.getOperand(0).getReg();
     MIRBuilder.buildMerge(DstReg, DstRegs);
     MI.eraseFromParent();
     return Legalized;
   }
+  case TargetOpcode::G_BSWAP: {
+    if (SizeOp0 % NarrowSize != 0)
+      return UnableToLegalize;
+
+    Observer.changingInstr(MI);
+    SmallVector<Register, 2> SrcRegs, DstRegs;
+    unsigned NumParts = SizeOp0 / NarrowSize;
+    extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, SrcRegs);
+
+    for (unsigned i = 0; i < NumParts; ++i) {
+      auto DstPart = MIRBuilder.buildInstr(MI.getOpcode(), {NarrowTy},
+                                           {SrcRegs[NumParts - 1 - i]});
+      DstRegs.push_back(DstPart.getReg(0));
+    }
+
+    MIRBuilder.buildMerge(MI.getOperand(0).getReg(), DstRegs);
+
+    Observer.changedInstr(MI);
+    MI.eraseFromParent();
+    return Legalized;
+  }
   }
 }
 
 void LegalizerHelper::widenScalarSrc(MachineInstr &MI, LLT WideTy,
                                      unsigned OpIdx, unsigned ExtOpcode) {
   MachineOperand &MO = MI.getOperand(OpIdx);
   auto ExtB = MIRBuilder.buildInstr(ExtOpcode, {WideTy}, {MO.getReg()});
   MO.setReg(ExtB->getOperand(0).getReg());
LegalizerHelper::lower(MachineInstr &MI, unsigned TypeIdx, LLT Ty) {
   case G_SHUFFLE_VECTOR:
     return lowerShuffleVector(MI);
   case G_DYN_STACKALLOC:
     return lowerDynStackAlloc(MI);
   case G_EXTRACT:
     return lowerExtract(MI);
   case G_INSERT:
     return lowerInsert(MI);
+  case G_BSWAP:
+    return lowerBswap(MI);
   }
 }
 
 LegalizerHelper::LegalizeResult LegalizerHelper::fewerElementsVectorImplicitDef(
     MachineInstr &MI, unsigned TypeIdx, LLT NarrowTy) {
   SmallVector<Register, 2> DstRegs;
 
   unsigned NarrowSize = NarrowTy.getSizeInBits();
auto ResultLowerThanLHS =
       MIRBuilder.buildICmp(CmpInst::ICMP_SLT, BoolTy, Dst0, LHS);
   auto ConditionRHS = MIRBuilder.buildICmp(
       IsAdd ? CmpInst::ICMP_SLT : CmpInst::ICMP_SGT, BoolTy, RHS, Zero);
 
   MIRBuilder.buildXor(Dst1, ConditionRHS, ResultLowerThanLHS);
   MI.eraseFromParent();
   return Legalized;
 }
+
+LegalizerHelper::LegalizeResult
+LegalizerHelper::lowerBswap(MachineInstr &MI) {
+  Register Dst = MI.getOperand(0).getReg();
+  Register Src = MI.getOperand(1).getReg();
+  const LLT Ty = MRI.getType(Src);
+  unsigned SizeInBytes = Ty.getSizeInBytes();
+  unsigned BaseShiftAmt = (SizeInBytes - 1) * 8;
+
+  // Swap most and least significant byte, set remaining bytes in Res to zero.
+  auto ShiftAmt = MIRBuilder.buildConstant(Ty, BaseShiftAmt);
+  auto LSByteShiftedLeft = MIRBuilder.buildShl(Ty, Src, ShiftAmt);
+  auto MSByteShiftedRight = MIRBuilder.buildLShr(Ty, Src, ShiftAmt);
+  auto Res = MIRBuilder.buildOr(Ty, MSByteShiftedRight, LSByteShiftedLeft);
+
+  // Set i-th high/low byte in Res to i-th low/high byte from Src.
+  for (unsigned i = 1; i < SizeInBytes / 2; ++i) {
+    // AND with Mask leaves byte i unchanged and sets remaining bytes to 0.
+    APInt APMask(SizeInBytes * 8, 0xFF << (i * 8));
+    auto Mask = MIRBuilder.buildConstant(Ty, APMask);
+    auto ShiftAmt = MIRBuilder.buildConstant(Ty, BaseShiftAmt - 16 * i);
+    // Low byte shifted left to place of high byte: (Src & Mask) << ShiftAmt.
+    auto LoByte = MIRBuilder.buildAnd(Ty, Src, Mask);
+    auto LoShiftedLeft = MIRBuilder.buildShl(Ty, LoByte, ShiftAmt);
+    Res = MIRBuilder.buildOr(Ty, Res, LoShiftedLeft);
+    // High byte shifted right to place of low byte: (Src >> ShiftAmt) & Mask.
+    auto SrcShiftedRight = MIRBuilder.buildLShr(Ty, Src, ShiftAmt);
+    auto HiShiftedRight = MIRBuilder.buildAnd(Ty, SrcShiftedRight, Mask);
+    Res = MIRBuilder.buildOr(Ty, Res, HiShiftedRight);
+  }
+  Res.getInstr()->getOperand(0).setReg(Dst);
+
+  MI.eraseFromParent();
+  return Legalized;
+}

llvm/lib/Target/Mips/MipsLegalizerInfo.cpp

getActionDefinitionsBuilder({G_GLOBAL_VALUE, G_JUMP_TABLE})
       .legalFor({p0});
 
   getActionDefinitionsBuilder(G_DYN_STACKALLOC)
       .lowerFor({{p0, s32}});
 
   getActionDefinitionsBuilder(G_VASTART)
      .legalFor({p0});
 
+  getActionDefinitionsBuilder(G_BSWAP)
+      .legalIf([=, &ST](const LegalityQuery &Query) {
+        if (ST.hasMips32r2() && CheckTyN(0, Query, {s32}))
+          return true;
+        return false;
+      })
+      .lowerIf([=, &ST](const LegalityQuery &Query) {
+        if (!ST.hasMips32r2() && CheckTyN(0, Query, {s32}))
+          return true;
+        return false;
+      })
+      .maxScalar(0, s32);
+
   // FP instructions
   getActionDefinitionsBuilder(G_FCONSTANT)
       .legalFor({s32, s64});
 
   getActionDefinitionsBuilder({G_FADD, G_FSUB, G_FMUL, G_FDIV, G_FABS, G_FSQRT})
       .legalIf([=, &ST](const LegalityQuery &Query) {
         if (CheckTyN(0, Query, {s32, s64}))
           return true;

llvm/lib/Target/Mips/MipsRegisterBankInfo.cpp

MipsRegisterBankInfo::getInstrMapping(const MachineInstr &MI) const {
   case G_AND:
   case G_OR:
   case G_XOR:
   case G_SHL:
   case G_ASHR:
   case G_LSHR:
   case G_BRINDIRECT:
   case G_VASTART:
+  case G_BSWAP:
     OperandsMapping = &Mips::ValueMappings[Mips::GPRIdx];
     break;
   case G_ADD:
   case G_SUB:
   case G_MUL:
   case G_SDIV:
   case G_SREM:
   case G_UDIV:

llvm/test/CodeGen/Mips/GlobalISel/instruction-select/bswap.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=mipsel-linux-gnu -run-pass=instruction-select -mattr=+mips32r2 -verify-machineinstrs %s -o - | FileCheck %s -check-prefixes=MIPS32R2
+--- |
+
+  define void @bswap_i32() { entry: ret void }
+
+...
+---
+name:            bswap_i32
+alignment:       4
+legalized:       true
+regBankSelected: true
+tracksRegLiveness: true
+body:             |
+  bb.1.entry:
+    liveins: $a0
+
+    ; MIPS32R2-LABEL: name: bswap_i32
+    ; MIPS32R2: liveins: $a0
+    ; MIPS32R2: [[COPY:%[0-9]+]]:gpr32 = COPY $a0
+    ; MIPS32R2: [[WSBH:%[0-9]+]]:gpr32 = WSBH [[COPY]]
+    ; MIPS32R2: [[ROTR:%[0-9]+]]:gpr32 = ROTR [[WSBH]], 16
+    ; MIPS32R2: $v0 = COPY [[ROTR]]
+    ; MIPS32R2: RetRA implicit $v0
+    %0:gprb(s32) = COPY $a0
+    %1:gprb(s32) = G_BSWAP %0
+    $v0 = COPY %1(s32)
+    RetRA implicit $v0
+
+...

llvm/test/CodeGen/Mips/GlobalISel/legalizer/bswap.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=mipsel-linux-gnu -run-pass=legalizer -verify-machineinstrs %s -o - | FileCheck %s -check-prefixes=MIPS32
+# RUN: llc -mtriple=mipsel-linux-gnu -run-pass=legalizer -mattr=+mips32r2 -verify-machineinstrs %s -o - | FileCheck %s -check-prefixes=MIPS32R2
+--- |
+
+  define void @bswap_i32() { entry: ret void }
+  define void @bswap_i64() { entry: ret void }
+
+...
+---
+name:            bswap_i32
+alignment:       4
+tracksRegLiveness: true
+body:             |
+  bb.1.entry:
+    liveins: $a0
+
+    ; MIPS32-LABEL: name: bswap_i32
+    ; MIPS32: liveins: $a0
+    ; MIPS32: [[COPY:%[0-9]+]]:_(s32) = COPY $a0
+    ; MIPS32: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 24
+    ; MIPS32: [[SHL:%[0-9]+]]:_(s32) = G_SHL [[COPY]], [[C]](s32)
+    ; MIPS32: [[LSHR:%[0-9]+]]:_(s32) = G_LSHR [[COPY]], [[C]](s32)
+    ; MIPS32: [[OR:%[0-9]+]]:_(s32) = G_OR [[LSHR]], [[SHL]]
+    ; MIPS32: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 65280
+    ; MIPS32: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 8
+    ; MIPS32: [[AND:%[0-9]+]]:_(s32) = G_AND [[COPY]], [[C1]]
+    ; MIPS32: [[SHL1:%[0-9]+]]:_(s32) = G_SHL [[AND]], [[C2]](s32)
+    ; MIPS32: [[OR1:%[0-9]+]]:_(s32) = G_OR [[OR]], [[SHL1]]
+    ; MIPS32: [[LSHR1:%[0-9]+]]:_(s32) = G_LSHR [[COPY]], [[C2]](s32)
+    ; MIPS32: [[AND1:%[0-9]+]]:_(s32) = G_AND [[LSHR1]], [[C1]]
+    ; MIPS32: [[OR2:%[0-9]+]]:_(s32) = G_OR [[OR1]], [[AND1]]
+    ; MIPS32: $v0 = COPY [[OR2]](s32)
+    ; MIPS32: RetRA implicit $v0
+    ; MIPS32R2-LABEL: name: bswap_i32
+    ; MIPS32R2: liveins: $a0
+    ; MIPS32R2: [[COPY:%[0-9]+]]:_(s32) = COPY $a0
+    ; MIPS32R2: [[BSWAP:%[0-9]+]]:_(s32) = G_BSWAP [[COPY]]
+    ; MIPS32R2: $v0 = COPY [[BSWAP]](s32)
+    ; MIPS32R2: RetRA implicit $v0
+    %0:_(s32) = COPY $a0
+    %1:_(s32) = G_BSWAP %0
+    $v0 = COPY %1(s32)
+    RetRA implicit $v0
+
+...
+---
+name:            bswap_i64
+alignment:       4
+tracksRegLiveness: true
+body:             |
+  bb.1.entry:
+    liveins: $a0, $a1
+
+    ; MIPS32-LABEL: name: bswap_i64
+    ; MIPS32: liveins: $a0, $a1
+    ; MIPS32: [[COPY:%[0-9]+]]:_(s32) = COPY $a0
+    ; MIPS32: [[COPY1:%[0-9]+]]:_(s32) = COPY $a1
+    ; MIPS32: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 24
+    ; MIPS32: [[SHL:%[0-9]+]]:_(s32) = G_SHL [[COPY1]], [[C]](s32)
+    ; MIPS32: [[LSHR:%[0-9]+]]:_(s32) = G_LSHR [[COPY1]], [[C]](s32)
+    ; MIPS32: [[OR:%[0-9]+]]:_(s32) = G_OR [[LSHR]], [[SHL]]
+    ; MIPS32: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 65280
+    ; MIPS32: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 8
+    ; MIPS32: [[AND:%[0-9]+]]:_(s32) = G_AND [[COPY1]], [[C1]]
+    ; MIPS32: [[SHL1:%[0-9]+]]:_(s32) = G_SHL [[AND]], [[C2]](s32)
+    ; MIPS32: [[OR1:%[0-9]+]]:_(s32) = G_OR [[OR]], [[SHL1]]
+    ; MIPS32: [[LSHR1:%[0-9]+]]:_(s32) = G_LSHR [[COPY1]], [[C2]](s32)
+    ; MIPS32: [[AND1:%[0-9]+]]:_(s32) = G_AND [[LSHR1]], [[C1]]
+    ; MIPS32: [[OR2:%[0-9]+]]:_(s32) = G_OR [[OR1]], [[AND1]]
+    ; MIPS32: [[SHL2:%[0-9]+]]:_(s32) = G_SHL [[COPY]], [[C]](s32)
+    ; MIPS32: [[LSHR2:%[0-9]+]]:_(s32) = G_LSHR [[COPY]], [[C]](s32)
+    ; MIPS32: [[OR3:%[0-9]+]]:_(s32) = G_OR [[LSHR2]], [[SHL2]]
+    ; MIPS32: [[AND2:%[0-9]+]]:_(s32) = G_AND [[COPY]], [[C1]]
+    ; MIPS32: [[SHL3:%[0-9]+]]:_(s32) = G_SHL [[AND2]], [[C2]](s32)
+    ; MIPS32: [[OR4:%[0-9]+]]:_(s32) = G_OR [[OR3]], [[SHL3]]
+    ; MIPS32: [[LSHR3:%[0-9]+]]:_(s32) = G_LSHR [[COPY]], [[C2]](s32)
+    ; MIPS32: [[AND3:%[0-9]+]]:_(s32) = G_AND [[LSHR3]], [[C1]]
+    ; MIPS32: [[OR5:%[0-9]+]]:_(s32) = G_OR [[OR4]], [[AND3]]
+    ; MIPS32: $v0 = COPY [[OR2]](s32)
+    ; MIPS32: $v1 = COPY [[OR5]](s32)
+    ; MIPS32: RetRA implicit $v0, implicit $v1
+    ; MIPS32R2-LABEL: name: bswap_i64
+    ; MIPS32R2: liveins: $a0, $a1
+    ; MIPS32R2: [[COPY:%[0-9]+]]:_(s32) = COPY $a0
+    ; MIPS32R2: [[COPY1:%[0-9]+]]:_(s32) = COPY $a1
+    ; MIPS32R2: [[BSWAP:%[0-9]+]]:_(s32) = G_BSWAP [[COPY1]]
+    ; MIPS32R2: [[BSWAP1:%[0-9]+]]:_(s32) = G_BSWAP [[COPY]]
+    ; MIPS32R2: $v0 = COPY [[BSWAP]](s32)
+    ; MIPS32R2: $v1 = COPY [[BSWAP1]](s32)
+    ; MIPS32R2: RetRA implicit $v0, implicit $v1
+    %1:_(s32) = COPY $a0
+    %2:_(s32) = COPY $a1
+    %0:_(s64) = G_MERGE_VALUES %1(s32), %2(s32)
+    %3:_(s64) = G_BSWAP %0
+    %4:_(s32), %5:_(s32) = G_UNMERGE_VALUES %3(s64)
+    $v0 = COPY %4(s32)
+    $v1 = COPY %5(s32)
+    RetRA implicit $v0, implicit $v1
+
+...

llvm/test/CodeGen/Mips/GlobalISel/llvm-ir/bswap.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -O0 -mtriple=mipsel-linux-gnu -global-isel -verify-machineinstrs %s -o -| FileCheck %s -check-prefixes=MIPS32
+; RUN: llc -O0 -mtriple=mipsel-linux-gnu -global-isel -mattr=+mips32r2 -verify-machineinstrs %s -o -| FileCheck %s -check-prefixes=MIPS32R2
+
+declare i32 @llvm.bswap.i32(i32)
+define i32 @bswap_i32(i32 %x) {
+; MIPS32-LABEL: bswap_i32:
+; MIPS32:       # %bb.0: # %entry
+; MIPS32-NEXT:    sll $1, $4, 24
+; MIPS32-NEXT:    srl $2, $4, 24
+; MIPS32-NEXT:    or $1, $2, $1
+; MIPS32-NEXT:    andi $2, $4, 65280
+; MIPS32-NEXT:    sll $2, $2, 8
+; MIPS32-NEXT:    or $1, $1, $2
+; MIPS32-NEXT:    srl $2, $4, 8
+; MIPS32-NEXT:    andi $2, $2, 65280
+; MIPS32-NEXT:    or $2, $1, $2
+; MIPS32-NEXT:    jr $ra
+; MIPS32-NEXT:    nop
+;
+; MIPS32R2-LABEL: bswap_i32:
+; MIPS32R2:       # %bb.0: # %entry
+; MIPS32R2-NEXT:    wsbh $1, $4
+; MIPS32R2-NEXT:    rotr $2, $1, 16
+; MIPS32R2-NEXT:    jr $ra
+; MIPS32R2-NEXT:    nop
+entry:
+  %0 = tail call i32 @llvm.bswap.i32(i32 %x)
+  ret i32 %0
+}
+
+declare i64 @llvm.bswap.i64(i64)
+define i64 @bswap_i64(i64 %x) {
+; MIPS32-LABEL: bswap_i64:
+; MIPS32:       # %bb.0: # %entry
+; MIPS32-NEXT:    sll $1, $5, 24
+; MIPS32-NEXT:    srl $2, $5, 24
+; MIPS32-NEXT:    or $1, $2, $1
+; MIPS32-NEXT:    andi $2, $5, 65280
+; MIPS32-NEXT:    sll $2, $2, 8
+; MIPS32-NEXT:    or $1, $1, $2
+; MIPS32-NEXT:    srl $2, $5, 8
+; MIPS32-NEXT:    andi $2, $2, 65280
+; MIPS32-NEXT:    or $2, $1, $2
+; MIPS32-NEXT:    sll $1, $4, 24
+; MIPS32-NEXT:    srl $3, $4, 24
+; MIPS32-NEXT:    or $1, $3, $1
+; MIPS32-NEXT:    andi $3, $4, 65280
+; MIPS32-NEXT:    sll $3, $3, 8
+; MIPS32-NEXT:    or $1, $1, $3
+; MIPS32-NEXT:    srl $3, $4, 8
+; MIPS32-NEXT:    andi $3, $3, 65280
+; MIPS32-NEXT:    or $3, $1, $3
+; MIPS32-NEXT:    jr $ra
+; MIPS32-NEXT:    nop
+;
+; MIPS32R2-LABEL: bswap_i64:
+; MIPS32R2:       # %bb.0: # %entry
+; MIPS32R2-NEXT:    wsbh $1, $5
+; MIPS32R2-NEXT:    rotr $2, $1, 16
+; MIPS32R2-NEXT:    wsbh $1, $4
+; MIPS32R2-NEXT:    rotr $3, $1, 16
+; MIPS32R2-NEXT:    jr $ra
+; MIPS32R2-NEXT:    nop
+entry:
+  %0 = tail call i64 @llvm.bswap.i64(i64 %x)
+  ret i64 %0
+}

llvm/test/CodeGen/Mips/GlobalISel/regbankselect/bswap.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=mipsel-linux-gnu -run-pass=regbankselect -mattr=+mips32r2 -verify-machineinstrs %s -o - | FileCheck %s -check-prefixes=MIPS32R2
+--- |
+
+  define void @bswap_i32() { entry: ret void }
+
+...
+---
+name:            bswap_i32
+alignment:       4
+legalized:       true
+tracksRegLiveness: true
+body:             |
+  bb.1.entry:
+    liveins: $a0
+
+    ; MIPS32R2-LABEL: name: bswap_i32
+    ; MIPS32R2: liveins: $a0
+    ; MIPS32R2: [[COPY:%[0-9]+]]:gprb(s32) = COPY $a0
+    ; MIPS32R2: [[BSWAP:%[0-9]+]]:gprb(s32) = G_BSWAP [[COPY]]
+    ; MIPS32R2: $v0 = COPY [[BSWAP]](s32)
+    ; MIPS32R2: RetRA implicit $v0
+    %0:_(s32) = COPY $a0
+    %1:_(s32) = G_BSWAP %0
+    $v0 = COPY %1(s32)
+    RetRA implicit $v0
+
+...