死碼刪除
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() | 此條目包含過多行話或專業術語,可能需要簡化或提出進一步解釋。 (2013年3月16日) |
![]() | 此條目需要精通或熟悉相關主題的編者參與及協助編輯。 (2013年3月16日) |
編譯器原理中,死碼消除(Dead code elimination)是一種編譯最佳化技術,它的用途是移除對程式執行結果沒有任何影響的程式碼。移除這類的程式碼有兩種優點,不但可以減少程式的大小,還可以避免程式在執行中進行不相關的運算行為,減少它執行的時間。不會被執行到的程式碼(unreachable code)以及只會影響到無關程式執行結果的變數(Dead Variables),都是死碼(Dead code)的範疇。
範例
下列的範例,以C語言寫成:
int foo(void)
{
int a = 24;
int b = 25; /* 賦值給一個無用的變數*/
int c;
c = a << 2;
return c;
b = 24; /* 不會被執行到的程式碼*/
return 0;
}
分析上述程式對於數值的使用,將會發現b
的數值在第一次被賦值之後,就不再使用,而且b
是在foo
函數內宣告,無法在函數外面使用,所以變數b
是無用的,最佳化的過程可以回收他所使用的空間,並刪除他的初始化。
當第一個return
被執行,則代表函數已經結束,之後變數b
的賦值行為則不會被執行,所以賦值行為是可以被刪除的。如果程式有更複雜的控制流程,例如在第一個return
之後加上一個標簽,使得程式中任和一個地方都可以用goto
來執行到這個程式段,那麼變數b
的賦值行為將有可能被執行。
儘管一些計算行為被包裝成函數,他們的數值也無法被函數外所存取,但仍然還是有些函數僅會回傳一個固定的數值,這或許可以將該數值取代所有函數的呼叫。(這個簡化的過程被稱之為常數折疊)
更進階的編譯器則會有些選項可以啓動死碼刪除的功能,而有些則是可以選擇不同等級的死碼刪除,比較低階等級的死碼刪除僅會移除不會被執行到的指令,而較高階的可能不會保留無用變數的空間,其他高階等級的做法可能會判斷哪些指令及函數沒有任何用途,並且刪除他們。
死碼刪除最普遍的做法,是透過預處理器來判斷程式碼是否需要被編譯,如下列這個範例:
int main(void) {
int a = 5;
int b = 6;
int c;
c = a * (b >> 1);
if (0) { /* DEBUG */
printf("%d\n", c);
}
return c;
}
由於0將永遠被視為False,所以if判斷式內的程式將永遠不會被執行,死碼刪除將會把它移除,這個技術在除錯上相當常見,我們可以透過一個數值來決定程式段是否該被編譯,使用死碼刪除的最佳化過程,將會使用預處理器來進行相同的工作。
實作中,有些在最佳化過程中找到的死碼,是被其他最佳化技術產生,舉例來說,典型強度折減的技術,將會在程式碼內插入新的運算以取代昂貴的運算行為,而被取代的程式碼就成了死碼[1],隨後,死碼刪除會移除那些計算,以完成這個效果(沒有複雜的強度折減演算法)。
從歷史上來看,死碼刪除使用來自資料流分析的資訊[2],Cytron et al在原始文章中發佈了一個基於靜態單賦值形式的演算法[3],Shillingsburg改進了這個演算法,並開發了一個演算法來移除無用的控制流(Control-flow)[4]。
動態死碼刪除
死碼通常被視為無條件的(unconditionally),所以我們可以在編譯時期透過死碼刪除來移除這些無用的程式碼。
然而,在實作上,只有在特定的情形才會標注一個程式碼區段是無用的,或是不會執行到的,這可能無法在編譯時期所得知。例如在不同的執行環境有不同的結果(舉例來說,目標環境可能會有不同的作業系統版本,或是不同的驅動程式及可用服務的組合),可能會在程式碼內要求不同特例的集合,同時在這些案例下就變成有條件的死碼。然而,軟件(例如驅動程式、或是常駐服務)可能會根據用戶的設置,而組態或排除特定的功能,使得在一些特定的情境,會變成部分無用的死碼。模組化軟件實作方式,是在需要時才讀取動態函式庫,在多數的案例中,不可能僅從特定的函式庫讀取相關的程式,它仍然會包含一些程式片段,在特定的環境下是可被視為死碼,但是這在編譯時期是無法被排除的。
動態死碼刪除(dynamic dead code elimination)被使用在執行時動態偵測,可辨識及解析相依性,用以移除有條件的死碼,在執行時期重新組合保留的程式碼。
多數的電腦語言、編譯器、作業系統不提供,或是僅比動態讀取函式庫及後連結(late linking)提供多一點點的功能,能使用動態死碼刪除的軟件是相當稀少的。
參考文獻
Partial dead code elimination using slicing transformations Found in: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation (PLDI '97) By Rastislav Bodík, Rajiv Gupta Issue Date:June 1997 pp. 682–694
- ^ Frances Allen, John Cocke, and Ken Kennedy. Reduction of Operator Strength. In Program Flow Analysis, Muchnick and Jones (editors), Prentice-Hall, 1981.
- ^ Ken Kennedy. A Survey of Data-flow Analysis Techniques. In Program Flow Analysis, Muchnick and Jones (editors), Prentice-Hall, 1981.
- ^ Ron Cytron, Jeanne Ferrante, Barry Rosen, and Ken Zadeck. Efficiently Computing Static Single Assignment Form and the Program Dependence Graph. ACM TOPLAS 13(4), 1991.
- ^ Keith D. Cooper and Linda Torczon, Engineering a Compiler, Morgan Kaufmann, 2003, pages 498ff.
參考書籍
- Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. Compilers - Principles, Techniques and Tools. Addison Wesley Publishing Company. 1986. ISBN 0-201-10194-7.
- Muchnick, Steven S. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers. 1997. ISBN 1-55860-320-4.
- Grune, Dick; Bal, Henri E.; Jacobs, Ceriel J.H.; Langendoen, Koen G. Modern Compiler Design. John Wiley & Sons, Inc. 2000. ISBN 0-471-97697-0.
外部連結
|