为什么GCC的VLA（可变长度数组）实现中有数字22？

Question

int read_val();
long read_and_process(int n) {
    long vals[n];
    for (int i = 0; i < n; i++)
        vals[i] = read_val();
    return vals[n-1];
}

x86-64 GCC 5.4编译的汇编语言代码为：

read_and_process(int):
        pushq   %rbp
        movslq  %edi, %rax
>>>     leaq    22(,%rax,8), %rax
        movq    %rsp, %rbp
        pushq   %r14
        pushq   %r13
        pushq   %r12
        pushq   %rbx
        andq    $-16, %rax
        leal    -1(%rdi), %r13d
        subq    %rax, %rsp
        testl   %edi, %edi
        movq    %rsp, %r14
        jle     .L3
        leal    -1(%rdi), %eax
        movq    %rsp, %rbx
        leaq    8(%rsp,%rax,8), %r12
        movq    %rax, %r13
.L4:
        call    read_val()
        cltq
        addq    $8, %rbx
        movq    %rax, -8(%rbx)
        cmpq    %r12, %rbx
        jne     .L4
.L3:
        movslq  %r13d, %r13
        movq    (%r14,%r13,8), %rax
        leaq    -32(%rbp), %rsp
        popq    %rbx
        popq    %r12
        popq    %r13
        popq    %r14
        popq    %rbp
        ret

为什么需要计算 8*%rax+22，然后与 -16 进行 AND，因为可能有 8*%rax+16，这会给出相同的结果并且看起来更自然？

x86-64 GCC 11.2 编译的其他汇编语言代码看起来几乎相同，只是数字 22 被替换为 15。那么这个数字只是随机确定的，还是因为某些原因？

Answer 1

摘要：该数字不是随机的，它是确保正确堆栈对齐的计算的一部分。这个数字应该是 15，而 22 是旧版本 GCC 中一个小错误的结果。

回想一下，x86-64 SysV ABI 要求 16 字节堆栈对齐；任何指令之前的堆栈指针必须是 16 的倍数call。因此，当我们输入 时read_and_process，堆栈指针比 16 的倍数小 8，因为call我们在这里推送了 8 个字节。因此，在调用 之前read_val()，堆栈指针必须递减 8，大于 16 的倍数，即 8 的奇数倍。序言将奇数个寄存器（即 5 个rbp, r14, r13, r12, rbx）压入其中，每个寄存器 8 个字节。所以剩余的堆栈调整必须是16的倍数。

因此，无论要为数组分配多少内存vals，都必须向上舍入为 16 的倍数。标准方法是先加 15，然后与 -16: 进行 AND 运算adjusted = (orig + 15) & -16。

为什么这样有效？ -16，由于二进制补码运算，低 4 位被清除，其他位被设置，因此 AND 的-16结果是 16 的倍数 - 但由于 AND 清除低位，所以结果x & -16小于x; 这是向下舍入。如果我们先加上 15（当然，比 16 少 1），最终的结果就是向上舍入。添加 15 将orig导致其传递 16 的倍数，然后向下& -16舍入为16的倍数 。除非 orig已经是 16 的倍数，在这种情况下orig+15向下舍入回orig自身。所以这在所有情况下都是正确的。

这就是 GCC 从 8.1.0 开始所做的事情。加 15 就等于lea乘以n8，AND-16会在几行之后出现。

在本例中，由于orig = 8*n已经是 8 的倍数，因此除了 15 之外还有其他值也可以工作；例如 8（虽然不是 16，见下文）。但使用 15 在数学上以及代码大小和速度方面是完全等效的，并且由于无论先前的对齐方式如何，15 都可以工作，因此编译器作者可以无条件地使用 15，而无需编写额外的代码来跟踪可能orig已经具有的对齐方式。

但像旧版 GCC 那样添加 22 显然是错误的。如果orig已经是 16 的倍数，比如说orig = 32，那么orig+22就是 54，四舍五入为 48。但是 32 字节已经是一个完美的大小，所以我们无缘无故地浪费了 16 字节。（这里orig是8*n这样，如果输入n是偶数，就会发生这种情况。）出于类似的原因，您使用 16 而不是 22 的建议也是错误的。

所以22是一个错误。这是一个相当小的错误；生成的代码仍然可以正常工作并符合 ABI，唯一的不良影响是有时会浪费一点堆栈空间。但它在 GCC 8.1.0 中被一个名为“改进分配对齐”的提交修复了。（alloca是一个古老的非标准函数，它执行动态堆栈分配，编译器编写者经常使用该术语来指代任何堆栈分配。）

显然，问题在于编译器之前的一些传递已确定需要将大小对齐到（至少）8 字节，这可以通过添加 7 并与 -8 进行 AND 运算来完成（稍后可能会在编译器后来意识到它n*8已经对齐到 8 字节）。现在，当编译器意识到实际上需要 16 字节对齐时，这个约束应该是多余的，因为 16 的每个倍数都已经是 8 的倍数。但是编译器错误地添加了偏移量 7 和 15，而正确的做法是取最大值（这是提交所实现的）。7 + 15 是... 22。

如果您使用 GCC 5.4 并关闭优化来编译代码，您可以看到这两个操作分别发生：

        lea     rdx, [rax+7]  ; add 7 to rax and write to rdx
        mov     eax, 16
        sub     rax, 1        ; now rax = 15
        add     rax, rdx      ; add 15 to rdx

当优化开启时，优化器将这些组合成一个 22 的加法 - 没有注意到 7 的加法一开始就不应该存在。在较新版本的 GCC 中-O0，lea rdx, [rax+7]已消失。