posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

          原來GCC是支持尾遞歸的遞推優(yōu)化的

          Posted on 2008-05-24 02:05 ZelluX 閱讀(2453) 評論(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編譯運(yùn)行后會不停地打印從0開始的自然數(shù),注意如果編譯器沒有做優(yōu)化的話,打印到某個數(shù)的時候肯定會發(fā)生棧溢出從而程序終止的情況,但這個程序卻能一直運(yùn)行下去,說明編譯器做了尾遞歸優(yōu)化。

          用gcc -O2 -S生成這個程序的匯編代碼后證實(shí)了這一點(diǎn)。
          .L6:
          ????????movl????
          %ebx,?4(%esp)
          ????????addl????$
          1,?%ebx
          ????????movl????$.LC0,?(
          %esp)
          ????????call????printf
          ????????jmp?????.L6
          print_forever的關(guān)鍵部分被優(yōu)化成了一個n不斷增加的死循環(huán)。

          接下來是分析哪個優(yōu)化選項(xiàng)處理了尾遞歸。

          用O3 O2 O1三個優(yōu)化強(qiáng)度編譯程序,查看匯編代碼后,發(fā)現(xiàn)尾遞歸優(yōu)化是O2中新增的功能。于是查看O2新開啟的優(yōu)化開關(guān):
          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
          輸出結(jié)果:

          經(jīng)證實(shí)是-foptimize-sibling-calls這個選項(xiàng)實(shí)現(xiàn)了尾遞歸的優(yōu)化,具體內(nèi)容可以參看
          http://gcc.gnu.org./ml/gcc-patches/2000-03/msg00867.html

          評論

          # re: 原來GCC是支持尾遞歸的遞推優(yōu)化的  回復(fù)  更多評論   

          2013-09-02 22:37 by darkhorse
          我在ubuntu下面匯編的結(jié)果是:

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

          怎么跟你的不一樣?
          主站蜘蛛池模板: 泰和县| 忻州市| 镇康县| 方城县| 丹棱县| 井研县| 龙胜| 荔浦县| 通渭县| 耒阳市| 玉林市| 隆林| 图木舒克市| 南郑县| 五指山市| 合江县| 荆州市| 界首市| 崇明县| 阜宁县| 区。| 饶平县| 平陆县| 泾川县| 渑池县| 巢湖市| 万山特区| 武义县| 大城县| 沈丘县| 泽普县| 农安县| 惠水县| 香港 | 克拉玛依市| 枞阳县| 噶尔县| 洞头县| 汤阴县| 婺源县| 崇左市|