ACM通信

实践

c++编译器中的优化

作者:Matt Godbolt
ACM通信，2020年2月，第63卷第2期，第41-49页
10.1145 / 3369754
评论(1)

编译器是一种必要的技术，可以将高级的、易于编写的代码转换为计算机执行的高效机器代码。他们在这方面的老练往往被忽视。您可能会花大量时间仔细考虑算法和处理错误消息，但可能不会花足够的时间研究编译器能够做什么。

本文介绍了一些编译器和代码生成的概念，然后介绍了编译器为您完成的一些非常令人印象深刻的转换壮举，并对我最喜欢的优化进行了一些实际演示。我希望您能够了解编译器可以为您做哪些类型的优化，以及如何进一步探索这个主题。最重要的是，您可能会学会喜欢查看汇编输出，并学会尊重编译器中的工程质量。

这里显示的示例是用C或c++编写的，这是我最熟悉的两种语言，但许多优化也可以在其他编译语言中使用。实际上，像LLVM这样的前端不可知编译器工具包的出现^3.意味着这些优化在Rust、Swift和D等语言中以完全相同的方式工作。

我一直着迷于编译器的能力。我花了10年时间制作电子游戏，每个CPU周期都与战争有关，以便在屏幕上获得比竞争对手更多的精灵、爆炸或复杂场景。编写定制程序集，并读取编译器输出以查看它的能力，这是意料之中的事情。

5年过去了，我在一家贸易公司工作，为了快速处理财务数据，我放弃了精灵和多边形。就像以前一样，知道编译器对代码做了什么有助于了解我们编写代码的方式。

显然，编写良好的、可测试的代码是非常重要的，特别是如果该代码具有每秒进行数千次金融交易的潜力。速度快是很好，但没有bug更重要。

2012年，我们在讨论c++ 11的哪些新特性可以被采纳为可接受的编码实践的一部分。当每一纳秒都很重要时，您希望能够向程序员提供建议，告诉他们如何在不影响性能的情况下最好地编写代码。在试验代码如何使用新特性时，例如汽车， lambdas和基于范围的为，我写了一个shell脚本(一)持续运行编译器并显示其过滤后的输出。事实证明，在回答所有这些“如果……会怎样”的问题时，这是非常有用的，以至于那天晚上我回到家，创建了编译器浏览器。¹

---

许多优化都属于强度降低的范畴:采用昂贵的操作，并将它们转换为使用成本较低的操作。

---

多年来，我一直惊讶于编译器为了把我们的代码变成汇编代码艺术所做的努力。我鼓励所有编译语言程序员学习一点汇编知识，以便理解编译器为他们所做的工作。即使你自己不会写，能够阅读也是一项有用的技能。

这里显示的所有汇编代码都适用于64位x86处理器，因为这是我最熟悉的CPU，也是最常见的服务器架构之一。这里显示的一些示例是特定于x86的，但实际上，许多类型的优化也适用于其他体系结构。此外，我只讨论GCC和Clang编译器，但是来自Microsoft和Intel的编译器上也有同样聪明的优化。

回到顶部

优化101

本文还远远没有深入讨论编译器优化，但是了解编译器使用的一些概念是有用的。在这些页面中，您将注意到一个正在运行的专栏，其中包含所讨论的流程和操作的脚本示例和说明。所有的都由相应的链接(信)．

许多优化都属于强度降低将昂贵的操作转变为使用便宜的操作。一个非常简单的强度降低的例子是使用一个包含循环计数器的乘法循环，如图所示(b)．即使在今天的cpu上，乘法运算也比简单的算术运算要慢一些，所以编译器会将这个循环重写为(c)．

在这里，强度折减法将一个包含乘法的循环转化为只使用加法的等效操作序列。有许多形式的强度折减，更多的显示在后面给出的实际例子。

另一个关键优化是内联在这种方法中，编译器用函数体替换对函数的调用。这消除了调用的开销，并且常常解锁进一步的优化，因为编译器可以将组合代码作为单个单元进行优化。稍后您将看到大量这方面的例子。

其他优化类别包括:

• 常数合并。编译器接受其值可以在编译时计算的表达式，并直接用计算结果替换它们。
• 不断的传播。编译器跟踪值的来源，并利用知道某些值对于所有可能的执行都是常量的优势。
• 公共子表达式消除。重复的计算被重写为一次计算并复制结果。
• 死代码删除。在许多其他优化之后，代码中可能有一些区域对输出没有影响，这些区域可以被删除。这包括值未使用的load和store，以及整个函数和表达式。
• 指令选择。这并不是优化，但当编译器使用程序的内部表示并生成CPU指令时，它通常有大量等价的指令序列可供选择。要做出正确的选择，编译器需要对它所瞄准的处理器的体系结构有很多了解。
• 循环不变代码移动。编译器会识别出循环中的某些表达式在循环期间是常量，并将它们移出循环。在此基础上，编译器能够将循环不变条件检查移出循环，然后复制循环主体两次:一次是在条件为真时，一次是在条件为假时。这可以导致进一步的优化。
• 窥孔优化。编译器接受短指令序列，并查找这些指令之间的局部优化。
• 尾呼叫移除。以调用自身结束的递归函数通常可以重写为循环，从而减少调用开销并减少堆栈溢出的机会。

帮助编译器优化的黄金法则是确保它拥有尽可能多的信息来做出正确的优化决策。信息的一个来源是您的代码:如果编译器可以看到更多的代码，它就能够做出更好的决策。另一个信息来源是您使用的编译器标志:告诉编译器您所瞄准的确切CPU架构会产生很大的不同。当然，编译器拥有的信息越多，它运行的时间就越长，因此这里需要达到一个平衡。

让我们看一个例子(d)，计算向量中通过某种测试的元素数量(用GCC编译，优化级别3;https://godbolt.org/z/acm19_count1)．如果编译器没有关于testFunc，它将生成一个内部循环，如(e)．

要理解这段代码，知道astd::向量< >包含一些指针:一个指向数据的开头;一到数据末尾;一个到当前分配的存储的末尾(f)．向量的大小不直接存储，它隐含在开始()和结束()的指针。注意，调用向量< >::大小（）和vector<>::operator[]已经完全内联了。

在程序集代码(e)中，ebp指向向量对象，而开始()而且结束()因此指针是[rbp+0]而且QWORD PTR [rbp+8],分别。

编译器做的另一个巧妙的技巧是删除任何分支:您可能会合理地期望if(testFunc(…))会变成一个比较和分支。这里由编译器进行比较CMP al, 1，如果设置处理器进位标志testFunc ()返回false，否则会清除它。的SBB r12d， -1然后指令用borrow减去-1，这个减法相当于carry，它也使用carry标志。这有预期的副作用:如果进位是清晰的(testFunc()返回true)，它减去－1，这和加法是一样的1．如果进位设置了，则减去-1 + 1，对数值没有影响。在某些情况下，如果处理器不容易预测分支，那么避免分支是有利的。

编译器重新加载开始()而且结束()指向每个循环迭代，实际上它重新派生尺寸()每次都是。然而，编译器是被迫这样做的:它不知道是什么testFunc ()做并且必须做最坏的打算。也就是说，它必须假定调用testFunc ()可能导致vec被修改。的常量这里的引用不允许任何额外的优化，原因如下:testFunc ()可能有一个对vec的非const引用(可能通过一个全局变量)，或者testFunc ()可能会丢弃const。

但是，如果编译器可以看到testFunc ()，由此可知，它实际上并没有修改vec(g)，故事就很不一样了。https://godbolt.org/z/acm19_count2)．

在这种情况下，编译器已经意识到向量的开始()而且结束()在循环运行期间是恒定的。正因为如此，人们才得以意识到这一呼唤尺寸()也是一个常数。有了这些知识，它将这些常量从循环中提出来，然后重写索引操作(vec(我))是指针走路，开始于开始()每次上升一int到结束()．这极大地简化了生成的程序集。

在本例中，我为编译器提供了一个主体testFunc ()但将其标记为不可内联(一个GNU扩展)，以孤立地演示这种优化。在更实际的代码库中，编译器可以内联testFunc ()如果它认为这是有益的。

启用此优化而不向编译器公开函数体的另一种方法是将其标记为[[gnu:纯]](另一种语言扩展)。这向编译器保证，该函数完全是其参数的函数，没有副作用。

有趣的是，在最初的示例中使用range-for生成了最优组装，即使不知道这一点testFunc ()不修改vec（https://godbolt.org/z/acm19_count3)．这是因为范围定义为放置开始()而且结束()到局部变量中，如(h)它被解释为(我)．

综合考虑，如果你需要使用“原始”循环，现代范围样式是首选:即使编译器看不到被调用函数的主体，它也是最优的，而且对读者来说更清晰。可以说更好的方法是使用STLcount_if函数为您完成所有工作:编译器仍然生成最佳代码(https://godbolt.org/z/acm19_count4)．

在传统的一次一个翻译单元的编译模型中，函数体通常对调用站点隐藏，因为编译器只看到它们的声明。链接时间优化(LTO，也称为链接时间代码生成的LTCG)可用于允许编译器查看跨翻译单元边界的内容。在LTO中，单个翻译单元被编译成中间形式，而不是机器代码。在链接过程中，当整个程序(或动态链接库)是可见的，机器代码就会生成。编译器可以利用这一点进行跨翻译单元的内联，或者至少使用关于被调用函数的副作用的信息进行优化。

为优化构建启用LTO通常是一个很好的胜利，因为编译器可以看到您的整个程序。现在，我依靠LTO将更多的函数体移出头文件，以减少耦合、编译时间，并为调试构建和测试构建依赖关系，同时仍然提供最终构建所需的性能。

尽管LTO是一种相对成熟的技术(我在21世纪初的Xbox上使用LTCG)，但我惊讶地发现使用LTO的项目如此之少。在某种程度上，这可能是因为程序员无意中依赖于未定义的行为，而这些行为只有在编译器变得更加可见时才会变得明显:我知道我为此感到内疚。

回到顶部

最喜欢的优化示例

多年来，我收集了许多有趣的真实世界的优化，既有优化我自己代码的第一手经验，也有在Compiler Explorer上帮助别人理解他们的代码的经验。下面是我最喜欢的一些例子，说明编译器是多么的聪明。

整数除以常数。你可能会惊讶地发现，直到最近，你在现代CPU上所能做的最昂贵的事情是整数除法。除法比加法贵50多倍，比乘法贵10多倍。(这在英特尔发布Cannon Lake微架构之前是正确的，在该微架构中，64位除的最大延迟从96个周期减少到18个周期。6这只比加法慢20倍左右，比乘法贵5倍。)

值得庆幸的是，编译器作者在除以常数时有一些降低强度的技巧。我相信我们都已经意识到，除以2的幂通常可以被逻辑右移所取代，我保证编译器会为你做到这一点。我建议不要在你的代码中写>>来做除法;让编译器为您计算。它更清晰，编译器也知道如何正确地解释有符号值:整数除法将截断为零，而自身向下移动将截断为负无穷。

但是，如果要除以一个非2的幂值，会怎样呢(j)？你运气不好吗?幸运的是，编译器再次支持您。代码编译为(k)（https://godbolt.org/z/acm19_div3)．

眼前没有除法指令。只是一个移位，和一个乘以一个奇怪的大常数:32位无符号输入值乘以Oxaaaaaaab，得到的64位值向下移动33位。编译器用更便宜的点倒数乘法取代了除法。本例中的固定点在位33处，常数的三分之一用这些术语表示(它实际上是0.33333333337213844)。编译器有一种算法，用于确定适当的不动点和常数来实现除法，同时在输入范围内保持与实际除法操作相同的舍入和相同的精度。有时这需要一些额外的操作，例如，除1022，如(l，https://godbolt.org/z/acm19_div1023)．

这个算法众所周知，在一本优秀的书中有大量的记录，黑客的喜悦．⁸

简而言之，您可以依赖编译器来优化除以编译时已知常数的除法。

您可能会想:为什么这是一个如此重要的优化?整数除法的实际执行频率是多少?问题不在于除法本身，而在于相关的模操作，它经常在哈希映射实现中用作将哈希值带入哈希桶数量范围的操作。

知道编译器在这里可以做什么可以得到有趣的哈希映射实现。一种方法是使用固定数量的桶来允许编译器生成完美的模运算，而不使用昂贵的除法指令。

大多数哈希映射支持重新哈希到不同数量的桶。天真地说，这将导致模数只有在运行时才知道，迫使编译器发出一个缓慢的除法指令。实际上，这正是GCC libstdc++库实现的功能Std::unordered _ map所做的事。

Clang的libc++更进一步:它检查桶的数量是否为2的幂，如果是，则跳过除指令而使用逻辑指令和．拥有一个2的桶计数是很有吸引力的，因为它使模运算更快，但为了避免过多的冲突，它依赖于一个好的哈希函数。质数桶计数即使对于简单的哈希函数也能提供良好的抗碰撞性能。

---

您可以依赖编译器来优化除以编译时已知常数的除法。

---

一些库，例如Boost:: multi_ index更进一步:它们使用固定数量的质数桶计数，而不是存储桶的实际数量(m)．

这样，对于所有可能的哈希表大小，编译器会生成完美的模数代码，惟一额外的开销是分派到开关声明。

GCC 9有一个巧妙的技巧(n)用于检查能否被非二的幂数整除(https://godbolt.org/z/acm19_multof3)并编译到(o)．

Daniel Lemire在他的博客中很好地解释了这种明显的巫术。²说句题外话，在运行时也可以做这种整数除法。如果需要将多个数字除以相同的值，可以使用诸如libdivide．⁵

回到顶部

计数集合位

你是否经常想知道，这个整数中有多少位集合?可能不会经常发生。但事实证明，这个简单的操作在很多情况下都非常有用。例如，计算两个bitset之间的Hamming距离，处理稀疏矩阵的填充表示，或者处理向量运算的结果。

你可以写一个函数来计算位数，如(p)．值得注意的是位操作“技巧”A &= (A - 1);，它清除最底部的设置位。向自己证明它在纸上是如何工作的是一件有趣的事。试一试。

当以Haswell微架构为目标时，GCC 8.2将此代码编译为中所示的程序集(问)（https://godbolt.org/z/acm19_bits)．注意GCC是如何巧妙地找到BLSR取下底部设置位的位操作指令。整洁的,对吧?但是没有Clang 7.0那么聪明(右)．

这个操作非常常见，大多数CPU架构上都有一条指令可以一次性完成它:POPCNT(总体计数)。Clang非常聪明，可以在c++中使用整个循环并将其简化为一条指令。这是一个很好的指令选择示例:Clang的代码生成器识别这种模式，并能够选择完美的指令。

我在这里实际上有点不公平:GCC 9也实现了这一点(年代)，实际上显示了轻微的差异。乍一看，这似乎不是最优的:究竟为什么要写一个零值，却要立即用“population count”指令的结果覆盖它popcnt吗?

一个小研究提出了英特尔CPU勘误表SKL029: "POPCNT指令执行时间可能比预期的要长“CPU有bug!虽然popcnt指令完全覆盖输出寄存器eax，它被错误地标记为依赖于eax的先验值。这限制了CPU调度指令的能力，直到之前写入eax的任何指令完成，即使它们没有影响。

GCC的方法是打破对的依赖eax:CPU识别Xor eax, eax作为打破依赖性的习惯用法。任何事先的指示都不会影响之后的eaxXor eax, eax，和popcnt能否在其输入操作数edi是可用的。

这只影响Intel cpu，并且似乎在Cannon Lake微架构中得到了修复，尽管GCC仍然会发出信号XOR当瞄准它的时候。

回到顶部

链接条件

也许您从来没有需要计算整数中的集合位的数量，但是您可能编写过类似于中的示例的代码(t)．本能地，我认为代码生成将充满比较和分支，但Clang和GCC都使用了一个聪明的技巧来使代码相当高效。GCC 9.1的输出显示在(u；https://godbolt.org/z/acm19_conds）

编译器将这个比较序列转换为一个查找表。加载到rax中的神奇值是一个33位查找表，在返回true的位置有一个1位(' '的索引32、13、10和9，\ r \ n,而且\ t,分别)。shift和&然后取出第c位并返回。Clang生成的代码略有不同，但大致相同。这是强度降低的另一个例子。

看到这种优化，我感到非常惊喜。这绝对是那种在Compiler ExplorerI中调查之前我会手动编写的东西，假设我比编译器更了解。

一件不幸的事情是，我在做实验时注意到，对于GCC，至少比较的顺序会影响编译器进行这种优化的能力。如果你改变比较的顺序r \而且\ n， GCC生成代码(v)．

和的比较有一个很巧妙的技巧r \而且\ t，但这似乎比之前生成的代码更糟糕。也就是说，Quick Bench上的一个简单基准测试表明，基于比较的版本在可预测的紧密循环中可能会更快一点。^一个谁说过这很简单?

回到顶部

求和

有时候你需要把一堆东西加起来。编译器非常擅长利用大多数cpu中可用的向量化指令，所以即使是像(w)被转换成核心循环看起来像(x)（https://godbolt.org/z/acm19_sum)．

编译器能够处理每条指令的8个值，方法是将总数分为每条指令的8个小计。最后，它将这些小计相加，得到最终的总数。就好像代码被重写了让你看起来更像(y)的例子。

只需将编译器的优化级别设置在足够高的位置，并选择一个适当的CPU体系结构作为目标，向量化就会发挥作用。太棒了!

这确实依赖于这样一个事实:将总数分离为单独的小计，然后在结束时相加相当于按程序指定的顺序将它们相加。对于整数，这是非常正确的;但对于浮点数据类型，情况并非如此。浮点运算是没有关联的:(a+b)+c和a+(b+c)是不一样的，因为加法运算的精度取决于两个输入的相对大小。

不幸的是，这意味着改变向量< int >做一个向量<飘>不会产生您理想中想要的代码。编译器可以使用一些向量操作(它可以一次对8个值进行平方)，但它被迫串行地对这些值求和，如(z；https://godbolt.org/z/acm19_sumf)．

这是不幸的，而且没有简单的解决办法。如果您绝对确定加法的顺序在您的情况下并不重要，您可以给GCC一个危险的(但有趣的名称)-funsafe-math-optimizations国旗。这让它生成了这个漂亮的内部循环，如(一个“；https://godbolt.org/z/acm19_sumf_unsafe)．

神奇的东西:一次处理8个浮点数，使用一个指令来累积和平方。缺点是潜在的无限精度损失。此外，GCC不允许你只对你需要的函数打开这个特性，它是一个编译单元标志。Clang至少可以让您在源代码中控制它#pragma Clang fp合同。

在进行这些优化的过程中，我发现编译器还有更多的锦囊妙计(b)．GCC为此生成相当简单的代码，并通过适当的编译器设置将使用前面提到的向量操作。然而，Clang生成的代码(c)；（https://godbolt.org/z/acm19_sum_up)．

首先，注意这里根本没有循环。通过运行生成的代码，你会看到Clang返回:

它用和的闭合形式的通解代替了循环的迭代。解决方案与我自己天真地写的不同:

这大概是Clang使用的通用算法的结果。

进一步的实验表明，Clang足够聪明，可以优化许多这种类型的循环。Clang和GCC都以允许这种优化的方式跟踪循环变量，但只有Clang选择生成封闭形式的版本。并不总是更少的工作:对于较小的值x封闭形式解决方案的开销可能不仅仅是循环。Krister Walfridsson在一篇博文中详细阐述了这是如何实现的。⁷

另外值得注意的是，为了进行这种优化，编译器可能依赖于无符号整数溢出为未定义行为。因此，它可以假定您的代码不能传递会溢出结果的值x(在本例中是65536)。如果Clang不能做出这样的假设，它有时就无法找到一个封闭的解决方案(https://godbolt.org/z/acm19_sum_fail)．

回到顶部

Devirtualization

尽管传统的基于虚拟函数的多态似乎有点失宠了，但它仍有一席之地。无论是允许真正的多态行为，还是为可测试性添加一个“缝”，还是允许未来的可扩展性，通过虚函数的多态都是一个方便的选择。

正如我们所知，虚函数很慢。果真如此吗?让我们看看它们是如何影响之前的平方和例子的(d)．

当然，这还不是多态性的。快速运行编译器可以看到相同的高度向量化的程序集(https://godbolt.org/z/acm19_poly1)．

的前面添加virtual关键字int运营商()应该会导致一个更慢的实现，充满了间接调用，对吧?嗯，有点(https://godbolt.org/z/acm19_poly2)．现在发生的事情比以前多得多，但在这个循环的核心，可能有一些令人惊讶的东西(e)．

现在的情况是GCC打了个赌。的一个实现变换类，则很可能是所使用的那个实现。它没有盲目地通过虚函数指针进行间接操作，而是将指针与唯一已知的实现进行了比较。如果匹配，那么编译器知道该怎么做:它内联变换::操作符()然后把它平方。

没错:编译器内联了一个虚调用。这太神奇了，当我第一次发现这一点时，我感到非常惊讶。这种优化称为投机devirtualization并且是编译器作者持续研究和改进的源泉。编译器也能够在LTO时去虚拟化，允许对可能的函数实现进行整个程序的确定。

然而，编译器错过了一个机会。注意，在循环的顶部，它每次都从虚函数表中重新加载虚函数指针。如果编译器能够注意到，如果被调用的函数没有改变Transform的动态类型，那么这个值将保持不变，那么这个检查就可以从循环中提升出来，这样循环中就根本没有动态检查了。编译器可以使用循环不变的代码运动将虚表检出循环。这时，其他优化就可以发挥作用了，整个代码可以用前面传递虚表检查时的向量化循环替换。

你可能会认为对象的动态类型不可能改变，这是可以理解的，但这实际上是标准允许的:一个对象可以在自身上放置新的位置，只要它在被销毁时返回到它的原始类型。但是，我建议您永远不要这样做。Clang有一个选项保证你永远不会在你的代码中做这样可怕的事情:-fstrict-vtable-pointers。

在我使用的编译器中，GCC是唯一一个理所当然地这样做的编译器，但Clang正在彻底改进它的类型系统，以更多地利用这种优化。⁴

c++ 11添加了最后一个说明符，以允许将类和虚方法标记为不被进一步覆盖。这为编译器提供了更多关于哪些方法可以从此类优化中受益的信息，在某些情况下甚至可能允许编译器完全避免虚调用(https://godbolt.org/z/acm19_poly3)．即使没有final关键字，有时分析阶段也能够证明正在使用特定的具体类(https://godbolt.org/z/acm19_poly4)．这种静态去虚拟化可以产生显著的性能改进。

回到顶部

结论

希望在阅读完本文之后，您会欣赏编译器为确保高效的代码生成所做的努力。我希望其中的一些优化会给您带来惊喜，并在您决定编写清晰、揭示意图的代码时将其考虑在内，并将其留给编译器来做正确的事情。我强调了这样一个观点:编译器拥有的信息越多，它就能做得越好。这包括允许编译器一次查看更多的代码，以及向编译器提供关于您所瞄准的CPU体系结构的正确信息。在给编译器提供更多信息时需要做一个权衡:它会使编译变慢。像链接时间优化这样的技术可以两全其美。

编译器中的优化在不断改进，间接调用和虚拟函数分派方面即将进行的改进可能很快会带来更快的多态性。我对编译器优化的未来感到兴奋。看看编译器的输出。

致谢作者想向Matt Hellige、Robert Douglas和Samy Al Bahra表示感谢，他们对本文的草稿提供了反馈。

相关文章
在queue.acm.org

C不是一门低级语言
David Chisnall
https://queue.acm.org/detail.cfm?id=3212479

未初始化的读取
罗伯特·c·西科德
https://queue.acm.org/detail.cfm?id=3041020

你对共享变量和内存模型一无所知
Hans-J。Boehm, Sarita V. Adve
https://queue.acm.org/detail.cfm?id=2088916

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2020 ACM, Inc.

---

评论

---

显示1评论