<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/111433>111433</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [BMI2] Interleaving bitstrings should compile to `pdep`s
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          Validark
      </td>
    </tr>
</table>

<pre>
    I can write a bitstring interleave easily like so, in Zig:

```zig
const std = @import("std");

export fn foo(a: u32, b: u32) u64 {
    return @bitCast(std.simd.interlace(.{
 @as(@Vector(32, u1), @bitCast(a)),
        @as(@Vector(32, u1), @bitCast(b))
    }));
}
```

After optimizations, LLVM sees this:

```llvm
define dso_local i64 @foo(i32 %0, i32 %1) local_unnamed_addr {
Entry:
  %2 = bitcast i32 %0 to <32 x i1>
  %3 = bitcast i32 %1 to <32 x i1>
  %4 = shufflevector <32 x i1> %2, <32 x i1> %3, <64 x i32> <i32 0, i32 32, i32 1, i32 33, i32 2, i32 34, i32 3, i32 35, i32 4, i32 36, i32 5, i32 37, i32 6, i32 38, i32 7, i32 39, i32 8, i32 40, i32 9, i32 41, i32 10, i32 42, i32 11, i32 43, i32 12, i32 44, i32 13, i32 45, i32 14, i32 46, i32 15, i32 47, i32 16, i32 48, i32 17, i32 49, i32 18, i32 50, i32 19, i32 51, i32 20, i32 52, i32 21, i32 53, i32 22, i32 54, i32 23, i32 55, i32 24, i32 56, i32 25, i32 57, i32 26, i32 58, i32 27, i32 59, i32 28, i32 60, i32 29, i32 61, i32 30, i32 62, i32 31, i32 63>
  %5 = bitcast <64 x i1> %4 to i64
  ret i64 %5
}
```

It would be nice if this could be recognized as interleaving the bits, and emit a nice algorithm to accomplish that.

Currently, it compiles like so on znver4:

```asm
.LCPI0_0:
        .byte   0
        .byte 64
        .byte   1
        .byte   65
        .byte   2
 .byte   66
        .byte   3
        .byte   67
        .byte 4
        .byte   68
        .byte   5
        .byte   69
 .byte   6
        .byte   70
        .byte   7
        .byte 71
        .byte   8
        .byte   72
        .byte   9
 .byte   73
        .byte   10
        .byte   74
        .byte 11
        .byte   75
        .byte   12
        .byte   76
 .byte   13
        .byte   77
        .byte   14
        .byte 78
        .byte   15
        .byte   79
        .byte   16
 .byte   80
        .byte   17
        .byte   81
        .byte 18
        .byte   82
        .byte   19
        .byte   83
 .byte   20
        .byte   84
        .byte   21
        .byte 85
        .byte   22
        .byte   86
        .byte   23
 .byte   87
        .byte   24
        .byte   88
        .byte 25
        .byte   89
        .byte   26
        .byte   90
 .byte   27
        .byte   91
        .byte   28
        .byte 92
        .byte   29
        .byte   93
        .byte   30
 .byte   94
        .byte   31
        .byte   95
foo:
 vmovdqa64       zmm2, zmmword ptr [rip + .LCPI0_0]
        kmovd   k0, edi
        kmovd   k1, esi
        vpmovm2b        zmm0, k1
 vpmovm2b        zmm1, k0
        vpermi2b        zmm2, zmm1, zmm0
 vpmovb2m        k0, zmm2
        kmovq   rax, k0
 vzeroupper
        ret
```

On Zen 3 and before, it's a lot worse.

I believe it should compile like so, on machines that have a fast `pdep` instruction:

```asm
foo:
        movabs  rax, 6148914691236517205
        pdep    rcx, rdi, rax
        pdep    rax, rsi, rax
        lea     rax, [rax + 2*rcx]
 ret
```


</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyUmEuP4ygQxz8NuZQmMoWfhxz6MS21NKPd0xzm0sI2Sdj2IwMk_fj0K0hSTrJmdjdqdVD9i-JHUQYTaa3eDEqtWHbPsseF3LvtaFY_ZKdbaV4X9dh-rJ6hkQO8Ge0USKi1s87oYQN6cMp0Sh4UKGl19wGdflVgR4YPoAf4qTdM3LHkkSXn_3ly_PvUm6OlGQfrwLoWmHgElia6343GMSwZonUtQ2RYMXF_GUa9ex9YD7AeR4alZOIO9gL9uDW1K9jnKbDi1BUAwCi3N4MfptbuQVo_jnXt0uq-XR6nIxvFsFxO3ViaSOt50uSHatxoGJbHofbco-HDdTwZjN4-jes__zdOfYpDQVjxeDJRNorHm7xeZulu7ZSBced0rz-l0-Ng_SDfvv34DlYpC26rbWyBuu7QH02tWutBQWvHl25sZAfaZzVNjqnXAoFhloQlP7b9bCC4vuyHQfaqfZFta6aV-Do480EDg--DYflr7Rpp3TlQAm4EJh4EwjtozsTXix5irgf_XY809LDb_XrdqUNYgmvfABLW4dYqTtY89VaBwSwe_Kg08-Na-hYnkzi3SBMptaiRnVuTlp9bpIni3CJNlOcWaaI6t0hLiZC0lAg5iemET2pKjJzUlCA5qSlRclJTwuTT_IiTk5oSKCc1JVJO6lRinNSMSJHUjEiR1GxaB1IzIkVSMyJFUjMiRVIzIsVpoYgUSc2IFEnNiRRJzaeKITWfSobUXFxXdHb1DFB9nqs29U-DztNzD6Pc8eHFLPsvG8izg7dx37VQKxh0o0Cvw54BzdlqVDNuBv2pWpB2Og_84eC2KhwVnl0OLaheO5DHOLLbjEa7be8BZdOM_a7TdgtuK93ykuBhb4waXPcRMuDAe-pO2fNBA-MAn8NBmTS2j0l72saW3x7-fE5ekot95_hZ1h9OAUAyZ56Sd-3M5815Nm_Hk5n88nk_EQlbzNkjaHk5b4-g5dUt27xfMZsfgFm0IpKfCFqB8_ZbtCKSHx5jm00Rj8AVkQzxCF2R3-DxCF4xmyPwm-Vc7iJJ4hG8oor43-KVkSzxCF45mycewSsjWeIRvFLc4GEEr4zUOc7ilbEnMIJXRsodb_HKSJYwglfO5gkjeGUkSxjBq5Lb7EXwqkix4yxeFckSRvCqSMWLW7wqkiURwatOefIvmbRhH_rx0P6SeXpy_uz7cEh-9v3baFrYOQMsuzd6BwzvgXb87PF6kFcfx3-Hw1a1OiKHc1fZG_mw68dDjzVMFCHO63kqMw4h0mtyG0iZXl_5nafDT9_JZcgae0JMTg74T_Rf_p4j369GPHwqM-53O2Wu_Y1yvzn__xjgpxpAhPO7VuvRqOM5zLCwIKEb_QuCserqzH6GWnVaHZQ_sO02vCqczu3L--E4QC-brR7CRUQ62Pp7pIR1eJXJk12rdixPQA_WmX3jry__esZfVcvp048HWVtKSc7TsuJpXnEUecYLTG6eSD9uSE0T_E2rw5d8j7gdwxo779YpCRduvjrle6hOZHjnx6Di_P1aLNqVaCtRyYVa8QJLIQQvcLFd8bLMamwq2TYVL0SqskSpqqm5KPNUiHKhV5hgypOkwERghssib6o8z7J2nRdVUUuWJqqXulv6O99yNJuFtnavVpzzVIhFJ2vV2fADAeKg3iCo_l6ePS7Mynf6Uu83lqVJp62zUxinXRd-Wbj__uy94fnyBZF-R7C3VeLvcFQAdrE33Wrr3C7cVfGJ4dNGu-2-XjZjz_Ap3FSPX192ZvxLNY7hU4C0DJ9Oszis8O8AAAD__wjhP0w">