为什么在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，因为可能会有8*%rax+16，它给出相同的结果，看起来更自然？

由x86-64位的GCC 11.2编译的其他汇编语言代码看起来几乎是一样的，数字22被替换为15，那么这个数字是随机决定的，还是出于某种原因？

Answer 1

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

回想一下，在任何call指令之前，堆栈指针必须是16的倍数。因此，当我们进入read_and_process时，堆栈指针比16的倍数小8，因为让我们进入这里的call压入了8个字节。因此，在调用read_val()之前，堆栈指针必须比16的倍数递减8，即8的奇数倍。序号将奇数个寄存器(5个，即rbp, r14, r13, r12, rbx)推入每个寄存器的8个字节。因此，剩余的堆栈调整必须是16的倍数。

因此，无论分配给数组vals的内存量是多少，都必须向上舍入到16的倍数。一种标准的做法是添加15，然后使用-16：adjusted = (orig + 15) & -16。

多亏了二的补码运算，-16的低4位被清除，其他位被置位，所以与-16的结果是16的倍数-但由于和清除低阶位，x & -16的结果小于x；这是向下舍入。如果我们先加15 (当然是1减16)，净效果就是四舍五入。将15加到orig将导致它传递16的倍数，然后& -16将向下舍入到16的倍数。除非orig已经是16的倍数，在这种情况下，orig+15将向下舍入到orig本身。所以这在所有情况下都是正确的。

这就是GCC从8.1.0开始所做的事情。将15添加到将n乘以8的相同lea中，并将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是个bug。这是一个相当小的bug；生成的代码仍然工作得很好，并且符合ABI，唯一的负面影响是有时会浪费一点堆栈空间。但这是由a commit entitled "Improve alloca alignment"为GCC 8.1.0修复的。(alloca是一个执行动态堆栈分配的旧的非标准函数，编译器编写者经常使用这个术语来指代任何堆栈分配。)

显然，问题是编译器之前的一些步骤已经确定需要将大小对齐到(至少)8字节，这可以通过将7和ANDing与-8相加来实现(当编译器后来意识到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的加法一开始就不应该存在。在带有-O0的较新版本的GCC中，lea rdx, [rax+7]消失了。

Answer 2

为什么需要计算8*%rax+22，然后和-16，因为可能有8*%rax+16，它给出相同的结果，看起来更自然。

它不会给出相同的结果。表达式( ( rax*8 + 22 ) % -16 )将输出对齐16个字节。

在64位CPU上，以这种方式写入时，-16等同于0xFFFFFFFFFFFFFFF0，很明显AND指令正在做什么:它从值中剥离四个最低有效位，这使得结果按16字节对齐，向下舍入。( ( rax*8 + 15 ) % -16 )表达式按16个字节进行对齐，向上舍入。但是编译器还需要8个字节的对齐，因为它使用5个push指令将5个值推送到堆栈，而每个指令都是8个字节。

您的下一个问题可能是“当alignof(Long)=8时，为什么按16个字节对齐？”

答案是preferred-stack-boundary编译器选项。在GCC中，该选项默认为4，这意味着编译器将堆栈帧对齐2^4 = 16字节。

尝试使用-mpreferred-stack-boundary=3 ( BTW，这是AMD64允许的最小值)编译相同的代码。它要求对齐大小至少为一个指针)，并查看程序集发生了什么情况。