手続き間の最適化

プロシージャ間最適化( IPO ) は、頻繁に使用される短いまたは中程度の長さの関数を多数含むプログラムのパフォーマンスを向上させるためにコンピュータ プログラミングで使用されるコンパイラテクニックの集合です。IPO は、単一の関数またはコード ブロックではなく、プログラム全体を分析する点で他のコンパイラ最適化とは異なります。

IPO は、重複した計算やメモリの非効率的な使用を削減または排除し、ループなどの反復シーケンスを簡素化することを目指します。ループ内で別のルーチンの呼び出しが発生した場合、IPO 分析により、そのルーチンをインライン化することが最適であると判断されることがあります。さらに、IPO は、メモリ レイアウトと局所性を向上させるためにルーチンの順序を変更することがあります。

IPO には、プログラム全体のレベルで適用される一般的なコンパイラ最適化 (実行されないコードを削除するデッド コード除去(DCE) など) も含まれる場合があります。また、IPO は定数のより有効な使用を確実にしようとします。最新のコンパイラは、コンパイル時に IPO をオプションとして提供しています。実際の IPO プロセスは、人間が判読できるソース コードから完成した実行可能なバイナリ プログラムの作成までの間のどの段階でも発生する可能性があります。

ファイルごとにコンパイルする言語の場合、翻訳単位(モジュール ファイル) 全体にわたって効果的な IPO を行うには、プログラムの「エントリ ポイント」を認識して、プログラム全体の最適化( WPO ) を実行できるようにする必要があります。多くの場合、プログラム全体がリンカーから見えるため、これはリンク時の最適化( LTO ) パスとして実装されます。

速度最適化の目的は、プログラムをできるだけ速く実行することです。問題は、コンパイラがプログラムを正しく分析して、それが何を行うかを判断することは不可能であり、プログラマが何を意図したかを判断することは不可能であるということです。対照的に、人間のプログラマは、目的を持ってプログラムを作成し、その過程で多くの思考を費やすことなく、目的を達成するプログラムを作成しようとします。

読みやすさなどのさまざまな理由から、プログラムは、いくつかの一般的なケースを処理するいくつかの手順に分割されることがよくあります。ただし、各手順の汎用性により、特定の用途で無駄な労力が発生する可能性があります。手順間の最適化は、この無駄を削減する試みです。

F(x) を評価する手続きがあり、 F が純粋関数であるとします。コードが F(6) の結果を要求し、その後で再び F(6) を要求します。この 2 回目の評価はほぼ間違いなく不要です。代わりに結果を保存して後で参照することもできます。この単純な最適化は、F(x) の実装が不純になった瞬間に失敗に終わります。つまり、その実行には、呼び出し間で変更された明示的な引数 6 以外のパラメータへの参照が伴います。または、ログに何らかのメッセージを出力する、評価回数をカウントする、消費されたCPU時間を累計する、関連するパラメータの後続の呼び出しを容易にするための内部テーブルの準備などの副作用があります。2 回目の評価を行わないことでこれらの副作用がなくなることは許容できる場合もあれば、そうでない場合もあります。

より一般的には、最適化以外に、プロシージャを使用する 2 番目の理由は、プロシージャが実行されるたびに同じ結果、またはほぼ同じ結果を生成するコードの重複を避けることです。したがって、最適化の一般的なアプローチは、これを逆にすることです。つまり、特定のプロシージャの一部またはすべての呼び出しを、パラメータが適切に置き換えられたそれぞれのコードに置き換えます。その後、コンパイラは結果を最適化しようとします。

プログラム全体の最適化( WPO ) は、プログラム内のすべてのモジュールに関する情報を使用して、プログラムをコンパイラで最適化することです。通常、最適化はモジュールごとに、つまり「コンパイル単位」ごとに実行されます。しかし、このアプローチは、記述とテストが容易で、コンパイル自体のリソースの要求も少ないものの、積極的なインライン化などの多くの最適化の安全性について確信が持てないため、生成されたオブジェクト コードのセマンティクスを変更せずに実際に効率が向上する場合でも、最適化を実行することはできません。

リンク時最適化( LTO ) は、コンパイラがプログラムのリンク時に実行するプログラム最適化の一種です。リンク時最適化は、すべてのファイルを一度にコンパイルするのではなく ( Javaのジャストインタイムコンパイル (JIT)など) 、ファイルごとにプログラムをコンパイルし、それらのファイルをリンクするプログラミング言語 ( CやFortranなど) に関係します。

すべてのファイルが個別にオブジェクト ファイルにコンパイルされると、従来、コンパイラはオブジェクト ファイルを 1 つのファイル (実行可能ファイル) にリンク (マージ) します。ただし、 GNU コンパイラ コレクション(GCC) とLLVMによって実装されている LTO では、コンパイラは中間表現(IR)、つまりそれぞれGIMPLEバイトコードまたは LLVM ビットコードをダンプできるため、単一の実行可能ファイルを構成するすべての異なるコンパイル ユニットを、リンクが最終的に行われるときに 1 つのモジュールとして最適化できます。これにより、プロシージャ間の最適化の範囲がプログラム全体 (または、リンク時に表示されるすべてのもの) に拡張されます。リンク時の最適化により、コンパイラはさまざまな形式のプロシージャ間の最適化をプログラム全体に適用できるため、より深い分析、より多くの最適化、そして最終的にはプログラムのパフォーマンスが向上します。

実際には、LTO は必ずしもプログラム全体を最適化するわけではありません。ライブラリ関数、特に動的にリンクされた共有オブジェクトは、過度の重複を避け、更新を可能にするために意図的に除外されます。静的リンクは当然 LTO の概念に役立ちますが、マシンコードのみのオブジェクト ファイルではなく、IR オブジェクトを含むライブラリ アーカイブでのみ機能します。^[1]パフォーマンス上の懸念から、ユニット全体が直接使用されることさえありません。プログラムは、GCC の WHOPR などの分割統治スタイルの LTO に分割できます。^[2]そしてもちろん、ビルドされるプログラム自体がライブラリである場合、最適化は外部で利用可能な (エクスポートされた) シンボルをすべて保持し、DCE の一部としてそれらを削除しようとしすぎません。^[1]

LTO を使わなくても、はるかに限定された形式の WPO は可能です-fwhole-program。これは GCC のスイッチに例えられます。このモードでは、コンパイルされるモジュールにプログラム全体のエントリ ポイントが含まれていると GCC が想定するため、モジュール内の他のすべての関数は外部で使用されず、安全に最適化できます。これは単一のモジュールにのみ適用されるため、プログラム全体を網羅することはできません。これは、1 つの大きなモジュールという意味で LTO と組み合わせることができます。これは、リンカーが外部で使用されているエントリ ポイントまたはシンボルについて GCC に通信していない場合に役立ちます。^[1]

プログラム例;整数b ; {プロシージャ Silly に対して「グローバル」な変数。}プロシージャSilly ( a , x ) if x < 0 then a := x + b else a :=- 6 ; End Silly ; {パラメーターではなく b への参照により、Silly は一般に「不純」になります。}整数a , x ; {これらの変数は、パラメーターの場合にのみ Silly から参照できます。} x := 7 ; b := 5 ; Silly ( a , x ) ; write ( x ) ; Silly ( x , a ) ; write ( x ) ; Silly ( b , b ) ; write ( b ) ; End example ; 
                  
    
               
                  
                
    
    
    
    
 

Sillyへのパラメータが値渡しされる場合、プロシージャのアクションは元の変数には影響しません。また、Silly は環境に対して何も行わないため (ファイルからの読み取り、ファイルへの書き込み、bなどのグローバル変数の変更など)、そのコードとすべての呼び出しは最適化によって完全に削除され、 aの値は未定義のままになり (これは重要ではありません)、ステートメントだけが残り、単に定数値が出力されることになります。 write

代わりにパラメータが参照渡しされる場合、 Silly内でのパラメータに対するアクションは、実際に元のパラメータに影響します。これは通常、パラメータのマシン アドレスをプロシージャに渡すことによって行われ、プロシージャの調整は元のストレージ領域に対して行われます。したがって、参照渡しの場合、プロシージャSilly は効果があります。その呼び出しが、アドレスによって識別されるパラメータを使用して、その場で展開されると仮定します。コードは次のようになります。

x := 7 ; b := 5 ; if x < 0 then a := x + b else a :=- 6 ; write ( x ) ; {a が変更されます。} if a < 0 then x := a + b else x :=- 6 ; write ( x ) ; {パラメーターが入れ替わっているためです。} if b < 0 then b := b + b else b :=- 6 ; write ( b ) ; {Silly の変数 b の 2 つのバージョンと、グローバルな使用法。} 
             
             
             

すると、この比較的小さな例では、コンパイラはロジックに沿って定数をたどり（現状のまま）、if ステートメントの述語が定数であることなどを発見できます。

x := 7 ; b := 5 ; a :=- 6 ; write ( 7 ) ; {b は参照されていないため、この使用法は「純粋」のままです。} x :=- 1 ; write ( - 1 ) ; {b は参照されています...} b :=- 6 ; write ( - 6 ) ; {b はパラメータの表現によって変更されます。} 
             
            
            

そして、 a、b、xへの代入は外部に何も伝えないので、出力文にも現れず、後続の計算の入力にもならない（その結果は出力につながるが、そうでなければそれらは不要である）ので、このコードにも意味がなく、結果は次のようになる。

書く( 7 ) ;
書く( - 1 ) ;
書く( - 6 ) ;

「参照渡し」のように見えるパラメータを渡すための別の方法として、コピーイン、コピーアウトがあります。この方法では、プロシージャはパラメータのローカル コピーに対して動作し、プロシージャの終了時にその値が元のパラメータにコピーされます。プロシージャが同じパラメータにアクセスするが、呼び出し方法が異なる場合 ( Silly(a,a)やSilly(a,b)など)、矛盾が生じる可能性があります。したがって、パラメータがコピーイン、コピーアウトによって左から右の順序で渡された場合、Silly(b,b) は次のように展開されます。

p1 := b ; p2 := b ; {コピーイン。ローカル変数 p1 と p2 は等しくなります。} if p2 < 0 then p1 := p2 + b else p1 :=- 6 ; {したがって、p1 は p2 と等しくなくなる可能性があります。} b := p1 ; b := p2 ; {コピーアウト。左から右の順序で、p1 の値が上書きされます。}                                
               
                                

この場合、変更されたp1の値をbにコピーしても意味がありません。なぜなら、 p2の値によってすぐに上書きされてしまうからです。 p2 の値は、手順内で元のbの値から変更されていないため、3番目の文は次のようになります。

（5 ）を書きます; {-6ではない}          

このような動作の違いは、困惑を引き起こす可能性があり、パラメータがコピーされる順序に関する疑問によってさらに悪化します。つまり、開始時だけでなく終了時も左から右にコピーされるのでしょうか。これらの詳細は、おそらくコンパイラのマニュアルで詳しく説明されていません。説明されていたとしても、当面のタスクには関係ないとして無視され、問題が発生する頃には忘れ去られている可能性があります。一時的な値がスタック ストレージ スキームを介して提供される場合 (おそらくそうでしょう)、コピーバック プロセスはコピーインと逆の順序になる可能性があり、この例では、代わりにp1 がbに返される最後の値になることを意味します。

プロシージャをインラインで展開するプロセスは、テキスト置換の変形 (マクロ展開など) として考えるべきではありません。これは、パラメータが変更され、特定の呼び出しでパラメータとして定数が使用されると、構文エラーが発生する可能性があるためです。パラメータとして提供される定数の値が変更されないようにすることが重要であるため (定数は変数と同様にメモリ内に保持できます)、その定数のその後の使用 (メモリ位置への参照を介して行われる) がうまくいかないようにするため、一般的な手法として、定数の値を一時変数にコピーするコードをコンパイラで生成し、そのアドレスがプロシージャに渡されるようにします。その値が変更されても、定数の場所にコピーされることはありません。

言い換えれば、注意深く書かれたテスト プログラムは、パラメータが値で渡されるか参照で渡されるか、また使用される場合はどのようなコピーインおよびコピーアウト スキームであるかを報告できます。ただし、バリエーションは無限です。単純なパラメータはコピーで渡されるかもしれませんが、配列などの大きな集合体は参照で渡されるかもしれません。ゼロなどの単純な定数は特別なマシン コード (Clear や LoadZ など) によって生成されるかもしれませんが、より複雑な定数は読み取り専用としてタグ付けされたメモリに格納され、変更しようとするとすぐにプログラムが終了するなどです。

この例は非常に単純ですが、複雑さはすでに明らかです。むしろ、多くのプロシージャが、コンパイラの最適化で何らかの利点を見つけられる可能性のあるさまざまな推定可能またはプログラマ宣言されたプロパティを持つケースになるでしょう。プロシージャへのパラメータは、読み取り専用、書き込み可能、​​読み取りと書き込みの両方、または完全に無視される可能性があり、一時変数による保護を必要としない定数などの機会が生じますが、特定の呼び出しで何が起こるかは、複雑な考慮事項の網に依存する可能性があります。他のプロシージャ、特に関数のようなプロシージャには、特定の呼び出しで一部の作業を回避できる特定の動作があります。たとえば、ガンマ関数は、整数パラメータで呼び出されると、整数の階乗を含む計算に変換できます。

一部のコンピュータ言語では、パラメータの使用に関するアサーションが有効 (または必須) になっており、さらに変数の値が何らかの集合 (たとえば 6 < x ≤ 28) に制限されていると宣言する機会も提供されている可能性があります。これにより、最適化プロセスをさらに進めるための材料がさらに提供され、ソース コードの一貫性をチェックして誤りを検出することもできます。しかし、これだけでは十分ではありません。一部の変数には単純な制約しか与えられず、他の変数には複雑な仕様が必要です。変数Pが素数であること、素数である場合、値 1 が含まれるかどうかをどのように指定すればよいでしょうか。複雑な問題はすぐに発生します。M が月番号である場合、月の日 D の有効な範囲はどこでしょうか。すべての違反は即時終了する価値があるでしょうか。たとえこれらすべてを処理できたとしても、どのようなメリットがあるでしょうか。また、コストはいくらでしょうか。完全な仕様は、プログラムの機能を別の形式で再記述することになり、コンパイラが処理に費やす時間は別としても、バグが発生する可能性が高くなります。代わりに、実行時の範囲チェックが提供される単純な仕様のみが許可されます。

プログラムが入力を読み取らない場合 (例のように)、コンパイラの分析が続行され、結果が一連の print ステートメント、またはそのような値を便宜的に生成するいくつかのループのみになることが考えられます。その場合、素数を生成するプログラムを認識し、そのための最もよく知られている方法に変換するか、代わりにライブラリへの参照を提示するでしょうか。あり得ません。一般に、これを妨げる任意の複雑な考慮事項 (Entscheidungsproblem )が発生し、限定的な改善のみでコードを実行する以外に選択肢はありません。

ALGOLのような手続き型言語では、手続き間分析と最適化は1970年代初頭に商業的に実施されたようです。IBMのPL/I最適化コンパイラは、手続き呼び出しと例外（PL/I用語では「条件付き」）の両方の副作用を理解するために手続き間分析を実行しました^{[3] 。また、} Fran Allenの論文でも説明されています。^{[4] [5]} APLプログラミング言語のコンパイル作業は必然的に手続き間分析でした。^{[6] [7]}

インタープロシージャ分析と最適化の技術は、1980 年代と 1990 年代に学術研究の対象となりました。これらの技術は、1990 年代初頭にConvex Computer Corporation (Convex C4 の「アプリケーション コンパイラ」) と Ardent ( Ardent Titanのコンパイラ) の両社のコンパイラによって商用コンパイラの世界に再登場しました。これらのコンパイラは、この技術が商用コンパイラで受け入れられるほど十分に高速化できることを実証しました。その後、インタープロシージャ技術は、多くの商用および非商用システムに登場しました。

GNUコンパイラコレクションは、すべての最適化レベルで関数のインライン化を行います。 では、これは-O1一度だけ呼び出される関数にのみ適用され( -finline-functions-once)、 では-O2この制約は緩和されます( -finline-functions)。デフォルトでは、これは単一ファイルのみの動作ですが、リンク時の最適化により-fltoプログラム全体になります。^[1] Clangのコマンドラインインターフェースは、オプションがない点を除けば、GCCのものと似ています-fwhole-program。^[8]

LTO によって生成されるオブジェクト ファイルには、リンク時に解釈されるコンパイラ固有の中間表現(IR) が含まれています。これが静的ライブラリで適切に機能するように、新しいGNU リンカーには「リンカー プラグイン」インターフェイスがあり、必要に応じてコンパイラがオブジェクト ファイルをマシン コード形式に変換できます。このプラグインは、LTO プロセス全般の駆動にも役立ちます。代わりに、マシン コードと IR の両方を含む「ファット LTO」オブジェクトを生成することもできますが、これにはより多くのスペースが必要です。^[1]

GCCとLLVM（clang）はどちらもさまざまなプログラミング言語からIRを生成できるため、リンク時のIPOは言語の境界を越えても発生する可能性があります。これはCとC++で最もよく見られますが^{[9] 、LLVMは}Rustやその他のLLVMベースのコンパイラでも可能になります。 ^[10]

GCCとClangは、最適化レベル2でデフォルトでIPOを実行します。しかし、LTOが無効になっている場合、IPOはオブジェクトファイル内でのみ実行でき、非静的関数は削除できないため、最適化の程度は制限されます。後者の問題には、LTO以外の解決策があります。-fwhole-programスイッチを使用して、 のみがmain()非静的、つまり外部から見えると想定することができます。^[11]

もう1つの非LTO技術は「関数セクション」（-ffunction-sectionsGCCおよびClang）です。各関数をオブジェクトファイル内の独自のセクションに配置することで、リンカーは参照されていないセクションを削除することでIRなしでデッドコード削除を実行できます（リンカーオプションを使用--gc-sections）。^[12]同様のオプションが変数にも使用できますが、生成されるコードの品質が大幅に低下します。

Intel C/C++コンパイラはプログラム全体のIPOを許可しています。単一ファイルに対して手続き間最適化を有効にするフラグは であり-ip、プログラム内のすべてのファイルにわたって手続き間最適化を有効にするフラグは です-ipo。^{[13] [14]}

Visual Studioに統合されたMSVCコンパイラは、プログラム全体の手続き間最適化もサポートしています。^[15]

プログラム全体の手続き間最適化を可能にするコンパイラに依存しないインターフェースは、CMakeINTERPROCEDURAL_OPTIMIZATIONのプロパティを介して提供されます。^[16]

• プロファイルガイド最適化(PGO)
• 単一コンパイル単位

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