Destination register for x86 bsf and bsr should always be initialized

[CatsAreFluffy]

The x86 instructions bsf and bsr (which are used to implement countl_zero and countr_zero respectively on targets not supporting BMI1) have a dependency on their output register. Currently, LLVM does not do anything to break this dependency, which can lead to strange slowdowns depending on the whims of register allocation. For example, in this Rust program, on the baseline target "New isqrt" is much slower than "Stdlib isqrt", while on a modern target "New isqrt" is much faster than "Stdlib isqrt", since on the baseline target "New isqrt" has a damaging bsr-induced dependency. This dependency should be broken by initializing the output register before bsr or bsf. (LLVM already does this on 64-bit targets when the argument is not known to be nonzero as of #123623, but the dependency still exists even in other cases.)

[llvmbot]

@llvm/issue-subscribers-backend-x86

Author: None (CatsAreFluffy)

The x86 instructions `bsf` and `bsr` (which are used to implement `countl_zero` and `countr_zero` respectively on targets not supporting BMI1) have a dependency on their output register. Currently, LLVM does not do anything to break this dependency, which can lead to strange slowdowns depending on the whims of register allocation. For example, in [this Rust program](https://godbolt.org/z/45axenMjd), on the baseline target "New isqrt" is much slower than "Stdlib isqrt", while on a modern target "New isqrt" is much faster than "Stdlib isqrt", since on the baseline target "New isqrt" has a damaging `bsr`-induced dependency. This dependency should be broken by initializing the output register before `bsr` or `bsf`. (LLVM already does this on 64-bit targets when the argument is not known to be nonzero as of #123623, but the dependency still exists even in other cases.)

[RKSimon]

Are there CPUs that are affected worse by this?

[tgross35]

Are there CPUs that are affected worse by this?

rust-lang/rust#137786 (comment) has one such example. The missed optimization described here may not account for the entire difference between the two benchmarks though.

[nikic]

We generate rep bsf (aka tzcnt) instead of bsf for trailing zeroes to avoid this dependency. Is there any reason why we don't use rep bsr (aka lzcnt) for the leading zeroes case? I see GCC doesn't do it in the bsr case either, so maybe there's some difference between these instructions I'm missing.

[phoebewang]

Yes, bsr and lzcnt are totally different. When SRC is 0, BSR set ZF, while LZCNT set CF. When SRC is non-0, BSR return the index of MSB, which LZCNT return OperandSize - Index.

[nikic]

Thanks, I didn't realize that the return value between bsr and lzcnt is inverted.