[MIPS GlobalISel] Select bitreverse

[Petar.Avramovic]

Summary

G_BITREVERSE is generated from llvm.bitreverse.<type> intrinsics, clang
genrates these intrinsics from builtin_bitreverse32 and
builtin_bitreverse64.
Add lower and narrowscalar for G_BITREVERSE.
Lower G_BITREVERSE on MIPS32.

[Petar.Avramovic]

Forgot to run regression tests for amd.

[atanasyan]

When I apply this one and D71362 to the master branch I get a couple of failed tests:

LLVM :: CodeGen/Mips/GlobalISel/legalizer/bitreverse.mir
LLVM :: CodeGen/Mips/GlobalISel/llvm-ir/bitreverse.ll

Should I apply any other patches before?

[Petar.Avramovic]

This patch needs only bswap, I just checked and it worked fine for me, what was the error?

[atanasyan]

I'll check again on my side tomorrow.

******************** TEST 'LLVM :: CodeGen/Mips/GlobalISel/llvm-ir/bitreverse.ll' FAILED ********************
Script:
--
: 'RUN: at line 2';   /home/simon/work/llvm/bld/bin/llc -O0 -mtriple=mipsel-linux-gnu -global-isel -verify-machineinstrs /home/simon/work/llvm/git/llvm/test/CodeGen/Mips/GlobalISel/llvm-ir/bitreverse.ll -o -| /home/simon/work/llvm/bld/bin/FileCheck /home/simon/work/llvm/git/llvm/test/CodeGen/Mips/GlobalISel/llvm-ir/bitreverse.ll -check-prefixes=MIPS32                                                                                                  
: 'RUN: at line 3';   /home/simon/work/llvm/bld/bin/llc -O0 -mtriple=mipsel-linux-gnu -global-isel -mattr=+mips32r2 -verify-machineinstrs /home/simon/work/llvm/git/llvm/test/CodeGen/Mips/GlobalISel/llvm-ir/bitreverse.ll -o -|
/home/simon/work/llvm/bld/bin/FileCheck /home/simon/work/llvm/git/llvm/test/CodeGen/Mips/GlobalISel/llvm-ir/bitreverse.ll -check-prefixes=MIPS32R2                                                                               
--
Exit Code: 1

Command Output (stderr):
--
/home/simon/work/llvm/git/llvm/test/CodeGen/Mips/GlobalISel/llvm-ir/bitreverse.ll:20:16: error: MIPS32-NEXT: expected string not found in input                                                                                  
; MIPS32-NEXT: sll $3, $1, 4
               ^
<stdin>:34:2: note: scanning from here
 and $3, $1, $2
 ^
<stdin>:36:2: note: possible intended match here
 sll $1, $1, 4
 ^
/home/simon/work/llvm/git/llvm/test/CodeGen/Mips/GlobalISel/llvm-ir/bitreverse.ll:89:16: error: MIPS32-NEXT: expected string not found in input                                                                                  
; MIPS32-NEXT: sll $3, $1, 4
               ^
<stdin>:89:2: note: scanning from here
 and $3, $1, $2
 ^
<stdin>:91:2: note: possible intended match here
 sll $1, $1, 4
 ^

[atanasyan]

LGTM

[gribozavr2]

This change broke buildbots: http://lab.llvm.org:8011/builders/clang-x86_64-debian-fast/builds/21066.

I reverted it in 32cc14100e802fddd9f88e7a862250ce3108a583. Please always run ninja check-all before pushing.

[Petar.Avramovic]

Buildbot failures depend on compiler used to build clang.
Problem was in order which new MachineInstructions get inserted into MachineFunction.
Generated assembler does the same thing, but regression tests require consistent behavior regardless of compiler used.
In:

return B.buildOr(Dst, B.buildLShr(Ty, B.buildAnd(Ty, Src, MaskLoNTo0), C_N),
                 B.buildAnd(Ty, B.buildShl(Ty, Src, C_N), MaskLoNTo0));

it is important which method was executed first since they insert MachineInstructions into MachineFunction. Order of execution:
gcc

B.buildAnd(Ty, B.buildShl(Ty, Src, C_N), MaskLoNTo0)
B.buildLShr(Ty, B.buildAnd(Ty, Src, MaskLoNTo0), C_N)

clang

B.buildLShr(Ty, B.buildAnd(Ty, Src, MaskLoNTo0), C_N)
B.buildAnd(Ty, B.buildShl(Ty, Src, C_N), MaskLoNTo0)

recommit notes:
Introduce temporary variables in order to make sure instructions get inserted into MachineFunction in same order regardless of compiler used to build llvm.

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

public:
   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);
+  LegalizeResult lowerBitreverse(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: {
+  case TargetOpcode::G_BSWAP:
+  case TargetOpcode::G_BITREVERSE: {
     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);
 
LegalizerHelper::lower(MachineInstr &MI, unsigned TypeIdx, LLT Ty) {
   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);
+  case G_BITREVERSE:
+    return lowerBitreverse(MI);
   }
 }
 
 LegalizerHelper::LegalizeResult LegalizerHelper::fewerElementsVectorImplicitDef(
     MachineInstr &MI, unsigned TypeIdx, LLT NarrowTy) {
   SmallVector<Register, 2> DstRegs;
 
   unsigned NarrowSize = NarrowTy.getSizeInBits();
for (unsigned i = 1; i < SizeInBytes / 2; ++i) {
     auto HiShiftedRight = MIRBuilder.buildAnd(Ty, SrcShiftedRight, Mask);
     Res = MIRBuilder.buildOr(Ty, Res, HiShiftedRight);
   }
   Res.getInstr()->getOperand(0).setReg(Dst);
 
   MI.eraseFromParent();
   return Legalized;
 }
+
+//{ (Src & Mask) >> N } | { (Src << N) & Mask }
+static MachineInstrBuilder SwapN(unsigned N, DstOp Dst, MachineIRBuilder &B,
+                                 MachineInstrBuilder Src, APInt Mask) {
+  const LLT Ty = Dst.getLLTTy(*B.getMRI());
+  MachineInstrBuilder C_N = B.buildConstant(Ty, N);
+  MachineInstrBuilder MaskLoNTo0 = B.buildConstant(Ty, Mask);
+  return B.buildOr(Dst, B.buildLShr(Ty, B.buildAnd(Ty, Src, MaskLoNTo0), C_N),
+                   B.buildAnd(Ty, B.buildShl(Ty, Src, C_N), MaskLoNTo0));
+}
+
+LegalizerHelper::LegalizeResult
+LegalizerHelper::lowerBitreverse(MachineInstr &MI) {
+  Register Dst = MI.getOperand(0).getReg();
+  Register Src = MI.getOperand(1).getReg();
+  const LLT Ty = MRI.getType(Src);
+  unsigned Size = Ty.getSizeInBits();
+
+  MachineInstrBuilder BSWAP =
+      MIRBuilder.buildInstr(TargetOpcode::G_BSWAP, {Ty}, {Src});
+
+  // swap high and low 4 bits in 8 bit blocks 7654|3210 -> 3210|7654
+  //    [(val & 0xF0F0F0F0) >> 4] | [(val & 0x0F0F0F0F) << 4]
+  // -> [(val & 0xF0F0F0F0) >> 4] | [(val << 4) & 0xF0F0F0F0]
+  MachineInstrBuilder Swap4 =
+      SwapN(4, Ty, MIRBuilder, BSWAP, APInt::getSplat(Size, APInt(8, 0xF0)));
+
+  // swap high and low 2 bits in 4 bit blocks 32|10 76|54 -> 10|32 54|76
+  //    [(val & 0xCCCCCCCC) >> 2] & [(val & 0x33333333) << 2]
+  // -> [(val & 0xCCCCCCCC) >> 2] & [(val << 2) & 0xCCCCCCCC]
+  MachineInstrBuilder Swap2 =
+      SwapN(2, Ty, MIRBuilder, Swap4, APInt::getSplat(Size, APInt(8, 0xCC)));
+
+  // swap high and low 1 bit in 2 bit blocks 1|0 3|2 5|4 7|6 -> 0|1 2|3 4|5 6|7
+  //    [(val & 0xAAAAAAAA) >> 1] & [(val & 0x55555555) << 1]
+  // -> [(val & 0xAAAAAAAA) >> 1] & [(val << 1) & 0xAAAAAAAA]
+  SwapN(1, Dst, MIRBuilder, Swap2, APInt::getSplat(Size, APInt(8, 0xAA)));
+
+  MI.eraseFromParent();
+  return Legalized;
+}

llvm/lib/Target/Mips/MipsLegalizerInfo.cpp

getActionDefinitionsBuilder(G_BSWAP)
       })
       .lowerIf([=, &ST](const LegalityQuery &Query) {
         if (!ST.hasMips32r2() && CheckTyN(0, Query, {s32}))
           return true;
         return false;
       })
       .maxScalar(0, s32);
 
+  getActionDefinitionsBuilder(G_BITREVERSE)
+      .lowerFor({s32})
+      .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/test/CodeGen/AMDGPU/GlobalISel/legalize-bitreverse.mir

 # NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
-# RUN: llc -mtriple=amdgcn-mesa-mesa3d -mcpu=fiji -O0 -run-pass=legalizer -global-isel-abort=0 %s -o - | FileCheck %s
+# RUN: llc -mtriple=amdgcn-mesa-mesa3d -mcpu=fiji -O0 -run-pass=legalizer %s -o - | FileCheck %s
 
 ---
 name: bitreverse_s8
 
 body: |
   bb.0:
     liveins: $vgpr0
     ; CHECK-LABEL: name: bitreverse_s8

 ---
 name: bitreverse_s64
 
 body: |
   bb.0:
     liveins: $vgpr0_vgpr1
     ; CHECK-LABEL: name: bitreverse_s64
     ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $vgpr0_vgpr1
-    ; CHECK: [[BITREVERSE:%[0-9]+]]:_(s64) = G_BITREVERSE [[COPY]]
-    ; CHECK: $vgpr0_vgpr1 = COPY [[BITREVERSE]](s64)
+    ; CHECK: [[UV:%[0-9]+]]:_(s32), [[UV1:%[0-9]+]]:_(s32) = G_UNMERGE_VALUES [[COPY]](s64)
+    ; CHECK: [[BITREVERSE:%[0-9]+]]:_(s32) = G_BITREVERSE [[UV1]]
+    ; CHECK: [[BITREVERSE1:%[0-9]+]]:_(s32) = G_BITREVERSE [[UV]]
+    ; CHECK: [[MV:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[BITREVERSE]](s32), [[BITREVERSE1]](s32)
+    ; CHECK: $vgpr0_vgpr1 = COPY [[MV]](s64)
     %0:_(s64) = COPY $vgpr0_vgpr1
     %1:_(s64) = G_BITREVERSE %0
     $vgpr0_vgpr1 = COPY %1
 ...
 
 ---
 name: bitreverse_v2s64
 
 body: |
   bb.0:
     liveins: $vgpr0_vgpr1_vgpr2_vgpr3
     ; CHECK-LABEL: name: bitreverse_v2s64
     ; CHECK: [[COPY:%[0-9]+]]:_(<2 x s64>) = COPY $vgpr0_vgpr1_vgpr2_vgpr3
     ; CHECK: [[UV:%[0-9]+]]:_(s64), [[UV1:%[0-9]+]]:_(s64) = G_UNMERGE_VALUES [[COPY]](<2 x s64>)
-    ; CHECK: [[BITREVERSE:%[0-9]+]]:_(s64) = G_BITREVERSE [[UV]]
-    ; CHECK: [[BITREVERSE1:%[0-9]+]]:_(s64) = G_BITREVERSE [[UV1]]
-    ; CHECK: [[BUILD_VECTOR:%[0-9]+]]:_(<2 x s64>) = G_BUILD_VECTOR [[BITREVERSE]](s64), [[BITREVERSE1]](s64)
+    ; CHECK: [[UV2:%[0-9]+]]:_(s32), [[UV3:%[0-9]+]]:_(s32) = G_UNMERGE_VALUES [[UV]](s64)
+    ; CHECK: [[BITREVERSE:%[0-9]+]]:_(s32) = G_BITREVERSE [[UV3]]
+    ; CHECK: [[BITREVERSE1:%[0-9]+]]:_(s32) = G_BITREVERSE [[UV2]]
+    ; CHECK: [[MV:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[BITREVERSE]](s32), [[BITREVERSE1]](s32)
+    ; CHECK: [[UV4:%[0-9]+]]:_(s32), [[UV5:%[0-9]+]]:_(s32) = G_UNMERGE_VALUES [[UV1]](s64)
+    ; CHECK: [[BITREVERSE2:%[0-9]+]]:_(s32) = G_BITREVERSE [[UV5]]
+    ; CHECK: [[BITREVERSE3:%[0-9]+]]:_(s32) = G_BITREVERSE [[UV4]]
+    ; CHECK: [[MV1:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[BITREVERSE2]](s32), [[BITREVERSE3]](s32)
+    ; CHECK: [[BUILD_VECTOR:%[0-9]+]]:_(<2 x s64>) = G_BUILD_VECTOR [[MV]](s64), [[MV1]](s64)
     ; CHECK: $vgpr0_vgpr1_vgpr2_vgpr3 = COPY [[BUILD_VECTOR]](<2 x s64>)
     %0:_(<2 x s64>) = COPY $vgpr0_vgpr1_vgpr2_vgpr3
     %1:_(<2 x s64>) = G_BITREVERSE %0
     $vgpr0_vgpr1_vgpr2_vgpr3 = COPY %1
 ...

llvm/test/CodeGen/Mips/GlobalISel/legalizer/bitreverse.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 @bitreverse_i32() { entry: ret void }
+  define void @bitreverse_i64() { entry: ret void }
+
+...
+---
+name:            bitreverse_i32
+alignment:       4
+tracksRegLiveness: true
+body:             |
+  bb.1.entry:
+    liveins: $a0
+
+    ; MIPS32-LABEL: name: bitreverse_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: [[C3:%[0-9]+]]:_(s32) = G_CONSTANT i32 4
+    ; MIPS32: [[C4:%[0-9]+]]:_(s32) = G_CONSTANT i32 -252645136
+    ; MIPS32: [[SHL2:%[0-9]+]]:_(s32) = G_SHL [[OR2]], [[C3]](s32)
+    ; MIPS32: [[AND2:%[0-9]+]]:_(s32) = G_AND [[SHL2]], [[C4]]
+    ; MIPS32: [[AND3:%[0-9]+]]:_(s32) = G_AND [[OR2]], [[C4]]
+    ; MIPS32: [[LSHR2:%[0-9]+]]:_(s32) = G_LSHR [[AND3]], [[C3]](s32)
+    ; MIPS32: [[OR3:%[0-9]+]]:_(s32) = G_OR [[LSHR2]], [[AND2]]
+    ; MIPS32: [[C5:%[0-9]+]]:_(s32) = G_CONSTANT i32 2
+    ; MIPS32: [[C6:%[0-9]+]]:_(s32) = G_CONSTANT i32 -858993460
+    ; MIPS32: [[SHL3:%[0-9]+]]:_(s32) = G_SHL [[OR3]], [[C5]](s32)
+    ; MIPS32: [[AND4:%[0-9]+]]:_(s32) = G_AND [[SHL3]], [[C6]]
+    ; MIPS32: [[AND5:%[0-9]+]]:_(s32) = G_AND [[OR3]], [[C6]]
+    ; MIPS32: [[LSHR3:%[0-9]+]]:_(s32) = G_LSHR [[AND5]], [[C5]](s32)
+    ; MIPS32: [[OR4:%[0-9]+]]:_(s32) = G_OR [[LSHR3]], [[AND4]]
+    ; MIPS32: [[C7:%[0-9]+]]:_(s32) = G_CONSTANT i32 1
+    ; MIPS32: [[C8:%[0-9]+]]:_(s32) = G_CONSTANT i32 -1431655766
+    ; MIPS32: [[SHL4:%[0-9]+]]:_(s32) = G_SHL [[OR4]], [[C7]](s32)
+    ; MIPS32: [[AND6:%[0-9]+]]:_(s32) = G_AND [[SHL4]], [[C8]]
+    ; MIPS32: [[AND7:%[0-9]+]]:_(s32) = G_AND [[OR4]], [[C8]]
+    ; MIPS32: [[LSHR4:%[0-9]+]]:_(s32) = G_LSHR [[AND7]], [[C7]](s32)
+    ; MIPS32: [[OR5:%[0-9]+]]:_(s32) = G_OR [[LSHR4]], [[AND6]]
+    ; MIPS32: $v0 = COPY [[OR5]](s32)
+    ; MIPS32: RetRA implicit $v0
+    ; MIPS32R2-LABEL: name: bitreverse_i32
+    ; MIPS32R2: liveins: $a0
+    ; MIPS32R2: [[COPY:%[0-9]+]]:_(s32) = COPY $a0
+    ; MIPS32R2: [[BSWAP:%[0-9]+]]:_(s32) = G_BSWAP [[COPY]]
+    ; MIPS32R2: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 4
+    ; MIPS32R2: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 -252645136
+    ; MIPS32R2: [[SHL:%[0-9]+]]:_(s32) = G_SHL [[BSWAP]], [[C]](s32)
+    ; MIPS32R2: [[AND:%[0-9]+]]:_(s32) = G_AND [[SHL]], [[C1]]
+    ; MIPS32R2: [[AND1:%[0-9]+]]:_(s32) = G_AND [[BSWAP]], [[C1]]
+    ; MIPS32R2: [[LSHR:%[0-9]+]]:_(s32) = G_LSHR [[AND1]], [[C]](s32)
+    ; MIPS32R2: [[OR:%[0-9]+]]:_(s32) = G_OR [[LSHR]], [[AND]]
+    ; MIPS32R2: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 2
+    ; MIPS32R2: [[C3:%[0-9]+]]:_(s32) = G_CONSTANT i32 -858993460
+    ; MIPS32R2: [[SHL1:%[0-9]+]]:_(s32) = G_SHL [[OR]], [[C2]](s32)
+    ; MIPS32R2: [[AND2:%[0-9]+]]:_(s32) = G_AND [[SHL1]], [[C3]]
+    ; MIPS32R2: [[AND3:%[0-9]+]]:_(s32) = G_AND [[OR]], [[C3]]
+    ; MIPS32R2: [[LSHR1:%[0-9]+]]:_(s32) = G_LSHR [[AND3]], [[C2]](s32)
+    ; MIPS32R2: [[OR1:%[0-9]+]]:_(s32) = G_OR [[LSHR1]], [[AND2]]
+    ; MIPS32R2: [[C4:%[0-9]+]]:_(s32) = G_CONSTANT i32 1
+    ; MIPS32R2: [[C5:%[0-9]+]]:_(s32) = G_CONSTANT i32 -1431655766
+    ; MIPS32R2: [[SHL2:%[0-9]+]]:_(s32) = G_SHL [[OR1]], [[C4]](s32)
+    ; MIPS32R2: [[AND4:%[0-9]+]]:_(s32) = G_AND [[SHL2]], [[C5]]
+    ; MIPS32R2: [[AND5:%[0-9]+]]:_(s32) = G_AND [[OR1]], [[C5]]
+    ; MIPS32R2: [[LSHR2:%[0-9]+]]:_(s32) = G_LSHR [[AND5]], [[C4]](s32)
+    ; MIPS32R2: [[OR2:%[0-9]+]]:_(s32) = G_OR [[LSHR2]], [[AND4]]
+    ; MIPS32R2: $v0 = COPY [[OR2]](s32)
+    ; MIPS32R2: RetRA implicit $v0
+    %0:_(s32) = COPY $a0
+    %1:_(s32) = G_BITREVERSE %0
+    $v0 = COPY %1(s32)
+    RetRA implicit $v0
+
+...
+---
+name:            bitreverse_i64
+alignment:       4
+tracksRegLiveness: true
+body:             |
+  bb.1.entry:
+    liveins: $a0, $a1
+
+    ; MIPS32-LABEL: name: bitreverse_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: [[C3:%[0-9]+]]:_(s32) = G_CONSTANT i32 4
+    ; MIPS32: [[C4:%[0-9]+]]:_(s32) = G_CONSTANT i32 -252645136
+    ; MIPS32: [[SHL2:%[0-9]+]]:_(s32) = G_SHL [[OR2]], [[C3]](s32)
+    ; MIPS32: [[AND2:%[0-9]+]]:_(s32) = G_AND [[SHL2]], [[C4]]
+    ; MIPS32: [[AND3:%[0-9]+]]:_(s32) = G_AND [[OR2]], [[C4]]
+    ; MIPS32: [[LSHR2:%[0-9]+]]:_(s32) = G_LSHR [[AND3]], [[C3]](s32)
+    ; MIPS32: [[OR3:%[0-9]+]]:_(s32) = G_OR [[LSHR2]], [[AND2]]
+    ; MIPS32: [[C5:%[0-9]+]]:_(s32) = G_CONSTANT i32 2
+    ; MIPS32: [[C6:%[0-9]+]]:_(s32) = G_CONSTANT i32 -858993460
+    ; MIPS32: [[SHL3:%[0-9]+]]:_(s32) = G_SHL [[OR3]], [[C5]](s32)
+    ; MIPS32: [[AND4:%[0-9]+]]:_(s32) = G_AND [[SHL3]], [[C6]]
+    ; MIPS32: [[AND5:%[0-9]+]]:_(s32) = G_AND [[OR3]], [[C6]]
+    ; MIPS32: [[LSHR3:%[0-9]+]]:_(s32) = G_LSHR [[AND5]], [[C5]](s32)
+    ; MIPS32: [[OR4:%[0-9]+]]:_(s32) = G_OR [[LSHR3]], [[AND4]]
+    ; MIPS32: [[C7:%[0-9]+]]:_(s32) = G_CONSTANT i32 1
+    ; MIPS32: [[C8:%[0-9]+]]:_(s32) = G_CONSTANT i32 -1431655766
+    ; MIPS32: [[SHL4:%[0-9]+]]:_(s32) = G_SHL [[OR4]], [[C7]](s32)
+    ; MIPS32: [[AND6:%[0-9]+]]:_(s32) = G_AND [[SHL4]], [[C8]]
+    ; MIPS32: [[AND7:%[0-9]+]]:_(s32) = G_AND [[OR4]], [[C8]]
+    ; MIPS32: [[LSHR4:%[0-9]+]]:_(s32) = G_LSHR [[AND7]], [[C7]](s32)
+    ; MIPS32: [[OR5:%[0-9]+]]:_(s32) = G_OR [[LSHR4]], [[AND6]]
+    ; MIPS32: [[SHL5:%[0-9]+]]:_(s32) = G_SHL [[COPY]], [[C]](s32)
+    ; MIPS32: [[LSHR5:%[0-9]+]]:_(s32) = G_LSHR [[COPY]], [[C]](s32)
+    ; MIPS32: [[OR6:%[0-9]+]]:_(s32) = G_OR [[LSHR5]], [[SHL5]]
+    ; MIPS32: [[AND8:%[0-9]+]]:_(s32) = G_AND [[COPY]], [[C1]]
+    ; MIPS32: [[SHL6:%[0-9]+]]:_(s32) = G_SHL [[AND8]], [[C2]](s32)
+    ; MIPS32: [[OR7:%[0-9]+]]:_(s32) = G_OR [[OR6]], [[SHL6]]
+    ; MIPS32: [[LSHR6:%[0-9]+]]:_(s32) = G_LSHR [[COPY]], [[C2]](s32)
+    ; MIPS32: [[AND9:%[0-9]+]]:_(s32) = G_AND [[LSHR6]], [[C1]]
+    ; MIPS32: [[OR8:%[0-9]+]]:_(s32) = G_OR [[OR7]], [[AND9]]
+    ; MIPS32: [[SHL7:%[0-9]+]]:_(s32) = G_SHL [[OR8]], [[C3]](s32)
+    ; MIPS32: [[AND10:%[0-9]+]]:_(s32) = G_AND [[SHL7]], [[C4]]
+    ; MIPS32: [[AND11:%[0-9]+]]:_(s32) = G_AND [[OR8]], [[C4]]
+    ; MIPS32: [[LSHR7:%[0-9]+]]:_(s32) = G_LSHR [[AND11]], [[C3]](s32)
+    ; MIPS32: [[OR9:%[0-9]+]]:_(s32) = G_OR [[LSHR7]], [[AND10]]
+    ; MIPS32: [[SHL8:%[0-9]+]]:_(s32) = G_SHL [[OR9]], [[C5]](s32)
+    ; MIPS32: [[AND12:%[0-9]+]]:_(s32) = G_AND [[SHL8]], [[C6]]
+    ; MIPS32: [[AND13:%[0-9]+]]:_(s32) = G_AND [[OR9]], [[C6]]
+    ; MIPS32: [[LSHR8:%[0-9]+]]:_(s32) = G_LSHR [[AND13]], [[C5]](s32)
+    ; MIPS32: [[OR10:%[0-9]+]]:_(s32) = G_OR [[LSHR8]], [[AND12]]
+    ; MIPS32: [[SHL9:%[0-9]+]]:_(s32) = G_SHL [[OR10]], [[C7]](s32)
+    ; MIPS32: [[AND14:%[0-9]+]]:_(s32) = G_AND [[SHL9]], [[C8]]
+    ; MIPS32: [[AND15:%[0-9]+]]:_(s32) = G_AND [[OR10]], [[C8]]
+    ; MIPS32: [[LSHR9:%[0-9]+]]:_(s32) = G_LSHR [[AND15]], [[C7]](s32)
+    ; MIPS32: [[OR11:%[0-9]+]]:_(s32) = G_OR [[LSHR9]], [[AND14]]
+    ; MIPS32: $v0 = COPY [[OR5]](s32)
+    ; MIPS32: $v1 = COPY [[OR11]](s32)
+    ; MIPS32: RetRA implicit $v0, implicit $v1
+    ; MIPS32R2-LABEL: name: bitreverse_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: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 4
+    ; MIPS32R2: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 -252645136
+    ; MIPS32R2: [[SHL:%[0-9]+]]:_(s32) = G_SHL [[BSWAP]], [[C]](s32)
+    ; MIPS32R2: [[AND:%[0-9]+]]:_(s32) = G_AND [[SHL]], [[C1]]
+    ; MIPS32R2: [[AND1:%[0-9]+]]:_(s32) = G_AND [[BSWAP]], [[C1]]
+    ; MIPS32R2: [[LSHR:%[0-9]+]]:_(s32) = G_LSHR [[AND1]], [[C]](s32)
+    ; MIPS32R2: [[OR:%[0-9]+]]:_(s32) = G_OR [[LSHR]], [[AND]]
+    ; MIPS32R2: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 2
+    ; MIPS32R2: [[C3:%[0-9]+]]:_(s32) = G_CONSTANT i32 -858993460
+    ; MIPS32R2: [[SHL1:%[0-9]+]]:_(s32) = G_SHL [[OR]], [[C2]](s32)
+    ; MIPS32R2: [[AND2:%[0-9]+]]:_(s32) = G_AND [[SHL1]], [[C3]]
+    ; MIPS32R2: [[AND3:%[0-9]+]]:_(s32) = G_AND [[OR]], [[C3]]
+    ; MIPS32R2: [[LSHR1:%[0-9]+]]:_(s32) = G_LSHR [[AND3]], [[C2]](s32)
+    ; MIPS32R2: [[OR1:%[0-9]+]]:_(s32) = G_OR [[LSHR1]], [[AND2]]
+    ; MIPS32R2: [[C4:%[0-9]+]]:_(s32) = G_CONSTANT i32 1
+    ; MIPS32R2: [[C5:%[0-9]+]]:_(s32) = G_CONSTANT i32 -1431655766
+    ; MIPS32R2: [[SHL2:%[0-9]+]]:_(s32) = G_SHL [[OR1]], [[C4]](s32)
+    ; MIPS32R2: [[AND4:%[0-9]+]]:_(s32) = G_AND [[SHL2]], [[C5]]
+    ; MIPS32R2: [[AND5:%[0-9]+]]:_(s32) = G_AND [[OR1]], [[C5]]
+    ; MIPS32R2: [[LSHR2:%[0-9]+]]:_(s32) = G_LSHR [[AND5]], [[C4]](s32)
+    ; MIPS32R2: [[OR2:%[0-9]+]]:_(s32) = G_OR [[LSHR2]], [[AND4]]
+    ; MIPS32R2: [[BSWAP1:%[0-9]+]]:_(s32) = G_BSWAP [[COPY]]
+    ; MIPS32R2: [[SHL3:%[0-9]+]]:_(s32) = G_SHL [[BSWAP1]], [[C]](s32)
+    ; MIPS32R2: [[AND6:%[0-9]+]]:_(s32) = G_AND [[SHL3]], [[C1]]
+    ; MIPS32R2: [[AND7:%[0-9]+]]:_(s32) = G_AND [[BSWAP1]], [[C1]]
+    ; MIPS32R2: [[LSHR3:%[0-9]+]]:_(s32) = G_LSHR [[AND7]], [[C]](s32)
+    ; MIPS32R2: [[OR3:%[0-9]+]]:_(s32) = G_OR [[LSHR3]], [[AND6]]
+    ; MIPS32R2: [[SHL4:%[0-9]+]]:_(s32) = G_SHL [[OR3]], [[C2]](s32)
+    ; MIPS32R2: [[AND8:%[0-9]+]]:_(s32) = G_AND [[SHL4]], [[C3]]
+    ; MIPS32R2: [[AND9:%[0-9]+]]:_(s32) = G_AND [[OR3]], [[C3]]
+    ; MIPS32R2: [[LSHR4:%[0-9]+]]:_(s32) = G_LSHR [[AND9]], [[C2]](s32)
+    ; MIPS32R2: [[OR4:%[0-9]+]]:_(s32) = G_OR [[LSHR4]], [[AND8]]
+    ; MIPS32R2: [[SHL5:%[0-9]+]]:_(s32) = G_SHL [[OR4]], [[C4]](s32)
+    ; MIPS32R2: [[AND10:%[0-9]+]]:_(s32) = G_AND [[SHL5]], [[C5]]
+    ; MIPS32R2: [[AND11:%[0-9]+]]:_(s32) = G_AND [[OR4]], [[C5]]
+    ; MIPS32R2: [[LSHR5:%[0-9]+]]:_(s32) = G_LSHR [[AND11]], [[C4]](s32)
+    ; MIPS32R2: [[OR5:%[0-9]+]]:_(s32) = G_OR [[LSHR5]], [[AND10]]
+    ; MIPS32R2: $v0 = COPY [[OR2]](s32)
+    ; MIPS32R2: $v1 = COPY [[OR5]](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_BITREVERSE %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/bitreverse.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.bitreverse.i32(i32)
+define i32 @bitreverse_i32(i32 signext %a) {
+; MIPS32-LABEL: bitreverse_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 $1, $1, $2
+; MIPS32-NEXT:    lui $2, 61680
+; MIPS32-NEXT:    ori $2, $2, 61680
+; MIPS32-NEXT:    sll $3, $1, 4
+; MIPS32-NEXT:    and $3, $3, $2
+; MIPS32-NEXT:    and $1, $1, $2
+; MIPS32-NEXT:    srl $1, $1, 4
+; MIPS32-NEXT:    or $1, $1, $3
+; MIPS32-NEXT:    lui $2, 52428
+; MIPS32-NEXT:    ori $2, $2, 52428
+; MIPS32-NEXT:    sll $3, $1, 2
+; MIPS32-NEXT:    and $3, $3, $2
+; MIPS32-NEXT:    and $1, $1, $2
+; MIPS32-NEXT:    srl $1, $1, 2
+; MIPS32-NEXT:    or $1, $1, $3
+; MIPS32-NEXT:    lui $2, 43690
+; MIPS32-NEXT:    ori $2, $2, 43690
+; MIPS32-NEXT:    sll $3, $1, 1
+; MIPS32-NEXT:    and $3, $3, $2
+; MIPS32-NEXT:    and $1, $1, $2
+; MIPS32-NEXT:    srl $1, $1, 1
+; MIPS32-NEXT:    or $2, $1, $3
+; MIPS32-NEXT:    jr $ra
+; MIPS32-NEXT:    nop
+;
+; MIPS32R2-LABEL: bitreverse_i32:
+; MIPS32R2:       # %bb.0: # %entry
+; MIPS32R2-NEXT:    wsbh $1, $4
+; MIPS32R2-NEXT:    rotr $1, $1, 16
+; MIPS32R2-NEXT:    lui $2, 61680
+; MIPS32R2-NEXT:    ori $2, $2, 61680
+; MIPS32R2-NEXT:    sll $3, $1, 4
+; MIPS32R2-NEXT:    and $3, $3, $2
+; MIPS32R2-NEXT:    and $1, $1, $2
+; MIPS32R2-NEXT:    srl $1, $1, 4
+; MIPS32R2-NEXT:    or $1, $1, $3
+; MIPS32R2-NEXT:    lui $2, 52428
+; MIPS32R2-NEXT:    ori $2, $2, 52428
+; MIPS32R2-NEXT:    sll $3, $1, 2
+; MIPS32R2-NEXT:    and $3, $3, $2
+; MIPS32R2-NEXT:    and $1, $1, $2
+; MIPS32R2-NEXT:    srl $1, $1, 2
+; MIPS32R2-NEXT:    or $1, $1, $3
+; MIPS32R2-NEXT:    lui $2, 43690
+; MIPS32R2-NEXT:    ori $2, $2, 43690
+; MIPS32R2-NEXT:    sll $3, $1, 1
+; MIPS32R2-NEXT:    and $3, $3, $2
+; MIPS32R2-NEXT:    and $1, $1, $2
+; MIPS32R2-NEXT:    srl $1, $1, 1
+; MIPS32R2-NEXT:    or $2, $1, $3
+; MIPS32R2-NEXT:    jr $ra
+; MIPS32R2-NEXT:    nop
+entry:
+  %0 = call i32 @llvm.bitreverse.i32(i32 %a)
+  ret i32 %0
+}
+
+declare i64 @llvm.bitreverse.i64(i64)
+define i64 @bitreverse_i64(i64 signext %a) {
+; MIPS32-LABEL: bitreverse_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 $1, $1, $2
+; MIPS32-NEXT:    lui $2, 61680
+; MIPS32-NEXT:    ori $2, $2, 61680
+; MIPS32-NEXT:    sll $3, $1, 4
+; MIPS32-NEXT:    and $3, $3, $2
+; MIPS32-NEXT:    and $1, $1, $2
+; MIPS32-NEXT:    srl $1, $1, 4
+; MIPS32-NEXT:    or $1, $1, $3
+; MIPS32-NEXT:    lui $3, 52428
+; MIPS32-NEXT:    ori $3, $3, 52428
+; MIPS32-NEXT:    sll $5, $1, 2
+; MIPS32-NEXT:    and $5, $5, $3
+; MIPS32-NEXT:    and $1, $1, $3
+; MIPS32-NEXT:    srl $1, $1, 2
+; MIPS32-NEXT:    or $1, $1, $5
+; MIPS32-NEXT:    lui $5, 43690
+; MIPS32-NEXT:    ori $5, $5, 43690
+; MIPS32-NEXT:    sll $6, $1, 1
+; MIPS32-NEXT:    and $6, $6, $5
+; MIPS32-NEXT:    and $1, $1, $5
+; MIPS32-NEXT:    srl $1, $1, 1
+; MIPS32-NEXT:    or $1, $1, $6
+; MIPS32-NEXT:    sll $6, $4, 24
+; MIPS32-NEXT:    srl $7, $4, 24
+; MIPS32-NEXT:    or $6, $7, $6
+; MIPS32-NEXT:    andi $7, $4, 65280
+; MIPS32-NEXT:    sll $7, $7, 8
+; MIPS32-NEXT:    or $6, $6, $7
+; MIPS32-NEXT:    srl $4, $4, 8
+; MIPS32-NEXT:    andi $4, $4, 65280
+; MIPS32-NEXT:    or $4, $6, $4
+; MIPS32-NEXT:    sll $6, $4, 4
+; MIPS32-NEXT:    and $6, $6, $2
+; MIPS32-NEXT:    and $2, $4, $2
+; MIPS32-NEXT:    srl $2, $2, 4
+; MIPS32-NEXT:    or $2, $2, $6
+; MIPS32-NEXT:    sll $4, $2, 2
+; MIPS32-NEXT:    and $4, $4, $3
+; MIPS32-NEXT:    and $2, $2, $3
+; MIPS32-NEXT:    srl $2, $2, 2
+; MIPS32-NEXT:    or $2, $2, $4
+; MIPS32-NEXT:    sll $3, $2, 1
+; MIPS32-NEXT:    and $3, $3, $5
+; MIPS32-NEXT:    and $2, $2, $5
+; MIPS32-NEXT:    srl $2, $2, 1
+; MIPS32-NEXT:    or $3, $2, $3
+; MIPS32-NEXT:    move $2, $1
+; MIPS32-NEXT:    jr $ra
+; MIPS32-NEXT:    nop
+;
+; MIPS32R2-LABEL: bitreverse_i64:
+; MIPS32R2:       # %bb.0: # %entry
+; MIPS32R2-NEXT:    wsbh $1, $5
+; MIPS32R2-NEXT:    rotr $1, $1, 16
+; MIPS32R2-NEXT:    lui $2, 61680
+; MIPS32R2-NEXT:    ori $2, $2, 61680
+; MIPS32R2-NEXT:    sll $3, $1, 4
+; MIPS32R2-NEXT:    and $3, $3, $2
+; MIPS32R2-NEXT:    and $1, $1, $2
+; MIPS32R2-NEXT:    srl $1, $1, 4
+; MIPS32R2-NEXT:    or $1, $1, $3
+; MIPS32R2-NEXT:    lui $3, 52428
+; MIPS32R2-NEXT:    ori $3, $3, 52428
+; MIPS32R2-NEXT:    sll $5, $1, 2
+; MIPS32R2-NEXT:    and $5, $5, $3
+; MIPS32R2-NEXT:    and $1, $1, $3
+; MIPS32R2-NEXT:    srl $1, $1, 2
+; MIPS32R2-NEXT:    or $1, $1, $5
+; MIPS32R2-NEXT:    lui $5, 43690
+; MIPS32R2-NEXT:    ori $5, $5, 43690
+; MIPS32R2-NEXT:    sll $6, $1, 1
+; MIPS32R2-NEXT:    and $6, $6, $5
+; MIPS32R2-NEXT:    and $1, $1, $5
+; MIPS32R2-NEXT:    srl $1, $1, 1
+; MIPS32R2-NEXT:    or $1, $1, $6
+; MIPS32R2-NEXT:    wsbh $4, $4
+; MIPS32R2-NEXT:    rotr $4, $4, 16
+; MIPS32R2-NEXT:    sll $6, $4, 4
+; MIPS32R2-NEXT:    and $6, $6, $2
+; MIPS32R2-NEXT:    and $2, $4, $2
+; MIPS32R2-NEXT:    srl $2, $2, 4
+; MIPS32R2-NEXT:    or $2, $2, $6
+; MIPS32R2-NEXT:    sll $4, $2, 2
+; MIPS32R2-NEXT:    and $4, $4, $3
+; MIPS32R2-NEXT:    and $2, $2, $3
+; MIPS32R2-NEXT:    srl $2, $2, 2
+; MIPS32R2-NEXT:    or $2, $2, $4
+; MIPS32R2-NEXT:    sll $3, $2, 1
+; MIPS32R2-NEXT:    and $3, $3, $5
+; MIPS32R2-NEXT:    and $2, $2, $5
+; MIPS32R2-NEXT:    srl $2, $2, 1
+; MIPS32R2-NEXT:    or $3, $2, $3
+; MIPS32R2-NEXT:    move $2, $1
+; MIPS32R2-NEXT:    jr $ra
+; MIPS32R2-NEXT:    nop
+entry:
+  %0 = call i64 @llvm.bitreverse.i64(i64 %a)
+  ret i64 %0
+}