デッドコードの削除

コンパイラ理論 では、デッドコード除去（DCE、デッドコード削除、デッドコードストリッピング、またはデッドコードストリップ）は、デッドコード（プログラムの結果に影響を与えないコード）を削除するコンパイラの最適化です。このようなコードを削除すると、いくつかの利点があります。プログラムのサイズが縮小します（一部の状況では重要な考慮事項です）。転送するバイト数などのリソース使用量が削減されます^{[ 1 ]}。実行中のプログラムが無関係な操作の実行を回避できるため、実行時間が短縮されます。また、プログラム構造を簡素化することで、さらなる最適化が可能になります。デッドコードには、決して実行されないコード（到達不能コード）と、デッド変数（書き込まれるが二度と読み込まれない）にのみ影響するコード、つまりプログラムに無関係なコードが含まれます。

C言語で書かれた以下の例を考えてみましょう。

int foo ( void ) {int a = 24 ;int b = 25 ; // デッド変数への代入整数c ;c = a * 4 ;cを返す;b = 24 ; // 到達不能なコード0を返す;}

制御フローを単純に分析すると、 の後には決して到達しないため、7 行目と 8 行目は削除対象としてマークされますreturn c;。プロシージャの制御フローがより複雑で、例えば return ステートメントの後にラベルがあり、gotoプロシージャの別の場所に がある場合、 への代入まで実行可能なパスが存在する可能性がありますb。

さらに、値の使用状況を簡単に分析すると、の値はbに書き込まれるだけで、から読み取られることはないことがわかります。bは内部でローカル変数として宣言されているfooため、その値は外部では使用できませんfoo。したがって、変数は無効bであり、オプティマイザはその記憶領域を解放し、初期化を省略できます。

また、関数内で計算が行われる場合でも、その値は関数のスコープ外からアクセス可能な場所に格納されません。さらに、関数は静的な値（96）を返すため、その値に単純化することができます（この単純化は定数畳み込みと呼ばれます）。その結果、次のようになります。

int foo ( void ) {96を返す;}

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

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

// 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++コンパイラを騙してひどいコードを生成させる方法とは？