Dead-code elimination

In compiler theory, dead-code elimination (DCE, dead-code removal, dead-code stripping, or dead-code strip) is a compiler optimization to remove dead code (code that does not affect the program results). Removing such code has several benefits: it shrinks program size (an important consideration in some contexts); reduces resource usage, such as the number of bytes to be transferred^[1]; and allows the running program to avoid executing irrelevant operations, which reduces its running time. It can also enable further optimizations by simplifying program structure. Dead code includes code that can never be executed (unreachable code) and code that only affects dead variables (written to, but never read again), that is, irrelevant to the program.

Consider the following example written in C.

intfoo(void){inta=24;intb=25;// Assignment to dead variableintc;c=a*4;returnc;b=24;// Unreachable codereturn0;}

Trivial analysis of the control flow would mark lines 7 and 8 for removal as they are never reached after return c;. If the procedure had a more complex control flow, such as a label after the return statement and a goto elsewhere in the procedure, then a feasible execution path might exist to the assignment to b.

Furthermore, simple analysis of the uses of values would then show that the value of b is only written to and never read from. b is declared as a local variable inside foo, so its value cannot be used outside foo. Thus, the variable b is dead and an optimizer can reclaim its storage space and eliminate its initialization.

Also, even though some calculations are performed in the function, their values are not stored in locations accessible outside the scope of this function. Furthermore, given the function returns a static value (96), it may be simplified to the value it returns (this simplification is called constant folding), resulting in:

intfoo(void){return96;}

ほとんどの高度なコンパイラには、デッドコード除去を有効にするオプションがあり、そのレベルは様々です。低いレベルでは、実行できない命令のみを削除する場合があります。高いレベルでは、未使用変数用のメモリ領域を確保しない場合もあります。さらに高いレベルでは、役に立たない命令や関数を特定して削除する場合もあります。

デッドコード除去の一般的な用途は、プリプロセッサによるオプションのコードインクルードの代替手段として使用されることです。次のコードを考えてみましょう。

// DEBUG_MODEをfalseに設定するconstexpr bool DEBUG_MODE = false ;int main ( void ) {int a = 5 ;int b = 6 ;整数c ;c = a * ( b / 2 );if ( DEBUG_MODE ) {printf ( "%d \n " , c );}cを返す;}

定数は常にfalseDEBUG_MODEと評価されるため(そのように定義されているため)、if 文内のコードは決して実行されず、デッドコード除去によって最適化されたプログラムから完全に削除されます。この手法はデバッグ時にコードブロックを任意にアクティブ化するためによく用いられます。デッドコード除去機能を備えたオプティマイザを使用すると、同じタスク (例えばthen ...) を実行するためにプリプロセッサを使用する必要がなくなります。#define DEBUG_MODE 0#if DEBUG_MODE

実際には、オプティマイザが見つけるデッドコードの多くは、オプティマイザ内の他の変換によって生成されます。たとえば、演算子強度削減の古典的な手法では、コードに新しい計算を挿入し、古い、よりコストのかかる計算をデッドコードにします。^{[ 2 ]}その後のデッドコード削除により、これらの計算が削除され、効果が完了します（強度削減アルゴリズムを複雑にすることなく）。

歴史的に、デッドコードの削除はデータフロー分析から得られた情報を使用して実行されていました。^{[ 3 ]}静的単一代入形式（SSA）に基づくアルゴリズムは、Ron Cytron らによるSSA形式に関する最初の論文に掲載されています。^{[ 4 ]} Robert Shillingsburg（別名 Shillner）は、このアルゴリズムを改良し、不要な制御フロー操作を削除するための付随アルゴリズムを開発しました。^{[ 5 ]}

• 冗長なコード
• 簡略化（記号計算）
• 部分的な冗長性の排除
• 接続詞の除去
• 動的なソフトウェア更新
• 動的結合（コンピューティング）
• 自己移転
• ソフトウェアの不要な要素
• ツリーシェイキング–動的言語向けのバンドル時DCE（リンク時DCEに類似）
• パス後の最適化
• プロファイルに基づいた最適化
• スーパーオプティマイザー
• 機能のマルチバージョン化

• Bodík, Rastislav; Gupta, Rajiv (1997年6月)「スライシング変換を用いた部分的なデッドコード除去」ACM SIGPLAN 1997 プログラミング言語設計および実装に関する会議 (PLDI '97) 議事録: 682–694。
• Aho, Alfred Vaino ; Sethi, Ravi ; Ullman, Jeffrey David (1986). Compilers - Principles, Techniques and Tools . Addison Wesley Publishing Company . ISBN 0-201-10194-7。
• ムチニック、スティーブン・スタンレー（1997）。高度なコンパイラ設計と実装。モーガン・カウフマン出版。ISBN 1-55860-320-4。
• ディック・グルーン;アンリ・エル・バル;ジェイコブズ、セリエル JH;ランゲンドーエン、Koen G. (2000)。最新のコンパイラ設計。ジョン・ワイリー・アンド・サンズ社ISBN 0-471-97697-0。
• Kennedy, Ken ; Allen, Randy (2002). 「第 4.4 章 データ フロー解析 - 第 4.4.2 章 デッド コード除去」『現代アーキテクチャ向けコンパイラの最適化: 依存性に基づくアプローチ』（ 2011 年初版デジタル版 ）。Academic Press / Morgan Kaufmann Publishers / Elsevier。pp . 137、145–147、167。ISBN  978-1-55860-286-1。LCCN 2001092381。 
• Muth, Robert; Debray, Saumya K.; Watterson, Scott; De Bosschere, Koen (2001年1月) [1999-11-02]. "alto: Compaq Alpha 用リンクタイム最適化ツール". Software: Practice and Experience . 31 (1): 67– 101. CiteSeerX 10.1.1.33.4933 . doi : 10.1002/1097-024X(200101)31:1 < 67::AID-SPE357 > 3.0.CO ; 2-A . S2CID 442062 .  

• C/C++コンパイラを騙してひどいコードを生成させる方法とは？