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

    <tr>
        <th>Summary</th>
        <td>
            [AVX-512] Prefix-sum of a Vector of 8 u8's could be computed with `vpmullq`
        </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>
    [Godbolt link](https://zig.godbolt.org/z/YPTeo4csj)

Despite the title, I'm not entirely sure what's better between these two. I actually do not have a Zen 4 or equivalent Intel machine, so I have not done a speedtest. But, preferably, LLVM should take a side and pick whichever is better.

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

export fn prefix_sum1(v: @Vector(8, u8)) @Vector(8, u8) {
    var x = v;
    x += std.simd.shiftElementsRight(x, 1, 0);
    x += std.simd.shiftElementsRight(x, 2, 0);
    x += std.simd.shiftElementsRight(x, 4, 0);
    return x;
}

export fn prefix_sum2(v: @Vector(8, u8)) @Vector(8, u8) {
    return @bitCast(@as(u64, @bitCast(v)) *% 0x0101010101010101);
}
```

```asm
prefix_sum1:
 vpsllq  xmm1, xmm0, 8
        vpaddb  xmm0, xmm1, xmm0
        vpsllq xmm1, xmm0, 16
        vpaddb  xmm0, xmm1, xmm0
        vpsllq  xmm1, xmm0, 32
        vpaddb  xmm0, xmm1, xmm0
 ret

.LCPI1_0:
        .quad   72340172838076673
prefix_sum2:
 vpmullq xmm0, xmm0, qword ptr [rip + .LCPI1_0]{1to2}
 ret
```

The first one seems definitely better on those  Intel machines where `vpmullq` is much, much slower. It is also nice because it is not loading anything from memory. The second implementation loads from memory, but is only a single instruction, and the multiply itself takes 3 cycles on the most efficient hardware implementations.

I think the optimization is a lot more cut and dry when starting and ending in a general-purpose register (even on earlier architectures) [Godbolt link](https://zig.godbolt.org/z/v8G8cnhda):

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

export fn prefix_sum1(v: u64) u64 {
    var x: @Vector(8, u8) = @bitCast(v);
    x += std.simd.shiftElementsRight(x, 1, 0);
    x += std.simd.shiftElementsRight(x, 2, 0);
    x += std.simd.shiftElementsRight(x, 4, 0);
    return @bitCast(x);
}

export fn prefix_sum2(v: u64) u64 {
    return v *% 0x0101010101010101;
}

export fn prefix_sum3(v: u64) u64 {
 var x = v;
    x += x << 8;
    x += x << 16;
    x += x << 32;
 return x;
}
```

```asm
prefix_sum1:
        vmovq xmm0, rdi
        vpsllq  xmm1, xmm0, 8
        vpaddb  xmm0, xmm1, xmm0
        vpsllq  xmm1, xmm0, 16
        vpaddb  xmm0, xmm1, xmm0
        vpsllq  xmm1, xmm0, 32
        vpaddb  xmm0, xmm1, xmm0
        vmovq   rax, xmm0
        ret

prefix_sum2:
 movabs  rax, 72340172838076673
        imul    rax, rdi
 ret

prefix_sum3:
        movabs  rax, 72340172838076673
 imul    rax, rdi
        ret
```

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzcV11v2zYU_TX0y0UMibJs-cEPSbwUATqgGIpg20tBidcWG34o5JU_-usH0k5sp07SLsMwrA1Mh7z33MNL5hxJhKCWFnHGyitWzgeip9b52Z3QSgp_P6id3Ma1D07WThNoZe9ZOWe8aom6wIpLxm8Yv_mmlsPlLmbo_DLOMH7zx6fP6EZN-Mr4lGVzll3uPucYOkUI1CKQIo2MX8Mt4xMD1hGgJeVRbyH0HmHdCmJ8EqBGIvRxWCPamBwQaO2GcAuioV5ovQXpEkQrVggC_kQLI3Ae8KFXK6HREtxaQg1GNK2yqXBwcLtLiJnS2ZgZOkRJGGgIVz3FsM7jAr2o9Tb-9vHj3a8QWtdrCSTuU4qSCMJK6FRzD-tWNS2u0IN6pD487gEbZ7ufb2q5m2mcDQSBJLBiDmyUKdM5T4xXjPNAknEe-1hcHcPgJsbAwiZ-avMl9CZnvFqx4jJi3GFDzjNeVZF1X0UEPn1hBdhkDw4AsBIeNonL6qlonN8A41dxOpAcBmXkMLRqQb9oNGgp_KaWbSS9ibB5_MiOaf8sAn83wugsgkfqvYXNoZ-T-VuN5f9MY_el2SirFV2LkI54lInAeNWPE92TtdUjNr9kvIRsk-Wn_0-uxdM2Hi_Y2VsngtnNHF-bYh8Fqy5o_QCwMSad4MaYLI7VYRPphnRCyhqelk_Cn0UmwOd4-fidgN8hFvynET3ScYuGH68_3eZfskM39v-GD72QADDhxSjLJ7wqqmwyHk-K543kx400_X7j2THNh7XzEjrywMorr7p4neGpcjlnk6ucHH86zCOS5471c4uwUD4QRPUKiCaAxIWyiqKO7pXTRdF0AeFUAwOsW_QIbJzt6bJxFlXL9E0bycYRgnZr9EO4pbgkdHBgVYNQYyP6gKDSfFRQ7YRUdgnCbqmNXxbeGTBonN8OIVIN2DgrQZlu9_cqSDmb8sJxcKxd9wnXWb1NEmuXGkHZQL5vYlaMiZobrcT0mlSnt6AooF4kXQ5QQLNtNIbd9hGMCwS4WKhGRTtohZdr4fEZm3Ai1rcQd3Kf8l1HyqhvO86xFaAdgXEeoekpkZF-G3tqIZDwtOuFBLSpLcqCgCVa9EJfdL3v4ol4XKoQz4jxCldoI1kUXiv0IHzTKsKGeo8h6cDf9eNV9aFqbCtFEozLf9uOkrZN43DGaF6W1cf6zwTxf2tJJ1vdnNf2ty3qpWbvi6xecZOfKFe8Wu7NJ4i4eM2KaCyvr-fjNwIKfgh4xdrf4YmPhmLc6qDnXqof86X3Oud_0zpPegLgxeZ8wDOLPWuVxq1EHZ5AXnDZR0Rleg2HkodzeLFU8d1R_mDFF0t9t7nT2zWQs0JOi6kY4Cyf5FlVldV0NGhnOM6qnGfjqczzphktpqWoxKguJwXKXEynAzXjGR9lRT7lPBuVfFjWGa-mZcUlz0o-jk-LaITSQ61XJgr8QIXQ46wqqwkfaFGjDumVjnOLa0iLUa_L-cDPYs5F3S8DG2VaBQoHlPQyFhMv736_KPOYAJ9SBy9Cb8AtQMBOoeP3KunzJECTXoNqhMaZrieUsFbUnj5QDHqvZ6cmtVTU9vWwcYbxm8hhP1x03n3Fhhi_ScwD4zdpZ38FAAD__5jKOP8">