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

Question

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

如果您的答案是"查看生成的汇编程序",我想知道我正在寻找什么,以及我是否可以编写一个简单的程序来检查汇编程序以查看是否存在优化.

PS.我知道这似乎是问题的一部分,如果有的话,C++编译器会进行尾递归优化吗？从5个月前.但是,我不认为这个问题的这一部分得到了令人满意的答复.(答案是"检查编译器是否进行了优化(我知道)的最简单方法是执行调用,否则会导致堆栈溢出 - 或者查看汇编输出.")

Answer 1

让我们使用其他问题的示例代码.编译它,但告诉gcc不要汇编:

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

现在让我们看看_atoi生成的test.s文件中的函数(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值),那么我认为假设优化也将在没有您的仪器的情况下执行是合理的,但如果测试失败,我们将无法知道失败是否是由于添加了仪器代码.

Answer 2

编辑我的原始帖子也阻止了GCC实际进行尾部呼叫抵消.我在傻瓜GCC之下添加了一些额外的技巧,无论如何都要进行尾部调用消除.

扩展Steven的答案,您可以通过编程方式检查是否具有相同的堆栈帧:

#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;
}

在非递归地调用函数时,将check参数传入0.否则传入oracle.如果应该已经消除的尾递归调用不是,那么将在运行时通知您.

测试时,看起来我的GCC版本没有优化第一个尾调用,但剩余的尾调用已经过优化.有趣.

Answer 3

查看生成的汇编代码,看看它是否在x86上使用call或jmp指令进行递归调用(对于其他架构,查找相应的指令).您可以使用nm和objdump获取与您的函数对应的程序集.考虑以下功能:

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,这奇怪地打印"事实不是尾递归".

请注意,这可能会产生假阴性,正如他的评论中指出的那样.如果函数根本不包含对自身的递归调用,则此脚本将仅产生正确的答案,并且它也不会检测兄弟递归(例如,A()调用的B()调用A()).我现在想不出一个更强大的方法,不需要人工查看生成的程序集,但至少可以使用此脚本轻松获取对应于目标文件中特定函数的程序集.

Answer 4

扩展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                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   8b 55 08                mov    0x8(%ebp),%edx
   6:   8b 45 0c                mov    0xc(%ebp),%eax
   9:   85 d2                   test   %edx,%edx
   b:   74 16                   je     23 <foo+0x23>
   d:   85 c0                   test   %eax,%eax
   f:   74 12                   je     23 <foo+0x23>
  11:   51                      push   %ecx
  12:   48                      dec    %eax
  13:   51                      push   %ecx
  14:   50                      push   %eax
  15:   8d 42 ff                lea    -0x1(%edx),%eax
  18:   50                      push   %eax
  19:   e8 fc ff ff ff          call   1a <foo+0x1a>
  1e:   83 c4 10                add    $0x10,%esp
  21:   eb 02                   jmp    25 <foo+0x25>
  23:   01 d0                   add    %edx,%eax
  25:   c9                      leave
  26:   c3                      ret

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

00000000 <foo>:
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   8b 55 08                mov    0x8(%ebp),%edx
   6:   8b 45 0c                mov    0xc(%ebp),%eax
   9:   85 d2                   test   %edx,%edx
   b:   74 08                   je     15 <foo+0x15>
   d:   85 c0                   test   %eax,%eax
   f:   74 04                   je     15 <foo+0x15>
  11:   48                      dec    %eax
  12:   4a                      dec    %edx
  13:   eb f4                   jmp    9 <foo+0x9>
  15:   5d                      pop    %ebp
  16:   01 d0                   add    %edx,%eax
  18:   c3                      ret

在第一种情况下,<foo+0x11>-<foo+0x1d>推送函数调用的参数,而在第二种情况下,<foo+0x11>-<foo+0x14>将变量和jmps 修改为相同的函数,在前导码之后的某处.这就是你想要的东西.

我认为你不能以编程方式做到这一点; 有太多可能的变化.函数的"肉"可能更接近或远离开始,并且您无法jmp在不看它的情况下将其与循环或条件区分开来.它可能是条件跳转而不是jmp. gcc可能会call在某些情况下留下来,但将兄弟呼叫优化应用于其他情况.

仅供参考,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+..>在生成的程序集中找到了一个单一的未优化调用也不会超过单个级别.