Allow `AND-NOT` to be emitted from `NOT` + <some bit/byte reordering> + `AND`

[Validark]

Zen 5 Assembly:

foo:
        mov     rax, rdi
-       not     rax
        bswap   rax
-       and     rax, rdi
+       andn    rax, rax, rdi
        ret

Zig version: (Godbolt)

export fn foo(a: u64) u64 {
    return a & ~@byteSwap(a);
}

export fn bar(a: u64) u64 {
    return andn(a, @byteSwap(a));
}

LLVM version (optimized): (Godbolt)

define dso_local i64 @foo(i64 %0) local_unnamed_addr {
Entry:
  %1 = xor i64 %0, -1
  %2 = tail call i64 @llvm.bswap.i64(i64 %1)
  %3 = and i64 %2, %0
  ret i64 %3
}

declare i64 @llvm.bswap.i64(i64) #1

define dso_local i64 @bar(i64 %0) local_unnamed_addr {
Entry:
  %1 = tail call i64 @llvm.bswap.i64(i64 %0)
  %2 = tail call i64 asm "andn ${1}, ${2}, ${0}", "=r,r,r,~{dirflag},~{fpsr},~{flags}"(i64 %0, i64 %1) #3
  ret i64 %2
}

Problem occurs in foo even when you manually change it to:

define dso_local i64 @foo(i64 %0) local_unnamed_addr {
Entry:
  %1 = tail call i64 @llvm.bswap.i64(i64 %0)
  %2 = xor i64 %1, -1
  %3 = and i64 %2, %0
  ret i64 %3
}

[Validark]

Same issue happens to: (Zig godbolt)

export fn foo(a: u64) u64 {
    return a & ~@bitReverse(a);
}

export fn bar(a: u64) u64 {
    return andn(a, @bitReverse(a));
}

.LCPI0_1:
        .byte   1
        .byte   2
        .byte   4
        .byte   8
        .byte   16
        .byte   32
        .byte   64
        .byte   128
foo:
-       mov     rax, rdi
-       not     rax
        vmovq   xmm0, rax
        vgf2p8affineqb  xmm0, xmm0, qword ptr [rip + .LCPI0_1]{1to2}, 0
        vmovq   rax, xmm0
        bswap   rax
-       and     rax, rdi
        ret

.LCPI1_1:
        .byte   1
        .byte   2
        .byte   4
        .byte   8
        .byte   16
        .byte   32
        .byte   64
        .byte   128
bar:
        vmovq   xmm0, rdi
        vgf2p8affineqb  xmm0, xmm0, qword ptr [rip + .LCPI1_1]{1to2}, 0
        vmovq   rax, xmm0
        bswap   rax
+       andn    rax, rax, rdi
        ret

LLVM version: (Godbolt)

define dso_local i64 @foo(i64 %0) local_unnamed_addr {
Entry:
  %1 = xor i64 %0, -1
  %2 = tail call i64 @llvm.bitreverse.i64(i64 %1)
  %3 = and i64 %2, %0
  ret i64 %3
}

declare i64 @llvm.bitreverse.i64(i64) #1

define dso_local i64 @bar(i64 %0) local_unnamed_addr {
Entry:
  %1 = tail call i64 @llvm.bitreverse.i64(i64 %0)
  %2 = tail call i64 asm "andn ${1}, ${2}, ${0}", "=r,r,r,~{dirflag},~{fpsr},~{flags}"(i64 %0, i64 %1) #3
  ret i64 %2
}

[Validark]

Same problem exists on Aarch64:

foo:
        mvn     x8, x0
        rbit    x8, x8
        and     x0, x8, x0
        ret

bar:
        rbit    x8, x0
        bic     x0, x0, x8
        ret

Godbolt

Happens on RISC-V and PowerPC targets as well, but the assembly is messy. Same problem occurs for machines that have OR-NOT

[dtcxzyw]

We did similar optimization in InstCombine: #77460

This optimization also holds for BITREVERSE/ROTL/ROTR.

[RKSimon]

Yes, it looks like DAG needs the reverse fold on targets with TLI.hasAndNot