デッドコードの除去

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

Cで書かれた次の例を考えてみましょう。

int foo ( void ) { int a = 24 ; int b = 25 ; /* 無効な変数への代入 */ int c ; c = a * 4 ; return c ; b = 24 ; /* 到達不可能なコード */ return 0 ; }  
     
      
   
      
   
     
   

値の使用を簡単に分析すると、b最初の割り当て後の の値は の内部では使用されていないことがわかります。fooさらに、bは の内部でローカル変数として宣言されているfooため、その値は の外部で使用することはできませんfoo。したがって、 変数は不要bであり、オプティマイザは変数のストレージ領域を再利用して初期化を省略できます。

さらに、最初の return 文は無条件に実行され、その後に "goto" が到達できるラベルがないため、 への 2 番目の割り当てに到達する実行可能なパスはありません。bしたがって、割り当ては到達不可能であり、削除できます。プロシージャに、return 文の後のラベルやプロシージャ内の他の場所など、より複雑な制御フローgotoがある場合は、 への割り当てへの実行可能な実行パスが存在する可能性がありますb。

また、関数内でいくつかの計算が実行される場合でも、その値は関数のスコープ外でアクセス可能な場所に格納されません。さらに、関数が静的な値 (96) を返す場合、関数が返す値に簡略化される可能性があります (この簡略化は定数の畳み込みと呼ばれます)。

高度なコンパイラのほとんどには、デッドコードの削除を有効にするオプションがあり、そのレベルはさまざまです。低いレベルでは、実行できない命令のみが削除されることがあります。高いレベルでは、未使用の変数用のスペースも確保されないことがあります。さらに高いレベルでは、役に立たない命令や関数が判別され、削除されることがあります。

デッドコード除去の一般的な使用法は、プリプロセッサを介したオプションのコード組み込みの代替としてです。次のコードを考えてみます。

int main ( void ) { int a = 5 ; int b = 6 ; int c ; c = a * ( b / 2 ); if ( 0 ) { /* DEBUG */ printf ( "%d \n " , c ); } return c ; }  
     
     
   
        
       
     
  
   

式 0 は常にfalseと評価されるため、 if ステートメント内のコードは実行されず、デッドコード除去によって最適化されたプログラムから完全に削除されます。この手法は、コード ブロックをオプションでアクティブ化するためにデバッグでよく使用されます。デッドコード除去機能を備えたオプティマイザーを使用すると、同じタスクを実行するために プリプロセッサを使用する必要がなくなります。

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

歴史的に、デッドコードの除去はデータフロー解析から得られた情報を使用して実行されました。^[3]静的単一割り当て形式(SSA)に基づくアルゴリズムは、 Ron Cytron らによるSSA形式に関するオリジナルのジャーナル記事に記載されています。 ^[4] Robert Shillingsburg (別名 Shillner) は、このアルゴリズムを改良し、無駄な制御フロー操作を削除するためのコンパニオンアルゴリズムを開発しました。^[5]

通常、デッドコードは無条件にデッドコードとみなされます。したがって、コンパイル時にデッドコード除去を行うことでデッドコードを削除しようとするのは合理的です。

しかし、実際には、コードセクションが特定の条件下でのみデッドコードまたは到達不能コードを表すこともよくあり、その条件はコンパイル時またはアセンブリ時にはわからない場合があります。このような条件は、異なるランタイム環境（たとえば、オペレーティングシステムの異なるバージョン、または特定のターゲット環境にロードされるドライバーまたはサービスの異なるセットと組み合わせ）によって課される場合があります。これにより、コードに異なる一連の特殊なケースが必要になる場合がありますが、同時に、他のケースでは条件付きでデッドコードになります。^{[6] [7]}また、ソフトウェア（たとえば、ドライバーまたは常駐サービス）は、ユーザーの好みに応じて特定の機能を含めたり除外したりするように構成できる場合があり、特定のシナリオでは未使用のコード部分が役に立たなくなります。^{[6] [7]}モジュール式ソフトウェアは、オンデマンドでのみライブラリを動的にロードするように開発される場合がありますが、ほとんどの場合、特定のライブラリから関連するルーチンのみをロードすることはできず、たとえこれがサポートされている場合でも、ルーチンには、特定のシナリオではデッドコードと見なすことができるが、コンパイル時に除外できなかったコードセクションが含まれる場合があります。

動的に需要を検出し、依存関係を識別して解決し、条件付きでデッドコードを削除し、ロード時または実行時に残りのコードを再結合するために使用される技術は、動的デッドコード除去^{[6] [7] [8] [9] [10] [11] [12 ] [13] [14 ] [15] [16] [17] [18]}または動的デッド命令除去と呼ばれます。^[19]

ほとんどのプログラミング言語、コンパイラ、オペレーティングシステムは、ライブラリの動的ロードと遅延リンク以上のサポートをまったく提供していないか、提供しているとしてもわずかであるため、事前にコンパイルされた言語やアセンブリ言語で書かれた言語と組み合わせて動的なデッドコード除去を利用するソフトウェアは非常にまれです。 [ ^{8] [12] [9]ただし、}ジャストインタイムコンパイルを行う言語実装では、デッドコード除去のために動的に最適化される場合があります。^{[18] [20] [21]}

焦点はかなり異なりますが、同様のアプローチが動的ソフトウェア更新やホットパッチにも利用されることがあります。

• 冗長コード
• 簡略化（記号計算）
• 部分的な冗長性の排除
• 接続詞の除去
• 動的なソフトウェア更新
• 動的結合（コンピューティング）
• 自己移転
• ソフトウェアの欠陥
• 木を揺らす
• パス後の最適化
• プロファイルガイドによる最適化
• スーパーオプティマイザー
• 関数のマルチバージョン化

• Bodík, Rastislav、Gupta, Rajiv (1997 年 6 月)。「スライス変換を使用した部分的なデッド コード除去」。ACM SIGPLAN 1997 プログラミング言語設計および実装会議 (PLDI '97) の議事録: 682–694。
• Aho, Alfred Vaino ; Sethi, Ravi ; Ullman, Jeffrey David (1986)。コンパイラ- 原理、テクニック、ツール。Addison Wesley Publishing Company。ISBN 0-201-10194-7。
• Muchnick, Steven Stanley (1997)。Advanced Compiler Design and Implementation。Morgan Kaufmann Publishers。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 年第 1 版デジタル印刷)。Academic Press / Morgan Kaufmann Publishers / Elsevier。pp . 137、145–147、167。ISBN 978-1-55860-286-1LCCN  2001092381 。
• Muth, Robert; Debray, Saumya K.; Watterson, Scott; De Bosschere, Koen (2001 年 1 月) [1999-11-02]. 「alto: Compaq Alpha のリンク時オプティマイザ」.ソフトウェア: 実践と経験. 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.[5]

• C/C++ コンパイラを騙してひどいコードを生成させるにはどうすればよいでしょうか?