JP2008071065A - インライン展開を行うコンパイル装置、方法、プログラム、記憶媒体 - Google Patents

Abstract

【課題】インライン展開を行うコンパイラにおいて、実引数と仮引数が共に配列で、かつ、配列の次元が互いに異なる場合に、コンパイラにより適用される最適化処理を受けることができ、オブジェクトプログラムの実行性能を高めることができるインライン展開を実施する。
【解決手段】インライン展開処理において、呼び出し先関数内で参照されている仮引数情報と、呼び出し元の実引数情報とを比較し、仮引数の配列次元数が実引数の次元数以下であり、かつ添字が実引数の添字範囲と一致し、かつ実引数で与えた添字が添字の下限値である場合に、呼び出し先関数内で参照されている仮引数名を、呼び出し元の実引数名を使った参照へと置き換える処理を行う。インライン展開時に置き換えを実施することで、実行時までメモリアドレスの参照関係が確定しなくなる要素を省き、コンパイラの最適化処理を受けやすくする。
【選択図】 図５

Description

本発明は、情報処理装置の利用技術において、ソースプログラムを実行可能形式プログラムにコンパイルする方法であって、該実行可能形式プログラムの実行時間と使用メモリを抑えるコンパイル装置、方法、プログラム、記憶媒体に関する。

従来より、情報処理装置の利用技術において、ソースプログラムを実行可能形式プログラムにコンパイルする際に、コンパイルされた結果作成される実行可能形式プログラムの実行時間と使用メモリを抑えるコンパイル方法として、コンパイル処理の１ステップにおいて、呼び出し先の関数をインライン展開する技術がある。

インライン展開とは、コンパイルの直前またはコンパイル実施時に、コンパイラが、実行対象のプログラムのソースプログラムを読み込み、ソースプログラムのうち、関数を呼び出している箇所(呼び出し元)に、関数を呼び出すコードの代わりに、呼び出された関数(呼び出し先関数)のコードを展開して中間的なコードを作成するという最適化方法である。

ここで生成された中間的なコードを使用することで、コンパイラは実行形式プログラムを生成することができる。技術者がプログラムを作成する際には可読性・保守性を高められるようにプログラムを記述し、これを情報処理装置で実行する際には一度実行速度を重視した中間的なソースコードを生成しこれをコンパイルすることで、可読性・保守性を高め、かつ実行性能を確保することが可能となる。

このインライン展開の技術的な原理を以下に説明する。

通常、ある情報処理装置にて実行対象のプログラムを実行させ、その処理ステップの中で関数呼出しを実行する場合には、Ｃａｌｌｅｅ−ｓａｖｅレジスタ(呼び出し先で退避・回復の必要なレジスタ)の退避・回復や、スタックフレームの確保・開放などのメモリ領域の利用に関する制御処理を情報処理装置が行う。

例えば、図７は実行対象のソースプログラム４１の一例である。なお、図の左端に記述してある“数字：”は、図の説明を容易にするために記述してあるもので、実際のソースプログラム中ではその記述はない。このプログラムは、２１行目から２７行目までにｍａｉｎ関数があり、そのｍａｉｎ関数から、関数ｆｕｎｃ１（１行目から９行目）と関数ｆｕｎｃ２（１１行目から１９行目）を呼び出す構造になっている。情報処理装置は、２４行目でｆｕｎｃ１の呼び出しを実施すると、３行目の文を実行する前に、関数内で参照されているＣａｌｌｅｅ−ｓａｖｅレジスタの退避とスタックフレームの確保を行う。また、関数内の実行が終了し呼び出し元へ制御を戻す文（８行目）を実行する前には、Ｃａｌｌｅｅ−ｓａｖｅレジスタの回復とスタックフレームの開放を行う。

この関数呼び出し時に必要なＣａｌｌｅｅ−ｓａｖｅレジスタの退避・回復やスタックフレームの確保・開放などが、関数呼び出し時に必要となり、オーバーヘッド負荷となる。この関数呼び出し部分をなくすために、コンパイルの前に呼び出される関数を呼び出し元にあらかじめ展開することで、関数呼び出し部分をなくし、上記オーバーヘッド負荷を最小化する、というのがインライン展開の原理である。

本願に先立つ技術として、特許文献１に記載されているインライン展開方法がある。

この特許文献１に記載されているインライン展開方法は、上記インライン展開をさらに進め、呼び出し元のプログラムから呼び出し先のプログラムへ引き渡す引数が配列であって、かつこの配列の次元が互いに相違する場合の効率的なインライン展開の方法である。

ここで、引数の配列の次元が互いに相違する場合とは、図７のような例である。

図７を見ると、呼び出し元の関数ｍａｉｎでは、配列ａが３次元配列として宣言されている（図７の２２行目）のに対し、呼び出し先の関数ｆｕｎｃ１やｆｕｎｃ２では、配列ａｒｇ１やａｒｇ２が２次元配列として宣言されている（それぞれ図７の２行目と１２行目）。このように、図７に示されたプログラムは、実行対象のプログラムから関数ｆｕｎｃ１やｆｕｎｃ２を呼び出すときの引数（これを実引数と呼ぶ）が３次元配列であり、呼び出された先で参照する引数（これを仮引数と呼ぶ）が２次元配列であり、実引数と仮引数の次元数が互いに相違するといえる。

特許文献１に記載された発明では、上記実引数と仮引数の次元数の相違を以下の方法で吸収している。

インライン展開を実施する手段は、実行対象のプログラムのコンパイルの１ステップにおいて、実行対象のプログラムのソースプログラムを検索し、関数を呼び出している命令行を対象として、実引数が記憶されているメモリ上のアドレスを求め、記憶装置に記憶する。その後、インライン展開を実施する手段は、上記で求めた実引数が記憶されているメモリ上のアドレスを基底とする配列を生成する命令コードを作成し、呼び出し先関数のソースコードから仮引数を参照する命令行を抽出し、前記配列を生成する命令コードに置き換える。

この引数の次元数の相違を吸収するインライン展開方法を適用すると、図７の２４行目のｆｕｎｃ１を呼び出す箇所は、図８の６行目から１１行目に置き換えられる。この展開方法を具体的に説明する。なお、図８に記載しているソースイメージは、当説明の便宜を図るために表したものであり、実際に該ソースイメージそのものが中間ソースプログラムとして出力されるわけではない。

まず、呼び出し元の命令行では、関数ｆｕｎｃ１呼び出し時の実引数がａ（１，１，ｋ）なので、インライン展開を実施する手段は、この実引数が記憶されているメモリアドレスと同じアドレスを基底とする新しい配列ｐｔｒ＿ａｒｇ１を確保するための宣言文を挿入する（図８の３行目）。なお、インライン展開を実施する手段は、新しい配列ｐｔｒ＿ａｒｇ１の次元数を、仮引数の次元数と同じ２次元で展開し、かつ、各次元の宣言範囲も同じ下限値１、上限値５となるように展開している。

続いて、インライン展開を実施する手段は、実引数が記憶されたメモリアドレスを新しい配列ｐｔｒ＿ａｒｇ１の基底とするために、アドレスの代入を行う文を挿入する（図８の６行目）。ここで、「ｐｔｒ＿ａｒｇ１＝＆（ａ（１，１，ｋ））」という行は、配列要素ａ（１，１，ｋ）のアドレスを、ｐｔｒ＿ａｒｇ１の基底アドレスと設定するための命令コードである。即ち、この命令コードが実行されると、ａ（１，１，ｋ）のアドレスとｐｔｒ＿ａｒｇ１（１，１）の指すメモリアドレスを一致させることができる。

最後に、インライン展開を実施する手段は、関数ｆｕｎｃ１内の仮引数ａｒｇ１による参照行（図７の５行目）を、新しい配列ｐｔｒ＿ａｒｇ１による参照行に置き換える（図８の９行目）。

同様に、図７の２５行目でｆｕｎｃ２を呼び出す箇所のインライン展開後のコードは、図８の１２行目から１７行目である。関数ｆｕｎｃ２が実行対象のプログラムへインライン展開された後には、新しい配列としてｐｔｒ＿ａｒｇ２が宣言され（図８の４行目）、関数ｆｕｎｃ２内の仮引数ａｒｇ２による参照行（図７の１５行目）は、新しい配列ｐｔｒ＿ａｒｇ２による参照行に置き換えられる（図８の１５行目）。

以上が、従来技術によるインライン展開方法である。

特開平４-２８７２３０号公報 MICHAEL WOLFE: High Performance Compilers for Parallel Computing. Addison-Wesley Publishing Company, 1996, pp.315-322

従来技術によるインライン展開では、コンパイラは、インライン展開に際して、呼び出される関数を呼び出す側にインライン展開すると共に、呼び出される関数側で使用している仮引数を利用するために、実引数のメモリアドレスを基底とする新しい配列を生成し、この配列にメモリアドレスを代入する処理を実施していた。具体的には、コンパイラは、実引数のメモリアドレスを基底とする新しい配列を生成するための命令コードと、この配列にメモリアドレスを代入する命令コードと、を生成して、中間コードにこれらのコードを挿入することにより、インライン展開時の変数参照を行っていた。

この弊害として、この方法でインライン展開を行うと、コンパイラがその後のステップとして実施する各種最適化処理（ループ融合、ループ不変式の移動、ループ展開など）の適用を受けられなくなり、結果として実行プログラムの処理が最適化されず、実行性能を高めることができない、という弊害がある。

具体的には、コンパイラは、上記最適化処理を行う際には、通常、プログラム中の変数をチェックして、異なる変数が同じメモリ領域を参照する可能性があるかどうかを判定し、判定の結果、同じ領域を参照しない場合に限り、各種最適化を適用する処理を行う。つまり、プログラム実行時に実際のメモリアドレスが代入される変数が存在すると、その変数が参照する領域はコンパイル時には確定できないため、コンパイラでその変数の参照領域を解析するのが困難になる。変数が参照する領域が解析できない場合、その他の変数と同じ領域を指す可能性があるとして、扱わなければならない。これを配列間の依存関係があるという。

よって、コンパイラは、アドレスを代入された変数間は常に依存があるとして扱わなければならないので、コンパイラの解析精度が落ちてしまい、各種最適化を適用できなくなる。上記従来技術によりインライン展開が適用された中間コードをコンパイルすると、アドレス代入文を伴う処理が含まれることになるため、コンパイラによる最適化が適用されないという問題が発生する。

例えば、図８では６行目と１２行目で変数ｐｔｒ＿ａｒｇ１とｐｔｒ＿ａｒｇ２にアドレスが代入される。そして、ｐｔｒ＿ａｒｇ１は７行目から１１行目で構成されるループ内で配列添字を更新しながら参照を行う。また、ｐｔｒ＿ａｒｇ２は１３行目から１７行目で構成されるループ内で配列添字を更新しながら参照を行う。ここで、インライン展開後の最適化として、７行目から１１行目で構成されるループと１３行目から１７行目で構成されるループとのループ融合について考える。

ループ融合については、例えば上記背景技術に記載した非特許文献１に記載がある。ループ融合を行うためには、それぞれのループ内で参照されているメモリ領域に重なりがあるかどうかを調べ、重なりのあるメモリ領域の参照順序がループ融合前とループ融合後で変わらないことをコンパイラが判断できるだけの合理性が必要となる。

ここで、ループ内で参照されているメモリ領域のうち、コンパイルを行う時点で参照先が確定しないものが存在すると、コンパイルを行う時点でメモリ領域の参照順序が確定しないため、それらのループに対してループ融合を適用できないとコンパイラは判断せざるを得なくなる。図８では、ｐｔｒ＿ａｒｇ１とｐｔｒ＿ａｒｇ２がアドレスを代入された変数であるため、それらの変数が参照するメモリ領域はコンパイル時点では確定しないため、これらが含まれるループ間で参照順序を確定することができないとコンパイラは判断せざるを得なくなり、ループ融合は適用できない。これは、アドレス代入文を伴うインライン展開を適用したことで、コンパイラの解析精度が落ちてしまうことを意味する。

本発明の目的は、呼び出し元の実引数と呼び出し先の仮引数が共に配列または変数で、実引数と仮引数の次元数が異なる場合であっても、代入文を用いた変数展開を行わずにインライン展開を行う方法を提供することである。

前記目的を達成するための発明に係るコンパイル装置は、
ｎ次元の第１の配列変数を仮引数とする呼び出し先の関数を、ｍ次元の第２の配列変数を実引数とする呼び出し元の関数にインラインで展開するコンパイル装置であって、
記憶部と、所定の条件の満足を判別する判別部と、前記判別部が前記所定の条件を満足すると判別した場合にインライン展開を行うインライン展開部と、を有して構成され、
前記判別部が判別する前記所定の条件は、
前記第１の配列変数の宣言情報における配列次元数（ｎ）が、前記第２の配列変数の宣言情報における配列次元数（ｍ）を超えず、
かつ、前記第１の配列変数の宣言情報における各次元の添字範囲が、前記第２の配列変数の宣言情報における各次元の添字範囲と一致し、
かつ、前記第２の配列変数の各次元の添字のうち、前記第１の配列変数の宣言情報における配列次元数（ｎ）以下の次元の添字が、前記第２の配列変数の宣言情報における各次元の添字範囲の下限値と一致する、
ことであり、
前記インライン展開部は、前記第１の配列変数名を、前記第２の配列変数名に置き換えて中間ソースプログラムを生成し前記記憶部に記憶する、
ことを特徴とする。

また、前記目的を達成するための発明に係るコンパイル装置は、
ｎ次元の第１の配列変数を仮引数とする呼び出し先の関数を、ｍ次元の第２の配列変数を実引数とする呼び出し元の関数にインラインで展開するコンパイル装置であって、
所定の条件の満足を判別する判別部と、前記判別部が前記所定の条件を満足すると判別した場合にインライン展開を行うインライン展開部と、を有して構成され、
前記判別部は、
コンパイル対象の関数の仮引数情報を収集する処理ステップと、
前記所定の条件の満足を判別する処理ステップと、
前記判別の結果、所定の条件を満足する場合に、実引数情報と、対応する仮引数情報と、を前記記憶部に記憶させる処理ステップと、
を順に実行し、
前記インライン展開部は、
前記記憶部にて記憶した実引数情報と仮引数情報とを元に、関数呼び出しのインライン展開時に仮引数を実引数に置き換える処理ステップと、
を順に実行する、
ことを特徴とする。

また、前記目的を達成するための発明に係るコンパイル方法は、
ｎ次元の第１の配列変数を仮引数とする呼び出し先の関数を、ｍ次元の第２の配列変数を実引数とする呼び出し元の関数にインラインで展開するコンパイル方法であって、
前記第１の配列変数の宣言情報における配列次元数（ｎ）が、前記第２の配列変数の宣言情報における配列次元数（ｍ）を超えず、
かつ、前記第１の配列変数の宣言情報における各次元の添字範囲が、前記第２の配列変数の宣言情報における各次元の添字範囲と一致し、
かつ、前記第２の配列変数の各次元の添字のうち、前記第１の配列変数の宣言情報における配列次元数（ｎ）以下の次元の添字が、前記第２の配列変数の宣言情報における各次元の添字範囲の下限値と一致する、
ことの満足を判別するステップと、
前記判別においてその結果が満足である場合に、前記第１の配列変数名を、前記第２の配列変数名に置き換えてインライン展開を行うステップと、
を有することを特徴とする。

また、前記目的を達成するための発明に係るコンパイルプログラムは、
ｎ次元の第１の配列変数を仮引数とする呼び出し先の関数を、ｍ次元の第２の配列変数を実引数とする呼び出し元の関数にインラインで展開するコンパイルプログラムであって、
情報処理装置に対して、
前記第１の配列変数の宣言情報における配列次元数（ｎ）が、前記第２の配列変数の宣言情報における配列次元数（ｍ）を超えず、
かつ、前記第１の配列変数の宣言情報における各次元の添字範囲が、前記第２の配列変数の宣言情報における各次元の添字範囲と一致し、
かつ、前記第２の配列変数の各次元の添字のうち、前記第１の配列変数の宣言情報における配列次元数（ｎ）以下の次元の添字が、前記第２の配列変数の宣言情報における各次元の添字範囲の下限値と一致する、
ことの満足を判別する処理と、
前記判別においてその結果が満足である場合に、前記第１の配列変数名を、前記第２の配列変数名に置き換えてインライン展開を行う処理と、
を実行させることを特徴とする。

以下、本発明に係る実施形態について、図面を用いて説明する。

本発明に係る実施形態としてのコンパイル装置について、図１〜１３を用いて説明する。

図１は、本発明によるコンパイル装置の構成図である。このコンパイル装置は、装置本体１と、ＣＰＵなどのプロセッサ２と、主記憶装置３と、記憶装置４と、ディスプレイ装置５と、入力装置６と、を有して構成される。

プロセッサ２は、コンパイル処理部２１と、コンパイル処理部２１に含まれる処理部としてのインライン展開部２２と、を有して構成される。

主記憶装置３は、後述する仮引数情報テーブル３１と、後述する実引数情報テーブル３２と、を有して構成される。上記テーブルはインライン展開部２２により作成され、書き込み・読み取りされ、削除される。

記憶装置４には、本実施形態にてコンパイル対象となるコンパイル対象ソースプログラム４１と、本実施形態にてコンパイルを行った結果作成されるオブジェクトプログラム４２と、が記憶される。

図２は、本実施形態のコンパイル処理部２１が処理する概要をフローチャートにして表現したものである。コンパイル処理部２１は、指定されたコンパイル対象ソースプログラム４１を対象として、構文解析を行うステップ２０１、インライン展開を行うステップ２０２、コード最適化を行うステップ２０３、レジスタ割付を行うステップ２０４、オブジェクトプログラム４２のコード生成を行うステップ２０５、を実施する。

図３は、図２にて示したコンパイル処理部２１の処理ステップのうち、インライン展開部２２が実行するインライン展開２０２の処理ステップを詳細に記載したものである。

インライン展開２０２のステップは、コンパイル対象ソースプログラム４１を対象として、呼び出し先関数の仮引数情報を収集し仮引数情報テーブル３１に登録するステップ３０１と、コンパイル対象ソースプログラム４１に記載されている全関数のインライン展開の要否判断またはインライン展開（後述のステップ３０３〜ステップ３０８）が完了したかどうかを判定するステップ３０２と、コンパイル対象ソースプログラム４１に含まれる関数の全てについてインライン展開可否の判断がなされたかどうかを判定するステップ３０３と、その関数内から他の関数を呼び出す箇所（以降、該箇所を「コール文」と記載する。）が、インライン展開が可能な関数呼び出しか否かを判断するステップ３０４と、インライン展開が可能であればその関数呼び出しの実引数の情報を実引数情報テーブル３２に登録するステップ３０５と、ステップ３０５に続いて対応する仮引数に関する情報を実引数情報テーブル３２に登録するステップ３０６と、仮引数情報テーブル３１と実引数情報テーブル３２とを参照して、関数呼び出し文をインライン展開するステップ３０７と、インライン展開が行われた後に実引数情報テーブル３２に登録された情報を破棄するステップ３０８と、からなり、これを順次インライン展開部２２が実行していくことで実現される。

図４は、図３にて示したインライン展開部２２が実施するステップのうち、呼び出し先関数の仮引数情報を収集し仮引数情報テーブル３１に登録するステップ３０１をより詳細に示したものである。

該ステップ３０１は、コンパイル対象のプログラムに含まれる全関数の仮引数情報を登録し終わったかどうかを検査するステップ４０１と、ある１つの関数の仮引数の名前・型・次元数などの情報を収集し、後に示す仮引数情報テーブル３１に登録するステップ４０２と、からなり、各ステップは、インライン展開部２２によって実行される。

図５は、図３にて示したインライン展開部２２が実施するステップのうち、対応する仮引数に関する情報を実引数情報テーブル３２に登録するステップ３０６を詳細に示したものである。

該ステップ３０６は、関数呼び出し時の実引数の情報を前記の仮引数情報テーブル３１に記憶された仮引数情報と突合して、呼び出される関数をインライン展開する際に仮引数を実引数に置き換えてインライン展開することが可能かどうかを判断し、可能であれば実引数情報テーブル３２に対応する仮引数情報を登録して後に置き換えを行うための情報を取得するステップである。

ここで、仮引数を実引数に置き換えてインライン展開することができると、結果として、代入文を用いた変数展開を行うことなくインライン展開を行うことができるようになり、コンパイラによる最適化処理時の不確定要素を減らすことができれば、本願の目的である最適化の恩恵を受けることができるため、置き換えを行うための情報を取得する必要がある。

具体的には、ステップ３０６は、以下のステップからなる。

各コール文で指定した実引数に対して置き換えが可能かどうかの判断を完了したかどうかを判定するステップ５０１と、実引数に対応する仮引数情報を取得するステップ５０２と、実引数と仮引数の型が一致するかどうかを判定するステップ５０３と、一致した場合に実引数の次元数が仮引数の次元数以上であるかどうかを判定するステップ５０４と、実引数の次元数が仮引数の次元数以上である場合に実引数と仮引数の配列の添字の範囲が下限値上限値共に仮引数の次元数まで一致するかどうかを判定するステップ５０５と、仮引数の次元数まで添字範囲が一致した場合に、各コール文で実引数に指定された際の添字が、仮引数の次元数までの実引数の添字の下限値と一致するかどうかを判定するステップ５０６と、実引数の添字の下限値と一致した場合に、コール文で指定した実引数に置き換えることを決定し、対応する仮引数名と次元数を実引数情報登録テーブル３２に登録するステップ５０７と、を備える。

ここで、各判定ステップ５０３、５０４、５０５、５０６、の判定結果がすべて真でない限りコール文で指定した実引数に置き換えることが可能でないと判断し、ステップ５０７の登録を行わない。

図６は、図３にて示したインライン展開部２２が実施するステップのうち、ステップ３０６にてインライン展開時に実引数への置き換えが可能であると判断された仮引数を、実際に実引数名に置き換えてインライン展開を行うステップ３０７を詳細に示したものである。

該ステップ３０７は、各コンパイル対象のコール文について実際に仮引数を実引数に置き換えることが可能かどうかを判断し、可能であれば置き換えを実施してインライン展開を行うステップである。

具体的には、コール文がインライン展開をなされている、あるいはインライン展開を行う必要がないと判断されているかどうかを判定するステップ６０１と、対象のコール文で使用する全実引数の変数と配列がすでにインライン展開をなされているかどうかを判定するステップ６０２と、呼び出し先関数をインライン展開した場合に、仮引数名で参照を行う部分があるかどうかを判定するステップ６０３と、その参照を行う仮引数は実引数情報テーブル３２に登録されている引数であるかどうかを判定するステップ６０４と、登録されている引数であれば仮引数名を実引数名に置き換えてインライン展開するステップ６０５と、ステップ６０３の判定結果あるいはステップ６０４の判定結果が真でない場合に従来技術と同様のインライン展開を行うステップ６０６と、を実行するステップである。

図１１,１２を用いて、実引数情報テーブル３２の構造を説明する。
実引数情報テーブル３２は、引数番号１１０１と、変数配列名１１０２と、型１１０３と、次元数１１０４と、各次元ごとの添字の範囲を示す次元情報１１０５と、コール文で引き渡している添字情報１１０６と、対応仮引数名１１０７と、仮引数次元数１１０８と、を有して構成される。

引数番号１１０１とは、コール文１つにつき複数の実引数が引き渡される場合に、１コール文中の何番目の引数であるのかを識別するための番号である。
変数配列名１１０２とは、コール文で引き渡されている実引数の変数名である。
型１１０３とは、コール文で引き渡されている実引数の変数のデータ型である。
次元数１１０４とは、コール文で引き渡されている実引数の変数の配列次元数である。実引数が変数の場合は０である。
次元情報１１０５とは、コール文で引き渡されている実引数の変数の各次元ごとの添字の下限値と上限値を、各次元ごとに取得したものである。
添字情報１１０６とは、コール文で引き渡されている実引数の変数の各次元ごとの添字である。
対応仮引数名１１０７とは、インライン展開時に該実引数で置き換える仮引数名の候補である。
仮引数次元数１１０８とは、対応仮引数名１１０７で示される仮引数の次元数である。

ここで、該テーブルのうち、上記対応仮引数名１１０７と、仮引数次元数１１０８以外の情報は、インライン展開部２２により、実引数情報登録のステップ３０５にて登録され、実引数情報破棄のステップ３０８にて破棄される。該テーブルのうち、上記対応仮引数名１１０７と、仮引数次元数１１０８は、インライン展開部２２により、実引数情報に対応した仮引数情報登録のステップ３０６にて登録され、実引数情報破棄のステップ３０８にて破棄される。

図１３を用いて、仮引数情報テーブル３１の構造を説明する。
仮引数情報テーブル３１は、関数名１２０１と、引数番号１２０２と、変数配列名１２０３と、型１２０４と、次元数１２０５と、各次元ごとの添字の範囲を示す次元情報１２０６と、を有して構成される。

関数名１２０１とは、コールされる関数の名称であり、どの関数の仮引数情報が登録されているかを識別するためのもの、引数番号１２０２とは、その関数を呼び出す際に複数の引数が引き渡される場合に、１コール文中の何番目の引数であるのかを識別するための番号である。
変数配列名１２０３とは、仮引数の変数名である。
型１２０４とは、仮引数の変数のデータ型である。
次元数１２０５とは、仮引数の変数の配列次元数である。仮引数が変数の場合は、０を登録する。
次元情報１２０６とは、仮引数の変数の各次元ごとの添字の下限値と上限値を、各次元ごとに取得したものである。

ここで、該テーブルのレコードは、インライン展開部２２により、仮引数情報登録のステップ３０１にて登録される。

次に、図１〜１３を用いて、本実施形態のコンパイル装置の動作を説明する。

まず、図１と図２を用いて、コンパイル装置１の動作の概要を示す。

コンパイル装置１は、プロセッサ２が備えるコンパイル処理部２１が、図２に示すステップに従って処理を実行することにより、記憶装置４に記憶されたコンパイル対象ソースプログラム４１のコンパイルを実現し、オブジェクトプログラム４２を出力する。

具体的には、コンパイル処理部２１は、構文解析２０１、インライン展開２０２、コード最適化２０３、レジスタ割り付け２０４、コード生成２０５の順で処理を実行する。

構文解析２０１のステップでは、コンパイル対象ソースプログラム４１を入力として構文解析を行い、中間コード（図示せず）を出力する。インライン展開２０２のステップは、後に詳細に説明するため、ここでは説明を割愛する。コード最適化２０３のステップでは、該中間コードを入力として、ループ融合、ループ交換、ループ展開や部分冗長性削除などの最適化処理を適用し、その結果を変換後の中間コード（図示せず）として出力する。レジスタ割り付け２０４のステップでは、上記変換後の中間コードの各ノードに対してレジスタ割り付けを実施する。コード生成２０５のステップでは、上記変換後の中間コードをオブジェクトプログラム４２に変換し出力する。

次に、主に図７に示すサンプルのプログラムを用いて、本実施形態のコンパイル装置の詳細な動作を図３〜１３を用いて具体的に説明する。

図７のサンプルプログラムはＦｏｒｔｒａｎ言語で記述したプログラムである。このプログラムでは、２１行目から２７行目までにｍａｉｎ関数があり、そのｍａｉｎ関数から、関数ｆｕｎｃ１（１行目から９行目）と関数ｆｕｎｃ２（１１行目から１９行目）を呼び出す構造になっている。このプログラムに対し、ステップ３０１の呼び出し先関数の仮引数情報収集処理（図４のステップ４０１と４０２を含む）を適用すると、図１３に示す仮引数情報テーブル３１が得られる。

該仮引数情報テーブル３１の１つめのエントリは、主に関数名ｆｕｎｃ１（図７の１行目から９行目）にある配列変数の宣言文（図７の２行目）から取得した仮引数情報が登録されている。ｆｕｎｃ１にて定義されている１番目の仮引数は、変数配列名がａｒｇ１、型がｒｅａｌ＊８（テーブル中ではｒ８と略している）、次元数が２次元で、各次元の（下限値：上限値）の組が共に（１：５）であることを示している。仮引数情報テーブルの２つめのエントリには、主に関数名ｆｕｎｃ２（図７の１１行目から１９行目）にある配列変数の宣言文（図７の１２行目）から取得した仮引数情報が登録されている。ｆｕｎｃ２の１番目の仮引数は、変数・配列名がａｒｇ２、型がｒｅａｌ＊８、次元数が２次元で、各次元の（下限値：上限値）の組が共に（１：５）であることを示している。

ステップ３０２の判定では、コンパイル対象の全関数（ｍａｉｎ，ｆｕｎｃ１，ｆｕｎｃ２）に対するインライン展開が完了したかどうかを判定するが、この段階ではまだいずれも展開していないため、判定結果の真偽値は偽となり、次にステップ３０３を実施する。
なお、全関数のインライン展開が完了した場合には、判定結果の真偽値は真となり、インライン展開２０２の処理そのものを終了する。

ステップ３０３の判定では、前記の全関数のうちの一つを対象として関数内を走査し、他の関数を呼び出す文の全て（図７では、関数ｆｕｎｃ１と、ｆｕｎｃ２と、を呼び出すｍａｉｎ内の２４行目と２５行目のコール文）のインライン展開が完了したかどうかを判定する。この段階では、まだいずれのコール文も展開していないため、判定結果の真偽値は偽となり、次にステップ３０４を実施する。
なお、全コール文のインライン展開が完了した場合には、判定結果の真偽値は真となり、ステップ３０２の判定に戻って全関数の処理が完了したかどうかの判定を行う。

ステップ３０４の判定では、対象の１つのコール文（図７では、例えばｍａｉｎ内の２４行目のコール文）が、インライン展開画可能な関数呼び出しであるかどうかを判定する。

その判定の方法としては、呼び出し先関数に含まれる文の数を比較するなどの方法がある。呼び出し先関数の文の数が多い場合、その関数をインライン展開すると、呼び出し元のコードサイズが不必要に増加したり、レジスタの消費量が増えるなどの悪影響が出ることが知られている。そのため、インライン展開する場合は、あらかじめ閾値とする文の数を決めておき、その文の数以下の関数の場合だけインライン展開対象とする、などの判定を行う。このような判定のもとで、インライン展開不可と判定された場合は、ステップ３０３へ戻る。インライン展開可能と判定した場合は、ステップ３０５を実施する。

ステップ３０５では、該コール文における実引数の順に応じて引数番号１１０１を付番して記録し、実引数の名前を変数配列名１１０２に、変数の型を型１１０３に、変数の次元数を次元数１１０４に、実引数の変数の各次元ごとの添字の下限値と上限値を、各次元ごとに次元情報１１０５に、実引数の変数の各次元ごとの添字を添字情報１１０６に、対応させて実引数情報テーブル３２に登録する。

例では、図１１（ａ）に、ｍａｉｎ内の２４行目にあるｆｕｎｃ１コール文を対象として上記登録を行った直後の実引数情報テーブル３２を示す。

引数番号１１０１には、引数の一つ目であることを示す１を、実引数の名前であるａを変数配列名１１０２に、変数の型であるｒ８（実数８バイト）を型１１０３に、変数の次元数である３を次元数１１０４に、次元情報１１０５には一次元目の下限値を１、上限値を５、二次元目の下限値を１、上限値を５、三次元目の下限値を１、上限値を１０として記録してある。添字情報１１０６には１次元目に１、２次元目に１、３次元目にｋを記録しており、対応仮引数名１１０７と、仮引数次元数１１０８には、この段階では記録するステップを経ていないため何も記録されていない。

同様に、ｆｕｎｃ２に関しては、図１２の（ｃ）に記載の情報が該当する。

ステップ３０６では、仮引数情報テーブル３１と実引数情報テーブル３２に登録されている情報を使い、呼び出し先の関数をインライン展開したときに、その関数内において仮引数名で参照されている箇所を、呼び出し元の実引数名を使った参照に置き換えることができるかどうかを判定し、可能な場合は対応する仮引数情報を登録する。

ステップ３０６の処理の詳細は、図５のステップ５０１からステップ５０７により実現される。
コール文で指定した実引数全てに対して置き換えが可能かどうかの判断を完了したかどうかを判定するステップ５０１では、該コール文（例では図７の２４行目のｆｕｎｃ１コール文）に指定されているすべての引数を対象として仮引数を実引数に置き換える判断を完了したかどうかを判定する。すべての引数を判断した場合はステップ３０６を終了する。判断済みでない引数がある場合は、ステップ５０２へ進む。

該当する実引数に対応する仮引数情報を取得するステップ５０２では、呼び出し先の関数名と引数の順序に従って、仮引数情報テーブル３１から、対象の実引数と同順序に指定されている仮引数のエントリを取得する。

ステップ５０３では、該仮引数と該実引数のデータ型が同じかどうかを、型１２０４と型１１０３の記録データを比較して調べる。型が異なる場合は、ステップ５０１へ戻る。型が一致する場合は、ステップ５０４へ進む。この比較の意図は、型に相違がある場合には、置き換えを行ってしまうとデータ型の互換性が得られず、例えば算式などによる後の処理で型変換エラー等が発生し、オブジェクトプログラム４２の実行が不可能となってしまうのを避けることにある。

ステップ５０４では、同様に仮引数と実引数の次元数の比較を行い、仮引数の次元数（ｎ）が実引数の次元数（ｍ）より大きければ、ステップ５０１へ戻る。仮引数の次元数（ｎ）が実引数の次元数（ｍ）以下であれば、ステップ５０５へ進む。これは、仮引数情報テーブル３１上のエントリの次元数１２０５と、実引数情報テーブル３２上の次元数１１０４とを比較することで調べられる。

この比較の意図は、仮引数の次元数（ｎ）が実引数の次元数（ｍ）より大きければ、呼び出し元で用意した実引数のメモリエリアを超えて呼び出される側の関数にてデータにアクセスするという結果を招く虞があり、その結果オブジェクトプログラム４２が扱うデータの整合性を得られなくなり、オブジェクトプログラム４２の実行が不可能となってしまうのを避けることにある。

ステップ５０５では、上記ｎ次元目までの下限値と上限値が、仮引数と実引数間で一致するかどうかを調べる。これは、仮引数情報テーブル３１上のエントリの次元情報１２０６と、実引数情報テーブル３２上の次元情報１１０５とを比較することで調べられる。ｎ次元目までの下限値と上限値が一致しない場合は、ステップ５０１へ戻る。ｎ次元目までの下限値と上限値が一致する場合は、ステップ５０６へ進む。

この比較の意図は、仮引数と実引数のｎ次元目までの下限値と上限値が一致しない場合には、呼び出し元で用意した実引数のメモリエリアを超えて呼び出される側の関数にてデータにアクセスするという結果を招く虞があり、その結果オブジェクトプログラム４２が扱うデータの整合性を得られなくなり、オブジェクトプログラム４２の実行が不可能となってしまうのを避けることにある。

ステップ５０６では、コール文における実引数のn次元目までの添字が、実引数の下限値と完全一致するかどうかを調べる。これは、実引数の各次元の添字と、実引数情報テーブル３２に登録されている次元情報１１０５の下限値を比較することで調べられる。添字が下限値と一致しない場合は、ステップ５０１へ進む。添字が下限値と一致する場合は、ステップ５０７へ進む。これは、配列のアクセス開始位置を、仮引数と実引数との間で共に下限値からアクセスする場合に限って置き換えを許可するためである。

ステップ５０７では、インライン展開時に仮引数名での参照を実引数名を使った参照に置き換えるための情報として、実引数名に対応する仮引数名を実引数情報テーブル３２の対応仮引数名１１０７に登録する。さらに、仮引数の次元数を仮引数次元数１１０８へ登録する。

例で説明すると、ステップ５０２では、呼び出し先の関数名がｆｕｎｃ１で、１番目の引数を処理中なので、図１３に示した仮引数情報テーブル３１の対応する仮引数のエントリとして１行目のａｒｇ１が登録されているエントリが取得される。ステップ５０３の判定では、仮引数と実引数の型は同じｒｅａｌ＊８であるので、型は一致するため、ステップ５０４へ進む。

ステップ５０４では、実引数の次元数は図１１（ａ）より３次元なのでｍ＝３、仮引数の次元数は図１３より２次元なのでｎ＝２。判定した結果、仮引数の次元数２が実引数の次元数３以下なので、ステップ５０５へ進む。

ステップ５０５の判定では、ｎ＝２なので実引数と仮引数の２次元目までの（下限値：上限値）の組を調べる。図１１（ａ）より実引数は１次元目、２次元目共に（１：５）の組であり、図１３より仮引数も１次元目、２次元目共に（１：５）の組であるので、各次元の（下限値：上限値）の組が一致すると判定され、ステップ５０６へ進む。

ステップ５０６の判定では、図１１（ａ）より、実引数の２次元目までの添字が共に１で、これは実引数の１次元目、２次元目の下限値と一致しているため、ステップ５０７へ進む。

ステップ５０７では、対応する仮引数情報である、仮引数名ａｒｇ１と仮引数の次元数２をそれぞれ対応仮引数名１１０７と仮引数次元数１１０８に登録して、ステップ５０１へ処理を戻し、次なる引数に処理を移す。しかし、この実施例では引数は１つであり、置き換えの判断は完了したため、該ステップ３０６を終了する。

上記登録ステップ３０６が実施された直後には、ｆｕｎｃ１に関しては図１１（ｂ）のとおり、対応仮引数名１１０７にａｒｇ１が、仮引数次元数１１０８には２が記録された状態となる。
同様に、ｆｕｎｃ２に関しては図１２（ｄ）のとおり、対応仮引数名１１０７にａｒｇ２が、仮引数次元数１１０８には２が記録された状態となる。

ステップ３０７では、処理対象としたコール文に対するインライン展開処理を実施する。このとき、実引数テーブル３２に仮引数名が登録されている場合、インライン展開時に仮引数名を実引数名を使った参照に置き換えた中間コードを生成する。

ステップ３０７の処理の詳細は、図６のステップ６０１からステップ６０６により実現される。

コール文がインライン展開をなされているかどうかを判定するステップ６０１では、呼び出し先関数に含まれるすべての文をインライン展開したかどうかを判定する。すべての文がインライン展開済みであれば、処理を終了する。すべての文がインライン展開されていなければ、ステップ６０２へ進む。

対象のコール文で使用する全実引数の変数と配列がすでにインライン展開をなされているかどうかを判定するステップ６０２では、文中の全変数・配列名を処理したかどうかを判定する。全変数・配列名を処理済みであれば、ステップ６０１へ戻る。全変数・配列名が処理済みでなければ、ステップ６０３へ進む。

呼び出し先関数をインライン展開した場合に、仮引数名で参照を行う部分があるかどうかを判定するステップ６０３では、処理中の変数・配列名が仮引数であるか否かを判定する。判定は、インライン展開されている関数名と変数・配列名の組が、仮引数情報テーブル３１に登録されているか否かで判断することができる。処理中の変数・配列名が仮引数でない場合は、ステップ６０６へ進む。処理中の変数・配列名が仮引数の場合は、ステップ６０４へ進む。

参照を行う仮引数は実引数情報テーブル３２に登録されている引数であるか否かを判定するステップ６０４では、処理中の仮引数名が実引数情報テーブル３２の対応仮引数名欄に登録されているか否かを調べる。登録されていない場合は、ステップ６０６へ進む。登録されている場合は、ステップ６０５へ進む。

仮引数名を実引数名に置き換えてインライン展開するステップ６０５では、文中の仮引数名による参照を、呼び出し元で与えた実引数名を使った参照に置き換えることが可能であるため、仮引数名を実引数名に変更するインライン展開を実施する。実引数名で展開した場合の添字は、仮引数の次元数をｎ、実引数の次元数をｍとすると、ｎ次元目までは仮引数の添字を使い、それ以上の次元は実引数の添字を使うものとする。処理終了後ステップ６０２へ戻る。

ステップ６０３の判定結果あるいはステップ６０４の判定結果が真でない場合に従来技術と同様のインライン展開を行うステップ６０６では、従来のインライン展開を実施する。処理終了後はステップ６０２へ戻る。

図７の２４行目のコール文に、関数ｆｕｎｃ１の３行目から９行目を展開する処理例を挙げる。図７の５行目の文をインライン展開する際、ステップ６０３の判定により配列ａｒｇ１は仮引数名であることが分かる。ステップ６０４では、実引数情報テーブル３２（図１１（ｂ）参照）にａｒｇ１が登録されているかどうかを調べる。このとき、ａｒｇ１は実引数情報テーブル３２に登録されているので、ステップ６０５に進む。ステップ６０５では、仮引数名を実引数名に変更するインライン展開を実施する。このインライン展開処理後の中間コードをソースイメージで示したものが図９の４行目から８行目となる。図９の６行目は仮引数ａｒｇ１での参照を実引数ａを使った参照に変更したものである。ここで、配列ａの添字は、２次元目までが仮引数ａｒｇ１のもの（図７の５行目）で、３次元目は実引数ａのもの（図７の２４行目）である。

図７の２５行目のｆｕｎｃ２のコール文においても同様の処理を行うと、実引情報テーブル３２として、図１２（ｃ）（ｄ）が作成される。また、インライン展開後の中間コードのソースイメージは図９の９行目から１３行目となる。

ステップ３０８では、該コール文でのインライン展開が完了したので、ステップ３０５で作成した実引数情報テーブル３２を破棄する。

その後、コンパイラは、主記憶装置３に作成した中間コードを記憶させ（図示せず）、中間コードに対してコンパイル処理を継続する。

本発明によるインライン展開を適用した後の中間コードのソースイメージは図９のようになる。この例では、外側ｋループの内側にｊ，ｉの２重ループが２つ存在している。ここで、あるｋのときに、内側ｊ，ｉの２重ループが参照する領域を解析すると、前半ループと後半ループで３次元目のｋの添字が異なるため、同一領域を参照することはないことが容易に判別でき、コンパイル処理部にて実施する後続処理２０３にて最適化の一つであるループ融合が容易に適用される。（図１０）。

このように、本実施形態におけるコンパイル装置により、呼び出し元の実引数と呼び出し先の仮引数が共に配列または変数で、かつ、実引数と仮引数の次元数が異なる場合であっても、代入文を用いた変数展開を行わずにインライン展開を行うことができる。

本発明に係る第１の実施形態に係る最適化方法を実施するコンパイラが稼動するコンパイル装置の構成図である。 本発明に係る第１の実施形態におけるコンパイラの処理手順を示す。 本発明に係る第１の実施形態におけるインライン展開の処理手順概要を示す 本発明に係る第１の実施形態における仮引数情報収集の処理手順を示す。 本発明に係る第１の実施形態における対応仮引数名情報の登録処理手順を示す。 本発明に係る第１の実施形態の関数呼び出しのインライン展開処理手順を示す。 本発明に係る第１の実施形態におけるソースプログラムの一例を示す。 本発明に係る第１の実施形態における従来技術のインライン展開コード例を示す。 本発明に係る第１の実施形態におけるインライン展開結果コード例を示す。 本発明に係る第１の実施形態におけるコード最適化結果例を示す。 本発明に係る第１の実施形態における実引数情報テーブルの一つの例を示す。 本発明に係る第１の実施形態における実引数情報テーブルの他の例を示す。 本発明に係る第１の実施形態における仮引数情報テーブルの例を示す。

符号の説明

１：コンパイル装置、２：プロセッサ、３：主記憶装置、４：記憶装置、５：ディスプレイ、６：入力装置、２１：コンパイル処理部、２２：インライン展開部、３１：仮引数情報テーブル、３２：実引数情報テーブル、４１：コンパイル対象ソースプログラム、４２：オブジェクトプログラム

Claims (5)

1. ｎ次元の第１の配列変数を仮引数とする呼び出し先の関数を、ｍ次元の第２の配列変数を実引数とする呼び出し元の関数にインラインで展開するコンパイル装置であって、
   記憶部と、所定の条件の満足を判別する判別部と、前記判別部が前記所定の条件を満足すると判別した場合にインライン展開を行うインライン展開部と、を有して構成され、
   前記判別部が判別する前記所定の条件は、
   前記第１の配列変数の宣言情報における配列次元数（ｎ）が、前記第２の配列変数の宣言情報における配列次元数（ｍ）を超えず、
   かつ、前記第１の配列変数の宣言情報における各次元の添字範囲が、前記第２の配列変数の宣言情報における各次元の添字範囲のうち前記第１の配列変数の宣言情報における配列次元数（ｎ）以下の次元のものと一致し、
   かつ、前記第２の配列変数の各次元の添字のうち、前記第１の配列変数の宣言情報における配列次元数（ｎ）以下の次元の添字が、前記第２の配列変数の宣言情報における各次元の添字範囲の下限値と一致する、
   ことであり、
   前記インライン展開部は、前記第１の配列変数名を、前記第２の配列変数名に置き換えて中間コードを生成し前記記憶部に記憶する、
   ことを特徴とするコンパイル装置。
2. ｎ次元の第１の配列変数を仮引数とする呼び出し先の関数を、ｍ次元の第２の配列変数を実引数とする呼び出し元の関数にインラインで展開するコンパイル装置であって、
   所定の条件の満足を判別する判別部と、前記判別部が前記所定の条件を満足すると判別した場合にインライン展開を行うインライン展開部と、を有して構成され、
   前記判別部は、
   コンパイル対象の関数の仮引数情報を収集する処理ステップと、
   前記所定の条件の満足を判別する処理ステップと、
   前記判別の結果、所定の条件を満足する場合に、実引数情報と、対応する仮引数情報と、を前記記憶部に記憶させる処理ステップと、
   を順に実行し、
   前記インライン展開部は、
   前記記憶部にて記憶した実引数情報と仮引数情報とを元に、関数呼び出しのインライン展開時に仮引数を実引数に置き換える処理ステップと、
   を順に実行する、
   ことを特徴とするコンパイル装置。
3. ｎ次元の第１の配列変数を仮引数とする呼び出し先の関数を、ｍ次元の第２の配列変数を実引数とする呼び出し元の関数にインラインで展開するコンパイル方法であって、
   前記第１の配列変数の宣言情報における配列次元数（ｎ）が、前記第２の配列変数の宣言情報における配列次元数（ｍ）を超えず、
   かつ、前記第１の配列変数の宣言情報における各次元の添字範囲が、前記第２の配列変数の宣言情報における各次元の添字範囲のうち前記第１の配列変数の宣言情報における配列次元数（ｎ）以下の次元のものと一致し、
   かつ、前記第２の配列変数の各次元の添字のうち、前記第１の配列変数の宣言情報における配列次元数（ｎ）以下の次元の添字が、前記第２の配列変数の宣言情報における各次元の添字範囲の下限値と一致する、
   ことの満足を判別するステップと、
   前記判別においてその結果が満足である場合に、前記第１の配列変数名を、前記第２の配列変数名に置き換えてインライン展開を行うステップと、
   を有することを特徴とするコンパイル方法。
4. ｎ次元の第１の配列変数を仮引数とする呼び出し先の関数を、ｍ次元の第２の配列変数を実引数とする呼び出し元の関数にインラインで展開するコンパイルプログラムであって、
   情報処理装置に対して、
   前記第１の配列変数の宣言情報における配列次元数（ｎ）が、前記第２の配列変数の宣言情報における配列次元数（ｍ）を超えず、
   かつ、前記第１の配列変数の宣言情報における各次元の添字範囲が、前記第２の配列変数の宣言情報における各次元の添字範囲のうち前記第１の配列変数の宣言情報における配列次元数（ｎ）以下の次元のものと一致し、
   かつ、前記第２の配列変数の各次元の添字のうち、前記第１の配列変数の宣言情報における配列次元数（ｎ）以下の次元の添字が、前記第２の配列変数の宣言情報における各次元の添字範囲の下限値と一致する、
   ことの満足を判別する処理と、
   前記判別においてその結果が満足である場合に、前記第１の配列変数名を、前記第２の配列変数名に置き換えてインライン展開を行う処理と、
   を実行させることを特徴とするコンパイルプログラム。
5. 請求項４のコンパイルプログラムを記録したコンピュータ読み取り可能な記録媒体。

Images