[DAG] Add SimplifyDemandedBits support for BSWAP

[spatel]

Summary

This affects a couple of changes that I need some target-specific advice on:

aarch64 - we're losing this as the zext is being simplified to aext, so the canonicalization fails to confirm that the upper bits are zero. I can try adding a zext(bswap(trunc(x))) variant if that'd be useful as an alternative?

amdgpu - I think these are all benign.

[efriedma]

and+rev16/rev32 isn't really any better than rev+lsr; that's fine as far as it goes. But please make sure we have coverage for cases where the zero-extension is free (e.g. the operand is a load, or a zeroext value, or the result of i32 arithmetic).

[nhaehnle]

Hmm, this is one of those cases where it'd be awesome to have a Godbolt for the tests.

AMDGPU/bitreverse.ll looks good to me. AMDGPU/bswap.ll is _probably_ fine but I'd feel more comfortable seeing the assembly in full.

[arsenm]

test/CodeGen/AMDGPU/bitreverse.ll

1009–1024

This increased the instruction count?

[RKSimon]

rebase

[RKSimon]

updated with the new aarch64 tests

• the zext(load()) test fails to recognise the upper bits are zero as it becomes anyext(load())
• the arithmetic ubfx tests do still exercise the rotr(bswap()) combine

just need to address the powerpc regression now

[arsenm]

LGTM

[RKSimon]

@nemanjai Do you have any comments on the powerpc issue? You created the original test case at rL347288.

[efriedma]

test/CodeGen/AArch64/arm64-rev.ll

102

This is a regression... but it's sort of orthogonal to this patch, I guess. It's okay for now.

[RKSimon]

test/CodeGen/AArch64/arm64-rev.ll

102

I've raised https://bugs.llvm.org/show_bug.cgi?id=40881 to cover this - its a common issue as we make SimplifyDemandedBits more capable.

[RKSimon]

rebase

[RKSimon]

rebase

[RKSimon]

rebased now that BITREVERSE support has been committed in rL360534

[spatel]

Commandeering to rebase.

[spatel]

Patch updated:
No code changes, but the PPC regression disappears after rG2f0c7fd2dbd0, so I think this is safe to commit now.

[xbolva00]

Seems fine.

Please update commit message.

[RKSimon]

Thanks for completing this @spatel !

lib/CodeGen/SelectionDAG/TargetLowering.cpp

if (ConstantSDNode *SA = isConstOrConstSplat(Op2)) {
       Known2.Zero <<= (IsFSHL ? Amt : (BitWidth - Amt));
       Known.One.lshrInPlace(IsFSHL ? (BitWidth - Amt) : Amt);
       Known.Zero.lshrInPlace(IsFSHL ? (BitWidth - Amt) : Amt);
       Known.One |= Known2.One;
       Known.Zero |= Known2.Zero;
     }
     break;
   }
+  case ISD::BITREVERSE: {
+    SDValue Src = Op.getOperand(0);
+    APInt DemandedSrcBits = DemandedBits.reverseBits();
+    if (SimplifyDemandedBits(Src, DemandedSrcBits, DemandedElts, Known2, TLO,
+                             Depth + 1))
+      return true;
+    Known.One = Known2.One.reverseBits();
+    Known.Zero = Known2.Zero.reverseBits();
+    break;
+  }
+  case ISD::BSWAP: {
+    SDValue Src = Op.getOperand(0);
+    APInt DemandedSrcBits = DemandedBits.byteSwap();
+    if (SimplifyDemandedBits(Src, DemandedSrcBits, DemandedElts, Known2, TLO,
+                             Depth + 1))
+      return true;
+    Known.One = Known2.One.byteSwap();
+    Known.Zero = Known2.Zero.byteSwap();
+    break;
+  }
   case ISD::SIGN_EXTEND_INREG: {
     SDValue Op0 = Op.getOperand(0);
     EVT ExVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
     unsigned ExVTBits = ExVT.getScalarSizeInBits();
 
     // If we only care about the highest bit, don't bother shifting right.
     if (DemandedBits.isSignMask()) {
       unsigned NumSignBits = TLO.DAG.ComputeNumSignBits(Op0);

test/CodeGen/AArch64/arm64-rev.ll

entry:
   ret i64 %0
 }
 
 ; Canonicalize (srl (bswap x), 16) to (rotr (bswap x), 16) if the high 16-bits
 ; of %a are zero. This optimizes rev + lsr 16 to rev16.
 define i32 @test_rev_w_srl16(i16 %a) {
 ; CHECK-LABEL: test_rev_w_srl16:
 ; CHECK:       // %bb.0: // %entry
-; CHECK-NEXT:    and w8, w0, #0xffff
-; CHECK-NEXT:    rev16 w0, w8
+; CHECK-NEXT:    rev w8, w0
+; CHECK-NEXT:    lsr w0, w8, #16
 ; CHECK-NEXT:    ret
 entry:
   %0 = zext i16 %a to i32
   %1 = tail call i32 @llvm.bswap.i32(i32 %0)
   %2 = lshr i32 %1, 16
   ret i32 %2
 }
 
 define i32 @test_rev_w_srl16_load(i16 *%a) {
 ; CHECK-LABEL: test_rev_w_srl16_load:
 ; CHECK:       // %bb.0: // %entry
 ; CHECK-NEXT:    ldrh w8, [x0]
-; CHECK-NEXT:    rev16 w0, w8
+; CHECK-NEXT:    rev w8, w8
+; CHECK-NEXT:    lsr w0, w8, #16
 ; CHECK-NEXT:    ret
 entry:
   %0 = load i16, i16 *%a
   %1 = zext i16 %0 to i32
   %2 = tail call i32 @llvm.bswap.i32(i32 %1)
   %3 = lshr i32 %2, 16
   ret i32 %3
 }
entry:
   ret i32 %4
 }
 
 ; Canonicalize (srl (bswap x), 32) to (rotr (bswap x), 32) if the high 32-bits
 ; of %a are zero. This optimizes rev + lsr 32 to rev32.
 define i64 @test_rev_x_srl32(i32 %a) {
 ; CHECK-LABEL: test_rev_x_srl32:
 ; CHECK:       // %bb.0: // %entry
-; CHECK-NEXT:    mov w8, w0
-; CHECK-NEXT:    rev32 x0, x8
+; CHECK-NEXT:    // kill: def $w0 killed $w0 def $x0
+; CHECK-NEXT:    rev x8, x0
+; CHECK-NEXT:    lsr x0, x8, #32
 ; CHECK-NEXT:    ret
 entry:
   %0 = zext i32 %a to i64
   %1 = tail call i64 @llvm.bswap.i64(i64 %0)
   %2 = lshr i64 %1, 32
   ret i64 %2
 }
 
 define i64 @test_rev_x_srl32_load(i32 *%a) {
 ; CHECK-LABEL: test_rev_x_srl32_load:
 ; CHECK:       // %bb.0: // %entry
 ; CHECK-NEXT:    ldr w8, [x0]
-; CHECK-NEXT:    rev32 x0, x8
+; CHECK-NEXT:    rev x8, x8
+; CHECK-NEXT:    lsr x0, x8, #32
 ; CHECK-NEXT:    ret
 entry:
   %0 = load i32, i32 *%a
   %1 = zext i32 %0 to i64
   %2 = tail call i64 @llvm.bswap.i64(i64 %1)
   %3 = lshr i64 %2, 32
   ret i64 %3
 }

test/CodeGen/AMDGPU/bitreverse.ll

 ;
 ; FLAT-LABEL: s_brev_i16:
 ; FLAT:       ; %bb.0:
 ; FLAT-NEXT:    s_load_dwordx2 s[4:5], s[0:1], 0x24
 ; FLAT-NEXT:    s_load_dword s0, s[0:1], 0x2c
 ; FLAT-NEXT:    s_mov_b32 s7, 0xf000
 ; FLAT-NEXT:    s_mov_b32 s6, -1
 ; FLAT-NEXT:    s_waitcnt lgkmcnt(0)
-; FLAT-NEXT:    s_and_b32 s0, s0, 0xffff
 ; FLAT-NEXT:    s_brev_b32 s0, s0
 ; FLAT-NEXT:    s_lshr_b32 s0, s0, 16
 ; FLAT-NEXT:    v_mov_b32_e32 v0, s0
 ; FLAT-NEXT:    buffer_store_short v0, off, s[4:7], 0
 ; FLAT-NEXT:    s_endpgm
   %brev = call i16 @llvm.bitreverse.i16(i16 %val) #1
   store i16 %brev, i16 addrspace(1)* %out
   ret void

 ; FLAT-NEXT:    s_endpgm
   %tid = call i32 @llvm.amdgcn.workitem.id.x()
   %gep = getelementptr <2 x i64> , <2 x i64> addrspace(1)* %valptr, i32 %tid
   %val = load <2 x i64>, <2 x i64> addrspace(1)* %gep
   %brev = call <2 x i64> @llvm.bitreverse.v2i64(<2 x i64> %val) #1
   store <2 x i64> %brev, <2 x i64> addrspace(1)* %out
   ret void
 }
 
 define float @missing_truncate_promote_bitreverse(i32 %arg) {
 ; SI-LABEL: missing_truncate_promote_bitreverse:
 ; SI:       ; %bb.0: ; %bb
 ; SI-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
 ; SI-NEXT:    v_bfrev_b32_e32 v0, v0
 ; SI-NEXT:    v_lshrrev_b32_e32 v0, 16, v0
 ; SI-NEXT:    v_cvt_f32_f16_e32 v0, v0
 ; SI-NEXT:    s_setpc_b64 s[30:31]
 ;
 ; FLAT-LABEL: missing_truncate_promote_bitreverse:
 ; FLAT:       ; %bb.0: ; %bb
 ; FLAT-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
-; FLAT-NEXT:    v_bfrev_b32_sdwa v0, v0 dst_sel:DWORD dst_unused:UNUSED_PAD src0_sel:WORD_0
+; FLAT-NEXT:    v_bfrev_b32_e32 v0, v0
 ; FLAT-NEXT:    v_cvt_f32_f16_sdwa v0, v0 dst_sel:DWORD dst_unused:UNUSED_PAD src0_sel:WORD_1
 ; FLAT-NEXT:    s_setpc_b64 s[30:31]
 bb:
   %tmp = trunc i32 %arg to i16
   %tmp1 = call i16 @llvm.bitreverse.i16(i16 %tmp)
   %tmp2 = bitcast i16 %tmp1 to half
   %tmp3 = fpext half %tmp2 to float
   ret float %tmp3
 }
 
 attributes #0 = { nounwind }
 attributes #1 = { nounwind readnone }

test/CodeGen/AMDGPU/bswap.ll

 ; SI-NEXT:    v_bfi_b32 v0, s6, v0, v1
 ; SI-NEXT:    v_lshrrev_b32_e32 v0, 16, v0
 ; SI-NEXT:    v_cvt_f32_f16_e32 v0, v0
 ; SI-NEXT:    s_setpc_b64 s[30:31]
 ;
 ; VI-LABEL: missing_truncate_promote_bswap:
 ; VI:       ; %bb.0: ; %bb
 ; VI-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
-; VI-NEXT:    v_and_b32_e32 v0, 0xffff, v0
 ; VI-NEXT:    v_alignbit_b32 v1, v0, v0, 8
 ; VI-NEXT:    v_alignbit_b32 v0, v0, v0, 24
 ; VI-NEXT:    s_mov_b32 s6, 0xff00ff
 ; VI-NEXT:    v_bfi_b32 v0, s6, v0, v1
 ; VI-NEXT:    v_cvt_f32_f16_sdwa v0, v0 dst_sel:DWORD dst_unused:UNUSED_PAD src0_sel:WORD_1
 ; VI-NEXT:    s_setpc_b64 s[30:31]
 bb:
   %tmp = trunc i32 %arg to i16
   %tmp1 = call i16 @llvm.bswap.i16(i16 %tmp)
   %tmp2 = bitcast i16 %tmp1 to half
   %tmp3 = fpext half %tmp2 to float
   ret float %tmp3
 }

test/CodeGen/PowerPC/pr39478.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=powerpc64le-unknown-unknown -verify-machineinstrs | FileCheck %s --check-prefix=CHECKLE
 ; RUN: llc < %s -mtriple=powerpc64-unknown-unknown -verify-machineinstrs | FileCheck %s --check-prefix=CHECKBE
 
 define void @pr39478(i64* %p64, i32* %p32) {
 ; CHECKLE-LABEL: pr39478:
 ; CHECKLE:       # %bb.0: # %entry
-; CHECKLE-NEXT:    lbz 3, 4(3)
+; CHECKLE-NEXT:    ld 3, 0(3)
+; CHECKLE-NEXT:    rldicl 3, 3, 56, 8
+; CHECKLE-NEXT:    srwi 3, 3, 24
 ; CHECKLE-NEXT:    stb 3, 0(4)
 ; CHECKLE-NEXT:    blr
 ;
 ; CHECKBE-LABEL: pr39478:
 ; CHECKBE:       # %bb.0: # %entry
-; CHECKBE-NEXT:    lbz 3, 3(3)
+; CHECKBE-NEXT:    ld 3, 0(3)
+; CHECKBE-NEXT:    rldicl 3, 3, 56, 8
+; CHECKBE-NEXT:    srwi 3, 3, 24
 ; CHECKBE-NEXT:    stb 3, 3(4)
 ; CHECKBE-NEXT:    blr
 entry:
   %tmp32 = load i64, i64* %p64, align 8
   %tmp33 = load i32, i32* %p32, align 4
   %tmp34 = and i32 %tmp33, -256
   %tmp35 = lshr i64 %tmp32, 32
   %tmp36 = shl nuw nsw i64 %tmp35, 24
   %tmp37 = trunc i64 %tmp36 to i32
   %tmp38 = call i32 @llvm.bswap.i32(i32 %tmp37)
   %tmp39 = or i32 %tmp38, %tmp34
   store i32 %tmp39, i32* %p32, align 4
   ret void
 }
 
 declare i32 @llvm.bswap.i32(i32)

test/CodeGen/X86/combine-bitreverse.ll

; X64-NEXT:    retq
   %b = call i32 @llvm.bitreverse.i32(i32 %a0)
   %c = call i32 @llvm.bitreverse.i32(i32 %b)
   ret i32 %c
 }
 
 define <4 x i32> @test_demandedbits_bitreverse(<4 x i32> %a0) nounwind {
 ; X86-LABEL: test_demandedbits_bitreverse:
 ; X86:       # %bb.0:
-; X86-NEXT:    por {{\.LCPI.*}}, %xmm0
 ; X86-NEXT:    pxor %xmm1, %xmm1
 ; X86-NEXT:    movdqa %xmm0, %xmm2
 ; X86-NEXT:    punpckhbw {{.*#+}} xmm2 = xmm2[8],xmm1[8],xmm2[9],xmm1[9],xmm2[10],xmm1[10],xmm2[11],xmm1[11],xmm2[12],xmm1[12],xmm2[13],xmm1[13],xmm2[14],xmm1[14],xmm2[15],xmm1[15]
 ; X86-NEXT:    pshuflw {{.*#+}} xmm2 = xmm2[3,2,1,0,4,5,6,7]
 ; X86-NEXT:    pshufhw {{.*#+}} xmm2 = xmm2[0,1,2,3,7,6,5,4]
 ; X86-NEXT:    punpcklbw {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1],xmm0[2],xmm1[2],xmm0[3],xmm1[3],xmm0[4],xmm1[4],xmm0[5],xmm1[5],xmm0[6],xmm1[6],xmm0[7],xmm1[7]
 ; X86-NEXT:    pshuflw {{.*#+}} xmm0 = xmm0[3,2,1,0,4,5,6,7]
 ; X86-NEXT:    pshufhw {{.*#+}} xmm1 = xmm0[0,1,2,3,7,6,5,4]

 ; X86-NEXT:    psrlw $1, %xmm0
 ; X86-NEXT:    pand {{\.LCPI.*}}, %xmm0
 ; X86-NEXT:    por %xmm1, %xmm0
 ; X86-NEXT:    pand {{\.LCPI.*}}, %xmm0
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_demandedbits_bitreverse:
 ; X64:       # %bb.0:
-; X64-NEXT:    vpor {{.*}}(%rip), %xmm0, %xmm0
 ; X64-NEXT:    vpshufb {{.*#+}} xmm0 = xmm0[3,2,1,0,7,6,5,4,11,10,9,8,15,14,13,12]
 ; X64-NEXT:    vmovdqa {{.*#+}} xmm1 = [15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15]
 ; X64-NEXT:    vpand %xmm1, %xmm0, %xmm2
 ; X64-NEXT:    vmovdqa {{.*#+}} xmm3 = [0,128,64,192,32,160,96,224,16,144,80,208,48,176,112,240]
 ; X64-NEXT:    vpshufb %xmm2, %xmm3, %xmm2
 ; X64-NEXT:    vpsrlw $4, %xmm0, %xmm0
 ; X64-NEXT:    vpand %xmm1, %xmm0, %xmm0
 ; X64-NEXT:    vmovdqa {{.*#+}} xmm1 = [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]

test/CodeGen/X86/combine-bswap.ll

; X64-NEXT:    retq
   %b = call i32 @llvm.bswap.i32(i32 %a0)
   %c = call i32 @llvm.bswap.i32(i32 %b)
   ret i32 %c
 }
 
 define i32 @test_demandedbits_bswap(i32 %a0) nounwind {
 ; X86-LABEL: test_demandedbits_bswap:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl $-16777216, %eax # imm = 0xFF000000
-; X86-NEXT:    orl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    bswapl %eax
 ; X86-NEXT:    andl $-65536, %eax # imm = 0xFFFF0000
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_demandedbits_bswap:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movl %edi, %eax
-; X64-NEXT:    orl $-16777216, %eax # imm = 0xFF000000
 ; X64-NEXT:    bswapl %eax
 ; X64-NEXT:    andl $-65536, %eax # imm = 0xFFFF0000
 ; X64-NEXT:    retq
   %b = or i32 %a0, 4278190080
   %c = call i32 @llvm.bswap.i32(i32 %b)
   %d = and i32 %c, 4294901760
   ret i32 %d
 }