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

          怎么跟你的不一樣？
          
			
          
		




          








          

				
			
          
		          		
	
          
	
          
		
			


		
	
          

          



    







          
        
	




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