常數折疊
![本頁使用了標題或全文手工轉換](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)
常數摺疊(Constant folding)以及常數傳播(constant propagation)都是編譯器最佳化技術,他們被使用在現代的編譯器中。進階的常數傳播形式,或稱之為稀疏有條件的常數傳播(sparse conditional constant propagation),可以更精確地傳播常數及無縫的移除無用的程式碼。
常量摺疊
常數摺疊是一個在編譯時期簡化常數的一個過程,常數在表示式中僅僅代表一個簡單的數值,就像是整數 2
,若是一個變數從未被修改也可作為常數,或者直接將一個變數被明確地被標注為常數,例如下面的描述:
i = 320 * 200 * 32;
多數的現代編譯器不會真的產生兩個乘法的指令再將結果儲存下來,取而代之的,他們會辨識出語句的結構,並在編譯時期將數值計算出來(在這個例子,結果為2,048,000),通常會在中介碼(IR,intermediate representation)樹中進行。
有些編譯器,常數摺疊會在初期就處理完,所以像是C語言的陣列,初始化時就可以接受簡單的運算表示式。而將常數摺疊放在較後期的階段的編譯器,也相當常見。
常數摺疊可以在編譯器前端的IR樹完成,在程式碼轉換為三位址碼之前。常數摺疊也可以在後端完成,作為常數傳播的附加功能。
常數摺疊與跨平台編譯
在實現一個跨平台編譯器時,必須確保目標平台的算術運算的行為與編譯平台結構是吻合的,而且啓動常數摺疊將會改變程式的行為,這在浮點數的運算中是非常重要的,浮點數精確度問題的影響是非常廣的。
常數傳播
常數傳播是一個替代表示式中已知常數的過程,也是在編譯時期進行,包含前述所定義,內建函數也適用於常數,以下列描述為例:
int x = 14;
int y = 7 - x / 2;
return y * (28 / x + 2);
傳播x變數將會變成:
int x = 14;
int y = 7 - 14 / 2;
return y * (28 / 14 + 2);
持續傳播,則會變成:(還可以再進一步的消除無用程式碼x及y來進行最佳化)
int x = 14;
int y = 0;
return 0;
常數傳播在編譯器中使用定義可達性(Reaching definition)分析實作,如果一個變數的所有定義可達性,都是賦予相同的數值,那麼這個變數將會是一個常數,而且會被常數取代。
常數傳播也可能導致使狀態的分支簡化,或是變成更複雜,當狀態表示式在編譯時期可以被計算為TRUE或是FALSE時,就可以決定他唯一的一種可能。
最佳化的行為
常數摺疊及傳播通常會同時被使用在簡化以及減少,藉由交錯使用他們,一直到沒有必要再改變,舉例來說:
int a = 30;
int b = 9 - a / 5;
int c;
c = b * 4;
if (c > 10) {
c = c - 10;
}
return c * (60 / a);
使用常數傳播,再使用常數摺疊後,產生:
int a = 30;
int b = 3;
int c;
c = b * 4;
if (c > 10) {
c = c - 10;
}
return c * 2;
再做一次:
int a = 30;
int b = 3;
int c;
c = 12;
if (true) {
c = 2;
}
return c * 2;
當 a
及 b
已經被簡化為常數,他們的數值取代了程式碼中任何一個使用到變數的地方,編譯器接著將會使用死碼刪除(dead code elimination)來消除他們:
int c;
if (true) {
c = 2;
}
return c * 2;
在上述的程式,可以根據編譯器的框架來判別可以用1或是其他的布林常數來取代 True
,伴隨傳統的常數傳播,我們將得到相當多的最佳化,他無法改變程式的結構。
還有其他類似的最佳化,被稱之為稀疏有條件的常量傳播(sparse conditional constant propagation),他依據if狀態
選擇了合適的分支[1],編譯器偵測到 if
的描述中,將永遠被賦予TRUE, c
變數可以被消除,完成之後程式碼變成:
return 4;
如果這個虛擬碼為一個函數,編譯器將可將其以整數 4
來取代,以消除無用的函數呼叫,改進整體的運行效能。
參見
參考文獻
- ^ Wegman, Mark N; Zadeck, F. Kenneth, Constant Propagation with Conditional Branches, ACM Transactions on Programming Languages and Systems, April 1991, 13 (2): 181–210
延伸閱讀
- Muchnick, Steven S., Advanced Compiler Design and Implementation, Morgan Kaufmann, 1997, ISBN 9781558603202
|