(57)【特許請求の範囲】
【請求項１】
ソースコードを取得して、複数のレジスタと該複数のレジスタを使いながら演算処理を実行する複数の演算器とを有するプロセッサでの実行が可能なオブジェクトコードを作成するコンパイル装置であって、
ソースコードを取得するソースコード取得部と、
ソースコード内に記述されたループを複数の命令群にアンローリングするアンローリング部と、
前記アンローリング部で生成された前記複数の命令群に出現する変数にレジスタを割り付けるレジスタ割付部と、
前記レジスタ割付部におけるレジスタの割付け結果に基づいてオブジェクトコードを生成するオブジェクトコード生成部と、
前記オブジェクトコード生成部で生成されたオブジェクトコードを出力するオブジェクトコード出力部とを有し、
前記レジスタ割付部が、前記複数のレジスタを複数のレジスタ群にグループ分けしたときの各１つのレジスタ群を該複数の命令群それぞれに割り当て、前記複数の命令群それぞれについて、当該命令群に出現する変数のうちの該複数の命令群に共通に使用される共通変数を除く個別変数の全てを当該命令群に割り当てられた１つのレジスタ群を構成するレジスタのみに割り付ける第１の割付部を含むことを特徴とするコンパイル装置。
【請求項２】
前記レジスタ割付部が、前記第１の割付部による、前記個別変数全てについてのレジスタへの割付けが不能であった場合に、該第１の割付部でレジスタの割付けが不能であった変数のレジスタへの割付けに代えて、該変数のメモリへの退避およびメモリからの復元を指示するコードを挿入するメモリ退避復元コード挿入部を含むことを特徴とする請求項１記載のコンパイル装置。
【請求項３】
前記レジスタ割付部が、前記第１の割付部による前記個別変数全てについてのレジスタへの割付けが不能であった場合に、前記複数の命令群のいずれにおいても、グループ分けされる前の前記複数のレジスタのいずれもが使用可能であるとして、該複数の命令群に出現する全ての変数をレジスタに割り付ける第２の割付部を含むことを特徴とする請求項１記載のコンパイル装置。
【請求項４】
前記レジスタ割付部が、前記第１の割付部による前記個別変数全てについてのレジスタへの割付けが不能であった場合に、前記複数の命令群に出現する全ての変数のうちの該第１の割付部ではレジスタの割り当てが不能であった全ての変数の参照回数の、プログラム全体の長さに対する比率と、閾値とを比較する比較部と、
前記比較部において前記比率が前記閾値未満であると判定された場合に、前記第１の割付部ではレジスタの割付けが不能であった変数のレジスタへの割付けに代えて、該変数のメモリへの退避およびメモリからの復元を指示するコードを挿入するメモリ退避復元コード挿入部と、
前記比較部において前記比率が前記閾値以上であると判定された場合に、前記複数の命令群のいずれにおいても、グループ分けされる前の前記複数のレジスタのいずれもが使用可能であるとして、該複数の命令群に出現する全ての変数をレジスタに割り付ける第２の割付部とを有することを特徴とする請求項１記載のコンパイル装置。
【請求項５】
プログラムを実行する演算処理装置で実行されて該演算処理装置を、ソースコードを取得して、複数のレジスタと該複数のレジスタを使いながら演算処理を実行する複数の演算器とを有するプロセッサでの実行が可能なオブジェクトコードを作成するコンパイル装置として動作させるコンパイルプログラムであって、
前記演算処理装置を、
ソースコードを取得するソースコード取得部と、
ソースコード内に記述されたループを複数の命令群にアンローリングするアンローリング部と、
前記アンローリング部で生成された前記複数の命令群に出現する変数にレジスタを割り付けるレジスタ割付部と、
前記レジスタ割付部におけるレジスタの割付け結果に基づいてオブジェクトコードを生成するオブジェクトコード生成部と、
前記オブジェクトコード生成部で生成されたオブジェクトコードを出力するオブジェクトコード出力部とを有し、
前記レジスタ割付部が、前記複数のレジスタを複数のレジスタ群にグループ分けしたときの各１つのレジスタ群を該複数の命令群それぞれに割り当て、前記複数の命令群それぞれについて、当該命令群に出現する変数のうちの該複数の命令群に共通に使用される共通変数を除く個別変数の全てを当該命令群に割り当てられた１つのレジスタ群を構成するレジスタのみに割り付ける第１の割付部を含むコンパイル装置として動作させることを特徴とするコンパイルプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本件は、ソースコードを取得してプロセッサでの実行が可能なオブジェクトコードを作成するコンパイル装置、および演算処理装置内で実行されてその演算処理装置をコンパイル装置として動作させるコンパイルプログラムに関する。
【背景技術】
【０００２】
プログラマがプログラムを作成するときに使用するプログラム言語で記述されたプログラムであるソースコードは、そのままではコンピュータのプロセッサで実行することはできない。そのプログラムをプロセッサで実行させるためには、そのソースコードを、プロセッサでの実行が可能な、そのプロセッサの構造が考慮されたオブジェクトコードに変換する必要がある。このコンパイルでは、レジスタ割付け処理が行なわれる。このレジスタ割付け処理は、コンパイラの中間言語に出現する変数が割り付けられた無制限の数の仮想レジスタを少数の実レジスタに割り付けることにより、変数を実レジスタに割り付ける作業である。
【０００３】
しかしながら、プロセッサによっては、実レジスタが複数のグループに分かれていて、別グループに属する実レジスタであっても共用可能であるが、１つの命令内で別グループの実レジスタを使用すると、同一グループ内の実レジスタを使用したときよりも命令の実行に遅延が生じる。
【０００４】
また、レジスタ割付結果によっては、複数の演算器を持つプロセッサであってもレジスタの読み書きによる依存関係が生まれて並列処理が大きく制限されるおそれがある。
【０００５】
ある演算器ではその演算器でしか使用できず他の演算器では使用できないという、演算器とレジスタとの対応関係が完全に固定されたシステムの場合の並列処理の工夫の提案は存在する。これに対し、本件は、複数の演算器と複数のレジスタを有し、複数の演算器のうちのどの演算器であっても複数レジスタのうちのどのレジスタをも使用可能なタイプのプロセッサを対象としている。このタイプのプロセッサを使う場合の演算処理の高速化のためのコンパイルの工夫は見当たらない。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平９−６２６３６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本件開示のコンパイル装置およびコンパイルプログラムの課題は、上記のタイプのプロセッサでの演算処理の高速化を図ることにある。
【課題を解決するための手段】
【０００８】
本件開示のコンパイル装置は、ソースコードを取得して、複数のレジスタと該複数のレジスタを使いながら演算処理を実行する複数の演算器とを有するプロセッサでの実行が可能なオブジェクトコードを作成するコンパイル装置である。
【０００９】
本件開示のコンパイル装置は、ソースコード取得部と、アンローリング部と、レジスタ割付部と、オブジェクトコード生成部と、オブジェクトコード出力部とを有する。
【００１０】
ソースコード取得部は、ソースコードを取得する。
【００１１】
アンローリング部は、ソースコード内に記述されたループを複数の命令群にアンローリングする。
【００１２】
レジスタ割付部は、アンローリング部で生成された複数の命令群に出現する変数にレジスタを割り付ける。
【００１３】
オブジェクトコード生成部は、レジスタ割付部におけるレジスタの割付け結果に基づいてオブジェクトコードを生成する。
【００１４】
オブジェクトコード出力部は、オブジェクトコード生成部で生成されたオブジェクトコードを出力する。
【００１５】
ここで、上記レジスタ割付部は、第１の割付部を含む。第１の割付部は、上記複数のレジスタを複数のレジスタ群にグループ分けしたときの各１つのレジスタ群を複数の命令群それぞれに割り当てる。そして、この第１の割付部は、それら複数の命令群それぞれについて、当該命令群に出現する変数のうちの複数の命令群に共通に使用される共通変数を除く個別変数の全てを当該命令群に割り当てられた１つのレジスタ群を構成するレジスタのみに割り付ける。
【００１６】
また、本件のコンパイルプログラムは、プログラムを実行する演算処理装置で実行されてその演算処理装置を本件のコンパイル装置として動作させるプログラムである。
【発明の効果】
【００１７】
本件開示のコンパイル装置およびコンパイルプログラムによれば、複数の演算器とそれら複数の演算器で共用可能な複数のレジスタとを有するプロセッサでの演算処理の高速化が図られる。
【図面の簡単な説明】
【００１８】
【図１】本件の第１実施形態のコンパイル装置の基本構成図である。
【図２】図１のコンパイル装置で作成されるオブジェクトコードの実行が予定されているプロセッサの概念図である。
【図３】第２実施形態のコンパイル装置で実行される処理の手順を示す図である。
【図４】ソースファイルに格納されているソースコードの一例を示す図である。
【図５】構文解析処理で生成される、中間言語で記述されたコードを示す図である。
【図６】アンローリング処理のフローチャートである。
【図７】図５に示す中間言語で記述されたコードがアンローリングされた状態を示した図である。
【図８】レジスタ割付け処理における、ループ内の変数をレジスタグループに分類する処理を示すフローチャートである。
【図９】図７に示す例における、変数（仮想レジスタ）が分配された配列Ｓを示す図である。
【図１０】レジスタグループ数Ｎ（ここではＮ＝２）に分類された実レジスタを示す図である。
【図１１】配列Ｂ（ｎ）の内容を示す図である。
【図１２】レジスタ割付け処理のフローチャートである。
【図１３】レジスタ割付けステップのフローチャートである。
【図１４】参照オペランド割付けステップのフローチャートである。
【図１５】定義オペランド割付けステップのフローチャートである。
【図１６】退避復元命令生成ステップのフローチャートである。
【図１７】実レジスタへの割付け結果を示した図である。
【図１８】図１０に代わるレジスタグループの例である。
【図１９】図１１に代わる、配列Ｂ（ｎ）の内容を示す図である。
【図２０】図１８，図１９に示す前提における、実レジスタへの割付けの結果を示した図である。
【図２１】図２０の状態が生じた場合の、図１２のステップＳ３４の処理結果を示す図である。
【図２２】１つのグループにまとめたレジスタを示す図である。
【図２３】アンローリングされた命令についてグループ分けせずにレジスタを使ったときの例ある。
【図２４】アンローリングされた命令についてグループ分けせずにレジスタを使ったときの例を示す図である。
【図２５】プロセッサの説明図である。
【図２６】命令の実行に遅延を生じさせない例を示す図である。
【図２７】命令の実行に遅延を生じさせる例を示す図である。
【図２８】並列性が低い例を示す図である。
【図２９】並列性が高い例を示す図である。
【発明を実施するための形態】
【００１９】
以下、本件の実施形態を説明する。
【００２０】
図１は、本件の第１実施形態のコンパイル装置の基本構成図である。このコンパイル装置１０は、ソースコードを取得して、プロセッサでの実行が可能なオブジェクトコードを作成する装置である。ただし、このコンパイル装置１０で作成されるオブジェクトコードは、複数のレジスタと該複数のレジスタを使いながら演算処理を実行する複数の演算器とを有するプロセッサで実行されるオブジェクトコードである。したがってこのオブジェクトコードは、この図１に示すプロセッサ２１で実行されることを予定するものではない。
【００２１】
図２は、図１のコンパイル装置で作成されるオブジェクトコードの実行が予定されているプロセッサの概念図である。
【００２２】
図１に示すプロセッサ２１は、その図１に示すＯＳ３０やコンパイルプログラム４０を実行するプロセッサである。これに対し、この図２に示すプロセッサ５０は、図１のコンパイル装置４０で作成されたオブジェクトコードの実行を担うプロセッサである。
【００２３】
コンパイル装置４０で作成されたオブジェクトコードは、例えばＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  光ディスク）等に書き込まれ、図２に示す構成のプロセッサを持つ、図１の演算処理装置とは別の演算処理装置ないし計算機にインストールされる。そしてこのオブジェクトコードは、そのインストール先の演算処理装置ないし計算機のプロセッサで実行される。
【００２４】
この図２に示すプロセッサ５０は、演算処理を実行する複数（図２に示す例では２個）の演算器５１ａ，５１ｂと、それら複数の演算器５１ａ，５１ｂでの共用が可能な複数（ここではｎ個）のレジスタ５２ａ，５２ｂ，…，５２ｎとを有する。
【００２５】
図１に戻って説明を続ける。
【００２６】
このコンパイル装置１０は、演算処理装置のハードウェア２０と、そのハードウェア２０上で実行されるオペレーティング・システム（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ  ＯＳ）３０と、そのＯＳ３０の管理下で実行されるコンパイルプログラム４０とを有する。
【００２７】
ハードウェア２０は、プロセッサ２１と、メモリ２２と、入力装置２３と、出力装置２４を有する。
【００２８】
プロセッサ２１では、ＯＳ３０やコンパイルプログラム４０が実行される。
【００２９】
また、メモリ２２は、データの記憶を担う。
【００３０】
また、ハードウェア２０を構成する入力装置２３は、このコンパイル装置１０の利用者により操作されるキーボードやマウス、ＣＤやＤＶＤ等の可搬型記録媒体の装填を受けてドライブするＣＤ／ＤＶＤドライブ、さらに通信回線（図示せず）を介しての外部からの情報受信を担う受信装置等を含む。
【００３１】
さらに出力装置２４は、画像を表示する画像表示装置や音声を出力するスピーカ、さらに、外部に向けて情報を送信する送信装置等を含む。
【００３２】
またＯＳ３０は、ハードウェア２０上で動作するプログラム（ここではコンパイルプログラム４０）の実行を制御する。
【００３３】
コンパイルプログラム４０は、ソースコード取得部４１、アンローリング部４２、レジスタ割付部４３、オブジェクトコード生成部４４、およびオブジェクトコード出力部４５を有する。これらの各部４１〜４５は、ここではプログラム部品の名称であるが、それらの各プログラム部品がプロセッサ２１で実行されたときの機能としての、コンパイル装置１０の各構成要素を指す名称でもある。
【００３４】
ソースコード取得部４１は、ソースコードを取得する。このソースコードは、入力装置２３から利用者が入力したものであってもよく、ＣＤやＤＶＤに記憶されているソースコードがインストールされたものであってもよい。あるいは外部から通信回線を経由して入力されたものであってもよい。
【００３５】
またアンローリング部４２は、ソースコード内に記述されたループを複数の命令群にアンローリングする。具体例の説明は後に譲る。
【００３６】
また、レジスタ割付部４３は、アンローリング部４２で生成された複数の命令群に出現する変数にレジスタを割り付ける。このレジスタ割付部４３は、第１の割付部４３１、比較部４３２、メモリ退避復元コード挿入部４３３、および第２の割付部４３４を有する。
【００３７】
第１の割付部４３１は、図２に示すプロセッサ５０を構成する複数のレジスタ５２ａ，５２ｂ，…，５２ｎを複数のレジスタ群にグループ分けしたときの各１つのレジスタ群を上記の複数の命令群それぞれに割り当てる。そして、この第１の割付部４３１は、それら複数の命令群それぞれについて、当該命令群に出現する変数のうちの複数の命令群に共通に使用される共通変数を除く個別変数の全てを当該命令群に割り当てられた１つのレジスタ群を構成するレジスタのみに割り付ける。
【００３８】
また、比較部４３２は、第１の割付部４３１による個別変数全てについてのレジスタへの割付けが不能であった場合に作用する。この比較部４３２は、上記複数の命令群に出現する全ての変数のうちの第１の割付部４３１ではレジスタの割り当てが不能であった全ての変数の参照回数の、プログラム全体の長さに対する比率と、閾値とを比較する。
【００３９】
メモリ退避復元コード挿入部４３３は、比較部４３２において上記比率が閾値未満であると判定された場合に動作する。このメモリ退避復元コード挿入部４３３は、第１の割付部４３１ではレジスタの割付けが不能であった変数のレジスタへの割付けに代えて、レジスタへの割付け不能な変数のメモリ２２への退避およびメモリ２２からの復元を指示するコードを挿入する。
【００４０】
第２の割付部４３４は、比較部４３２において上記比率が閾値以上であると判定された場合に動作する。この第２の割付部４３４は、複数の命令群のいずれにおいても、グループ分けされる前の複数のレジスタ５２ａ，５２ｂ，…，５２ｎ（図２参照）のいずれもが使用可能であるとして、それら複数の命令群に出現する全ての変数をレジスタに割り付ける。
【００４１】
さらに、オブジェクトコード生成部４４は、レジスタ割付部４３におけるレジスタの割付け結果に基づいてオブジェクトコードを生成する。
【００４２】
さらにオブジェクトコード出力部４５は、オブジェクトコード生成部４４で生成されたオブジェクトコードを出力する。ここでの出力は、例えば、ＣＤ等の可搬型記録媒体への書込みや、あるいは通信回線を介して外部に送信することなど、どのような出力であってもよい。
【００４３】
以上で、概括的な第１実施形態の説明を終了し、以下では、より具体的な第２実施形態を説明する。
【００４４】
図３は、第２実施形態のコンパイル装置で実行される処理の手順を示す図である。ここに示す処理は、図１に示すハードウェア２０およびＯＳ３０の下で、第２実施形態としてのコンパイルプログラムが実行されることにより実現する処理である。演算処理装置のハードウェアおよびＯＳは図１のものと代わるところがないため、ここでは必要に応じて図１を参照することとする。また、この第２実施形態で作成されるオブジェクトコードも、図２に示す構成のプロセッサ５０で実行されるオブジェクトコードである。
【００４５】
この図３には、ソースファイル６０と、オブジェクトファイル８０が示されている。
【００４６】
ソースファイル６０には、ソースコード用のプログラム言語で記述されたソースコードが格納されている。
【００４７】
また、オブジェクトファイル８０には、図２に示すプロセッサ５０で実行可能なオブジェクトコード用のプログラム言語（アセンブラなど）で記述されたオブジェクトコードが格納される。
【００４８】
また、この図３には、この第２実施形態のコンパイル装置で実行されるコンパイル処理７０として、構文解析処理７１、アンローリング処理７２、レジスタ割付け処理７３、命令スケジューリング処理７４およびコード生成処理７５が示されている。
【００４９】
前述の第１実施形態との対応関係は次の通りである。
【００５０】
図３に矢印Ａで示す、ソースファイル６０を受け取る処理が、図１のソースコード取得部４１に相当する。また構文解析処理７１は、その次のアンローリング処理７２の前処理の役割りを担っており、構文解析処理７１とアンローリング処理７２を合わせた処理が図１のアンローリング部４２に相当する。さらに、レジスタ割付け処理７３がレジスタ割付部４３に相当する。また、命令スケジューリング処理７４は、その次のコード生成処理７５の前処理の役割りを担っており、それら命令スケジューリング処理７４とコード生成処理７５とを合わせたものが図１のオブジェクトコード生成部４４に対応する。さらに、矢印Ｂで示す、コード生成処理７５で生成されたオブジェクトコードがファイリングされたオブジェクトファイル７０を出力する処理が、図１のオブジェクトコード出力部４５に相当する。
【００５１】
ここでは、図３に示す処理７０の概要を説明する。その後、詳細な具体例を説明する。
【００５２】
構文解析処理７１では、受け取ったソースファイル６０の構文解析を行なって中間言語に変換する。この中間言語では、個数に制限のない仮想レジスタが使用され、出現する変数に仮想レジスタが割り当てられる。したがってここでは仮想レジスタと変数を区別する必要はなく、以下では特に断らない限りそれらの用語を区別せずに使用することがある。
【００５３】
構文解析処理７１が行なわれたあと、アンローリング処理７２が行なわれる。このアンローリング処理７２では、中間言語に変換されたプログラム内のループが複数の命令群にアンローリングされる。
【００５４】
レジスタ割付け処理７４では、アンローリング処理７２によって生成された複数の命令群を含む、中間言語で記述されたコード中の変数（仮想レジスタ）に、実際に使用できる実レジスタ（図２に示すレジスタ５２ａ，５２ｂ，…，５２ｎ）が割り付けられる。
【００５５】
命令スケジューリング処理７５では、複数の演算器５１ａ，５１ｂ（図２参照）での処理の並列度を上げるように命令のスケジューリングが行なわれる。
【００５６】
コード生成処理７５では、命令スケジューリング処理７４でのスケジューリングに従うオブジェクトコードの生成が行なわれる。
【００５７】
以下、図３に示す各種処理７１〜７５について具体的に説明する。
【００５８】
図４は、ソースファイルに格納されているソースコードの一例を示す図である。本実施形態ではプログラムのループの部分に関心があり、ここではループに関する部分のみ例示している。
【００５９】
（１）行目では、変数ＩとＮが整数であることが定義されている。
【００６０】
（２）行目では、配列Ａ（１０），配列Ｂ（１０），変数Ｃ，配列Ｄ（１０），変数ｔ１とｔ２とｔ３のいずれもが実数であることが定義されている。
【００６１】
（２）行目と（ｎ）行目との間（符号（ａ）で示す部分）で、Ｎ，Ａ（１０），Ｂ（１０），Ｃについて具体的な数値が定義されているものとする。
【００６２】
（ｎ）行目は、ループの始点であって、Ｉ＝１を初期値としＩを１ずつインクリメントしながら、Ｉ＝Ｎとなるまで、（ｎ＋１）行目から（ｎ＋４）行目までの処理を繰り返し実行すべきことが示されている。
【００６３】
（ｎ＋１）行目は、Ａ（Ｉ）とＣを加算してｔ１に格納すべきことをあらわしている。
【００６４】
（ｎ＋２）行目は、ｔ１からＢ（Ｉ）を引き算してｔ２に格納すべきことをあらわしている。
【００６５】
（ｎ＋３）行目は、Ａ（Ｉ）とｔ２を乗算してｔ３に格納すべきことをあらわしている。
【００６６】
（ｎ＋４）行目は、Ｂ（Ｉ）をｔ３で割ってＤ（Ｉ）に格納すべきことをあらわしている。
【００６７】
（ｎ＋５）行目は、ループの終点をあらわしている。
【００６８】
ここでは、この図４に示すソースコードを基にして具体例を説明する。
【００６９】
図５は、構文解析処理７１で生成される、中間言語で記述されたコードを示す図である。
【００７０】
この図５や、以下に説明する各図に出現するＰＲｎ（ｎ＝１，２，…）は仮想レジスタをあらわしている。
【００７１】
また、この図５において、Ａ（Ｉ），Ｂ（Ｉ），Ｄ（Ｉ）はメモリ上の配列を意味しており、Ａ（Ｉ），Ｂ（Ｉ）（Ｉ＝１，２，…，Ｎ）には、この図５に示す部分よりも前にそのメモリ上の配列数値が格納されているものとする。また、この図５に示す部分よりも前にＮの値も定義されており、さらに、Ｃの値も定義されて仮想レジスタＰＲ２に対応づけられているものとする。
【００７２】
図５のコードの（１）行目は、Ｉに１を代入すべきことが示されている。
【００７３】
（２）行目は、ループの始点であって、（１１）行目に記述された条件を満足するときの、その（１１）行目からの戻り点である。
【００７４】
（３）行目は、メモリ上のＡ（Ｉ）の内容を仮想レジスタＰＲ１に格納すべきことが示されている。
【００７５】
（４）行目は、ＰＲ１（Ａ（Ｉ）に対応する）の内容とＰＲ２（Ｃに対応する）の内容を加算してＰＲ３（ｔ１に対応する）に格納すべきことが示されている。
【００７６】
（５）行目は、メモリ上のＢ（Ｉ）の内容を仮想レジスタＰＲ４に格納すべきことが示されている。
【００７７】
（６）行目は、ＰＲ３（ｔ１に対応する）の内容からＰＲ４（Ｂ（Ｉ）に対応する）の内容を引き算してＰＲ５（ｔ２に対応する）に格納すべきことが示されている。
【００７８】
（７）行目は、ＰＲ１（Ａ（Ｉ）に対応する）の内容とＰＲ５（ｔ２に対応する）とを乗算してＰＲ６（ｔ３に対応する）に格納すべきことが示されている。
【００７９】
（８）行目は、ＰＲ４（Ｂ（Ｉ）に対応する）の内容をＰＲ６（ｔ３に対応する）の内容で割り算してＰＲ７（Ｄ（Ｉ）に対応する）に格納すべきことが示されている。
【００８０】
（９）行目は、ＰＲ７の内容をメモリ上のＤ（Ｉ）に格納すべきことが示されている。
【００８１】
（１０）行目は、Ｉに１を加えて再びＩとすることが示されている。
【００８２】
（１１）行目は、Ｉ＜Ｎ＋１ならばＬＡＢＥＬ（（２）行目）に戻るべきことが示されている。
【００８３】
図３に示す構文解析処理７１では、一例として、図４に示すソースコードが図５に示す、中間言語であらわされたコードに変換される。
【００８４】
図６は、アンローリング処理のフローチャートである。また図７は、図５に示す中間言語で記述されたコードがアンローリングされた状態を示した図である。
【００８５】
尚ここでは、アンローリングされた部分のみ関心があり、図７には、図５のうちの（３）行目から（９）行目に相当する部分のみ示されている。実際には、例えば図７に示す部分の後に、（１０），（１１）に対応する処理（但し、（１０）に相当する処理ではＩに４が加えられる）が実行されるなど、さらにいくつかの処理が追加される。
【００８６】
図７では、図５に示すループが４展開されている。アンローリング処理７２（図３参照）が実行されると各命令に展開番号が埋め込まれる。ただし、図７では、分かり易さのため、展開番号を命令とは別にして命令に並べて示してある。
【００８７】
図５の（３）〜（９）行目と図７とを比較すると、図７では、図５の（３）〜（９）行目の各命令からなる命令群が４回繰り返され、各命令群について１〜４の各展開番号が付されている。また、各展開番号１〜４の命令群に出現する変数が各展開番号１〜４ごとに異なる仮想レジスタに割り当てられるように仮想レジスタの番号（ＰＲｎのｎ）が変更されている。ただし、各展開番号１〜４のそれぞれでは、各展開番号１〜４の命令群で共通に使用される共通変数（共通に使用される仮想レジスタ）であるＰＲ２（図４のＣに対応する）については、全ての展開番号１〜４で共通に使用されている。
【００８８】
図６のフローチャートに基づいてアンローリング処理７２を説明する。
【００８９】
ここでは先ず、カウンタに１が設定され（ステップＳ１１）、元の命令（ここでは図５の（３）行目）がコピーされ（ステップＳ１２）、カウンタ（ここでは１）が展開番号としてその命令に設定される（ステップＳ１３）。ステップＳ１４ではループ内にまだ命令が残っているか否かが判定される。ここでは、図５の（３）行目がコピーされただけであって、（４）〜（９）行目が残っているからステップＳ１２に戻り、今度は図５の（４）行目について、ステップＳ１２，Ｓ１３の処理が行なわれる。同様にして（５）行目〜（９）行目についてステップＳ１２，Ｓ１３の処理が順次繰り返される。ステップＳ１２，Ｓ１３の処理が（９）行目まで終了すると、ステップＳ１４を経由してステップＳ１５に進み、カウンタがカウントアップされる。ステップＳ１６ではカウンタが展開数（ここでは４）を超えたか否かが判定され、展開数４を超えるまで、ステップＳ１２〜Ｓ１５の処理が繰り返される。ステップＳ１６で展開数４を超えたことが判定されると、ステップＳ１７に進み、コピーした命令が参照する変数（仮想レジスタ）が展開ごとにリネームされる。ただし、各展開番号１〜４で共通に使用される変数（仮想レジスタ）（図５に示す例ではＰＲ２）はリネームされずにそのまま残される。
【００９０】
以上のアンローリング処理により、図５のコードが図７のコードにアンローリングされる。
【００９１】
図８は、レジスタ割付け処理７３における、ループ内の変数をレジスタグループに分類する処理を示すフローチャートである。この図８の処理は、変数をレジスタに割り付ける処理（図１２参照）の前準備の処理である。
【００９２】
ここでは、ここでのコンパイルにより生成されるオブジェクトコードの実行が想定されているプロセッサ５０（図２参照）で使用可能なレジスタが複数のレジスタ群にグループ分けされる。このグループ分けされるレジスタ群の数Ｎは、使用可能なレジスタの数とアンローリング展開数Ｌ（ここではＬ＝４）とから決定される（ステップＳ２１）。Ｎは２以上Ｌ以下である。ここではＮ＝２とする。
【００９３】
次に配列Ｓ（Ｎ＋１），Ｂ（Ｎ＋１）の領域を確保する（ステップＳ２２）。ここで、配列Ｓ（Ｎ＋１）は、レジスタグループごとに変数（仮想レジスタ）を分類するための配列である。また、配列Ｂ（Ｎ＋１）はレジスタ（実レジスタ）をグループごとに分類するための配列である。配列の数がＮ（レジスタグループの数）ではなく、Ｎ＋１となっているのは、複数の展開番号に跨って共通に使用される共通変数をレジスタグループとは別に分類するためである。またここでは、ループ内に出現するすべての変数（仮想レジスタ）の集合をＶとする。
【００９４】
ステップＳ２３では、変数（仮想レジスタ）の集合Ｖ内の任意の変数（仮想レジスタ）ｖが取り出される。そして、その変数ｖが出現する命令が全て同一の展開番号に属する命令であるか否か、すなわち、その変数ｖがある１つの展開番号内の命令にのみ出現する変数であるか否かが判定される（ステップＳ２４）。そして、その変数ｖが出現する命令が全て同一の展開番号に属する命令であるときは、その変数ｖが出現する展開番号によって配列Ｓに分配される。ここでは、展開数は４、レジスタグループ数Ｎは２なので、Ｓ（１）には、展開番号１と３の変数（仮想レジスタ）が分配され、Ｓ（２）には展開番号２と４の変数（仮想レジスタ）が分配される。
【００９５】
ステップＳ２４において、ｖが複数の展開番号の命令に跨って出現すると判定されたときは、ステップＳ２６に進み、その変数ｖが配列Ｓ（Ｎ＋１）に加えられる。
【００９６】
以上の処理が集合Ｖ内の全ての変数ｖについて実行された後、今度は配列Ｓ（ｎ）に対応する配列Ｂ（ｎ）が作成される。ここで、Ｂ（ｎ）はｎ番目のレジスタグループに属するレジスタの集合を意味する。Ｂ（Ｎ＋１）は特別な集合であり、各レジスタグループに属するレジスタすべてを含むレジスタの集合である。
【００９７】
さらに、ステップＳ２８において命令群全体をサーチして、メモリへの退避／メモリからの復元用としていくつのレジスタが必要か調べ、必要な数のレジスタを予約しておく。
【００９８】
図９は、図７に示す例における、変数（仮想レジスタ）が分配された配列Ｓを示す図である。
【００９９】
Ｓ（１）には、展開番号１の命令群のみに出現する変数（仮想レジスタ）と展開番号３の命令群のみに出現する変数（仮想レジスタ）が分配されている。またＳ（２）には、展開番号２の命令群のみに出現する変数（仮想レジスタ）と展開番号４の命令群のみに出現する変数が分配されている。さらに、Ｓ（３）には、複数の展開番号の命令群に共通的に出現する変数（仮想レジスタ）が分配されている。
【０１００】
図１０は、レジスタグループ数Ｎ（ここではＮ＝２）に分類された実レジスタを示す図である。
【０１０１】
ここでは、使用可能なレジスタがＲ０〜Ｒ１１の１２個（図２のｎ＝１２）存在し、Ｒ０〜Ｒ５がグループ１に、Ｒ６〜Ｒ１１がグループ２に分かれている。
【０１０２】
図１１は、配列Ｂ（ｎ）の内容を示す図である。
【０１０３】
Ｂ（１）には、レジスタどうしの間での定義参照（演算）で使用できるレジスタとしてＲ０〜Ｒ３、メモリへの退避／メモリからの復元用の予約レジスタとしてＲ４，Ｒ５が分配されている。また、Ｂ（２）には、レジスタどうしの間での定義参照で使用できるレジスタとしてＲ６〜Ｒ７、予約レジスタとしてＲ１０，Ｒ１１が分配されている。さらにＢ（３）には、全てのレジスタＲ０〜Ｒ１１が配置されている。これら全てのレジスタのうちのＲ１０，Ｒ１１は予約レジスタとして設定されており、使用できるレジスタはＲ０〜Ｒ９である。
【０１０４】
図１２は、レジスタ割付け処理のフローチャートである。
【０１０５】
図３に示すレジスタ割付け処理７３では、図８に示す前処理に続いて図１２に示すレジスタ割付け処理が実行される。
【０１０６】
ここでは、先ず、任意の変数ｖがＳ（ｎ）（図９参照）に含まれる場合、Ｂ（ｎ）（図１１参照）のレジスタしか利用することができないとしてレジスタ割付けを実行する。退避復元用のレジスタは別に予約されており、ここでは、図１１に示す「使用できるレジスタ」のみに割付けが行なわれる。
【０１０７】
ステップＳ３２では、「使用できるレジスタ」がすべての変数に割付けることができたか否かが判定される。「使用できるレジスタ」がすべての変数に割付けることができたときは、レジスタ割付け処理が終了する。「使用できるレジスタ」のみでは全ての変数にレジスタを割付けることができなかったときは、次に、割付けることができなかった変数の参照回数の合計がプログラムの全体に対して十分に小さいか否かが判定される（ステップＳ３３）。具体的には、展開番号１〜４の全てについて割り付けることができなかった変数の参照回数の合計が数えられ、その参照回数の、プログラム全体のステップ数に対する比率と閾値とが比較され、その比率が閾値未満か閾値以上かが判定される。その比率が閾値未満の場合、すなわち、割付けることができなかった変数の参照回数の合計がプログラム全体の大きさに対して十分に小さい場合はステップＳ３４に進み、そうでない場合はステップＳ３５に進む。
【０１０８】
ステップＳ３４では、予約したレジスタ（図１１参照）を使って、レジスタに割付けることができなかった変数をメモリに退避復元する命令が生成され、この割付け処理を終了する。
【０１０９】
一方、ステップＳ３５では、任意の変数ｖにすべてのレジスタを利用できると考えてレジスタ割付けを実行する。ただし、ステップＳ３１の場合と同様、退避復元用のレジスタは別に予約しておく。
【０１１０】
ステップＳ３６では、ステップＳ３５においてレジスタをすべての変数に割付けることができたか否かが判定され、すべての変数にレジスタを割付けることができたときは、レジスタ割付け処理を終了する。レジスタをすべての変数には割付けることができなかったときは、予約したレジスタを使って、レジスタに割付けることができなかった変数メモリに退避復元する命令が生成される（ステップＳ３７）。
【０１１１】
図１３は、レジスタ割付けステップのフローチャートである。このレジスタ割付けステップは、図１２のステップＳ３１およびステップＳ３５の双方で実行されるが処理のフローは同一である。ただし、ステップＳ３１とステップＳ３５では、割付けに利用できるレジスタの数が相違する。
【０１１２】
図１３のフローに従って、図７に示すようにアンローリングされた命令を上から順に見ていき（ステップＳ４１）、参照オペランドの割付け（ステップＳ４２）、および定義オペランドの割付け（ステップＳ４３）を、すべての命令について実行する（ステップＳ４４）。
【０１１３】
ここで、参照オペランドとは、命令の左側の変数である。例えば展開番号１中の
ＡＤＤ  Ｒ１，Ｒ０  ⇒  Ｒ２
における変数（仮想レジスタ）Ｒ１，Ｒ０が参照オペランドである。また、命令の右側の変数、ここではＲ２が定義オペランドである。
【０１１４】
図１４は、参照オペランド割付けステップ（図１３のステップＳ４２）のフローチャートである。
【０１１５】
ここでは、命令の参照オペランドが調べられ（ステップＳ５１）、その参照オペランドがその命令以降には参照がない最後の参照か否かが判定され、最後の参照であったときはその参照オペランドに割当てられているレジスタが解放される（ステップＳ５３）。この処理をすべての参照オペランドについて行なう（ステップＳ５４）。
【０１１６】
図１５は、定義オペランド割付けステップ（図１３のステップＳ４３）のフローチャートである。
【０１１７】
ここでは、命令の定義オペランドが調べられ（ステップＳ６１）、その定義オペランドがレジスタに割付けられているか否かが判定される（ステップＳ６２）。その定義オペランドがレジスタに割付けられていれば次の定義オペランドの調べに移り（ステップＳ６６）、その定義オペランドがレジスタに割付けられていないときは変数に割付けられていないレジスタが余っているか否かが調べられる（ステップＳ６３）。変数に割付けられていないレジスタが余っているときは、その定義オペランドにその余っているレジスタが割付けられ（ステップＳ６４）、一方、レジスタが余っていないときはその定義オペランド（変数）が集合ＳＰＩＬＬに追加される（ステップＳ６５）。この集合ＳＰＩＬＬは、レジスタに割付けることができなかった変数（仮想レジスタ）の集合である。以上の処理がすべての定義オペランドに対し行なわれる。
【０１１８】
図１６は、退避復元命令生成ステップ（図１２のステップＳ３４およびステップＳ３７）のフローチャートである。
【０１１９】
ここでは、レジスタを割付けることができなかった集合ＳＰＩＬＬの中から任意の変数ｖが取り出される（ステップＳ３７）。
【０１２０】
次いで、その変数ｖに対してメモリ上の一時領域Ｍが決められる（ステップＳ７２）。
【０１２１】
さらに、その変数ｖの定義に対して一時領域Ｍへストアする命令を生成する。この命令で用いるストアのためのレジスタは、退避復元用に予約しておいたレジスタが使用される（図１１参照）。
【０１２２】
次に、変数ｖの参照に対して一時領域Ｍからレジスタにロードする命令が生成される（ステップＳ７４）。ここでも、ロードするためのレジスタとして退避復元用に予約しておいたレジスタが使用される。
【０１２３】
以上の処理が、集合ＳＰＩＬＬ内の全ての変数について行なわれる（ステップＳ７５）。
【０１２４】
図１７は、実レジスタへの割付け結果を示した図である。この図１７は、図７に示すアンローリング処理された命令にあらわれた変数を図１０に示す数のレジスタが存在することを前提にしてレジスタに割り付けたときの割付け結果である。
【０１２５】
この図１７では、各展開番号ごとに、その展開番号の命令群のみにあらわれる全ての変数が、グループ分けされた１つのグループに属するレジスタに割付けられている。ただし、図１７に×印を付した２つの命令については、図１０に示すグループ１とグループ２との双方が参照されている。この×印を付した命令の数が多くなってくると、その分、処理の並列化の妨げや処理速度の低下を来たすおそれがあるが、図１７に示す例では×印は２つの命令にとどまっている。
【０１２６】
次に、レジスタが足りない場合の例を示す。
【０１２７】
図１８は、図１０に代わるレジスタグループの例である。
【０１２８】
図１０では、各グループには、６つのレジスタが属しているが、この図１８では各グループに５つのレジスタしか存在しない。
【０１２９】
図１９は、図１１に代わる、配列Ｂ（ｎ）の内容を示す図である。この図１９では、図１１と比べ「使用できるレジスタ」の数が減少している。
【０１３０】
図２０は、図１８，図１９に示す前提における、実レジスタへの割付け（図１２のステップＳ３１）の結果を示した図である。
【０１３１】
変数（仮想レジスタ）に割付けるレジスタが不足し、図中に★印を付した変数（仮想レジスタ）がレジスタに割付けられずに残っている。
【０１３２】
図２１は、図１２のステップＳ３１で図２０の状態が生じた場合の、図１２のステップＳ３４の処理結果を示す図である。
【０１３３】
図中に△印を付した部分に、メモリへの退避／メモリからの復元の命令が挿入されている。
【０１３４】
メモリへの退避／メモリからの復元の処理はレジスタ間のデータ移動と比べ大幅に時間がかかるが、頻度が少ないときは、メモリへの退避／メモリからの復元の処理を挿入することで並列化を妨げる要因を増やさずに済む。
【０１３５】
次に、図１２のステップＳ３５の例を説明する。このステップＳ３５では、レジスタをグループ分けせずに１つのグループにまとめ、この１つのグループ内のレジスタを全ての展開番号の命令で利用できるものとして、レジスタ割付けが行なわれる。
【０１３６】
図２２は、１つのグループにまとめたレジスタを示した図である。
【０１３７】
図２３は、図７のようにアンローリングされた命令についてグループ分けせずにレジスタを使ったときの例である。
【０１３８】
ここでは、メモリへの退避／メモリからの復元の処理を行なわなくても、全ての変数にレジスタが割付けられている。これは、メモリへの退避／メモリからの復元の処理の数が多過ぎるとき、並列処理をあきらめてレジスタに割付けることを意味している。すなわち、展開番号１〜４にわたって同じレジスタが割付けられており、複数の演算器での並列処理が難しい状況となっている。例えば８番目のＬＯＡＤはその直前のＳＴＯＲＥとの間でレジスタの依存関係があるので、これらの命令を並列に実行することはできない。
【０１３９】
図２３では、使用するレジスタの数をできるだけ減らすために同じレジスタを使い回すようにしている。処理の並列性を少しでも向上させるためになるべく違うレジスタを使うように割り当ててもよい。
【０１４０】
図２４は、図２３と同様、図７に示すようにアンローリングされた命令についてグループ分けせずにレジスタを使ったときの例を示す図である。ただしここでは、できるだけ違うレジスタを使うように工夫されている。例えば４番目の命令ＳＵＢの定義では、Ｒ２が解放されているので図２３に示すように再びＲ２を使うこともできるが、図２４ではＲ４が割付けられている。できるだけ違うレジスタを使う工夫をした結果、図２４の８番目のＬＯＡＤでは、その上のＳＴＯＲＥやＤＩＶと同時に実行することができる。ただし、ここではレジスタグループについては考慮されていないため、図２４に×印で示すように、レジスタグループ（図１８参照）が依存している命令が多数発生している。このため、図２１に示すメモリへの退避／メモリからの復元の命令を挿入したときと比べると並列性は低い。
【０１４１】
次に、上記の実施形態のメリットについて説明する。
【０１４２】
図２５は、あるプロセッサの説明図である。
【０１４３】
ここに示すプロセッサは、３つの演算器Ａ，Ｂ，Ｃと３つのレジスタグループＡ，Ｂ，Ｃを有する。演算器ＡはレジスタグループＡを直接参照することができるが、他のレジスタグループＢ，Ｃは直接には参照できず、参照しようとすると時間がかかる。他の演算器Ｂ，Ｃやレジスタグループも同様である。この場合、１つの命令に複数のレジスタグループに属するレジスタが依存すると命令の実行に時間がかかることとなる。
【０１４４】
図２６は、命令の実行に遅延を生じさせない例を示す図である。
【０１４５】
ここでは、レジスタグループＡのレジスタをａ１，ａ２，ａ３，…とし、レジスタグループＢのレジスタをｂ１，ｂ２，ｂ３，…とする。
【０１４６】
図２６に示す命令列では全てレジスタグループＡのレジスタを使用しているので命令の遅延は生じない。
【０１４７】
図２７は、命令の実行に遅延を生じさせる例を示す図である。
【０１４８】
図２７に示す命令列には、レジスタグループＡのレジスタとレジスタグループＢのレジスタが混在しており、命令の実行に遅延が生じる。
【０１４９】
上述の実施形態では、グループ分けされたレジスタをできる限り使おうとしているため、命令の実行に遅延が生じる要素が最小限に抑えられ、高速処理が可能となる。
【０１５０】
また、本実施形態のもう１つのメリットは並列性の点である。図２５に示すようなレジスタグループがハードウェア上では存在しておらず全てのレジスタが平等に参照可能であったとしても、レジスタを本実施形態のようにグループ分けすることにより並列性が高められ処理速度が向上する。
【０１５１】
図２８は、並列性が低い例を示す図である。
【０１５２】
ここではレジスタはグループ分けされないまま割付け処理が行なわれ、その結果、（３）行目でレジスタｒ１が解放されてからでないと（５）行目のＬＯＡＤ命令は実行できない。すなわち（５）行目のＬＯＡＤ命令は（４）行目のＳＴＯＲＥ命令と同時にしか実行できない。
【０１５３】
図２９は、並列性が高い例を示す図である。
【０１５４】
ここではレジスタはグループ分けされており、したがって（１）行目と（５）行目の命令を並列に実行することができる。
【０１５５】
上述の実施形態では、できる限り、グループ分けされたレジスタを使おうとしているため、並列性が向上する。したがって、図５に示すような、レジスタがハードウェア的にグループ分けされたプロセッサでなくても複数の演算器を使った並列処理により処理速度が向上する。
【符号の説明】
【０１５６】
１０，４０    コンパイル装置
２０    ハードウェア
２１，５０    プロセッサ
２２    メモリ
２３    入力装置
２４    出力装置
３０    オペレーティング・システム（ＯＳ）
４０    コンパイルプログラム
４１    ソースコード取得部
４２    アンローリング部
４３    レジスタ割付部
４４    オブジェクトコード生成部
４５    オブジェクトコード出力部
５１ａ，５１ｂ    演算器
５２ａ，５２ｂ，５２ｎ    レジスタ
６０    ソースファイル
７０    コンパイル処理
７１    構文解析処理
７２    アンローリング処理
７３    レジスタ割付け処理
７４    命令スケジューリング処理
７５    コード生成処理
８０    オブジェクトファイル
４３１    第１の割付部
４３２    比較部
４３３    メモリ退避復元コード挿入部
４３４    第２の割付部
【図１】
0005402752.tif 000002
【図２】
0005402752.tif 000003
【図３】
0005402752.tif 000004
【図４】
0005402752.tif 000005
【図５】
0005402752.tif 000006
【図６】
0005402752.tif 000007
【図７】
0005402752.tif 000008
【図８】
0005402752.tif 000009
【図９】
0005402752.tif 000010
【図１０】
0005402752.tif 000011
【図１１】
0005402752.tif 000012
【図１２】
0005402752.tif 000013
【図１３】
0005402752.tif 000014
【図１４】
0005402752.tif 000015
【図１５】
0005402752.tif 000016
【図１６】
0005402752.tif 000017
【図１７】
0005402752.tif 000018
【図１８】
0005402752.tif 000019
【図１９】
0005402752.tif 000020
【図２０】
0005402752.tif 000021
【図２１】
0005402752.tif 000022
【図２２】
0005402752.tif 000023
【図２３】
0005402752.tif 000024
【図２４】
0005402752.tif 000025
【図２５】
0005402752.tif 000026
【図２６】
0005402752.tif 000027
【図２７】
0005402752.tif 000028
【図２８】
0005402752.tif 000029
【図２９】
0005402752.tif 000030