如果不使用C中的条件语句，我如何保证变量永远不会为零？

Question

例如，假设一个变量 x，x 可以是包含 0 的任何内容。
然后我们得到了这样的代码：

if(x==0) {
    y = 1;
}
else {
    y = x;
}

我可以在不生产 C/C 分支的情况下做到这一点吗？

我正在尝试优化一段代码。我想尽可能多地清除树枝。也有类似的判断，所以我想将它们转换为没有分支的语句，以使代码尽可能高效。

Answer 1

如果对于< code>__builtin_clz的输入需要这种非零保证(对于零输入给出未定义的结果，否则计算前导零位)，一个有用的技巧是< code>y = x|1。这不会影响任何非零输入的前导零的数量，因为只有当所有高位都为零时，您才设置CLZ将查看的最后一个位置。如果< code>x=1，那么< code>x|1仍然是< code>1。

与__builtin_ctz（计数尾随零）的设置类似，y=x|（1UL

无条件设置其中一位将改变一些非零值；这仅在某些情况下有用。

为了准确获得您要求的语义，y = x ？ x ： 1 可以这样表示，或者按照另一个答案中的建议表示为 x ！x，它要求编译器具体化一个布尔整数并将其相加。

当然，一个聪明的编译器有望选择一种在目标机器上高效的方法。对于x86，如果可以覆盖x，人们可能会希望智能编译器可以这样做：

    cmp  eax, 1          ; CF=1 only if EAX==0 because only 0 is < 1U
    adc  eax, 0          ; x += (eax < 1U)

而对于 AArch64，tst 或 cmp 然后 cinc 可以根据任何标志条件有条件地复制和递增值。

在Godbolt编译器资源管理器上-

int make_nonzero_booleanize(int x){
    return x + !x;
}

int make_nonzero_ternary(int x){
    return x ? x : 1;
}

int make_nonzero_if(int x){
  // the original.  Compilers may compile it to branchless code
  // especially gcc -O3 instead of -O2 is more aggressive about if-conversion
    int y;
    if (x)
        y = x;
    else
        y = 1;
    return y;
}

# GCC12 -O3 for x86-64
make_nonzero_booleanize(int):           # return x + !x
        cmp     edi, 1
        mov     eax, edi
        adc     eax, 0       # Apparently a GCC dev already thought of this peephole and taught GCC10 about it
           # I was expecting compilers to naively do xor-zeroing + test/setcc + add
        ret

make_nonzero_ternary(int):
        mov     eax, edi
        test    edi, edi
        mov     edx, 1
        cmove   eax, edx     # standard ternary using conditional-move
        ret

make_nonzero_if(int):
         # same asm as ternary; GCC did an if-conversion optimization

// ARM64 gcc12 -O2
make_nonzero_booleanize(int):
        cmp     w0, 0
        cinc    w0, w0, eq       // return x==0 ? x : x+1
        ret
make_nonzero_ternary(int):
        cmp     w0, 0
        csinc   w0, w0, wzr, ne  // return x==0 ? x : 0+1
        ret
make_nonzero_if(int):
     // identical to ternary, if-conversion even with -O2

两种方式都一样好；< code>csinc结果仍然依赖于输入< code>w0，即使条件为真，并且结果来自递增零寄存器(< code>wzr)。

# RISC-V 32-bit clang 15 -O3
make_nonzero_booleanize(int):
        seqz    a1, a0                # tmp = (x==0)
        add     a0, a0, a1            # return x + tmp
        ret

make_nonzero_ternary(int):
        mv      a1, a0                  # tmp = x
        li      a0, 1                   # retval = 1
        beqz    a1, .LBB1_2             # if (x != 0) {
        mv      a0, a1                    # retval = tmp
.LBB1_2:                                # }
        ret                             # return retval

make_nonzero_if(int):
      # identical to ternary, same branching.

Clang在这里选择的分支策略甚至做得不好；它可以在retval=1上执行bnez，从而避免两条 指令。除非有一些调优的东西，在 mv上的分支被一些RISC-V微体系结构作为条件移动来处理？希望在内联之后它不会如此糟糕，并且可能会将 ==0特例的分支目标放在其他地方，在那里它不必跳过它。

因此，x ！x 在 x86-64 和 RISC-V 上使用一些真实世界的编译器更好，在 AArch64 上相同。

如果您关心某些特定上下文中某些 ISA 的特定编译器，请查看它如何在您的代码中进行编译。（如果你知道ASM中什么是有效的。

GCC7和更早的版本在三元上做得更好，避免了mov eax，di，而是做mov eax，1，然后使用cmovnz来复制EDI或不复制EDI。希望GCC8和后来的低效率只发生在没有内联这个小函数的时候；众所周知，当GCC不得不绕过调用约定或内联的硬寄存器约束时，它会浪费指令。

GCC9 及更早版本不知道 x86-64 的 cmp/adc 技巧，而是使用 x ！x 的文字实现，不幸的是，这不是很好，因为 x86 在将布尔条件实现为 0/1 整数方面很糟糕由于 setcc 的设计不佳。

# GCC9 and earlier  -O3
make_nonzero_booleanize(int):
        xor     eax, eax       # zero the full reg
        test    edi, edi       # set FLAGS according to x
        sete    al             # EAX = !x
        add     eax, edi       # EAX += x
        ret

公平地说，在Sandybridge之前，adc eax，0在Intel上的成本为2 uop。（并且GCC调整选择可能没有意识到立即为0的adc是特殊的；一般来说，adc在Broadwell之前在Intel上的成本为2 uop。）

即使在最好的情况下，x86-64、AArch64 和 RISC-V 的无分支代码也会将关键路径依赖链延长 2 条指令，在大多数 CPU 上都有 1 个周期延迟。（例如，在 cmp 的标志结果准备就绪之前，csinc 无法运行。

但是正确预测的分支是一种控制依赖项，因此它由CPU单独处理，乐观地假设y=x会是这种情况，只有在后来检测到错误预测时才会退出。

但是在C源代码中编写if（）并不能保证你会得到分支asm。（不过，与其他编写方法相比，||使其更有可能编译分支。）

相关：

• gcc优化标志-O3使代码比-O2慢-在这种情况下，当分支是高度可预测的时，GCC的x86-64的无分支代码生成比分支慢。（特别是因为GCC使循环承载的依赖链比必要的长。）-O3在if-转换为无分支方面更积极，但它没有自动矢量化。
• 为什么条件移动不容易受到分支预测失败的影响？
• http://yarchive.net/comp/linux/cmov.html-Linus Torvalds oncmov，回到奔腾4天时它更慢。

Answer 2

您应该检查编译器的汇编程序输出。例如，X86架构有一条名为cmov的指令(https://www.felixcloutier.com/x86/cmovcc)它被设计用于处理这种没有分支的事情。Arm架构允许根据CPU标志执行几乎所有指令：https://developer.arm.com/documentation/dui0473/m/condition-codes/conditional-execution-in-arm-state.

因此，当启用优化时，您的编译器可能不会产生任何分支。

Answer 3

一些一般性说明：

1. 如其他注释中所述，某些编译器可以优化和消除分支。您可以检查程序集输出（例如在 Godbolt 中）以确保。
2. 当心过早的优化。
3. 始终衡量并确保你对占用时间的猜测是正确的。

话虽如此，您可以尝试以下“技巧”：

y = !x + x;

假设< code>x，< code>y是整数类型:

• 如果 x==0，则 ！x 将为 1，y 将被赋值 1。
• 如果 x！=0，则 ！x 将为 0，y 将被赋值 x。

注:关于标准中的保证，见下面@CostantinoGrana的评论。您也可以在您的特定环境(编译器等)中验证它。).