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

    <tr>
        <th>Summary</th>
        <td>
            Suboptimal codegen for `llvm.ctlz` on x86_64 (no BMI1)
        </td>
    </tr>

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

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

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

<pre>
    ## Summary

Intel has changed it's documentation of it's `bsf` instruction implementation to match AMD's. Intel's `bsf` is now documented to leave the destination register unchanged if the input is zero. This allows a significant performance optimization to `llvm.ctlz.{i16,i32,i64}` that LLVM currently doesn't do. (See "Legality of the optimization" for further caveats.)

## Background

`llvm.ctlz.*` relies on the `bsf` instruction on x86 if BMI1 isn't known to be available. It uses `rep bsf` so that CPUs that do support `tzcnt` execute it as `tzcnt` (as the representation is the same), however just in case the target executes it as `bsf`, LLVM generates a branch to handle the case where the input is zero, as unlike `tzcnt`, `bsf` has different behavior for the case where the input is zero.

## What LLVM currently does

[Here's the Godbolt link demonstrating what follows. It's in Rust; hope that's okay.](https://godbolt.org/z/35eov4q5v)

It tests if the input is zero, then branches.

```asm
tzcnt_u64:
        test    rdi, rdi
        je .LBB2_1
        rep       bsf rax, rdi
        ret
.LBB2_1:
        mov eax, 64
        ret
```

(Similarly for i32, but for i16 LLVM uses a different trick to improve `llvm.ctlz.i16` at the moment. That trick _could_ be used for 32-bit integers on 64-bit platforms too, I think? Not sure. You can see it occur in the generated assembly for `tzcnt_u16` in the Godbolt link above.)

## The optimized version

If and only if `bsf` leaves the desination register unchanged, then the following implementation of `llvm.ctlz.i64` is valid:

```asm
tzcnt_u64:
        mov     eax, 64
 rep       bsf rax, rdi
        ret
```

This is for 64-bit integers. The same can be applied for 32-bit integers and 16-bit integers.

## Legality of the optimization

Of course, if `rep bsf` is run as `tzcnt` then `tzcnt` will write the operand size into the destination register making the `mov` redundant.

The necessary behavior is that `bsf`/`rep bsf` leaves the destination register unchanged.

On x86, it's generally assumed that the destination of the `bsf` instruction is undefined when the input is zero. There are quite a few manufacturers of x86 chips, so it's tougher to make the case that the above holds. So I'm solely focusing on x86_64.

AMD64 implements the desired behavior: https://www.amd.com/content/dam/amd/en/documents/processor-tech-docs/programmer-references/24594.pdf

> If the second operand contains 0, the instruction sets ZF to 1 and does not change the contents of the destination register.

Intel used to document the destination register's contents as undefined (but implemented it in the same way as AMD), but it has decided to commit to the same behavior relatively recently: https://cdrdv2.intel.com/v1/dl/getContent/671110

> If the content of the source operand is zero, the destination operand is unmodified. [Footnote: On some older processors, use of a 32-bit operand size may clear the upper 32 bits of a 64-bit destination while leaving the lower 32 bits unmodified.] 

The detail in the footnote does not prevent the optimization (the value 32 will not be overwritten) but I'm including it for completeness.

The only other implementation of x86_64 that I'm aware of is the VIA's Nanos (2008-2015). I can't find an instruction set reference for them. I don't know whether they're relevant, or whether they can be safety excluded as possibilities from certain x86_64 target triples. **This is the crux of the matter, I believe.** I don't know if it's reasonable for LLVM to bother trying to cater to an ISA that requires signing an NDA to get manuals for according to https://forum.osdev.org/viewtopic.php?t=26351 and MIGHT have an implementation that doesn't conform to AMD64 or Intel64 - who knows what they're doing - they probably maintain compilers that work for their implementation anyway.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJyMWFtz2zjS_TXwS5dZEnSx9KAHOf4046pk8tU6O1u7Ly4QaIqIQYABQCryr99qgNTFjmdHlYpMEJdGn9OnuyVC0HuLuGGLe7Z4uBFdrJ3fPO3ulRd7Z29Kp44bxmeMz-Cpaxrhj2yyZZPto41ooBYBZC3sHhXoyPhdAOVk16CNImpnwVXjOFtOylCx5QS0DdF3Mr3XTWvwPD06aESUNWy_PNCqAtI5bzcIYN3hdBIqWmdQ9AixRlAYorZ5Q497HSJ66OzJzirN0rbtIm31it4V8K3WAYQx7hBAAHlFV1oKG6FFXznfCCsRXBt1o19PxrLlxJi-KWQ0rwW7u9fTJeOf9IzT_8s5u3sge2MtInz-_OcXkJ33aKM5gnIYLON3EZQrgPHVEyIwzj_jXhgdj-Q5MvPyRMY5VM5D1flYowcpehQxFIyvMygDUPdCvuy966wahq-s5PQMHo3GAHSNGj8Ax1n4uVqSw-6_PE5BDwa_WHdIty8RRC-0EaXBAh4jdAETTh5bGPYLLl__0___M-S_lIPQta3zkabGV2kjTcSfKLuIoCOIcPWG8ZUIyUyPrcdwYovOo0E0SC7gn6B2B-zRw_cuRNAWpAiZE1H4PcbxkHA-JZtJaxNAe7ToBc0QUHphZU0XrYVVJm-UdjzU6PE9i2gXEaCzRr_g5RXoxdnFFDRKVxUSFaDEWvSaUHX-f55QXOH8rw94NUxa3P-OHlPs0Ea_OVU6E8Fo-wIKG0dIi6jtHg60UeUS-wnItEZb-EcXIpvdQ-1aTOClF-5FHAu2eGB8VcfYBjbbMr5jfLfPJxTO7xnfvTK-my3Q9fMfi_5E0ccIEUMMvwxD8lOs0Q6ux1CcCJz_idCwyTa59blbzunkyRaGD-1L315p2oi-zi-_IxSf7-_58_RikHiaP2WowIuf79d5jGyyHZdende4HjCvWc7fLTnZPEK2etKNNsKbY4I6iwSUXcyP02WGMsWQuCBI9Fq-EAt103rX47XokOIsJyBi8mbjSBBJzcS48Fm6zqhnCtYuoEqHzfhtqSlAIu7RJxVYztNQa0QktQsQXYLjEWKt7Qub7eAPFyF0Hgv4t-tACgsBU7w6KTtPfCETxghSIELAphyuO0bDc5cNHmZfkVKUrsd3avbtrIKooEcfSAozmSoQVoGz5kh8OodYSgZhzAYfJ4MT4WhmDgCKhzdZyVVvfL6cD2moF0arzIq_TVOiDX2uqPO3mfiGVilt6ZBcPEA4olokz5E4JqxIrNvW6A8oQH6cLq83uILhLxNTmvi1Auk6H5Bsz3BcJAIdwHf2rbYn518OHLQxcPA64nAKejIt6FfSiug-zvCNeCHshnTWuD6nOdVZJWwsRn8hWJQYgvDHs_bqITddJITdtfnXjPqL-mI46GvKnckTWTVzXBhzpLjoGipa6iFqLzccvPtBtUTJRWGlLSpKEfbXlQylDuERfnTkRgEVHqARtquEjJ1PAV-lzC5r3QayMbjRzOi6PdUWqRJ7uch5J2tTlELtjAoFPDl4ZPyugeAMplCXXSAYcu3wvJwP_th-eVjOz4F1jk2P6oQDm23hOqUcDodCNKqQrmF8J52NaCPjOyXoWTSK8R1aGhiKwcD4rvWOEHb-NqKsb5WTw-jei6ZBf-sxaatEGufzxXpetKoa6D77P3jMIASUjuRl4CCdLrQNMBlk4wqbgDHAf3bkuGmKJsrEYF0cCuTsyXyBMML8KyoVlwV2kuzoTrXuh6sSeKftxSVRGF9Rljn5PtXqowAnfTgIYmUuutdjVtIxVyootcpGSNc0OsIQhGnlKYI8GhF1TxzwKFMt8h5NqbzqeUECYwZI-ymBZ6h6wPjphO_ybjqdTt4hMlxwdF9wnZdnkbiuIq7D6jyls41TutKoCmCL-51z0bqIZO1XC8E1CM4o9HCiUQqRLiAdK0blvFKmRhxBGhS5guvaFklhodQZajFq86VJh1obTLoyypZxh4t1F3ayxQOc9UthFNqMAFaD_We-tR77kSpXDQvjKxrrhemQjklaSytKBNejJ9mNFE3rRIAc2NpK06mUFXOlIh0RKaLFEC5UNSVhl_qS9-kzS0HWkLytOJBCUXuYpeDPx22i8B_CukCW8slkdcsn0wXj6wIeKYel7qPSVoGwb2MPTjE9FtINrVLu3LOQYib7Yo1Hxu88NRQGe0GM-wTOX00Yk2YQFcYj4E9yQ6pqoHUh6FIbHamFqrxrQKInbThdNLcb0evWYKD-bsv4KVknJvvu50jjRsQUwVRtldSXpSqIVry9gT610x5FcJY6r3TfVDpSS5YRiP6YSOVAipjVXFh4fNpmCDz-6LTHkPtcu6eXfzxsaRqZTblCmFxUCCmdV8Nm19FcOd81hQsK-6Hk7zUeomu1LNq6ZbNdZLMHvpwtsiB-efzt929QU5su3nf-uTUcm2LpLJWhdGjOHM7nnwKWc7iFQ-2SP0LuXM54KkeW3mYAW-9KQfVnI3RS7kRdbSgBpuMOzr-MbNHvaCvs8SCOxY3azNR6thY3uJnezZZ8tZ7OFjf1ZjGbllW5WPNqeifWqzlfi5Iv6HlRrZVY3egNn_DFZDq543zGp4tivVys5ELOxeJuNZtxweYTbIQ2RSotnd_f6BA63Ew5n0zmN0aUaEL6aYZziwdIbxnnbPFw4ze06Lbs9oHNJ0aHGM7bRB0Nbp66MoW_MCCdwj3asRI_lbJUYJwyNUWddanXZ3x903mzedPf6Vh35SDctMfwddt69x0l6XYykbLqcId-w_8bAAD__18ZHzI">