PDFC++ 编译器中的优化
一次实践之旅
Matt Godbolt
编译器是将高级、易于编写的代码转换为计算机可以执行的有效机器代码的必要技术。它们在这方面的精细程度常常被忽视。您可能会花费大量时间仔细考虑算法和解决错误消息，但可能没有足够的时间关注编译器能够做什么。
本文介绍了一些编译器和代码生成概念，然后重点介绍了一些编译器为您执行的非常令人印象深刻的转换壮举，并提供了一些我最喜欢的优化的实际演示。我希望您能了解可以期望编译器为您执行哪些类型的优化，以及您可能如何进一步探索该主题。最重要的是，您可能会学会喜欢查看汇编输出，并可能学会尊重编译器中工程的质量。
此处显示的示例使用 C 或 C++ 语言，这是我最有经验的语言，但许多这些优化也适用于其他编译语言。实际上，诸如 LLVM3 之类的与前端无关的编译器工具包的出现意味着大多数这些优化在 Rust、Swift 和 D 等语言中以完全相同的方式工作。
关于我
我一直对编译器的功能着迷。我花了十年时间制作视频游戏，在争夺比竞争对手在屏幕上获得更多精灵、爆炸或复杂场景的战争中，每个 CPU 周期都至关重要。编写自定义汇编代码，并阅读编译器输出以了解其功能，是司空见惯的事情。
快进五年，我来到一家贸易公司，将精灵和多边形换成了金融数据的快速处理。正如以前一样，了解编译器如何处理代码有助于指导我们编写代码的方式。
显然，编写良好、可测试的代码非常重要——特别是如果该代码有可能每秒进行数千笔金融交易。速度最快固然很棒，但没有错误甚至更重要。
2012 年，我们正在讨论可以将哪些新的 C++11 功能作为可接受的编码实践规范的一部分来采用。当每一纳秒都很重要时，您希望能够向程序员提供关于如何最好地编写代码的建议，而又不会与性能相悖。在试验代码如何使用诸如 auto、lambda 和基于范围的 for 等新功能时，我编写了一个 shell 脚本 (a) 来持续运行编译器并显示其过滤后的输出
$ g++ /tmp/test.cc -O2 -c -S -o - -masm=intel \
| c++filt \
| grep -vE '\s+\.'
(a)
事实证明，这在回答所有这些“如果……会怎样？”的问题中非常有用，以至于那天晚上我回家创建了 Compiler Explorer。1
多年来，我一直对编译器为了获取我们的代码并将其转换为汇编代码艺术品所付出的努力感到惊讶。我鼓励所有编译语言程序员学习一点汇编，以便欣赏他们的编译器为他们所做的事情。即使您自己无法编写，能够阅读它也是一项有用的技能。
此处显示的所有汇编代码都适用于 64 位 x86 处理器，因为这是我最熟悉的 CPU，也是最常见的服务器架构之一。此处显示的一些示例是 x86 特有的，但实际上，许多类型的优化也类似地适用于其他架构。此外，我仅涵盖 GCC 和 Clang 编译器，但同样巧妙的优化也出现在 Microsoft Visual Studio 和 Intel 的编译器中。
优化 101
这远非深入探讨编译器优化，但是了解编译器使用的一些概念是有用的。
许多优化都属于强度缩减的范畴：采用昂贵的操作并将其转换为使用不那么昂贵的操作。强度缩减的一个非常简单的示例是采用一个循环，其中包含涉及循环计数器的乘法 (b)
for (int i = 0; i < 100; ++i)
{
func(i * 1234);
}
(b)
即使在今天的 CPU 上，乘法也比简单的算术运算慢一些，因此编译器会将该循环重写为类似 (c) 的内容
for (int iTimes1234 = 0; iTimes1234 < 100 * 1234; i += 1234)
{
func(iTimes1234);
}
(c)
在这里，强度缩减采用了一个涉及乘法的循环，并将其转换为仅使用加法的等效操作序列。
强度缩减有很多形式，稍后给出的实际示例中会显示更多。
另一个关键优化是内联，其中编译器将对函数的调用替换为该函数的主体。这消除了调用的开销，并且通常解锁了进一步的优化，因为编译器可以将组合的代码作为一个单元进行优化。您将在稍后看到大量示例。
其他优化类别包括
• 常量折叠。编译器采用可以在编译时计算值的表达式，并将其直接替换为计算结果。
• 常量传播。编译器跟踪值的来源，并利用已知某些值对于所有可能的执行都是常量的事实。
• 公共子表达式消除。重复的计算被重写为计算一次并复制结果。
• 死代码消除。在许多其他优化之后，代码中可能存在对输出没有影响的区域，这些区域可以被删除。这包括值未使用的加载和存储，以及整个函数和表达式。
• 指令选择。这本身不是一种优化，但当编译器采用程序的内部表示并生成 CPU 指令时，它通常有一大组等效的指令序列可供选择。做出正确的选择需要编译器了解很多关于其目标处理器架构的知识。
• 循环不变代码移动。编译器识别出循环内的一些表达式在该循环的持续时间内是常量，并将它们移动到循环外部。除此之外，编译器还能够将循环不变条件检查移出循环，然后将循环体复制两次：一次在条件为真时，一次在条件为假时。这可能会导致进一步的优化。
• 窥孔优化。编译器采用指令的短序列，并在这些指令之间查找局部优化。
• 尾调用消除。以自身调用结束的递归函数通常可以重写为循环，从而减少调用开销并减少堆栈溢出的机会。
帮助编译器优化的黄金法则是确保它拥有尽可能多的信息来做出正确的优化决策。信息的一个来源是您的代码：如果编译器可以看到更多您的代码，它就能够做出更好的决策。信息的另一个来源是您使用的编译器标志：告诉您的编译器您要定位的确切 CPU 架构可能会产生很大的不同。当然，编译器拥有的信息越多，运行时间就可能越长，因此这里需要权衡。
让我们看一个示例 (d)，计算向量中通过某些测试的元素的数量（使用 GCC 编译，优化级别 3，https://godbolt.org/z/acm19_count1）
int count(const vector<int> &vec)
{
int numPassed = 0;
for (size_t i = 0; i < vec.size(); ++i)
{
if (testFunc(vec[i]))
numPassed++;
}
return numPassed;
}
(d)
如果编译器没有关于 testFunc 的信息，它将生成类似 (e) 的内部循环
.L4
mov edi, DWORD PTR [rdx+rbx*4] ; 读取 vec 的第 rbx 个元素
; (内联 vector::operator [])
call testFunc(int) ; 调用测试函数
mov rdx, QWORD PTR [rbp+0] ; 重新读取向量基指针
cmp al, 1 ; 测试结果为真吗？
mov rax, QWORD PTR [rbp+8] ; 重新读取向量结束指针
sbb r12d, -1 ; 如果为真则加 1，如果为假则加 0
inc rbx ; 递增循环计数器
sub rax, rdx ; 从开始指针减去结束指针...
sar rax, 2 ; 并除以 4 以获得 size()
; (内联 vector::size())
cmp rbx, rax ; 循环计数器等于 size() 吗？
jb .L4 ; 如果不是，则循环
(e)
要理解这段代码，了解 std::vector<> 包含一些指针是有用的：一个指向数据的开头；一个指向数据的结尾；以及一个指向当前分配的存储的结尾 (f)。向量的大小不是直接存储的，而是隐含在 begin() 和 end() 指针之间的差异中。请注意，对 vector<>::size() 和 vector<>::operator[] 的调用已完全内联。
template<typename T> struct _Vector_impl {
T *_M_start;
T *_M_finish;
T *_M_end_of_storage;
};
(f)
在汇编代码 (e) 中，ebp 指向向量对象，因此 begin() 和 end() 指针分别是 QWORD PTR [rbp+0] 和 QWORD PTR [rbp+8]。
编译器完成的另一个巧妙技巧是删除任何分支：您可能会合理地期望 if (testFunc(...)) 会变成比较和分支。在这里，编译器执行比较 cmp al, 1，如果 testFunc() 返回 false，则设置处理器进位标志，否则清除它。然后 sbb r12d, -1 指令执行带借位的减法 -1，这是进位的减法等效操作，也使用进位标志。这具有期望的副作用：如果进位被清除（testFunc() 返回 true），则它减去 -1，这与加 1 相同。如果进位被设置，则它减去 -1 + 1，这不会对值产生任何影响。如果分支不易被处理器预测，则在某些情况下避免分支可能是有利的。
编译器在每次循环迭代中重新加载 begin() 和 end() 指针，甚至每次都重新派生 size()，这似乎令人惊讶。但是，编译器被迫这样做：它不知道 testFunc() 做什么，并且必须假设最坏的情况。也就是说，它必须假设对 testFunc() 的调用可能会导致 vec 被修改。这里的 const 引用不允许任何额外的优化，原因有两个：testFunc() 可能具有对 vec 的非 const 引用（可能通过全局变量），或者 testFunc() 可能会强制转换掉 const。
但是，如果编译器可以看到 testFunc() 的主体，并由此知道它实际上不会修改 vec (g)，那么情况就大不相同了（https://godbolt.org/z/acm19_count2）
.L6
mov edi, DWORD PTR [rdx] ; 读取下一个值
call testFunc(int) ; 使用它调用 testFunc
cmp al, 1 ; 检查返回代码
sbb r8d, -1 ; 如果为真则加 1，否则加 0
add rdx, 4 ; 移动到下一个元素
cmp rcx, rdx ; 我们到达末尾了吗？
jne .L6 ; 如果没有，则循环
(g)
在这种情况下，编译器意识到 vector 的 begin() 和 end() 在循环操作期间是常量。因此，它能够意识到对 size() 的调用也是常量。有了这些知识，它将这些常量提升到循环之外，然后将索引操作 (vec[i]) 重写为指针遍历，从 begin() 开始，每次增加一个 int，直到 end()。这大大简化了生成的汇编代码。
在这个示例中，我为编译器提供了 testFunc() 的主体，但将其标记为不可内联（GNU 扩展），以单独演示此优化。在更实际的代码库中，如果编译器认为内联 testFunc() 有利，则可以内联它。
在不向编译器公开函数主体的情况下启用此优化的另一种方法是将其标记为 [[gnu::pure]]（另一个语言扩展）。这向编译器承诺该函数是纯函数——完全是其参数的函数，没有副作用。
有趣的是，即使不知道 testFunc() 不会修改 vec，在初始示例中使用 range-for 也会产生最佳汇编代码（https://godbolt.org/z/acm19_count3）。这是因为 range-for 被定义为源代码转换，它将 begin() 和 end() 放入局部变量 (h)
for (auto val : vec)
{
if (testFunc(val))
numPassed++;
}
(h)
被解释为 (i)
{
auto __begin = begin(vec);
auto __end == end(vec);
for (auto __it = __begin; __it != __end; ++__it)
{
if (testFunc(*__it))
numPassed++;
}
}
(i)
考虑到所有因素，如果您需要使用“原始”循环，则首选现代 range-for 样式：即使编译器看不到被调用函数的主体，它也是最佳的，并且对读者来说更清晰。可以说更好的是使用 STL 的 count_if 函数来完成所有工作：编译器仍然生成最佳代码（https://godbolt.org/z/acm19_count4）。
在传统的单次翻译单元编译模型中，函数主体通常对调用站点隐藏，因为编译器只看到了它们的声明。LTO（链接时优化；也称为 LTCG，链接时代码生成）可用于允许编译器跨翻译单元边界查看。在 LTO 中，各个翻译单元被编译为中间形式而不是机器代码。在链接过程中——当整个程序（或动态链接库）可见时——会生成机器代码。编译器可以利用这一点来跨翻译单元内联，或者至少使用有关被调用函数的副作用的信息来进行优化。
为优化的构建启用 LTO 通常是一个不错的选择，因为编译器可以看到您的整个程序。我现在依赖 LTO，以便我可以将更多函数主体移出头文件，以减少调试构建和测试的耦合、编译时间和构建依赖性，同时仍然在最终构建中为我提供所需的性能。
尽管 LTO 是一项相对成熟的技术（我在 2000 年代初期在原始 Xbox 上使用了 LTCG），但我一直惊讶于很少有项目使用 LTO。部分原因可能是程序员无意中依赖于未定义的行为，这种行为只有在编译器获得更多可见性时才会变得明显：我知道我曾为此感到内疚。
我最喜欢的优化示例
多年来，我已经收集了许多有趣的真实世界优化示例，这些示例既来自优化我自己的代码的第一手经验，也来自帮助其他人在 Compiler Explorer 上理解他们的代码。以下是一些我最喜欢的示例，说明了编译器有多么聪明。
常数整数除法
得知直到最近，在现代 CPU 上您能做的最昂贵的事情之一就是整数除法，这可能会令人惊讶。除法比加法昂贵 50 倍以上，比乘法昂贵 10 倍以上。（在 Intel 发布 Cannon Lake 微架构之前，情况确实如此，其中 64 位除法的最大延迟从 96 个周期减少到 18 个周期。6 这仅比加法慢约 20 倍，比乘法贵 5 倍。）
值得庆幸的是，当涉及到常数除法时，编译器作者有一些强度缩减技巧。我相信我们都意识到，除以 2 的幂通常可以用逻辑右移来代替——请放心，编译器会为您完成此操作。我建议不要在您的代码中编写 >> 来进行除法；让编译器为您计算出来。它更清晰，并且编译器也知道如何正确地处理有符号值：整数除法向零截断，而单独向下移位则向负无穷大截断。
但是，如果您除以非 2 的幂的值 (j) 呢？您是否运气不佳？
unsigned divideByThree(unsigned x)
{
return x / 3;
}
(j)
幸运的是，编译器再次为您撑腰。这段代码 (k) 被编译为 (https://godbolt.org/z/acm19_div3)
divideByThree(unsigned int)
mov eax, edi ; eax = edi
mov edi, 2863311531 ; edi = 0xaaaaaaab
imul rax, rdi ; rax = rax * 0xaaaaaaab
shr rax, 33 ; rax >>= 33
ret
(k)
没有看到任何除法指令。只有一个移位和一个奇怪的大常数乘法：32 位无符号输入值乘以 0xaaaaaaab，得到的 64 位值向右移动 33 位。编译器已将除法替换为更便宜的倒数乘法，以定点形式表示。在这种情况下，定点位于第 33 位，常数是三分之一用这些术语表示的（实际上是 0.33333333337213844）。编译器有一种算法，用于确定适当的定点和常数，以实现除法，同时在输入范围内保持与相同精度的实际除法运算相同的舍入。有时这需要一些额外的操作——例如 (l)，在除以 1023 时（https://godbolt.org/z/acm19_div1023）
divideBy1023(unsigned int)
mov eax, edi
imul rax, rax, 4198405
shr rax, 32
sub edi, eax
shr edi
add eax, edi
shr eax, 9
ret
(l)
该算法是众所周知的，并在优秀的著作《黑客的喜悦》8 中得到了广泛的记录。
简而言之，您可以依靠编译器在优化编译时已知的常数除法方面做得非常出色。
您可能会想：为什么这是一个如此重要的优化？无论如何，实际执行整数除法的情况有多频繁？问题与其说是除法本身，不如说是相关的模运算，模运算通常在哈希映射实现中用作将哈希值带入哈希桶数量范围内的运算。
了解编译器在这里可以做什么可以带来有趣的哈希映射实现。一种方法是使用固定数量的桶，以允许编译器生成完美的模运算，而无需使用昂贵的除法指令。
大多数哈希映射都支持重新哈希到不同数量的桶。天真地，这将导致模运算的数字仅在运行时才知道，迫使编译器发出缓慢的除法指令。实际上，这就是 GCC libstdc++ 库的 std::unordered_map 实现所做的事情。
Clang 的 libc++ 更进一步：它检查桶的数量是否是 2 的幂，如果是，则跳过除法指令，而使用逻辑 AND。拥有 2 的幂桶计数很诱人，因为它使模运算速度很快，但是为了避免过多的冲突，它依赖于拥有一个良好的哈希函数。即使对于简单的哈希函数，素数桶计数也具有不错的抗冲突能力。
诸如 boost::multi_index 之类的一些库更进一步：它们不存储桶的实际数量，而是使用固定数量的素数大小的桶计数 (m)。
size_t reduce(size_t hash, int bucketCountIndex) {
switch (tableSizeIndex)
{
case 0: return hash % 7;
case 1: return hash % 17;
case 2: return hash % 37;
// 等等...
}
}
(m)
这样，对于所有可能的哈希表大小，编译器都会生成完美的模代码，唯一的额外开销是在 switch 语句中调度到正确的代码片段。
GCC 9 有一个巧妙的技巧 (n) 用于检查是否可被非 2 的幂整除（https://godbolt.org/z/acm19_multof3）
bool divisibleBy3(unsigned x)
{
return x % 3 == 0;
}
(n)
这被编译为 (o)
divisibleBy3(unsigned int)
imul edi, edi, -1431655765 ; edi = edi * 0xaaaaaaab
cmp edi, 1431655765 ; 与 0x55555555 比较
setbe al ; 如果 edi <= 0x55555555 则返回 1
ret
(o)
Daniel Lemire 在他的博客2 中很好地解释了这种明显的巫术。顺便说一句，也有可能在运行时进行这些类型的整数除法技巧。如果您需要将许多数字除以相同的值，则可以使用诸如 libdivide5 之类的库。
计数设置位
您多久会想知道，这个整数中有多少个设置位？可能不是那么频繁。但是事实证明，这种简单的操作在许多情况下都非常有用。例如，计算两个位集之间的汉明距离，处理稀疏矩阵的打包表示形式，或处理向量运算的结果。
您可以编写一个函数来计算位 (p)，如下所示
int countSetBits(unsigned a)
{
int count = 0;
while (a != 0)
{
count++;
a &= (a - 1); // 清除最低设置位
}
return count;
}
(p)
值得注意的是位操作“技巧” a &= (a - 1);，它清除最低设置位。证明它如何在纸上工作是一件有趣的事情。试试看。
当以 Haswell 微架构为目标时，GCC 8.2 将此代码编译为 (q) 中的汇编代码（https://godbolt.org/z/acm19_bits）
countSetBits(unsigned int)
xor eax, eax ; count = 0
test edi, edi ; a == 0 吗？
je .L4 ; 如果是，则返回
.L3
inc eax ; count ++
blsr edi, edi ; a &= (a - 1);
jne .L3 ; 如果 a != 0，则跳回 L3
ret
.L4
Ret
(q)
请注意 GCC 如何巧妙地找到 BLSR 位操作指令来挑出最低设置位。很简洁，对吧？但不如 Clang 7.0 (r) 那么聪明
countSetBits(unsigned int)
popcnt eax, edi ; count = a 中设置位的数量
ret
(r)
此操作非常常见，以至于大多数 CPU 架构上都有一个指令可以一次完成它：POPCNT（人口计数）。Clang 足够聪明，可以将 C++ 中的整个循环简化为单个指令。这是良好指令选择的一个很好的例子：Clang 的代码生成器识别出这种模式，并且能够选择完美的指令。
实际上，我在这里有点不公平：GCC 9 也实现了这一点 (s)，实际上显示出细微的差异
countSetBits(unsigned int)
xor eax, eax ; count = 0
popcnt eax, edi ; count = a 中设置位的数量
ret
(s)
乍一看，这似乎是次优的：为什么要写一个零值，只是立即用“人口计数”指令 popcnt 的结果覆盖它呢？
一点研究揭示了 Intel CPU 勘误表 SKL029：“POPCNT 指令的执行时间可能比预期的要长”——存在 CPU 错误！尽管 popcnt 指令完全覆盖了输出寄存器 eax，但它被错误地标记为依赖于 eax 的先前值。这限制了 CPU 调度指令的能力，直到任何先前写入 eax 的指令完成——即使它们没有影响。
GCC 在这里的做法是打破对 eax 的依赖性：CPU 将 xor eax, eax 识别为打破依赖性的习语。在 xor eax, eax 之后，任何先前的指令都不能影响 eax，并且 popcnt 可以在其输入操作数 edi 可用后立即运行。
这仅影响 Intel CPU，并且似乎在 Cannon Lake 微架构中得到了修复，尽管 GCC 在以其为目标时仍然发出 XOR。
链式条件
也许您从不需要计算整数中设置位的数量，但您可能以前编写过类似这样的代码 (t)
bool isWhitespace(char c)
{
return c == ' '
|| c == '\r'
|| c == '\n'
|| c == '\t';
}
(t)
本能地，我认为代码生成将充满比较和分支，但是 Clang 和 GCC 都使用了一个巧妙的技巧来使这段代码非常高效。(u) 显示了 GCC 9.1 的输出（https://godbolt.org/z/acm19_conds）
isWhitespace(char)
xor eax, eax ; result = false
cmp dil, 32 ; c > 32 吗
ja .L4 ; 如果是，则退出并返回 false
movabs rax, 4294977024 ; rax = 0x100002600
shrx rax, rax, rdi ; rax >>= c
and eax, 1 ; result = rax & 1
.L4
ret
(u)
编译器将这一系列的比较转换为查找表。加载到 rax 中的魔术值是一个 33 位查找表，在您将返回 true 的位置（索引 32、13、10 和 9 分别对应 ' '、\r、\n 和 \t）中有一个一位。然后，移位和 & 挑选出第 c 位并返回它。Clang 生成的代码略有不同，但大致等效。这是强度缩减的另一个例子。
我很高兴看到这种优化。这绝对是在 Compiler Explorer 中进行调查之前，我会手动编写并假设我比编译器更了解的那种东西。
我在实验中注意到的一件不幸的事情是——至少对于 GCC 而言——比较的顺序会影响编译器进行这种优化的能力。如果您切换 \r 和 \n 的比较顺序，GCC 会生成代码 (v)。
isWhitespace(char)
cmp dil, 32 ; c == 32 吗？
sete al ; 如果是，则 al = 1，否则为 0
cmp dil, 10 ; c == 10 吗？
sete dl ; 如果是，则 dl = 1，否则为 0
or al, dl ; al |= dl
jne .L3 ; 如果 al 非零，则返回它（c 是 ` ` 或 `\n`）
and edi, -5 ; 清除位 2（`\r` 和 `\t` 之间唯一不同的位）
; `\r` 和 `\t`)
cmp dil, 9 ; 与 `\t` 比较
sete al ; 如果相等，dl = 1，否则为 0
.L3
ret
(v)
有一个非常巧妙的技巧，可以使用 and 来组合 \r 和 \t 的比较，但这似乎比之前生成的代码更糟糕。 尽管如此，Quick Bench 上的一个简单基准测试表明，在可预测的紧密循环中，基于比较的版本可能会稍微快一点。 谁说这很简单呢，嗯？
求和
有时你需要将一堆东西加起来。 现在的编译器非常擅长利用大多数 CPU 中可用的向量化指令，因此即使是很简单的代码，例如 (w)
int sumSquared(const vector<int> &v)
{
int res = 0;
for (auto i : v)
{
res += i * i;
}
return res;
}
(w)
会被转换成核心循环看起来像 (x) 的代码 (https://godbolt.org/z/acm19_sum)
.loop
vmovdqu ymm2, YMMWORD PTR [rax] ; 将 32 字节读入 ymm2
add rax, 32 ; 前进到下一个元素
vpmulld ymm0, ymm2, ymm2 ; 平方 ymm2，视为
; 8 个 32 位值
vpaddd ymm1, ymm1, ymm0 ; 加到小计中
cmp rax, rdx ; 我们到达末尾了吗？
jne .loop ; 如果没有，继续循环
(x)
编译器已经能够通过每条指令处理八个值，方法是将总数分成八个单独的小计。 最后，它将这些小计相加得到最终总数。 这就像代码被重写成更像 (y) 的样子
int res_[] = {0,0,0,0,0,0,0,0};
for (; index < v.size(); index += 8)
{
// 这可以通过并行指令执行，而无需
// 实际的循环。 以下内容归结为几个
// 向量指令
for (size_t j = 0; j < 8; ++j)
{
auto val = v[index + j];
res_[j] += val * val;
}
}
res = res_[0] + res_[1]
+ res_[2] + res_[3]
+ res_[4] + res_[5]
+ res_[6] + res_[7];
(y)
只需将编译器的优化级别设置为足够高的设置，并选择适当的目标 CPU 架构，向量化就会启动。 太棒了！
这确实依赖于这样一个事实：将总数分成单独的小计，然后在最后求和，等同于按照程序指定的顺序相加。 对于整数，这显然是正确的； 但对于浮点数据类型，情况并非如此。 浮点运算不具有结合律：(a+b)+c 与 a+(b+c) 不同，因为——除其他外——加法结果的精度取决于两个输入的相对大小。
这意味着，不幸的是，将 vector<int> 更改为 vector<float> 不会产生您理想的代码。 编译器可以使用一些向量操作（它可以一次平方八个值），但它被迫串行地对这些值求和 (z) (https://godbolt.org/z/acm19_sumf)
.loop
vmovups ymm4, YMMWORD PTR [rax] ; 将 32 字节读入 ymm4
add rax, 32 ; 前进
vmulps ymm1, ymm4, ymm4 ; 平方 8 个浮点数
; （唯一的并行操作）
vaddss xmm0, xmm0, xmm1 ; 累加第一个值
vshufps xmm3, xmm1, xmm1, 85 ; 重新排列
; （置换 8 个浮点数
; 在寄存器内）
vshufps xmm2, xmm1, xmm1, 255 ; ...
vaddss xmm0, xmm0, xmm3 ; 累加第二个值
vunpckhps xmm3, xmm1, xmm1 ; 更多重新排列
vextractf128 xmm1, ymm1, 0x1 ; ...
vaddss xmm0, xmm0, xmm3 ; 累加第三个...
vaddss xmm0, xmm0, xmm2 ; 和第四个值
vshufps xmm2, xmm1, xmm1, 85 ; 重新排列
vaddss xmm0, xmm0, xmm1 ; 累加第五个
vaddss xmm0, xmm0, xmm2 ; 和第六个
vunpckhps xmm2, xmm1, xmm1 ; 更多重新排列...
vshufps xmm1, xmm1, xmm1, 255 ; ...
vaddss xmm0, xmm0, xmm2 ; 累加第七个
vaddss xmm0, xmm0, xmm1 ; 和最后一个值
cmp rax, rcx ; 我们完成了吗？
jne .loop ; 如果没有，继续
(z)
这很不幸，而且没有简单的解决办法。 如果您绝对确定在您的情况下加法顺序不重要，您可以给 GCC 危险的（但名称很有趣的）-funsafe-math-optimizations 标志。 这使它可以生成这个漂亮的内部循环 (a') (https://godbolt.org/z/acm19_sumf_unsafe)
.loop
vmovups ymm2, YMMWORD PTR [rax] ; 读取 8 个浮点数
add rax, 32 ; 前进
vfmadd231ps ymm0, ymm2, ymm2 ; 对于 8 个浮点数：
; ymm0 += ymm2 * ymm2
cmp rax, rcx ; 我们完成了吗？
jne .loop ; 如果没有，继续
(a')
令人惊叹的东西：一次处理八个浮点数，使用单个指令来累加和平方。 缺点是可能存在无限的精度损失。 此外，GCC 不允许您仅为您需要的函数启用此功能——这是一个按编译单元的标志。 Clang 至少允许您在源代码中使用 #pragma Clang fp contract 控制它。
在研究这些优化时，我发现编译器还有更多的绝招 (b')
int sumToX(int x)
{
int result = 0;
for (int i = 0; i < x; ++i)
{
result += i;
}
return result;
}
(b')
GCC 为此生成相当简单的代码，并且在适当的编译器设置下将使用如上的向量运算。 然而，Clang 生成了这段代码 (https://godbolt.org/z/acm19_sum_up)
sumToX(int): # @sumToX(int)
test edi, edi ; 测试 x
jle .zeroOrBelow ; 如果 x <= 0 则跳过
lea eax, [rdi - 1] ; eax = x - 1
lea ecx, [rdi - 2] ; ecx = x - 2
imul rcx, rax ; rcx = ecx * eax
shr rcx ; rcx >>= 1
lea eax, [rcx + rdi] ; eax = rcx + x
add eax, -1 ; 返回 eax - 1
ret
.zeroOrBelow
xor eax, eax ; 答案为零
ret
(c')
首先，请注意根本没有循环。 通过生成的代码，您会看到 Clang 返回
它已将循环迭代替换为总和的闭式通用解。 该解决方案与我自己天真地写出的解决方案不同
这大概是 Clang 使用的通用算法的结果。
进一步的实验表明，Clang 非常聪明，足以优化许多此类循环。 Clang 和 GCC 都以允许这种优化方式跟踪循环变量，但只有 Clang 选择生成闭式版本。 这并不总是减少工作量：对于 x 的小值，闭式解决方案的开销可能比仅循环更大。 Krister Walfridsson 在一篇博客文章中详细介绍了如何实现这一点。7
还值得注意的是，为了进行这种优化，编译器可能依赖于有符号整数溢出是未定义行为。 因此，它可以假设您的代码不能传递一个会导致结果溢出的 x 值（在本例中为 65536）。 如果 Clang 无法做出这种假设，有时它就无法找到闭式解决方案 (https://godbolt.org/z/acm19_sum_fail)。
去虚化
尽管传统的基于虚函数的 polymorphism 似乎有点不受欢迎了，但它仍然有其用武之地。 无论是为了实现真正的 polymorphic 行为，还是为可测试性添加“接缝”，还是为了未来的可扩展性，通过虚函数实现 polymorphism 可能是一个方便的选择。
众所周知，虚函数很慢。 真是这样吗？ 让我们看看它们如何影响前面平方和的例子——类似于 (d')。
struct Transform
{
int operator()(int x) const { return x * x; }
};
int sumTransformed(const vector<int> &v,
const Transform &transform)
{
int res = 0;
for (auto i : v)
{
res += transform(i);
}
return res;
}
(d')
当然，这还不是 polymorphic 的。 快速运行编译器显示了相同的、高度向量化的汇编代码 (https://godbolt.org/z/acm19_poly1)。
现在在 int operator() 前面添加 virtual 关键字应该会导致更慢的实现，充满了间接调用，对吗？ 嗯，有点 (https://godbolt.org/z/acm19_poly2)。 比以前发生了很多事情，但在循环的核心是某些可能令人惊讶的事情 (e')。
; rdx 指向 vtable
.L8
mov rax, QWORD PTR [rdx] ; 读取虚函数指针
mov esi, DWORD PTR [rbx] ; 读取下一个 int 元素
; 将函数指针与唯一的地址进行比较
; 已知实现...
cmp rax, Transform::operator()(int) const
jne .L5 ; 如果它不是唯一的已知实现，
; 然后跳转到更复杂的情况
imul esi, esi ; 平方该数字
add rbx, 4 ; 移动到下一个
add r12d, esi ; 累加平方
cmp rbp, rbx ; 完成了吗？
jne .L8 ; 如果没有，循环
e'
这里发生的事情是 GCC 做了一个赌注。 鉴于它只看到了 Transform 类的一个实现，很可能将使用该实现。 它没有盲目地通过虚函数指针进行间接调用，而是稍微付出了一点代价，将指针与唯一已知的实现进行了比较。 如果匹配，则编译器知道该怎么做：它内联 Transform::operator() 的主体并在原地对其进行平方。
没错：编译器内联了一个虚函数调用。 这太令人惊讶了，当我第一次发现这一点时，我感到非常惊讶。 这种优化称为推测性去虚化，是编译器编写者持续研究和改进的来源。 编译器也能够在 LTO 时进行去虚化，从而可以进行整个程序范围的函数实现确定。
然而，编译器错过了一个技巧。 请注意，在循环的顶部，它每次都会从 vtable 重新加载虚函数指针。 如果编译器能够注意到，如果被调用的函数不更改 Transform 的动态类型，则此值保持不变，则可以将此检查提升到循环之外，然后循环中将根本没有动态检查。 编译器可以使用循环不变代码移动将 vtable 检查提升到循环之外。 此时，其他优化可能会启动，并且在 vtable 检查通过的情况下，整个代码可以替换为前面提到的向量化循环。
您可能会原谅自己认为对象的动态类型不可能改变，但标准实际上允许这样做：对象可以对其自身进行 placement `new`，只要它在销毁时返回到其原始类型即可。 我建议您永远不要这样做。 Clang 有一个选项可以保证您永远不会在代码中做如此可怕的事情：-fstrict-vtable-pointers。
在我使用的编译器中，GCC 是唯一一个默认执行此操作的编译器，但 Clang 正在彻底改革其类型系统，以更多地利用这种优化。4
C++11 添加了 final 说明符，以允许将类和虚方法标记为不再被重写。 这为编译器提供了更多关于哪些方法可能从这种优化中获益的信息，并且在某些情况下甚至可能允许编译器完全避免虚函数调用 (https://godbolt.org/z/acm19_poly3)。 即使没有 final 关键字，有时分析阶段也能够证明正在使用特定的具体类 (https://godbolt.org/z/acm19_poly4)。 这种静态去虚化可以产生显着的性能改进。
结论
希望在阅读本文后，您会体会到编译器为确保高效代码生成所做的努力。 我希望其中的一些优化会给您带来惊喜，并将影响您编写清晰、意图明确的代码，并将其余的事情留给编译器来做的决定。 我已经强调了这样一个观点，即编译器拥有的信息越多，它就能做得越好。 这包括允许编译器一次看到更多代码，以及为编译器提供有关您目标 CPU 架构的正确信息。 在为编译器提供更多信息方面需要权衡：这可能会使编译速度变慢。 链接时优化等技术可以为您提供两全其美的方案。
编译器中的优化在不断改进，即将到来的间接调用和虚函数分派方面的改进可能很快就会带来更快的 polymorphism。 我对编译器优化的未来感到兴奋。 去看看你的编译器的输出吧。
感谢
作者要感谢 Matt Hellige、Robert Douglas 和 Samy Al Bahra，他们对本文草稿提供了反馈。
参考文献
1. Godbolt, M. 2012. Compiler explorer（编译器浏览器）; https://godbolt.org/.
2. Lemire, D. 2019. Faster remainders when the divisor is a constant: beating compilers and libdivide（当除数是常数时，更快的余数：击败编译器和 libdivide）. https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/.
3. LLVM. 2003. The LLVM compiler infrastructure（LLVM 编译器基础设施）; https://llvm.net.cn.
4. Padlewski, P. 2018. RFC: Devirtualization v2（RFC：去虚化 v2）. LLVM; http://lists.llvm.org/pipermail/llvm-dev/2018-March/121931.html.
5. ridiculous_fish. 2010. Libdivide; https://libdivide.com/.
6. Uops. Uops.info Instruction Latency Tables（Uops.info 指令延迟表）; https://uops.info/table.html.
7. Walfridsson, K. 2019. How LLVM optimizes power sums（LLVM 如何优化幂和）; https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geometric-sums.html.
8. Warren, H. S. 2012. Hacker's Delight（黑客的快乐）. 第 2 版。Addison-Wesley Professional.
相关文章
C 不是一种低级语言
你的计算机不是一台快速的 PDP-11。
- David Chisnall
https://queue.org.cn/detail.cfm?id=3212479
未初始化的读取
理解 C 语言的拟议修订
- Robert C. Seacord
https://queue.org.cn/detail.cfm?id=3041020
你对共享变量或内存模型一窍不通
数据竞争是邪恶的。
- Hans-J. Boehm, Sarita V. Adve
https://queue.org.cn/detail.cfm?id=2088916
Matt Godbolt 是 Compiler Explorer 网站的创建者。 他热衷于编写高效的代码。 他目前在 Aquatic Capital 工作，并且曾从事低延迟交易系统、在 Google 从事移动应用程序工作、经营自己的 C++ 工具公司，并花费了十多年的时间制作游戏机游戏。 当他不 hack Compiler Explorer 时，Matt 喜欢为旧的 8 位计算机硬件编写模拟器。
版权所有 © 2019，由所有者/作者持有。 出版权已授权给 。
最初发表于 Queue vol. 17, no. 5—
在 数字图书馆 中评论本文
更多相关文章
Ulan Degenbaev, Michael Lippautz, Hannes Payer - Garbage Collection as a Joint Venture（作为合资企业的垃圾收集）
跨组件跟踪是解决跨组件边界的引用循环问题的一种方法。 一旦组件可以形成具有跨 API 边界的非平凡所有权的任意对象图，就会出现此问题。 CCT 的增量版本在 V8 和 Blink 中实现，从而能够以安全的方式有效且高效地回收内存。
David Chisnall - C Is Not a Low-level Language（C 不是一种低级语言）
在最近的 Meltdown 和 Spectre 漏洞之后，值得花一些时间研究根本原因。 这两个漏洞都涉及处理器推测性地执行指令，绕过某种访问检查，并允许攻击者通过侧信道观察结果。 导致这些漏洞以及其他几个漏洞的功能的添加，是为了让 C 程序员继续相信他们正在用低级语言编程，但这在几十年里早已不是事实。
Tobias Lauinger, Abdelberi Chaabane, Christo Wilson - Thou Shalt Not Depend on Me（你不应该依赖我）
大多数网站使用 JavaScript 库，其中许多库已知存在漏洞。 了解问题的范围以及包含库的许多意外方式只是改善情况的第一步。 这里的目标是，本文中包含的信息将有助于为社区提供更好的工具、开发实践和教育工作。
Robert C. Seacord - Uninitialized Reads（未初始化的读取）
大多数开发人员都明白，在 C 语言中读取未初始化的变量是一个缺陷，但有些人仍然这样做。 在当前版本的 C 标准 (C11).3 中，读取未初始化的对象时会发生什么是未解决的问题。 为了在计划中的 C2X 标准修订版中解决这些问题，已提出各种提案。 因此，现在是了解现有行为以及拟议的标准修订以影响 C 语言发展的好时机。 鉴于 C11 中未初始化读取的行为尚不确定，谨慎的做法是从代码中消除未初始化的读取。
© 版权所有。