bee*_*ane 45 optimization assembly llvm clang arm64
我承认这个问题的答案可能是“一些非常具体的魔法”，但我对在这里观察到的情况感到有点震惊。我想知道是否有人了解这些类型的优化是如何工作的。我发现编译器的设计非常有趣，我真的无法想象它是如何工作的。我确信答案就在 clang 源代码中的某个地方，但我什至不知道该在哪里查找。
我是大学课程的助教，最近有人要求我帮助解决一个简单的家庭作业问题。这让我走上了一条有趣的道路......
问题很简单：在 x86_64 汇编中，编写一个给定（正）整数 n 返回的函数1^2 + 2^2 + 3^2 + ... + n^2。
我决定尝试一下，在帮助他们在 x86_64 汇编中编写此代码后，我（拥有一台 M1 macbook）决定看看是否可以在 arm64 汇编中创建一个不错的解决方案。我想出了一个相对简单直接的解决方案：
_sum_squares:
mov x1, x0 ; Do multiplication from x1
mov x0, xzr ; Clear x0
Lloop:
; x0 <-- (x1 * x1) + x0
madd x0, x1, x1, x0
; Loop until x1 == 0
subs x1, x1, #1
bne Lloop
ret
（我希望有某种很好的方法可以--x1 == 0在一条指令中进行分支，但我想不出任何方法）
注意：任何基础数论课程中都有一个简单的公式，即[n(n + 1)(2n + 1)] / 6，但我认为这并不真正符合问题的精神。
然后我想知道 clang 如何为简单的 C 版本生成程序集。在编写简单的 C 实现时，我发现 clang with-Og生成程序集似乎有点冗长，但通常与循环和累加器一起按预期工作（尽管效率非常低）：
int sum_squares(int n)
{
int a = 0;
while (n--)
a += (n * n);
return a;
}
（clang -Og -S，我自己注释，cfi 已删除，标签已重命名）
_sum_squares:
sub sp, sp, #16 ; create stack space
str w0, [sp, #12] ; store n
str wzr, [sp, #8] ; store 0
b Ldec ; silly clang, this just falls through...
Ldec: ; n-- and return if n == 0
ldr w8, [sp, #12] ; load n
subs w9, w8, #1 ; w9 = (n - 1)
str w9, [sp, #12] ; store (n - 1) over n
subs w8, w8, #0 ; w8 = n - 0 (set flags based on n)
cset w8, eq ; set w8 = 1 if n == 0 else w8 = 0
tbnz w8, #0, Lret ; branch to return if n == 0, else fall through
b Ladd ; silly clang, this falls through again...
Ladd: ; a += n^2
ldr w8, [sp, #12] ; load n
ldr w9, [sp, #12] ; load n
mul w9, w8, w9 ; w9 = n * n
ldr w8, [sp, #8] ; load a
add w8, w8, w9 ; a += w9
str w8, [sp, #8] ; store a
b Ldec ; go back to start of look
Lret: ; return a from top of stack
ldr w0, [sp, #8] ; w0 = a
add sp, sp, #16 ; cleanup temp stack
ret ; back to caller
对于将 C 代码直接翻译为 arm64 汇编来说，这是完全合理的。经过一些优化（O1 使用类似的公式，O2 和 O3 相同），clang 发挥了一些魔力。我不知道它是如何想出这个代码的，它似乎有点类似于这个求和的基本公式，除了位魔法。我没想到编译器能够在没有循环的情况下导出公式，但看来我错了。生成的代码如下（我尽力注释一下，n是中的输入w0）：
_sum_squares:
cbz w0, Lret ; return if n == 0
sub w8, w0, #1 ; w8 = (n - 1)
mul w9, w8, w8 ; w9 = (n - 1)^2
orr w9, w9, #0x2 ; w9 = ((n - 1)^2) | 2
sub w9, w9, w0 ; w9 = [((n - 1)^2) | 2] - n
mov w10, #5 ; w10 = 5
sub w10, w10, w0, lsl #1 ; w10 = 5 - (n / 2)
sub w11, w0, #2 ; w11 = n - 2
umull x11, w8, w11 ; w11 = (n - 1)(n - 2)
lsr x12, x11, #1 ; x12 = ((n - 1)(n - 2)) / 2
mul w10, w10, w12 ; w10 = (5 - (n / 2))(((n - 1)(n - 2)) / 2)
sub w12, w0, #3 ; w12 = n - 3
mul x11, x11, x12 ; x11 = (n - 1)(n - 2)(n - 3)
lsr x11, x11, #1 ; x11 = ((n - 1)(n - 2)(n - 3)) / 2
mov w12, #21846 ; w12 = 0x5556
movk w12, #21845, lsl #16 ; w12 = 0x55555556
; w8 = ((n - 1)([((n - 1)^2) | 2] - n)) + (5 - (n / 2))(((n - 1)(n - 2)) / 2)
madd w8, w9, w8, w10
; let A = w8 (set in last instruction)
; w0 = (0x55555556 * (((n - 1)(n - 2)(n - 3)) / 2)) + A
madd w0, w11, w12, w8
; somehow, this is the correct result?
; this feels like magic to me...
Lret:
ret ; return. Result already in w0.
我的问题：这到底是如何运作的？C 编译器如何得到这样的循环并推导出一个甚至不涉及循环的公式？我预计也许会有一些循环展开，但没有像这样的。有人有涉及此类优化的参考吗？
我特别不明白某些步骤orr w9, w9, #0x2或幻数 0x55555556 的作用。任何对这些步骤的见解都将受到额外赞赏。
Pet*_*des 54
TL:DR：是的，clang 知道整数幂级数和的封闭式公式，并且可以检测此类循环。 聪明的人已经教会现代编译器识别某些操作模式，并用源代码中不存在的操作替换它们，例如循环，甚至 popcount 循环和 bithacks。特别是对于 clang/LLVM，还有 i^power 总和的封闭式公式，包括除 1 以外的步长。耶，数学！因此，您可以获得的汇编逻辑不仅仅是源代码的展开或矢量化版本。
另请参阅博客文章LLVM 如何优化幂和，其中讨论了编译器如何通过查看变量如何在循环迭代中更新来找到这些循环。
Matthieu M. 评论说，封闭式公式是通过 LLVM 中的标量进化优化导出的。 代码中的注释表明它主要用于分析涉及循环中归纳变量的表达式。并引用了用于循环链的技术的参考文献。
现代 C 编译器可以识别代码内部表示中某些循环或短逻辑序列中的模式。人类（编译器开发人员）已经告诉编译器要寻找什么，并提供了一个手工制作的替换“公式”。我希望在 GIMPLE (GCC) 或 LLVM-IR 中，不仅仅是在生成 asm 时进行窥孔优化那样的编译后期。
因此，我猜测 LLVM 优化器内部的逻辑会检查它找到的每个循环是否存在以下一种或多种可能性，并使用一些代码来查找代表该循环的程序逻辑的 LLVM-IR 的某些属性：
__builtin_memcpy，稍后可能会内联扩展或编译为call memcpy. 如果它有其他副作用，例如使指针变量递增，则也将其表示在包含循环的函数的新 LLVM-IR 中。memsetpopcnt，否则保留循环策略。（因此，它不仅仅是将其视为__builtin_popcount，而不是用 bithack 或对辅助函数的调用来替换循环。这是有道理的，因为某些策略适用于设置很少位的数字，并且程序员可能会选择这种策略心里。）1，请添加偏移量和/或比例因子。）检查可能会考虑循环修改的变量，该变量在循环后读取。因此它知道在查看操作时要考虑什么变量。（没有使用结果的循环将被删除。）
GCC 不查找整数序列的和，但 clang 会查找。我不知道这实际上加速了多少现实世界的代码库；封闭式公式相当著名，著名的是高斯在学生时代就重新发现了它。（所以希望很多代码使用公式而不是循环）。我想，除了作为练习之外，没有多少程序需要这样做。
（封闭式平方和公式的存在不太为人所知，但有一个，并且显然也适用于一般幂。）
当然，Clang 的公式实现必须为每个输入整数提供精确正确的结果，其中 C 抽象机不会遇到未定义的行为（有符号整数溢出），或者匹配无符号乘法的截断。否则它不会满足 as-if 规则，或者只能在内联到具有已知有限值范围的位置时使用。（实际上，clang 似乎没有对无符号使用封闭式优化，但也许我只是在尝试的版本中犯了一个错误。使用 64 位整数可以安全地计算 32 位整数的总和。并且然后截断可能会得到与源相同的结果。）
n*(n+1)在仍在范围内的情况下可能会溢出n*(n+1)/2，因此这并不简单。对于 64 位机器上的 32 位int，LLVM 可以并且确实简单地使用 64 位乘法和右移。如果产品不适合一个寄存器，这可能是对使用双宽度输出和扩展精度右移的一般情况的窥视孔优化，跨两个寄存器。（例如，在 EDX:EAX 中生成 64 位乘积shrd edx, eax, 1后，x86 将低位从高半部分移至 EAX 的顶部。）mul r32
它也可以n * (n-1) / 2 + n代替通常的n * (n+1)/2; 不知道这有什么帮助。我想，它可以避免输入类型的溢出，以防万一这对于unsigned原始循环仅具有换行而不是 UB 的类型很重要。但它不会对无符号进行此优化。（顺便说一句，要么n要么n+-1是偶数，所以除法（右移）是精确的；这很好，因为整数之和最好是整数。）
在您的平方和汇编中，您可以看到它umull x, w, w在除以 3 的 32 位乘法逆元之前执行加宽乘法和 64 位右移。
尝试使用您的代码和不平方的简化版本，当您倒计时或向上计数时，它会在代码生成中产生微小的差异。
int sum_ints(int n) {
int a = 0;
//for (int i=0 ; i<n ; i++) a += i; // count up, skipping n
while (n--) a += n; // count down, skipping n
return a;
}
负数n将使 UB 与您的版本一起出现，因为循环将运行到INT_MIN--, 并a首先溢出。因此 clang 可能会也可能不会使用它来假设初始值n是非负的。但如果不是，我不知道为什么它会编写更复杂的乘以两次的代码。
// count down version, starting with a += n-1, so x = n-1 in the usual formulae.
// clang15 -O3
sum_ints(int):
cbz w0, .LBB0_2 // only bail on zero, not negative.
sub w8, w0, #1 // n-1
sub w9, w0, #2 // n-2
umull x10, w8, w9 // (n-1)*(n-2)
madd w8, w8, w9, w0 // w8 = (n-1)*(n-2) + n
lsr x9, x10, #1 // w9 = (n-1)*(n-2)/2
mvn w9, w9 // w9 = ~w9 = -w9 - 1
add w0, w8, w9 // (n-1)*(n-2) - (n-1)*(n-2)/2 + n - 1 I think?
.LBB0_2:
ret
// count up version, ending with n-1. clang15 -O3
sum_ints(int):
subs w8, w0, #1 // n-1
b.lt .LBB0_2
sub w9, w0, #2 // n-2
umull x9, w8, w9 // (n-1)*(n-2)
lsr x9, x9, #1 // . / 2
add w0, w8, w9 // (n-1)*(n-2)/2 + (n-1) = (n-1)*(n-2 + 2)/2
// = the usual x * (x+1 )/2 for x=n-1
ret
.LBB0_2:
mov w0, wzr // separate return path for all negative inputs
ret
GCC 和 clang 对计算设置位的循环进行模式识别，以及人们将从 SO 复制/粘贴的标准 bithack 。（这很有用，因为 ISO C 无法提供一种可移植的方式来表达大多数现代 CPU 所具有的此操作。并且 ISO C++ 仅使用<bit>, 或 通过修复了 C++20 中的缺陷std::bitset<32> .count()）。因此，一些真正的代码库只是对设置位进行了位黑客或简单循环，而不是__builtin_popcount因为人们更喜欢简单性并希望将性能留给编译器。
这些模式识别器仅适用于某些特定的实现方式popcount，即x &= x-1; count++；试图证明每个可能的循环的等效性可能会花费太多的编译时间。由此，我们可以非常确定这些是通过寻找特定的实现来工作的，而不是针对每个可能的整数的实际结果。
变量名称当然并不重要，但输入变量的操作顺序却很重要。我认为重新排序操作具有一定的灵活性，可以在检查等效性时给出相同的结果。在 GCC 的例子中，显然number_of_iterations_popcount是发现这一点的函数的名称：编译器通常想知道循环将运行多少次迭代：如果它是一个小常量，他们可能会完全展开它。如果它可以在开始循环之前从其他变量计算出来，那么它就是自动矢量化的候选者。（GCC/clang 无法自动向量化搜索循环，或任何其他具有数据相关 if()break 的内容。）
如计数 32 位整数中设置位数的最佳答案所示，GCC10 和 clang10 ( Godbolt ) 也可以使用 SWAR bithack 来识别popcount，因此您可以两全其美：理想情况下是一条指令，但是如果不是，那么至少是一个好的策略。
x &= x-1当预期的设置位数很小时，计算直到的迭代x == 0是可以的，因此有时也是一个明智的选择，因为如果硬件 popcount 可用，GCC / clang 可以替代其他东西。（并且编写起来很简单，不需要掩码常量，并且可以编译为较小的机器代码大小（-Os如果不替换为单个指令）。）
int popcount_blsr_until_zero(unsigned x){
int count = 0;
while (x){
count++; // loop trip-count = popcount, this is what GCC looks for
x &= x - 1;
}
return count;
}
用于 x86-64 或更高版本的 GCC 和 clang -O3 -march=nehalem，用于此版本和其他一些版本的Godbolt 。
# gcc12 -O3 -march=znver2
popcount_blsr_until_zero(unsigned int):
popcnt eax, edi
ret
// clang -O3 for AArch64
popcount_blsr_until_zero(unsigned int):
mov w8, w0 // this is pointless, GCC doesn't do it.
fmov d0, x8
cnt v0.8b, v0.8b // ARM unfortunately only has vector popcnt
uaddlv h0, v0.8b // hsum bytes
fmov w0, s0 // copy back to GP-integer
ret
通过模式识别进行代码替换的最简单形式之一是编译(n<<5) | (n>>(32-5))为向左旋转 5。（请参阅此问答了解运行时变量计数，以及如何安全地编写可被识别的内容，但即使对于计数也可以避免 UB共 0 个。）
但这可能在编译过程中发生得足够晚，您可以将其称为窥视孔优化。CISC ISA 往往有更多的窥孔优化，例如 x86 具有特殊情况的较短指令以在累加器内进行签名（cdqe而不是movzx eax, ax）。将寄存器设置为零的x86xor归零mov eax, 0仍然可以称为窥视孔，尽管有时需要重新排列事物，因为它会破坏标志，而不会。
-fpeephole2GCC 使用（的一部分-O2）启用异或归零；也许将其视为只是一个窥视孔，这就是为什么 GCC 有时会做得很糟糕并且无法找到方法将其重新排序为xor-zero //cmp而setcc不是cmp// ，因为 x86 setcc 根据 FLAGS 条件设置寄存器很糟糕，只写入低8位。AArch64 有更好的指令，例如可以与零寄存器一起使用来实现 0/1，或者与其他寄存器一起使用来有条件地选择和递增。setccmovzxcsinc
但级数总和循环是一种更大规模的替代，并不完全是我所认为的窥视孔，特别是因为它不是特定于目标的。
还相关：
是否允许 C 编译器用一种算法替换另一种算法？- 是的。但通常情况下它们不会，因为编译器足够机械，它们并不总是正确的，并且为数据选择有效的算法是 C 程序员希望编译器尊重的事情，除非有一条指令显然总是更快。
clang 知道如何__builtin_popcount使用 AVX2vpshub作为半字节查找表对数组进行自动矢量化。它不仅仅是从相同的操作中创建一个 SIMD 版本，它还使用了人类编译器开发人员放置在那里供其使用的扩展。
为什么编译器优化不生成 1..N 整数之和的循环？是关于这种优化不会发生的情况，例如j <= nfor unsigned，这可能是一个无限循环。
那里的评论发现了一些关于 clang 何时可以优化的有趣限制：例如，如果循环是for (int j=0 ; j < n; j += 3)，则行程计数将不太可预测/可计算，并且会破坏此优化。
Nat*_*dge 15
至少首先，这是您的“基本数论”公式，尽管其形式相当混乱且低效。clang 开发人员显然也参加了该课程。
一些有助于验证的提示：
您的sum_squares函数有一个差一错误，并且总和仅为n-1。因此我们期望得到的公式是n(n-1)(2n-1)/6。
在这种情况orr w9, w9, #0x2下， 相当于add w9, w9, #0x2。上一条指令mul w9, w8, w8加载了w9的平方w8。现在唯一的模 4 的完美平方是 0 和 1，两者的位 1 都清零，因此 的位 1w9将始终清零。所以w9 | 2相当于w9 + 2. （不，我不知道 clang 为什么要这样做。）
正如 harold 所评论的，乘法0x55555556相当于除以 3 再乘以 2 的 mod 2^32（假设没有余数）。这种技术有时被称为“幻数除法”。请参阅为什么 GCC 在实现整数除法时使用乘以奇怪的数字？。因此，在此之前，请x11 = ((n - 1)(n - 2)(n - 3)) / 2注意，它始终是 3 的倍数（并且除以 2 始终是精确的，因为分子始终是偶数）。因此w11 * w12结果为(n-1)(n-2)(n-3)/6.
将所有这些放在一起，您可以检查代数以验证最终结果是否等于n(n-1)(2n-1)/6。
我无法谈论 clang 如何执行此优化。我想我曾经尝试过找出哪个 LLVM 优化过程可以实现这一目标，但我不记得它是什么。但有一些已知的算法可以自动导出这种封闭式表达式，例如Gosper 算法。所以 clang 可能正在应用类似的东西。我现在正在推测，但也许算法以未简化的形式输出一个公式，也许 clang 只是发出直接对应的代码，而不是首先尝试进行代数简化。
| 归档时间： |
|
| 查看次数： |
3298 次 |
| 最近记录： |