无分支代码中的分支

# 无分支代码中的分支 来源：https://00f.net/2026/10/09/llvm-compiles-branch-free-code-into-branches-on-risc-v/ ## 让我们来加两个数 这是一个完整的 C 函数，用于将两个无符号 128 位整数相加： ``` typedef unsigned _BitInt(128) u128; u128 add(u128 a, u128 b) { return a + b; } ``` 现在让我们把它编译到 32 位 RISC-V 上： ``` clang --target=riscv32 -march=rv32imac -mabi=ilp32 -O2 -S add.c -o - ``` 你可以在 Compiler Explorer (https://godbolt.org/z/z97rT71ds) 上看到输出结果，旁边还有用 GCC 和我们下面会讨论的 Zicond 扩展编译的版本。以下是相关的片段： ``` add a1, t1, t0 add a2, a7, t2 sltu t0, a1, t1 add a2, a2, t0 beq a2, a7, .LBB0_2 sltu t0, a2, a7 .LBB0_2: add a5, a5, a3 add a4, a4, a6 add t0, t0, a5 sltu a3, a5, a3 sltu a5, t0, a5 ``` 等等，为什么一个加法里会有 `beq`？那是一个条件分支，对吧？RV32 的寄存器只能容纳 32 位，所以 LLVM 必须把我们的 128 位加法拆分成四个较小的加法，将进位从一个传递到下一个。编译后的代码就是这样执行加法的；`a0` 和 `b0` 是我们输入的最低 32 位字，`a1` 和 `b1` 是接下来的 32 位。所有值都是无符号的，`low32()` 只保留最低 32 位，比较结果返回 0 或 1。 ``` sum0 = low32(a0 + b0) carry0 = (sum0 < a0) sum1 = low32(a1 + b1 + carry0) if sum1 == b1: carry1 = carry0 else: carry1 = (sum1 < b1) ``` 你能猜到为什么检查 `sum1 == b1` 吗？像 x86 和 AArch64 这样的 CPU 有条件移动指令（`cmov`），允许在没有分支的情况下实现进位传播。但在 RV32 上，即使比较两个 64 位整数的 `<` 也会产生分支。 ## 那通常用的位掩码呢？ 我们一直在讨论大整数中的进位传播，但如果你写过常数时间代码，你可能到处都在用某种版本的这个： ```c #include <stdint.h> uint32_t ct_select(uint32_t bit, uint32_t a, uint32_t b) { uint32_t mask = -(bit & 1); return (a & mask) | (b & ~mask); } ``` 如果 `bit` 的最低位被置位，`mask` 就全是 1，所以该表达式保留 `a` 并将 `b` 清零。否则，掩码为零，我们就得到 `b`。全是位运算，源代码中没有分支。 让我们用 clang 23 把它编译到 RV32 上： ``` ct_select: andi a0, a0, 1 beqz a0, .LBB0_2 mv a2, a1 .LBB0_2: mv a0, a2 ret ``` 啊啊啊啊啊，一条 `beqz` 指令，对刚才用位运算精心选择的那一位进行分支。精心用位运算写选择逻辑到头来全是白费。而且这在 64 位 RISC-V 上也会发生。你可以在 Compiler Explorer (https://godbolt.org/z/zq7nnWonn) 上看到编译后的代码，其中包含了两个目标架构，以及 clang 17、GCC 和 Zicond 作为对比。 为什么要包含 clang 17？因为这个分支在 15 中存在，16 和 17 中消失了，又从 18 回到了 23。很有趣，是吧？ 所以，即使用某个特定版本的编译器审查过汇编代码，一切看起来都没问题，编译器版本或编译标志的任何更改都需要重新审查。 ## Zig 呢？ 让我们试试在 Zig 中做 128 位加法，以及同样的位掩码选择： ```zig export fn add(a: *const u128, b: *const u128, r: *u128) void { r.* = a.* +% b.*; } ``` ```zig export fn ctSelect(bit: u32, a: u32, b: u32) u32 { const mask = 0 -% (bit & 1); return (a & mask) | (b & ~mask); } ``` ``` zig build-obj add.zig -target riscv32-freestanding -O ReleaseFast -femit-asm=add.s -fno-emit-bin ``` 第二个字之后同样出现了 `beq`，选择函数也得到了同样的 `beqz`（Compiler Explorer 代码 (https://godbolt.org/z/9jrqdvPjo)）。更换源语言并不能让我们摆脱这个问题。而且是的，Rust 也有同样的问题。 ## 其他平台呢？ 现在让我们把 C 示例编译到其他几个目标上。我还加了一个 64 位的 `a < b` 比较，因为在 RV32 上它就足以产生分支。以下是 clang 23 在 `-O2` 下产生的条件分支和条件返回的数量。一如既往，所有内容都可以在 Compiler Explorer (https://godbolt.org/z/9Ys7Tovfz) 上验证： | 目标 | `add` | `ct_select` | 64 位 `<` | |---|---|---|---| | x86_64, x86 | 0 | 0 | 0 | | AArch64, 32 位 ARM, Cortex-M3 | 0 | 0 | 0 | | MIPS32, LoongArch64, WebAssembly | 0 | 0 | 0 | | Cortex-M0 | 0 | 1 | 1 | | 32 位 PowerPC | 0 | 1 | 2 | | RV32 | 1 | 1 | 1 | | RV64 | 0 | 1 | 0 | | 带 Zicond 的 RV32 和 RV64 | 0 | 0 | 0 | 目标为零的是安全的。其他的都有丑陋的侧信道，尽管源代码看起来像是在常数时间运行。WebAssembly 有一条 `select`（`cmov`）指令，所以在模块中看不到明显的条件跳转，但 WebAssembly 编译器可以为所欲为。在没有等效原生指令的平台上，我们很可能得到一个跳转。Cortex-M0（Thumb-1）和通用 32 位 PowerPC 没有类似 `cmov` 的指令，所以它们会分支。 ## 让我们试试 GCC 现在有一个令人愉快的发现：GCC 16.1 在 RISC-V 上编译这两个示例都没有产生分支。它的进位使用 `sltu`，并且放过了掩码的算术运算。很酷。 但让我们做一个小改动：从比较结果推导掩码。 ```c uint32_t m = -(uint32_t)(x < y); return (a & m) | (b & ~m); ``` 然后……分支回来了！GCC 现在在 RV32 和 RV64 上都发出一条 `bgeu`（Compiler Explorer (https://godbolt.org/z/65P3eWeTr)）。它在 RV32 上的 64 位比较也会分支。 ## 我们能对优化器隐藏掩码吗？ 对于位掩码示例，有一个常见的变通方法：在使用掩码之前，先让它通过一个空的 `asm` 语句。让我们试试： ```c uint32_t ct_select(uint32_t bit, uint32_t a, uint32_t b) { uint32_t mask = -(bit & 1); __asm__("" : "+r"(mask)); return (a & mask) | (b & ~mask); } ``` 这个汇编什么也不做，但它的声明告诉编译器它可能会改变 `mask`。现在，两个版本在 RV32 和 RV64 上都没有产生分支。呼。 我们能对加法做同样的事吗？我试着把输入藏在内存屏障后面，但分支还在。但是对*每个* 32 位字加上寄存器屏障就可以了，每个进位都变成了 `sltu`。两次尝试都在 Compiler Explorer (https://godbolt.org/z/KWj99rshe) 上。 说实话，我不会依赖这两种屏障实验作为加法的修复方案。对于涉及密钥的算术运算，我会避免使用超过两个寄存器宽度的整数类型，并在 RV32 上用 32 位字显式编写进位链。目前，clang 23 保持了我手写的进位链没有分支，但谁知道下一个版本会发生什么。 ## 给 LLVM 补上缺失的指令 不过对于 RISC-V，有一个解决方案：RISC-V 有一个叫 `Zicond` 的扩展。它添加了 `czero.eqz` 和 `czero.nez`，它们根据另一个寄存器是否为零来将寄存器清零。这可以用来在没有分支的情况下选择值。 让我们用 `-march=rv32imac_zicond` 启用它，然后重新编译我们的位掩码示例： ``` ct_select: andi a0, a0, 1 czero.eqz a1, a1, a0 czero.nez a0, a2, a0 or a0, a0, a1 ret `` 耶，没有跳转。上面测试的所有情况在启用 Zicond 后都没有分支。 Zicond 是 RVA23 profile 的一部分，但不幸的是，目前使用的许多核心并没有实现它，尤其是微控制器。而且即使它可用，还有一个容易忽略的重要细节：Zicond 规范 (https://docs.riscv.org/reference/isa/unpriv/zicond.html) 只有在同时也实现了 `Zkt` 扩展的情况下，才保证其时序与数据无关。 编写安全、可移植的代码很难。防御侧信道和清零密钥一样容易踩坑。 哦，如果你还没读过的话，Thomas Pornin 的[为什么需要常数时间加密？](https://www.bearssl.org/constanttime.html)和[常数时间乘法](https://www.bearssl.org/ctmul.html)页面绝对值得一读。