Suboptimal code generation for __builtin_ctz(ll)

[gcp]

Bugzilla Link	34843
Version	5.0
OS	Linux
CC	@topperc,@RKSimon,@rotateright

Extended Description

Right now, when no specific arch target is set, the builtin

__builtin_ctz (and long, long long variants)

will generate a bsf instruction.

This is suboptimal for AMD machines, which can do a TZCNT much faster than they can do a BSF. Due to the way TZCNT is encoded, it is equal to a REP BSF, so it is in fact "backwards compatible" as long as the different behavior for a 0 is fine. And it is, because __builtin_ctz has undefined behavior for 0 (which is why it can use BSF in the first place).

On Intel hardware, either way is equally fast, so for a generic target it makes sense to deal with the AMD case and encode the intrinsic as REP BSF/TZNCT.

At least GCC 4.8 and later are able to do this optimization and generate a REP BSF for their generic target. Clang fails to do so. (It does generate TZCNT with -march=znver1)

Example snippet:
https://godbolt.org/g/eXU6xf

Of note in this snippet is also that newer GCC adds a XOR ESI, ESI before the REP BSF. So there may be a false dependency issue in some CPUs.

[gcp]

The false dependency was fixed in GCC here: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62011

Despite the bug talking about popcount, the patch from an Intel engineer also addressed CTZ, and the patch applies for Sandy Bridge and Haswell micro-architectures (and the generic target).

I checked and with -march=haswell Clang seems to generate a tzcnt without the false dependency elimination. So there's a 2nd optimization opportunity here.

[rotateright]

There's discussion about the popcnt hardware bug and possible work-arounds in #33216.

[topperc]

mentioned in issue llvm/llvm-bugzilla-archive#36881

[RKSimon]

Candidate Patch: https://reviews.llvm.org/D130956

[nickdesaulniers]

/cherry-pick c2066d1

[llvmbot]

/branch llvm/llvm-project-release-prs/issue34191

[llvmbot]

/pull-request llvm/llvm-project-release-prs#55

[nickdesaulniers]

sounds like this was reverted in 84e9194

[aaronpuchert]

[...] __builtin_ctz has undefined behavior for 0 (which is why it can use BSF in the first place).

Turns out that's not quite the case. GCC docs simply state that "the result is undefined" instead of the "the behavior/program is undefined". As long as you're not using the result in the problematic case you're fine. Similarly llvm.cttz.* is specified to return poison for zero input.

The bsf instruction similarly leaves the destination operand undefined, but still sets ZF to indicate zero input. One might want to use this flag to overwrite the undefined result in the zero input case. But here it gets tricky, because tzcnt sets CF instead, so if we always emit tzcnt without knowing the machine that will run the code, we don't know which flag to look at.

[nickdesaulniers]

Given the risk of the first landing, I'm content to let this ride the release trains out to clang-16. Thanks again for the patch and fix, @phoebewang !

[tstellar]

I've dropped this from the 15.0.0 milestone. It can always be re-added we change our minds.