无Zbb扩展的32位RISC-V无分支全范围前导零计数优化问询

需求背景 #

为无浮点硬件支持、无高级位操作Zbb扩展的32位RISC-V平台，实现符合IEEE-754标准的抗侧信道单精度平方根。硬件支持整数乘法指令（MUL、MULHU）且延迟固定。对非规格化操作数进行归一化时需前导零计数（CLZ），因抗侧信道设计要求CLZ实现为无分支类型。

初始ARMv4t移植实现 #

最初使用20年前ARMv4t平台的32位全范围CLZ实现（输入为0时返回32），C99代码如下：

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;
}

ARMv4t编译验证 #

用Clang 18.1以-marm -march=armv4t编译，生成16条无返回指令的代码，比已知最优ARMv4t实现多1条指令：

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

RISC-V编译结果对比 #

因无RISC-V开发平台，使用Compiler Explorer以Clang 18.1的-march=rv32gc编译初始代码，生成24条无返回指令的汇编代码：

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

该代码无微指令融合适用场景（参考Christopher Celio等人的技术报告*"The Renewed Case for the Reduced Instruction Set Computer: Avoiding ISA Bloat with Macro-Op Fusion for RISC-V"*），预计执行24周期。

启用__builtin_clz()生成的代码更慢，包含31条指令：

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

核心问询 #

尝试多种CLZ变体均未得到少于24条指令的实现，网络搜索也未找到更优方案。现正式询问：
是否存在针对32位RISC-V平台的无分支全范围前导零计数实现，其执行周期少于24？保守假设无微指令融合（低端微控制器通常无此特性），也接受基于现有RISC-V微指令融合的方案。

注意： 查表法不适用，因缓存缺失易被利用进行侧信道攻击。

2024年6月9日更新：22指令变体实现 #

经研究找到可将指令数从24减至22的变体，但部分编译器无法生成期望代码。核心思路是利用RISC-V ISA的SET类指令特性，将正操作数转换为负数以直接使用“小于”比较，避免每次比较的反转操作。对应的可移植C++11代码及注释如下：

// Only applies right shift to non-negative values to avoid implementation-defined behavior
int32_t sra (int32_t x, int32_t y)
{
     return (x < 0) ? (~(~x >> y)) : (x >> y);
}

uint32_t cntlz_rv32 (uint32_t a)
{
    uint32_t n, t;
    int32_t as;
    n = !a;                                           // 1: seqz
    t = ((a >> 16)!=0)*16; n = n - t; a = a >> t;     // 5: srli, snez, slli, sub, srl
    as = (int32_t)(~a);                               // 1: not
    t = (as < -256) * 8; n = n - t; as = sra (as, t); // 4: slti, slli, sub, sra
    t = (as <  -16) * 4; n = n - t; as = sra (as, t); // 4: slti, slli, sub, sra
    t = (as <   -4) * 2; n = n - t; as = sra (as, t); // 4: slti, slli, sub, sra
    t = (as <   -2) * 1; n = n - t;                   // 2: slti, sub
    n += 31;                                          // 1: addi
    return n;                                         // 22 instructions total w/o ret
}

编译结果差异 #

使用GCC 13.3可生成22条无返回指令的无分支代码：

cntlz_rv32(unsigned int):
        srli    a3,a0,16
        snez    a3,a3
        slli    a3,a3,4
        srl     a4,a0,a3
        not     a4,a4
        slti    a1,a4,-256
        slli    a1,a1,3
        sra     a4,a4,a1
        slti    a2,a4,-16
        slli    a2,a2,2
        seqz    a5,a0
        addi    a5,a5,31
        sra     a0,a4,a2
        slti    a4,a0,-4
        sub     a5,a5,a3
        slli    a4,a4,1
        sub     a5,a5,a1
        sub     a5,a5,a2
        sra     a0,a0,a4
        sub     a5,a5,a4
        slti    a0,a0,-2
        sub     a0,a5,a0
        ret

但GCC 14.1无法生成预期的SLTI与-256组合的指令，Clang 18.1则生成33条指令的低效代码。

内容的提问来源于stack exchange，提问作者njuffa