clang如何为平方和生成非循环代码？

Question

我承认这个问题的答案可能是“一些非常具体的魔法”，但我对我在这里观察到的有点震惊。我想知道是否有人了解这些类型的优化是如何工作的。我发现编译器设计非常有趣，我真的无法想象这是如何工作的。我肯定答案在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（n1）（2n1）]/6，但我认为这不是真正的问题。

然后我想知道clang将如何为一个简单的C版本生成汇编。在编写简单的C实现时，我发现带有< code>-Og的clang会生成assembly，这看起来有点冗长，但通常使用循环和累加器时会像预期的那样工作(尽管效率非常低):

int sum_squares(int n)
{
    int a = 0;

    while (n--)
        a += (n * n);

    return a;
}

(< code >铿锵-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是< code>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编译器怎么可能被给一个这样的循环，并且推导出一个甚至不包含循环的公式？我期待一些循环展开，也许，但没有像这样。有人参考过这种类型的优化吗？

我尤其不明白像< code>orr w9，w9，#0x2或幻数0x55555556这样的某些步骤是干什么的。对这些步骤的任何见解都将不胜感激。

Answer 1

TL:DR:是的，clang知道整数幂级数和的封闭形式公式，并且可以检测到这样的循环。聪明的人已经教会现代编译器识别某些操作模式，并用源代码中不存在的操作替换它们，例如循环，甚至是popcount循环和bithacks。特别是对于clang/LLVM，还有i^power和的闭合形式公式，包括步长不为1的公式。数学太棒了。因此，您可以获得asm逻辑，而不仅仅是源代码的展开或矢量化版本。

另请参阅一篇博客文章LLVM如何优化幂和，该文章讨论了编译器如何通过查看变量如何在循环迭代中更新来找到这些循环。

Matthieu M.评论道，闭式公式是由LLVM中的标量进化优化导出的。代码中的注释表示，它主要用于分析循环中包含归纳变量的表达式。并引用了其用于复发链的技术的参考文献。

现代C编译器可以在代码的内部表示中识别某些循环或逻辑短序列中的模式。人类（编译器开发人员）已经告诉编译器要寻找什么，并提供了手工制作的替换“公式”。我希望在GIM譬如GCC或LLVM-IR中，不仅仅是编译后期，比如在生成ASM时进行窥视孔优化。

因此，我猜LLVM优化器内部的逻辑会检查它找到的每个循环，以寻找以下一种或多种可能性，并使用一些代码来查找LLVM-IR的某些属性，该属性表示该循环的程序逻辑：

• 它是否未经修改就将一个阵列复制到另一个阵列？如果是，请替换为__builtin_memcpy，稍后可能会内联扩展或编译为调用memcpy。如果它有其他副作用，比如让指针变量递增，也可以在包含循环的函数的新LLVM-IR中表示
• 它是否将内存范围的每个字节设置为一个恒定的字节值？如果是，memset
• 它的操作序列与popcnt的操作序列等价吗？如果存在硬件支持，则发出＜code＞popcnt＜/code＞，否则保持循环策略。（因此，它不只是将其视为__builtin_popcount，而不是将循环替换为位破解或对辅助函数的调用。这是有意义的，因为有些策略适合于设置了很少位的数字，程序员可能会考虑到这一点。）
• 循环变量是用一系列整数的和（有一定步幅）更新的，还是提升到幂？然后使用避免固定宽度整数溢出的闭式公式。（如果起点和步幅不是1，请添加偏移和/或比例因子。）

检查可以考虑循环修改的变量，该变量在循环之后读取。因此，它知道在查看操作时要考虑什么变量。（没有使用结果的循环将被删除。）

GCC不会寻找整数序列的和，但clang会。IDK这实际上加速了多少真实世界的代码库；封闭形式公式相当有名，高斯在上学时就重新发现了它。（所以希望很多代码使用公式而不是循环）。我想，没有多少程序需要完全这样做，除了作为练习。

(封闭形式的平方和公式的存在不太为人所知，但确实存在，而且显然也适用于一般幂。)

当然，当C抽象机器没有遇到未定义的行为（对于有符号整数溢出）时，Clang对公式的实现必须为每个输入整数给出精确的正确结果，或者匹配无符号乘法的截断。否则，它将无法满足好像规则，或者只能在内联到已知有限值范围的地方时使用。（实际上，clang似乎没有对无符号使用封闭形式优化，但也许我只是在尝试的版本中犯了一个错误。使用64位整数可以安全地计算32位整数的总和。然后截断可能会给出与源相同的结果。）

在n*（n1）/2仍在范围内的情况下，n*（n 1）可能会溢出，因此这是非常重要的。对于64位机器上的32位＜code＞int＜/code＞，LLVM可以并且确实简单地使用64位乘法和右移。这可能是对使用双倍宽度输出和扩展精度右移的一般情况的窥视优化，如果产品不适合一个寄存器，则跨两个寄存器。（例如，x86＜code＞shrd edx，eax，1＜/code＞在＜code＞mul r32＜/code>生成edx:eax中的64位乘积后，将低位从高位移到eax的顶部。）

它也做 n * （n-1） / 2 n 而不是通常的 n * （n 1）/2;不知道这有什么帮助。我想，它避免了输入类型的溢出，以防万一对于原始循环只有包装而不是 UB 的无符号类型很重要。除非它不对无符号进行此优化。（顺便说一句，n 或 n -1 是偶数，所以除法（右移）是精确的;这很好，因为整数的总和最好是整数。

在平方和中，您可以看到它使用umull x， w， w进行加宽乘法，并在32位乘法逆除以3之前进行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--，并首先溢出 n是非负的。但如果不是，IDK为什么要制作更复杂的代码，而且要加倍。

// 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 复制/粘贴的标准位黑客。（这很有用，因为 ISO C 无法提供大多数现代 CPU 具有的可移植方法来表达此操作。ISO C 仅在 C 20 中修复了该缺陷

这些模式识别器只工作在一些特定的方式来实现PopCount，即x

变量名当然不重要，但是输入变量的操作顺序很重要。我假设在检查等价性时，以给出相同结果的方式重新排序操作有一定的灵活性。在GCC的情况下，显然< code > number _ of _ iterations _ pop count 是发现这一点的函数的名称:编译器通常想知道一个循环将运行多少次迭代:如果它是一个小常数，他们可能会完全展开它。如果它可以在开始循环之前从其他变量中计算出来，那么它就是自动矢量化的候选对象。(GCC/clang不能自动向量化搜索循环，或者任何具有数据相关if()中断的东西。)

如上面的答案所示，计算32位整数中的设置位数，GCC10和clang10（上帝螺栓）也可以使用SWAR bithack识别PopCount，因此您可以两全其美：理想情况下是一条指令，但如果不是，那么至少是一个好的策略。

计算< code>x的迭代次数

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

通过模式识别进行代码替换的最简单形式之一是编译＜code＞（n

但这可能在编译过程中发生得足够晚，你可以称之为窥视孔优化。CISC ISA倾向于有更多的窥视孔优化，比如x86有特殊情况的更短指令来在累加器中签名（cdqe而不是movzx eax， ax）。x86xor-将寄存器设置为零的归零仍然可以称为窥视孔，尽管有时需要重新排列东西，因为这会破坏FLAGS，而mov eax，0不会。

GCC 使用 -fpeephole2（-O2 的一部分）实现异或归零;也许将其视为只是一个窥视孔是GCC有时做得不好并且无法找到重新排序的方法的原因，因此xor-zero / cmp / setcc而不是cmp / setcc / movzx，因为x86 setcc根据FLAGS条件设置寄存器很糟糕，只写入低8位。 AArch64 有更好的指令，比如 csinc 可以与零寄存器一起使用以实现 0/1，或者与其他寄存器一起使用以实现有条件的选择和增量。

但系列循环的总和是一个更大规模的替换，并不是我认为的窥视孔，特别是因为它不是特定于目标的。

还相关：

>

是否允许 C 编译器用另一种算法替换算法？ - 是的。但通常他们不会，因为编译器足够机械，以至于它们并不总是正确的，并且为数据选择一个有效的算法是 C 程序员希望编译器尊重的东西，除非有一个指令显然总是更快。

clang知道如何使用AVX2 vpshub作为半字节的查找表在数组上自动矢量化__builtin_popcount。它不仅仅是从相同的操作中制作 SIMD 版本，而是再次使用人类编译器开发人员放置的扩展以供其使用。

为什么编译器优化不会为1… N的整数之和生成循环？是关于这种优化没有发生的情况，例如带有j的情况

注释中发现了一些关于clang何时可以优化的有趣限制：例如，如果循环是＜code＞for（int j=0；j

Answer 2

至少让事情开始，这是你的“基本数论”公式，尽管以一种相当混乱和低效的形式。clang开发人员显然也上了这门课。

一些有助于验证它的提示:

> < li>

您的< code>sum_squares函数有一个减一的错误，其总和仅为< code>n-1。因此，我们期望得到的公式是< code>n(n-1)(2n-1)/6。

在这种情况下，＜code＞orr w9，w9，#0x2＜/code＞等同于＜code＞add w9，w 9，#x2＜/ccode＞。上一条指令＜code＞mul w9，w8，w8＜/code＞加载了＜code＞w9＜/code>和＜code＞w8＜/code＞的平方。现在，mod 4的唯一完美正方形是0和1，这两个正方形都有位1清除，因此w9的位1将始终清除。因此，w9|2等同于w9|2。（不，我不知道为什么clang会这样做。）

正如harold所评论的，乘以0x55555556相当于mod 2^32除以3和乘以2（假设没有余数）。这种技术有时被称为“神奇的数字除法”。请参阅为什么GCC在实现整数除法时使用奇怪数字的乘法？。所以在此之前，您有x11=（（n-1）（n-2）（n-3））/2，请注意，它总是3的倍数（除以2总是精确的，因为分子总是偶数）。因此w11*w12导致（n-1）（n-2）（n-3）/6。

将所有这些放在一起，您可以检查代数以验证最终结果等价于< code>n(n-1)(2n-1)/6。

我不能说clang是如何执行这种优化的。我想我曾经经历过弄清楚哪个LLVM优化通过使它发生的练习，但我不记得它是什么。但是有已知的算法可以自动导出这种封闭形式的表达式，例如戈斯珀算法。所以clang可能正在应用类似的东西。我现在正在推测，但也许算法会以未简化的形式吐出一个公式，也许clang只是发出直接对应的代码，而不是先尝试代数简化。