C#中的乱序执行

Question

C#中的乱序执行

c#assemblyx86-64compiler-optimizationcpu-architecture

3

我有以下的代码片段：

static long F(long a, long b, long c, long d) 
{
    return a + b + c + d;
}

生成：

<Program>$.<<Main>$>g__F|0_0(Int64, Int64, Int64, Int64)
    L0000: add rdx, rcx
    L0003: lea rax, [rdx+r8]
    L0007: add rax, r9
    L000a: ret

如果我从这篇《乱序执行》手册（§ Out of order execution）（来源）中正确理解的话，上面的代码可以转化为 ((a + b) + c) + d。为了计算这个式子，CPU必须等待第一个括号和第二个括号等等。在这里我们可以看到LEA位于中间，这意味着它们无法并行执行（如果我理解正确的话）。因此，作者建议：

将“独立”的括号配对：

static long G(long a, long b, long c, long d) 
{
    return (a + b) + (c + d);
}

但是这会生成相同的汇编代码：

<Program>$.<<Main>$>g__G|0_1(Int64, Int64, Int64, Int64)
    L0000: add rdx, rcx
    L0003: lea rax, [rdx+r8]
    L0007: add rax, r9
    L000a: ret

相比之下，这是C代码使用GCC（O2）生成的结果：

int64_t
f(int64_t a, int64_t b, int64_t c, int64_t d) {
        return a + b + c + d;
}

int64_t
g(int64_t a, int64_t b, int64_t c, int64_t d) {
        return (a + b) + (c + d);
}

以下是输出结果：

f: 
        add     rcx, rdx        ; I guess -O2 did the job for me.
        add     rcx, r8         ; I guess -O2 did the job for me.
        lea     rax, [rcx+r9]
        ret
g:
        add     rcx, rdx
        add     r8, r9
        lea     rax, [rcx+r8]
        ret

问题

我是否正确理解了手册？这两个ADD应该连在一起（中间没有LEA）吗？如果是，我如何提示C#编译器不要忽略我的括号？

注释

这里是SharpLab链接。
这里是Gotbolt链接。

- user12722843

4

整数加法是可结合的；您的括号在语义上无关紧要。C＃编译器将直接将其转换为IL代码（因此大体上尊重您的顺序），但JIT编译器仍会重新排列该IL代码以最佳方式编写代码，如果可以进行改进，这肯定不应取决于您放置括号的位置。C＃不是C ++。 - Jeroen Mostert

2

还有一个有趣的事情：在gotbolt中选择Clang编译器，它会使用add、lea、add指令。而MSVC编译器则使用lea、add、add指令，但是这些指令之间存在数据依赖关系。 - canton7

2

无论是较慢的版本还是较快的版本（就延迟而言 - 吞吐量没有区别），都可以编写为 lea add add，add lea add 和 add add lea，这并没有什么区别，它们之间的差异在于它们的依赖图（允许前两个指令并行执行或不允许）。 - harold

2

@NateEldredge：是的，我应该说未经检查的整数加法是可结合的；大多数开发人员（包括我在内）往往会忘记.NET具有已检查的数学功能，因为它很少被使用（更不用说作为默认值）。对于这种情况，这并不重要，因为JIT知道如果您正在进行已检查的数学运算，则要按照不同的规则操作；在这种情况下，它显然可以自由地输出指令。 - Jeroen Mostert

2

@canton7：汇编中的依赖模式确实很重要。乱序执行不会尝试重新关联整数加法等可结合操作。GCC在带符号的int64_t上有愚蠢的优化错误——C中有符号溢出是未定义行为，似乎阻止了它将其视为可结合的。使用uint64_t可以使其正确地进行双向优化：先进行两个独立的加法，然后组合成对。https://godbolt.org/z/W13WEjjMh。Clang无论如何都会自我打败，像C#的JIT一样串行化操作，即使你在源代码中提示它使用更多的指令级并行性。 - Peter Cordes

显示剩余19条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Cordes · Answer 1

整数加法是可结合的。编译器可以利用这一点（“仿佛规则”），而不考虑操作的源级顺序。

（不幸的是，似乎大多数编译器在这方面做得很糟糕，即使你聪明地编写源代码也会让情况变得更糟。）

汇编整数溢出没有副作用；即使在像MIPS这样的目标上，add在有符号溢出时触发陷阱，编译器也使用addu，它不会触发陷阱，因此可以进行优化。（在C中，编译器可以假定源级操作顺序永远不会溢出，因为那将是未定义行为。因此，他们可以在同一输入下使用有陷阱的add进行计算，对于具有这种指令集体系结构的ISA而言，但即使使用gcc -fwrapv以定义带符号整数溢出的二进制补码环绕行为也不是默认值，编译器也使用可能允许静默包装而非陷入的指令。主要是因为他们不必关心任何给定操作是否针对在C抽象机中出现的值或不出现的值。UB并不意味着需要故障；-fsanitize=undefined需要额外的代码来实现这一点。）

例如，INT_MAX + INT_MIN + 1 可以被计算为 INT_MAX + 1（溢出到 INT_MIN），然后在二进制补码机器上 . + INT_MIN 再次溢出回到 0，或者按源代码顺序执行而没有溢出。最终结果相同，这是从操作中逻辑上可见的全部内容。

具有乱序执行的CPU不会尝试重新关联指令，而是遵循汇编/机器代码的依赖图。

首先，这对于硬件来说太多了，无法即时考虑；其次，每个操作的FLAGS输出确实取决于您创建的临时变量，中断可能在任何时候到达。因此，在所有旧指令完成时，正确的体系结构状态需要在指令边界处可恢复。这意味着编译器的工作是在汇编中公开指令级并行性，而不是让硬件使用数学来创建它。另请参见现代微处理器90分钟指南！和此答案）

编译器的表现如何？

大多数情况下很糟糕，会自己给自己惹麻烦/使您在进行源代码级别优化时变得悲观，至少在这种情况下是这样。

C#: 即使源代码中存在 ILP，也会将其删除；将 (a+b) + (c+d) 序列化为一个线性操作链；3个周期的延迟。

clang12.0：相同，序列化两个版本。

MSVC：相同，序列化两个版本。

GCC11.1 用于有符号的 int64_t：保留操作的源顺序。这是一个长期存在的 GCC 优化问题，其优化器避免在临时变量中引入有符号溢出，原因是它在承诺/保证/优化机会方面退步了，即在创建在抽象机器上运行的具体实现时，某些东西在抽象机器中是 UB 时所创建的承诺/保证/优化机会。尽管 GCC 知道它可以自动向量化 int 加法，但它只是在标量表达式内重新排序，其中一些过度保守的检查将有符号整数与浮点数归为非关联性。

GCC11.1 用于无符号的 uint64_t 或使用 -fwrapv：视为关联性，并以相同方式编译 f 和 g。序列化大多数调优选项（包括用于其他 ISA，如 MIPS 或 PowerPC），但 -march=znver1 恰好创建了 ILP。（这并不意味着只有 AMD Zen 是超标量的，而是 GCC 存在优化问题！）

ICC 2021.1.2：即使在线性源版本中（f）也会创建 ILP，但使用 add/mov 而不是 LEA 作为最后一步。 :/

Godbolt 适用于 clang/MSVC/ICC。

Godbolt 用于 GCC 带符号、无符号或 -fwrapv。

理想情况是从两个独立的加法开始，然后将它们组合起来。这三个加法中的一个应该使用lea将结果放入RAX中，但可以选择任意一个。在独立的函数中，您可以销毁任何传入的参数寄存器，并且没有必要避免覆盖其中两个而不仅仅是一个。

您只需要一个LEA，因为2个寄存器的寻址模式使其成为比ADD更长的指令。