posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

原来GCC是支持尾递归的递推优化的

Posted on 2008-05-24 02:05 ZelluX 阅读(2414) 评论(1)  编辑  收藏 所属分类: C/C++

水木上有人贴了个有趣的程序

#include  < stdlib.h >
#include  < stdio.h >

void  print_forever( int  n)
 {
    printf( " %d\n " , n);
    print_forever(n  +   1 );
}

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

用gcc -O2编译运行后会不停地打印从0开始的自然数，注意如果编译器没有做优化的话，打印到某个数的时候肯定会发生栈溢出从而程序终止的情况，但这个程序却能一直运行下去，说明编译器做了尾递归优化。

用gcc -O2 -S生成这个程序的汇编代码后证实了这一点。
.L6:
        movl    %ebx, 4(%esp)
        addl    $1, %ebx
        movl    $.LC0, (%esp)
        call    printf
        jmp     .L6
print_forever的关键部分被优化成了一个n不断增加的死循环。

接下来是分析哪个优化选项处理了尾递归。

用O3 O2 O1三个优化强度编译程序，查看汇编代码后，发现尾递归优化是O2中新增的功能。于是查看O2新开启的优化开关：
gcc -c -Q -O1 --help=optimizers > /tmp/O1-opts
gcc -c -Q -O2 --help=optimizers > /tmp/O2-opts
diff /tmp/O2-opts /tmp/O1-opts | grep enabled
输出结果：

经证实是-foptimize-sibling-calls这个选项实现了尾递归的优化，具体内容可以参看
http://gcc.gnu.org./ml/gcc-patches/2000-03/msg00867.html

评论

# re: 原来GCC是支持尾递归的递推优化的  回复  更多评论   

2013-09-02 22:37 by darkhorse
我在ubuntu下面汇编的结果是：

print_forever:
pushl %ebp
movl %esp, %ebp
pushl %ebx
subl $20, %esp
movl 8(%ebp), %ebx
.p2align 4,,7
.p2align 3

怎么跟你的不一样？

只有注册用户登录后才能发表评论。
网站导航: