Snowdream

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

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

Posted on 2008-05-24 02:05 ZelluX 阅读(1083) 评论(0)  编辑  收藏 所属分类: 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

标题  
姓名  
主页
验证码 *  
内容(请不要发表任何与政治相关的内容)  
  登录  使用高级评论  新用户注册  返回页首  恢复上次提交      
 
 
相关链接:
网站导航: