为什么gcc -O3会生成多个ret指令？

Question

我正在查看一些递归函数，来自这里：

int get_steps_to_zero(int n)
{
    if (n == 0) {
        // Base case: we have reached zero
        return 0;
    } else if (n % 2 == 0) {
        // Recursive case 1: we can divide by 2
        return 1 + get_steps_to_zero(n / 2);
    } else {
        // Recursive case 2: we can subtract by 1
        return 1 + get_steps_to_zero(n - 1);
    }
}

我检查了反汇编代码，以确定gcc是否进行了尾递归优化/展开。看起来它做到了，但是使用x86-64 gcc 12.2 -O3，我得到了像这样的一个函数，以两个ret指令结尾：

get_steps_to_zero:
        xor     eax, eax
        test    edi, edi
        jne     .L5
        jmp     .L6
.L10:
        mov     edx, edi
        shr     edx, 31
        add     edi, edx
        sar     edi
        test    edi, edi
        je      .L9
.L5:
        add     eax, 1
        test    dil, 1
        je      .L10
        sub     edi, 1
        test    edi, edi
        jne     .L5
.L9:
        ret
.L6:
        ret

Godbolt example。

多个返回的目的是什么？这是一个错误吗？

---

编辑

似乎是从gcc 11.x开始出现的。在使用gcc 10.x编译时，函数的结尾如下:

.L1:
        mov     eax, r8d
        ret
.L6:
        xor     r8d, r8d
        mov     eax, r8d
        ret

比如：将结果存储在eax中。11.x版本改为在函数开始时将eax清零，然后在函数体内修改它，从而消除了额外的mov指令。

- Lundin

---

对我来说，这似乎是一个被忽略的优化。另一个可能的原因是两个“ret”指令对应不同的源代码行。将它们分开保持可能会提供更精确的调试信息。 - fuz

@fuz 如果是这样，为什么不对应原始C源代码中的3个return，使用3个ret呢？ - Lundin

@phuclv 不是很确定。那个问题来自2020年，gcc 11于2021年发布之后行为发生了变化。 - Lundin

我已发布了一个具体回答来解决你的问题，而且链接中的原因是相同的。你对我的解释满意吗？ - amonakov

@amonakov 我在上面的编辑中得出了同样的结论，我使用旧版gcc进行编译。一个标签也会将eax设置为零。我主要是好奇为什么，因为我的编辑中的代码也可以在第二个mov eax，r8d行处设置L1标签。但显然这是一个已知的错误。 - Lundin

Answer 1

这是pass ordering问题的一种表现。在优化管道的某个时刻，以ret结尾的两个基本块不相等，然后某个pass使它们变得相等，但是没有后续的pass能够将这两个相等的块合并成一个。

在Compiler Explorer上，您可以通过检查各个pass之间的内部表示快照来了解编译器优化流程。对于GCC，请在编译器窗格中选择“Add New > GCC Tree/RTL”。这是您的示例，在新窗格中预先选择了有问题转换之前的快照: https://godbolt.org/z/nTazM5zGG 在转储的末尾，您可以看到两个基本块：

   65: NOTE_INSN_BASIC_BLOCK 8
   77: use ax:SI
   66: simple_return

并且

  43: NOTE_INSN_BASIC_BLOCK 9
    5: ax:SI=0
   38: use ax:SI
   74: NOTE_INSN_EPILOGUE_BEG
   75: simple_return

基本上第二个块不同的地方在于返回之前将eax设置为零。如果你看下一次通过（称为“jump2”），你会发现它把ax:SI=0指令从基本块9和基本块3提取到基本块2中，使得BB 9与BB 8等价。

如果你使用-fno-crossjumping禁用此优化，差异将一直保留到最后，导致生成的汇编代码更加出人意料。

- amonakov

Answer 2

首先得出结论：这是GCC的一种有意的优化选择。

如果您在本地使用GCC（gcc -O3 -S），而不是在Godbolt上使用，您会发现两个ret指令之间有对齐指令。

; top part omitted
.L9:
        ret
        .p2align 4,,10
        .p2align 3
.L6:
        ret
        .cfi_endproc

当反汇编目标文件时，填充区域中包含一个 NOP：

   8:   75 13                   jne    1d <get_steps_to_zero+0x1d>
   a:   eb 24                   jmp    30 <get_steps_to_zero+0x30>
   c:   0f 1f 40 00             nopl   0x0(%rax)
<...>
  2b:   75 f0                   jne    1d <get_steps_to_zero+0x1d>
  2d:   c3                      ret
  2e:   66 90                   xchg   %ax,%ax
  30:   c3                      ret

第二个ret指令对齐到16字节边界，而第一个则没有。当从远处的源作为跳转目标使用时，这使处理器能够更快地加载指令。然而，随后的C return语句足够靠近第一个ret指令，以至于它们不会从跳转到对齐的目标中获益。

在我的Zen 2 CPU上使用-mtune=native，这种对齐甚至更加明显，添加了更多的填充字节：

  29:   75 f2                   jne    1d <get_steps_to_zero+0x1d>
  2b:   c3                      ret
  2c:   0f 1f 40 00             nopl   0x0(%rax)
  30:   c3                      ret

- iBug

---

ret是1字节长，且无条件跳转。在它后面加载后续指令字节没有任何用处，并且包括它的任何代码块的任何代码获取都将得到整个指令。对其进行对齐没有益处。而且，如果这种推理是正确的，我们也会预期较早的jmp .L6也会指向“对齐”的ret，只有通过fall-through才能到达不对齐的部分。 - Peter Cordes

@PeterCordes .L6 是 对齐的 ret。假设你的意思是另一种方式，那是因为 jmp .L9 指令足够接近（<16字节）不对齐的 ret，以至于在 jmp 进入执行阶段之前就已经被加载了，所以没有必要加载一个更远的 ret 仅用作跳转目标。 - iBug

如果有人对GCC内部足够熟悉，我们可以通过查找GCC内部的代码来确认这个答案，该代码检查跳转目标范围并在其超过16字节时发明一个新的对齐的结尾块。但是这种方式很难证明否定，需要挖掘大量的代码来证明没有这样的代码存在。 - Peter Cordes

@PeterCordes 另一个（猜测）是GCC没有在最低级别的IR中跨基本块进行优化。 - iBug

@PeterCordes 仍然没有解释到 gcc 在 10.x.x 版本之前的行为，见问题的编辑。或者查看这里 https://godbolt.org/z/48dPjv9Pf。为什么他们不跳过 L1 标签下面的部分，直接将 L1 标签移到最后的 mov eax, r8d ？它是相同奇怪代码的不同风味。我认为问题的答案部分在于版本 11.x.x 中代码生成/优化上的一些变化。 - Lundin