死碼刪除

編譯器原理中，死碼消除（Dead code elimination）是一種編譯最佳化技術，它的用途是移除對程式執行結果沒有任何影響的程式碼。移除這類的程式碼有兩種優點，不但可以減少程式的大小，還可以避免程式在執行中進行不相關的運算行為，減少它執行的時間。不會被執行到的程式碼（unreachable code）以及只會影響到無關程式執行結果的變數（Dead Variables），都是死碼（英语：dead code）（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

1. Frances Allen, John Cocke, and Ken Kennedy. Reduction of Operator Strength. In Program Flow Analysis, Muchnick and Jones (editors), Prentice-Hall, 1981.
2. Ken Kennedy. A Survey of Data-flow Analysis Techniques. In Program Flow Analysis, Muchnick and Jones (editors), Prentice-Hall, 1981.
3. 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.
4. 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.  引文使用过时参数coauthors (帮助)

• 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.  引文使用过时参数coauthors (帮助)

外部連結

• How to trick C/C++ compilers into generating terrible code?