如果没有副作用，编译器/JIT是否可以优化短路求值？

Question

我有一个测试，要求如下：

if(variable==SOME_CONSTANT || variable==OTHER_CONSTANT)

在这种情况下，如果在一个分支超过第二个测试的平台上进行分支需要更多的周期，那么优化器是否允许将||视为简单的|？

- Medinoc

---

如果一个表达式可以证明没有任何副作用，那么根据定义，它的（不）计算是无法被观察到的。任何语言/运行时设计者都不会如此受虐以要求在有勇气的开发人员检查它是否真实存在时生成代码。当然，诀窍在于证明没有副作用，这里编译器通常必须保持谨慎。 - Jeroen Mostert

一个标准的优化策略是使用条件移动（CMOV指令）。但.NET优化器倾向于仅在赋值表达式中使用它。如果它们是真正的编译时常数，那么常量折叠优化会使整个表达式消失。这就是您可以帮助提高代码效率的地方，如果您不需要短路，请勿使用它。一个预测不良的lhs表达式可能会使Haswell上的代码变慢5倍，假设最小的if()语句体。 - Hans Passant

出于好奇，当您说“编译器是否能够...”时，您是在询问语言是否允许这样做（即使尚未在任何编译器中实现），还是在询问当前的 C# 编译器是否实际上会实现此优化？ - BeeOnRope

@BeeOnRope 前者是正确的（尽管其中一个答案也指出后者是正确的）。 - Medinoc

Answer 1

在这种情况下，在一个分支测试需要更多周期的平台上，优化器是否可以将||视为简单的|呢？

是的，这是允许的，实际上C#编译器在某些情况下会对&&和||执行此优化，将它们减少到&和|。正如您所指出的，评估右侧时必须没有副作用。

请查阅编译器源代码以获取生成优化的确切详细信息。

当逻辑操作涉及提升为可空操作数时，编译器也会执行该优化。例如，请考虑以下情况：

int? z = x + y;

其中x和y也是可空整数；这将生成为

int? z;
int? temp1 = x;
int? temp2 = y;
z = temp1.HasValue & temp2.HasValue ? 
  new int?(temp1.GetValueOrDefault() + temp2.GetValueOrDefault()) :
  new int?();

请注意，应该是&而不是&&。我知道调用HasValue非常快，因此没有必要使用额外的分支逻辑来避免它。

如果您对我编写的可为空算术优化器感兴趣，我在这里写了详细说明：https://ericlippert.com/2012/12/20/nullable-micro-optimizations-part-one/。

- Eric Lippert

Answer 2

编译器可以将短路比较优化为非两个测试和分支的汇编代码。但有时这并不划算（特别是在x86上，因为将比较转换到寄存器需要多个指令），而且有时编译器会错过这种优化。

或者，如果编译器选择使用条件移动来生成无分支代码，则两个条件始终会被评估。（当然，只有在没有副作用时才能选择此选项）。

一个特殊情况是范围检查：编译器可以将x>min&&x<max（特别是当min和max是编译时常量时）转换为单个检查。这可以用2条指令完成，而不是分别在每个条件上进行分支。从范围的低端减去将会使输入小于0，所以减法加上无符号比较就可以进行范围检查。

范围检查优化易于实现/广为人知（由编译器开发人员知晓），因此我认为C# JIT和预先编译的编译器也会这样做。

以C示例（具有与C#相同的短路评估规则）为例：

int foo(int x, int a, int b) {
    if (10 < x && x < 100) {
        return a;
    }
    return b;
}

使用gcc7.3编译（-O3）生成x86-64 Windows ABI。你可以在Godbolt编译器资源管理器上查看ICC、clang或MSVC的输出，或者在ARM、MIPS等平台上查看gcc的输出：在Godbolt编译器资源管理器上查看。

foo(int, int, int):
    sub     ecx, 11        # x-11
    mov     eax, edx       # retval = a;
    cmp     ecx, 89
    cmovnb  eax, r8d       # retval = (x-11U) < 89U ? retval : b;
    ret

因此，该函数是无分支的，使用cmov（条件移动）。@HansPassant表示，.NET的编译器只倾向于对赋值操作进行此操作，因此，如果您将其写成C#源代码，则可能仅获得该asm：retval = (10 < x && x < 100) ? a : b;。

---

或者以一个分支示例为例，我们可以将范围检查优化为sub，然后是无符号比较/分支，而不是比较/cmov。

int ext(void);
int bar(int x) {
    if (10 < x && x < 100) {
        return ext();
    }
    return 0;
}

  # gcc -O3
    sub     ecx, 11
    cmp     ecx, 88
    jbe     .L7             # jump if ((unsigned)x-11U) <= 88U
    xor     eax, eax        # return 0;
    ret
.L7:
    jmp     ext()           # tailcall ext()

我不确定现有的C#实现是否以相同的方式进行了这种优化，但对于所有可能的输入来说，这是易于实现的且有效的，所以他们应该这样做。

Godbolt没有C＃编译器；如果有一个可以方便地显示汇编代码的在线C＃编译器，那么在那里尝试这些函数会很有趣。(我认为它们是有效的C#语法，也是有效的C和有效的C ++)。

---

其他情况

某些情况除了范围检查之外，将多个条件优化为单个分支或cmov可能会更加有利。x86不能非常高效地将比较结果存储到寄存器中(xor-zero / cmp / setcc)，但在某些情况下，您只需要0 / 非零而不是0 / 1布尔值以稍后合并。x86的OR指令设置标志位，因此您可以使用or/jnz跳转，以在任一寄存器为非零时跳转。(但请注意，在jcc之前保存test reg,reg只节省了代码大小；测试/跳转时，宏融合可行，但在or/jcc中不可行，因此or/test/jcc与or/jcc的uops数量相同。使用cmovcc或setcc可以节省一个uop。)

如果分支预测完美，则两个cmp/jcc可能仍然是最便宜的(由于宏融合：cmp/jne在最近的CPU上是单个uop)，但如果没有，则两个条件一起可能会有更好的预测效果，或者使用CMOV会更好。

int foo(int x, int a, int b) {
    if ((a-10) || (x!=5)) {
        return a;
    }
    return b;
}

# compiled for the x86-64 System V ABI this time: args in edi=x, esi=a, edx=b mov eax, esi xor eax, 10 xor edi, 5 or edi, eax # flags set from edi=(a^10) | (x^5) cmovne edx, esi # edx = (edi!=0) ? a : b mov eax, edx # return edx ret

如果想让其他编译器生成像这样的代码，可能需要一些辅助。clang也需要类似的帮助来意识到它可以使用lea进行复制和减法，而不需要在xor之前使用mov来避免破坏后续需要的输入。

int should_optimize_to(int x, int a, int b) {
    // x!=10 fools compilers into missing the optimization
    if ((a-10) | (x-5)) {
        return a;
    }
    return b;
}

gcc、clang、msvc和ICC编译这个基本上是一样的：

    # gcc7.3 -O3
    lea     eax, [rsi-10]      # eax = a-10
    sub     edi, 5             # x-=5
    or      eax, edi           # set flags
    mov     eax, edx
    cmovne  eax, esi
    ret

这比clang的代码更加智能：在cmov之前将mov放入eax中可以创建指令级并行性。如果mov具有非零延迟，则该延迟可以与创建cmov的标志输入的延迟并行发生。

如果您想要这种优化，通常需要手动引导编译器实现它。

- Peter Cordes

---

说实话，“范围检查”技巧是一种特定情况，其中检查的形式允许将其简化为单个检查。如果您假设 OP 正在询问不能像他提供的那样简化的检查（例如，更通用的检查），则基于我的测试，答案是至少在 x86 上，即使没有任何检查具有副作用，它们仍然更喜欢一系列跳转。可能的原因之一是 x86 没有很好的方式将比较的结果（标志寄存器中的位）进行 AND 或 OR 运算，因此一系列检查通常是最有效的... - BeeOnRope

我想说的是，所给出的例子并不是真正意义上的“尽管使用了快捷操作符仍然以无条件方式执行第二个检查”，而是“一种消除其中一个检查的转换”，这有点不同。我实际上对编译器实际保留所有检查但以非短路方式执行它们的情况感兴趣，因为我以前寻找过它们，但没有找到。顺便说一句，即使x86可以将比较结果存储到寄存器中（ARM可以吗？），这也会很麻烦：两次比较，一个OR，然后再比较和分支... - BeeOnRope

啊，我明白了。关于范围检查太特殊的观点很好。对于x-10 || a==5（和可能存在的其他多个相等比较情况），这是合法且有利可图的，但gcc/clang/MSVC/ICC错过了这种优化（https://godbolt.org/g/74qpyn）。`OR`设置标志（但无法宏融合，因此在`jcc`之前省略`test`只能节省代码大小）。 - Peter Cordes

有趣。请注意，在您的示例中，if语句的主体足够简单，以至于可以无需分支来完成，因此这使得编译器更有创意地将条件组合成单个检查，因为在那时整个事情就变成了对最终组合条件的“cmov”。在更一般的情况下，if语句不能/不会无需分支完成，[计算似乎会发生变化]（https://godbolt.org/g/tsVKoG），并且“clang”仍然选择两个分支。但是，“icc 18”仍然结合了条件并使用了单个跳转。嗯... - BeeOnRope

很不幸的是，由于时间限制（JIT编译需要快速完成），C#的JIT没有进行尽可能多的优化。这里有一个在线编译器，可以使用你的示例，它显示没有条件移动。请参见此问题。 - Lucas Trzesniewski

Answer 3

是的，编译器可以进行这种优化。实际上，每种有趣的语言通常都有一个明确或隐含的“好像”类型条款，使得这种不可观察的优化允许而无需特定规则。这允许以非快捷方式实现检查，以及一系列更极端的优化，例如将多个条件组合成一个条件、完全消除检查、使用预测指令在没有任何分支的情况下实现检查等。

然而，另一方面，在大多数常见平台上，你提到的无条件执行第二个检查的特定优化并不经常发生，因为在许多指令集中，如果假定它不改变分支的可预测性，分支方法是最快的。例如，在x86上，可以使用cmp将变量与已知值（如您的示例中）进行比较，但“结果”最终会出现在EFLAGs寄存器中（体系结构上只有一个）。在这种情况下，如何在两个比较结果之间实现||？第二个比较将覆盖第一个设置的标志，因此你将被卡在某个地方保存标志，然后进行第二个比较，然后尝试以某种方式“组合”标志，以便进行单个测试1。

事实上，忽略预测，条件分支通常几乎是免费的，特别是当编译器将其组织为“不采取”时。例如，在x86上，您的条件可能看起来像两个cmp操作，每个操作紧接着跳过if()块中的代码。因此，只需要两个分支指令，而不是为了将其减少到一个而必须跳过的各种麻烦。更进一步-这些cmp和随后的分支通常会macro-fuse成为一个单独的操作，其成本与仅比较相同（并且需要一个周期）。虽然存在各种警告，但总体假设“在第二次测试中进行分支”需要很长时间可能并不牢固。

主要的限制在于分支预测。如果每个子句都是不可预测的，但整个条件是可预测的，将所有内容合并成一个单独的分支可能非常有利。例如，假设在您的(variable == SOME_CONSTANT || variable == OTHER_CONSTANT)中，variable有50%的时间等于SOME_CONSTANT，49%的时间等于OTHER_CONSTANT。因此，if将被执行99%的时间，但第一个检查variable == SOME_CONSTANT将是完全不可预测的：正好一半的时间进行分支！在这种情况下，即使有一些代价，合并检查也是一个好主意，因为错误预测是昂贵的。

现在有某些情况下编译器可以仅由于检查的形式而将检查组合在一起。Peter在他的答案中展示了使用类似范围检查的示例的示例，还有其他情况。

这里有一个有趣的例子，其中SOME_CONSTANT为2，OTHER_CONSTANT为4：

void test(int a) {
    if (a == 2 || a == 4) {
        call();
    }
}

无论是 clang 还是 icc，都将其实现为两个检查和两个分支的系列，但最近的 gcc 使用 另一种技巧：

test(int, int):
  sub edi, 2
  and edi, -3
  je .L4
  rep ret
.L4:
  jmp call()

基本上它从a中减去2，然后检查是否设置了除0b10以外的任何位。该检查仅接受值2和4。有趣的变换！对于可预测的输入，它并没有比两个分支方法更好，但对于“不可预测的子句但可预测的最终结果”情况，它将是一个巨大的胜利。

然而，这并不是无条件地进行两个检查的情况：只是一种聪明的情况，可以将多个检查合并成较少的检查，可能需要一些数学技巧。因此，我不知道它是否符合您对“是的，在实践中他们确实这样做”的标准答案。也许编译器会进行这种优化，但我在x86上没有看到过。如果它存在，那么它可能只会被触发通过基于概率的优化，其中编译器对各种子句的概率有一个想法。

---

¹ 在具有快速cmov的平台上，使用两个cmov来实现||可能不是一个糟糕的选择，而&&可以类似地实现。

- BeeOnRope