Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

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

Posted on 2008-05-24 02:05 ZelluX 阅读(2097) 评论(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

怎么跟你的不一样?

只有注册用户登录后才能发表评论。


网站导航: