C++编译器中的优化

2019年11月12日第17卷第5期编译器是将高级的、更容易编写的代码转化为高效的机器代码以供计算机执行的必备技术。他们在做这件事上的老练经常被忽视。您可能会花费大量时间仔细考虑算法和处理错误消息，但可能没有足够的时间来了解编译器能够做些什么。

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

这里显示的示例是用C或C++编写的，这是我使用过的最有经验的语言，但是很多这样的优化在其他编译语言中也是可用的。事实上，前端不可知的编译器工具包(如LLVM3)的出现意味着大多数这些优化在Rust、Swift和D等语言中以完全相同的方式工作。

我一直对编译器的能力着迷。我花了十年的时间制作视频游戏，在这场战争中，每个CPU周期都很重要，以便在屏幕上获得比我们的竞争对手更多的精灵、爆炸或复杂的场景。编写自定义程序集，并读取编译器输出以了解其功能，这是本课程的常规做法。

快进五年后，我在一家贸易公司工作，换掉了精灵和多边形，以便快速处理金融数据。就像以前一样，了解编译器对代码所做的事情有助于了解我们编写代码的方式。

显然，编写良好、可测试的代码极其重要-尤其是当该代码每秒可能进行数千笔金融交易时。速度最快固然很好，但没有错误更重要。

在2012年，我们讨论了哪些新的C++11特性可以被采纳为可接受的编码实践规范的一部分。当每一毫微秒都很重要时，您希望能够就如何最好地编写代码而不影响性能向程序员提供建议。在试验代码如何使用新特性(如AUTO、lambdas和基于范围的)的同时，我编写了一个shell脚本(A)来持续运行编译器并显示其过滤后的输出：

$g++/tmp/test.cc-O2-c-S-o--MASM=intel\t|c++filt\t|grep-ve'；\s+\.'；

事实证明，这对回答所有这些问题非常有用，以至于那天晚上我回家创建了Compiler Explorer。1个。

多年来，我一直对编译器将我们的代码转化为汇编码艺术作品所做的努力感到惊讶。我鼓励所有的汇编语言程序员学习一点汇编语言，以便欣赏他们的编译器为他们做的事情。即使你不会自己写，能读也是一项有用的技能。

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

这并不是深入研究编译器优化，但是了解编译器使用的一些概念是很有用的。

许多优化都属于强度降低的范畴：采用昂贵的操作并将其转换为使用成本较低的操作。强度降低的一个非常简单的例子是采用涉及循环计数器(B)的乘法的循环：

即使在今天的CPU上，乘法也比更简单的算术慢一点，因此编译器会将该循环重写为类似(C)：

for(int iTimes1234=0；iTimes1234<；100*1234；i+=1234){iTimesFunc(ITimes1234)；}。

这里，强度降低采用了一个涉及乘法的循环，并将其转化为仅使用加法的一系列等价操作。

强度降低的形式有很多种，更多的形式出现在后面给出的实际例子中。

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

·持续折叠。编译器接受其值可以在编译时计算的表达式，并直接用计算结果替换它们。

·持续传播。编译器跟踪值的来源，并利用知道某些值对于所有可能的执行都是常量的优势。

·公共子表达式消除。重复的计算被重写为计算一次并复制结果。

·删除死代码。在许多其他优化之后，可能存在对输出没有影响的代码区域，这些区域可以删除。这包括其值未使用的加载和存储，以及整个函数和表达式。

·指令选择。这并不是这样的优化，但是当编译器获取程序的内部表示并生成CPU指令时，它通常有大量等价的指令序列可供选择。做出正确的选择需要编译器对其目标处理器的体系结构有很多了解。

·循环不变代码移动。编译器识别出循环内的某些表达式在该循环的持续时间内是恒定的，并将它们移出循环。最重要的是，编译器能够将循环不变条件检查移出循环，然后复制循环体两次：如果条件为真，则复制一次；如果条件为假，则复制一次。这可以导致进一步的优化。

·窥视孔优化。编译器采用较短的指令序列，并查找这些指令之间的局部优化。

·删除尾部呼叫。以调用自身结束的递归函数通常可以重写为循环，从而减少调用开销并减少堆栈溢出的机会。

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

让我们看一个示例(D)，计算通过某些测试的向量的元素数(由GCC编译，优化级别3，https://godbolt.org/z/acm19_count1)：

int count(const Vector<；int>；&；vec){t_t；int numPassed=0；for(size_t i=0；i<；vec.size()；++i){t_t_i=0；++i){testFunc(vec[i])){testFunc(vec[i])}{}返回NumPassed；**numPassed++；}返回NumPasss；}。

如果编译器没有关于testFunc的信息，它将生成一个内部循环，如(E)：

.L4：vmov EDI，DWORD PTR[RDX+RBX*4]；读取vec的第RBX&39；第39个元素；读取vc的第39个元素；读取vc的第39个元素；读取vc的第39个元素；调用测试函数emov RDX、QWORD PTR；(内联向量：Operator[])调用testFunc(Int)；调用测试函数Emov RDX、QWORD PTR[inline Vector：OPERATOR[])；调用测试函数Emov RDX，QWORD PTR[。重读向量基址指针cmp al，1度；重读向量基址指针cmp al；1度；重读向量基址指针cmp al；重读向量基址指针cmp al；1度；重读向量基址指针cmp al；重读向量基址指针cmp al；重读向量基址指针sbb r12d，-1%；重读向量基址指针cmp al，1度；重读向量基址指针cmp al；重读向量基址指针cmp al，1度；重读向量基址指针；测试结果为false，则添加0。递增循环计数器SUB RAX，RDX从BEGIN中减去END，从BEGIN中减去END。*sar rax，2，*；(内嵌向量：：size())*CMP RBX，rax*；循环计数器大小相等()吗？JB.L4的循环计数器大小相等吗？如果不相等，则循环。

要理解这段代码，知道std：：Vector<；>；包含一些指针是很有用的：一个指向数据的开头；一个指向数据的结尾；还有一个指向当前分配的存储的结尾(F)。向量的大小不是直接存储的，它隐含在BEGIN()和END()指针之间的差异中。注意，对Vector<；>；：：size()和Vector<；>；：：Operator[]的调用已经完全内联。

在汇编代码(E)中，eBP指向向量对象，因此BEGIN()和END()指针分别是QWORD PTR[RBP+0]和QWORD PTR[RBP+8]。

编译器完成的另一个巧妙技巧是删除任何分支：您可以合理地预期if(testFunc(.))。会变成比较和分支。在这里，编译器执行比较cmp al，1，如果testFunc()返回false，则设置处理器进位标志，否则将其清除。然后，SBB r12d，-1指令用BORKE减去-1，这相当于进位，这也使用进位标志。这有预期的副作用：如果进位是清零的(testFunc()返回true)，它会减去-1，这与加1相同。如果设置了进位，它会减去-1+1，这对值没有任何影响。如果处理器不容易预测分支，则避免分支在某些情况下可能是有利的。

编译器在每次循环迭代时都会重新加载BEGIN()和END()指针，这似乎令人惊讶，实际上，编译器每次都会重新派生size()。但是，编译器被迫这样做：它不知道testFunc()做什么，必须做最坏的打算。也就是说，它必须假设对testFunc()的调用可能会导致vec被修改。这里的const引用不允许任何额外的优化，原因有两个：testFunc()可能有对vec的非常数引用(可能是通过全局变量)，或者testFunc()可能会丢弃const。

但是，如果编译器可以看到testFunc()的主体，并且由此知道它实际上没有修改vec(G)，那么情况就非常不同了(https://godbolt.org/z/acm19_count2)：

.L6：Emov EDI，DWORD PTR[RDX]；读取NEXT VALUE以调用testFunc(Int)和TestFunc；使用CMP al调用testFunc，1%调用TestFunc，1%将其用于；检查SBB R8D的返回码，-1%；如果为真，则添加1；否则，添加0；如果为真，则添加RDX，4%；如果是，则添加RDX；如果为真，则添加0；如果为True，则添加0；如果为True，则添加0。移动到下一个元素：CMP RCX，RDX和；我们是否已经走到尽头了？Jjne.L6：；如果没有，就循环；如果没有，我们将继续；如果没有，我们将循环；如果没有，我们将继续；如果没有，我们将循环到；如果没有，我们就会循环。

在这种情况下，编译器已经意识到向量BEGIN()和END()在循环操作期间是恒定的。因此，它已经能够意识到对size()的调用也是常量。有了这些知识，它将这些常量提升出循环，然后将索引操作(vec[i])重写为指针遍历，从Begin()开始，一次向上遍历一个int以结束()。这极大地简化了生成的程序集。

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

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

有趣的是，即使在不知道testFunc()不会修改vec(https://godbolt.org/z/acm19_count3).)的情况下，在初始示例中使用Range-For也会产生最佳组装。这是因为Range-For被定义为将Begin()和End()放入局部变量(H)的源代码转换：

{*AUTO__BEGIN=BEGIN(Vec)；*AUTO_END==end(Vec)；for(auto__it=__Begin；__it！=__End；+__it)|{_Begin=Begin(Vec)；AUTO__END==End(Vec)；AUTO__END==end(Vec)；__end==end(Vec)；for(auto__it=__Begin；__it！=__end；+__it)如果(testFunc。

综合考虑，如果您需要使用RAW循环，最好使用现代的range-for样式：即使编译器看不到调用的函数体，它也是最佳的，而且对读者来说更清晰。可以说，更好的做法是使用STL的COUNT_IF函数为您完成所有工作：编译器仍然会生成最佳代码(https://godbolt.org/z/acm19_count4).。

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

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

尽管这是一项相对成熟的技术(我在21世纪初在最初的Xbox上使用了LTCG)，但我感到惊讶的是，使用LTO的项目如此之少。在一定程度上，这可能是因为程序员无意中依赖了未定义的行为，只有当编译器获得更高的可见性时，这种行为才会变得明显：我知道我曾经犯过这种错误。

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

了解到-直到最近-关于在现代CPU上可以做的最昂贵的事情是整数除法，这可能会让人感到惊讶。除法比加法贵50倍以上，比乘法贵10倍以上。(在英特尔发布Cannon Lake微体系结构之前，这一点是正确的，64位除法的最大延迟从96个周期减少到18.6个周期，仅比加法慢约20倍，比乘法贵5倍。)

值得庆幸的是，编译器作者在用常量除法时有一些减少强度的诀窍。我确信我们都已经意识到，被2的幂除法通常可以被逻辑右移所取代--请放心，编译器会为您做这件事的。我建议不要在您的代码中编写>；>；来做除法；让编译器为您解决这个问题。它更清晰，编译器也知道如何正确地计算有符号的值：整数除法向零截断，而自动向下移位向负无穷截断。

但是，如果您重新除以非2次方的值(J)呢？你是不是运气不好？

DivideByThree(无签名整数)：0mov eax，edi=；eax=edi=edi；mov edi，2863311531；edi=0xaaaaaab，rdi；>；=33 rret；rax=rax*0xaaaaaab；shr rax；33；rx>；=33 rret；rx>；>；=33 rret。

看不到任何分割指令。只是一个移位，然后乘以一个奇怪的大型常量：32位无符号输入值乘以0xaaaaaaab，得到的64位值向下移位33位。编译器用更便宜的定点倒数乘法取代了除法。本例中的固定点位于第33位，常量是用这些项表示的三分之一(实际上是0.33333333337213844)。编译器具有一种算法，用于确定适当的固定点和常量以实现除法，同时保持与实际除法操作相同的舍入，在输入范围内具有相同的精度。有时，这需要许多额外的运算-例如(L)除以1023时(https://godbolt.org/z/acm19_div1023)：

除以1023(无符号整型)：eax，edi，imul rax，rax，4198405，shr rax，32，subedi，eax，shr edi，add eax，edi，shr eax，9。

简而言之，您可以依靠编译器在优化编译时已知常量的除法方面做得很好。

您可能会想：为什么这是如此重要的优化？不管怎么说，人们实际执行整数除法的频率是多少？与其说问题在于除法本身，不如说在于相关的模运算，该运算经常用于散列映射实现中，作为将散列值带入散列桶数目范围的操作。

了解编译器在这里可以做什么可以导致有趣的散列映射实现。一种方法是使用固定数量的存储桶，以允许编译器在不使用昂贵的除法指令的情况下生成完美模运算。

大多数散列映射都支持重新散列到不同数量的存储桶。天真地，这将导致模数具有一个只有在运行时才知道的数字，从而迫使编译器发出缓慢的除法指令。实际上，这正是GCC libstdc++库实现std：：unordered_map所做的事情。

clang'；的libc++更进一步：它检查存储桶的数量是否为2的幂，如果是，则跳过除法指令，转而执行逻辑AND运算。拥有2的幂存储桶计数很诱人，因为它使得模运算速度很快，但是为了避免过多的冲突，它依赖于具有良好的散列函数。质数桶计数即使对于简单的散列函数也能提供良好的抗冲突性。

有些库(如Boost：：MULTI_INDEX)更进一步：它们不存储存储桶的实际数量，而是使用固定数量的素数存储桶计数(M)。

size_t Reduce(size_t hash，int bucketCountIndex){*Switch(TableSizeIndex)**开关(TableSizeIndex)*案例0：返回哈希%7；*案例1：返回哈希%17；*案例2：返回哈希%37；*：//依此类推.。{##**}}。

这样，对于所有可能的哈希表大小，编译器都会生成完美的模代码，唯一的额外开销就是分派到switch语句中的正确代码段。

GCC 9有一个巧妙的技巧(N)，可以用2的非幂(https://godbolt.org/z/acm19_multof3)：)来检查可除性。

可被3整除(无符号整型)：jimul edi，edi，-1431655765；edi=edi*0xaaaaaab，cmp edi，1431655765；比较0x55555555，setbe al，cmp edi；*；如果edi<；=0x55555555，则返回1；如果edi<；=0x55555555，则返回1；如果edi<；=0x55555555，则返回1。

丹尼尔·勒迈尔(Daniel Lemire)在他的博客中很好地解释了这种明显的巫术。2顺便说一句，在运行时也可以使用这种整数除法技巧。如果您需要将多个数字除以相同的值，您可以使用诸如libdivide这样的库。5个

您有多少次在想，这个整数中有多少设置位？可能不会那么频繁。但事实证明，这个简单的操作在许多情况下都出人意料地有用。例如，计算汉明距离。

.