我承认答案可能是“某些非常特定的魔法”，但我对这里观察到的情况感到震惊。我想知道这些类型的优化如何工作。我发现编译器设计非常有趣，但我真的无法想象这是如何实现的。我确定答案在clang源代码中某个地方，但我甚至不知道该去哪里找。
我是大学课程的TA，最近被要求帮助解决一个简单的作业问题。这使我走上了一条有趣的道路...
问题很简单：在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实现后，我发现使用-Og选项的clang会生成似乎有点冗长但通常按预期工作的汇编代码，其中包括循环和累加器（尽管非常低效）：
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就产生了一些神奇的代码。我不知道它是如何得出这段代码的，它似乎与这个求和的基本公式有些相似，但却用了位运算。我没想到编译器能在没有循环的情况下推导出这个公式，但事实证明我错了。生成的代码如下（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是什么意思。对这些步骤的任何见解都将不胜感激。