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

    <tr>
        <th>Summary</th>
        <td>
            prefix-xor should be optimized to carryless multiply
        </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>
    In [this article](https://validark.github.io/mask_even_odd_bits.html#prefix-xor) I explain the prefix-xor operation and explain how it can be computed with a carryless multiply.

Basically, I would like to see LLVM recognize this pattern:

```zig
fn prefixXOR(bitstring: u64) u64 {
    var x = bitstring;
    x ^= x << 1;
    x ^= x << 2;
    x ^= x << 4;
    x ^= x << 8;
    x ^= x << 16;
    x ^= x << 32;
    return x;
}
```

and possibly:

```zig
fn prefixXOR(bitstring: u64) u64 {
    var x = bitstring;
    inline for (1..64) |i| { // i ∈ [1, 63]
        x ^= bitstring << i;
    }
    return x;
}
```

And convert it to a carryless multiply:

```zig
fn prefixXOR(bitmask: u64) u64 {
    const all_ones: u64 = @bitCast(@as(i64, -1));
    return @mulCarryless(bitmask, all_ones);
}
```

I believe it would look like so in x86-64 assembly:

```asm
prefixXOR:
        vmovq   xmm0, rdi
        vpcmpeqd        xmm1, xmm1, xmm1
        vpclmulqdq      xmm0, xmm1, xmm0, 0
        vmovq   rax, xmm0
        ret
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzEVU1v4kgQ_TXFpRRktw02Bx8SGKRIs1ppD6O9RW27gmvTH053m0B-_aoNIcBGQZrLShbGXa--XtdTSe95Y4gqmD3AbDWRQ-isq35Jxa10L5Patvvq0SDMHkLHHqUL3CiC2QpE2YXQe8juQaxBrLdHn-mGQzfUU7Yg1lr6lyfaknmybftUc_DTLmgFIusdPfPubmcdiAU-Iu16Jdlg6Ag_bWh7cjKwNShNewJ19g05YCMN1oSN1f0QqMU3Dh1KbKRze0Xeox5U4F7tp5CsILk__D5Iz41Uag9iiY_4ZgfVouIXwmDRE-HPn7_-QEeN3Rh-Jxwb72UI5Ezs9iwUzJPD886bw8mzOVb_959_gShjx8Gx2UB2j8M8j70O8xyheDjgERG30uEOIVvhGfzMvkOY_YjmCFpCtsT0hl3csOc37OWt_PMbgOyyAkdhcAZ3p0MoVlcMntMar7q33nOt9v8L42wUG8Jn6xBEmU6nhzhQLBmKZYyFh6FHRvghoCyhLKNI0jhT8yzq4xTsgqFTvg-m-CLxiZffYO3etNhYsyUXojiC_VIKv8FnFPF3bDbW-IBSqSdryB-RI7uQJzWHpfQBRAl5Ij2IkmOYJd6lIBbx-WJQIE_0oJYfxZ-VIZafic58v2fmEWtSTFuKvBz1bu3LQfTeIhvclfO7eY7Se9LfTJ30-nDySdEH8uOqt9puX-OVa53Ecl3LV4C-0T29tqfZ0Hocm4v3tYfSg3ptX08eyZXH-J18XYmTuxPqAuAoXPU3aausXWQLOaEqLZI8LRYzkU-6qk5zmou2bMVzkRUyb_JikeaLlKQUVFA64UokIk_SRCRFKpJ8Wkoh4r-6XGRtQw3kCWnJaqrUVk-t20zY-4GqYl4k6UTJmpQf15AQht5wNIIQcSu5Kvrc1cPGQ54o9sF_RgkcFFVnK8N34w3XhLYPrPmd2iiG_0phMjhVXS6x4-5qrAaxjimOr7ve2X-oCSDWY2EexHos_N8AAAD__3GgDDw">