(57)【要約】【課題】  キャッシュを有効に利用可能なように変数をキャッシュ上に配置することができるコンパイラを提供すること。【解決手段】  １つの演算式内で同種の複数の変数を使用しているかを判定するステップと、その判定結果に基づき、同種の変数がキャッシュの連続領域に配置されるようにキャッシュ上での配置アドレスを決定するステップとを備えることを特徴とする。【選択図】      図１
2005100240.tif 000002
【特許請求の範囲】
【請求項１】
１つの演算式内で同種の複数の変数を使用しているかを判定するステップと、その判定結果に基づき、同種の変数がキャッシュの連続領域に配置されるようにキャッシュ上での配置アドレスを決定するステップとを備えることを特徴とするコンパイラ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソースコードを実行形式のコードに変換するコンパイラに関するものである。
【背景技術】
【０００２】
従来において、（株）ルネサス テクノロジのＳｕｐｅｒＨ ＲＩＳＣ Ｅｎｇｉｎｅ ファミリのマイコン ７７５０シリーズ（以下、ＳＨ４と呼ぶ）には、データ用にコピーバック・ライトスルー選択可能な１６Ｋバイトのオペランドキャッシュが設けられている。
オペランドキャッシュは、図７に示すように、５１２本のキャッシュラインで構成され、各キャッシュラインはキャッシュされるデータのメモリアドレスのビット２８〜ビット１０を格納するタグ、１キャッシュラインあたり３２バイトのデータを格納するデータ部、キャッシュに有効なデータが格納されているかを示すＶビット、キャッシュとメモリとが一致しているかを示すＵビットで構成されている。なお、Ｕビットは、キャッシュミスした場合に、新たなデータをキャッシュに読み込むが、その際に、Ｕビットを参照しキャッシュとメモリが不一致ならばキャッシュのデータをメモリに書き戻すために使用する。すなわち、キャッシュミスした場合に、新たなデータをキャッシュに読み込むが、その際に、Ｕビットを参照しキャッシュとメモリが不一致ならばキャッシュのデータをメモリに書き戻す。
オペランドキャッシュを利用する際は、メモリの実効アドレスのビット１３〜ビット５で示されるインデックス（配列番号）のキャッシュラインからタグ、Ｕ、Ｖビットを読み出し（図７のＳ１）、メモリの実効アドレスのビット２８〜ビット１０とタグを比較する（図７のＳ２）。比較の結果、一致し、かつＶビットが有効であれば、キャッシュヒットとなり、キャッシュラインのデータ部からメモリの実効アドレスのビット４〜ビット０で示されるアドレスのデータの読み出し、または書き込みを行う（図７のＳ３）。
なお、この種の従来技術として、次の特許文献１に示されるような技術がある。
【特許文献１】特開平５−２５７８１４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ところで、ソースコードで記述される変数の種類には大きく分けて３つある。すなわち、図８に示すように関数func(){…}を定義しているソースコードにおいて（１）関数内部で宣言され、その関数の実行時にスタックからメモリを確保し、関数内でのみ使用可能なローカル変数、（２）関数外部で宣言され、ソースファイル単位にコンパイルし作成されたオブジェクトファイルから１つの実行ファイルに纏めるリンク時にメモリ上のアドレスが決まり、どの関数からも使用可能なグローバル変数、（３）関数内部で“ｓｔａｔｉｃ”を付加して宣言され、リンク時にメモリ上のアドレスが決まり、宣言した関数内でのみ使用可能な静的変数がある。
グローバル変数と静的変数はリンク時にアドレスを割り当てることができ、連続したアドレスに変数を配置することが可能である。しかし、ローカル変数は関数の実行時にスタックから割り当てられるので、グローバル変数、静的変数とローカル変数を連続したアドレスに配置することは出来ないが、ローカル変数同士であれば連続したアドレスに配置することができる。
【０００４】
しかしながら、従来のコンパイラにおいては、１つの演算式で複数の同じ種類の変数を使用しているか否かを考慮していない。このため、変数の配置先が非連続となり、１つの演算式で同じ種類の複数の変数を使用する場合に、キャッシュミスが発生し、処理速度が低下するという問題が発生している。
例えば、図８のように１つの関数で複数のローカル変数ａ，ｂ，ｃ，ｄｕｍｍｙ１，ｄｕｍｍｙ２を使用する場合、代入元となる変数ａを読み出す際には、変数ａが４バイトのｉｎｔ型であるので変数ａのアドレスのビット１３〜ビット５に対応したキャッシュラインに変数ａのアドレスのビット４〜ビット０が０ｘ００〜０ｘ１Ｆのアドレスデータとして読込まれる。図８において、変数ａのアドレスが０ｘ０Ｃ００００００の場合、０ｘ０Ｃ００００００〜０ｘ０Ｃ００００１Ｆまでのデータが読み込まれるため、変数ａとｄｕｍｍｙ１の２８バイトがキャッシュラインのデータ部に読込まれることになる。すると、図９に示すように、代入先となる変数ｂに書き込む時に変数ｂはキャッシュ上に読み込まれておらずキャッシュミスとなる。
また、変数ａ、ｂがそれぞれアドレス０ｘ０Ｃ００００００、０ｘ０Ｄ００００００のようにビット１３〜ビット５が同じ値となると同一のキャッシュラインを使用することとなり、変数ａのデータをキャッシュに読込んでも変数ｂに書き込む際に変数ｂのデータで上書きされ、次に変数ａを使用する時にキャッシュミスとなってしまう。この結果、キャッシュを有効に利用できず処理速度が低下してしまうという問題が起こる。
【０００５】
本発明の目的は、キャッシュを有効に利用可能なように変数をキャッシュ上に配置することができるコンパイラを提供することにある。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、本発明は、１つの演算式内で同種の複数の変数を使用しているかを判定するステップと、その判定結果に基づき、同種の変数がキャッシュの連続領域に配置されるようにキャッシュ上での配置アドレスを決定するステップとを備えることを特徴とする。
【発明の効果】
【０００７】
本発明によれば、各演算式の同じ種類の変数をキャッシュの連続した領域に配置されるようにすることにより、演算式の実行時に当該演算式の同じ種類の変数が共にキャッシュ上に格納され易くなり、処理速度の向上が可能となる。
【発明を実施するための最良の形態】
【０００８】
以下、本発明の実施形態について図面を参照しつつ説明する。
本発明に係るコンパイラは、図１に示す計算機上で動作する。図１の計算機はプロセッサ１０１と主記憶１０２，バス１０３、ディスク装置１０４、ＣＤ−ＲＯＭ読取り装置１０５を有し、ＣＤ−ＲＯＭ（記憶媒体）１０６に収めてあるコンパイラをＣＤ−ＲＯＭ読取り装置１０５を用いて読み込み、バス１０３を介してディスク装置１０４に格納する。
コンパイラを実行するには、当該コンパイラをディスク装置１０４からバス１０３を介して主記憶１０２に転送記憶させ、プロセッサ１０１で実行する。
【０００９】
本発明に係るコンパイラの機能構成の実施形態を図２に示す。
図２のコンパイラ２０１はソースプログラム２０２を入力として受け取り、中間コード変換部２０３で構文解析して中間コードに変換し、最適化部２０４で最適化を施し、最後にコード生成部２０５でローカル変数がキャッシュの連続した領域に配置されるようにした機械コード２０６に変換する。
図２のコード生成部２０５の詳細処理を図３および図４にフローチャートで示している。
【００１０】
図３において、コード生成部２０５はソースコード２０２の文の全てを検索したかを判定し（ステップ３０１）、全ての分の検索が終わっていたならばグローバル変数配置処理（図４）に進む。しかし、終わっていなければ、ソースコードの文を１つ取り出し（ステップ３０２）、その文でローカル変数を複数使用しているかを判定する（ステップ３０３）。
ステップ３０３において、１つの演算式中に複数のローカル変数を使用していた場合、ステップ３０４に進み、複数使用していなければステップ３０６へ進む。
ステップ３０４では、初期化データがないローカル変数が複数あるか判定する。コンパイラは初期化データ有りの変数と、初期化データ無しの変数とで配置される領域を分けてしまうため、初期化データ有りの変数と無しの変数を連続した領域に配置させることが出来ない。そこで、初期化データ無しの変数が複数ある場合はステップ３０５に進み、複数無い場合はステップ３０６へ進む。
ステップ３０５では、図５（ｂ）に示すようなローカル変数情報５１０を作成する。ローカル変数情報５１０には基準となるローカル変数名５１０１、その変数５１０１と代入関係にある変数名およびプログラムソース上で代入関係を持つ回数から成る情報５１０２を代入関係の数だけ登録する。この場合、既に基準となるローカル変数５１０１が登録され、代入関係にある変数名５１０２が登録済みであれば使用回数のカウントアップだけ行う。
【００１１】
ステップ３０６では１つの式中に複数のグローバル変数を使用しているかどうかを判定し、使用していたならばステップ３０７に進み、複数使用していなければステップ３０８へ進む。
ステップ３０７では、図５（ａ）のグローバル変数情報５００を作成する。グローバル変数情報５００には基準となるグローバル変数名５００１、配置先が決まっている場合はその配置先アドレス５００２、その基準となる変数５００１と代入関係にある変数名およびプログラムソース上で代入関係を持つ使用回数の情報５００３を代入関係の数だけ登録する。この場合も、既に基準となるグローバル変数５００１が登録され、代入関係にある変数名５００３が登録済みであれば使用回数のカウントアップだけ行う。
ステップ３０８では、１つの関数の検索終了か判定を行う。終了であればステップ３０９へ進む。終了でなければステップ３０１へ戻る。
ステップ３０９では、ステップ３０５で作成したローカル変数情報５１０を元に代入関係の回数の多いローカル変数がキャッシュの連続した領域に優先的に配置されるようにする。
具体的には、図８の例のように１つの演算式で複数の変数を使用し、且つ同じ種類の変数であれば連続したアドレスに配置されるようにする。その際、同一キャッシュラインのデータ部に読み込めるように配置されるアドレスのビット４〜ビット０以外が同じになるようにする。
【００１２】
こうすることにより、図８の例の演算式で使用されているローカル変数ａ，ｂは、実行時に図６に示すようにキャッシュラインの連続した領域のデータ部に配置される。
その結果、１度のキャッシュへの読み込みで代入関係にある変数のデータをキャッシュ上に読み込むことができ、キャッシュを有効的に使用でき処理速度の向上が可能となる。
この時、代入関係の使用回数が同じものが存在した場合は出現した順に配置されるようにする。
一方、ステップ３０１で全ての文を検索したらグローバル変数配置処理（図４）に進む。
【００１３】
図４において、ステップ４０１では前記ステップ３０７で作成した全てのグローバル変数情報５００を検索しているかどうかを判定し、検索していなければステップ４０２へ進み、全て検索していたら終了する。
ステップ４０２では代入関係の回数が１以上で最も多いものを検索する。続くステップ４０３では前記ステップ４０２で検索したグローバル変数と、そのグローバル変数と代入関係が一番多いグローバル変数が共にユーザーにより配置先が決められたものか判定する。
共に配置先が決められていたらステップ４０４へ進み、片方でも配置先が決まっていなければステップ４０５へ進む。
ステップ４０４ではグローバル変数をユーザーが指定した領域へ配置されるようにする。
ステップ４０５では、代入関係にあるグローバル変数の片方が、ユーザーにより配置先が決められたものか、または配置済みかを判定する。配置先が決められていたらステップ４０６へ進み、決められていなければステップ４０７へ進む。
ステップ４０６では配置先の決まっていない方の変数を配置先の決まっている変数に連続して配置されるようにする。
【００１４】
ステップ４０７では共に配置先が決まっていない変数を連続した領域に配置されるようにする。この時、同じキャッシュラインのデータ部に読み込みができるよう、配置されるアドレスのビット４〜ビット０以外が同じになるようにする。すなわち、インデックスを同じにする。そして、グローバル変数情報５００の配置先アドレス５００２に配置されるようにしたアドレスを設定しておく。
こうすることにより、次の代入関係を検索した時に、今回配置されるようにした領域に配置されるようになる。
ステップ４０８では配置済みのグローバル変数の代入関係の回数に「０」を設定し、次の検索時の対象にならないようにする。
【図面の簡単な説明】
【００１５】
【図１】本発明に係るコンパイラが実行される計算機の実施形態を示すブロック図である。
【図２】本発明に係るコンパイラの実施形態を示す機能構成図である。
【図３】図２のコード生成部の処理を示すフローチャートである。
【図４】図３のグローバル変数配置処理の詳細を示すフローチャートである。
【図５】グローバル変数、ローカル変数情報のデータ構造例を示す図である。
【図６】本発明を適用した場合のローカル変数の配置例を示す説明図である。
【図７】オペランドキャッシュの構成を示す説明図である。
【図８】代入関係のあるローカル変数が記述されたソースコードの例を示す図である。
【図９】キャッシュミスが起こるローカル変数の配置例を示す説明図である。
【符号の説明】
【００１６】
１０１    プロセッサ
１０２    主記憶
１０４    ディスク装置
２０２    ソースコード
２０１    コンパイラ
２０３    中間コード変換部
２０４    最適化部
２０５    コード生成部
２０６    機械コード
５００    グローバル変数情報
５１０    ローカル変数情報
【図１】
2005100240.tif 000003
【図２】
2005100240.tif 000004
【図３】
2005100240.tif 000005
【図４】
2005100240.tif 000006
【図５】
2005100240.tif 000007
【図６】
2005100240.tif 000008
【図７】
2005100240.tif 000009
【図８】
2005100240.tif 000010
【図９】
2005100240.tif 000011