首页 > 代码库 > Gcc 优化选项 与尾递归优化
Gcc 优化选项 与尾递归优化
今天做高性能计算机系统的作业的时候，发现gcc中的优化选项有很多应用 。
例如对于C源码：
#include <stdio.h>#include <stdlib.h>int main(){ int x[101],y[101]; int a,i; a = 5; for(i=0;i<=100;i++) { x[i] = i+1; y[i] = i; } for(i=100; i>=0; i--) y[i] += a*x[i]; return 0;}
1、直接用gcc main.c –S –O0进行编译，即禁止编译器进行优化，生成的汇编语言文件为:
.file "main.c" .def ___main; .scl 2; .type 32; .endef .text.globl _main .def _main; .scl 2; .type 32; .endef_main: pushl %ebp movl %esp, %ebp andl $-16, %esp subl $816, %esp call ___main movl $5, 808(%esp) movl $0, 812(%esp) jmp L2L3: movl 812(%esp), %eax movl 812(%esp), %edx incl %edx movl %edx, 404(%esp,%eax,4) movl 812(%esp), %eax movl 812(%esp), %edx movl %edx, (%esp,%eax,4) incl 812(%esp)L2: cmpl $100, 812(%esp) jle L3 movl $100, 812(%esp) jmp L4L5: movl 812(%esp), %eax movl 812(%esp), %edx movl (%esp,%edx,4), %ecx movl 812(%esp), %edx movl 404(%esp,%edx,4), %edx imull 808(%esp), %edx leal (%ecx,%edx), %edx movl %edx, (%esp,%eax,4) decl 812(%esp)L4: cmpl $0, 812(%esp) jns L5 movl $0, %eax leave ret
2、当用gcc main.c –S –O1进行编译的时候，尝试优化编译时间和可执行文件大小等，汇编程序如下：
1 .file "main.c" 2 3 .def ___main; .scl 2; .type 32; .endef 4 5 .text 6 7 .globl _main 8 9 .def _main; .scl 2; .type 32; .endef10 11 _main:12 13 pushl %ebp14 15 movl %esp, %ebp16 17 andl $-16, %esp18 19 call ___main20 21 movl $0, %eax22 23 leave24 25 ret
3、当用gcc main.c –S –O2进行编译的时候，会进行部分优化，但不进行循环展开和函数内联等操作，相比于O1的1级优化得到的汇编代码，多了一条对齐指令即.p2align 2,3；汇编程序如下：
1 .file "main.c" 2 3 .def ___main; .scl 2; .type 32; .endef 4 5 .text 6 7 .p2align 2,,3 8 9 .globl _main10 11 .def _main; .scl 2; .type 32; .endef12 13 _main:14 15 pushl %ebp16 17 movl %esp, %ebp18 19 andl $-16, %esp20 21 call ___main22 23 xorl %eax, %eax24 25 leave26 27 ret
4、用gcc main.c –S –O3进行优化时，会进行循环展开，分支预测，函数内联等，但与O2的2级优化得到的汇编代码一样，可能是因为在O2和O3的Gcc都能识别尾递归调用并进行优化，所以在这里使用了尾调用方式，从代码中也可以看到有一条递归调用指令call main。查资料得到，实现尾递归优化的选项是-foptimize-sibling-calls，是O2新增的的功能。汇编程序如下：
1 .file "main.c" 2 3 .def ___main; .scl 2; .type 32; .endef 4 5 .text 6 7 .p2align 2,,3 8 9 .globl _main10 11 .def _main; .scl 2; .type 32; .endef12 13 _main:14 15 pushl %ebp16 17 movl %esp, %ebp18 19 andl $-16, %esp20 21 call ___main22 23 xorl %eax, %eax24 25 leave26 27 ret
说到尾递归，则要说到递归调用。尾递归的wiki解释如下：
尾部递归是一种编程技巧。递归函数是指一些会在函数内调用自己的函数，如果在递归函数中，递归调用返回的结果总被直接返回，则称为尾部递归。尾部递归的函数有助将算法转化成函数编程语言，而且从编译器角度来说，亦容易优化成为普通循环。这是因为从电脑的基本面来说，所有的循环都是利用重复移跳到代码的开头来实现的。如果有尾部归递，就只需要叠套一个堆栈，因为电脑只需要将函数的参数改变再重新调用一次。利用尾部递归最主要的目的是要优化，例如在Scheme语言中，明确规定必须针对尾部递归作优化。[1][2]可见尾部递归的作用，是非常依赖于具体实现的。(http://zh.wikipedia.org/wiki/%E5%B0%BE%E9%80%92%E5%BD%92)
这种调用总是在函数末尾执行，并且不会用到调用函数里的任何局部变量。所以有些编译器对此进行优化，在被调用函数执行时，直接利用调用函数的堆栈，不需要重新开辟堆栈空间，所以一般不会导致递归中出现的栈溢出。而一般递归因为调用过程中会存储局部变量，所以调用次数太多时就会发生溢出。但是并不是所有编译器都会对尾递归进行优化，一般在函数式编程语言中会优化。所以当在gcc中用了-O2或者-O3优化选项之后，就会对尾递归进行优化，一般不会造成溢出，而默认的进行可能会造成溢出。可以参考这篇博文：http://www.cnblogs.com/JeffreyZhao/archive/2009/04/01/tail-recursion-explanation.html。其中说到：与普通递归相比，由于尾递归的调用处于方法的最后，因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义，因此完全可以把本次方法中留在堆栈中的数据完全清除，把空间让给最后的递归调用。这样的优化便使得递归不会在调用堆栈上产生堆积，意味着即时是“无限”递归也不会让堆栈溢出。
Gcc 优化选项 与尾递归优化