gcc - 如何检查 gcc 是否正在执行尾递归优化？

Question

如何判断 gcc（更具体地说，g++）是否正在优化特定函数中的尾递归？（因为它出现了几次：我不想测试 gcc 是否可以优化尾递归。我想知道它是否优化了我的尾递归函数。）

如果您的答案是“查看生成的汇编程序”，我想确切地知道我在寻找什么，以及是否可以编写一个简单的程序来检查汇编程序以查看是否有优化。

PS。我知道这似乎是问题的一部分，如果有的话，C++ 编译器会进行尾递归优化吗？从 5 个月前开始。但是，我认为该问题的这一部分没有得到令人满意的回答。（答案是“检查编译器是否进行了优化（据我所知）的最简单方法是执行一个调用，否则会导致堆栈溢出 - 或查看程序集输出。”）

score 69 · Accepted Answer

让我们使用另一个问题中的示例代码。编译它，但告诉 gcc 不要汇编：

gcc -std=c99 -S -O2 test.c

现在让我们看看生成的test.s_atoi文件中的函数（Mac OS 10.5 上的 gcc 4.0.1）：

        .text
        .align 4,0x90
_atoi:
        pushl   %ebp
        testl   %eax, %eax
        movl    %esp, %ebp
        movl    %eax, %ecx
        je      L3
        .align 4,0x90
L5:
        movzbl  (%ecx), %eax
        testb   %al, %al
        je      L3
        leal    (%edx,%edx,4), %edx
        movsbl  %al,%eax
        incl    %ecx
        leal    -48(%eax,%edx,2), %edx
        jne     L5
        .align 4,0x90
L3:
        leave
        movl    %edx, %eax
        ret

编译器对此函数进行了尾调用优化。我们可以判断，因为该代码中没有call指令，而原始 C 代码显然有一个函数调用。此外，我们可以看到jne L5在函数中向后跳转的指令，当 C 代码中明显没有循环时表示循环。如果您在关闭优化的情况下重新编译，您会看到一行显示call _atoi，并且您也不会看到任何向后跳转。

您是否可以自动执行此操作是另一回事。汇编代码的细节将取决于您正在编译的代码。

我认为你可以通过编程方式发现它。使函数打印出堆栈指针的当前值（在 x86 上注册 ESP）。如果函数在第一次调用时打印与递归调用相同的值，则编译器执行了尾调用优化。但是，这个想法需要修改您希望观察的函数，这可能会影响编译器选择优化函数的方式。如果测试成功（两次打印相同的 ESP 值），那么我认为可以合理地假设优化也将在没有您的仪器的情况下执行，但如果测试失败，我们将不知道失败是否是由于添加仪器代码。

score 15 · Accepted Answer

编辑我原来的帖子也阻止了 GCC 实际上进行尾调用消除。我在下面添加了一些额外的技巧，以使 GCC 无论如何都要进行尾调用消除。

扩展史蒂文的答案，您可以以编程方式检查您是否具有相同的堆栈帧：

#include <stdio.h>

// We need to get a reference to the stack without spooking GCC into turning
// off tail-call elimination
int oracle2(void) { 
    char oracle; int oracle2 = (int)&oracle; return oracle2; 
}

void myCoolFunction(params, ..., int tailRecursionCheck) {
    int oracle = oracle2();
    if( tailRecursionCheck && tailRecursionCheck != oracle ) {
        printf("GCC did not optimize this call.\n");
    }
    // ... more code ...
    // The return is significant... GCC won't eliminate the call otherwise
    return myCoolFunction( ..., oracle);
}

int main(int argc, char *argv[]) {
    myCoolFunction(..., 0);
    return 0;
}

非递归调用函数时，传入 0 检查参数。否则传入oracle。如果没有应该消除的尾递归调用，那么您将在运行时收到通知。

对此进行测试时，我的 GCC 版本似乎没有优化第一个尾调用，但优化了剩余的尾调用。有趣的。

score 7 · Accepted Answer

查看生成的汇编代码，看看它是否使用callorjmp指令进行 x86 上的递归调用（对于其他架构，请查找相应的指令）。您可以使用nmandobjdump来获取与您的功能相对应的程序集。考虑以下函数：

int fact(int n)
{
  return n <= 1 ? 1 : n * fact(n-1);
}

编译为

gcc fact.c -c -o fact.o -O2

然后，测试它是否使用尾递归：

# get starting address and size of function fact from nm
ADDR=$(nm --print-size --radix=d fact.o | grep ' fact$' | cut -d ' ' -f 1,2)
# strip leading 0's to avoid being interpreted by objdump as octal addresses
STARTADDR=$(echo $ADDR | cut -d ' ' -f 1 | sed 's/^0*\(.\)/\1/')
SIZE=$(echo $ADDR | cut -d ' ' -f 2 | sed 's/^0*//')
STOPADDR=$(( $STARTADDR + $SIZE ))

# now disassemble the function and look for an instruction of the form
# call addr <fact+offset>
if objdump --disassemble fact.o --start-address=$STARTADDR --stop-address=$STOPADDR | \
    grep -qE 'call +[0-9a-f]+ <fact\+'
then
    echo "fact is NOT tail recursive"
else
    echo "fact is tail recursive"
fi

当在上面的函数上运行时，这个脚本会打印“fact is tail recursive”。当使用而不是编译时-O3，-O2这会奇怪地打印“事实不是尾递归”。

请注意，正如 ehemient 在他的评论中指出的那样，这可能会产生假阴性。如果函数根本不包含对自身的递归调用，并且它也不会检测兄弟递归（例如 where A()calls B()which calls A()），此脚本只会产生正确的答案。目前我想不出一种更强大的方法，它不涉及人工查看生成的程序集，但至少您可以使用此脚本轻松获取与目标文件中特定函数相对应的程序集。

score 6 · Accepted Answer

扩展 PolyThinker 的答案，这里有一个具体的例子。

int foo(int a, int b) {
    if (a && b)
        return foo(a - 1, b - 1);
    return a + b;
}

i686-pc-linux-gnu-gcc-4.3.2 -Os -fno-optimize-sibling-calls输出：

00000000 <foo>:
   0: 55 推 %ebp
   1: 89 e5 移动 %esp,%ebp
   3: 8b 55 08 移动 0x8(%ebp),%edx
   6: 8b 45 0c 移动 0xc(%ebp),%eax
   9: 85 d2 测试 %edx,%edx
   b: 74 16 je 23 <foo+0x23>
   d: 85 c0 测试 %eax,%eax
   f: 74 12 je 23 <foo+0x23>
  11:51 推送 %ecx
  12：12 月 48 日
  13: 51 推送 %ecx
  14: 50 推%eax
  15: 8d 42 ff lea -0x1(%edx),%eax
  18: 50 推%eax
  19: e8 fc ff ff ff 调用 1a <foo+0x1a>
  1e: 83 c4 10 添加 $0x10,%esp
  21: eb 02 jmp 25 <foo+0x25>
  23: 01 d0 添加 %edx,%eax
  25：c9离开
  26：c3 回复

i686-pc-linux-gnu-gcc-4.3.2 -Os输出：

00000000 <foo>:
   0: 55 推 %ebp
   1: 89 e5 移动 %esp,%ebp
   3: 8b 55 08 移动 0x8(%ebp),%edx
   6: 8b 45 0c 移动 0xc(%ebp),%eax
   9: 85 d2 测试 %edx,%edx
   b: 74 08 je 15 <foo+0x15>
   d: 85 c0 测试 %eax,%eax
   f: 74 04 je 15 <foo+0x15>
  11：12 月 48 日
  12: 12 月 4 日 %edx
  13: eb f4 jmp 9 <foo+0x9>
  15: 5d 弹出 %ebp
  16: 01 d0 添加 %edx,%eax
  18：c3 雷特

在第一种情况下，<foo+0x11>-<foo+0x1d>为函数调用推送参数，而在第二种情况下，<foo+0x11>-<foo+0x14>将变量和jmps 修改为同一个函数，位于序言之后的某个位置。这就是你想要寻找的。

我认为您不能以编程方式执行此操作；有太多可能的变化。函数的“肉”可能离开始更近或更远，如果jmp不看它，你就无法将其与循环或条件区分开来。它可能是条件跳转而不是jmp. gcc在某些情况下可能会保留一个callin，但对其他情况应用同级调用优化。

仅供参考，gcc 的“兄弟调用”比尾递归调用更通用——实际上，任何可以重用相同堆栈帧的函数调用都可能是兄弟调用。

[编辑]

例如，当仅寻找自递归call会误导您时，

int bar(int n) {
    if (n == 0)
        return bar(bar(1));
    if (n % 2)
        return n;
    return bar(n / 2);
}

GCC 将对三个bar调用中的两个应用同级调用优化。我仍然称它为尾调用优化，因为单个未优化的调用永远不会超过单个级别，即使您会call <bar+..>在生成的程序集中找到 a 。

score 3 · Accepted Answer

我懒得看反汇编。试试这个：

void so(long l)
{
    ++l;
    so(l);
}
int main(int argc, char ** argv)
{
    so(0);
    return 0;
}

编译并运行这个程序。如果它永远运行，尾递归就被优化掉了。如果它破坏了堆栈，则不是。

编辑：对不起，读得太快了，OP想知道他的特定函数是否优化了尾递归。好的...

...原理仍然相同 - 如果尾递归被优化掉，那么堆栈帧将保持不变。您应该能够使用backtrace 函数从函数中捕获堆栈帧，并确定它们是否在增长。如果尾递归被优化掉，缓冲区中将只有一个返回指针。

score 2 · Accepted Answer

我检查的另一种方法是：

用'gcc -O2'编译你的代码
开始'gdb'
在您期望进行尾递归优化/消除的函数中放置一个断点
运行你的代码
如果已经消除了尾调用，则断点将只被命中一次或永远不会命中。有关这方面的更多信息，请参阅此

score 1 · Accepted Answer

一个简单的方法：构建一个简单的尾递归程序，编译，反汇编，看是否优化。

刚刚意识到你的问题中已经有了这个。如果您知道如何阅读汇编，则很容易分辨。递归函数将从函数体内调用自己（使用“调用标签”），并且循环将只是“jmp 标签”。

score 0 · Accepted Answer

如果没有优化，您可以制作由于该函数调用的递归太深而导致堆栈溢出的输入数据，并查看它是否发生。当然，这不是微不足道的，有时足够大的输入会使函数运行时间过长。

gcc - 如何检查 gcc 是否正在执行尾递归优化？

8 回答 8

Related

Reference