(57)【特許請求の範囲】
【請求項１】
プロシージャ間最適化の方法であって、
プロセッサが、複数のソースコードモジュールに含まれるソースコードモジュールごとに中間表現ファイルを生成するステップと、
前記プロセッサが、前記ソースコードモジュールごとに関数インデックスと関数サマリーデータとを生成するステップとを含み、
各々の関数インデックスは、前記中間表現ファイルにおいて関数のＩＤを関数ボディのオフセットにマッピングした関数のシンボルテーブルを含み、
前記方法は、さらに、
前記プロセッサが、対応する前記ソースコードモジュールのために生成された前記関数インデックスおよび前記関数サマリーデータを前記中間表現ファイルの異なる部分に格納するステップと、
前記プロセッサが、前記複数のソースコードモジュールについて、生成された前記中間表現ファイルに対応するシン・アーカイブを生成するステップとを含み、
前記生成されたシン・アーカイブは、前記生成された中間表現ファイルのコピーを含んでおらず、複合関数マップと、前記生成された中間表現ファイルへのリファレンスとを含み、
前記方法は、さらに、
前記プロセッサが、対応する前記シン・アーカイブを用いて、前記複数のソースコードモジュールに対してクロス・モジュール最適化を行うステップを含む、方法。
【請求項２】
前記クロス・モジュール最適化は、モジュール粒度で並列である、請求項１に記載の方法。
【請求項３】
前記クロス・モジュール最適化を行うステップは、関数の高速インポートを行うために前記複合関数マップを利用することを含む、請求項１または２に記載の方法。
【請求項４】
前記クロス・モジュール最適化を行うステップは、一つ以上のその他のモジュールからのデバッグ情報の要求駆動型インポートを利用することを含む、請求項１〜３のいずれか１項に記載の方法。
【請求項５】
プロシージャ間最適化のシステムであって、
少なくとも一つのプロセッサと、
前記少なくとも一つのプロセッサに接続され、命令を格納した非一時的なコンピュータ読取可能媒体とを備え、前記命令は、前記少なくとも一つのプロセッサによって実行されると、前記少なくとも一つのプロセッサに、
複数のソースコードモジュールに含まれるソースコードモジュールごとに中間表現ファイルを生成させ、
前記ソースコードモジュールごとに関数インデックスと関数サマリーデータとを生成させ、
各々の関数インデックスは、前記中間表現ファイルにおいて関数のＩＤを関数ボディのオフセットにマッピングした関数のシンボルテーブルを含み、
前記命令は、前記少なくとも一つのプロセッサに、さらに、
対応する前記ソースコードモジュールのために生成された前記関数インデックスおよび前記関数サマリーデータを前記中間表現ファイルの異なる部分に格納させ、
前記複数のソースコードモジュールについて、複合関数マップを有する、生成された前記中間表現ファイルに対応するシン・アーカイブを生成させ、
前記生成されたシン・アーカイブは、前記生成された中間表現ファイルのコピーを含んでおらず、複合関数マップと、前記生成された中間表現ファイルへのリファレンスとを含み、
前記命令は、前記少なくとも一つのプロセッサに、さらに、
対応する前記シン・アーカイブを用いて、前記複数のソースコードモジュールに対してクロス・モジュール最適化を行わせる、システム。
【請求項６】
前記クロス・モジュール最適化は、モジュール粒度で並列である、請求項５に記載のシステム。
【請求項７】
前記システムは、さらに、
前記少なくとも一つのプロセッサに、関数の高速インポートを行うために前記複合関数マップを利用させる、請求項５または６に記載のシステム。
【請求項８】
前記システムは、さらに、
前記少なくとも一つのプロセッサに、一つ以上のその他のモジュールからのデバッグ情報の要求駆動型インポートを利用させる、請求項５〜７のいずれか１項に記載のシステム。
【請求項９】
コンピュータによって実行可能な命令を含むプログラムであって、前記命令は、一つ以上のプロセッサによって実行されると、前記一つ以上のプロセッサに、
複数のソースコードモジュールに含まれるソースコードモジュールごとに中間表現ファイルを生成することと、
前記ソースコードモジュールごとに関数インデックスと関数サマリーデータとを生成することとを含む動作を行わせ、
各々の関数インデックスは、前記中間表現ファイルにおいて関数のＩＤを関数ボディのオフセットにマッピングした関数のシンボルテーブルを含み、
前記命令は、前記一つ以上のプロセッサに、さらに、
対応する前記ソースコードモジュールのために生成された前記関数インデックスおよび前記関数サマリーデータを前記中間表現ファイルの異なる部分に格納することと、
前記複数のソースコードモジュールについて、複合関数マップを有する、生成された前記中間表現ファイルに対応するシン・アーカイブを生成することとを含む動作を行わせ、
前記生成されたシン・アーカイブは、前記生成された中間表現ファイルのコピーを含んでおらず、複合関数マップと、前記生成された中間表現ファイルへのリファレンスとを含み、
前記命令は、前記一つ以上のプロセッサに、さらに、
対応する前記シン・アーカイブを用いて、前記複数のソースコードモジュールに対してクロス・モジュール最適化を行うこと、とを含む動作を行わせる、プログラム。
【請求項１０】
前記クロス・モジュール最適化は、モジュール粒度で並列である、請求項９に記載のプログラム。
【請求項１１】
前記コンピュータによって実行可能な命令は、前記一つ以上のプロセッサによって実行されると、前記一つ以上のプロセッサに、
関数の高速インポートを行うために前記複合関数マップを利用することを含むさらなる動作を行わせる、請求項９または１０に記載のプログラム。
【請求項１２】
前記コンピュータによって実行可能な命令は、前記一つ以上のプロセッサによって実行されると、前記一つ以上のプロセッサに、
一つ以上のその他のモジュールからのデバッグ情報の要求駆動型インポートを利用することを含むさらなる動作を行わせる、請求項９〜１１のいずれか１項に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、２０１５年２月２日に出願された米国仮出願第６２／１１０，７３８号の利益を主張するものであり、そのすべての記載内容を、引用により本明細書に援用する。
【背景技術】
【０００２】
背景
クロス・モジュール最適化（Ｃｒｏｓｓ  Ｍｏｄｕｌｅ  Ｏｐｔｉｍｉｚａｔｉｏｎ：ＣＭＯ）（プロシージャ間最適化（Ｉｎｔｅｒｐｒｏｃｅｄｕｒａｌ  Ｏｐｔｉｍｉｚａｔｉｏｎ：ＩＰＯ）の意味によく含まれる）は、コンパイラがユーザプログラムを最適化できるようにする最も効果的な方法のうちの一つである。慣例に従い、ＣＭＯは、リンク時最適化（Ｌｉｎｋ  Ｔｉｍｅ  Ｏｐｔｉｍｉｚａｔｉｏｎ：ＬＴＯ）と呼ばれる技術を使って実装されている。ＬＴＯは、（名称が示すとおり）リンク時にクロス・モジュール最適化および全プログラム解析をできるようにするコンパイルモデルである。しかしながら、ＬＴＯにはいくつかの制約があるため、極めて大きいアプリケーションと合わせて使うのには適さない。このような制約は、たとえば、以下を含む。（１）ＬＴＯは、リンクステップを実行するために膨大なメモリ量を必要とする。（２）リンクステップは逐次的（ｓｅｒｉａｌ）であり、コンパイル全体の速度を大幅に落としてしまう。（３）ＬＴＯは、大きな分散ビルドシステムとの統合が容易にできない。
【０００３】
ＣＭＯを実装するための別の既存の技術は、軽量ＩＰＯ（ＬｉｇｈｔｗｅｉｇｈｔＩＰＯ：ＬＩＰＯ）と呼ばれ、これは、ＬＴＯよりはるかにスケーラブルである。しかしながら、ＬＩＰＯは、それ自体の一連の制約があるため、ＬＩＰＯの性能をこれ以上向上させられる可能性という点でその上限に達してしまっている。ＬＩＰＯの問題点のいくつかの例を挙げる。（１）ＬＩＰＯは、プロファイルのフィードバックを必要とし、デフォルトで有効にできない。（２）ＬＩＰＯは、ビルドシステムにとって非常にじゃまである（たとえば、デプロイするために複雑なビルドシステムサポートを必要とする）。（３）ＬＩＰＯは、ＣＭＯの可能性を大幅に制限してしまう粗粒度インポート法を利用している。
【発明の概要】
【課題を解決するための手段】
【０００４】
概要
本概要欄は、本開示のいくつかの態様の基本的理解を示すために、概念の抜粋を簡略化した形で紹介する。本概要欄は、本開示の包括的な大要ではなく、本開示の主要または重要な要素の特定、本開示の範囲の描写を目的としない。本概要欄は、以下に示す詳細な説明欄への導入部として本開示の概要のいくつかを表すものにすぎない。
【０００５】
本開示は、全体的に、ソースコードコンパイルの方法およびシステムに関する。より具体的には、本開示の態様は、ＩＰＯを実装するための新しいアーキテクチャに関する。
【０００６】
詳細は本明細書に後述するが、本開示のＩＰＯアーキテクチャは、極めて大きいプログラムに対して拡張できるように設計されており、処理できるソースモジュールの数という点においての制限がほとんどなく、きわめて速く、そして既定のコンパイルモードになる（たとえば、デフォルトで起動される）ことを目的としている。加えて、本明細書に記載のＩＰＯアーキテクチャは、単一マシン並列ビルドおよび大きな分散ビルドシステムの両方にとって使い易いように設計されており、最小限のオーバーヘッドで非常に深い最適化を可能にする。
【０００７】
本開示の一実施の形態は、プロシージャ間最適化の方法に関し、方法は、複数のソースコードモジュールに含まれるソースコードモジュールごとに中間表現ファイルを生成するステップと、ソースコードモジュールごとに関数インデックスと関数サマリーデータとを生成するステップと、対応するソースコードモジュールのために生成された関数インデックスおよび関数サマリーデータを中間表現ファイルの異なる部分に格納するステップと、複合関数マップを有する、生成された中間表現ファイルのシン（ｔｈｉｎ）アーカイブを生成するステップと、複数のソースコードモジュールに対してクロス・モジュール最適化を行うステップ、とを含む。
【０００８】
別の実施の形態において、プロシージャ間最適化の方法においてクロス・モジュール最適化を行うステップは、関数の高速インポートを行うために複合関数マップを利用することを含む。
【０００９】
別の実施の形態において、プロシージャ間最適化の方法においてクロス・モジュール最適化を行うステップは、一つ以上のその他のモジュールからのデバッグ情報の要求駆動型インポートを利用することを含む。
【００１０】
本開示の別の実施の形態は、複数のソースコードモジュールに対してクロス・モジュール最適化を行うステップを含む、コンピュータで実行される方法に関し、クロス・モジュール最適化は、モジュール粒度で並列であり、関数の高速インポートを行うために複合関数マップを利用し、その他のモジュールからのデバッグ情報の要求駆動型インポートを利用する。
【００１１】
別の実施の形態において、方法は、さらに、複数のソースコードモジュールに含まれるソースコードモジュールごとに中間表現ファイルを生成するステップを含む。
【００１２】
別の実施の形態において、方法は、さらに、ソースコードモジュールごとに関数インデックスと関数サマリーデータとを生成するステップを含む。
【００１３】
さらに別の実施の形態において、方法は、さらに、複数のソースコードモジュールに含まれるソースコードモジュールごとに中間表現ファイルを生成するステップと、ソースコードモジュールごとに関数インデックスと関数サマリーデータとを生成するステップと、対応するソースコードモジュールのために生成された関数インデックスおよび関数サマリーデータを中間表現ファイルの異なる部分に格納するステップと、複合関数マップを有する、生成された中間表現ファイルのシン・アーカイブを生成するステップとを含む。
【００１４】
本開示の別の実施の形態は、プロシージャ間最適化のシステムに関し、システムは、少なくとも一つのプロセッサと、当該少なくとも一つのプロセッサに接続され、命令を格納した非一時的なコンピュータ読取可能媒体とを備え、命令は、少なくとも一つのプロセッサによって実行されると、当該少なくとも一つのプロセッサに、複数のソースコードモジュールに含まれるソースコードモジュールごとに中間表現ファイルを生成させ、ソースコードモジュールごとに関数インデックスと関数サマリーデータとを生成させ、対応するソースコードモジュールのために生成された関数インデックスおよび関数サマリーデータを中間表現ファイルの異なる部分に格納させ、複合関数マップを有する、生成された中間表現ファイルのシン・アーカイブを生成させ、複数のソースコードモジュールに対してクロス・モジュール最適化を行わせる。
【００１５】
別の実施の形態において、プロシージャ間最適化のシステムにおける少なくとも一つのプロセッサに、さらに、関数の高速インポートを行うために複合関数マップを利用させる。
【００１６】
さらに別の実施の形態において、プロシージャ間最適化のシステムにおける少なくとも一つのプロセッサに、さらに、一つ以上のその他のモジュールからのデバッグ情報の要求駆動型インポートを利用させる。
【００１７】
本開示のさらに別の実施の形態は、システムに関し、システムは、少なくとも一つのプロセッサと、当該少なくとも一つのプロセッサに接続され、命令を格納した非一時的なコンピュータ読取可能媒体とを備え、命令は、少なくとも一つのプロセッサによって実行されると、当該少なくとも一つのプロセッサに、複数のソースコードモジュールに対してクロス・モジュール最適化を行わせ、クロス・モジュール最適化は、モジュール粒度で並列であり、関数の高速インポートを行うために複合関数マップを利用し、その他のモジュールからのデバッグ情報の要求駆動型インポートを利用する。
【００１８】
別の実施の形態において、システムにおける少なくとも一つのプロセッサに、さらに、複数のソースコードモジュールに含まれるソースコードモジュールごとに中間表現ファイルを生成させる。
【００１９】
さらに別の実施の形態において、システムにおける少なくとも一つのプロセッサに、さらに、ソースコードモジュールごとに関数インデックスと関数サマリーデータとを生成させる。
【００２０】
さらに別の実施の形態において、システムにおける少なくとも一つのプロセッサに、さらに、複数のソースコードモジュールに含まれるソースコードモジュールごとに中間表現ファイルを生成させ、ソースコードモジュールごとに関数インデックスと関数サマリーデータとを生成させ、対応するソースコードモジュールのために生成された関数インデックスおよび関数サマリーデータを中間表現ファイルの異なる部分に格納させ、複合関数マップを有する、生成された中間表現ファイルのシン・アーカイブを生成させる。
【００２１】
本明細書に開示するプロセッサおよびメモリシステムの一部またはすべての実施の形態は、上に開示の方法の実施例の一部またはすべてを行うように構成されてもよい。また、上に開示の方法の一部またはすべての実施例は、光メモリや磁気メモリなどの一時的または非一時的なプロセッサ読取可能記憶媒体に含まれる命令として表されてもよく、インターネットや電話接続などの通信ネットワークを介してプロセッサまたはデータ処理装置に提供される伝播信号として表されてもよい。
【００２２】
本開示の方法およびシステムの利用可能性のさらなる範囲は、以下の詳細な説明欄から明らかになるであろう。しかしながら、本明細書に開示する概念の趣旨および範囲内の各種の変更および変更例は詳細な説明欄から当業者に明らかになるため、詳細な説明欄および具体例は、方法およびシステムの実施例を示すが、例示のためだけである。
【００２３】
本開示のこれらのおよびその他の目的、特徴、および特性は、本明細書を構成する、請求の範囲および図面と合わせた以下の詳細な説明欄の検討に基づき、当業者にとってより明らかになるであろう。
【図面の簡単な説明】
【００２４】
【図１】本明細書に記載の一つ以上の実施の形態に係るＩＰＯシステムにおける例示的なフェーズを示すフロー図である。
【図２】本明細書に記載の一つ以上の実施の形態に係る例示的なＩＲ生成処理を示すフローチャートである。
【図３】本明細書に記載の一つ以上の実施の形態に係るｌａｚｙ関数インポートを利用した例示的なＩＰＯ処理を示すフローチャートである。
【図４】本明細書に記載の一つ以上の実施の形態に係る反復的なｌａｚｙ関数インポートの例示的な方法を示すフローチャートである。
【図５】本明細書に記載の一つ以上の実施の形態に係るクロス・モジュール最適化を作成するために構成された例示的なコンピューティングデバイスを示すブロック図である。
【発明を実施するための形態】
【００２５】
本明細書に示す見出しは便宜上のためだけであり、必ずしも本開示のクレームされた範囲または意味に影響するものではない。
【００２６】
図面において、同一の参照番号および略語は、理解を容易にするため、および便宜上、同一または同様の構造あるいは機能を有する構成要素または作用を識別するものである。図面は、以下の詳細な説明欄の進行において詳細に説明される。
【００２７】
詳細な説明
本開示の方法およびシステムのさまざまな実施例および実施の形態を説明する。以下の説明では、これら実施例を十分に理解するための具体的詳細、およびこれら実施例を実施可能にするための説明を示す。しかしながら、当業者は、本明細書に記載の一つ以上の実施の形態がこれら詳細の多くが無くても実践できるであろうことを理解するであろう。同様に、当業者は、本開示の一つ以上の実施の形態は、本明細書に詳細を記載していないその他の特徴を含み得ることも理解するであろう。加えて、いくつかの周知の構造または機能については、関連する記載を必要以上に曖昧にしないように、以下に詳細を示したり記載したりしていない場合がある。
【００２８】
クロス・モジュール最適化（ＣＭＯ）（プロシージャ間最適化（ＩＰＯ）の意味によく含まれる）は、コンパイラがユーザプログラムを最適化できるようにする最も効果的な方法のうちの一つである。デフォルトでは、コンパイラはシングル・モジュール・モードで動作する。このモードでは、コンパイラの最適化能力は、プログラマによって確立された人工的なソースモジュール境界によって制限されている。
【００２９】
この課題を解決するために、リンク時最適化（ＬＴＯ）および軽量プロシージャ間最適化（ＬＩＰＯ）を含む、現存するいくつかの機構が提案されてきた。しかしながら、このような既存の手法には制約があるため、デフォルトで起動されるのには適さない。詳細は後述するが、本開示の新しいＣＭＯアーキテクチャ（本明細書において「ＴｈｉｎＬＴＯ」と称する場合もある）は、ＬＴＯおよびＬＩＰＯの両方の弱点および制約を解決し、リンク時最適化の新しい標準となるように設計されている。
【００３０】
ＴｈｉｎＬＴＯには、既存の手法に勝る多様な利点を提供する多数の特徴がある。たとえば、本開示の方法およびシステムは、ＣＭＯを実装するための既存の手法を悩ませているＣＭＯスケーラビリティ問題を解決する。また、ＴｈｉｎＬＴＯは、コンパイル処理の逐次（たとえば、並列化可能でないため、ボトルネックである）部分にかかる時間も、デフォルトで最低限に減らすことができる。たとえば、副次的な中間表現（ＩＲ）のシリアル化を無くすことができるので、Ｉ／Ｏ動作も最小化できる。たとえば、これまでのＣＭＯを使う場合、プロシージャ間解析の後、コンパイラは、異なるパーティションにおいて異なる変換を生じさせるために、複数のＩＲファイルを読み込み、変換（たとえば、インライン変換）に必要な関数のクローンを作成し、再分割されたＩＲをディスクに書き戻さなければならない。このシリアル化ステップは、Ｉ／Ｏに非常に左右されやすく、本明細書において提示される方法およびシステムでは排除されている。
【００３１】
ＴｈｉｎＬＴＯを使うと、要求駆動型かつサマリーに基づいた細粒度インポートによってＣＭＯの可能性が最大限に引き出される。これによって、ＣＭＯを可能な限り有用なものにすることができる。また、ＴｈｉｎＬＴＯは、グローバルなインデックス作成（ｉｎｄｅｘｉｎｇ）にも対応している。これは、関数の高速インポートを可能にし、パフォーマンス重視だが高価なプロシージャ間解析および変換のいくつかを並列化し、デバッグビルドにかかるメモリ消費を最小化するデバッグ情報の要求駆動型ｌａｚｙインポートを利用し、サードパーティ分散ビルドシステムの統合を容易にすることができる。加えて、ＴｈｉｎＬＴＯは、ＩＰＯサーバを使って実装することも可能なため、逐次ステップが不要になる。
【００３２】
本開示の新しいＩＰＯ（たとえば、ＣＭＯ）アーキテクチャは、ＬＩＰＯおよびこれまでのＬＴＯの最適な特徴の多くを兼ね備えているが、重要な変更／追加も含んでいる。ＴｈｉｎＬＴＯに組み込まれたこれらの重要な変更／追加によって、既存の手法に勝る多くの利点がもたらされるが、概念においての類似点もいくつかある。以下に、本開示において使用される一般的な用語のいくつかの例を説明する。
【００３３】
プロシージャ間最適化（ＩＰＯ）。ＩＰＯは、通常、ＣＭＯの意味を含むため、クロス・モジュール最適化を意味する。
【００３４】
プライマリ・モジュール。ＬＩＰＯおよびＴｈｉｎＬＴＯにおいて使用される概念。内部で定義された関数のアウト・オブ・ライン・コピーが発行されることになるモジュールとして定義される。また、プライマリ・モジュールにおいて定義されるグローバル変数は、データ空間にストレージを「所有」することになる。
【００３５】
補助モジュール。ＬＩＰＯおよびＴｈｉｎＬＴＯにおいて使用される概念。プライマリ・モジュールによってインポートされるモジュール。補助モジュールにおいて定義される関数のボディは、少しの例外を除いて、ＣＭＯ（インライン展開）後に破棄されることになる。
【００３６】
補助関数。ＬＩＰＯおよびＴｈｉｎＬＴＯの概念。補助モジュールにおいて定義される関数。このような関数は、特別なリンケージを有する。
【００３７】
関数インポート。ＴｈｉｎＬＴＯの概念。必要な関数をその他のモジュールからプライマリ・モジュールに高速ロードする処理を指す。
【００３８】
静的プロモーション。ＬＩＰＯ、ＴｈｉｎＬＴＯ、およびパーティションに基づいたＬＴＯにおける概念。静的プロモーションとは、モジュールまたはパーティションの境界をリファレンスが跨いだときに、ファイルの静的変数および関数が外部でも利用できるように昇格させる処理を指す。
【００３９】
シン（Ｔｈｉｎ）・アーカイブ。アーカイブに含まれるメンバーファイルの元のファイルへのシンボルインデックスおよびリファレンスを含んだアーカイブ。シン・アーカイブによって、ローカルビルドシステムやリモートキャッシュにおいてファイルが不必要にコピーされるのを回避できる。たとえば、アーカイブ／関数マップを作成する際にＩＲファイルのコピーが作られない。代わりに、アーカイブは、元のＩＲファイルを参照するのみである。
【００４０】
中間表現（ＩＲ）。中間プログラム表現用語。なお、中間表現は、中間言語（ＩＬ）を指す場合もあるが、明確にするために、本開示の各種特徴および実施の形態の記載においてはＩＲのみを指す。
【００４１】
リンカ・プラグイン。これまでのＬＴＯおよびＴｈｉｎＬＴＯによって使用されるコンポーネント。プラグインは、リアル・リンカにロード可能なモジュールであって、最終的な再配置可能なオブジェクトではない形式の中間ファイルを処理する。
【００４２】
以下では、まず、欠点および制約を理解するために従来のＬＴＯおよびＬＩＰＯを詳細に説明し、続いて、本開示の一つ以上の実施の形態に係るＴｈｉｎＬＴＯを詳細に説明する。
【００４３】
従来のＬＴＯ
ＬＴＯは、（名称が示すとおり）リンク時にクロス・モジュール最適化および全プログラム解析をできるようにするコンパイルモデルである。通常のコンパイル時に、コンパイラは、再配置可能なリアル・オブジェクト・ファイルを生成する代わりに、プログラムＩＲ（中間表現）を有するビットコード・ファイルを生成する。これらのファイルは、リンカ・プラグインによってリンク時に収集、マージされる。プラグインによってコンパイラのＩＰＡおよびコード生成コンポーネントが呼び出し（ｉｎｖｏｋｅ）され、ＣＭＯを使ってリアル・オブジェクト・ファイルを生成する。そして、リアル・オブジェクト・ファイルはリアル・リンカに渡され、目的の実行可能ファイルまたは共有ライブラリが生成される。従来の（たとえば、これまでの、典型的な、などの）ＬＴＯモデルには、たとえば以下を含む、いくつかの異なる種類がある。
【００４４】
（ｉ）完全モノリシックモデル：このモデルでは、ＬＴＯリンクフェーズは、並列化を一切行わずに、すべての作業を行う。作業は、関数レベルの最適化やコード生成だけでなく、すべてのＩＰＡ解析および変換を含む。たとえば、ＬＬＶＭ（正しく定義されたインターフェースを有した、一連の再利用可能なライブラリとして設計されたコンパイラ基盤）の現在のＬＴＯは、完全モノリシックモデルを採用している。別例として、ＧＣＣ（ＧＮＵコンパイラコレクション）の以前のバージョンのＬＴＯも、−ｆｗｈｏｐｒが指定されない場合に完全モノリシックモデルを利用する。より最近のＧＣＣでは、−ｆｗｈｏｐｒオプションを除外してｗｈｏｐｒモードをデフォルトとしている。モノリシックモデルは、オプション−ｆｌｔｏ−ｐａｒｔｉｔｉｏｎ＝ｎｏｎｅを使って今でもＧＣＣで起動することができる。
【００４５】
（ｉｉ）スレッドレベル並列性を使ったモノリシックモデル：このモデルは項目（ｉ）において上述の完全モノリシックモデルと類似しており、主な違いは、関数レベルの最適化／コード生成がスレッドレベルの並列性を使って行われる点である。
【００４６】
（ｉｉｉ）逐次ＩＰＯ＋並列ＢＥ：このモデルでは、ＬＴＯリンクステップがすべてのＩＰＡ解析および変換（インライン変換を含む）を行う。逐次ステップの後、プロセスレベルの並列ビルドが呼び出し（ｉｎｖｏｋｅ）されて、モジュールレベルで最適化／コード生成が行われることになる。
【００４７】
（ｉｖ）分割を使ったＬＴＯ：このモデルでは、逐次リンクステップにおいてサマリーに基づいたＩＰＡ解析が行われる。また、このモデルを使ってＩＰＡインライン展開を行ってもよい（モデルは、インライン展開決定のみを生成し、変換処理はあとに回される）。ＩＰＡ解析の後、コールグラフの分割が行われてもよい。その目的は、パーティションを跨いだエッジの重みが最小化されるように、コールグラフのノードをバランスの取れたサブグラフに分割することである。各パーティションは、プロシージャ内変換および機械語生成を行うために異なるサブプロセスによって処理される。複数のサブプロセスは同時に生み出され得る。パーティションサイズは、大きすぎても小さすぎてもいけない。サイズが大きすぎると、大きなパーティションをバックエンドでコンパイルする際にメモリ負荷が大きくなり、総ビルド時間に対してのボトルネックになる。一方で、サイズが小さすぎると、ＣＭＯの効果が大幅に低減する、またはパーティションを跨いだノードの複製が完了すると重大なシリアル化オーバーヘッドを招くことになる。たとえば、ＧＣＣのＬＴＯがこのようなモデルを利用する。デフォルトモードはバランスの取れた分割を行うことである。パーティションの数は動的であるが、デフォルトでは、平均３２個程度である。また、各パーティションは、パラメータによって指定される最小サイズよりも大きいのがよい。
【００４８】
上述した完全モノリシックモデル（ｉ）の例外を除いて、その他の既存のＬＴＯモデルはすべて、いくらかのレベルの並列性を利用することによってスケーラビリティを向上させようと試みている。しかしながら、これらのモデルはすべて、単一マルチコア・マシンを使ったビルドを考慮して設計されているため、大きな分散ビルドシステムにとって制御しやすいものではない。その上、パーティションに基づいたモデルによる最大限の努力をもってしても、逐次リンクステップにおいて行われるコンパイル作業は依然として重大であろう。
【００４９】
スレッドレベル並列性について留意すべきことは、これはＬＴＯコンパイルを高速化できる一方、ベースラインコンパイルをＬＴＯなしに高速化できるという点である。非ＬＴＯコンパイルについては、構文解析は容易に並列化できないので、非ＬＴＯコンパイル用にスレッドを使うことはあまり効果的でないかもしれない。また、非ＬＴＯコンパイルは、通常、プロセスレベル並列性を使う。そのため、スレッドレベル並列性を盲目的に加えることは、システムに過負荷をかけ得る。
【００５０】
−ｇが指定されているか否かに関係なく、ＧＣＣのＩＲは型情報すべてのオーバーヘッドを抱えている。これが、ＧＣＣのＩＲのサイズがＬＬＶＭのものよりはるかに大きい理由の一つである。しかしながら、−ｇを使うと、ＬＬＶＭのＩＲサイズは、それを使わない場合の１０倍になり得る。これは、大きなアプリをモノリシックモードでビルドする、または大きなパーティションを使ってビルドするには重大な限定要因になるであろう。
【００５１】
従来のＬＴＯ技術がかなり長い間使われてきたことは注目すべきことである。初期のコンパイラは、プレリンカ（ｐｒｅ−ｌｉｎｋｅｒ）と呼ばれるモノリシックコンポーネントを使ってクロス・モジュール最適化を行っていた。プレリンカは、複合．ｏファイルを作り出し、複合．ｏファイルは、その後、最終的な実行ファイル／共有ライブラリを生成するためにリアル・リンカに送られる。初期のＬＬＶＭもＬＴＯを同様に実装した。
【００５２】
スケーラブルＬＴＯを最初に実装した初期に存在したコンパイラは、二つの革新を導入した。一つ目の革新は、リンカ・プラグインであり、もう一つは、完全並列なバックエンドである。リンカ・プラグインの導入によって、ＬＴＯは既存のビルドシステムとシームレスに、最低限の変更だけで統合できる。また、リアル・リンカのフィードバックを必要とするプログラム全体の機能も可能にする。プラグイン変更を除いて、ＬＬＶＭのＬＴＯは、２年以上にわたる発展の後も依然としてモノリシックなままである（最近ではＬＬＶＭにおいてＧＣＣタイプの分割を行う取り組みが行われた）。
【００５３】
軽量ＩＰＯ（ＬＩＰＯ）
ＬＩＰＯは、軽量ＩＰＯ（ＬｉｇｈｔｗｅｉｇｈｔＩＰＯ）を表す。ＬＩＰＯは、フィードバック最適化（Ｆｅｅｄｂａｃｋ−Ｄｉｒｅｃｔｅｄ  Ｏｐｔｉｍｉｚａｔｉｏｎ：ＦＤＯ）と密に結びついたクロス・モジュール最適化技術であり、ＬＴＯが効果を発揮するためにはプロファイル・フィードバックを必要とするという考えに基づいている。このコンパイルモデルでは、一つの追加ステップ：軽量動的ＩＰＡ（ｄｙｎ−ｉｐａ）を使ってプログラム・インストルメンテーション実行が拡張される。この追加ステップにおいて、プロファイル・カウンタの直接および間接呼び出し（ｃａｌｌ）からビルドされた動的コールグラフに基づいて粗粒度のインライン解析が実行され、解析結果はモジュール群としてプロファイルデータに記録される。
【００５４】
ＬＩＰＯを使うと、最適化ビルド（ｐｒｏｆｉｌｅ−ｕｓｅパス（ｐａｓｓ））において、従来のＬＴＯで行われていた逐次リンク・プラグイン・ステップは、ない。ＬＩＰＯモデルでは、いわゆる、補助モジュールとして、一つのソースモジュールが多数のモジュール群に含まれ得る。その結果、ｐｒｏｆｉｌｅ−ｕｓｅコンパイルは、通常のＯ２ビルドのように、完全に並列化可能になる。また、それは、分散ビルドシステムとも自然に動作し、ビルド並列性を十分に調べる。ＬＩＰＯは、ｆｕｌｌ  ｄｅｂｕｇ  ｉｎｆｏを起動させた状態で使用できる。これは、ピーク最適化を使ってビルドされたプロダクションバイナリにとって重要である。
【００５５】
ＬＩＰＯの制約
既存のＬＩＰＯ技術には、たとえば以下を含む、いくつかの制約および厄介な問題がある。
【００５６】
（ｉ）ＬＩＰＯは、プロファイル・フィードバックを使ったビルドのみに限られている（ＦＤＯと合わせて使う場合はＬＴＯの方がより効果的と思われるが）。
【００５７】
（ｉｉ）パーサーに基づいたマルチモジュール・コンパイルは、言語間のグループ化を扱えない。
【００５８】
（ｉｉｉ）パーサーに基づいたマルチモジュール・コンパイルは、実装（たとえば、パース中のコンテキストを隔離）するには複雑で扱いにくい。
【００５９】
（ｉｖ）モジュールグループ化のサイズは、メモリ制約によって制限されている。大きなＣ＋＋プログラムでは、Ｃ＋＋モジュールが何千もの関数を含むことは一般的ではない。粗粒度のインライン解析およびモジュールのグループ化を行うＬＩＰＯのｄｙｎ−ｉｐａパスにとって、当該制約を有する最良の補助モジュールを選択するための最良のヒューリスティックを考え付くことはとても難しい。モジュールのグループ化におけるわずかな違いが重大な性能変動になりかねない。
【００６０】
（ｖ）分散ビルドシステムは、適切なファイル一式をビルド・ノードに送るために、ＬＩＰＯによって導入された追加のソース依存関係について教えられる必要がある。
【００６１】
（ｖｉ）レガシーｍａｋｅｆｉｌｅにとって、新しく導入された、生成されたソースファイルへの依存関係は、ビルド・エラーにつながり得る。
【００６２】
（ｖｉｉ）古いプロファイルと連携するためには、分散ビルドのフロントエンドのより多くのサポートが必要である。
【００６３】
ＴｈｉｎＬＴＯの概要
上述したように、従来のＬＴＯおよびＬＩＰＯは、いずれも各種の制約があり、すぐそのまま使う（ｏｕｔ  ｏｆ  ｔｈｅ  ｂｏｘ）用途や一般的な用途には適していない。したがって、本開示の実施の形態は、従来のＬＴＯおよびＬＩＰＯの上記制約および問題を解決するための新しいＬＴＯ機構（「ＴｈｉｎＬＴＯ」）を示す。詳細は後述するが、ＴｈｉｎＬＴＯは、ＬＩＰＯ固有の弱点なしに、ＬＩＰＯの多くの最適部分を同様の原理で維持するように設計されている。モジュール群の決定がトレーニング実行時に行われるＬＩＰＯとは異なり、ＴｈｉｎＬＴＯは、当該決定をコンパイル実行時に、大規模並列性を容易にするＬａｚｙモードで行う。ＴｈｉｎＬＴＯでは、逐次リンカ・プラグイン・フェーズは、きわめてシン（ｔｈｉｎ）かつ高速になるように設計されている。また、少なくとも一つの実施の形態によると、デフォルトでは、このステップは、のちに行われる並列ｌａｚｙインポートを可能にするための最低限の準備作業しか行わない。
【００６４】
ＴｈｉｎＬＴＯの設計目標および特徴
本明細書に記載の一つ以上の実施の形態によると、本開示のクロス・モジュール最適化の方法、システム、およびアーキテクチャは、以下の目標および特徴のうちの一つ以上に基づいて設計されている。
【００６５】
（ｉ）ＴｈｉｎＬＴＯは、プロファイル・フィードバックに依存しないで動作してもよい。
【００６６】
（ｉｉ）デフォルトでは、ＴｈｉｎＬＴＯは、無駄なく経費を抑える（ｌｅａｎ  ａｎｄ  ｍｅａｎ）ように設計され、大型メモリ構成を有するマシンに依存しない。ＴｈｉｎＬＴＯは、通常のＯ２と同程度に使い勝手が良くスケーラブルであってもよい。
【００６７】
（ｉｉｉ）ＬＴＯの逐次部分は、大規模並列性を効果的なものにするために、（アムダールの法則の通り）できるだけシン（ｔｈｉｎ）である。これは、たとえば、このステップにおいて厳密に必要でないものは、デフォルトで剪定（ｐｒｕｎｅｄ）してもよいことを意味する。ＩＯ動作は最低限であってもよく、ほとんどの演算は並列ステージまで先延ばししてもよい。
【００６８】
（ｉｖ）ＴｈｉｎＬＴＯは、最低限のメモリおよびコンパイル時のオーバーヘッドで、クロス・モジュール・インライン展開の利益を最大限に引き出すように設計されている。異なるコストでのサマリーに基づいた全プログラム解析を、追加フラグまたはより高い最適化レベルを使って、任意に起動することができる。
【００６９】
（ｖ）ｐｒｏｆｉｌｅ−ｆｅｅｄｂａｃｋを起動すると、逐次ステップを完全に排除できる。
【００７０】
（ｖｉ）並列化の粒度はソースモジュールレベルで維持されてもよく、オンデマンドインポートの粒度は関数レベルで維持されてもよい。分散ビルドについては、粒度は大きすぎても（たとえば、低い並列性）小さすぎても（たとえば、高いセットアップコスト、インポート共有の欠如、コード複製にかかるコスト、など）いけない。
【００７１】
（ｖｉｉ）ＴｈｉｎＬＴＯは、単一マシン並列ビルドおよび大規模分散ビルドの両方にとって使い易いように設計されている。
【００７２】
（ｖｉｉｉ）ＴｈｉｎＬＴＯは、コンパイル時およびランタイムでのバグトリアージおよびデバッグを簡単にできる（たとえば、非ＬＴＯオブジェクトファイルの組み合わせを容易にできる）。
【００７３】
少なくとも一つの実施の形態によると、従来のＬＴＯビルドと同様に、ＴｈｉｎＬＴＯは、３−フェーズ・コンパイルである（詳細は後述するが、１−フェーズに簡略化できるＴｈｉｎＬＴＯ＋ＦＤＯは除く）。しかしながら、ＴｈｉｎＬＴＯにおいて各フェーズで実行されるタスクは、従来のＬＴＯにおいて各ステージで実行されるものと異なる。従来のＬＴＯと比較すると、ＴｈｉｎＬＴＯの設計は、並列性を解放し、全体のスケーラビリティを向上させるものである。
【００７４】
以下では、（たとえば、単一マシンビルドのための）ＴｈｉｎＬＴＯの基本設計についての、さらなる詳細を示し、また、たとえば、分散ビルド、ＦＤＯなどを含む異なる状況を対象とするＴｈｉｎＬＴＯのいくつかの異なる例についても説明する。
【００７５】
単一マシン並列ビルドのためのＴｈｉｎＬＴＯ
図１は、本明細書に記載の一つ以上の実施の形態に係る、ＴｈｉｎＬＴＯにおける例示的な３−フェーズ・コンパイル１００を示す。図１に示す各フェーズの詳細は後述する。
【００７６】
フェーズ−１：関数インデックスとサマリーと共にＩＲを生成
本開示の一つ以上の実施の形態によると、第一フェーズ（たとえば、図１に示す例示的なコンパイル１００の１１０）において、コンパイラは、再配置可能なリアル・オブジェクトの代わりにＩＲビットコード・ファイルを作り出してもよい。加えて、コンパイラは、以下を生成してＩＲファイルの異なる部分に格納してもよい。
【００７７】
（１）関数ボディ・インデックス。基本的には、ＩＲファイルにおいて関数のｉｄをそのボディのオフセットにマッピングした、関数のシンボルテーブルである。これによって、のちの高速読み取りおよびｌａｚｙインポートが可能になる。
【００７８】
（２）関数サマリーデータ。サマリーデータは、フェーズ−３コンパイルで行われる関数インポートの決定を補助するために使われる。関数サマリーデータは、以下を含んでもよいが、これらに限定されない。（ａ）サイズ、プロローグ／エピローグ・コスト、分岐数、ｍａｌｌｏｃコールを有するかなどのコア関数属性。（ｂ）ｔｒａｎｓｆｅｒ関数（もしあれば）。ｔｒａｎｓｆｅｒ関数は、パラメータ値／値の範囲をインライン展開後の潜在的コストの削減にマッピングする。
【００７９】
図２は、本明細書に記載の一つ以上の実施の形態に係る、クロス・モジュール最適化の方法、システム、およびアーキテクチャのフェーズ−１についての例示的なコンパイル・パイプライン２００を示す。例示的なフェーズ−１のコンパイラコマンドラインは次のようになるであろう。
【００８０】
${CC} -O2 -c -fthin-lto -o source.o source.cc
フェーズ−２：超薄リンカ・プラグイン層
本開示の少なくとも一つの実施の形態によると、デフォルトでは、ＴｈｉｎＬＴＯの第二フェーズ（たとえば、図１に示す例示的なコンパイル１００の１２０）では、最低限の作業量のみが行われる。ＴｈｉｎＬＴＯでは、プラグインは、フェーズ−１から、複合関数マップを有する、生成されたＩＲファイルのシン・アーカイブを生成するだけでよい。このように、メモリ使用量は非常に少なく、Ｉ／Ｏは最小化されることになる。加えて、以下の例示的技法を行って、関数インデックスの総サイズを低減することができる。
【００８１】
（１）「ＣＯＭＤＡＴ」の削除。たとえば、最後のインデックスのｃｏｍｄａｔコピーの一つだけを選択する。プロファイルデータが存在する状況では、アウト・オブ・ライン・コピーが選択されてもよい。
【００８２】
（２）（たとえば、ユーザまたはプロファイルデータによってマーク付けされた）すべてのｕｎｌｉｋｅｌｙ／ｃｏｌｄ関数を、利益（たとえば、サイズ削減）をもたらし得ないのであれば、スキップする。なお、より正確な推定を行うためのコールサイト情報が利用可能でない限り、この技法は、非常に小さい関数に限定されるべきであろう）。
【００８３】
（３）インライン展開をしても利益がない極めて大きい関数をスキップする。
少なくとも一つの実施の形態によると、より重量な、サマリーに基づいたＩＰＡパスを任意に行うことができる。しかしながら、このようなパスは、デフォルトで起動しなくてもよい。このような追加パスの設計詳細は本開示の範囲を超えている。
【００８４】
デフォルトのＴｈｉｎＬＴＯモードを使うと、リンカ・プラグイン・ステップは、フェーズ−１にとって、事実上、同期点であり、リンカ・プラグイン・ステップの後、フェーズ−３がＩＲ共有を開始できるようになる。なお、同期ステップを完全に無くすことも可能である。これをどのように実現できるかについての一例として、ＩＲを連続して事前演算するビルド・サーバがある。これによって、コンパイラ・ビルドは関数のボディをデータベースからフェッチするだけでよい。見つからない場合は、ビルド・サーバに対してオンデマンド要求を行うことができる。
【００８５】
フェーズ−２の終わりに、プラグインは、バックエンド・ドライバを並列して呼び出す（ｉｎｖｏｋｅ）ことになる。バックエンド・ドライバの呼び出し毎に、複合関数ボディ・インデックスを有するシン・アーカイブ・ファイルに加えて、修正されていないＩＲファイルがフェーズ−１から渡されることになる。リンカ・プラグインを呼び出す（ｉｎｖｏｋｅ）ための例示的コマンドラインは次のようになるであろう。
【００８６】
${CC} -fthin-lto=./$ [some_dir]/prog_thin_arch.a sourcel.o source2.o … -o a.out
上記例示的コマンドラインにおいて、ｓｏｕｒｃｅｘ．ｏファイルは、フェーズ−１で作り出された関数マップおよびサマリーデータを有するＩＲファイルである。リンカ・プラグインは、フェーズ−２において、ｐｒｏｇ＿ｔｈｉｎ＿ａｒｃｈ．ａファイルを作り出すことになる。重量ＩＰＡパスが起動されている状況において、ＩＰＡ解析の結果もアーカイブファイルに格納されてもよい。
【００８７】
以下は、ｌｄプラグインによる、並列バックエンド・ドライバ呼び出しの例示的なコマンドラインである。
【００８８】
${BE_DRIVER}  -fthin-lto-use=./${some_dir}/prog_thin_arch.a source1.o -o source1_real.o ….
この例示的コマンドラインで何が起こるかについてのさらなる詳細を以下に示す。
【００８９】
フェーズ−３：Ｌａｚｙ関数インポートを利用した、完全並列化可能な要求駆動型ＩＰＯ
本開示の一つ以上の実施の形態によると、ＴｈｉｎＬＴＯの第三フェーズ（たとえば、図１に示す例示的なコンパイル１００の１３０）におけるコンパイル・パイプラインは、図３に示す例示ブロックを含んでもよい。
【００９０】
ＴｈｉｎＬＴＯの第三フェーズ３００のブロック３０５は、反復的なｌａｚｙ関数インポートを含んでもよい。さらなる詳細は図４に示すが、このステップではシン・アーカイブに含まれる補助モジュールから、必要とされる可能性がある補助関数のみがプライマリ・モジュールにインポートされる。なお、これは、補助モジュールに含まれるすべての関数が強制的に同時にインポートされるＬＩＰＯとは異なる。ブロック３０５にて行われるであろう反復的なｌａｚｙ関数インポートについてのさらなる詳細を、図４を参照して以下に示す。
【００９１】
図４は、本明細書に記載の一つ以上の実施の形態に係る、反復的なｌａｚｙ関数インポートについての例示的な処理４００を示す。
【００９２】
ブロック４０５において、モジュールに含まれる、外部の非ライブラリ関数へのすべてのコールサイトが決定（たとえば、識別、場所を特定など）されてもよい。
【００９３】
ブロック４１０において、ブロック４０５で決定されたコールサイトごとに、コールサイトについての関数サマリーデータが読み出され、インポートすることについての推定利益について判定がなされる。本開示の少なくとも一つの実施の形態によると、サイトをインポートすることが有益である（たとえば、サイトについて判定された、インポートすることについての推定利益＞０）と判定された場合、当該サイトは、優先キューに入れられてもよい。
【００９４】
ブロック４１５において、優先キューが空であるか、または優先キューが限界に達したかどうかの判定が行われてもよい。
【００９５】
ブロック４１５において優先キューが空である、または優先キューが限界に達したと判定された場合、関数インポートは完了し、処理はブロック４４０に進んでよい。
【００９６】
ブロック４４０において、（たとえば、ブロック４１５で決定されたように）反復的な関数インポートが完了すると、インポートされた関数の型情報がｌａｚｙにインポートされてもよい。
【００９７】
一方で、ブロック４１５において優先キューが空ではなく、優先キューが限界に達していないと判定された場合、反復的な処理はブロック４２０で継続してもよい。ブロック４２０では、優先キューから最上位のエントリが取り出される。
【００９８】
ブロック４２５において、グローバル関数インデックスに含まれる関数のエントリを使用して、対応するモジュールに含まれる関数のＩＲの位置を特定、ＩＲをロードしてもよい。
【００９９】
ブロック４３０において、関数についてのプロファイルが存在し、当該プロファイルがロードされた関数ＩＲにおいて使用可能でない場合、プロファイルを、ブロック４２５でロードされた関数ＩＲにアノテート（ａｎｎｏｔａｔｅ）してもよい。
【０１００】
ブロック４３５において、ブロック４２５でロードされた関数ＩＲから、新しい、外部の非ライブラリへのコールサイトが収集（たとえば、取得、決定など）されてもよい。新しい、外部の非ライブラリへのコールサイトのいずれかは、インポートするのに有益であると（たとえば、コールサイトの関数サマリーおよびコールサイト解析に基づいて）判定された場合、優先キューに加えられる。
【０１０１】
図３に示す例示的な処理３００に戻ると、ブロック３１０は、グローバル・シンボルのリンク設定（クロス・モジュール）および静的プロモーションを含んでもよい。明示的に「インポートしない」とマーク付けされたｃｏｌｄモジュールは、そうする必要はない。
【０１０２】
ブロック３１５は、ｌａｚｙデバッグ情報のインポートおよび補助モジュールからのマージを含んでもよい。このステップでは、インポートされた関数によって必要とされるデバッグ情報エントリ（ＤＩＥ）（または、それらのメタ・データ）のみがプライマリ・モジュールにマージ（たとえば、統一）される。なお、本開示の一つ以上の実施の形態によると、ブロック３１０（グローバル・シンボルのリンク設定および静的プロモーション）およびブロック３１５（デバッグのインポート）のいずれかまたは両方は、ＴｈｉｎＬＴＯの第三フェーズ３００（関数インポート）の間に反復的に行われてもよい。
【０１０３】
ブロック３２０は、拡張プライマリ・モジュールに対するプロシージャ間解析Ｐａｓｓを含んでもよい。
【０１０４】
ＴｈｉｎＬＴＯの第三フェーズ３００に含まれるブロック３２５は、後期の大域的最適化、特定マシン向け最適化、およびコード生成を含んでもよい。
【０１０５】
なお、その他のモジュールからインポートされたすべての関数は、ＬＩＰＯにしたがって定義された補助関数であることを理解されたい。これらは、コピーがローカル関数になる、またはその他のモジュールによって定義される保証がない場合を除いて、インライン変換後に安全に破棄することができる。
【０１０６】
ＴｈｉｎＬＴＯのデバッグ情報のＬａｚｙインポート
デバッグ情報は、メモリの多くを消費し、多くの型を統一／マージするにはコストがかかり得る。プライマリ・モジュールがＮ個の関数をＭ個の異なるモジュールからインポートしたとすると、Ｍ個すべてのモジュールからデバッグ情報をインポートすることは、ひどくコストがかかることである。本開示の一つ以上の実施の形態によると、この問題を処理する一つの方法として、デバッグ情報エントリを要求駆動方式でインポートする方法がある。このような手法は、たとえば、インポートされた関数ごとにＩＲを確認（ｗａｌｋ）すること、過渡的に参照された、一連のデバッグ情報エントリを演算すること、およびそれらをプライマリ・モジュールにマージすることを含んでもよい。
【０１０７】
フェーズ−２およびフェーズ−３ビルドを２つのＰａｓｓに分ける
ビルド並列性を活用するためには、フェーズ−１コンパイルは、通常、（たとえば、コンパイラ・オプション−ｃおよびソースファイルごとの独立したビルド・アクションを介して）自身のパスにおいて行われる。しかしながら、本開示の少なくとも一つの実施の形態によると、デフォルトでは、ＴｈｉｎＬＴＯのフェーズ−２およびフェーズ−３ステップは、バックエンド・アクションの並列ビルドを駆動しているリンカ・プラグインを使って、マージされたパスにおいて行われてもよい。
【０１０８】
ＴｈｉｎＬＴＯについては、別のビルドモードも存在する。リンカ・プラグイン・ステップでは、シン・アーカイブ・ファイルが作成された後、リンカ・プラグインは、バックエンド・アクション・ファイル（たとえば、通常、ＧＮＵのｍａｋｅｆｉｌｅ）を作成し、コンパイルを、バックエンド・ドライバの呼び出し（ｉｎｖｏｋｅ）によって再開する代わりに停止することを選べる。そして、ユーザは、たとえば以下のように、生成されたｍａｋｅｆｉｌｅを使った「ｍａｋｅ」を直接呼び出す（ｉｎｖｏｋｅ）ことができる。
【０１０９】
Pass 1:
${CC} -fthin-lto -c source1.cc
${CC} -fthin-lto -c source2.cc
Pass 2:  #（ｇｅｎｅｒａｔｅｄ．ｍｋを生成し、ＢＥを呼び出し（ｉｎｖｏｋｉｎｇ）しないで停止する)
${CC} -fthin-lto=./thin_arch.a -fthin-lto-twopass=./generated.mk source1.cc source2.c
Pass 3:  #（ユーザによって明示的に呼び出し（ｉｎｖｏｋｅ）される）
make -j10 -f ./generated.mk
上述のモードによって、ユーザは、ＴｈｉｎＬＴＯビルドをユーザがリモート・コンパイル用にカスタマイズしたビルドシステムと容易に統合する柔軟性を持つことができる。
【０１１０】
分散ビルドシステム用のＴｈｉｎＬＴＯ
本開示の少なくとも一つの実施の形態によると、ＴｈｉｎＬＴＯのフェーズ−１は、任意の分散ビルドシステムが提供する完全並列性に完全に従ってもよい。リンカ・プラグインは逐次ステップだが、ＴｈｉｎＬＴＯはそれを最小限にまで縮小する。しかしながら、ビルドのより高価なステップの間、フェーズ−３（たとえば、リンカ・プラグイン）は、任意の分散ビルドシステムと、ビルドシステム特有のナレッジをコンパイラ自体に埋め込むことなく、連携する必要がある。
【０１１１】
本開示のＴｈｉｎＬＴＯ設計およびアーキテクチャを使うと、この問題を容易に解決できる。たとえば、上述の２−ｐａｓｓコンパイルを使ってこの問題を解決できる。リンカ・プラグインによってｍａｋｅｆｉｌｅが生成された後、ビルドシステム特有の変換ツールを使ってｍａｋｅｆｉｌｅを目的のビルドファイル形式に変換することができる。そして、ビルドファイルは分散ビルドのフロントエンドに送られて実行することができる。
【０１１２】
プロファイル・フィードバック（ＦＤＯ／ＡＦＤＯ）を使ったビルド
ＴｈｉｎＬＴＯは、自動フィードバック最適化（Ａｕｔｏｍａｔｉｃ  Ｆｅｅｄｂａｃｋ−Ｄｉｒｅｃｔｅｄ  Ｏｐｔｉｍｉｚａｔｉｏｎ：ＡＦＤＯ）と透過的に連携し、古いプロファイルとも同様に透過的に連携する。インストルメンテーションに基づいたＦＤＯでは、ＴｈｉｎＬＴＯを使ったｐｒｏｆｉｌｅ−ｕｓｅコンパイルは、通常のＯ２やＬＩＰＯビルド同然の単一フェーズ・コンパイルに退化し得る。シン・アーカイブはｐｒｏｆｉｌｅ−ｇｅｎパスで生成できてｐｒｏｆｉｌｅ−ｕｓｅステップで再利用できる、という考えである。
【０１１３】
なお、本明細書に記載の実施の形態の一つ以上によると、プロファイル・フィードバックを使ったＴｈｉｎＬＴＯに関して、モジュールレベルのサマリーによって、大部分のｃｏｌｄモジュールの関数のインポートをせずに済むようになる。また、関数レベルのインポートは、プロファイル・ガイダンスを使うとより選択的かつ高速であり得る。
【０１１４】
本開示の少なくとも一つの実施の形態に従い、クロス・モジュール・インライン展開においてＴｈｉｎＬＴＯと同様の効果を実現できる、ＩＰＯ基盤の一つの考えられる代替設計例を以下に説明する。
【０１１５】
（１）リンカ・プラグイン・ステップでは、ＬＩＰＯ方式の粗粒度のインライン解析が行われる。インライン解析は、サマリーデータ（たとえば、主にコールグラフ）に基づいている。
【０１１６】
（２）（たとえば、ＧＣＣで行われるような）本格的なインライン決定を行う代わりに、このパスは、有用なＣＭＯを可能にするために必要なグループ化の決定のみを行う。
【０１１７】
（３）関数は、元のソースモジュールの境界に基づいて分割されてもよい。
（４）ＣＭＯインライン展開を可能にするために必要な関数は、上記のインライン解析に基づいて、目的のソースモジュールにクローン作成（ｃｌｏｎｅ）されてもよい。関数クローニング（ｃｌｏｎｉｎｇ）は、ＴｈｉｎＬＴＯにおいて、事実上、補助関数のインポートであるが、リンカ・プラグイン・ステージで行われる。
【０１１８】
ＴｈｉｎＬＴＯと比較すると、上述の例示的な代替設計は、たとえば以下を含む、いくつかの欠点がある。
【０１１９】
（ｉ）インライン解析がコンパイル・パイプラインのボトルネックに加えられるので、並列化の最大可能スピード・ファクターが減少する。
【０１２０】
（ｉｉ）補助関数のインポートステップが、シリアル化ステップにも追加される。スレッドレベル並列性が適用されるとしても、単一マシンに限られる。
【０１２１】
（ｉｉｉ）サマリーデータのサイズは、依然としてプログラムサイズに対して線形関係であるため、将来のある時点でビルドマシン限界に達してしまうかもしれない。
【０１２２】
（ｉｖ）デバッグ情報処理問題。デバッグ型のｌａｚｙ／オンデマンドインポートをサポートするために、コンパイラは、シリアル化されたステップにおいて、ほとんどのモジュールのＩＲを確認してゆく（ｗａｌｋ  ｔｈｒｏｕｇｈ）必要がある。
【０１２３】
図５は、本明細書に記載の一つ以上の実施の形態に係る、クロス・モジュール最適化を作成するために構成された例示的なコンピュータ（５００）のハイレベルブロック図である。非常に基本的な構成（５０１）において、コンピューティングデバイス（５００）は、一般的に、一つ以上のプロセッサ（５１０）とシステムメモリ（５２０）とを備える。メモリバス（５３０）は、プロセッサ（５１０）とシステムメモリ（５２０）との間の通信に使用することができる。
【０１２４】
所望の構成によっては、プロセッサ（５１０）は、マイクロプロセッサ（μＰ）、マイクロコントローラ（μＣ）、デジタルシグナルプロセッサ（ＤＳＰ）、またはそれらの組み合わせを含む任意の種類でよいが、これらに限定されない。プロセッサ（５１０）は、Ｌ１キャッシュ（５１１）およびＬ２キャッシュ（５１２）などの、一つ以上のレベルのキャッシュ、プロセッサコア（５１３）、および複数のレジスタ（５１４）を備え得る。プロセッサコア（５１３）は、算術論理演算装置（ＡＬＵ）、浮動小数点演算装置（ＦＰＵ）、デジタル信号処理コア（ＤＳＰコア）、またはそれらの組み合わせを備え得る。メモリコントローラ（５１６）は、プロセッサ（５１０）と合わせて使うことも可能であり、実装によっては、メモリコントローラ（５１５）は、プロセッサ（５１０）の内部部品であり得る。
【０１２５】
所望の構成によっては、システムメモリ（５２０）は、揮発性メモリ（ＲＡＭなど）、不揮発性メモリ（ＲＯＭ、フラッシュメモリなど）、またはそれらの任意の組み合わせを含む任意の種類であり得るが、これらに限定されない。システムメモリ（５２０）は、一般的に、オペレーティングシステム（５２１）、一つ以上のアプリケーション（５２２）、およびプログラムデータ（５２４）を備える。アプリケーション（５２２）は、それ用のクロス・モジュール最適化を作成する方法およびアーキテクチャ（５２３）を含んでよい。プログラムデータ（５２４）は、命令を含んでもよく、命令は、一つ以上の処理装置によって実行されると、プログラムの最適化（５２３）の方法およびアーキテクチャを実装する。少なくともいくつかの実施の形態によると、アプリケーション（５２２）は、オペレーティングシステム（５２１）上のプログラムデータ（５２４）で動作するように構成され得る。
【０１２６】
コンピューティングデバイス（５００）は、基本的な構成（５０１）と必要な装置およびインターフェースとの間の通信を容易にするための、さらなる特徴または機能、およびさらなるインターフェースを有し得る。
【０１２７】
システムメモリ（５２０）は、コンピュータ記憶媒体の一例である。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、またはその他のメモリ・テクノロジー、ＣＤ−ＲＯＭ、デジタル多目的ディスク（ＤＶＤ）、またはその他の光記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置、またはその他の磁気記憶装置、または所望の情報を格納するのに使用でき、コンピューティングデバイス５００によって利用可能な任意のその他の媒体を含むが、これらに限定されない。このようなコンピュータ記憶媒体は、いずれもデバイス（５００）の一部であり得る。
【０１２８】
コンピューティングデバイス（５００）は、携帯電話、スマートフォン、携帯情報端末（ＰＤＡ）、個人向けメディアプレーヤーデバイス、タブレットコンピュータ（タブレット）、無線ウェブウォッチデバイス、個人向けヘッドセット装置、特定用途装置、または上述の機能のいずれかを含むハイブリッド装置などの、スモール・フォーム・ファクター・ポータブル（またはモバイル）電子機器の一部として実装することができる。また、コンピューティングデバイス（５００）は、ラップトップコンピュータおよび非ラップトップコンピュータ構成の両方を含むパーソナルコンピュータとして実装することもできる。
【０１２９】
上述の詳細な説明では、デバイスおよび／または処理の各種実施の形態を、ブロック図、フロー図、および／または実施例を用いて説明した。このようなブロック図、フロー図、および／または実施例が一つ以上の機能および／または動作を含んでいる限り、このようなブロック図、フロー図、または実施例内の各機能および／または動作がさまざまなハードウェア、ソフトウェア、ファームウェア、またはそれらの実質的な任意の組み合わせによって、個々、および／またはまとめて実装され得ることが、当業者に理解されるであろう。少なくとも一つの実施の形態によると、本明細書に記載の主題のいくつかの部分は、特定用途向け集積回路（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ：ＡＳＩＣ）、フィールド・プログラマブル・ゲート・アレイ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ：ＦＰＧＡ）、デジタル信号プロセッサ（ＤＳＰ）、またはその他の統合形式で実装されてもよい。しかしながら、本明細書に開示の実施の形態のいくつかの態様の全体または一部は、一つ以上のコンピュータで動作する一つ以上のコンピュータプログラムとして、一つ以上のプロセッサで動作する一つ以上のプログラムとして、ファームウェアとして、またはそれらの実質的な任意の組み合わせとして、集積回路において同等に実装可能であること、およびソフトウェアおよび／またはファームウェア用に回路を設計するおよび／またはプログラムを書くことは、本開示に鑑みて、当業者の技能の範囲内であるだろうことが当業者にはわかるであろう。加えて、本明細書に記載の主題の機構は、さまざまな形式のプログラムプロダクトとして配布できること、および本明細書に記載の主題の例示的な実施の形態は、実際に配布を行うために使用される特定の種類の非一時的な信号担持媒体に関係なく、適用されることを、当業者は理解するであろう。たとえば、非一時的な信号担持媒体は、以下を含むが、これらに限定されない。フロッピー（登録商標）ディスク、ハードディスクドライブ、コンパクトディスク（Ｃｏｍｐａｃｔ  Ｄｉｓｃ：ＣＤ）、デジタルビデオディスク（Ｄｉｇｉｔａｌ  Ｖｉｄｅｏ  Ｄｉｓｋ：ＤＶＤ）、デジタルテープ、コンピュータメモリなどの記録可能型の媒体、およびデジタルおよび／またはアナログ通信媒体などの伝送媒体。（たとえば、光ファイバケーブル、導波路、有線通信リンク、無線通信リンクなど）
本明細書における実質的にすべての複数形および／または単数形の用語の使用について、当業者は、文脈および／または用途に対して適切に複数形から単数形、および／または単数形から複数形に言い換えることができる。各種の単数形／複数形の置き換えは、明確にするために本明細書において明示されている場合がある。
【０１３０】
したがって、主題の特定の実施の形態について説明した。その他の実施の形態は、以下の請求項の範囲内である。場合によっては、請求項に記載の動作は、異なる順序で行うことができ、それでもなお所望の結果が得られる。加えて、添付の図面に示した処理は、所望の結果を得るために必ずしも順次または図示された特定の順序で行われなければならないわけではない。実装によっては、マルチタスクおよび並列処理は利点になる場合がある。
【要約】
プロシージャ間最適化（ＩＰＯ）の方法およびシステムを提供する。新しいＩＰＯアーキテクチャ（「ＴｈｉｎＬＴＯ」と称する）は、これまでのリンク時最適化（ＬＴＯ）や軽量プロシージャ間最適化（ＬＩＰＯ）などの、既存のＩＰＯ手法の弱点および制約を解決し、リンク時最適化の新しい標準となるように設計されている。ＴｈｉｎＬＴＯを使うと、要求駆動型かつサマリーに基づいた細粒度インポートによってクロス・モジュール最適化（ＣＭＯ）の可能性が最大限に引き出される。これによって、ＣＭＯを可能な限り有用なものにすることができる。また、ＴｈｉｎＬＴＯは、グローバルなインデックス作成（ｉｎｄｅｘｉｎｇ）にも対応している。これは、関数の高速インポートを可能にし、パフォーマンス重視だが高価なプロシージャ間解析および変換のいくつかを並列化し、デバッグビルドにかかるメモリ消費を最小化するデバッグ情報の要求駆動型ｌａｚｙインポートを利用し、サードパーティ分散ビルドシステムの統合を容易にすることができる。加えて、ＴｈｉｎＬＴＯは、ＩＰＯサーバを使って実装することも可能なため、逐次ステップが不要になる。【図１】
0006275929.tif 000002
【図２】
0006275929.tif 000003
【図３】
0006275929.tif 000004
【図４】
0006275929.tif 000005
【図５】
0006275929.tif 000006