(57)【要約】【課題】指示先が定数アドレス領域に限定されるポインタを解析し、プログラムの実行コードサイズの縮小および実行速度の向上を行うコンパイル方法を提供する。【解決手段】プログラム中のポインタについて、その指示先が定数アドレス領域に限定されるかどうかを判定する解析を行う。ポインタに代入される値が変数のアドレス値に依存しない数値（確定値）であるかを調べ（ステップ３０６）、確定値しか取らないポインタの指示先は定数アドレス領域に限定されるものとする（ステップ３１１）。【選択図】　図３
2004139369.tif 000002
【特許請求の範囲】
【請求項１】
定数アドレス領域をポインタの指示先として参照するプログラムにおいて、該ポインタの指示先が定数アドレス領域に限定されるかどうかを、該ポインタの値が常に数値として求められるかを調べることによって判定し、条件を満たす場合に該ポインタの指示先に変数メモリ領域が含まれないことを利用した最適化を適用することで、実行コードサイズの縮小および実行速度の向上を達成することを特徴とするコンパイル方法。
【請求項２】
定数アドレス領域をポインタの指示先として参照するプログラムにおいて、該ポインタの指示先が定数アドレス領域に限定されるかどうかを、該ポインタの値が常に数値として求められるかを調べることによって判定し、条件を満たす場合に該ポインタの指示先に変数メモリ領域が含まれないことを利用した最適化を適用することで、実行コードサイズの縮小および実行速度の向上を達成することを特徴とするコンパイラ。
【請求項３】
定数アドレス領域をポインタの指示先として参照するプログラムにおいて、該ポインタの指示先が定数アドレス領域に限定されるかどうかを、該ポインタの値が常に数値として求められるかを調べることによって判定し、条件を満たす場合に該ポインタの指示先に変数メモリ領域が含まれないことを利用した最適化を適用することで、実行コードサイズの縮小および実行速度の向上を達成することを特徴とするコンパイラを格納した記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は計算機の利用技術において、実行コードサイズを縮小し、実行速度を向上させるコンパイル方法に関する。特に、ポインタの指示先が定数アドレス領域に限定されるかどうかを判定し、その結果を利用した最適化を可能とするコンパイル方法に関する。
【０００２】
【従来の技術】
コンパイラ最適化技術のひとつに、プログラムで使用されているポインタの指示先を求めるポインタ解析がある。ポインタを用いて間接的にデータを操作するプログラムでは、ポインタの指示先を特定することで、冗長なメモリ参照命令を削減する等の最適化が可能となる。
【０００３】
たとえば図６（ａ）はＣ言語で書かれたプログラム例である。このプログラムのコンパイル時に、ポインタｐの指示先がｘであることがわかれば、文６０２と文６０４の間で定義される変数はｘとｙのみであり、ａの値は変化しないことがわかる。従って、文６０４で使用している変数ａの値に対して、文６０２での値を再利用し、ロード命令を削減する最適化が可能となる。
【０００４】
従来のポインタ解析では、プログラム中のポインタへの代入文を調べ、ポインタにアドレス値が代入される変数を求め、それらの変数の集合をポインタの指示先としていた。
【０００５】
ポインタ解析およびその結果を利用した最適化に関しては、「ポインタ変数のコンパイルを最適化する方法」と題する特許文献１に示されている手法がある。これによって、変数を指示するポインタを用いたプログラムを最適化し、効率的な実行コードを生成することができる。
【０００６】
【特許文献１】
特開平１０−２６９０８８号公報
【０００７】
【発明が解決しようとする課題】
組み込み用プロセッサを用いた制御システムでは、外部デバイスとのデータのやりとりに特定の定数アドレスから始まるメモリ領域（定数アドレス領域）を利用することが多い。制御プログラムでは、ポインタに定数アドレスを代入し、定数アドレス領域をポインタの指示先とすることで、ポインタを用いてデータを読み書きする。従来技術によるポインタ解析では、このようにポインタに定数を代入しているプログラムについては、その指示先に対応する変数が特定できないため、指示先は不明であり、すべての変数が指示先になり得るとみなさざるを得なかった。そのため、定数アドレス領域を利用するプログラムでは最適化が阻害され、効率的な実行コードが生成できなかった。たとえば図６（ａ）の文６０１を定数アドレスの代入文に変更した図６（ｂ）の例では、ポインタｐの指示先が不明と解析され、文６０７で変数ａの値が変更される可能性があるため、文６０８で使用している変数ａの値のロード命令を削除する最適化が行えなかった。
【０００８】
【課題を解決するための手段】
本発明では上記課題を解決するために、プログラム中のポインタについて、その指示先が定数アドレス領域に限定されるかどうかを判定する解析を行う。
【０００９】
ポインタの指示先に変数メモリ領域が含まれる場合、そのアドレス値はポインタ解析時に確定しないため、ポインタの値は数値として求めることができない。逆にポインタの値が常に何らかの数値として求められる場合、そのポインタの指示先は変数メモリ領域でないと判断してよい。ここで何らかの数値として求められるとは、プログラムの実行を通じて常に一定の値であるという意味ではなく、変数のアドレス値が確定していない状態においてその値が求められる、すなわち変数のアドレス値に依存しない値である、という意味である。以後、この意味での数値のことを確定値と称する。
【００１０】
ポインタの指示先が定数アドレス領域に限定されることが判定できれば、たとえば、ある文でそのポインタの指示先に値を代入していても、代入先は変数でなく、その文によって変数の値は変化しないことがわかる。そのため、この文をまたいで存在する冗長な変数値のロード命令を削除する等の最適化が可能となる。
【００１１】
ポインタの指示先が定数アドレス領域に限定されるかどうか、すなわちポインタの値が確定値かどうかの判定は次のようにして行う。
【００１２】
ポインタを含めたすべての変数および式の値を、未定値、確定値、非確定値の３つに分類する。未定値は未初期化状態の変数の値、確定値は前述した確定値、非確定値は確定値でない、もしくは確定値であるかどうか不明な値、をそれぞれ意味している。
【００１３】
プログラム中の代入文ごとに、代入値がこの３つのいずれに相当するかを調べ、代入先の変数の値を更新する。更新は、未定値≦確定値≦非確定値という順序関係に基づき、より大きな値になる場合に限って行う。これにより、一度でも非確定値を代入された変数の値は必ず非確定値となる。すべての変数の値を未定値に設定し、値が変化しなくなるまで解析を繰り返すことで、確定値となるポインタを求めることができる。
【００１４】
【発明の実施の形態】
以下、比較処理の一括化の場合における本発明の一実施例を説明する。
【００１５】
図１は本発明によるコンパイラが稼動する計算機システムの構成図である。図示するように、計算機システムはＣＰＵ１０１、主記憶装置１０４、外部記憶装置１０５、ディスプレイ装置１０２、キーボード１０３より構成されている。外部記憶装置１０５にはソースプログラム１０６、実行コード１０７が格納される。主記憶装置１０４には、コンパイラ１０８と、コンパイル処理過程で必要となる中間コード１０９、ポインタ指示先表１１０、確定値情報表１１１が保持される。コンパイル処理はＣＰＵ１０１がコンパイラプログラム１０８を実行することにより行われる。キーボード１０３はユーザからのコマンドをコンパイラ１０８に与えるのに用いる。ディスプレイ装置１０２はコンパイルの終了またはエラーをユーザに知らせる。
【００１６】
図２はコンパイル処理の流れを示したフローチャートである。コンパイラの処理は、まずステップ２０１で、構文解析を行う。構文解析はソースプログラム１０６を読み出し、コンパイラ内部で処理可能な中間コード１０９を作成する。構文解析処理については、たとえば「エイホ、セシィ、ウルマン著：コンパイラＩ（サイエンス社、１９９０年）３０頁〜７４頁」に記載されている。次にステップ２０２で、従来技術である変数メモリ領域に関するポインタ解析を行う。従来技術であるポインタ解析については、たとえば「エイホ、セシィ、ウルマン著：コンパイラＩＩ（サイエンス社、１９９０年）７９０頁〜８０６頁」に記載がある。従来技術であるポインタ解析により、プログラム中のポインタの指示先が求められ、これがポインタ指示先表１１０に記録される。次にステップ２０３で、ポインタが定数アドレス領域を指示するかどうかの解析を行う。この処理については図３を用いてさらに詳しく説明する。次にステップ２０４でポインタ指示先表１１０を用いた最適化を行う。最適化については、たとえば「エイホ、セシィ、ウルマン著：コンパイラＩＩ（サイエンス社、１９９０年）７１４頁〜８８１頁」に記載がある。最後にステップ２０５で実行コード生成を行う。実行コード生成については、たとえば「エイホ、セシィ、ウルマン著：コンパイラＩＩ（サイエンス社、１９９０年）６２４頁〜７０７頁」に記載がある。
【００１７】
図３はステップ２０３の処理の流れを詳しく示した図である。ここでは、ポインタが定数アドレス領域を指示するかどうかの解析を行い、解析結果をもとにポインタ指示先表１１０を更新する。
【００１８】
ステップ３０１は解析の初期化処理である。確定値情報表１１１に、すべての変数の値を未定値として初期設定する。次にステップ３０２へ進み、未処理の代入文があるかどうかを調べる。あればステップ３０３へ進み、未処理の代入文をひとつ取り出す（ｓとする）。次にステップ３０４で、ｓの代入先が定数アドレス領域に限定されるかどうかを調べる。この処理については図４を用いてさらに詳しく説明する。代入先が定数アドレス領域に限定されるならば、ｓによって変数の値は変化しないので、ステップ３０２へ戻り、次の文の処理に移る。そうでなければ、ステップ３０５へ進み、代入先の変数集合を求める（Ｖとする）。代入先がポインタの指示先の場合、Ｖはポインタ指示先表１１０にあるすべての指示先となる。次にステップ３０６へ進み、ｓの代入元が確定値かどうかを調べる。この処理については図５を用いてさらに詳しく説明する。代入元が確定値であればステップ３０７へ進み、Ｖのなかで値が未定値である変数の値を確定値に変更し、ステップ３０２へ戻る。そうでなければステップ３０８へ進み、Ｖのすべての変数の値を非確定値に変更し、ステップ３０２へ戻る。ステップ３０２へ戻って、未処理の代入文がなければ、ステップ３０９へ進み、確定値情報表１１１が変化したかどうかを調べる。変化していたらステップ３１０へ進み、すべての代入文を未処理とし、ステップ３０２へ進み、解析を反復する。そうでなければステップ３１１へ進み、確定値情報表１１１で確定値となっているすべてのポインタについて、ポインタ指示先表１１０にある指示先からすべての変数を削除する。
【００１９】
図４はステップ３０４の処理の流れを詳しく示した図である。ここでは与えられた代入先が定数アドレス領域に限定されるかどうかの判定を行う。
【００２０】
まずステップ４０１で代入先がポインタを用いた間接参照式であるかを調べる。間接参照式でなければ、代入先は変数であるため、ステップ４０４へ進み、代入先は定数アドレス領域に限定されないと判定する。間接参照式であればステップ４０２へ進み、確定値情報表１１１における値が確定値であるポインタの指示先を参照する式であるかを調べる。そうであればステップ４０３へ進み、代入先は定数アドレス領域に限定されると判定する。そうでなければステップ４０４へ進み、代入先は定数アドレス領域に限定されないと判定する。
【００２１】
図５はステップ３０６の処理の流れを詳しく示した図である。ここでは代入元の式の値が確定値であるかどうかの判定を行う。
【００２２】
まずステップ５０１で代入値が定数であるかどうかを調べる。定数であればステップ５０６へ進み確定値であると判定する。そうでなければステップ５０２へ進み、値が確定値である変数であるかどうかを調べる。そうであればステップ５０６へ進み確定値であると判定する。そうでなければステップ５０３へ進み、算術または論理演算式であるかを調べる。そうでなければステップ５０５へ進み確定値でないと判定する。そうであればステップ５０４へ進み、すべてのオペランドが確定値であるかを調べる。そうであればステップ５０６へ進み確定値であると判定する。そうでなければステップ５０５へ進み確定値でないと判定する。
【００２３】
続いて、本実施例の適用例を示す。入力として図７（ａ）のようなプログラムを考える。
【００２４】
図２のステップ２０２のポインタ解析により、図７（ｂ）のようなポインタ指示先表を作成する。
【００２５】
次にステップ２０３でポインタが定数アドレス領域を指示するかどうかの解析を行う。ステップ２０３を詳しくした図３では、最初にステップ３０１で確定値情報表にすべての変数の値を未定値として初期設定する。初期設定した確定値情報表を図７（ｃ）の（７０７）に示す。次にステップ３０２へ進み、すべての代入文が未処理なのでステップ３０３へ進み、未処理の代入文として文７０１を取り出す。次にステップ３０４へ進み、代入先が定数アドレス領域に限定されるかどうかの判定を行う。ステップ３０４を詳しくした図４では、最初にステップ４０１で代入先がポインタを用いた間接参照式であるかを調べる。文７０１の代入先は変数ｑであり間接参照式ではないので、ステップ４０４へ進み、代入先が定数アドレス領域に限定されることはないと判定する。そこでステップ３０５へ進み、代入先の変数集合Ｖを求める。代入先は変数ｑであり、Ｖ＝｛ｑ｝となる。次にステップ３０６へ進み、代入元が確定値かどうかを判定する。ステップ３０６を詳しくした図５において、代入元の式＆ｄａｔａは定数、変数、算術または論理演算式のいずれでもないので、ステップ５０１からステップ５０２、ステップ５０３、ステップ５０５と進み、確定値でないと判定する。そこでステップ３０８に進み、変数ｑの値を非確定値に変更し、ステップ３０２へ戻る。未処理な代入文はまだ存在するので、ステップ３０３へ進み、未処理の代入文として文７０２を取り出す。代入先は変数ｂａｓｅなので、文１と同様の処理によってステップ３０４からステップ３０５へ進み、Ｖ＝｛ｂａｓｅ｝となる。次にステップ３０６へ進み、代入元が確定値かどうかを判定する。ステップ３０６を詳しくした図５において、代入元の式（ｉｎｔ　＊）０ｘ０ｆ００は定数なので、ステップ５０１からステップ５０６へ進み、確定値であると判定する。そこでステップ３０７に進み、変数ｂａｓｅの値は未定値なので、これを確定値に変更し、ステップ３０２へ戻る。未処理な代入文はまだ存在するので、ステップ３０３へ進み、未処理の代入文として文７０３を取り出す。文７０３に対する処理は文７０２と同様であり、ステップ３０４、ステップ３０５、ステップ３０６、ステップ３０７と進み、変数ｓｔｒｉｄｅの値を確定値に変更し、ステップ３０２へ戻る。未処理な代入文はまだ存在するので、ステップ３０３へ進み、未処理の代入文として文７０４を取り出す。代入先は変数ｐなので、文１と同様の処理によってステップ３０４からステップ３０５へ進み、Ｖ＝｛ｐ｝となる。次にステップ３０６へ進み、代入元が確定値かどうかを判定する。ステップ３０６を詳しくした図５において、代入元の式ｂａｓｅは、文７０２の処理によって確定値になっているため、ステップ５０１、ステップ５０２、ステップ５０６と進み、確定値であると判定する。そこでステップ３０７に進み、変数ｐの値は未定値なので、これを確定値に変更し、ステップ３０２へ戻る。未処理な代入文はまだ存在するので、ステップ３０３へ進み、未処理の代入文として文７０５を取り出す。ステップ３０４を詳しくした図４において、代入先＊ｐはポインタを用いた間接参照式なので、ステップ４０１からステップ４０２へ進む。変数ｐの値は文７０４の処理によって確定値になっているため、ステップ４０３へ進み、代入先は定数アドレス領域に限定されると判定する。そこでこの文の処理は終了し、ステップ３０２へ戻る。未処理な代入文はまだ存在するので、ステップ３０３へ進み、未処理の代入文として文７０６を取り出す。代入先は変数ｐなので、文７０４と同様の処理によってステップ３０４からステップ３０５へ進み、Ｖ＝｛ｐ｝となる。次にステップ３０６へ進み、代入元が確定値かどうかを判定する。ステップ３０６を詳しくした図５において、代入元の式ｐ＋１は算術演算式なのでステップ５０１から、ステップ５０２、ステップ５０３、ステップ５０４と進み、オペランドであるｐおよび１が確定値であるかを調べる。ｐは値が確定値である変数であり、１は定数であるため、これらは共に確定値となる。そこでステップ５０６へ進み、代入元の式ｐ＋１は確定値であると判定する。そこでステップ３０７へ進むが、変数ｐの値はすでに確定値であるため、値を変更することはなく、ステップ３０２へ戻る。この時点で未処理な代入文は存在しないため、ステップ３０９へ進み、確定値情報表が変化したかを調べる。１度目の解析によって得た確定値情報表を図７（ｃ）の（７０８）に示す。確定値情報表の値は初期設定時から変化しているので、ステップ３１０へ進み、すべての文を未処理にしてステップ３０２へ戻り、解析を反復する。前回と同様にすべての文を処理し、ステップ３０９へ進むと、今度は確定値情報表は変化していないことがわかる。そこでステップ３１１へ進み、値が確定値であるポインタｐおよびｂａｓｅについて、ポインタ指示先表にある指示先からすべての変数を削除する。更新後のポインタ指示先表は図７（ｄ）のようになる。
【００２６】
ステップ２０３によって更新されたポインタ指示先表を用いると、ステップ２０４において、文５で変数ｑおよびｑの指示先であるｄａｔａの値は更新されないことがわかるため、本来であればループの繰り返しの度に必要となるｑおよびｑの指示先のロード命令をループの外側に移動する最適化が可能となる。これによりステップ２０５では、メモリ参照命令の数および実行時のメモリ参照回数のより少ない実行コードが生成できる。
【００２７】
【発明の効果】
本発明によれば、コンパイラは定数アドレス領域をポインタの指示先として参照するプログラムにおいて、ポインタの指示先に変数メモリ領域が含まれないことを利用した最適化を適用することが可能となる。これにより、実行コードサイズの縮小および実行速度の向上に効果がある。
【図面の簡単な説明】
【図１】本発明のコンパイラが稼動する計算機システムの構成図。
【図２】コンパイラの処理の流れを示す図。
【図３】指示先が定数アドレス領域に限定されるポインタの解析処理の流れを示す図。
【図４】代入先が定数アドレス領域に限定されるかどうかの判定処理の流れを示す図。
【図５】代入値が確定値であるかどうかの判定処理の流れを示す図。
【図６】従来技術の例を示す図。
【図７】本発明の例を示す図。
【符号の説明】
１０１…ＣＰＵ、１０２…ディスプレイ装置、１０３…キーボード、１０４…主記憶装置、１０５…外部記憶装置、１０８…コンパイラ。
【図１】
2004139369.tif 000003
【図２】
2004139369.tif 000004
【図３】
2004139369.tif 000005
【図４】
2004139369.tif 000006
【図５】
2004139369.tif 000007
【図６】
2004139369.tif 000008
【図７】
2004139369.tif 000009