The context of this question is the creation of a side-channel resistant implementation of a IEEE-754 compliant single-precision square root for a 32-bit RISC-V platform without hardware support for floating-point arithmetic and without the Zbb extension for advanced bit manipulation. Integer multiplies, in particular the MUL and MULHU instructions, are supported by the hardware and can be assumed to have fixed latency. Counting the leading zero bits is required for normalization of subnormal operands, and the CLZ emulation should be branchless because of the side-channel resistant design.

I started with C99 code for a 32-bit leading-zero count that I used twenty years ago on ARMv4t processors. This is a full-range implementation, i.e. it returns 32 for an input of zero.

uint32_t cntlz (uint32_t a)
{ 
    uint32_t n = 0;
#if 0
    n = __builtin_clz (a);
#else
    n = !a + 1;
    if (a < 0x00010000u) { n |= 16;  a <<= 16; }
    if (a < 0x01000000u) { n |=  8;  a <<=  8; }
    if (a < 0x10000000u) { n |=  4;  a <<=  4; }
    if (a < 0x40000000u) { n +=  2;  a <<=  2; }
    n = n - (a >> 31);
#endif
    return n;
}

As a sanity check, I compiled the above source with clang 18.1 -marm -march=armv4t, resulting in the following code that, at 16 instruction without function return, uses one instruction more than the best ARMv4t implementation I am aware of (which uses 15 instructions without the function return):

cntlz:
        mov     r1, #1
        cmp     r0, #0
        moveq   r1, #2
        cmp     r0, #65536
        lsllo   r0, r0, #16
        orrlo   r1, r1, #16
        cmp     r0, #16777216
        lsllo   r0, r0, #8
        orrlo   r1, r1, #8
        cmp     r0, #268435456
        lsllo   r0, r0, #4
        orrlo   r1, r1, #4
        cmp     r0, #1073741824
        addlo   r1, r1, #2
        lsllo   r0, r0, #2
        add     r0, r1, r0, asr #31
        bx      lr

I am currently working without access to a RISC-V development platform and used Compiler Explorer to compile for a 32-bit RISC-V target. I could not figure out how to specify extensions properly to turn off floating-point support, so I used clang 18.1 with -march=rv32gc, which resulted in the following assembly code being generated:

cntlz:                                  # @cntlz
        seqz    a1, a0
        srli    a2, a0, 16
        seqz    a2, a2
        slli    a2, a2, 4
        or      a1, a1, a2
        sll     a0, a0, a2
        srli    a2, a0, 24
        seqz    a2, a2
        slli    a2, a2, 3
        or      a1, a1, a2
        sll     a0, a0, a2
        srli    a2, a0, 28
        seqz    a2, a2
        slli    a2, a2, 2
        or      a1, a1, a2
        sll     a0, a0, a2
        srli    a2, a0, 30
        seqz    a2, a2
        slli    a2, a2, 1
        or      a1, a1, a2
        sll     a0, a0, a2
        srai    a0, a0, 31
        add     a0, a0, a1
        addi    a0, a0, 1             
        ret

I am unable to identify any improvements to the code generated by Clang, that is, it appears to be as tight as possible. I am aware that RISC-V implementations could implement macro-op fusion. See: Christopher Celio, et al., “The Renewed Case for the Reduced Instruction Set Computer:
Avoiding ISA Bloat with Macro-Op Fusion for RISC-V”, UC Berkeley technical report EECS-2016-130. But none of the fusion idioms discussed in the report appear to apply to this code, leading me to assume an execution time of 24 cycles for this 24 instruction sequence (without the function return). I was curious what __builtin_clz() resolves to. Compiling with that code path enabled results in a 31-instruction sequence that converts the leading zeros into a left-justified mask of 1-bits and then applies a population count computation to the mask:

        srli    a1, a0, 1
        or      a0, a0, a1
        srli    a1, a0, 2
        or      a0, a0, a1
        srli    a1, a0, 4
        or      a0, a0, a1
        srli    a1, a0, 8
        or      a0, a0, a1
        srli    a1, a0, 16
        or      a0, a0, a1
        not     a0, a0          // a0 now left-aligned mask of 1-bits
        srli    a1, a0, 1
        lui     a2, 349525
        addi    a2, a2, 1365
        and     a1, a1, a2
        sub     a0, a0, a1
        lui     a1, 209715
        addi    a1, a1, 819
        and     a2, a0, a1
        srli    a0, a0, 2
        and     a0, a0, a1
        add     a0, a0, a2
        srli    a1, a0, 4
        add     a0, a0, a1
        lui     a1, 61681
        addi    a1, a1, -241
        and     a0, a0, a1
        lui     a1, 4112
        addi    a1, a1, 257
        mul     a0, a0, a1
        srli    a0, a0, 24
        ret

Again, I am not sure what instructions could be subject to macro-op fusion here, but the most likely candidate seems to be the LUI/ADDI idiom used to load 32-bit immediate data, similar to the way modern ARM processors fuse MOVW/MOVT pairs. With that assumption, the code would still appear to be slower than what I currently have. I tried half a dozen additional integer-based variants of 32-bit CLZ emulation and did not find any that resulted in fewer than 24 instructions. I also searched the internet and was unable to find anything superior to my current code.

Are there any branchless full-range implementations of leading-zero count for 32-bit RISC-V platforms that require fewer than 24 cycles? Conservatively, I want to assume the absence of macro-op fusion as this seems like an expensive feature in a low-end microcontroller, but answers relying on macro-op fusion as present in existing RISC-V implementations are also welcome.