为什么 rv32gc 针对 RISC-V 优化带有分支的无分支代码？

Question

让我们尝试定义一个返回两个值 x 和 y 中的最大值的函数。这些公式有效的充分条件是，对于有符号整数，\xe2\x80\x932^30 <= x, y <= 2^30 \xe2\x80\x93 1，对于无符号整数，0 <= x, y <= 2^31 \xe2\x80\x93 1（即，只需要处理有效减少一位的缩小整数范围）。最通用（且最简单）的实现是：

\n

int max(int x, int y) {\n    return (x > y) ? x : y\n}\n

\n

在 Pentium Pro 之前，这将是 x86 中生成的程序集：

\n

max:  # GCC -O3 -march=pentium -m32\n  mov eax, DWORD PTR [esp+8]\n  cmp eax, DWORD PTR [esp+4]\n  jge .L4\n  mov eax, DWORD PTR [esp+4]\n.L4:\n  ret\n

\n

但从 Pentium Pro 开始，CMOVcc r32,r/m引入了一条新指令，它根据某些指定的状态标志执行条件移动：

\n

\n

CMOVcc 指令检查 EFLAGS 寄存器（CF、OF、PF、SF 和 ZF）中一个或多个状态标志的状态，并在标志处于指定状态（或条件）时执行移动操作。条件代码 (cc) 与每条指令相关联，以指示正在测试的条件。如果不满足条件，则不执行移动，并继续执行 CMOVcc 指令之后的指令。这些指令可以将 16 位或\n32 位值从内存移动到通用寄存器，或从一个通用寄存器移动到另一个通用寄存器。不支持 8 位寄存器操作数的条件移动。术语“更少”和“更大”用于有符号整数的比较，术语“上方”和“下方”用于无符号整数。

\n

\n

这允许创建无分支最大函数（如果您不知道为什么无分支实现通常是一件好事，您可能需要阅读一些有关指令流水线的内容）：

\n

max:  # GCC -O3 -march=pentiumpro -m32\n  mov edx, DWORD PTR [esp+4]\n  mov eax, DWORD PTR [esp+8]\n  cmp eax, edx\n  cmovl eax, edx\n  ret\n

\n

根据 x86-64 的函数调用约定，这进一步简化为：

\n

max:  # GCC -O3 \n  cmp esi, edi\n  mov eax, edi\n  cmovge eax, esi\n  ret\n

\n

---

\n

是否有其他架构的编译器生成无分支最大/最小函数？嗯，这是 ARMv7 的代码：

\n

max:  # CLANG -O3\n  cmp r0, r1\n  movle r0, r1\n  bx lr\n

\n

ARMv8-a 和 ARM64 有一条非常有趣的指令：

\n

max:  # GCC -O3\n  cmp w1, w0\n  csel w0, w1, w0, ge\n  ret\n

\n

RISC-V 怎么样？嗯，似乎没有条件 move的等价物，因此编译器生成基本的基于分支的版本：

\n

max:  # rv32gc clang -O3\n  blt a1, a0, .LBB1_2\n  mv a0, a1\n.LBB1_2:\n  ret\n

\n

---

\n

我们可以做得更好吗？在Hacker\xe2\x80\x99s Delight中，Warren 向我们展示了以下公式，该公式在上述范围内（即，在减少一位的整数范围内）工作，没有任何分支。在C中：

\n

int max_v1(int x, int y) {\n    return (x - ((x-y) & ((x-y) >> 31)));\n}\n

\n

其中>>应该代表算术（有符号）右移。该函数的手写 RISCV 汇编只有 4 条指令：

\n

max_v1:  # hand-written\n  sub a1, a0, a1\n  srai a2, a1, 31\n  and a1, a1, a2\n  sub a0, a0, a1\n  ret\n

\n

---

\n

分析它是如何编译为 x86-64 的\xe2\x80\x99 很有趣。由于该函数仅在定义的范围内起作用，因此它与最大值并不完全相同。但优化器并没有\xe2\x80\x99 完全产生我们所期望的结果：

\n

max_v1:  # Clang -O1\n  mov eax, edi\n  xor ecx, ecx\n  mov edx, edi\n  sub edx, esi\n  cmovns edx, ecx\n  sub eax, edx\n  ret\n

\n

它\xe2\x80\x99s无分支好吧，尽管它取决于条件移动。这是如何为 RISCV 编译的？

\n

max_v1:  # rv32gc clang -O3\n  sub a2, a0, a1\n  bltz a2, .LBB0_2\n  mv a1, a0\n.LBB0_2:\n  mv a0, a1\n  ret\n

\n

等等，什么？我们有分店！四个指令和一个分支。为什么？让\xe2\x80\x99s 看一下未优化的版本：

\n

max_v1:  # rv32gc clang -O0\n  addi sp, sp, -16\n  sw ra, 12(sp)\n  sw s0, 8(sp)\n  addi s0, sp, 16\n  sw a0, -12(s0)\n  sw a1, -16(s0)\n  lw a0, -12(s0)\n  lw a1, -16(s0)\n  sub a1, a0, a1   # <\n  srai a2, a1, 31  # <\n  and a1, a1, a2   # <\n  sub a0, a0, a1   # <\n  lw ra, 12(sp)\n  lw s0, 8(sp)\n  addi sp, sp, 16\n  ret\n

\n

如果忽略所有堆栈操作（因为编译器没有针对使用a函数参数的寄存器进行优化），则行10-13正是我们手动生成的代码。为什么，哦为什么，优化器尽其所能地引入一个分支？

\n

---

\n

PS我有一个理论，但我首先想听听专家的意见。

\n

Answer 1

Clang 也对 x86-sans-cmov 进行了这种转换： try clang -m32 -march=i486 -O2。它源于 LLVM 优化管道的工作原理。

对于如此小的测试用例，您可以轻松地检查编译器如何自行转换代码。在 Compiler Explorer 上，在编译器窗格中选择“Add New > LLVM Opt Pipeline”；它将生成一个新窗格，显示编译器传递的顺序，其中更改代码的传递以绿色突出显示： https: //godbolt.org/z/8jEq1nxGY

可以看到LLVM的InstCombine pass识别了指令序列

%sub = sub nsw i32 %x, %y
%shr = ashr i32 %sub, 31
%and = and i32 %sub, %shr
%sub2 = sub nsw i32 %x, %and
ret i32 %sub2

并将其替换为

%sub2 = call i32 @llvm.smax.i32(i32 %x, i32 %y)
ret i32 %sub2

然后在机器代码生成过程开始时，smax内在函数被扩展为分支序列。

请注意，与 Clang 不同，GCC 12 发出所需的无分支代码（它不与此表达式进行模式匹配）：

sub     a1,a0,a1
srai    a5,a1,31
and     a5,a5,a1
sub     a0,a0,a5
ret