firstbithigh, firstbitlow, clz, ctz..

[RobinMorisset]

HLSL got two functions firstbithigh/firstbitlow
Metal got clz/ctz.
SPIRV does not appear to have any equivalent to those (unless I missed it).

firstbithigh/firstbitlow got some... interesting semantics.
In the documentation, firstbithigh supports both int/uint, and only has the comment "For a signed integer, the first significant bit is zero for a negative number."
Still in the documentation (https://docs.microsoft.com/en-us/windows/win32/direct3dhlsl/firstbitlow), firstbitlow supports exclusively int for scalars and exclusively uint for vectors and has no comment whatsoever about edge cases.

microsoft/DirectXShaderCompiler#169 says:

• The hlsl firstbitlow function returns the first bit set from the lsb. If no bit is set it returns -1.
• The hlsl firstbithigh function changes behavior depending on the sign. For unsigned values it returns the index of the first bit set from the msb. However, the index starts from the lsb. For signed values if the value is negative it returns the index of first 0 from the msb, otherwise it returns the index of the first 1. Again all indexes relative to the lsb. If no 1 is found (or 0 for signed) then -1 is returned.

In practice, Myles tested it (https://bugs.webkit.org/show_bug.cgi?id=199531#c5), and the results match what was described in the DXC issue (with both functions supporting both signed and unsigned integers). In particular, note that firsthighbit(-1) and firsthighbit(0) are both -1 !

We generally try to match the HLSL standard library, but this kind of semantics is a bit crazy. It is a footgun for implementers (note that DXC got it wrong in the beginning), as well as for users. For an example of the latter, note that one of the first results in Google of "HLSL firstbithigh" is the following blog post: https://wickedengine.net/2018/01/05/next-power-of-two-in-hlsl/, which claims "If it is signed int, then you don’t have to worry about it, as the firstbithigh function will return zero for negative numbers." (which we saw is just wrong).

I doubt that these functions are heavily used because they have no direct equivalent in SPIRV.
A search on GitHub found 1.3k uses, but most of them appear to be forks of the same few projects.

So I suggest only specifying/implementing clz/ctz from Metal with their sane semantics. Anyone who really needs firsthighbit can easily reimplement it from this, and it would be one less trap for implementers and users both.

[litherum]

1.3k uses

This sounds enough to be worth the implementation annoyance.

[RobinMorisset]

I've specified firstbithigh/firstbitlow as per HLSL/dxc behavior for now, but I am keeping this issue open because I really wish we could get rid of this wart.

[RobinMorisset]

I found the SPIR-V equivalent. It is not in the SPIR-V main specification but in the GLSL.std450 extension to SPIR-V: https://www.khronos.org/registry/spir-v/specs/unified1/GLSL.std.450.html

• FindILsb behaves like firstbitlow
• FindSMsb behaves like firstbithigh
• FindUMsb behaves like a sane version of firstbithigh (i.e. it does not treat negative numbers specially, and differentiates between 0 and -1).

This kills my hope that the behavior of firstbithigh is a crazy fluke that no one relies on. At least SPIR-V documents it.