最適化コンパイラ

最適化コンパイラは、プログラムの実行時間、メモリ使用量、ストレージサイズ、電力消費を最小限に抑えるなどの面で最適化されたコードを生成するように設計されたコンパイラです。^{[1]最適化は通常、}最適化変換のシーケンスとして実装されます。最適化変換は、コードを変換して、ある側面に最適化された意味的に同等のコードを生成するアルゴリズムです。

実際には、利用可能なメモリやプログラマがコンパイルを待つ意思があるかどうかなどの要因によって、コンパイラが提供する最適化が制限されます。研究によると、最適化問題の中にはNP完全であったり、決定不可能であったりするものもあります。^{[2]一般的に、最適化では}最適な出力は得られません。これは、ある側面を最適化すると別の側面のパフォーマンスが低下する可能性があるためです。代わりに、最適化は一般的なプログラムでリソースの使用率を改善するためのヒューリスティックな方法です。^[3]^{: 585}

分類

ローカルスコープとグローバルスコープ

スコープは、入力コードのどの程度が最適化の適用対象と見なされるかを示します。

ローカルスコープの最適化は、基本ブロックにローカルな情報を使用します。^[4]基本ブロックには制御フロー文が含まれていないため、これらの最適化では最小限の分析しか必要とせず、時間とストレージ要件が削減されます。ただし、ジャンプ間では情報は保持されません。

グローバルスコープの最適化は、手続き内最適化とも呼ばれ、個々の関数に対して作用します。^[4]これにより、処理できる情報が増えますが、多くの場合、コストのかかる計算が必要になります。関数呼び出しが発生したり、グローバル変数にアクセスしたりする場合、それらについて利用できる情報が限られているため、最悪のケースを想定しなければなりません。

ピープホールの最適化

ピープホール最適化は、通常、マシンコードが生成された後のコンパイルプロセスの後半で実行されます。この最適化では、隣接するいくつかの命令を調べて（コードを「のぞき穴から見る」のと似ています）、それらを単一の命令またはより短い一連の命令に置き換えることができるかどうかを確認します。 ^[3]^{: 554}たとえば、値の2倍の乗算は、値を左シフトするか、値自体に加算することで、より効率的に実行できます（この例も強度削減の例です）。

手続き間の最適化

プロシージャ間の最適化では、プログラムのソースコード全体を分析します。利用できる情報が多いほど、最適化の効果は高まります。この情報は、関数の呼び出しを関数本体のコピーに置き換える関数のインライン化など、さまざまな最適化に使用できます。

リンク時の最適化

リンク時最適化(LTO)、またはプログラム全体の最適化は、より一般的なクラスのプロシージャ間最適化です。LTO 中、コンパイラは翻訳単位全体にわたって可視性を持つため、モジュール間のインライン化や仮想化解除などのより積極的な最適化を実行できます。

マシンとオブジェクトコードの最適化

マシンコードの最適化では、すべてのマシンコードがリンクされた後にオブジェクトコードオプティマイザを使用してプログラムを分析します。共通の命令シーケンスを圧縮してスペースを節約するマクロ圧縮などの手法は、実行可能なタスクイメージ全体が分析に利用できる場合により効果的になります。^[5]

言語非依存と言語依存

ほとんどの高水準プログラミング言語は、分岐構造 (if、switch)、ループ構造 (for、while)、カプセル化構造 (構造体、オブジェクト) などの共通のプログラミング構造と抽象化を共有しています。したがって、言語間で同様の最適化手法を使用できます。ただし、特定の言語機能により、一部の最適化が困難になります。たとえば、CおよびC++のポインターにより、配列の最適化が困難になります (エイリアス分析を参照)。ただし、ポインターもサポートするPL/Iなどの言語では、配列の最適化が実装されています。逆に、一部の言語機能により、特定の最適化が容易になります。たとえば、一部の言語では、関数に副作用が許可されていません。したがって、プログラムが同じ引数を使用して同じ関数を複数回呼び出す場合、コンパイラーは、関数の結果は 1 回だけ計算する必要があると推測できます。関数に副作用が許可されている言語では、コンパイラーは、副作用がないと判断できる関数にそのような最適化を制限できます。

マシン非依存 vs. マシン依存

抽象的なプログラミング概念 (ループ、オブジェクト、構造) を操作する最適化の多くは、コンパイラがターゲットとするマシンに依存しませんが、最も効果的な最適化の多くは、ターゲットプラットフォームの特殊な機能を最大限に活用する最適化です。例としては、レジスタのデクリメントやゼロでない場合は分岐など、一度に複数の処理を実行する命令があります。

以下は、ローカルマシン依存の最適化の例です。レジスタを 0 に設定するには、レジスタ値を定数に設定する命令で定数 '0' を使用するのが明白な方法です。あまり明白ではない方法は、レジスタをそれ自体とXOR することです。どの命令バリアントを使用するかは、コンパイラーが判断します。多くのRISCマシンでは、両方の命令は同じ長さで同じ時間がかかるため、どちらも同等に適切です。Intel x86ファミリなどの他の多くのマイクロプロセッサでは、即値オペランドをデコードする必要も、内部の「即値オペランドレジスタ」を使用する必要もないため、 XOR バリアントの方が短く、おそらく高速であることがわかります。これに伴う潜在的な問題は、XOR によってレジスタの以前の値に対するデータ依存性が生じ、パイプラインストールが発生する可能性があることです。パイプラインストールは、前の命令の結果に依存するためプロセッサが命令の実行を遅らせる必要がある場合に発生します。ただし、プロセッサは、レジスタをそれ自体と XOR することを、ストールが発生しない特別なケースとして扱うことがよくあります。

最適化に影響を与える要因

ターゲットマシン: 特定の最適化を適用できるかどうか、また適用すべきかどうかは、ターゲットマシンの特性に依存する。GCCやClangなどの一部のコンパイラは、マシンに依存する要素をパラメータ化して、異なるマシン向けに最適化できるようにしている。^[6]

ターゲットCPUアーキテクチャ

レジスタの数: レジスタを使用してパフォーマンスを最適化できます。ローカル変数はスタックではなくレジスタに格納できます。一時的/中間結果には、低速のメモリではなくレジスタでアクセスできます。

RISC vs. CISC : CISC 命令セットは、多くの場合、命令長が可変であり、^[7]使用可能な命令の数が多いことが多く、各命令にかかる時間が異なる場合があります。 RISC 命令セットは、これらのそれぞれにおける可変性を制限しようとします。命令セットの長さは通常一定ですが、例外はほとんどありません。レジスタとメモリ操作の組み合わせは通常少なく、命令発行率 (時間間隔あたりに完了する命令の数、通常はクロックサイクルの整数倍) は、メモリレイテンシが要因でない場合は通常一定です。特定のタスクを実行するには複数の方法がある場合があり、CISC では通常、RISC よりも多くの選択肢が提供されます。コンパイラは、さまざまな命令間の相対的なコストを認識し、最適な命令シーケンスを選択する必要があります (命令の選択を参照)。

パイプライン: パイプラインは、CPU をアセンブリラインに分割したものです。パイプラインでは、命令の実行を命令デコード、アドレスデコード、メモリフェッチ、レジスタフェッチ、計算、レジスタストアなどのさまざまな段階に分割することで、CPU の一部をさまざまな命令に使用できます。1 つの命令がレジスタストア段階にあるときに、別の命令がレジスタフェッチ段階にある場合があります。パイプラインの競合は、パイプラインのある段階の命令が、パイプライン内でその命令より前にあり、まだ完了していない別の命令の結果に依存する場合に発生します。パイプラインの競合は、パイプラインストール(CPU が競合の解決を待機してサイクルを無駄にする状態) につながる可能性があります。コンパイラーは、パイプラインストールの発生頻度が低くなるように命令をスケジュール(並べ替え) できます。

機能ユニットの数: 一部の CPU には、複数の命令を同時に実行できる複数のALUとFPU があります。どの命令が他のどの命令とペアになるか (「ペアリング」とは、2 つ以上の命令を同時に実行することです)、およびどの機能ユニットがどの命令を実行できるかに制限がある場合があります。また、パイプラインの競合に似た問題もあります。機能ユニットが完全にロードされるように命令をスケジュールできます。

機械アーキテクチャ

CPU キャッシュのサイズとタイプ (ダイレクトマップ、2/4/8/16 ウェイアソシエイティブ、フルアソシエイティブ):インライン展開やループアンローリングなどの手法により、生成されるコードのサイズが大きくなり、コードの局所性が低下する可能性があります。頻繁に使用されるコードセクション (さまざまなアルゴリズムの内部ループなど) が突然キャッシュに収まらなくなると、プログラムが大幅に遅くなる可能性があります。また、フルアソシエイティブでないキャッシュでは、キャッシュがいっぱいになっていてもキャッシュ衝突が発生する可能性が高くなります。

キャッシュ/メモリ転送速度: キャッシュミスのペナルティをコンパイラに通知します。これは主に特殊なアプリケーションで使用されます。

使用目的

デバッグ: 開発中は、コンパイル速度を上げたり、実行可能コードのデバッグを容易にしたりするために、最適化が無効になることがよくあります。変換、特にコードの順序を変更する変換を最適化すると、実行可能コードとソースコードを関連付けることが困難になることがあります。

汎用的な使用: 事前にパッケージ化されたソフトウェアは、多くの場合、同じ命令セットを共有しながらもパフォーマンス特性が異なるさまざまなマシンで実行することが想定されています。コードは特定のマシンに最適化されていないか、最も人気のあるマシンで最適に動作するように調整されているものの、他のマシンでは最適に動作しないことがあります。

特殊用途: ソフトウェアが均一な特性を持つマシン用にコンパイルされている場合、コンパイラはそれらのマシン用に生成されたコードを大幅に最適化できます。

注目すべきケースとしては、特別な並列化コンパイラが使用される並列プロセッサおよびベクトルプロセッサ用に設計されたコードが挙げられます。

組み込みシステムのファームウェアは、ターゲット CPU とメモリに合わせて最適化できます。システムコストや信頼性は、コード速度よりも重要になる場合があります。たとえば、組み込みソフトウェアのコンパイラは通常、速度を犠牲にしてコードサイズを削減するオプションを提供します。コードのタイミングは、できるだけ速くするのではなく、予測可能である必要がある場合があるため、コードキャッシュと、それを必要とするコンパイラの最適化は無効にされることがあります。

共通のテーマ

最適化には、次のような、時には矛盾するテーマが含まれます。

一般的なケースを最適化する: 一般的なケースでは、低速パスを犠牲にして高速パスを許可する独自のプロパティがある場合があります。高速パスをより頻繁に使用すると、全体的なパフォーマンスが向上します。
冗長性を避ける: すでに計算された結果を再利用し、再計算するのではなく、後で使用するために保存します。
コードが少ない: 不要な計算と中間値を削除します。CPU、キャッシュ、メモリの作業が減ると、通常は実行速度が速くなります。また、組み込みシステムでは、コードが少ないほど製品コストが低くなります。
直線コード（分岐なしコードとも呼ばれる）を使用することでジャンプが少なくなる: よりシンプルなコード。ジャンプ (条件付きまたは無条件の分岐) は命令のプリフェッチを妨害するため、コードの速度が低下します。インライン展開またはループ展開を使用すると、分岐を減らすことができますが、繰り返されるコードの長さによってバイナリファイルのサイズが増加します。これにより、複数の基本ブロックが 1 つにマージされる傾向があります。
地域: 時間的に近くにアクセスされるコードとデータは、参照の空間的局所性を高めるために、メモリ内で近くに配置する必要があります。
メモリ階層を活用する: メモリへのアクセスはメモリ階層の各レベルでますますコストがかかるため、最もよく使用される項目を最初にレジスタに配置し、次にキャッシュ、最後にメインメモリに配置してからディスクに配置します。
並列化: 命令、メモリ、またはスレッドレベルで複数の計算を並行して実行できるように、操作を並べ替えます。
より正確な情報の方がよい: コンパイラが持つ情報が正確であればあるほど、これらの最適化手法の一部またはすべてをより適切に活用できるようになります。
ランタイムメトリクスは役に立つ: テスト実行中に収集された情報は、プロファイルガイドによる最適化で使用できます。実行時に収集された情報は、理想的にはオーバーヘッドを最小限に抑えて、JITコンパイラーによって最適化を動的に改善するために使用されます。
強度低下: 複雑、困難、またはコストのかかる演算を、より単純な演算に置き換えます。たとえば、定数による除算をその逆数による乗算に置き換えたり、誘導変数分析を使用してループインデックスによる乗算を加算に置き換えたりします。

具体的なテクニック

ループの最適化

ループ最適化は、forループなどのループを構成する文に作用します。たとえば、ループ不変コードモーションなどです。多くのプログラムはループ内で多くの時間を費やすため、ループ最適化は大きな影響を与える可能性があります。^[3]^{: 596}

主にループを操作するために設計された最適化手法には次のものがあります。

誘導変数分析: 大まかに言えば、ループ内の変数がインデックス変数の単純な線形関数である場合（など）、j := 4*i + 1ループ変数が変更されるたびに適切に更新できます。これは強度の低下であり、インデックス変数の定義がデッドコードになる可能性もあります。^[3]^：596–598この情報は、境界チェックの除去や依存性の分析などにも役立ちます。

ループ分裂またはループ分配: ループ分割は、同じインデックス範囲でループを複数のループに分割し、各新しいループが元のループ本体の一部のみを使用するようにします。これにより、ループ内でアクセスされるデータとループ本体のコードの両方への参照の局所性が向上します。

ループ融合またはループ結合またはループラミングまたはループジャミング: ループのオーバーヘッドを削減しようとする別の手法。コンパイル時にその回数がわかっているかどうかに関係なく、2 つの隣接するループが同じ回数反復する場合、互いのデータを参照しない限り、それらのループ本体を組み合わせることができます。

ループ反転: この手法は、標準のwhileループを、if条件で囲まれたdo/while ( repeat/untilとも呼ばれる) ループに変更し、ループが実行される場合のジャンプの数を 2 つ減らします。これを行うと条件チェックが重複しますが (コードのサイズが増加します)、ジャンプは通常パイプラインストールを引き起こすため、より効率的です。さらに、初期条件がコンパイル時にわかっていて、副作用がないことがわかっている場合は、ifガードはスキップできます。

ループインターチェンジ: これらの最適化により、内部ループが外部ループと交換されます。ループ変数が配列にインデックス付けされる場合、このような変換により、配列のレイアウトに応じて参照の局所性が向上する可能性があります。

ループ不変コードの動き: ループ内で各反復中に量が計算され、その値が各反復で同じである場合、その量をループ外に持ち上げて、ループが始まる前にその値を一度だけ計算すると、効率が大幅に向上します。^[3]^{: 596}これは、配列のループによって生成されるアドレス計算式で特に重要です。すべてのコードがループ外に持ち上げても安全であるとは限らないため、正しく実装するには、この手法をループ反転とともに使用する必要があります。

ループネストの最適化: 行列乗算などの一部の一般的なアルゴリズムでは、キャッシュ動作が非常に悪く、メモリアクセスが過剰になります。ループネストの最適化では、小さなブロックで操作し、ループ交換を使用することで、キャッシュヒットの数が増加します。

ループ反転: ループ反転は、インデックス変数に値が割り当てられる順序を逆にします。これは、依存関係を排除して他の最適化を可能にするのに役立つ微妙な最適化です。さらに、一部のアーキテクチャでは、ループ反転はコードの小型化に貢献します。ループインデックスが減分されるときに、実行中のプログラムがループを終了するために満たす必要がある条件は、ゼロとの比較であるためです。これは、比較する数値を必要とする数値との比較とは異なり、多くの場合、特別なパラメーターなしの命令です。したがって、ループ反転を使用すると、パラメーターを格納するために必要なバイト数が節約されます。さらに、比較数がプラットフォームのワードサイズを超える場合、標準のループ順序では、比較を評価するために複数の命令を実行する必要がありますが、ループ反転ではそうではありません。

ループ展開: アンロールはループ本体を複数回複製し、ループ条件のテスト回数とジャンプ回数を減らします。テストとジャンプは命令パイプラインを損ない、パフォーマンスを低下させる可能性があります。「ジャンプ回数を減らす」最適化。ループを完全にアンロールすると、すべてのオーバーヘッドがなくなりますが、コンパイル時に反復回数を把握する必要があります。

ループ分割: ループ分割は、ループを複数のループに分割して、同じ本体を持ちながらインデックス範囲の連続する異なる部分を反復処理することで、ループを簡素化したり依存関係を排除したりします。便利な特殊なケースとして、ループピーリングがあります。これは、ループに入る前にその反復処理を個別に実行することで、問題のある最初の反復処理を含むループを簡素化できます。

ループの切り替え: アンスイッチングは、条件の各 if 句と else 句内でループ本体を複製することにより、条件をループ内からループ外に移動します。

ソフトウェアパイプライン: ループは、反復で実行される作業が複数の部分に分割され、複数の反復にわたって実行されるように再構成されます。タイトなループでは、この手法により、値の読み込みと使用の間の遅延が隠されます。

自動並列化: ループは、マルチコアマシンを含む共有メモリマルチプロセッサ (SMP) マシンで複数のプロセッサを同時に利用するために、マルチスレッドまたはベクトル化 (またはその両方) コードに変換されます。

先見性のある店舗最適化

先見的なストア最適化により、スレッドとロックのコンテキストで通常許可されるよりも早くストア操作を実行できます。プロセスでは、実行されるべき割り当てによってどの値が格納されるかを事前に知る方法が必要です。この緩和の目的は、コンパイラの最適化により、適切に同期されたプログラムのセマンティクスを保持する特定の種類のコードの再配置を実行できるようにすることです。^[8]

データフローの最適化

データフロー分析に基づくデータフロー最適化は、主に、データの特定のプロパティが制御フローグラフ内の制御エッジによってどのように伝播されるかに依存します。これには次のものが含まれます。

共通部分式の除去: 式において(a + b) - (a + b)/4、「共通部分式」は重複したを参照します(a + b)。この手法を実装するコンパイラはが(a + b)変化しないことを認識し、その値を一度だけ計算します。^[3]^{: 592–594}

定数の折り畳みと伝播: ^[9]定数からなる式（例：）を、実行時に計算するのではなく、コンパイル時に3 + 5最終値（）に置き換えること。ほとんどの現代言語で使用されている。8

誘導変数の認識と除去: 誘導変数分析については上記の説明を参照してください。

エイリアス分類とポインタ分析: ポインターが存在する場合、メモリ位置が割り当てられるときに任意の変数が変更される可能性があるため、最適化をまったく行うことは困難です。どのポインターがどの変数をエイリアスできるかを指定することにより、無関係なポインターを無視できます。

デッドストアの排除: 変数の有効期間が終了したため、または後続の割り当てによって最初の値が上書きされるため、その後読み取られない変数への割り当てを削除します。

SSAベースの最適化

これらの最適化は、プログラムを、すべての変数が 1 か所でのみ割り当てられる、静的単一割り当てと呼ばれる特殊な形式に変換した後に行うことを目的としています。一部の機能は SSA なしでも機能しますが、SSA を使用すると最も効果的です。他のセクションにリストされている多くの最適化も、レジスタ割り当てなどの特別な変更なしでメリットが得られます。

グローバル値の番号付け: GVN は、プログラムの値グラフを構築し、どの値が同等の式によって計算されるかを判断することで冗長性を排除します。GVN は、共通部分式の排除では識別できない冗長性を識別でき、その逆も同様です。

スパース条件付き定数伝播: 定数伝播、定数畳み込み、デッドコード除去を組み合わせ、別々に実行することで可能な範囲を改善します。^[10]^{[11]この最適化はプログラムをシンボリックに実行し、定数値の伝播と、これによって到達不能になる}制御フローグラフの部分の除去を同時に行います。

コードジェネレータの最適化

レジスタ割り当て: 最も頻繁に使用される変数は、最速のアクセスのためにプロセッサレジスタ内に保持する必要があります。どの変数をレジスタ内に配置するかを見つけるために、干渉グラフが作成されます。各変数は頂点であり、2 つの変数が同時に使用される場合 (交差するライブ範囲を持つ場合)、それらの変数間にはエッジがあります。このグラフは、レジスタと同じ数の色を使用して、たとえばChaitin アルゴリズムを使用して色付けされます。色付けが失敗すると、1 つの変数がメモリに「スピル」され、色付けが再試行されます。

命令の選択: ほとんどのアーキテクチャ、特にCISCアーキテクチャや多数のアドレッシングモードを備えたアーキテクチャでは、まったく異なる命令シーケンスを使用して、特定の操作を実行する複数の異なる方法が用意されています。命令セレクタの役割は、どの命令を使用して低レベルの中間表現のどの演算子を実装するかを全体的に適切に選択することです。たとえば、68000 ファミリや x86 アーキテクチャの多くのプロセッサでは、などのステートメントで複雑なアドレッシングモードを使用できるためlea 25(a1,d5*4), a0、1 つの命令で大量の演算をより少ないストレージで実行できます。

命令スケジューリング: 命令スケジューリングは、現代のパイプラインプロセッサにとって重要な最適化であり、依存関係のない命令をまとめてクラスタ化することで、パイプラインの停止やバブルを回避し、元のセマンティクスを慎重に維持します。

再物質化: 再マテリアライゼーションは、メモリから値をロードするのではなく、値を再計算してメモリへのアクセスを排除します。これは、レジスタ割り当てと連動して実行され、スピルを回避します。

コードファクタリング: 複数のコードシーケンスが同一であるか、同一になるようにパラメータ化または並べ替えることができる場合は、共有サブルーチンの呼び出しに置き換えることができます。これにより、サブルーチンのセットアップや末尾再帰のコードが共有されることがよくあります。^[12]

トランポリン: 多くの^{CPUには、低メモリにアクセスするための小さなサブルーチン呼び出し命令があり}ます。コンパイラは、コードの本体でこれらの小さな呼び出しを使用することでスペースを節約できます。低メモリ内のジャンプ命令は、任意のアドレスのルーチンにアクセスできます。これにより、コードファクタリングによるスペース節約が倍増します。^[12]

計算の順序変更: 整数線形計画法に基づいて、再構築コンパイラは計算を並べ替えることでデータの局所性を高め、より多くの並列性を実現します。スペース最適化コンパイラは、サブルーチンに分解できるシーケンスを長くするためにコードを並べ替える場合があります。

関数型言語の最適化

これらの多くは非関数型言語にも当てはまりますが、LispやMLなどの関数型言語に由来しているか、または関数型言語では特に重要です。

末尾呼び出し最適化: 関数呼び出しはスタック領域を消費し、パラメータの受け渡しや命令キャッシュのフラッシュに関連するオーバーヘッドが発生します。末尾再帰アルゴリズムは、末尾再帰除去または末尾呼び出し最適化と呼ばれるプロセスを通じて反復処理に変換できます。

森林破壊（データ構造の融合）: リストに一連の変換を適用するのが一般的な言語では、デフォレスト化によって中間データ構造の構築を削除しようとします。

部分的な評価: 実行時の動的入力に関係なく同じ出力を生成する計算は、コンパイル時に評価できます。

その他の最適化

境界チェックの除去: Javaなどの多くの言語では、すべての配列アクセスの境界チェックが強制されます。これは、科学コードなどの特定のアプリケーションでは重大なパフォーマンスのボトルネックとなります。境界チェックの排除により、コンパイラは、インデックスが有効な境界内に収まる必要があると判断できる多くの状況で、境界チェックを安全に削除できます。たとえば、単純なループ変数の場合などです。

分岐オフセット最適化（マシン依存）: ターゲットに到達する最短の分岐変位を選択します。

コードブロックの並べ替え: コードブロックの並べ替えでは、プログラム内の基本ブロックの順序を変更して、条件分岐を減らし、参照の局所性を向上させます。

デッドコードの除去: プログラムの動作に影響を与えない命令（デッドコードと呼ばれる、使用されていない定義など）を削除します。これにより、コードサイズが削減され、不要な計算が排除されます。

不変量の因数分解（ループ不変量）: 条件が満たされたときと満たされなかったときの両方で式が実行される場合、その式は条件文の外側に 1 回だけ記述できます。同様に、特定の種類の式 (たとえば、定数を変数に割り当てる) がループ内に出現する場合、その式はループ外に移動できます。何度も実行されても 1 回だけ実行されても、その効果は同じだからです。これは、完全な冗長性除去とも呼ばれます。類似していますが、より強力な最適化は、部分的な冗長性除去(PRE) です。

インライン展開またはマクロ展開: あるコードがプロシージャを呼び出す場合、制御をプロシージャに渡すのではなく、呼び出しコード内にプロシージャの本体を直接挿入することができます。これにより、プロシージャ呼び出しに関連するオーバーヘッドが節約され、さまざまなパラメータ固有の最適化の機会が提供されますが、スペースが犠牲になります。プロシージャがインラインで呼び出されるたびに、プロシージャ本体が複製されます。一般に、インライン化は、小さなプロシージャを多数呼び出すパフォーマンスクリティカルなコードで役立ちます。「ジャンプが少ない」最適化^{[文の断片]}。命令型プログラミング言語のステートメントも、このような最適化の例です。ステートメントは関数呼び出しで実装できますが、ほとんどの場合、コードインライン化で実装されます。

ジャンプスレッド: この最適化では、完全にまたは部分的に同じ条件を前提とする連続した条件付きジャンプがマージされます。; 例えば、if (c) { foo; } if (c) { bar; }if (c) { foo; bar; }; そして。if (c) { foo; } if (!c) { bar; }if (c) { foo; } else { bar; }

マクロ圧縮: 共通コードシーケンスを認識し、共通コードを含むサブプログラム (「コードマクロ」) を作成し、共通コードシーケンスの発生を対応するサブプログラムの呼び出しに置き換えるスペース最適化。^[5]これは、すべてのコードが存在する場合に、マシンコード最適化として最も効果的に実行されます。この手法は、マイクロコンピュータ上のMacro Spitbolの実装で使用される解釈バイトストリームのスペースを節約するために最初に使用されました。^[13]特定のコードセグメントに必要なスペースを最小化する最適なマクロセットを決定する問題はNP 完全であることが知られていますが、^[5]効率的なヒューリスティックにより、ほぼ最適な結果が得られます。^[14]

キャッシュ衝突の削減: （例えば、ページ内の配置を乱すなど）

スタック高さの低減: 式ツリーを再配置して、式の評価に必要なリソースを最小限に抑えます。^{[説明が必要]}

テストの並べ替え: 何かの条件となるテストが 2 つある場合、最初に簡単なテスト (たとえば、変数と何かの比較) を処理し、その後で複雑なテスト (たとえば、関数呼び出しを必要とするテスト) を処理することができます。この手法は遅延評価を補完しますが、テストが相互に依存していない場合にのみ使用できます。短絡セマンティクスはこれを困難にする可能性があります。

手続き間の最適化

プロシージャ間の最適化は、プロシージャとファイルの境界を越えて、プログラム全体に作用します。プロシージャ内の最適化と緊密に連携し、ローカル部分とグローバル部分の連携で実行されます。プロシージャ間の最適化の代表的なものとしては、プロシージャのインライン化、プロシージャ間のデッドコードの除去、プロシージャ間の定数の伝播、プロシージャの並べ替えなどがあります。通常どおり、コンパイラは実際の最適化の前にプロシージャ間の分析を実行する必要があります。プロシージャ間の分析には、エイリアス分析、配列アクセス分析、呼び出しグラフの構築などがあります。

手続き間最適化は、 SGI、Intel、Microsoft、Sun Microsystemsの最新の商用コンパイラでは一般的です。長い間、オープンソースのGCCは強力な手続き間分析と最適化が不足していると批判されていましたが、現在では改善されています。^[15]完全な分析と最適化のインフラストラクチャを備えた別のオープンソースコンパイラはOpen64です。

プロシージャ間分析には余分な時間とスペースが必要になるため、ほとんどのコンパイラはデフォルトではこれを実行しません。ユーザーはコンパイラオプションを明示的に使用して、プロシージャ間分析やその他のコストのかかる最適化を有効にするようにコンパイラに指示する必要があります。

実用的な考慮事項

コンパイラが実行できる最適化には、コンパイル時間がほとんどかからない単純で単純な最適化から、コンパイル時間がかなりかかる複雑で手の込んだ最適化まで、幅広い範囲があります。^[3]^{: 15}したがって、コンパイラは多くの場合、制御コマンドまたはプロシージャにオプションを提供し、コンパイラのユーザーがどの程度の最適化を要求するかを選択できるようにします。たとえば、IBM FORTRAN H コンパイラでは、ユーザーが最適化なし、レジスタレベルのみの最適化、または完全な最適化を指定できました。^[3]^{: 737} 2000 年代までには、 Clangなどのコンパイラでは、おなじみのスイッチから始めて、さまざまな最適化の選択に影響を与える可能性のある複数のコンパイラコマンドオプションを持つことが一般的でした-O2。^[16]

最適化を分離するアプローチとして、いわゆるポストパスオプティマイザ（商用版の一部は1970年代後半のメインフレームソフトウェアにまで遡る）の使用がある。^[17]これらのツールは、最適化コンパイラによる実行可能出力を受け取り、さらに最適化する。ポストパスオプティマイザは通常、アセンブリ言語またはマシンコードレベルで動作する（プログラムの中間表現を最適化するコンパイラとは対照的）。その一例が1980年代のポータブルCコンパイラ（PCC）で、生成されたアセンブリコードに対してポスト最適化を実行するオプションパスがあった。^[3]^{: 736}

もう一つの考慮すべき点は、最適化アルゴリズムが複雑であり、特に大規模で複雑なプログラミング言語をコンパイルするために使用される場合、生成されたコードにエラーを導入したり、コンパイル中に内部エラーを引き起こしたりするバグが含まれている可能性があることです。あらゆる種類のコンパイラエラーはユーザーを困惑させる可能性がありますが、この場合、最適化ロジックに問題があることが明確でない可能性があるため、特にそうです。^[18]内部エラーの場合、問題は「フェイルセーフ」プログラミング手法によって部分的に改善できます。この手法では、コンパイラの最適化ロジックが、失敗をトラップして警告メッセージを発行し、残りのコンパイルが正常に完了するようにコーディングされます。^[19]

歴史

1960 年代の初期のコンパイラは、単にコードを正しく、効率的にコンパイルすることに主眼を置いていたため、コンパイル時間が大きな懸念事項でした。注目すべき初期の最適化コンパイラの 1 つに、1960 年代後半の IBM FORTRAN H コンパイラがあります。^[3]^{: 737}初期の重要な最適化コンパイラのもう 1 つは、いくつかの高度な手法の先駆けとなったBLISS (1970) のコンパイラで、これはThe Design of an Optimizing Compiler (1975)で説明されています。 ^[3]^{: 740, 779} 1980 年代後半までには、最適化コンパイラが十分に効果的であったため、アセンブリ言語でのプログラミングは衰退しました。これは、RISC チップの開発や、スーパースカラープロセッサ、アウトオブオーダー実行、投機的実行などの高度なプロセッサ機能の開発とともに進化しました。これらは、人間が記述したアセンブリコードではなく、最適化コンパイラが対象とするように設計されていました。^[要出典]

静的コード解析のリスト

参照

参考文献

^ Godbolt, Matt (2019 年 11 月 12 日)。「C++ コンパイラの最適化」。ACM Queue。第 17 巻、第 5 号。
^ 「講義15：NP完全性、最適化、分離」（PDF）。IE 511：整数計画法、2021年春。
^ abcdefghijk Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986).コンパイラ：原理、テクニック、ツール。マサチューセッツ州レディング：Addison-Wesley。ISBN 0-201-10088-6。
^ ab Cooper, Keith D. ; Torczon, Linda (2003) [2002-01-01].コンパイラの設計. Morgan Kaufmann . pp. 404, 407. ISBN 978-1-55860-698-2。
^ abc Clinton F. Goss (2013年8月) [初版1986年6月]. マシンコードの最適化 - 実行可能オブジェクトコードの改善(PDF) (博士論文). Vol. コンピュータサイエンス学科技術レポート#246. ニューヨーク大学クーラント研究所. arXiv : 1308.4815 . Bibcode :2013arXiv1308.4815G. 2022年10月9日時点のオリジナルよりアーカイブ(PDF) . 2013年8月22日閲覧。
- Clinton F. Goss (2013) [1986]. マシンコードの最適化 - 実行可能オブジェクトコードの改善 (博士論文)。Courant Institute、ニューヨーク大学。
^ 「GCC – マシン依存オプション」。GNUプロジェクト。
^ 「RISC vs. CISC」. cs.stanford.edu . 2024年10月15日閲覧。
^ James Gosling、Bill Joy、Guy Steele。「17 スレッドとロック」。Java 言語仕様 (1.0 版)。17.8 予測可能なストアアクション。
^ Muchnick, Steven; Muchnick and Associates (1997 年 8 月 15 日)。Advanced Compiler Design Implementation。Morgan Kaufmann。pp. 329– 。ISBN 978-1-55860-320-2.定数の折り畳み。
^ Wegman, Mark N.; Zadeck, F. Kenneth (1991 年 4 月). 「条件分岐による定数伝播」(PDF) . ACM Transactions on Programming Languages and Systems . 13 (2): 181–210. doi :10.1145/103135.103136.
^ Click, Clifford; Cooper, Keith. (1995 年 3 月). 「分析の組み合わせ、最適化の組み合わせ」(PDF) . ACM Transactions on Programming Languages and Systems . 17 (2): 181–196. doi :10.1145/201059.201061.
^ ab Cx51 コンパイラマニュアル、バージョン 09.2001、p. 155、Keil Software Incorporated。
^ Dewar, Robert BK ; Golumbic, Martin Charles ; Goss, Clinton F. (2013 年 8 月) [1979 年 10 月]。MICRO SPITBOL 。コンピュータサイエンス部門技術レポート。第 11 巻。Courant Institute of Mathematical Sciences。arXiv : 1308.6096。Bibcode :2013arXiv1308.6096D。
^ Golumbic, Martin Charles ; Dewar, Robert BK ; Goss, Clinton F. (1980)。「MICRO SPITBOL のマクロ置換 - 組み合わせ分析」。第 11 回 Southeastern Conference on Combinatorics, Graph Theory and Computing の議事録、Congressus Numerantium、Utilitas Math.、ウィニペグ、カナダ。第 11 回 Southeastern Conference on Combinatorics, Graph Theory and Computing。第 29 巻。485 ～ 495 ページ。
^ Glazunov, NM (2012年11月25日). 「科学研究の基礎」. arXiv : 1212.1651 [cs.OH].
^ Guelton, Serge (2019 年 8 月 5 日)。「Clang でコンパイルプロセスをカスタマイズする: 最適化オプション」。Red Hat。
^ Evans, Michael (1982 年 12 月). 「Cobol 環境向けのソフトウェアエンジニアリング」. Communications of the ACM . 25 (12): 874–882. doi :10.1145/358728.358732 . 2013 年 8 月 10 日閲覧。
^ Sun , Chengnian; et al. (2016 年 7 月 18 ～ 20 日)。「GCC と LLVM のコンパイラバグの理解に向けて」。第 25 回ソフトウェアテストおよび分析に関する国際シンポジウムの議事録。Issta 2016。pp. 294 ～ 305。doi : 10.1145/2931037.2931074。ISBN 9781450343909. S2CID 8339241。
^ Schilling, Jonathan L. (1993 年 8 月). 「コンパイラ最適化におけるフェイルセーフプログラミング」. ACM SIGPLAN Notices . 28 (8): 39–42. doi :10.1145/163114.163118. S2CID 2224606.

外部リンク

Agner Fogによる最適化マニュアル – x86 プロセッサアーキテクチャと低レベルコードの最適化に関するドキュメント

[1] Godbolt, Matt (2019 年 11 月 12 日)。「C++ コンパイラの最適化」。ACM Queue。第 17 巻、第 5 号。

[2] 「講義15：NP完全性、最適化、分離」（PDF）。IE 511：整数計画法、2021年春。

[aho-sethi-ullman-3] Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986).コンパイラ：原理、テクニック、ツール。マサチューセッツ州レディング：Addison-Wesley。ISBN 0-201-10088-6。

[Cooper_2003-4] Cooper, Keith D. ; Torczon, Linda (2003) [2002-01-01].コンパイラの設計. Morgan Kaufmann . pp. 404, 407. ISBN 978-1-55860-698-2。

[MCO-5] Clinton F. Goss (2013年8月) [初版1986年6月]. マシンコードの最適化 - 実行可能オブジェクトコードの改善(PDF) (博士論文). Vol. コンピュータサイエンス学科技術レポート#246. ニューヨーク大学クーラント研究所. arXiv : 1308.4815 . Bibcode :2013arXiv1308.4815G. 2022年10月9日時点のオリジナルよりアーカイブ(PDF) . 2013年8月22日閲覧。
Clinton F. Goss (2013) [1986]. マシンコードの最適化 - 実行可能オブジェクトコードの改善 (博士論文)。Courant Institute、ニューヨーク大学。

[6] Clinton F. Goss (2013) [1986]. マシンコードの最適化 - 実行可能オブジェクトコードの改善 (博士論文)。Courant Institute、ニューヨーク大学。

[6] 「GCC – マシン依存オプション」。GNUプロジェクト。

[7] 「RISC vs. CISC」. cs.stanford.edu . 2024年10月15日閲覧。

[8] James Gosling、Bill Joy、Guy Steele。「17 スレッドとロック」。Java 言語仕様 (1.0 版)。17.8 予測可能なストアアクション。

[MuchnickAssociates1997-9] Muchnick, Steven; Muchnick and Associates (1997 年 8 月 15 日)。Advanced Compiler Design Implementation。Morgan Kaufmann。pp. 329– 。ISBN 978-1-55860-320-2.定数の折り畳み。

[10] Wegman, Mark N.; Zadeck, F. Kenneth (1991 年 4 月). 「条件分岐による定数伝播」(PDF) . ACM Transactions on Programming Languages and Systems . 13 (2): 181–210. doi :10.1145/103135.103136.

[11] Click, Clifford; Cooper, Keith. (1995 年 3 月). 「分析の組み合わせ、最適化の組み合わせ」(PDF) . ACM Transactions on Programming Languages and Systems . 17 (2): 181–196. doi :10.1145/201059.201061.

[keil-12] Cx51 コンパイラマニュアル、バージョン 09.2001、p. 155、Keil Software Incorporated。

[MicroSpitbol-13] Dewar, Robert BK ; Golumbic, Martin Charles ; Goss, Clinton F. (2013 年 8 月) [1979 年 10 月]。MICRO SPITBOL 。コンピュータサイエンス部門技術レポート。第 11 巻。Courant Institute of Mathematical Sciences。arXiv : 1308.6096。Bibcode :2013arXiv1308.6096D。

[14] Golumbic, Martin Charles ; Dewar, Robert BK ; Goss, Clinton F. (1980)。「MICRO SPITBOL のマクロ置換 - 組み合わせ分析」。第 11 回 Southeastern Conference on Combinatorics, Graph Theory and Computing の議事録、Congressus Numerantium、Utilitas Math.、ウィニペグ、カナダ。第 11 回 Southeastern Conference on Combinatorics, Graph Theory and Computing。第 29 巻。485 ～ 495 ページ。

[15] Glazunov, NM (2012年11月25日). 「科学研究の基礎」. arXiv : 1212.1651 [cs.OH].

[16] Guelton, Serge (2019 年 8 月 5 日)。「Clang でコンパイルプロセスをカスタマイズする: 最適化オプション」。Red Hat。

[17] Evans, Michael (1982 年 12 月). 「Cobol 環境向けのソフトウェアエンジニアリング」. Communications of the ACM . 25 (12): 874–882. doi :10.1145/358728.358732 . 2013 年 8 月 10 日閲覧。

[18] ^ Sun , Chengnian; et al. (2016 年 7 月 18 ～ 20 日)。「GCC と LLVM のコンパイラバグの理解に向けて」。第 25 回ソフトウェアテストおよび分析に関する国際シンポジウムの議事録。Issta 2016。pp. 294 ～ 305。doi : 10.1145/2931037.2931074。ISBN 9781450343909. S2CID 8339241。

[19] Schilling, Jonathan L. (1993 年 8 月). 「コンパイラ最適化におけるフェイルセーフプログラミング」. ACM SIGPLAN Notices . 28 (8): 39–42. doi :10.1145/163114.163118. S2CID 2224606.