(57)【特許請求の範囲】
【請求項１】
コード最適化のための方法であって、コンピュータが、
コンパイルされ且つリンクされたオブジェクト・コードをディスアセンブルするステップと、
ディスアセンブルされた前記コード内で、レジスタに関連するストア命令及びリストア命令を含む関数の複数の呼び出しを識別するステップと、
ディスアセンブルされた前記コードを分析し、前記レジスタをkillする命令が後に続く前記関数の前記呼び出しの一つを突き止めるステップであって、前記関数の少なくとも１つの他の呼び出しはレジスタをkillする命令が後に続かない、前記突き止めるステップと、
前記関数が少なくとも１つの他の呼び出しにより呼び出されるとき前記ストア命令の実行を削除せず、前記関数が前記呼び出しの前記１つにより呼び出されるとき前記関数から前記ストア命令の実行を削除するように前記関数に対応する前記コードを変更するステップと
を実行し、
前記コードを変更するステップが、前記ストア命令が削除された前記関数の最適化バージョンを作成するように、前記関数に対応する前記コードの一部を前記コードの終わりに複製するステップをさらに含む、方法。
【請求項２】
前記コードを変更するステップが、前記関数が前記呼び出しの前記１つにより呼び出されるとき、前記関数から前記リストア命令を削除するように、前記コードを変更するステップを含む、請求項１記載の方法。
【請求項３】
前記コードを変更するステップが、前記呼び出しの前記１つを前記関数の前記最適化バージョンのアドレスに指定変更するステップを含む、請求項１記載の方法。
【請求項４】
前記呼び出しの前記１つを指定変更するステップが、複数の前記呼び出しを前記関数の前記最適化バージョンの前記アドレスに指定変更するステップを含む、請求項３記載の方法。
【請求項５】
前記関数が複数のレジスタに関連するストア命令及びリストア命令を含み、指定変更される前記複数の呼び出しの各々が、前記複数のレジスタの少なくとも１つをkillするそれぞれの命令が後に続き、前記コードの一部を前記コードの終わりに複製するステップが、前記関数の前記最適化バージョンから、指定変更された前記呼び出しに続きkillされる全てのレジスタに関連する、前記ストア命令及びリストア命令を削除するステップを含む、請求項４記載の方法。
【請求項６】
前記コードを変更するステップが、前記関数の少なくとも１つの他の呼び出しに対して、ラッパ・コードを作成するステップを含み、前記ラッパ・コードが、前記関数の前記最適化バージョンの呼び出しを含み、該呼び出しが、前記レジスタに関連するストア命令により先行され、前記レジスタに関連するリストア命令が後に続き、前記コードを変更するステップが、前記関数の少なくとも１つの他の呼び出しを前記ラッパ・コードに指定変更するステップを含む、請求項５記載の方法。
【請求項７】
前記関数の少なくとも１つの他の呼び出しをラッパ・コードに指定変更するステップが、前記関数の少なくとも１つの他の呼び出しを、前記ラッパ・コードへの分岐命令により置換するステップを含む、請求項６記載の方法。
【請求項８】
前記ラッパ・コードを作成するステップが、指定変更される異なる呼び出しに対して、複数のそれぞれの前記ラッパ・コードを作成するステップを含み、前記複数の呼び出しを指定変更するステップが、異なる前記呼び出しをそれぞれの前記ラッパ・コードに指定変更するステップを含む、請求項６記載の方法。
【請求項９】
ディスアセンブルされた前記コードが、最後の命令で終わる命令の固定シーケンスを含み、前記コードを変更するステップが、複製された前記コードを、前記固定シーケンスを変更することなく、前記最後の命令の後に追加するステップを含む、請求項３記載の方法。
【請求項１０】
コード最適化のための装置であって、
コンパイルされ且つリンクされたオブジェクト・コードをディスアセンブルし、
ディスアセンブルされた前記コード内で、レジスタに関連するストア命令及びリストア命令を含む関数の複数の呼び出しを識別し、
ディスアセンブルされた前記コードを分析し、前記レジスタをkillする命令が後に続く前記関数の前記呼び出しの一つを突き止め、ここで前記関数の少なくとも１つの他の呼び出しはレジスタをkillする命令が後に続かず、
前記関数が少なくとも１つの他の呼び出しにより呼び出されるとき前記ストア命令の実行を削除せず、前記関数が前記呼び出しの前記１つにより呼び出されるとき前記関数から前記ストア命令の実行を削除するように前記関数に対応する前記コードを変更し、ここで前記コードを変更することが、前記ストア命令が削除された前記関数の最適化バージョンを作成するように、前記関数に対応する前記コードの一部を前記コードの終わりに複製することを含む、
前記装置。
【請求項１１】
前記コードを変更することが、前記関数が前記呼び出しの前記１つにより呼び出されるとき、前記関数から前記リストア命令を削除するように、前記コードを変更することを含む、請求項１０記載の装置。
【請求項１２】
前記コードを変更することが、前記呼び出しの前記１つを前記関数の前記最適化バージョンのアドレスに指定変更することを含む、請求項１０記載の装置。
【請求項１３】
前記呼び出しの前記１つを指定変更することが、複数の前記呼び出しを前記関数の前記最適化バージョンの前記アドレスに指定変更することを含む、請求項１２記載の装置。
【請求項１４】
前記関数が複数のレジスタに関連するストア命令及びリストア命令を含み、指定変更される前記複数の呼び出しの各々が、前記複数のレジスタの少なくとも１つをkillするそれぞれの命令が後に続き、前記コードの一部を前記コードの終わりに複製することが、前記関数の前記最適化バージョンから、指定変更された前記呼び出しに続きkillされる全てのレジスタに関連する、前記ストア命令及びリストア命令を削除することを含む、請求項１３記載の装置。
【請求項１５】
前記コードを変更することが、前記関数の少なくとも１つの他の呼び出しに対して、ラッパ・コードを作成することを含み、前記ラッパ・コードが、前記関数の前記最適化バージョンの呼び出しを含み、該呼び出しが、前記レジスタに関連するストア命令により先行され、前記レジスタに関連するリストア命令が後に続き、前記コードを変更することが、前記関数の少なくとも１つの他の呼び出しが前記ラッパ・コードに指定変更することを含む、請求項１４記載の装置。
【請求項１６】
前記関数の少なくとも１つの他の呼び出しをラッパ・コードに指定変更することが、前記関数の少なくとも１つの他の呼び出しを、前記ラッパ・コードへの分岐命令により置換することを含む、請求項１５記載の装置。
【請求項１７】
前記ラッパ・コードを作成することが、指定変更される異なる呼び出しに対して、複数のそれぞれの前記ラッパ・コードを作成することを含み、前記複数の呼び出しを指定変更することが、異なる前記呼び出しをそれぞれの前記ラッパ・コードに指定変更することを含む、請求項１５記載の装置。
【請求項１８】
ディスアセンブルされた前記コードが、最後の命令で終わる命令の固定シーケンスを含み、前記コードを変更することが、複製された前記コードを、前記固定シーケンスを変更することなく、前記最後の命令の後に追加することを含む、請求項１２記載の装置。
【請求項１９】
コード最適化のためのプログラムであって、
コンピュータに、請求項１〜９のいずれか一項に記載の方法の各ステップを実行させる、前記プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般に、高速実行を達成するコンピュータ・コードの最適化に関し、特に、コードのコンパイル及びリンクに続くオブジェクト・コードの最適化に関する。
【０００２】
【従来の技術】
ポストリンク・コード最適化プログラムは、一般に、静的にリンクされたライブラリ・コードを含む実行可能コード全体に渡る、全体的な分析を実行する。実行可能コードは再コンパイルまたは再リンクされないので、ポストリンク最適化プログラムは、コンパイラ及びリンカ規定を保守する必要がない。従って、ポストリンク最適化プログラムは、コンパイル単位に渡って、最適化コンパイラ（optimizing compiler）では使用できない積極的な最適化を実行することができる。
【０００３】
同時に、ポストリンク最適化プログラムは、コンパイル時の最適化において遭遇する問題を扱わねばならない。最適化コンパイラは高水準言語記述形式の入力に作用し、これは一般に、セマンティックスが明確に定義されたソース・コードである。それに対して、静的ポストリンク最適化ツールは、入力として、低水準実行可能命令（オブジェクト・コード）を受け取る。ポストリンク最適化プログラムは最初に、オブジェクト・コードに含まれるデータ及び命令を識別するために、オブジェクト・コードのディスアセンブルを試行しなければならない。ディスアセンブル後であっても、ポストリンク最適化プログラムに与えられる実行可能コードのセマンティックスは、以下の理由から、部分的にしか知られていない。すなわち、
１）実行可能オブジェクト内のコード命令及びデータが混ざり合い、ときとして、両者間の区別を不可能にする。一般に最適化プログラムが、データまたはコード命令のいずれかに明確に分類できないコード域が存在する。本出願の状況では、これらのコード域は"未分類コード域"（non-classified code area）と呼ばれる。
２）コード命令を含むことが知られている完全に分類されたコード域であっても、プログラムのセマンティックスは常に決定できる訳ではない。機械語命令は、データ情報またはメモリ位置のいずれかを含むレジスタに作用する。従って、最適化プログラムは、所与の命令が純粋なデータ計算を実行するか否か、或いは所与の命令がデータを検索または記憶するために、またはプログラム・コード内の制御転送を実行するために、後にプログラム内で使用されるアドレスを計算するか否かに関して不確かである。
３）データ要素、及びそれらのタイプに当たるアレイ、構造またはスカラなどは、Ｃ、Ｃ＋＋またはパスカルなどの、高水準言語内でのみ識別可能である。ポストリンク・コードでは、これらの要素が任意のデータ域として現れ、それらの参照が任意のアドレスとして扱われる。従って、ポストリンク・レベルでは、データ要素の参照が完全に解析されない。
【０００４】
これらの要因により、プログラムのコード・セマンティックスをポストリンク・コードから完全に抽出することはできず、プログラムにより使用されるデータとコード要素との間の幾つかの依存性が、不確かのままとなる。
【０００５】
Haberらは、彼らの論文"Reliable Post-Link Optimizations Based on Partial Information"、Proceedings of Feedback Directed and Dynamic Optimizations Workshop 3 (Monterey、California、December、2000)、Pages 91-100で、これらの問題を扱うアプローチについて述べている。最初に、最適化されるプログラムが、基本ブロックにディスアセンブルされる。これは、プログラム内で解析される全ての制御フロー・パスを、増分的に追跡することにより行われる。基本ブロックがコード、データ、または未分類（完全に分析されない）としてマークされる。コード・ブロックは更に、それらの制御フロー属性に従いフラグを立てられる。プログラムの部分的に分析されたエリアが、未分類ブロックを含むように区切られ、残りのプログラムを、これらのブロックが最適化に課する制限から解放する。部分的に分析されたエリアは、それらが内部的に最適化されなくても、まとめて安全に再配置され、全体としてコードの再順序化及び最適化を可能にする。
【０００６】
ポストリンク・コード最適化及び再構成の別の面が、Henisらによる"Feedback Based Post-Link Optimization for Large Subsystems"、Second Workshop on Feedback Directed Optimization (Haifa、Israel、November、1999)、pages 13-20、或いはSchmidtらによる"Profile-Directed Restructuring of Operating System Code"、IBM Systems Journal 37:2 (1998)、pages 270-297で述べられている。
【０００７】
【発明が解決しようとする課題】
特定のレジスタを使用する関数がプログラムの実行中に読出されるとき、一般に関数が実行を開始する前に、これらのレジスタの内容を記憶し（メモリに保管する）、この関数が復帰するとき、レジスタ内容を復元することが必要である。この目的のためにコンパイラは一般に、適切なストア命令を、エピローグ内の対応するリストア命令と一緒に、コンパイル済みコード内のその関数のプロローグに追加する。しかしながら、関数の特定の呼び出しでは、これらのストア／リストア命令の幾つかが余計となる。例えば、関数呼び出し後にレジスタが"kill"される場合（すなわち、レジスタ内の値が再度使用される前に上書きされる）、レジスタ内容を記憶し復元する目的は無くなる。最新の高速プロセッサではメモリ・アクセスがボトルネックとなるので、これらの余計なストア操作及びリストア操作を除去すれば、プログラム実行時間を大幅に低減することができる。
【０００８】
Martinらは、"Exploiting Dead Value Information"（Proceedings of Micro-30発行）で、デッド（dead）レジスタの内容の記憶及び復元の排除にもとづく、コンパイラ最適化の方法について述べている。レジスタの将来の使用に関する表明を提供するデッド値情報が、コンパイル時に計算される。著者は、この情報がプロセッサに伝達されるように、プロセッサ命令セット・アーキテクチャを拡張することを提案している。このハードウェア特殊化が無いと、プロシージャ呼び出し時及び復帰時に、一部のストア操作及びリストア操作を排除する際、標準ＲＩＳＣ呼び出し規定により、依然として、デッド値情報のサブセットがプロセッサにより推論され使用されることになる。
【０００９】
【課題を解決するための手段】
本発明の好適な実施例は、プログラム実行の最適化を目的とする、余計なストア命令及びリストア命令のポストリンク除去のための方法を提供する。Martinらにより述べられる方法などの、コンパイラ・ベースの方法と異なり、ポストリンク最適化は、デッド・レジスタがコンパイラ境界を横断して識別されることを可能にする。従って本発明の方法は、一般に最適化単位の範囲が制限されるコンパイラ最適化と異なり、実行可能コード全体を統一して扱うことができるので、グローバル・プログラム最適化を可能にする。
【００１０】
更に、コンパイラの最適化はリンク規定により拘束されるのに対して、ポストリンク最適化プログラムはこれらの規定を無視し、不要なストア命令及びリストア命令を除去することができる。従って本発明の方法は、コンパイル時ツールだけが使用される場合に比較して、不要なメモリ操作をより十分に排除するために使用される。更にこれらの方法は、例えばレガシー・オブジェクト・コードや、静的にリンクされたオブジェクト・コード・ライブラリが、実行可能コード内に組み込まれる場合のように、ソース・コードがコンパイル時の最適化のために使用不能な場合であっても、コード最適化のために使用される。
【００１１】
本発明の好適な実施例では、ポストリンク最適化プログラムがポストリンク・オブジェクト・コードをディスアセンブルし、ディスアセンブルされた該コード内で呼び出される関数を識別する。既知の最適化方法の場合のように、関数の制御フロー・グラフ全体を分析する必要はなく、それらの構成命令を決定するだけでよい。各々の関数は一般にプロローグとエピローグを有し、これらは、その関数により使用されるレジスタに関連するストア命令及びリストア命令を含む。これらのレジスタは、ここでは不揮発性レジスタと呼びばれる。最適化プログラムはディスアセンブルされたコードを分析し、その関数の呼び出しを突き止め、次に各関数呼び出しに続く命令を調査し、その関数が復帰した後に、不揮発性レジスタのいずれかがkillされるか否かを判断する。killされる場合、最適化プログラムは、killされるレジスタに関する関数プロローグ及びエピローグ内のストア命令及びリストア命令が、その関数のこの特定の呼び出しにおいて（また恐らく他の呼び出しにおいても、）必要でないと判断する。次に、最適化プログラムは、その関数がこの呼び出しにより呼び出されるときに、その関数から少なくとも不要なストア命令と、好適にはリストア命令も削除するように、ポストリンク・コードを変更する。
【００１２】
本発明の幾つかの好適な実施例では、最適化プログラムがポストリンク・コード内で、所与の関数の複数の呼び出しを識別及び分析し、その関数の特定の呼び出しに続いて、どの不揮発性レジスタがkillされるかを判断する。最適化プログラムは次に、killされる全ての不揮発性レジスタに関連するストア命令及びリストア命令が削除されるように、その関数の最適化バージョンを作成する。ある不揮発性レジスタがkillされる各関数呼び出しに対して、最適化プログラムは、その関数の最適化バージョンを呼び出すそれぞれのラッパ・コードを作成し、その関数呼び出しを、適切なラッパ・コードへの無条件分岐により置換する。ラッパ・コードは一般に、最適化関数の呼び出しに先行して、特定の関数呼び出しに続きkillされることのないレジスタの内容を記憶する１つ以上のストア命令を含み、更に、最適化関数に続く対応するリストア命令を含む。換言すると、ラッパは、最適化関数のプロローグ及びエピローグから削除された、一部のストア／リストア命令を置換するが、それらはその関数のそれぞれの特定の呼び出しにおいて必要とされるものに限られる。
【００１３】
ラッパ・コード及び最適化関数は、好適には、オリジナル・ポストリンク・コードの終わりに追加される。従って、この段階では、オリジナル関数呼び出しをラッパ・コードへの分岐命令により置換する以外は、コード本体の変更は行われない。その結果、オリジナル関数に代わる最適化関数の使用は、完全には分析できないオリジナル・コードの一部内に存在する参照へは影響せず、それらが有効に維持されるという意味で、全く安全である。最適化コードは一般に、オリジナル・ポストリンク・コードよりも長いが、コード矯正（code straightening）などの既知の追加の最適化ステップが、その後コードに適用される。
【００１４】
或いは、ストア命令が、前述のように分析される関数のプロローグ（または関数の最適化バージョン）内で都合良く順序付けられる場合、関数呼び出しを指定変更することにより、単に不要なストア操作をスキップするように、ポストリンク・コードが変更される。当業者には明らかであろう、コードを変更する他の方法についても、本発明の範囲に含まれるものとみなされる。
【００１５】
従って、本発明の好適な実施例によれば、コード最適化のための方法が提供され、この方法は、コンパイルされ且つリンクされたオブジェクト・コードをディスアセンブルするステップと、ディスアセンブルされた前記コード内で、レジスタに関連するストア命令及びリストア命令を含む関数の複数の呼び出しを識別するステップと、ディスアセンブルされた前記コードを分析し、前記レジスタをkillする命令が後に続く前記関数の前記呼び出しの一つを突き止めるステップと、前記関数が、突き止められた前記呼び出しにより呼び出されるとき、前記関数から前記ストア命令を削除するように、前記関数に対応する前記コードを変更するステップとを含み、
前記コードを変更するステップが、前記ストア命令が削除された前記関数の最適化バージョンを作成するように、前記関数に対応する前記コードの一部を前記コードの終わりに複製するステップをさらに含む。
【００１６】
好適には、前記コードを変更するステップが、前記関数が前記呼び出しの前記１つにより呼び出されるとき、前記関数から前記リストア命令を削除するように、前記コードを変更するステップを含む。
【００１７】
好適には、前記呼び出しの前記１つを指定変更するステップが、複数の前記呼び出しを前記関数の前記最適化バージョンの前記アドレスに指定変更するステップを含む。
【００１８】
好適には、前記関数が複数のレジスタに関連するストア命令及びリストア命令を含み、指定変更される前記複数の呼び出しの各々が、前記複数のレジスタの少なくとも１つをkillするそれぞれの命令が後に続き、前記コードの一部を前記コードの終わりに複製するステップが、前記関数の前記最適化バージョンから、指定変更された前記呼び出しに続きkillされる全てのレジスタに関連する、前記ストア命令及びリストア命令を削除するステップを含む。
【００１９】
好適には、前記コードを変更するステップが、前記関数の少なくとも１つの他の呼び出しに対して、ラッパ・コードを作成するステップを含み、前記ラッパ・コードが、前記関数の前記最適化バージョンの呼び出しを含み、該呼び出しが、前記レジスタに関連するストア命令により先行され、前記レジスタに関連するリストア命令が後に続き、前記コードを変更するステップが、前記関数の少なくとも１つの他の呼び出しを前記ラッパ・コードに指定変更するステップを含む。
【００２０】
好適には、前記関数の少なくとも１つの他の呼び出しをラッパ・コードに指定変更するステップが、前記関数の少なくとも１つの他の呼び出しを、前記ラッパ・コードへの分岐命令により置換するステップを含む。
【００２１】
好適には、前記ラッパ・コードを作成するステップが、指定変更される異なる呼び出しに対して、複数のそれぞれのラッパ・コードを作成するステップを含み、前記複数の呼び出しを指定変更するステップが、異なる前記呼び出しをそれぞれの前記ラッパ・コードに指定変更するステップを含む。
【００２２】
好適には、ディスアセンブルされた前記コードが、最後の命令で終わる命令の固定シーケンスを含み、前記コードの一部を置換するステップが、複製された前記コードを、前記固定シーケンスを変更することなく、前記最後の命令の後に追加するステップを含む。
【００２３】
更に、本発明の好適な実施例によれば、コード最適化のための装置が提供され、この装置は、コンパイルされ且つリンクされたオブジェクト・コードをディスアセンブルし、ディスアセンブルされた前記コード内で、レジスタに関連するストア命令及びリストア命令を含む関数を識別し、ディスアセンブルされた前記コードを分析し、前記レジスタをkillする命令が後に続く前記関数の前記呼び出しの一つを突き止め、ここで前記関数の少なくとも１つの他の呼び出しはレジスタをkillする命令が後に続かず、前記関数が少なくとも１つの他の呼び出しにより呼び出されるとき前記ストア命令の実行を削除せず、前記関数が前記呼び出しの前記１つにより呼び出されるとき前記関数から前記ストア命令の実行を削除するように前記関数に対応する前記コードを変更し、ここで前記コードを変更することが、前記ストア命令が削除された前記関数の最適化バージョンを作成するように、前記関数に対応する前記コードの一部を前記コードの終わりに複製する。
【００２４】
更に、本発明の好適な実施例によれば、コード最適化のためのプログラムが提供され、前記命令がコンピュータにより呼び出され、前記コンピュータに、コンパイルされ且つリンクされたオブジェクト・コードをディスアセンブルするステップと、ディスアセンブルされた前記コード内で、レジスタに関連するストア命令及びリストア命令を含む関数の複数の呼び出しを識別するステップと、ディスアセンブルされた前記コードを分析し、前記レジスタをkillする命令が後に続く前記関数の前記呼び出しの一つを突き止めるステップであって、前記関数の少なくとも１つの他の呼び出しはレジスタをkillする命令が後に続かない、前記突き止めるステップと、前記関数が少なくとも１つの他の呼び出しにより呼び出されるとき前記ストア命令の実行を削除せず、前記関数が前記呼び出しの前記１つにより呼び出されるとき前記関数から前記ストア命令の実行を削除するように前記関数に対応する前記コードを変更するステップとを実行させる。ここで、前記コードを変更するステップが、前記ストア命令が削除された前記関数の最適化バージョンを作成するように、前記関数に対応する前記コードの一部を前記コードの終わりに複製するステップをさらに含む。
【００２５】
【発明の実施の形態】
図１は、本発明の好適な実施例に従い、コンピュータ・プログラム・コードを処理するシステム２０を示すブロック図である。システム２０は好適には汎用コンピュータ・プロセッサを含み、これは後述の関数を実行するようにプログラムされる。プロセッサはこれらの関数を、この目的のために供給されるソフトウェアの制御の下で実行する。ソフトウェアはネットワークを介して、プロセッサに電子形式でダウンロードされるか、或いはＣＤ−ＲＯＭなどの有形媒体上に提供される。
【００２６】
システム２０は一般に、プログラマにより用意されたソース・コードを受信する。周知のように、コンパイラ２２がソース・コードをコンパイルして、オブジェクト・コードを生成し、リンカ２４がコンパイル済みのコードをライブラリ・コードとリンクする。リンクされたオブジェクト・コードが最適化プログラム２６に供給され、以下で詳述するように、これがコードを分析し、冗長なストア／リストア命令を削除するように変更する。次に同様に周知のように、最適化されたコードがランタイム・モジュール２８により実行される。単純化のために、これら全ての関数２２乃至２８は、システム２０内で実行されるように示されるが、これらは分離され、異なるコンピュータ上で実行されてもよい。従って、最適化プログラム２６は本発明にとって重要な要素であり、システム２０の外部にある別のソースからポストリンク・コードを受け取り、最適化されたコードを別のコンピュータに受け渡して実行する。
【００２７】
図２は、本発明の好適な実施例に従い、ポストリンク・コードを最適化するために、最適化プログラム２６により実行される方法を示すフローチャートである。ポストリンク・コードは、ディスアセンブル・ステップ３０においてディスアセンブルされ、コード内の命令が識別される。既知の任意の好適な方法が、この目的のために使用される。好適には、例えば前述のHaberら及びHenisらによる論文で述べられるように、増分ディスアセンブル方法が、コードをその基本ブロックにディスアセンブルするために使用される。この目的のために、実行可能コード内の命令のアドレスが、様々なソースから抽出されて、"潜在的なエントリ・ポイント"のリストが形成される。ソースは一般に、プログラム／ＤＬＬエントリ・ポイント、（関数及びラベルの）記号テーブル、及び再配置テーブル（これを通じて、コードを指し示すポインタがアクセスされる）を含む。最適化プログラムはこれらのエントリ・ポイントから開始して、制御フローに従いプログラムを横断し、全ての可能な制御フロー・パスを解析し、リストに例えばＪＵＭＰやＣＡＬＬ命令のターゲットなどの、追加の潜在的なエントリ・ポイントの新たに発見されたアドレスを追加する。
【００２８】
このようにプログラムの制御フローに従う割合が、コードの大きな割合を占める。増分ディスアセンブルにより直接発見可能でない基本ブロックは、"未分類コード"とマークされる。これらのブロックは一般に、ランタイム時にだけ解析されるターゲット・レジスタにより、ジャンプを介して到達されるコードから成る。ときに、Henisらにより述べられるように、コード及び動的ランタイム分析のツールを用いて、これらのブロックを分類することが可能であるが、この方法の説明は本願の範囲を超えるため、ここでは説明を省略する。
【００２９】
増分ディスアセンブルプロセスの終わりに、オリジナル・プログラムのコード・セクション全体が、分類済みまたは未分類の基本ブロックにディスアセンブルされる。分類済みブロックはフラグによりマークされ、フラグがそれらをコードまたはデータ（例えば分岐テーブル・データ）として特徴付け、例えばFallthrough、Continue、Call、Return、Jumpなどの、コード・ブロックの制御フロー属性を識別する。特に、Callフラグ及びReturnフラグは、関数識別ステップ３２において、コード内の関数及び関数呼び出しを識別するために使用される。
【００３０】
一般に、ステップ３２で識別される関数の各々は、プロローグ及びエピローグを有し、その関数により使用される特定のレジスタの内容を記憶及び復元する命令を含む。本願の状況では、これらのレジスタは"不揮発性レジスタ"と称される。各関数における不揮発性レジスタの処理が、分析ステップ３４で分析され、これらのどのレジスタがその関数の各呼び出しに続き、ランライム時に再度参照される前にkillされるかを判断する。好適には、レジスタＲｘが、プログラム・コード内のその関数の呼び出し命令に続く、所与のアドレスaddrにおいてkillされるか否かを判断するために、そのアドレスに続くディスアセンブルコードの制御フローが、Ｒｘをkillする命令に達するまでトレースされる。この場合、Ｒｘはアドレスaddrにおいてkillされるとみなされる。一方、トレースがＲｘを使用する命令に達する場合、または例えば条件付き分岐命令や、レジスタを介する分岐、或いは未分類コード域などに達し、トレースが失敗する場合には、Ｒｘはアドレスaddrでkillされるとみなされない。
【００３１】
各関数ｆに対して、ステップ３４の分析は、好適には次の情報を決定するために使用される。すなわち、
ａ）ＲＥＧ（ｆ）：関数ｆ内で使用される全ての不揮発性レジスタのセット。
ｂ）ＫＲＥＧ（addr，ｆ）：アドレスaddrでkillされるＲＥＧ（ｆ）内の全てのレジスタのサブセット。但し、addrは前述のように、関数ｆの呼び出し命令に続くアドレス。
ｃ）ＯＰＴ（ｆ）：全てのＫＲＥＧ（addri，ｆ）の和集合内の不揮発性レジスタのセット。但し、addriは関数ｆの呼び出し命令に続くアドレス（すなわち、全体プログラム内で、関数ｆの呼び出し命令の１つの後でkillされる、その関数ｆ内の不揮発性レジスタのセット）。
【００３２】
ＯＰＴ（ｆ）が空でないとき、プログラム内に、関数ｆの特定の不揮発性レジスタが続きkillされる１つ以上の呼び出し命令が存在する。従って、プログラム・コードは、コード変更ステップ３６において、killされるレジスタに対する、冗長なストア命令及びリストア命令を削除するように変更される。この変更は好適には、後述のように、冗長なストア／リストア命令無しに、関数ｆのコードを複製し、次に、必要なストア命令及びリストア命令を"ラッパ・コード"内に追加することにより実行される。或いは、コード変更の他の方法が同じ目的のために使用されてもよい。
【００３３】
図３は、本発明の好適な実施例に従うコード変更ステップ３６の詳細を示すフローチャートである。コード変更は、ＯＰＴ（ｆ）が空でないプログラム内の各関数ｆに対して実行される。最初に複製ステップ４０で、関数ｆのコードが、好適には既存のプログラム・コードの終わりにおいて複製される。この新たに複製された関数をｆ＿ｏｐｔと命名する。ＯＰＴ（ｆ）セット内の各レジスタＲｘに対して、削除ステップ４２で、ｆ＿ｏｐｔのプロローグ内のＲｘのストア命令、及びｆ＿ｏｐｔのエピローグ内のＲｘのリストア命令が削除される。
【００３４】
プログラム内の関数ｆの各呼び出し命令に対して、ラッパ・ステップ４４で、ラッパ・コードが生成される。このステップの目的上、addrを、関数ｆの呼び出し命令に続くコード・アドレスとする。ＯＰＴ（ｆ）−ＫＲＥＧ（addr，ｆ）が空でないと仮定すると、ラッパ・コードは次の命令を含む。すなわち、
store R1
store R2
・・・
store Rn
call f_opt
restore Rn
restore Rn-1
・・・
restore R1
branch addr
【００３５】
ここで｛Ｒ１，Ｒ２，．．，Ｒｎ｝＝ＯＰＴ（ｆ）−ＫＲＥＧ（addr，ｆ）である。オリジナル・プログラム内のｆの呼び出し命令は、分岐ステップ４６において、前記のラッパ・コードへの無条件分岐により置換される。ＯＰＴ（ｆ）−ＫＲＥＧ（addr，ｆ）が空の場合、関数ｆの呼び出し命令を、ｆ＿ｏｐｔの直接呼び出しにより置換すればよい。他方、ＫＲＥＧ（addr，ｆ）が空の場合、オリジナル・プログラム内の関数ｆの呼び出し命令は、好適には無変更のままである。
【００３６】
ステップ４０で関数ｆのコードを複製する理由は、プログラムの正当性を保持するためである。なぜなら、プログラムは関数ｆの他の検出されていない呼び出し命令を含み得るからである。これらの呼び出し命令はレジスタを介して、またはライブラリや、ポストリンク・コードが与えられていない他の実行可能コードなどの、他のコード・モジュールから生成され得るので、静的ポストリンク分析により呼び出しを確実に検出することは不可能である。関数ｆの不揮発性レジスタの１つのkillが後に続く、検出された全ての呼び出し命令が、前述のように、最適化関数ｆ＿ｏｐｔを呼び出すために指定変更される。不揮発性レジスタのkillが後に続かない呼び出し命令は、前述のように、好適には変更されずに維持される。同様に未検出の呼び出し命令は、オリジナル非最適化関数ｆへの分岐を続け、従って以前のプログラム・セマンティックスを維持する。
【００３７】
下記の表１は、ディスアセンブルされたポストリンク・コードのサンプルを示し、そこでは関数ｆｏｏの幾つかの呼び出しが発生する。この例では、関数ｆｏｏは次の定義により特徴付けされる。すなわち、
ａ）ＲＥＧ（ｆｏｏ）＝｛Ｒ２７，Ｒ２８，Ｒ２９｝
ｂ）ＫＲＥＧ（Ｌ２，ｆｏｏ）＝｛Ｒ２７｝、
ＫＲＥＧ（Ｌ４，ｆｏｏ）＝｛｝
ＫＲＥＧ（Ｌ４，ｆｏｏ）＝｛Ｒ２８｝
ｃ）ＯＰＴ（ｆｏｏ）＝｛Ｒ２７，Ｒ２８｝
【００３８】
下記の表の左辺は、最適化前のポストリンク・コードを示し、右辺はｆｏｏの２つの呼び出しを適切なラッパ・コードへの分岐により置換した、最適化後のコードを示す。
【表１】
コード比較：
最適化前                          最適化後
プログラム開始                    プログラム開始
・・・                            ・・・
L1: call foo                      L1: branch L7
L2: R27をここでkill               L2: R27をここでkill
・・・                            ・・・
L3: call foo                      L3: call foo
L4: .../*ここではfooの不揮発性*/ L4: .../*ここではfooの不揮発性*/
/*レジスタをkillしない*/          /*レジスタをkillしない*/
・・・                            ・・・
L5: call foo                      L5: branch L8
L6: R28をここでkill               L6: R28をここでkill
・・・                            ・・・
機能foo：                         機能foo：
プロローグ：                      プロローグ：
store R27                         storeR27
store R28                         storeR28
store R29                         storeR29
・・・                            ・・・
エピローグ：                       エピローグ：
・・・                            ・・・
restore R29                       restoreR29
restore R28                       restoreR28
restore R27                       restoreR27
return                            return
・・・                            ・・・
プログラム終了                    L7: store R28 /*ラッパ・コード１*/
call foo_opt/*指定変更呼び出し*/
restore R28
branch L2
L8: store R27 /*ラッパ・コード２*/
call foo_opt/*指定変更呼び出し*/
restore R27
branch L6
・・・
機能foo_opt：
プロローグ：
store R29
/*store R27, R28削除*/
・・・
エピローグ：
restore R29
/*restore R27, R28削除*/
return
・・・
プログラム終了
【００３９】
好適には、前述の最適化を実行後、生成コードにコード矯正（code-straightening）アルゴリズムが適用され、ラッパ・コードへの、及びラッパ・コードからの無条件分岐を削除する。この矯正アルゴリズムは、ポストリンク最適化ツールの分野では既知であり、こうしたツールには、例えばＩＢＭからＡＩＸ（商標）オペレーティング・システムのパフォーマンス・ツール・ボックス（ＰＴＸ）の一部として提供される、ＦＤＰＲ（Feedback Directed Program Restructuring）ツールなどがある。ＰＴＸの詳細については、Haberら、Henisら、及びSchmidtらによる前記論文で述べられている。
【００４０】
前述のような、コード複製及びラッパ・コードの使用は、便利で一般的な解決方法であり、プログラムのパーツが未分類または未知のままであっても、冗長なストア／リストア命令の削除を可能にする。しかしながら、プログラム・コード全体が使用可能で、完全に分析され、従って、コード内のｆの全ての関数呼び出し命令が確実に見いだされるケースが存在する。これらの場合、複製ステップ４０は不要となる。代わりに好適には、関数ｆのプロローグ及びエピローグから、冗長なストア／リストア命令が、対応するＮＯＰ命令により置換される。このとき、ステップ４４で生成されるラッパ・コードは、ｆ＿ｏｐｔではなく、ｆの呼び出しを含む。冗長なストア／リストア命令を単に削除する代わりに、ＮＯＰにより置換することは、関数ｆのプログラム・コード全体を再配置する必要性を排除する。
【００４１】
ｆの所与の関数呼び出し命令において、関数呼び出しに続きkillされる不揮発性レジスタのセットＫＲＥＧ（addr，f）に関するストア命令が、その関数のプロローグ内の最初の連続命令である場合がある。或いは、プログラム・セマンティックスに影響を及ぼすことなく、これらのストア命令がプロローグの先頭に再スケジュールされるかもしれない。こうした場合、ストア命令はｆ＿ｏｐｔ内に（または前述のようにｆが複製されない場合には、ｆ自身内に）取り残される。このとき、ｆ＿ｏｐｔまたはｆの先頭に配置される冗長なストア命令をスキップするように、所与の呼び出し命令のターゲット・アドレスを単に指定変更することにより、冗長なストア命令が回避される。このアプローチは、より短い単純なラッパ・コードの使用を可能にする。
【００４２】
同様に、ｆのkillされる全ての不揮発性レジスタＯＰＴ（ｆ）に関するストア命令が、関数のプロローグ内の最初の連続命令であるか、或いはこのように再スケジュールされる場合が発生し得る。こうした場合にも、関数ｆのコードを複製することなく、本発明の最適化が実行される。代わりに、ｆ内のストア命令がプロローグの先頭の所定位置に取り残され、関数の呼び出し命令が、適宜ストア命令をスキップするように指定変更される。この場合、冗長なリストア命令のあるものは依然実行されるかもしれない。
【００４３】
本発明の別の実施例は、ポストリンク時に新たなスタック・フレームを増加または作成することが可能な場合において使用される。この実施例では、ＯＰＴ（ｆ）内のレジスタに関連するｆ内の全てのストア命令及びリストア命令が、ＮＯＰ命令により置換され、ｆがｆ＿ｏｐｔとリネームされる。このとき前述のように、関数ｆに関して解析された全ての呼び出し命令が、killされないレジスタを記憶及び復元する適切なラッパ・コードの呼び出しにより置換される。関数ｆの任意の未解析の呼び出し命令を処理するために、次のように、新たな関数ｆがプログラム・コードに追加される。すなわち、
store R1
store R2
・・・
store Rn
call f_opt
restore Rn
restore Rn-1
・・・
restore R1
return
【００４４】
ここで再度、｛Ｒ１，Ｒ２，...，Ｒｎ｝は、ＯＰＴ（ｆ）内の不揮発性レジスタのセットである。
【００４５】
ｆの新たなスタック・フレームを増加または作成することにより、オリジナル関数ｆの全ての参照がこの新たな関数に指定変更されるように、ポストリンク・プログラムの再配置情報が更新される。このように、ｆに対する全ての未解析の呼び出し命令が自動的に新たなｆに分岐するようになり、プログラムのオリジナル・セマンティックスが維持される。
【００４６】
前述の好適な実施例は全て、安全性のために、オリジナル・ポストリンク・コードが最適化の間に拡張または短縮されないことを前提とする。しかしながら、本発明の原理は、コードの削除、追加及び移動を可能にする環境においても、適用可能である。この環境では代わりに、要求されるストア命令及びリストア命令を、ｆの対応する呼び出し命令の前後に直接挿入することにより、ラッパ・コードの必要性が回避される。同様な理由で、前述のように、ストア命令及びリストア命令をＮＯＰ命令により置換することにより、不要な命令が単にコードから削除される。
【００４７】
前述の好適な実施例は、例証として引用されたもので、本発明はここで特に示され、述べられた実施例に制限されるものではないことが理解されよう。本発明の範囲は、前述の様々なフィーチャの組み合わせ及び一部の組み合わせを含み、同様に本開示を参照することで、当業者に明らかになろうこれらの変形及び変更も含むものである。
【００４８】
【図面の簡単な説明】
【図１】  本発明の好適な実施例に従い、コンピュータ・プログラム・コードを処理するシステムを示すブロック図である。
【図２】  本発明の好適な実施例に従い、ポストリンク・コードを最適化する方法を示すフローチャートである。
【図３】  本発明の好適な実施例に従い、ポストリンク・コード内の冗長なストア命令及びリストア命令を削除する方法を示すフローチャートである。
【００４９】
【符号の説明】
２０  システム
２２  コンパイラ
２４  リンカ
２６  最適化プログラム
２８  ランタイム・モジュール
【図１】
0004181326.tif 000002
【図２】
0004181326.tif 000003
【図３】
0004181326.tif 000004