RISCV 无分支编码

Question

在 Intel AVX 上，可能存在无分支代码。您可以计算这两种情况，然后根据条件混合结果，而不是对 case0 或 case1 进行分支。

AVX 使用 vblendps 指令为浮点数执行这 8 种方式。

您也可以使用 x86 指令 CMOVcc 以有条件地执行移动操作的 x86 指令以标量方式执行此操作。

注意：ARM 有 CSEL and NEON has VBSL.

RISCV64 能否像这样进行标量移动，这样您就不必为

分支

a = c ? x : y;

据我所知，RISCV 实现是有序的，因此在不必分支时，它比 x86 更有优势。（后者至少可以绕过一些指令，甚至可以推测性地分支以隐藏延迟。）

我能找到的最接近 w.r.t riscv 的无分支操作是 SLT（设置小于），但设置为 1 或 0，然后需要乘法？将 SLT 设置为 -1 或 0 不是更有用，这样我们就可以 AND 吗？

更新

做的时候：

int foo(int a, int b, int x, int y)
{
    return a < b ? x : y;
}

我尝试了一个使用 SLT 的穷人版本的无分支。我不确定我是否完全正确，通过使用位掩码作为 0 - 条件 (0|1)，我想出了：

branchless:
    SLT t0,a0,a1
    SUB t0,zero,t0
    NOT t1,t0
    AND t0,a2,t0
    AND t1,a3,t1
    OR  a0,t0,t1
    RET
    .size   branchless, .-branchless

作为无分支版本：

branched:
    BGE a0,a1,.L2
    MV  a3,a2
.L2:
    MV  a0,a3
    RET
    .size   branched, .-branched

我想知道我是否为此使用了太多指令，但我测得分支版本在随机数据上比非分支版本稍快，但幅度不大。

Answer 1

建议的 RISC-V 扩展 B 包括 cmov（具有 4 个操作数：3 个输入和一个单独的目标！）。

我认为 David Patterson（MIPS 和 RISC-V 背后的主要架构师之一）真的不喜欢 cmov（以及 short-vector SIMD，喜欢 SSE/AVX）并且认为 CPU如果他们想这样做，应该专门处理“吊床”分支（像移动一样向前跳过单个指令）。像那样的东西。因此，这似乎是一个纯粹的哲学问题，妨碍了包含有用的说明。（AArch64 是一个更加实用的设计，在对 high-performance 实现很重要的方面仍然是 RISC。）

And/or 如果没有任何其他 3 输入指令，可能希望将指令限制为最多 2 个输入。这意味着如果严格遵守此限制，标量流水线只需要 2 个寄存器读取端口，而不是 3 个。（这也意味着没有 add-with-carry，当你必须处理 carry-in 和时，extended-precision 数学对于宽度超过 2 个寄存器的数字来说非常痛苦carry-out 到相同的添加操作。）

你可以模仿 cmov 就像你说的那样用 AND/ANDnot/OR 的掩码，但这需要很多指令而且通常不值得except 可能在 wide 和 deep out-of-order 机器上，其中分支未命中丢弃的工作量要大得多。（mask = (c == 0) - 1; 你可以用 sltiu / add reg,reg, -1 把 0 变成 -1 和 1 变成 0。）

关于哪种微体系结构从 CMOV 中获益更多，你有点倒退了，尽管这两种方式都有潜在的好处。 in-order 机器已经有点必须在条件分支处等待条件解决，而 out-of-order 机器处理控制依赖项与数据依赖项的方式截然不同。正如中所讨论的，通过 cmov 的数据依赖可以创建一个 loop-carried 依赖链，这是一个更大的瓶颈，高度可预测的分支。

有一些 out-of-order exec RISC-V 设计，甚至可能有一些是 open-source。例如，Erik Eidt 链接 The Berkeley Out-of-Order Machine (BOOM).

扩展 B：他们将遗漏的所有有趣说明放在那里

RISC-V 扩展 B 提案有条件移动，以及标量 min/max、popcount、leading/trailing 零计数、位域 insert/extract、two-register转变，以及一堆更深奥的东西。 https://five-embeddev.com/riscv-bitmanip/draft/bext.html#conditional-move-cmov

查看提议的指令列表，令人惊讶的是基线 RISC-V 中遗漏的内容，例如 sign-extension 窄整数（目前需要 slli/srai），如果它还没有得到保证的话通过调用约定或加载指令，以及大多数 ISA 具有的标准内容，例如 popcount 和 leading/trailing 零计数。

Godbolt 使用 cmov、min 和 sext.b 显示 clang 12.0。在那个 clang 版本中，-O3 -Wall -menable-experimental-extensions -march=rv32gcb0p93 是执行此操作的魔法咒语。扩展 B 0.93 由字符串的 b0p93 部分启用。（扩展 B 尚未最终确定，我不知道 clang 14.0 正在寻找什么版本；它的错误消息没有帮助，只是简单的 -march=rv32gcb 没有让编译器实际使用 cmov.)

//  -march=rv32gcb0p93 includes extension b 0.93 (0p93)

int sel(int x, int y, int c){
    return c ? x : y;
}
# extension B  clang
        cmov    a0, a2, a0, a1
        ret

# baseline gcc11.3  (clang and GCC12 waste several mv instructions)
        bne     a2,zero,.L2
        mv      a0,a1
.L2:
        ret

int min(int x, int y, int c){
    return (x<y) ? x : y;
}
# extension B  clang
        min     a0, a0, a1
        ret

# baseline gcc
        ble     a0,a1,.L5
        mv      a0,a1
.L5:
        ret

int sext(int c){
    return (signed char)c;
}
# extension B  clang
        sext.b  a0, a0
        ret

# baseline gcc
        slli    a0,a0,24
        srai    a0,a0,24
        ret

RISCV 无分支编码

RISCV branchless coding

assembly

cpu-architecture

riscv

branch-prediction

conditional-move

更新

扩展 B：他们将遗漏的所有有趣说明放在那里