为什么循环总是被编译成“do…while”样式（尾跳）？

Question

在尝试理解汇编时（打开编译器优化），我看到这样的行为：

像这样一个非常基本的循环

outside_loop;
while (condition) {
     statements;
}

经常被编译成（伪代码）

    ; outside_loop
    jmp loop_condition    ; unconditional
loop_start:
    loop_statements
loop_condition:
    condition_check
    jmp_if_true loop_start
    ; outside_loop

loop_condition:
    condition_check
    jmp_if_false loop_end
    loop_statements
    jmp loop_condition  ; unconditional
loop_end:

goto condition;
do {
    statements;
    condition:
}
while (condition_check);

Answer 1

相关：asm循环基础：汇编语言(emu8086)中循环的While,Do While

循环中的指令/UOP越少=越好。在循环之外构造代码来实现这一点通常是一个好主意。

有时这需要“循环旋转”（剥离第一次迭代的一部分，以便实际的循环主体在底部具有条件分支）。所以你做了一些第一次迭代，可能完全跳过循环，然后进入循环。有时您还需要在循环之后使用一些代码来完成最后一次迭代。

这些优化中的一些与软件流水线相关或启用软件流水线，例如为下一次迭代加载一些东西。（现在x86上的OoO exec使得SW流水线变得不是很重要，但它对于像许多ARM这样的有序内核仍然很有用。使用多个累加器展开对于隐藏缩减循环中的循环携带的FP延迟仍然很有价值，比如数组的点积或和。）

do{}虽然()是asm中所有体系结构中循环的规范/惯用结构，但要习惯它。IDK如果有它的名字；我会说这样的循环有一个“do while结构”。如果需要名称，可以将while()结构称为“crappy unoptimized code”或“由新手编写”。：p循环-底部的分支是通用的，作为循环优化甚至不值得一提。你总是这样。

这种模式被广泛使用，以至于在对分支预测器缓存中没有条目的分支使用静态分支预测的CPU上，未知的前向条件分支被预测为不采取，未知的后向分支被预测为采取（因为它们可能是循环分支）。请参阅Matt Godbolt的博客中关于较新Intel处理器的静态分支预测，以及Agner Fog在其microarch PDF开头的分支预测章节。

这个答案最终都使用x86示例，但大部分应用于所有体系结构。如果其他超标量/无序实现（如某些ARM或POWER）也有有限的分支指令吞吐量，无论它们是否被接受，我都不会感到惊讶。但是，当循环中只有一个条件分支，而没有无条件分支时，循环中的指令更少几乎是通用的。

如果循环可能需要运行零次，编译器通常会在循环外部放置一个test-and-branch来跳过它，而不是跳到底部的循环条件。（即，如果编译器不能证明循环条件在第一次迭代时总是为真）。

顺便说一句，本文将while()转换为if(){do{}while；}称为“反转”，但循环反转通常意味着反转嵌套循环。（例如，如果源代码以错误的顺序在主要行的多维数组上循环，那么聪明的编译器可以将(i)for(j)a[j][i]++的；改为(j)for(i)a[j][i]++的；（如果它能够证明正确的话）。）但是我想您可以将if()看作是一个零或一迭代循环。有趣的是，编译器开发人员教他们的编译器如何在一个（非常）特定的情况下反转循环（允许自动向量化），这就是为什么Specint2006的libquantum基准被“破坏”的原因。大多数编译器不能在一般情况下反转循环，只能反转类似于Specint2006中的循环...

当您知道调用方不允许传递size=0或其他任何保证循环至少运行一次的东西时，您可以通过在C中编写do{}while()循环来帮助编译器实现更紧凑的asm（更少的循环外指令）。

（对于带符号的循环边界，实际上是0或负数。带符号的循环计数器与无符号的循环计数器是一个棘手的优化问题，特别是如果您选择了比指针更窄的类型；请检查编译器的asm输出，以确保它不是带符号的--如果您将其用作数组索引，则经常在循环内扩展一个窄的循环计数器。但请注意，带符号的实际上是有帮助的，因为编译器可以假设i++<=bound最终将变为false，因为带符号的溢出是UB而无符号的不是。因此，如果bound=uint_max，while(i++<=bound)是无限的。）对于何时使用签名与未签名，我没有一个全面的建议；不过，size_t通常是在数组上循环的好选择，但如果您想避免循环开销中的x86-64 REX前缀（为了节省代码大小），但又想说服编译器不要浪费任何指令零或符号扩展，那么它可能会很棘手。

我看不出有什么巨大的业绩提升

这里有一个例子，在Haswell之前的Intel CPU上，这种优化将提供2倍的加速比，因为P6和SNB/IVB只能在端口5上运行分支，包括未采取的条件分支。

此静态性能分析所需的背景知识：Agner Fog的微拱指南（阅读Sandybridge部分）。也读他的优化装配指南，这是很好的。（虽然有时有些地方已经过时了。）请参阅x86标记wiki中的其他x86性能链接。又见x86的MOV真的可以“免费”吗？为什么我根本不能复制这个？通过性能计数器的实验进行一些静态分析，以及对融合域UOP与未融合域UOP的一些解释。

您还可以使用Intel的IACA软件（Intel Architecture Code Analyzer）对这些循环进行静态分析。

; sum(int []) using SSE2 PADDD (dword elements)
; edi = pointer,  esi = end_pointer.
; scalar cleanup / unaligned handling / horizontal sum of XMM0 not shown.

; NASM syntax
ALIGN 16          ; not required for max performance for tiny loops on most CPUs
.looptop:                 ; while (edi<end_pointer) {
    cmp     edi, esi    ; 32-bit code so this can macro-fuse on Core2
    jae    .done            ; 1 uop, port5 only  (macro-fused with cmp)
    paddd   xmm0, [edi]     ; 1 micro-fused uop, p1/p5 + a load port
    add     edi, 16         ; 1 uop, p015
    jmp    .looptop         ; 1 uop, p5 only

                            ; Sandybridge/Ivybridge ports each uop can use
.done:                    ; }

这总共是4个融合域UOP（具有CMP/JAE的宏融合），因此它可以在每个时钟的一次迭代中从前端发送到无序内核。但在未使用的域中，有4个ALU UOP和Intel pre-Haswell只有3个ALU端口。

更重要的是，port5压力是瓶颈：这个循环每2个循环只能执行一次迭代，因为CMP/JAE和jmp都需要在port5上运行。其他UOP窃取port5可能会使实际吞吐量略低于这一水平。

ALIGN 16
.looptop:                 ; do {
    paddd   xmm0, [edi]     ; 1 micro-fused uop, p1/p5 + a load port
    add     edi, 16         ; 1 uop, p015

    cmp     edi, esi        ; 1 uop, port5 only  (macro-fused with cmp)
    jb    .looptop        ; } while(edi < end_pointer);

请立即注意，与其他一切无关，这是循环中少了一条指令。这种循环结构至少在从简单的非流水线8086到经典的RISC（像早期的MIPS）的所有方面都略胜一筹，特别是对于长时间运行的循环（假设它们不在内存带宽上出现瓶颈）。

如果内存不是瓶颈（即假设L1D命中，或者实际上至少是L2；这只是SSE2每个时钟16字节），Core2和更高版本应该每时钟运行一次，比while(){}结构化循环快一倍。

这只有3个融合域UOP，因此可以在Core2之后的任何事情上以比一个时钟更好的速度发布，或者如果发布组总是以一个分支结束，则每个时钟只有一个。

但重要的部分是port5压力大大降低：只有cmp/jb需要它。其他UOP可能会在某些时间被调度到端口5，并从循环分支吞吐量中窃取周期，但这将是几%而不是2倍。看看x86 UOP是如何调度的，确切的？。

通常每2个周期有一个分支吞吐率的大多数CPU仍然可以执行每时钟1个的小循环。不过也有一些例外。（我忘了哪些CPU不能以每时钟1的速度运行紧密循环；可能是推土机系列？或者可能只是一些像VIA Nano这样的低功耗CPU。）Sandybridge和Core2绝对可以在每个时钟运行一个紧密循环。它们甚至有循环缓冲区；Core2在指令长度解码之后但在常规解码之前具有循环缓冲器。Nehalem和以后的版本将在提供问题/重命名阶段的队列中回收UOP。（除了在Skylake上有微码更新；由于部分寄存器合并错误，Intel不得不禁用循环缓冲区。）

但是，在xmm0上有一个循环携带的依赖链：Intel CPU有1个周期的延迟paddd，所以我们也遇到了这个瓶颈。添加esi，16也是1个周期延迟。在推土机系列中，即使是整数向量操作也有2c延迟，因此每迭代2c会使循环瓶颈。（AMD从K8开始，Intel从SnB开始，每个时钟可以运行两个负载，所以我们需要展开以获得最大吞吐量。）使用浮点，您肯定希望使用多个累加器展开。为什么mulss在Haswell上只需要3个周期，不同于Agner的指令表？（使用多个累加器展开FP循环）。

如果我使用了索引寻址模式，如paddd xmm0，[edi+eax]，我可以在循环条件下使用sub eax，16/jnc。Sub/JNC可以在Sandybridge-family上宏熔合，但索引负载将在SNB/IVB上不层压（但在Haswell和以后的版本上保持熔合，除非您使用AVX表单）。

    ; index relative to the end of the array, with an index counting up towards zero
    add   rdi, rsi          ; edi = end_pointer
    xor   eax, eax
    sub   eax, esi          ; eax = -length, so [rdi+rax] = first element

 .looptop:                  ; do {
    paddd   xmm0, [rdi + rax]
    add     eax, 16
    jl    .looptop          ; } while(idx+=16 < 0);  // or JNC still works

（通常最好展开一些以隐藏指针增量的开销，而不是使用索引寻址模式，特别是对于存储，部分原因是索引存储无法使用Haswell+上的port7存储AGU。）

在Core2/Nehalemadd/jl上不进行宏融合，因此即使在64位模式下，这也是3个融合域UOP，不依赖宏融合。AMD K8/K10/推土机系列/Ryzen也是一样：没有融合循环条件，但带有内存操作数的PADDD是1 m-op/UOP。

在SnB上，paddd从负载上取消层压，但添加/JL宏熔丝，因此再次出现3个熔丝域UOP。（但在未使用的域中，只有2个ALU UOP+1个负载，因此可能会减少资源冲突，从而降低环路的吞吐量。）

在HSW和更高版本上，这是2个融合域UOP，因为索引加载可以与PADDD保持微融合，add/jl宏融合。（预取分支在端口6上运行，因此从不存在资源冲突。）

当然，循环最多只能在每个时钟运行1次迭代，因为即使是小循环也存在分支吞吐量限制。如果您在循环中还有其他事情要做，那么这个索引技巧可能很有用。

是的，这夸大了循环开销的影响。但是gcc默认情况下即使在-o3下也不会展开（除非它决定完全展开）。它只是通过配置文件引导的优化来展开，让它知道哪些循环是热门的。(-fprofile-use)。您可以启用-funroll-all-loops，但我只建议您在每个文件的基础上为您知道有一个热循环需要它的编译单元执行该操作。或者甚至可以在每个函数的基础上使用__attribute__（如果有类似的优化选项的话）。

因此这与编译器生成的代码高度相关。（但clang默认将小循环按4展开，或将小循环按2展开，并且非常重要的是，使用多个累加器来隐藏延迟。）

考虑一下当循环主体运行一次或两次时会发生什么：使用do{}while以外的任何东西会有更多的跳变。

>

对于do{}while，执行是一条直线，没有取的分支，底部有一个未取的分支。这太棒了。

对于可能运行循环零次的if(){do{}while；}，它是两个未取的分支。那还是很好的。（当两者都正确预测时，对于前端来说，不采取比采取稍微便宜一些）。

对于一个jmp-toth-bottom的jmp；执行{}while（）时，它是一个取的无条件分支，一个取的循环条件，然后循环分支不取。这是有点笨拙，但现代分支预测器是非常好的...

对于while(){}结构，这是一个未采取的循环出口，一个在底部采取的jmp，然后一个在顶部采取的循环出口分支。

迭代次数越多，每个循环结构就会多执行一个分支。while(){}还会在每次迭代中多执行一个未取分支，因此它很快变得明显糟糕。

后两个循环结构有更多的跳跃，以小的行程计数。

跳到底部对于非微小循环也有一个缺点，即如果循环的底部没有运行一段时间，它在L1I缓存中可能是冷的。Code fetch/prefetch擅长将代码以一条直线带到前端，但是如果prediction没有足够早地预测分支，那么在跳转到底部时可能会错过代码。此外，并行解码可能已经（或者可能已经）解码了循环顶部的一些内容，同时将jmp解码到底部。

有条件地跳过do{}while循环避免了所有这些：您只在跳过的代码根本不应该运行的情况下跳过尚未运行的代码。它通常预测得很好，因为许多代码在循环中的实际行程从来不是0次。（即，它可能是do{}while，但编译器没有设法证明它。）

跳到底部也意味着核心不能开始工作在真正的环体，直到前端追逐两个采取的分支之后。

在一些复杂循环条件的情况下，这样编写最容易，而且性能影响很小，但编译器经常避免这样做。

考虑memchr循环或strchr循环：它们必须在缓冲区的末尾（基于计数）或隐式长度字符串的末尾（0字节）停止。但如果在循环结束前找到匹配项，他们还必须break退出循环。

所以你经常会看到这样的结构

do {
    if () break;

    blah blah;
} while(condition);

或者只是底部附近的两个条件。理想情况下，您可以使用同一实际指令测试多个逻辑条件（例如，使用sub eax、5/CMP eax、20/ja.outside_range、用于范围检查的unsigned compare trick或将其与或组合以检查4条指令中任一情况的字母字符的5 ，但有时您不能并且只需要使用 if()break样式的循环退出分支以及正常的向后取分支。

>

Matt Godbolt的CppCon2017演讲：“我的编译器最近为我做了什么？打开编译器的盖子“，以获得查看编译器输出的好方法（例如，什么样的输入提供有趣的输出，以及初学者阅读x86 asm的入门）。相关：如何从GCC/CLANG组件输出中去除“噪音”？

现代微处理器90分钟指南！详细介绍超标量流水线CPU，主要是与体系结构无关的。非常好。解释了指令级的并行性和诸如此类的东西。

x86标签wiki中的其他链接，包括Intel的优化手册。此外，我的几个答案（链接在标签wiki中）中有Agner在他对最近的微架构的测试中遗漏的东西（比如SnB上的微融合索引寻址模式的非层压，以及Haswell+上的部分寄存器）。

为什么mulss在Haswell上只需要3个周期，不同于Agner的指令表？（使用多个累加器展开FP循环）：如何使用多个累加器来隐藏还原循环的延迟（如FP点积）。

第七讲：循环转换（也在archive.org上）。编译器对循环做了很多很酷的东西，使用C语法来描述ASM。

https://en.wikipedia.org/wiki/loop_optimization

有点离题：

>

内存带宽几乎总是很重要的，但大多数现代x86 CPU上的单核无法使DRAM饱和，这一点并不广为人知，甚至在多核至强上也是如此，因为单线程带宽比具有双通道内存控制器的四核要差。

关于内存，每个程序员都应该知道些什么？（在乌尔里希·德雷珀那篇著名的优秀文章中，我的回答中有关于什么已经改变了，什么仍然相关的评论。）