(57)【要約】【課題】無駄にスピルコードを発行しないようにスピルコード発行位置を特定する。【解決手段】各基本ブロックの実行回数に関するデータを取得するステップと、レジスタに格納された特定の変数のデータをメモリに待避しなければならない範囲であるファットスポットを特定するステップと、特定の変数の定義ポイントと特定の変数への参照ポイントとファットスポットのデータと各基本ブロックの実行回数に関するデータとに基づき、特定の変数に関するスピルコードの実行回数が最小となる位置を特定するステップとを含む。このように各基本ブロックの実行回数（実測回数又は予測回数）に基づき、スピルコードの実行回数が最小となる位置を特定することにより、無駄なスピルコード発行を回避し、スピルコードの実行回数も最適化される。【選択図】  図１
2004227025.tif 000002
【特許請求の範囲】
【請求項１】
ソースプログラムをコンパイルする際にコンピュータにスピルコードの発行位置を特定させるスピルコード発行位置特定プログラムであって、
各基本ブロックの実行回数に関するデータを取得し、当該各基本ブロックの実行回数に関するデータを記憶装置に格納する実行回数取得機能と、
レジスタに格納された特定の変数のデータをメモリに待避しなければならない範囲であるファットスポットを特定し、当該ファットスポットのデータを記憶装置に格納するファットスポット特定機能と、
前記特定の変数の定義ポイントと前記特定の変数への参照ポイントと前記ファットスポットのデータと前記各基本ブロックの実行回数に関するデータとに基づき、前記特定の変数に関するスピルコードの実行回数が最小となる位置を特定する位置特定機能と、
をコンピュータに実現させるためのスピルコード発行位置特定プログラム。
【請求項２】
前記位置特定機能が、
前記特定の変数の定義ポイントに対応するノードと前記特定の変数への参照ポイントに対応するノードと制御の節目のポイントに対応するノードとを少なくとも含み、前記定義ポイント及び前記参照ポイントに対応するノードは第１の状態に設定され、前記ファットスポットに対応するノードは第２の状態に設定された状態グラフを生成し、記憶装置に格納する状態グラフ生成機能と、
前記各基本ブロックの実行回数に関するデータに基づき決定された優先順位に従って前記状態グラフにおいてノード間を接続するエッジを選択し、当該エッジに接続されたノードの状態を所定のルールに従って状態が未設定のノードに伝播させる機能と、
前記状態グラフにおいて両端のノードで設定された状態が異なるエッジを抽出する機能と、
を含む請求項１記載のスピルコード発行位置特定プログラム。
【請求項３】
前記ファットスポット特定機能が、
使用可能なレジスタの個数のデータと特定のレジスタに格納されたデータを破壊する命令に関するデータとの少なくともいずれかを参照する機能
を含むことを特徴とする請求項１記載のスピルコード発行位置特定プログラム。
【請求項４】
ソースプログラムをコンパイルする際にコンピュータにスピルコードの発行位置を特定させるスピルコード発行位置特定プログラムであって、
レジスタに格納された特定の変数のデータをメモリに待避しなければならない範囲であるファットスポットを特定するファットスポット特定機能と、
前記特定の変数の定義ポイントに対応するノードと前記特定の変数への参照ポイントに対応するノードと制御の節目のポイントに対応するノードとを少なくとも含み、前記定義ポイント及び前記参照ポイントに対応するノードは第１の状態に設定され、前記ファットスポットに対応するノードは第２の状態に設定された状態グラフを生成し、記憶装置に格納する状態グラフ生成機能と、
所定の優先順位に基づき前記状態グラフにおいてノード間を接続するエッジを選択し、当該エッジに接続されたノードの状態を所定のルールに従って状態が未設定のノードに伝播させる状態伝播機能と、
前記状態グラフにおいて両端のノードで設定された状態が異なるエッジを抽出する機能と、
をコンピュータに実現させるためのスピルコード発行位置特定プログラム。
【請求項５】
前記状態グラフの各エッジの実行回数に関するデータを取得する実行回数取得機能
をコンピュータにさらに実現させ、
前記実行回数の多い順に前記所定の優先順位が決定される
ことを特徴とする請求項４記載のスピルコード発行位置特定プログラム。
【請求項６】
前記特定の変数の生存範囲を特定する機能
をコンピュータにさらに実現させ、
前記状態グラフ生成機能が、
前記特定の変数の生存範囲のデータを参照して前記状態グラフにおけるノードの生成の是非を判断する機能
を含むことを特徴とする請求項４記載のスピルコード発行位置特定プログラム。
【請求項７】
スピルコードの発行位置を特定するコンパイル装置であって、
各基本ブロックの実行回数に関するデータを取得し、当該各基本ブロックの実行回数に関するデータを記憶装置に格納する手段と、
レジスタに格納された特定の変数のデータをメモリに待避しなければならない範囲であるファットスポットを特定し、当該ファットスポットのデータを記憶装置に格納する手段と、
前記特定の変数の定義ポイントと前記特定の変数への参照ポイントと前記ファットスポットのデータと前記各基本ブロックの実行回数に関するデータとに基づき、前記特定の変数に関するスピルコードの実行回数が最小となる位置を特定する手段と、
を有するコンパイル装置。
【請求項８】
スピルコードの発行位置を特定するコンパイル装置であって、
レジスタに格納された特定の変数のデータをメモリに待避しなければならない範囲であるファットスポットを特定する手段と、
前記特定の変数の定義ポイントに対応するノードと前記特定の変数への参照ポイントに対応するノードと制御の節目のポイントに対応するノードとを少なくとも含み、前記定義ポイント及び前記参照ポイントに対応するノードは第１の状態に設定され、前記ファットスポットに対応するノードは第２の状態に設定された状態グラフを生成し、記憶装置に格納する手段と、
所定の優先順位に基づき前記状態グラフにおいてノード間を接続するエッジを選択し、当該エッジに接続されたノードの状態を所定のルールに従って状態が未設定のノードに伝播させる手段と、
前記状態グラフにおいて両端のノードで設定された状態が異なるエッジを抽出する手段と、
を有するコンパイル装置。
【請求項９】
ソースプログラムをコンパイルする際にスピルコードの発行位置を特定する方法であって、
各基本ブロックの実行回数に関するデータを取得し、当該各基本ブロックの実行回数に関するデータを記憶装置に格納する実行回数取得ステップと、
レジスタに格納された特定の変数のデータをメモリに待避しなければならない範囲であるファットスポットを特定し、当該ファットスポットのデータを記憶装置に格納するファットスポット特定ステップと、
前記特定の変数の定義ポイントと前記特定の変数への参照ポイントと前記ファットスポットのデータと前記各基本ブロックの実行回数に関するデータとに基づき、前記特定の変数に関するスピルコードの実行回数が最小となる位置を特定する位置特定ステップと、
を含むスピルコード発行位置特定方法。
【請求項１０】
ソースプログラムをコンパイルする際にスピルコードの発行位置を特定する方法であって、
レジスタに格納された特定の変数のデータをメモリに待避しなければならない範囲であるファットスポットを特定するファットスポット特定ステップと、
前記特定の変数の定義ポイントに対応するノードと前記特定の変数への参照ポイントに対応するノードと制御の節目のポイントに対応するノードとを少なくとも含み、前記定義ポイント及び前記参照ポイントに対応するノードは第１の状態に設定され、前記ファットスポットに対応するノードは第２の状態に設定された状態グラフを生成し、記憶装置に格納する状態グラフ生成ステップと、
所定の優先順位に基づき前記状態グラフにおいてノード間を接続するエッジを選択し、当該エッジに接続されたノードの状態を所定のルールに従って状態が未設定のノードに伝播させる状態伝播ステップと、
前記状態グラフにおいて両端のノードで設定された状態が異なるエッジを抽出するステップと、
を含むスピルコード発行位置特定方法。
【発明の詳細な説明】
【０００１】
【発明が属する技術分野】
本発明は、コンパイラに関し、より詳しくはスピルコード発行位置の特定技術に関する。
【０００２】
【従来の技術】
最初に以下の説明において用いる用語の説明をしておく。
・スピルとは、レジスタの値をメモリ上に待避させ、一時的にレジスタを開放することである。
・スピルコードとは、スピルするために発行される命令をいう。なお、レジスタの値をメモリに待避するストア命令と、待避した内容をレジスタに復元するロード命令とを含む。
・ファットスポットとは、レジスタが足りない、又はハードウエア上の制限などによりレジスタをメモリ上に待避させておかなければならない範囲をいう。これは、レジスタ又は変数に特有なものであり、個々のレジスタが異なるファットスポットを有する可能性がある。
・生存範囲（ライブレンジ）とは、変数が定義されてから、最後に参照されるまでの区間をいう。
【０００３】
従来の技術では、スピルコードを、待避したいレジスタの内容が定義された直後及びそのレジスタが参照される直前に発行していた。そのままではスピルコードの数が多くなってしまって性能に影響するため、その後の最適化で統合、あるいは無駄な命令を除去することで最適化する方法が用いられていた。こうした最適化の例としては例えば部分冗長性の除去（Ｐａｒｔｉａｌ  Ｒｅｄｕｎｄａｎｃｙ  Ｅｌｉｍｉｎａｔｉｏｎ）などがある。
【０００４】
また他の方法としては、命令スケジューラとレジスタ割り付けとを同時に行い、スピルコードを発行すると同時にスケジューリングし、その際に冗長性を取り除くなどでスピルコードの冗長性を除去していた。
【０００５】
さらに、特開２００１−２９０６５３号公報には、以下のような技術が開示されている。すなわち、メモリへ待避かつメモリから復帰する変数を選定する第１選定ステップと、第１選定ステップで選定された変数と同時に待避可能な変数を選定する第２選定ステップと、第１選定ステップで選定された変数と同時に復帰可能な変数を選定する第３選定ステップと、第２及び第３選定ステップで共に選定された変数を選定する第４選定ステップと、第１選定ステップ及び第４選定ステップで選定された変数を同時に待避する待避命令及び同時に復帰する命令を挿入するステップと、プログラム中の変数をレジスタに割り付ける割付ステップとを含む資源割付方法である。本公報ではスピルすべき変数を選定する部分に特徴がある。
【０００６】
なお、例えば特開平１１−２７２４７３号公報、特開平９−３１１７９１号公報にもスピルコードについて技術が開示されているが、上で述べた従来技術に近い技術しか開示されていない。
【０００７】
【特許文献１】
特開２００１−２９０６５３号
【特許文献２】
特開平１１−２７２４７３号
【特許文献３】
特開平９−３１１７９１号
【０００８】
【発明が解決しようとする課題】
スピルコードを発行してから消去する方法を採用すると、一時的に無駄な命令を発行することになるため中間命令列が肥大化し、また無駄な命令や統合可能な命令を探すことにも計算時間をかけなければならなくなる。
【０００９】
また、命令スケジューラでスケジューリングせずにスピルコードだけを発行するようにすることは従来では困難で、レジスタ割り付けと命令スケジューラとを同時に実行する必要が出てくる。その際、命令スケジューラは一般にターゲットとなる計算機の情報を必要とするため、当該計算機の情報が得られない等の場合には不都合が生ずる。また、マシン依存性が低いスピルコードの冗長性を除去することも不可能である。
【００１０】
よって本発明の目的は、無駄にスピルコードを発行しないようにスピルコード発行位置を特定する技術を提供することである。
【００１１】
また、他の目的は、スピルコードの実行回数を最適化するための技術を提供することである。
【００１２】
さらに他の目的は、必要最低限のマシン依存性を有するスピルコード発行を可能とする技術を提供することである。
【００１３】
【課題を解決するための手段】
本発明の第１の態様に係る、ソースプログラムをコンパイルする際にスピルコードの発行位置を特定する方法は、各基本ブロックの実行回数に関するデータを取得し、当該各基本ブロックの実行回数に関するデータを記憶装置に格納する実行回数取得ステップと、レジスタに格納された特定の変数のデータをメモリに待避しなければならない範囲であるファットスポットを特定し、当該ファットスポットのデータを記憶装置に格納するファットスポット特定ステップと、特定の変数の定義ポイントと特定の変数への参照ポイントとファットスポットのデータと各基本ブロックの実行回数に関するデータとに基づき、特定の変数に関するスピルコードの実行回数が最小となる位置を特定する位置特定ステップと、を含む。
【００１４】
このように各基本ブロックの実行回数（実測回数と予測回数とのいずれか）に基づき、スピルコードの実行回数が最小となる位置を特定することにより、無駄なスピルコード発行を回避し、スピルコードの実行回数も最適化される。
【００１５】
また、上で述べた位置特定ステップが、特定の変数の定義ポイントに対応するノードと特定の変数への参照ポイントに対応するノードと制御の節目のポイントに対応するノードとを少なくとも含み、定義ポイント及び参照ポイントに対応するノードは第１の状態（例えば実施の形態におけるＲ状態（レジスタ（Ｒｅｇｉｓｔｅｒ）に格納されるべき状態））に設定され、ファットスポットに対応するノードは第２の状態（例えばＭ状態（メモリ（Ｍｅｍｏｒｙ）に格納されるべき状態））に設定された状態グラフを生成し、記憶装置に格納する状態グラフ生成ステップと、各基本ブロックの実行回数に関するデータに基づき決定された優先順位に従って状態グラフにおいてノード間を接続するエッジを選択し、当該エッジに接続されたノードの状態を所定のルールに従って状態が未設定のノードに伝播させるステップと、状態グラフにおいて両端のノードで設定された状態が異なるエッジを抽出するステップとを含むようにしてもよい。
【００１６】
このような状態グラフを用いることにより、正確且つ簡単にスピルコードを発行すべき適切な位置を特定できるようになる。
【００１７】
また、上で述べたファットスポット特定ステップが、使用可能なレジスタの個数のデータと特定のレジスタに格納されたデータを破壊する命令に関するデータとの少なくともいずれかを参照するステップを含むようにしてもよい。このように、ファットスポット特定ステップにおいて参照されるデータを限定的にすることにより、マシンに過度に依存するようなコンパイルを回避することができる。
【００１８】
さらに、上で述べた実行回数取得ステップが、各基本ブロックの実行回数をカウントするステップを含むようにしてもよいし、各基本ブロックの実行回数を予測するステップを含むようにしても良い。
【００１９】
本発明の第２の態様に係るスピルコード発行位置特定方法は、レジスタに格納された特定の変数のデータをメモリに待避しなければならない範囲であるファットスポットを特定するファットスポット特定ステップと、特定の変数の定義ポイントに対応するノードと特定の変数への参照ポイントに対応するノードと制御の節目のポイントに対応するノードとを少なくとも含み、定義ポイント及び参照ポイントに対応するノードは第１の状態に設定され、ファットスポットに対応するノードは第２の状態に設定された状態グラフを生成し、記憶装置に格納する状態グラフ生成ステップと、所定の優先順位に基づき状態グラフにおいてノード間を接続するエッジを選択し、当該エッジに接続されたノードの状態を所定のルールに従って状態が未設定のノードに伝播させる状態伝播ステップと、状態グラフにおいて両端のノードで設定された状態が異なるエッジを抽出するステップとを含む。
【００２０】
これによりスピルコードを無駄に発行することは無くなる。また、優先順位の設定に依存して両端のノードの状態が異なるエッジの位置が変化するため、優先順位を適切に設定することにより、スピルコードの発行位置を最適化させることも可能となる。
【００２１】
すなわち、本発明の第２の態様において、状態グラフの各エッジの実行回数に関するデータを取得する実行回数取得ステップをさらに含み、実行回数（実測実行回数又は予測実行回数）の多い順に所定の優先順位が決定されるような構成であってもよい。
【００２２】
また、本発明の第２の態様において、特定の変数の生存範囲を特定するステップをさらに含み、上で述べた状態グラフ生成ステップが、特定の変数の生存範囲のデータを参照して状態グラフにおけるノードの生成の是非を判断するステップを含むようにしてもよい。これにより無駄な処理を除去することが可能となる。
【００２３】
また、上で述べた状態伝播ステップが、選択されたエッジの両端のノードの状態が未設定である場合に、当該選択されたエッジの両端のノードの状態を第３の状態に仮設定するステップと、選択されたエッジの一方のノードの状態が第１又は第２の状態であり且つ他方のノードの状態が未設定と第３の状態とのいずれかである場合に、他方のノードの状態を一方のノードの状態に設定するステップと、上記他方のノードの状態が第３の状態であった場合には、当該他方のノードに接続されている別のノードの状態を一方のノードの状態に設定するステップとを含むようにしてもよい。
【００２４】
なお、上述の方法はプログラム及びコンピュータにて実施することができ、当該プログラムを実行するコンピュータは、コンパイラ装置である。また、このプログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等の記憶媒体又は記憶装置に格納される。また、ネットワークなどを介してデジタル信号として配信される場合もある。尚、中間的な処理結果はメモリに一時保管される。
【００２５】
【発明の実施の形態】
本発明の一実施の形態に係るコンパイラ装置１の機能ブロック図を図１に示す。コンパイラ装置１は、例えばパーソナルコンピュータやワークステーションなどのコンピュータであって、演算処理装置、メモリ、ファイル格納部などを含む。そして、入力ソース・プログラム１０をファイル格納部などから読み込み、出力オブジェクト・プログラム３０を出力して、ファイル格納部などに格納する。コンパイラ２０は、コンパイラ装置１において実行されるプログラムであって、入力ソース・プログラム１０から中間コード２１０を生成するフロントエンド処理部２００と、本発明の実施の形態に係る最適化パスを含む最適化処理を実施する最適化処理部２２０と、最適化処理部２２０の処理結果から出力オブジェクト・プログラム３０を生成するコード生成部２３０とを含む。
【００２６】
フロントエンド処理部２００は、字句解析処理を実施する字句解析部２０１と、構文解析処理を実施する構文解析部２０２と、意味解析処理を実施する意味解析部２０３とを含む。これらは従来技術と同様であるから詳しく述べない。
【００２７】
最適化処理部２２０は、本実施の形態における処理の前処理を実施する前処理部２２１と、各変数についてのファットスポットを特定するファットスポット特定部２２４と、ファットスポット特定部２２４及び状態グラフ処理部２２５により参照されるファットスポットに関するデータを格納するファットスポットデータ格納部２２３と、各変数についてレジスタに保持すべき状態とメモリに保持すべき状態との状態遷移を解析するための状態グラフを処理する状態グラフ処理部２２５と、状態グラフ処理部２２５から参照される実行回数データ格納部２２２と、状態グラフからスピルコードを生成すべき位置を特定しスピルコードを発行するスピルコード生成部２２６とを含む。上でも述べたように、本発明の実施の形態に係る最適化パス以外にも最適化パスが存在しているが、最適化処理部２２０には、本実施の形態に係る最適化パスに関係する処理部等のみ示している。
【００２８】
上で述べた前処理部２２１は、制御フローの解析処理を実施する制御フロー解析部２２１１と、各変数の生存範囲を解析する生存範囲解析部２２１２と、基本ブロックの実行回数を予測したり、実際の実行回数の計数結果を取得して実行回数データ格納部２２２に登録する実行回数設定部２２１３とが含まれる。なお、前処理部２２１については最適化処理部２２０に含まれない場合もあるが、本実施の形態では本実施の形態に係る処理に密接に関係するため最適化処理部２２０に含まれるものとして説明する。
【００２９】
次に図２及び図３を用いて図１に示したコンパイラ装置１の処理フローについて説明する。本実施の形態では、ファットスポットについてのデータの設定入力をユーザから受け付け、ファットスポット・データ格納部２２３に格納する（ステップＳ１）。レジスタに格納されたデータをメモリに待避させるということはスピルコード（ストア及びロード命令）を発行することになるためできるだけ避けたい。しかし、ハードウエア上のレジスタ数が変数の数より少ない場合、及びある命令が特定のレジスタの内容を破壊するため、レジスタに保持できない場合などにおいては、どうしてもスピルコードを発行しなければならない。特定のレジスタ及び当該特定のレジスタの内容を破壊するような命令のデータ、レジスタの総数又は使用可能数等のデータを保持しておかないとファットスポットを判定することができない。本実施の形態ではユーザによりこのようなデータを入力するようにしているが、出力オブジェクト・プログラム３０が実行され得るマシン毎に上記のようなデータを保持するテーブルを用意しておき、ユーザはマシンの選択を行うことにより、ファットスポットについてのデータを特定するようにしても良い。
【００３０】
次に、ユーザの指示に従ってコンパイルを行うソース・プログラム１０をメモリに読み込む（ステップＳ３）。そして、フロントエンド処理部２００の字句解析部２０１、構文解析部２０２及び意味解析部２０３により中間コード２１０を生成し、メモリに格納する（ステップＳ５）。そして、中間コード２０１を用いて、制御フロー解析処理、変数生存範囲解析処理及び実行回数予測処理を含む前処理を前処理部２２１により実行する（ステップＳ７）。制御フロー解析部２２１１は、中間コードを解析して制御フロー図（ＣＦＧ：  Ｃｏｎｔｒｏｌ  Ｆｌｏｗ  Ｇｒａｐｈ）を生成する。変数の状態（レジスタに値が格納されている状態又はメモリに格納されている状態）を決定する上で、プログラムの制御フローを解析する必要がある。このプログラムの制御フロー図を生成する方法は、例えば「コンパイラの構成と最適化」中田育男著、朝倉書店、ＩＳＢＮ：  ４２５４１２１３９３の第１２章に記載された方法を用いることができる。従って、ここでは詳しく説明しない。
【００３１】
また、変数生存範囲解析部２２１２は、ある変数が定義されてから、再定義されるまでの間で最後に参照されるまでの区間である生存範囲を、制御フロー解析部２２１１により生成される制御フロー図を用いて特定する。生存範囲外にある変数については以下の処理を実施する必要は無いので、余計な処理を無くし、使用済みのレジスタ数を無駄に減らさないために本処理が実施される。なお、この処理方法についても上で述べた書籍に詳しく述べられているため、これ以上述べない。
【００３２】
実行回数設定部２２１３は、制御フロー図に含む各基本ブロック（Ｂａｓｉｃ  Ｂｌｏｃｋ）について実行回数を予測し、各基本ブロックに対応して予測実行回数のデータを、実行回数データ格納部２２２に格納する。スピルコードを発行する位置は、ストア命令であれば変数の値をメモリに待避させなければならない範囲の始まりであるファットスポットより前、ロード命令であれば変数の値をメモリに待避させなければならない範囲の終わりである変数への参照命令より前の比較的広い範囲で設定可能である。しかし、実行回数が多い位置に発行するとスピルコードによる負荷が大きくなってしまうため適当ではない。従って、変数の定義命令及び参照命令、及びファットスポットから特定される範囲の中で実行回数ができるだけ少ない位置を特定して発行することが好ましい。なお、以下で説明するように実際に実行回数を計数しても良いが、本実施の形態では厳密な実行回数のデータが必要なわけではなく、実行回数の相対的な多寡が分かればよい。従って、図２においては、通常の基本ブロックには所定の基準値を割り当て、ループについては基準値より大きい値を割り当て、分岐については分岐の確率が例えば１／２として基準値の半分の値を割り当てるといった形で予測実行回数のデータを生成する。なお、他の方法を用いて実行回数を予測しても良い。
【００３３】
このような前処理の後にファットスポット特定部２２４は、ファットスポットデータ格納部２２３に格納されたデータを参照してファットスポット特定処理を実施する（ステップＳ９）。上でも述べたように、ファットスポットはレジスタのデータを破壊する命令や、レジスタの不足から生ずる。ファットスポットデータ格納部２２３に、特定のレジスタ及び当該特定のレジスタのデータを破壊する命令のデータが含まれている場合には、当該命令を抽出し、影響のある変数を特定して、当該変数のファットスポットであることをファットスポットデータ格納部２２３に格納しておく。例えばＳＰＡＲＣ（Ｓｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ社の商標）アーキテクチャの場合、浮動小数点レジスタのデータは関数呼出し命令によって破壊される。また、レジスタ不足を検出する方法としては、グラフ彩色によってレジスタ割り付けを行い、割り当てる色が存在しない変数をスピルすべき変数と特定する方法が、例えば「Ｍｏｄｅｒｎ  Ｃｏｍｐｉｌｅｒ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｉｎ  ＭＬ」Ａｎｄｗｅｒ  ｗ．  Ａｐｐｅｌ，  Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，    ＩＳＢＮ：  ０５２１５８２７４１  という書籍に開示されている。従って、このようにして特定された変数の生存範囲内において、この変数が割り付けられるべきレジスタがすべて使用されている範囲をファットスポットと特定し、ファットスポットデータ格納部２２３に格納する。なお、ファットスポットが存在しない場合もあり、その場合にはステップＳ１７に移行する。
【００３４】
次に、状態グラフ処理部２２５は、ファットスポットデータ格納部２２３に格納されたデータを参照して、初期状態グラフの生成処理を実施する（ステップＳ１１）。この処理については、後に詳しく述べるが、変数の生存範囲内で、変数の定義点、変数の参照点、ファットスポット、及び制御の節目点に対応するノードを含み、それらのノードを制御フローに従ってエッジで接続したグラフを生成する。なお、変数の定義点及び変数の参照点については、当該変数の値をレジスタに格納すべき状態を表すＲ状態が割り当てられ、ファットスポットについては、変数の値をメモリに格納すべき状態を表すＭ状態が割り当てられる。初期状態グラフだけでも、スピルコードを発行すべき範囲については特定できる。しかし、必ずしも最適とは言えない。そこで、状態グラフ処理部２２５は、実行回数データ格納部２２２に格納された予測実行回数についてのデータを用いて、状態グラフの状態決定処理を実施する（ステップＳ１３）。この処理についても後に詳しく述べるが、初期状態グラフでは状態が定まっていなかったノードに、予測実行回数に基づく優先順位に従って状態を設定してゆく。
【００３５】
このようにして状態グラフの各ノードに状態が定まると、Ｒ状態のノードとＭ状態のノードが接続されたエッジと、Ｍ状態のノードとＲ状態のノードが接続されたエッジが存在する。スピルコード生成部２２６は、このような状態遷移が発生しているエッジを検出し、当該エッジの位置にスピルコードを生成し、中間コードに加える（ステップＳ１５）。
【００３６】
その後他の最適化処理を実施する（ステップＳ１７）。なお、他の最適化処理はステップＳ７乃至Ｓ１５とは別に独立して実施されるため、必ずしもステップＳ１５の後に行われるものではない。そして、全ての最適化処理が終了すると、コード生成部２３０はオブジェクト・プログラム生成処理を実施し、出力オブジェクト・プログラム３０を生成・出力する（ステップＳ１９）。
【００３７】
以上のような処理を実施することにより、適切な位置にスピルコードを発行することができるようになる。なお、一旦発行したスピルコードを削除するような処理も行わないため、最初からスピルコードの発行数も最適化されている。また、ファットスポットデータ格納部２２３に格納したファットスポットの生成条件を限定することにより、発行されるスピルコードのマシン依存性を限定的にすることができるようになる。
【００３８】
次に、図３を用いて、実行回数を実際に計数するようにした場合の処理フローを説明する。本実施の形態では、ファットスポットについてのデータの設定入力をユーザから受け付け、ファットスポット・データ格納部２２３に格納する（ステップＳ２１）。出力オブジェクト・プログラム３０が実行され得るマシン毎に上記のようなデータを保持するテーブルを用意しておき、ユーザはマシンの選択を行うことにより、ファットスポットについてのデータを特定するようにしても良い。
【００３９】
次に、ユーザの指示に従ってコンパイルを行うソース・プログラム１０をメモリに読み込む（ステップＳ２３）。そして、フロントエンド処理部２００の字句解析部２０１、構文解析部２０２及び意味解析部２０３により中間コード２１０を生成し、メモリに格納する（ステップＳ２５）。そして、中間コード２０１を用いて、制御フロー解析処理、変数生存範囲解析処理及び実行回数予測処理を含む前処理を前処理部２２１により実行する（ステップＳ２７）。制御フロー解析部２２１１は、中間コードを解析して制御フロー図（ＣＦＧ：  Ｃｏｎｔｒｏｌ  Ｆｌｏｗ  Ｇｒａｐｈ）を生成する。また、変数生存範囲解析部２２１２は、生存範囲を、制御フロー解析部２２１１により生成される制御フロー図を用いて特定する。実行回数設定部２２１３は、制御フロー図に含む各基本ブロック（Ｂａｓｉｃ  Ｂｌｏｃｋ）について実行回数を予測し、各基本ブロックに対応して予測実行回数のデータを、実行回数データ格納部２２２に格納する。
【００４０】
このような前処理の後にファットスポット特定部２２４は、ファットスポットデータ格納部２２３に格納されたデータを参照してファットスポット特定処理を実施する（ステップＳ２９）。なお、ファットスポットが存在しない場合もあり、その場合にはステップＳ５７に移行する。
【００４１】
次に、状態グラフ処理部２２５は、ファットスポットデータ格納部２２３に格納されたデータを参照して、初期状態グラフの生成処理を実施する（ステップＳ３１）。この処理については、後に詳しく述べるが、変数の生存範囲内で、変数の定義点、変数の参照点、ファットスポット、及び制御の節目点に対応するノードを含み、それらのノードを制御フローに従ってエッジで接続したグラフを生成する。なお、変数の定義点及び変数の参照点については、当該変数の値をレジスタに格納すべき状態を表すＲ状態が割り当てられ、ファットスポットについては、変数の値をメモリに格納すべき状態を表すＭ状態が割り当てられる。そして、状態グラフ処理部２２５は、実行回数データ格納部２２２に格納された予測実行回数についてのデータを用いて、状態グラフの状態決定処理を実施する（ステップＳ３３）。この処理についても後に詳しく述べるが、初期状態グラフでは状態が定まっていなかったノードに、予測実行回数に基づく優先順位に従って状態を設定してゆく。
【００４２】
このようにして状態グラフの各ノードに状態が定まると、Ｒ状態のノードとＭ状態のノードが接続されたエッジと、Ｍ状態のノードとＲ状態のノードが接続されたエッジが存在する。スピルコード生成部２２６は、このような状態遷移が発生しているエッジを検出し、当該エッジの位置にスピルコードを生成し、中間コードに加える（ステップＳ３５）。
【００４３】
その後他の最適化処理を実施する（ステップＳ３７）。なお、他の最適化処理はステップＳ２７乃至Ｓ３５とは別に独立して実施されるため、必ずしもステップＳ３５の後に行われるものではない。ここまでは図２と同じである。そして、全ての最適化処理が終了すると、コード生成部２３０はオブジェクト・プログラム生成処理を実施し、出力オブジェクト・プログラム３０を生成・出力する（ステップＳ３９）。ここでは、実行回数を記録するため、各基本ブロックの入口で当該基本ブロック用のカウンタがインクリメントされるような関数を呼ぶようにコードを追加する。
【００４４】
このようにして実行回数を計数するためのコードを含む出力オブジェクト・プログラム３０が生成されるので、この出力オブジェクト・プログラム３０を実行して、各基本ブロックについての実行回数を計数する（ステップＳ４１）。この実行回数に関するデータは次のコンパイル処理において読み込まれ、用いられる。
【００４５】
ステップＳ４１実行後任意のタイミングで、コンパイルを行うソース・プログラム１０をメモリに読み込む（ステップＳ４３）。そして、フロントエンド処理部２００の字句解析部２０１、構文解析部２０２及び意味解析部２０３により中間コード２１０を生成し、メモリに格納する（ステップＳ４５）。そして、中間コード２０１を用いて、制御フロー解析処理及び変数生存範囲解析処理を含む前処理を前処理部２２１により実行する（ステップＳ４７）。制御フロー解析部２２１１は、中間コードを解析して制御フロー図（ＣＦＧ：  Ｃｏｎｔｒｏｌ  Ｆｌｏｗ  Ｇｒａｐｈ）を生成する。また、変数生存範囲解析部２２１２は、生存範囲を、制御フロー解析部２２１１により生成される制御フロー図を用いて特定する。なお、実行回数設定部２２１３が、この段階において上で述べた実行回数の計数結果を実行回数データ格納部２２２に読み込むようにしても良い。
【００４６】
このような前処理の後にファットスポット特定部２２４は、ファットスポットデータ格納部２２３に格納されたデータを参照してファットスポット特定処理を実施する（ステップＳ４９）。
【００４７】
次に、状態グラフ処理部２２５は、ファットスポットデータ格納部２２３に格納されたデータを参照して、初期状態グラフの生成処理を実施する（ステップＳ５１）。そして、状態グラフ処理部２２５は、実行回数データ格納部２２２に格納された実際の実行回数についてのデータを用いて、状態グラフの状態決定処理を実施する（ステップＳ５３）。その後スピルコード生成部２２６は、このような状態遷移が発生しているエッジを検出し、当該エッジの位置にスピルコードを生成し、中間コードに加える（ステップＳ５５）。
【００４８】
そして他の最適化処理を実施する（ステップＳ５７）。なお、他の最適化処理はステップＳ４７乃至Ｓ５５とは別に独立して実施されるため、必ずしもステップＳ５５の後に行われるものではない。全ての最適化処理が終了すると、コード生成部２３０はオブジェクト・プログラム生成処理を実施し、出力オブジェクト・プログラム３０を生成・出力する（ステップＳ５９）。
【００４９】
このようにすれば、各基本ブロックについての実際の実行回数から状態グラフの状態決定処理を実施して、実際に即したスピルコードの発行を行うことができるようになる。
【００５０】
次に、図４乃至図１２を用いて図２及び図３における初期状態グラフの生成処理について説明する。初期状態グラフの生成処理を詳しく述べる前に、前提として実行される制御フロー解析処理において生成される制御フロー図について説明しておく。
【００５１】
例えば以下のような中間コードが入力される場合を考える。
【００５２】
【表１】
2004227025.tif 000003
なお、行番号は説明のために示している。
【００５３】
この中間コードを制御フロー解析部２２１１が処理すると、図４のような制御フロー図を得ることができる。図４に示すように、第２０行及び第２１行により基本ブロックｂｂ９０が構成され、第２２行により基本ブロックｂｂ９１が構成され、第２３行により基本ブロックｂｂ９２が構成され、第２４行及び第２５行により基本ブロックｂｂ９３が構成され、ループのバックエッジの部分で基本ブロックｂｂ９５が構成され、第２６行により基本ブロックｂｂ９４が構成される。ここで、基本ブロックｂｂ９０の出口と基本ブロックｂｂ９１の入口と基本ブロックｂｂ９２の入口とが接続されている。また、基本ブロックｂｂ９１の出口と基本ブロックｂｂ９２の入口とが接続されている。また、基本ブロックｂｂ９２の出口と基本ブロックｂｂ９３の入口と基本ブロックｂｂ９５の出口とが接続されている。さらに、基本ブロックｂｂ９３の出口と基本ブロックｂｂ９５の入口と基本ブロックｂｂ９４の入口とが接続されている。
【００５４】
以下の説明では、変数ｔ０を解析対象とするが、通常は生存している全ての変数について処理を実施する必要がある。また、この例においてファットスポットは第２２行の関数呼出し命令ｃａｌｌであるものとする。なお、基本ブロックｂｂ９０の第２０行において変数ｔ０は定義され、すなわち生存範囲が開始され、基本ブロックｂｂ９４の第２６行において変数ｔ０は参照され、生存範囲が終了する。
【００５５】
以上の前提の下に図５を用いて初期状態グラフの生成処理を説明する。以下の処理は各変数について実施される。但し、基本ブロックの処理順番については任意である。最初に、状態グラフ処理部２２５は、各変数について節目ノードマップを生成し、メモリに格納する（ステップＳ６１）。状態グラフのノードは、基本的には基本ブロックの入口と出口とに設けられるが、下の基本ブロックの入口ノードと上の基本ブロックの出口ノードとが接続されるようでは、不要な制御節目のノードが生成されることになるため、以下の処理において適切ではない。従って、必要な制御節目のノードのみが生成されるように、下の基本ブロックの入口ノードと上の基本ブロックの出口ノードとが接続されるような場面では、下の基本ブロックの入口ノードと上の基本ブロックの出口ノードとで共通するノードを１つ生成するように、節目ノードマップの情報を生成しておく。但し、必ずしも単純に２つの基本ブロックが接続されるわけではなく、図４に示したように、基本ブロックｂｂ９０の出口と基本ブロックｂｂ９１の入口と基本ブロックｂｂ９２の入口とが接続されたり、基本ブロックｂｂ９２の出口と基本ブロックｂｂ９３の入口と基本ブロックｂｂ９５の出口とが接続されたり、基本ブロックｂｂ９３の出口と基本ブロックｂｂ９４の入口と基本ブロックｂｂ９５の入口とが接続されたりする。従って、これらのような場合であっても、共通する１つのノードが生成されるように、節目ノードマップの情報を生成しておく。
【００５６】
ステップＳ６１では、図４に示した基本ブロックの接続関係から、例えば図６（ａ）乃至（ｄ）に示すような節目ノードマップの情報を生成しておく。図６（ａ）は、基本ブロックｂｂ９０の出口ノードと基本ブロックｂｂ９１の入口ノードと基本ブロックｂｂ９２の入口ノードとが共通で生成されるように、いずれかが生成済みとされると他のノードも生成済みとされるようなデータ構造を有することを示している。例えば、未生成状態であれば０が、生成済みでれば１が登録される。また、図６（ｂ）は、基本ブロックｂｂ９１の出口ノードと基本ブロックｂｂ９２の入口ノードとが共通で生成されるように、いずれかが生成済みとされると他のノードも生成済みとされるようなデータ構造を有することを示している。また、図６（ｃ）は、基本ブロックｂｂ９２の出口ノードと基本ブロックｂｂ９３の入口ノードと基本ブロックｂｂ９５の出口ノードとが共通して生成されるように、いずれかが生成済みとされると他のノードも生成済みとされるようなデータ構造を有することを示している。図６（ｄ）は、基本ブロックｂｂ９３の出口ノードと基本ブロックｂｂ９４の入口ノードと基本ブロックｂｂ９５の入口ノードとが共通して生成されるように、いずれかが生成済みとされると他のノードも生成済みとされるようなデータ構造を有することを示している。なお、基本ブロックｂｂ９２の入口は２箇所に登録されているが、基本ブロックｂｂ９２の入口ノードが生成された場合には、最初に図６（ｂ）において生成済みと登録する。
【００５７】
次に、状態グラフ処理部２２５は、未処理の基本ブロックが存在しているか判断する（ステップＳ６３）。未処理の基本ブロックが無ければ既に初期状態グラフが生成されたことになるので元の処理に戻る。一方、未処理の基本ブロックが存在する場合には、未処理の基本ブロックを１つ選択し、当該未処理の基本ブロックの出口で生存している変数の出口ノードが節目ノードマップにおいて生成済みと登録されているか判断する（ステップＳ６５）。なお、生存していないと判断された変数については次の基本ブロックについての処理になるまで処理をスキップする。生成済みではないと判断された場合には、当該基本ブロックの出口ノードを生成し、状態グラフの記憶領域に格納する（ステップＳ６７）。そして、当該基本ブロックの出口ノード生成を節目ノードマップに登録する（ステップＳ６９）。節目ノードマップに登録することにより、接続された他の基本ノードの例えば入口ノードが生成済みとして登録されたことになる。
【００５８】
そしてステップＳ６９の後又はステップＳ６５において出口ノードが生成済みであると判断された場合、出口ノードを本基本ブロックの最終ノードマップに登録する（ステップＳ７１）。最終ノードマップは、当該基本ブロックにおいて最も最近に生成されたノードを示し、次に生成したノードと接続させるために用いる。そして、未処理の命令が存在するか判断する（ステップＳ７３）。以下の処理を基本ブロックの最も下の命令から順番に行う。未処理の命令が存在する場合には、端子Ｂを介して図７の処理に移行する。
【００５９】
次に図７の処理の内容を説明する。状態グラフ処理部２２５は、基本ブロック内の次の上の命令を取得する（ステップＳ８３）。そして、当該命令において定義されている変数について、Ｒ状態（レジスタに値を格納すべき状態）のノードを生成し、状態グラフの記憶領域に登録し、最終ノードマップを参照して最後に生成したノードとエッジを張って当該エッジのデータを状態グラフの記憶領域に登録し、最終ノードマップからエントリを削除する（ステップＳ８５）。定義されていない変数については本ステップをスキップする。また、当該命令がファットスポットである変数について、Ｍ状態（メモリに値を格納すべき状態）のノードを生成し、状態グラフの記憶領域に登録する。そして、Ｍ状態のノードと最終ノードマップに登録されている全ての最後に生成したノードとエッジを張って、当該エッジのデータを状態グラフの記憶領域に登録する（ステップＳ８７）。ファットスポットではない変数については、本ステップをスキップする。さらに、当該命令において参照されている変数について、Ｒ状態のノードを生成し、状態グラフの記憶領域に登録し、最終ノードマップを参照して最後に生成したノードとエッジを張って当該エッジのデータを状態グラフの記憶領域に登録する。また、生成したＲ状態のノードを最終ノードマップに登録する（ステップＳ８９）。参照されていない変数については本ステップをスキップする。そして端子Ｃを介して図５のステップＳ７３に戻る。
【００６０】
ステップＳ７３において未処理の命令が存在しないと判断された場合には、基本ブロックの入口で生存している変数の入口ノードが節目ノードマップにおいて生成済みと登録されているか判断する（ステップＳ７５）。もし、入口ノードが節目ノードマップに生成済みと登録されていない場合には、当該基本ブロックの入口ノードを生成し、状態グラフの記憶領域に登録すると共に、最終ノードマップを参照して最後に生成したノードとエッジを張り、当該エッジのデータを状態グラフの記憶領域に登録する（ステップＳ７７）。そして、当該基本ブロックの入口ノード生成を節目ノードマップに登録する（ステップＳ７９）。ステップＳ７９の後又はステップＳ７５において入口ノードが節目ノードマップに登録されていると判断された場合には、最終ノードマップのエントリを削除する（ステップＳ８１）。そして端子Ａを介してステップＳ６３に戻る。なお、ステップＳ７５において生存していないと判断された場合にはステップＳ８１に移行する。
【００６１】
このような処理を実施することにより、各変数の参照点、定義点、ファットスポット及び制御節目に対応するノードを含み、制御フローに従ったエッジが設けられた初期状態グラフが生成される。なお、参照点、定義点及びファットスポットに対応するノードには、Ｒ状態又はＭ状態が登録されているが、それ以外の制御節目のノードについては状態は設定されていない。これについては以下で状態を設定する処理について説明する。
【００６２】
念のため図４で示した制御フロー図から変数ｔ０についての初期状態グラフを生成する手順について説明しておく。基本ブロックｂｂ９４の出口で変数ｔ０は生存していないので基本ブロックｂｂ９４の出口ノードを生成せず、節目ノードマップにも登録しない（ステップＳ６５）。この場合ノードが無いのでステップＳ７１はスキップされる。次に、基本ブロックｂｂ９４の第２６行で変数ｔ０は参照されているので、Ｒ状態のノードｇを生成し、最終ノードマップに登録する（ステップＳ８９）。これが図８（ａ）の状態である。基本ブロックｂｂ９４の命令は終わりだが、基本ブロックｂｂ９４の入口ノードが生成済みであるとは節目ノードマップには登録されていないので、基本ブロックｂｂ９４の入口ノードｆを生成し、節目ノードマップ（図６（ｄ））にも基本ブロックｂｂ９４の入口ノードが生成済みであることを登録する。また、ノードｇとノードｆのエッジを張る。さらに最終ノードマップからノードｇを削除する（ステップＳ７５乃至Ｓ８１）。これが図８（ｂ）の状態である。
【００６３】
次に基本ブロックｂｂ９３の処理を行う。基本ブロックｂｂ９３の出口で変数ｔ０は生存しているが、節目ノードマップ（図６（ｄ））に基本ブロックｂｂ９３の出口ノードが生成済みであることが登録されているので出口ノードは生成せず、節目ノードマップにも登録を行わない。ここで最終ノードマップをノードｆに更新する（ステップＳ６５及びＳ７１）。基本ブロックｂｂ９３の第２５行及び第２６行では変数ｔ０に関する命令はないので処理をスキップする。そうすると、基本ブロックｂｂ９３の命令は終わりになるが、基本ブロックｂｂ９３の入口ノードが節目ノードマップに生成済みと登録されていないので、基本ブロックｂｂ９３の入口ノードｅを生成し、節目ノードマップ（図６（ｃ））に基本ブロックｂｂ９３の入口ノードを生成済みであるとして登録する。入口ノードｅから出口ノードｆにエッジを張る。そして最終ノードマップｆを削除する（ステップＳ７５乃至Ｓ８１）。これが図８（ｃ）の状態である。
【００６４】
次に、基本ブロックｂｂ９５の処理を行う。基本ブロックｂｂ９５の出口で変数ｔ０は生存しているが、節目ノードマップ（図６（ｃ））に基本ブロックｂｂ９５の出口ノードが生成済みと登録されているので、出口ノードを生成せず、節目ノードマップにも登録を行わない。但し、最終ノードマップにノードｅを登録する（ステップＳ６５及びＳ７１）。また、基本ブロックｂｂ９５の入口で変数ｔ０は生存しているが、節目ノードマップ（図６（ｄ））には基本ブロックｂｂ９５の入口ノードが生成済みであることが登録されているので入口ノードの生成は行わない。入口ノードｆから出口ノードｅにエッジを張る。また、最終ノードマップからノードｅを削除する（ステップＳ７５及びＳ８１）。これが図８（ｄ）の状態である。
【００６５】
そして、基本ブロックｂｂ９２の処理を行う。基本ブロックｂｂ９２の出口で変数ｔ０は生存しているが、節目ノードマップ（図６（ｃ））には基本ブロックｂｂ９２の出口ノードは生成済みと登録されているので、出口ノードを生成せず、節目ノードマップにも生成済みを登録しない。但し、最終ノードマップにノードｅを登録する（ステップＳ６５及びＳ７１）。また基本ブロックｂｂ９２の入口で変数ｔ０は生存しており、節目ノードマップ（図６（ｂ））にも生成済みが登録されていないので、基本ブロックｂｂ９２の入口ノードｄを生成し、節目ノードマップ（図６（ｂ））に基本ブロックｂｂ９２の入口ノードが生成済みであることを表すデータを登録する。但し、節目ノードマップにおいては、エントリが２つで入口及び出口の対だけのもの（図６（ｂ））を優先で登録する。また基本ブロックｂｂ９２の入口ノードｄから基本ブロックｂｂ９２の出口ノードｅへエッジを張る。そして、最終ノードマップからノードｅを削除する（ステップＳ７５乃至Ｓ８１）。これが図８（ｅ）の状態である。
【００６６】
次に、基本ブロックｂｂ９１の処理を行う。基本ブロックｂｂ９１の出口で変数ｔ０は存在しているが、節目ノードマップ（図６（ｂ））において基本ブロックｂｂ９１の出口ノードは生成済みであると登録されているので、出口ノードを生成しない。但し、最終ノードマップにノードｄを登録する（ステップＳ６５及びＳ７１）。基本ブロックｂｂ９１の第２２行は変数ｔ０のファットスポットであるから、Ｍ状態のノードｃを生成し、ノードｄとノードｃ間のエッジを張る（ステップＳ８７）。これが図８（ｆ）の状態である。そして、基本ブロックｂｂ９１の命令は終わりなので、基本ブロックｂｂ９１の入口ノードを節目ノードマップで検索すると登録されていないので、基本ブロックｂｂ９１の入口ノードｂを生成し、節目ノードマップ（図６（ａ））に生成済みを登録する。そして、ノードｃとノードｂ間のエッジを生成する。なお、基本ブロックｂｂ９２の入口ノードが２つ生成されたことになるので、ノードｂとノードｄも接続する。なお、最終ノードマップのエントリを削除する（ステップＳ７５乃至Ｓ８１）。これが図８（ｇ）の状態である。
【００６７】
次に、基本ブロックｂｂ９０の処理を行う。基本ブロックｂｂ９０の出口で変数ｔ０は存在しているが、節目ノードマップ（図６（ａ））において基本ｂｂ９０の出口ノードは生成済みであるから、出口ノードは生成しない。なお、最終ノードマップをノードｂに更新する（ステップＳ６５及びＳ７１）。そして、基本ブロックｂｂ９０の第２１行は変数ｔ０に関係しないので処理をスキップする。また、基本ブロックｂｂ９０の第２０行は変数ｔ０の定義であるから、Ｒ状態のノードａを生成し、最終ノードマップに登録されているノードｂと接続し、変数ｔ０の定義であるから最終ノードマップからエントリを削除する（ステップＳ８５）。これが図８（ｈ）の状態である。最後に基本ブロックｂｂ９０の命令は終わりであるが、最終ノードマップには登録が無いので、入口ノードは生成せず、節目ノードマップにも生成済みを登録することは無い（ステップＳ７５）。
【００６８】
図８（ｈ）のような初期状態グラフを見ると、ノードａはＲ状態であり、ノードｃはＭ状態であり、ノードｇはＲ状態である。状態の意味からして、ノードａでは変数ｔ０の値はレジスタに格納されていなければならず、ノードｃでは変数ｔ０の値はメモリに格納されていなければならず、ノードｇでは変数ｔ０の値はレジスタに格納されていなければならない。すなわち、スピルコードであるストア命令は、ノードａからノードｃの間に存在すればよく、スピルコードであるロード命令は、ノードｃからノードｇの間に存在すればよい。このように初期状態グラフでは、まだ適切なスピルコードの発行位置は特定できていない。但し、上で述べた間のいずれかに発行すれば、少なくとも問題なく命令は実行される。また、実行回数は多くなって非効率かもしれないが、上で述べた間のいずれかに発行すれば後に除去する必要は無くスピルコードは適切な個数発行されていることになる。
【００６９】
次に、図９乃至図１２を用いて、状態グラフの状態決定処理について説明する。なお、擬似コードについてもここで示しておき、フローチャートの各ステップが擬似コードのいずれの処理を行っているのかを説明する。
【００７０】
【表２】
2004227025.tif 000004
【００７１】
状態グラフ処理部２２５は、未処理の変数が存在するか判断する（ステップＳ９１）。未処理の変数が存在しないと判断された場合には、元の処理に戻る。一方、未処理の変数が存在すると判断された場合には、１つ未処理の変数を特定する（ステップＳ９３）。そして、実行回数データ格納部２２２を参照して実行回数を基準にエッジの処理順番を決定する（ステップＳ９５）。例えば、基本ブロックｂｂ９０の実行回数が１０回、基本ブロックｂｂ９１の実行回数が２回、基本ブロックｂｂ９２の実行回数が１０回、基本ブロックｂｂ９３が１００回、基本ブロックｂｂ９５の実行回数が９９回、基本ブロックｂｂ９４の実行回数が１０回であるとする。基本ブロック内のノード間のエッジは基本ブロックの実行回数と同じであり、それ以外の場合には基本ブロックの実行回数から導き出される。図８（ｈ）の例の場合、図１０に示すように、ノードａからノードｂへのエッジＡの実行回数は基本ブロックｂｂ９０の実行回数と同じ１０回、ノードｂからノードｃへのエッジＢはノードｂを含む基本ブロックｂｂ９１の実行回数から２回、ノードｂからノードｄへのエッジＤの実行回数は基本ブロックｂｂ９０の実行回数１０回と基本ブロックｂｂ９１の実行回数２回から８回、ノードｃからノードｄへのエッジＣは基本ブロックｂｂ９１の実行回数と同じ２回、ノードｄからノードｅへのエッジＥの実行回数は基本ブロックｂｂ９２の実行回数と同じ１０回、ノードｅからノードｆへのエッジＦの実行回数は基本ブロックｂｂ９３と同じ実行回数１００回、ノードｆからノードｅへのエッジＧの実行回数は基本ブロックｂｂ９５の実行回数と同じ９９回、ノードｆからノードｇへのエッジＨの実行回数は基本ブロックｂｂ９４の実行回数と同じ１０回となる。これを実行回数の多い順に並べると、Ｆ，Ｇ，（Ｈ，Ｅ，Ａ），Ｄ，（Ｂ，Ｃ）となる。なお括弧内は回数が同じであることを表している。次に、状態グラフ処理部２２５は、未処理のエッジが存在するか判断する（ステップＳ９７）。ここまでの処理が擬似コードの１０−０１行及び１０−０２行の処理になる。
【００７２】
もし、未処理のエッジがないと判断された場合にはステップＳ９１に戻る。一方、未処理のエッジが存在すると判断された場合には、優先順位の最も高い未処理のエッジを特定する（ステップＳ９９）。そして、エッジの両端の状態が決定済みか否かを判断する（ステップＳ１０１）。エッジの両端の状態が決定済みであると判断されると何も処理を行わずステップＳ９７に戻る。ここまでの処理が擬似コードの１０−０３行乃至１０−０６行までの処理になる。一方、エッジの両端の状態が決定済みではないと判断された場合には、エッジの両端の状態が未決定であるか判断する（ステップＳ１０３）。もし、エッジの両端の状態が未決定であると判断された場合には、両端のノードの状態をＳ状態に仮設定し、状態ノードを格納する記憶領域に登録する（ステップＳ１０５）。Ｓ状態は状態が確定しているノードではなく、後にＲ又はＭのいずれかに決定される。そしてステップＳ９７に戻る。ここまでの処理が擬似コード１０−１７行乃至１０−２０行の処理になる。
【００７３】
ステップＳ１０３においていずれか一方のノードの状態が決定されていると判断された場合には、両端のノードの状態を同じ状態に決定し、状態ノードを格納する記憶領域に登録する（ステップＳ１０７）。この際、Ｓ状態については仮設定された状態であるから状態未決定であるとして取り扱われる。従って、一方のノードがＲ又はＭ状態で、他方のノードがＳ状態であると、他方のノードはＲ又はＭ状態に変更される。そして、旧状態がＳ状態であったか否かを判断する（ステップＳ１０９）。旧状態がＳ状態ではなかったと判断された場合には、特に処理を行うことなくステップＳ９７に戻る。一方、旧状態がＳ状態であったと判断された場合には、後に述べる状態伝播処理を実施する（ステップＳ１１１）。状態伝播処理は、以下で詳しく述べるが、旧状態がＳ状態であるということは、このＳ状態であるノードに接続されたエッジにさらに接続されているノードの状態もＳ状態であるから、このＳ状態のノードについてもＲ又はＭ状態のノードとして設定してしまうという処理である。ここまでの処理は擬似コードの１０−０７行乃至１０−１６行までの処理を示している。擬似コードでは、エッジの両端のノードをＡとＢとに分けて記載しているので長くなっているが、内容は同じである。
【００７４】
このように実行回数の優先順位に従って上記の処理を実施することにより、実行回数の多いエッジに接続されているノードの状態が優先的に伝播されてゆくことになる。すなわち、実行回数の多いエッジに接続されているノードの状態が長く続くようになる。見方を変えれば、実行回数の多いエッジに接続されているノードの周りでは状態変更が発生しないのでスピルコードは発行されない。そして、状態変更を行わなければならない範囲において実行回数が最も少ないエッジにおいてノードの状態変更が発生するようになるので、スピルコードの発行位置は実行回数の少ないエッジになり、スピルコードの実行回数は最小限に抑えられることになる。
【００７５】
ステップＳ１１１の状態伝播処理について図１１及び図１２を用いて説明する。なお、状態伝播処理についても擬似コードを以下に示し、フローチャートの各ステップが擬似コードのいずれの処理を行っているのかを説明する。
【００７６】
【表３】
2004227025.tif 000005
【００７７】
状態グラフ処理部２２５は、未処理エッジ集合に、今回Ｓ状態からＲ又はＭ状態に状態変更がなされたノードに繋がる全エッジを追加する（ステップＳ１１３）。未処理エッジ集合を格納するための記憶領域に全エッジの情報を登録する。ここまでの処理が、擬似コードの１０−２３行及び１０−２４行の処理である。そして、未処理エッジ集合は空であるか判断する（ステップＳ１１５）。この処理が擬似コードの１０−２５行の処理である。もし、未処理エッジ集合が空であると判断されれば元の処理に戻る。一方、未処理エッジ集合が空ではないと判断された場合には、未処理エッジ集合からエッジを１つ取り出し、未処理エッジ集合から当該エッジを削除する（ステップＳ１１７）。この処理が擬似コード１０−２６行の処理である。取り出したエッジの一端のノードの状態を既に変更しているので、他端のノードの状態がどのようになっているかに依存して以下の処理が決定される。すなわち、他端のノードの状態がＭ又はＲ状態であるか否かを判断する（ステップＳ１１９）。他端のノードの状態がＭ又はＲ状態であると判断された場合には、状態の伝播はこれで終わりであるからステップＳ１１５に戻る。ここまでの処理が擬似コードにおける１０−２７行の処理である。一方、他端のノードの状態がＳ状態であると判断された場合には、Ｓ状態である他端のノードの状態を、一端のノード状態と同じに設定し、状態グラフを格納する記憶領域に登録する（ステップＳ１２１）。そしてステップＳ１１３に戻る。ここまでの処理が擬似コードにおける１０−２８行乃至１０−３０行の処理である。
【００７８】
このように、Ｓ状態であるノードには次々とステップＳ１０７で決定された状態が伝播されてゆく。
【００７９】
図１０に示した例を用いて、どのように状態が決定されてゆくかを具体的に説明する。最初に、最も実行回数の多いエッジＦが選択される。これらの両端のノードの状態は未決定であるから、Ｓ状態がノードｅ及びノードｆに割り当てられる。次に実行回数の多いエッジＧについては既にノードｅ及びノードｆの状態がＳ状態になっているのでスキップする。ここまでの状態が図１２（ａ）に示されている。次に実行回数の多いのはエッジＡ、エッジＥ、エッジＨである。エッジＡから実行すると、エッジＡの一端はＲ状態のノードａであるから、他端のノードｂについてはこの状態Ｒが伝播する。次にエッジＥを処理すると、両端のノードの状態は未決定であるから、Ｓ状態がノードｅ及びノードｄに割り当てられる。ここまでの状態が図１２（ｂ）に示されている。
【００８０】
次に、エッジＨが処理される。エッジＨの一端はＲ状態のノードｇであるから、他端のノードｆにはＲ状態が伝播される。すなわちノードｆの状態はＳ状態からＲ状態に変更される。ここで状態伝播処理（図１１）を実行する。未処理エッジ集合にエッジＦを登録すると、エッジＦの他端のノードｅもＳ状態であるから、エッジＦの他端のノードｅもＳ状態からＲ状態に変更する。そして、エッジＥを未処理エッジ集合に登録する。エッジＥの他端のノードｄもＳ状態であるから、エッジＥの他端のノードｄもＳ状態からＲ状態に変更する。そして、エッジＣ及びエッジＤを未処理エッジ集合に登録する。しかし、エッジＣ及びエッジＤについてはその他端が既にＲ状態又はＭ状態が登録されたノードｃ及びノードｂであるからここで元の処理に戻る。但し、これで全てのノードの状態が決定されており、図１２（ｃ）に示す状態になる。
【００８１】
このようにすればノードｂとノードｃの間のエッジＢにおいてＲ状態からＭ状態に遷移しているので、ストア命令を発行すべきであることが分かり、またノードｃからノードｄの間のエッジＣにおいてＭ状態からＲ状態に遷移しているので、ロード命令を発行すべきであることが分かる。
【００８２】
従って、表１で示した中間コードにスピルコードを加えると、以下のようになる。
【００８３】
【表４】
2004227025.tif 000006
【００８４】
このように第８２行と第８４行とにストア命令とロード命令を発行したので、第８１行で第８３行の関数呼び出し命令に分岐する場合にのみストア命令が実行され、さらに第８３行の後の第８４行でロード命令が実行される。すなわち、第８１行で第８３行の関数呼び出し命令に分岐しなければスピルコードは全く実行されないので、それだけでも実行回数が少なくなっていることが分かる。
【００８５】
一方、単純にスピルコードを発行することにすると、以下のようになる。
【００８６】
【表５】
2004227025.tif 000007
【００８７】
このように第９２行にストア命令を入れると必ず実行されるので、ストア命令の実行回数は増加してしまう。同様に、第９８行にロード命令を入れると必ず実行されるので、ロード命令の実行回数は増加してしまう。従って、非効率なスピルコードの実行がなされることになる。
【００８８】
このように表４に示した本実施の形態に従ったスピルコードの発行位置の方が、実行回数が少ない位置となっているため実行速度を上げることができるようになる。
【００８９】
以上本発明の一実施の形態を説明したが、本発明はこれに限定されない。すなわち、初期状態ノードの生成方法については、上で述べたような処理フローに従う必要は無く、別の方法を用いても図８（ｈ）のような初期状態グラフを決定することができる。特に、節目ノードマップの構成及び生成・使用方法及び最終ノードマップの生成・使用方法については、別の方法を用いることができる。
【００９０】
また、図１に示した機能ブロック図は一例であって必ずしも図１に示したような機能ブロック構成でなくともよい。特にプログラム・モジュールと機能ブロックとは必ずしも対応しない。
【００９１】
（付記１）
ソースプログラムをコンパイルする際にコンピュータにスピルコードの発行位置を特定させるスピルコード発行位置特定プログラムであって、
各基本ブロックの実行回数に関するデータを取得し、当該各基本ブロックの実行回数に関するデータを記憶装置に格納する実行回数取得機能と、
レジスタに格納された特定の変数のデータをメモリに待避しなければならない範囲であるファットスポットを特定し、当該ファットスポットのデータを記憶装置に格納するファットスポット特定機能と、
前記特定の変数の定義ポイントと前記特定の変数への参照ポイントと前記ファットスポットのデータと前記各基本ブロックの実行回数に関するデータとに基づき、前記特定の変数に関するスピルコードの実行回数が最小となる位置を特定する位置特定機能と、
をコンピュータに実現させるためのスピルコード発行位置特定プログラム。
【００９２】
（付記２）
前記位置特定機能が、
前記特定の変数の定義ポイントに対応するノードと前記特定の変数への参照ポイントに対応するノードと制御の節目のポイントに対応するノードとを少なくとも含み、前記定義ポイント及び前記参照ポイントに対応するノードは第１の状態に設定され、前記ファットスポットに対応するノードは第２の状態に設定された状態グラフを生成し、記憶装置に格納する状態グラフ生成機能と、
前記各基本ブロックの実行回数に関するデータに基づき決定された優先順位に従って前記状態グラフにおいてノード間を接続するエッジを選択し、当該エッジに接続されたノードの状態を所定のルールに従って状態が未設定のノードに伝播させる機能と、
前記状態グラフにおいて両端のノードで設定された状態が異なるエッジを抽出する機能と、
を含む付記１記載のスピルコード発行位置特定プログラム。
【００９３】
（付記３）
前記ファットスポット特定機能が、
使用可能なレジスタの個数のデータと特定のレジスタに格納されたデータを破壊する命令に関するデータとの少なくともいずれかを参照する機能
を含むことを特徴とする付記１記載のスピルコード発行位置特定プログラム。
【００９４】
（付記４）
前記実行回数取得機能が、
各基本ブロックの実行回数をカウントする機能、
を含むことを特徴とする付記１記載のスピルコード発行位置特定プログラム。
【００９５】
（付記５）
ソースプログラムをコンパイルする際にコンピュータにスピルコードの発行位置を特定させるスピルコード発行位置特定プログラムであって、
レジスタに格納された特定の変数のデータをメモリに待避しなければならない範囲であるファットスポットを特定するファットスポット特定機能と、
前記特定の変数の定義ポイントに対応するノードと前記特定の変数への参照ポイントに対応するノードと制御の節目のポイントに対応するノードとを少なくとも含み、前記定義ポイント及び前記参照ポイントに対応するノードは第１の状態に設定され、前記ファットスポットに対応するノードは第２の状態に設定された状態グラフを生成し、記憶装置に格納する状態グラフ生成機能と、
所定の優先順位に基づき前記状態グラフにおいてノード間を接続するエッジを選択し、当該エッジに接続されたノードの状態を所定のルールに従って状態が未設定のノードに伝播させる状態伝播機能と、
前記状態グラフにおいて両端のノードで設定された状態が異なるエッジを抽出する機能と、
をコンピュータに実現させるためのスピルコード発行位置特定プログラム。
【００９６】
（付記６）
前記状態グラフの各エッジの実行回数に関するデータを取得する実行回数取得機能
をコンピュータにさらに実行させ、
前記実行回数の多い順に前記所定の優先順位が決定される
ことを特徴とする付記５記載のスピルコード発行位置特定プログラム。
【００９７】
（付記７）
前記特定の変数の生存範囲を特定する機能
をさらにコンピュータに実行させ、
前記状態グラフ生成機能が、
前記特定の変数の生存範囲のデータを参照して前記状態グラフにおけるノードの生成の是非を判断する機能
を含むことを特徴とする付記５記載のスピルコード発行位置特定プログラム。
【００９８】
（付記８）
前記状態伝播機能が、
選択されたエッジの両端のノードの状態が未設定である場合に、当該選択されたエッジの両端のノードの状態を第３の状態に仮設定する機能と、
選択されたエッジの一方のノードの状態が第１又は第２の状態であり且つ他方のノードの状態が未設定と前記第３の状態とのいずれかである場合に、前記他方のノードの状態を前記一方のノードの状態に設定する機能と、
前記他方のノードの状態が前記第３の状態であった場合には、当該他方のノードに接続されている別のノードの状態を前記一方のノードの状態に設定する機能と、
を含むことを特徴とする付記５記載のスピルコード発行位置特定プログラム。
【００９９】
（付記９）
スピルコードの発行位置を特定するコンパイル装置であって、
各基本ブロックの実行回数に関するデータを取得し、当該各基本ブロックの実行回数に関するデータを記憶装置に格納する手段と、
レジスタに格納された特定の変数のデータをメモリに待避しなければならない範囲であるファットスポットを特定し、当該ファットスポットのデータを記憶装置に格納する手段と、
前記特定の変数の定義ポイントと前記特定の変数への参照ポイントと前記ファットスポットのデータと前記各基本ブロックの実行回数に関するデータとに基づき、前記特定の変数に関するスピルコードの実行回数が最小となる位置を特定する手段と、
を有するコンパイル装置。
【０１００】
（付記１０）
スピルコードの発行位置を特定するコンパイル装置であって、
レジスタに格納された特定の変数のデータをメモリに待避しなければならない範囲であるファットスポットを特定する手段と、
前記特定の変数の定義ポイントに対応するノードと前記特定の変数への参照ポイントに対応するノードと制御の節目のポイントに対応するノードとを少なくとも含み、前記定義ポイント及び前記参照ポイントに対応するノードは第１の状態に設定され、前記ファットスポットに対応するノードは第２の状態に設定された状態グラフを生成し、記憶装置に格納する手段と、
所定の優先順位に基づき前記状態グラフにおいてノード間を接続するエッジを選択し、当該エッジに接続されたノードの状態を所定のルールに従って状態が未設定のノードに伝播させる手段と、
前記状態グラフにおいて両端のノードで設定された状態が異なるエッジを抽出する手段と、
を有するコンパイル装置。
【０１０１】
（付記１１）
ソースプログラムをコンパイルする際にスピルコードの発行位置を特定する方法であって、
各基本ブロックの実行回数に関するデータを取得し、当該各基本ブロックの実行回数に関するデータを記憶装置に格納する実行回数取得ステップと、
レジスタに格納された特定の変数のデータをメモリに待避しなければならない範囲であるファットスポットを特定し、当該ファットスポットのデータを記憶装置に格納するファットスポット特定ステップと、
前記特定の変数の定義ポイントと前記特定の変数への参照ポイントと前記ファットスポットのデータと前記各基本ブロックの実行回数に関するデータとに基づき、前記特定の変数に関するスピルコードの実行回数が最小となる位置を特定する位置特定ステップと、
を含むスピルコード発行位置特定方法。
【０１０２】
（付記１２）
ソースプログラムをコンパイルする際にスピルコードの発行位置を特定する方法であって、
レジスタに格納された特定の変数のデータをメモリに待避しなければならない範囲であるファットスポットを特定するファットスポット特定ステップと、
前記特定の変数の定義ポイントに対応するノードと前記特定の変数への参照ポイントに対応するノードと制御の節目のポイントに対応するノードとを少なくとも含み、前記定義ポイント及び前記参照ポイントに対応するノードは第１の状態に設定され、前記ファットスポットに対応するノードは第２の状態に設定された状態グラフを生成し、記憶装置に格納する状態グラフ生成ステップと、
所定の優先順位に基づき前記状態グラフにおいてノード間を接続するエッジを選択し、当該エッジに接続されたノードの状態を所定のルールに従って状態が未設定のノードに伝播させる状態伝播ステップと、
前記状態グラフにおいて両端のノードで設定された状態が異なるエッジを抽出するステップと、
を含むスピルコード発行位置特定方法。
【０１０３】
【発明の効果】
以上述べたように本発明によれば、無駄にスピルコードを発行しないようにスピルコード発行位置を特定する技術を提供することができる。
【０１０４】
また、スピルコードの実行回数を最適化するための技術を提供することができる。
【０１０５】
さらに、必要最低限のマシン依存性を有するスピルコード発行を可能とする技術を提供することができる。
【図面の簡単な説明】
【図１】本発明の一実施の形態における機能ブロックを示す図である。
【図２】本発明の第１の態様に係る処理フローを示す図である。
【図３】本発明の第２の態様に係る処理フローを示す図である。
【図４】制御フロー図の一例を示す図である。
【図５】初期状態グラフの生成処理の処理フロー（その１）を示す図である。
【図６】（ａ）乃至（ｄ）は節目ノードマップの一例を示す図である。
【図７】初期状態グラフの生成処理の処理フロー（その２）を示す図である。
【図８】（ａ）乃至（ｈ）は初期状態グラフの生成過程を示す図である。
【図９】状態決定処理の処理フローを示す図である。
【図１０】状態グラフの各エッジの実行回数の一例を示す図である。
【図１１】状態伝播処理の処理フローを示す図である。
【図１２】状態グラフの状態遷移例を示す図である。
【符号の説明】
１０  入力ソース・プログラム
２０  コンパイラ
３０  出力オブジェクト・プログラム
２００  フロントエンド処理部
２１０  中間コード
２２０  最適化処理部
２３０  コード生成部
２０１  字句解析部
２０２  構文解析部
２０３  意味解析部
２２１  前処理部
２２２  実行回数データ格納部
２２３  ファットスポットデータ格納部
２２４  ファットスポット特定部
２２５  状態グラフ処理部
２２６  スピルコード生成部
２２１１  制御フロー解析部
２２１２  生存範囲解析部
２２１３  実行回数設定部
【図１】
2004227025.tif 000008
【図２】
2004227025.tif 000009
【図３】
2004227025.tif 000010
【図４】
2004227025.tif 000011
【図５】
2004227025.tif 000012
【図６】
2004227025.tif 000013
【図７】
2004227025.tif 000014
【図８】
2004227025.tif 000015
【図９】
2004227025.tif 000016
【図１０】
2004227025.tif 000017
【図１１】
2004227025.tif 000018
【図１２】
2004227025.tif 000019