有没有办法将条件赋值转换为无分支代码？

Question

有没有办法将下面的 C 代码转换成不带任何条件语句的代码？我分析了我的一些代码并注意到它在一个与这个非常相似的 if 语句上有很多分支未命中。

int cond = /*...*/;
int a = /*...*/;
int b = /*...*/;

int x;
if (cond) {
   x = a;
} else {
   x = b;
}

Answer 1

这取决于您的目标指令集。对于 x86，有 cmov。对于 arm64，有 csel。对于 armv7，mov 带有可选的条件操作码。

任何体面的编译器都应该能够将您拥有的代码优化为最佳指令集。 GCC 和 clang 就是这样做的（在 https://gcc.godbolt.org/ 上自己试试）。

更直接地回答你的问题：没有办法在直接 C 中强制执行此操作，因为 CPU 指令集可能没有可用作替代的无分支指令.所以你要么必须依赖你的编译器（这可能是个好主意），要么手写你自己的程序集。

举个小例子，考虑以下 C 代码：

int min(int a, int b) {
  int result;
  if (a < b) {
    result = a;
  } else {
    result = b;
  }
  return result;
}

gcc 5.4.1 for armv7 生成：

min(int, int):
        cmp     r0, r1
        movge   r0, r1
        bx      lr

gcc 5.4 for arm64 生成：

min(int, int):
        cmp     w0, w1
        csel    w0, w0, w1, le
        ret

x86 的 clang 4.0 生成：

min(int, int):                               # @min(int, int)
        cmp     edi, esi
        cmovle  esi, edi
        mov     eax, esi
        ret

x86 的 gcc 5 生成：

min(int, int):
        cmp     edi, esi
        mov     eax, esi
        cmovle  eax, edi
        ret

x86 的 icc 17 生成：

min(int, int):
        cmp       edi, esi                                      #8.10
        cmovl     esi, edi                                      #8.10
        mov       eax, esi                                      #8.10
        ret                                                     #8.10

如您所见，它们所有无分支（在 -O1 或更高版本编译时）。

Answer 2

一个更完整的示例会更有帮助，因为访问变量 x、a、b 和 cond 的方式可能会发挥作用。如果它们是在执行条件赋值的函数之外声明的全局变量，那么将使用加载和存储来访问它们，编译器可能认为有条件地执行这些操作代价太大。查看 https://godbolt.org/g/GEZbuf 中的示例，其中对全局变量和 foo 以及 foo2

中的局部参数执行相同的条件赋值

Answer 3

x = (!cond * b) | (!!cond * a);

有没有办法将条件赋值转换为无分支代码？

Is there a way to convert a conditional assignment to branch free code?

c

branch-prediction