(57)【要約】【課題】プログラムで用いられるレジスタの数を減らす。【解決手段】プログラムを最適化するコンパイラ装置は、プログラムの複数の命令間に定められた順序制約情報を取得する順序制約情報取得部と、複数の命令のそれぞれが実行される実行順序を、順序制約情報に基づいて順次決定する順序決定部と、実行順序が決定された命令を実行した場合に必要となるレジスタの数である必要レジスタ数を解析するレジスタ数解析部と、２つの命令の組合せであって、一方の命令が順序既決定命令であり、他方の命令が順序未決定命令であり、かつ一方の命令が他方の命令より先に実行されるべき順序の制約が順序制約情報に含まれない組合せを検出する命令検出部と、必要レジスタ数が予め定められた数を超える場合に、一方の命令を実行順序が決定されていない状態に変更し、他方の命令の次に一方の命令が実行されるべく実行順序を決定させる順序決定再処理部とを備える。【選択図】  図１
2004280744.tif 000002
【特許請求の範囲】
【請求項１】
コンパイル対象のプログラムである対象プログラムにおいて、命令が実行される順序を変更することにより前記対象プログラムを最適化するコンパイラ装置であって、
前記対象プログラムの複数の命令間に定められた、複数の命令が実行されるべき順序の制約を示す順序制約情報を取得する順序制約情報取得部と、
前記複数の命令のそれぞれが実行される実行順序を、前記順序制約情報に基づいて順次決定する順序決定部と、
前記複数の命令のうち、前記実行順序が決定された命令を実行した場合に必要となるレジスタの数である必要レジスタ数を解析するレジスタ数解析部と、
２つの命令の組合せであって、一方の命令が前記順序決定部により前記実行順序が既に決定されている順序既決定命令であり、他方の命令が前記順序決定部により前記実行順序が未だ決定されていない順序未決定命令であり、かつ前記一方の命令が前記他方の命令より先に実行されるべき順序の制約が前記順序制約情報に含まれない組合せを検出する命令検出部と、
前記必要レジスタ数が予め定められた数を超える場合に、前記一方の命令を前記実行順序が決定されていない状態に変更し、前記他方の命令の次に前記一方の命令が実行されるべく前記順序決定部により実行順序を決定させる順序決定再処理部と
を備えるコンパイラ装置。
【請求項２】
前記命令検出部は、前記他方の命令として、レジスタを解放する解放命令を検出し、前記一方の命令として、レジスタを新たに確保する確保命令を検出する請求項１記載のコンパイラ装置。
【請求項３】
前記命令検出部は、前記他方の命令として、レジスタを解放する解放命令を検出し、前記一方の命令として、レジスタを新たに確保する順序既決定命令より前に実行されるべき命令を検出し、
前記順序決定再処理部は、前記順序制約情報において前記順序既決定命令より後に実行されるべき全ての命令を、前記実行順序が決定されていない状態に更に変更する請求項１記載のコンパイラ装置。
【請求項４】
前記順序決定再処理部は、前記一方の命令及び前記他方の命令の組合せが前記命令検出部により複数検出された場合に、複数の前記組合せのうち、対象プログラムの開始点から前記他方の命令に至る順序の制約の深さと、前記一方の命令から対象プログラムの終了点に至る順序の制約の深さとの合計が最小となる組合せを選択し、選択した当該組合せに含まれる他方の命令及び一方の命令を用いて、実行順序を前記順序決定部により決定させる請求項１記載のコンパイラ装置。
【請求項５】
前記順序決定再処理部は、前記必要レジスタ数が予め定められた数を超える場合に、前記順序未決定命令の次に前記順序既決定命令を実行すべきことを示す順序の制約を、前記順序制約情報に追加することにより、前記順序未決定命令の次に前記順序既決定命令が実行される実行順序を、前記順序決定部により決定させる請求項１記載のコンパイラ装置。
【請求項６】
前記順序制約情報取得部は、前記対象プログラムの各命令をノードで表し、複数の命令が実行されるべき順序の制約を有向エッジで表した順序制約グラフを、前記順序制約情報として取得し、
前記順序決定部は、前記順序制約グラフに基づいて、有向エッジの始点のノードとして表された命令を、当該有向エッジの終点のノードとして表された命令より先に実行する前記実行順序を決定し、
前記命令検出部は、２つの命令の組合せであって、順序制約グラフにおいて、一方の命令を表すノードから他方の命令を表すノードに到達不能な命令の組合せを検出することにより、一方の命令が他方の命令より先に実行されるべき順序の制約が順序制約情報に含まれない組合せであることを検出し、
前記順序決定再処理部は、前記順序未決定命令を示すノードから、前記他方の命令を示すノードへの有向エッジを生成することにより、前記一方の命令の次に前記他方の命令を実行すべきことを示す順序の制約を、前記順序制約情報に追加する請求項５記載のコンパイラ装置。
【請求項７】
コンパイル対象のプログラムである対象プログラムにおいて、命令が実行される順序を変更することにより前記対象プログラムを最適化するコンパイラ装置としてコンピュータを機能させるコンパイラプログラムであって、
前記コンピュータを、
前記対象プログラムの複数の命令間に定められた、複数の命令が実行されるべき順序の制約を示す順序制約情報を取得する順序制約情報取得部と、
前記複数の命令のそれぞれが実行される実行順序を、前記順序制約情報に基づいて順次決定する順序決定部と、
前記複数の命令のうち、前記実行順序が決定された命令を実行した場合に必要となるレジスタの数である必要レジスタ数を解析するレジスタ数解析部と、
２つの命令の組合せであって、一方の命令が前記順序決定部により前記実行順序が既に決定されている順序既決定命令であり、他方の命令が前記順序決定部により前記実行順序が未だ決定されていない順序未決定命令であり、かつ前記一方の命令が前記他方の命令より先に実行されるべき順序の制約が前記順序制約情報に含まれない組合せを検出する命令検出部と、
前記必要レジスタ数が予め定められた数を超える場合に、前記一方の命令を前記実行順序が決定されていない状態に変更し、前記他方の命令の次に前記一方の命令が実行されるべく前記順序決定部により実行順序を決定させる順序決定再処理部として機能させるコンパイラプログラム。
【請求項８】
前記命令検出部は、前記他方の命令として、レジスタを解放する解放命令を検出し、前記一方の命令として、レジスタを新たに確保する確保命令を検出する請求項７記載のコンパイラプログラム。
【請求項９】
前記順序決定再処理部は、前記必要レジスタ数が予め定められた数を超える場合に、前記他方の命令の次に前記一方の命令を実行すべきことを示す順序の制約を、前記順序制約情報に追加することにより、前記他方の命令の次に前記一方の命令が実行される実行順序を、前記順序決定部により決定させる請求項７記載のコンパイラプログラム。
【請求項１０】
請求項７から請求項９の何れかに記載のコンパイラプログラムを記録した記録媒体。
【請求項１１】
コンピュータにより、コンパイル対象のプログラムである対象プログラムにおいて、命令が実行される順序を変更することにより前記対象プログラムを最適化するコンパイル方法であって、
前記対象プログラムの複数の命令間に定められた、複数の命令が実行されるべき順序の制約を示す順序制約情報を取得する順序制約情報取得段階と、
前記複数の命令のそれぞれが実行される実行順序を、前記順序制約情報に基づいて順次決定する順序決定段階と、
前記複数の命令のうち、前記実行順序が決定された命令を実行した場合に必要となるレジスタの数である必要レジスタ数を解析するレジスタ数解析段階と、
２つの命令の組合せであって、一方の命令が前記順序決定部により前記実行順序が既に決定されている順序既決定命令であり、他方の命令が前記順序決定部により前記実行順序が未だ決定されていない順序未決定命令であり、かつ前記一方の命令が前記他方の命令より先に実行されるべき順序の制約が前記順序制約情報に含まれない組合せを検出する命令検出段階と、
前記必要レジスタ数が予め定められた数を超える場合に、前記一方の命令を前記実行順序が決定されていない状態に変更し、前記他方の命令の次に前記一方の命令が実行されるべく前記順序決定部により実行順序を決定させる順序決定再処理段階と
を備えるコンパイル方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンパイラ装置、コンパイラプログラム、記録媒体、及びコンパイル方法に関する。特に本発明は、命令の実行順序を変更することによりプログラムを最適化するコンパイラ装置、コンパイラプログラム、記録媒体、及びコンパイル方法に関する。
【０００２】
【従来の技術】
従来、プログラムで用いられるレジスタの数を減らすことができる命令スケジューラが提案されている（非特許文献１参照。）。このスケジューラは、用いられるレジスタの数の最小値を解析するグラフ彩色処理を行うことにより、命令の実行順序を適切に決定し、コンパイル対象のプログラムを高速に動作させることができる。
【０００３】
【非特許文献１】
Ｒ．Ｇｏｖｉｎｄａｒａｊａｎ、Ｈｏｎｇｂｏ  Ｙａｎｇ、Ｃｈｉｈｏｎｇ  Ｚｈａｎｇ、  及びＧｕａｎｇ  Ｒ．  Ｇａｏ著、”Ｍｉｎｉｍｕｍ  Ｒｅｇｉｓｔｅｒ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｅｑｕｅｎｃｅ  Ｐｒｏｂｌｅｍ：Ｒｅｖｉｓｉｔｉｎｇ  Ｏｐｔｉｍａｌ  Ｃｏｄｅ  Ｇｅｎｅｒａｔｉｏｎｆｏｒ  ＤＡＧｓ”、国際並列分散処理シンポジウム（Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｐａｒａｌｌｅｌ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｙｍｐｏｓｉｕｍ）会議録、２００１年４月、邦題「最小レジスタ数命令順列問題：ＤＡＧに対する最適なコード生成処理への再訪」
【０００４】
【発明が解決しようとする課題】
しかしながら、上記技術は、グラフ彩色処理によって解析された数を超えた数のレジスタを必要とする場合がある。この結果、必要とするレジスタの数が、コンピュータに設けられたレジスタ数を超える場合には、レジスタより低速なメモリを用いて演算を行わなければならず、効率が悪い。
そこで本発明は、上記の課題を解決することのできるコンパイラ装置、コンパイラプログラム、記録媒体、及びコンパイル方法を提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【０００５】
【課題を解決するための手段】
即ち、本発明の第１の形態によると、コンパイル対象のプログラムである対象プログラムにおいて、命令が実行される順序を変更することにより対象プログラムを最適化するコンパイラ装置であって、対象プログラムの複数の命令間に定められた、複数の命令が実行されるべき順序の制約を示す順序制約情報を取得する順序制約情報取得部と、複数の命令のそれぞれが実行される実行順序を、順序制約情報に基づいて順次決定する順序決定部と、複数の命令のうち、実行順序が決定された命令を実行した場合に必要となるレジスタの数である必要レジスタ数を解析するレジスタ数解析部と、２つの命令の組合せであって、一方の命令が順序決定部により実行順序が既に決定されている順序既決定命令であり、他方の命令が順序決定部により実行順序が未だ決定されていない順序未決定命令であり、かつ一方の命令が他方の命令より先に実行されるべき順序の制約が順序制約情報に含まれない組合せを検出する命令検出部と、必要レジスタ数が予め定められた数を超える場合に、一方の命令を実行順序が決定されていない状態に変更し、他方の命令の次に一方の命令が実行されるべく順序決定部により実行順序を決定させる順序決定再処理部とを備えるコンパイラ装置、コンパイル方法、コンパイラプログラム、及び記録媒体を提供する。
なお上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションも又発明となりうる。
【０００６】
【発明の実施の形態】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、又実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【０００７】
図１は、コンパイラ装置１０の機能ブロック図を示す。コンパイラ装置１０は、命令の実行順序を最適化する装置であり、命令が実行される実行順序を順次決定する過程で、必要に応じて一旦決定した実行順序を取り消し、実行順序の決定を再処理することを特徴とする。コンパイラ装置１０は、順序制約取得部１００と、順序制約グラフ格納部１０５と、順序決定部１１０と、レジスタ数解析部１２０と、命令検出部１３０と、順序決定再処理部１４０とを備える。
【０００８】
順序制約取得部１００は、コンパイル対象のプログラムである対象プログラムの命令間に定められた、複数の命令が実行されるべき順序の制約を示す順序制約情報を、当該対象プログラムと共に取得する。一例としては、順序制約取得部１００は、当該対象プログラムの各命令をノードで表し、複数の命令が実行されるべき順序の制約を有向エッジで表した順序制約グラフを、順序制約情報として取得し、順序制約グラフ格納部１０５に格納する。そして、順序制約取得部１００は、対象プログラムを受け取った旨を、順序決定部１１０に通知する。
【０００９】
なお、コンパイル対象の対象プログラムは、最適化を効率良く行うべくソースプログラムから生成された中間表現であり、例えば、Ｊａｖａ（登録商標）言語のバイトコードである。これに代えて、対象プログラムは、ＲＴＬ（Ｒｅｇｉｓｔｅｒ  Ｔｒａｎｓｆｅｒ  Ｌａｎｇｕａｇｅ）であってもよいし、四つ組表現であってもよい。また、対象プログラムとは、利用者により実行される対象プログラム全体であってもよいし、対象プログラムのうちの一つの機能を示すモジュールであってもよい。モジュールとは、例えば、メソッド（ｍｅｔｈｏｄ）、関数（ｆｕｎｃｔｉｏｎ）、又は手続（ｐｒｏｃｅｄｕｒｅ）である。これに代えて、モジュールとは、最初に実行される命令及び最後に実行される命令以外の命令が、分岐命令の分岐元及び分岐命令の分岐先の何れでもない命令の集合である基本ブロック（Ｂａｓｉｃ  Ｂｌｏｃｋ）であってもよい。また、命令とは、上記中間表現を構成する処理の１単位であり、コンピュータに一つの処理を行わせる指示を示す。一例としては、命令は、コンピュータのインストラクション（ｉｎｓｔｒｕｃｔｉｏｎ）であってもよいし、インストラクションの集合であってもよい。
【００１０】
順序決定部１１０は、コンパイル対象の対象プログラムを受け取った旨を、順序制約取得部１００から受け取ると、順序制約グラフを順序制約グラフ格納部１０５から取得する。続いて、順序決定部１１０は、複数の命令のそれぞれが実行される実行順序を、順序制約グラフに基づいて決定する。例えば、順序決定部１１０は、命令の実行順序の決定を継続する旨をレジスタ数解析部１２０から受け取る毎に、以下に示す順序決定処理を行う。まず、順序決定部１１０は、順序制約グラフにおけるノードであって、当該ノードより先に実行されるべき全ての先行ノードの実行順序が既に決定されたノードを選択する。そして、順序決定部１１０は、選択した当該ノードとして表される命令を、既に実行順序を決定した命令の次に実行されるように実行順序を決定する。そして、順序決定部１１０は、決定した実行順序を、レジスタ数解析部１２０に通知する。即ち、順序決定部１１０は、順序制約グラフに基づいて、有向エッジの始点のノードとして表された命令を、有向エッジの終点のノードとして表された命令より先に実行されるように、実行順序を決定する。
【００１１】
また、順序決定部１１０は、命令を、実行順序が決定されていない状態に変更する旨を、順序決定再処理部１４０から受け取った場合に、当該命令及び当該命令より後に実行されるべき順序既決定命令を、実行順序が決定されていない状態に変更する。そして、順序決定部１１０は、上記の順序決定処理を行う。
【００１２】
レジスタ数解析部１２０は、実行順序を順序決定部１１０から受け取ると、実行順序が決定された命令を実行した場合に必要となるレジスタの数である必要レジスタ数を、順序制約グラフ格納部１０５から取得した順序制約グラフに基づいて解析する。そして、レジスタ数解析部１２０は、必要レジスタ数が予め定められた規定レジスタ数を超える場合に、その旨を示すレジスタ数超過通知を命令検出部１３０に送る。一方、レジスタ数解析部１２０は、必要レジスタ数が予め定められた規定レジスタ数を超えない場合に、命令の実行順序の決定を継続する旨を順序決定部１１０に通知する。
【００１３】
命令検出部１３０は、順序制約グラフ格納部１０５から順序制約グラフを取得する。そして、レジスタ数超過通知をレジスタ数解析部１２０から受け取った場合に、命令検出部１３０は、以下に示す条件を満たす、２つの命令の組合せを検出する。その条件とは、２つの命令のうち、一方の命令が、順序決定部１１０により実行順序が既に決定されレジスタを解放する命令である順序既決定命令であり、他方の命令が、順序決定部１１０により実行順序が未だ決定されておらずレジスタを新たに確保する順序未決定命令であり、かつ当該一方の命令が当該他方の命令より先に実行されるべき順序の制約が順序制約情報に含まれないことである。具体的には、命令検出部１３０は、順序制約グラフにおいて、一方の命令を表すノードから他方の命令を表すノードに到達不能な命令の組合せを検出することにより、一方の命令が他方の命令より先に実行されるべき順序の制約が順序制約情報に含まれない組合せであることを検出する。
【００１４】
順序決定再処理部１４０は、上記他方の命令を示すノードから上記一方の命令を示すノードへの有向エッジを生成することにより、他方の命令の次に一方の命令を実行すべきことを示す順序の制約を、順序制約情報に追加する。更に、順序決定再処理部１４０は、一方の命令を、実行順序が決定されていない状態に変更する旨を順序決定部１１０に通知する。これにより、順序決定再処理部１４０は、一方の命令と、順序制約情報においてこの一方の命令より後に実行されるべき全ての命令とを、実行順序が決定されていない状態に変更し、他方の命令の次に一方の命令が実行されるように、順序決定部１１０により実行順序を決定させることができる。
【００１５】
図２は、コンパイラ装置１０のフローチャートを示す。順序制約取得部１００は、順序制約グラフを取得する（Ｓ２００）。そして、順序決定部１１０は、取得した順序制約グラフに、必要に応じて、新たな順序制約を追加する（Ｓ２１０）。例えば、順序決定部１１０は、順序制約グラフにおいて、より後に実行されるべき複数の後続ノードを有する先行ノードを検出する。そして、順序決定部１１０は、先行ノードとして表された命令において確保されたレジスタを再利用する命令を示すノードを、当該複数の後続ノードの中から選択する。順序決定部１１０は、選択した当該ノードを除外した複数の後続ノードのそれぞれから、選択した当該ノードに至る有向エッジを追加する。続いて、順序決定部１１０は、実行順序を決定する準備として、対象プログラムの各命令において、当該命令が確保又は解放するレジスタの数を算出し、順序制約グラフの各ノードに対応付けて格納しておく。
また、順序決定部１１０は、命令検出部１３０により命令の組合せを高速に検出させるべく、実行順序が決定され、かつレジスタを新たに確保する命令の集合であるＧｅｎと、実行順序が決定されておらず、かつレジスタを解放する命令の集合であるＫｉｌｌとを初期化する。例えば、順序決定部１１０は、Ｇｅｎを空集合とし、Ｋｉｌｌを、対象プログラムにおいてレジスタを解放する全ての命令とする。
【００１６】
順序決定部１１０は、複数の命令のそれぞれが実行される実行順序を、順序制約グラフに基づいて決定する（Ｓ２２０）。例えば、順序決定部１１０は、順序制約グラフにおけるノードであって、当該ノードに先行する全てのノードの実行順序が既に決定されたノードを選択する。そして、順序決定部１１０は、選択した当該ノードとして表される命令を、既に実行順序を決定した命令の次に実行されるように実行順序を決定する。選択するべき複数のノードがある場合には、一例としては、順序決定部１１０は、当該複数のノードが示す命令のうち、命令の実行を開始してから終了するまでに要する時間であるレイテンシが最も大きい命令を選択し、実行順序を決定する。そして、順序決定部１１０は、新たに実行順序を決定した命令がレジスタを確保する命令である場合に、当該命令をＧｅｎに追加し、当該命令がレジスタを解放する命令である場合に、当該命令をＫｉｌｌから除外する。
【００１７】
レジスタ数解析部１２０は、実行順序が決定された命令を実行した場合に必要となる必要レジスタ数を、順序制約グラフに基づいて解析する（Ｓ２３０）。例えば、レジスタ数解析部１２０は、対象プログラム中で最初に実行される命令の実行順序が決定された場合に、当該命令が確保するレジスタの数を必要レジスタ数とする。そして、レジスタ数解析部１２０は、新たに命令の実行順序が決定される毎に、当該命令が確保するレジスタの数を、必要レジスタ数に加え、当該命令が解放するレジスタの数を、必要レジスタ数から減じる。
【００１８】
レジスタ数解析部１２０は、必要レジスタ数が規定レジスタ数を超えない場合に（Ｓ２４０：ＮＯ）、対象プログラム中の全ての命令の実行順序が決定されたか否かを判断する（Ｓ２５０）。全ての命令の実行順序が決定された場合に、コンパイラ装置１０は、処理を終了する。何れかの命令の実行順序が決定されていない場合に、コンパイラ装置１０は、Ｓ２２０に処理を移す。
【００１９】
一方、必要レジスタ数が規定レジスタ数を超える場合に（Ｓ２４０：ＹＥＳ）、命令検出部１３０は、Ｇｅｎに含まれる順序未決定命令及びＫｉｌｌに含まれる順序既決定命令のうち、順序未決定命令を表すノードから順序気決定命令を表すノードに到達不能な命令の組合せを検出する（Ｓ２６０）。即ち、命令検出部は、２つの命令のうち、一方の命令が、順序決定部１１０により実行順序が既に決定されレジスタを解放する命令である順序既決定命令であり、他方の命令が、順序決定部１１０により実行順序が未だ決定されておらずレジスタを新たに確保する順序未決定命令であり、かつ当該一方の命令が当該他方の命令より先に実行されるべき順序の制約が順序制約情報に含まれない命令の組合せを検出する。
なお、上記の条件を満たす命令の組合せが複数検出された場合に、命令検出部１３０は、当該複数の組合せのうち、対象プログラムの開始点から順序未決定命令に至る順序の制約の深さと、順序既決定命令から対象プログラムの終了点に至る順序の制約の深さとの合計が最小となる組合せを選択する。
【００２０】
順序決定再処理部１４０は、順序制約グラフにおいて、上記他方の命令を示すノードから上記一方の命令を示すノードへの有向エッジを生成することにより、他方の命令の次に一方の命令を実行すべきことを示す順序の制約を、順序制約情報に追加する（Ｓ２７０）。
【００２１】
そして、順序決定再処理部１４０は、上記一方の命令と、順序制約情報においてこの一方の命令より後に実行されるべき全ての命令とを、実行順序が決定されていない状態に変更する（Ｓ２８０）。また、順序決定再処理部１４０は、実行順序が決定されていない状態に変更した当該命令が、レジスタを確保する命令である場合に、当該命令をＧｅｎから除外し、当該命令がレジスタを解放する命令である場合に、当該命令をＫｉｌｌに追加する。続いて、コンパイラ装置１０は、Ｓ２２０に処理を移すことにより、順序未決定命令の次に順序既決定命令が実行されるように、順序決定部１１０により実行順序を決定させる。
【００２２】
図３は、順序制約取得部１００により順序制約グラフ格納部１０５に格納される順序制約グラフの一例を示す。ａからｈと書かれた円のそれぞれは、順序制約グラフにおいて、命令ａから命令ｈのそれぞれを表すノードである。また、ノード間を接続する矢印は、順序制約グラフにおける有向エッジを示す。即ち、本図の例では、順序制約取得部１００は、命令ａの後に命令ｂから命令ｅの何れかを実行するべき順序の制約と、命令ｂ及び命令ｃの後に命令ｆを実行するべき順序の制約と、命令ｄ及び命令ｅの後に命令ｇを実行するべき順序の制約と、命令ｆ及び命令ｇの後に命令ｈを実行するべき順序の制約とを含む順序制約情報を取得し、順序制約グラフ格納部１０５に格納する。
【００２３】
図４は、順序決定部１１０により追加された順序制約の一例を示す。順序決定部１１０は、図３に示した順序制約グラフにおいて、後続する複数の後続ノードを有する先行ノード、例えば、ノードａを検出する。そして、順序決定部１１０は、ノードａに後続する複数の後続ノード、例えば、ノードｂからノードｅの中から、ノードａとして表された命令において確保されたレジスタを再利用する命令を示すノードｂを選択する。順序決定部１１０は、ノードｂを除外した複数の後続ノード、即ち、ノードｃからノードｅのそれぞれから、ノードｂに至る有向エッジを追加する。本図において、順序決定部１１０により追加された順序制約の一例を点線の矢印で示した。
【００２４】
図５は、順序決定部１１０により解析された必要レジスタ数の一例を示す。順序決定部１１０は、図４に示した順序制約グラフに基づいて、対象プログラム中の各命令において、当該命令が確保又は解放するレジスタの数を算出し、順序制約グラフの各ノードに対応付けて順序制約グラフ格納部１０５に格納する。本図は、各ノードに対応付けて、確保するレジスタの数を正の数で、解放するレジスタの数を負の数でそれぞれ示す。
【００２５】
例えば、命令ａは、命令ａの結果を格納するべく新たにレジスタを１つ確保する確保命令である。命令ｃからｅのそれぞれは、当該命令の結果を格納するべく、命令ａにおいて確保されたレジスタとは別に、更に、レジスタを確保する確保命令である。なお、命令ｂは、命令ａで確保されたレジスタの値を用いる最後の命令であり、かつ当該レジスタを再利用するので、新たにレジスタを確保しない。
【００２６】
命令ｆは、命令ｂ及び命令ｃの結果を用いた処理を行い、命令ｂ及び命令ｃの何れかの結果を格納していたレジスタに処理結果を格納する。従って、命令ｆはレジスタを１つ解放する解放命令である。同様に、命令ｇは、命令ｄ及び命令ｅの結果を用いた処理を行い、命令ｄ及び命令ｅの何れかの結果を格納していたレジスタに処理結果を格納する。従って、命令ｇはレジスタを１つ解放する解放命令である。命令ｈは、命令ｆ及び命令ｇの結果を用いた処理を行い、対象プログラムを終了させる。従って、命令ｈは、レジスタを２つ解放する解放命令である。
【００２７】
図６（ａ）は、順序決定再処理部１４０により追加された順序制約の一例を示す。図６（ｂ）は、レジスタを確保する確保命令及びレジスタを解放する解放命令の集合を示す。本図において、順序決定部１１０が、図４に示した順序制約グラフに基づいて、命令ａ、命令ｃ、命令ｄ、及び命令ｅをこの順に順次実行する実行順序を決定する場合について説明する。レジスタ数解析部１２０は、各命令の実行順序が決定される毎に、図５に示した順序制約グラフに基づいて、必要レジスタ数を解析する。例えば、レジスタ数解析部１２０は、命令ａ、命令ｃ、及び命令ｄのそれぞれの実行順序が決定される毎に、必要レジスタ数を、１、２、及び３と解析する。そして、レジスタ数解析部１２０は、命令ｅの実行順序が決定された場合に、必要レジスタ数を４と解析し、予め定められた規定レジスタ数である３を超えると判断する。
【００２８】
命令検出部１３０は、解放命令の集合ＫＩＬＬの中から、レジスタを解放する解放命令かつ順序未決定命令であり、本発明に係る他方の命令の一例として、命令ｇを検出し、確保命令の集合ＧＥＮの中から、レジスタを確保する確保命令かつ順序既決定命令であり、本発明に係る一方の命令の一例として、命令ｃを検出する。更に、命令検出部１３０は、図４に示した順序制約グラフにおいて、命令ｃから命令ｇに到達不能であることを検出する。なお、命令ｃから命令ｇに到達不能であるとは、命令ｃから、有向エッジの矢印に沿って各ノードを経由するいかなる経路においても、命令ｇに達することのできない状態をいう。
【００２９】
続いて、順序決定再処理部１４０は、ノードｇからノードｃへの有向エッジを生成することにより、命令ｇの次に命令ｃを実行するべきことを示す順序の制約を、順序制約情報に追加する。本図において、順序決定再処理部１４０により追加される有向エッジを、太線の矢印で示す。また、新たに追加する順序制約の集合であるＳＥＱを示す。そして、順序決定再処理部１４０は、順序既決定命令である命令ｃを、実行順序が決定されていない状態に変更し、順序決定部１１０による実行順序の決定を継続させる。
【００３０】
以上の処理に代えて、命令検出部１３０は、レジスタを新たに確保する順序既決定命令より先に実行されるべき命令を、一方の命令として検出してもよい。即ち、命令検出部１３０は、より後に実行される命令の実行順序を決定されていない状態に変更することにより、必要レジスタ数を減らすことのできる命令を、一方の命令として検出してもよい。
【００３１】
なお、順序未決定命令及び順序既決定命令の組合せが複数検出された場合には、命令検出部１３０は、対象プログラムの開始点である命令ａから順序未決定命令に至る順序の制約の深さと、順序既決定命令から対象プログラムの終了点である命令ｈに至る順序の制約の深さとの合計が最小となる組合せを選択し、選択した当該組合せにおける順序未決定命令及び順序既決定命令の間に有向エッジを追加する。ここで、順序の制約の深さとは、例えば、順序の制約の始点から終点に至るまでに経由するノードの数である。具体的には、ノードａからノードｇに至る制約は、ノードｄを経由するので、順序の制約の深さは１である。また、命令検出部１３０は、経由するノードにおける処理の種類に応じて異なる制約の深さを用いてもよい。これに代えて、順序の制約の深さとは、順序の制約の始点から終点に至るまでに経由する有向エッジの数であってもよい。
【００３２】
また、順序決定再処理部１４０は、命令検出部１３０により検出された複数の組合せのそれぞれについて、当該組合せにおける順序既決定命令を表すノードから順序未決定命令を表すノードへの有向エッジを生成してもよい。この場合、順序決定再処理部１４０は、追加する複数の有向エッジにより順序制約グラフ内に循環が構成されないように、追加するべき有向エッジを選択してもよい。更に、順序決定再処理部１４０は、追加する複数の有向エッジが互いに冗長とならないように、追加するべき有向エッジを選択してもよい。また、これに代えて、命令検出部１３０が、追加することのできる命令の組合せのみを選択して検出してもよい。
【００３３】
このように、コンパイラ装置１０は、命令の実行順序を決定する過程で必要レジスタ数が既定数を超えた場合に、一旦決定した実行順序を取り消し、実行順序の決定を再処理する。この場合、コンパイラ装置１０は、取得した順序制約情報を保持しつつ、新たな順序制約を追加することにより、必要レジスタ数を減らす。これにより、コンパイラ装置１０は、実行順序の決定による最適化の効果を生かしつつ、必要レジスタ数を減らすことができるので、コンパイル対象の対象プログラムを高速に動作させることができる。また、コンパイラ装置１０は、順序制約を追加するために必要な処理を、実行順序を決定する処理と共に行うことにより、コンパイル処理に要する時間を短縮することができる。
【００３４】
図７（ａ）は、第１の他の例において命令の実行順序が決定される例を示す。本例におけるコンパイラ装置は、図４に示した順序制約グラフに基づき、同一のレジスタを用いることのできる命令の集合を検出する。例えば、本例のコンパイラ装置は、命令ａと、命令ｂと、命令ｆと、これらの命令による処理結果を命令ｈに与える処理との集合を、同一のレジスタを用いることのできる命令の集合であるＬ１として検出する。同様に、コンパイラ装置は、命令ｃと、命令ｃによる処理結果を命令ｆに与える処理との集合を、同一のレジスタを用いることのできる命令の集合であるＬ２として検出する。また、コンパイラ装置は、命令ｅと、命令ｇと、これらの命令による処理結果を命令ｈに与える処理との集合を、同一のレジスタを用いることのできる命令の集合であるＬ３として検出する。また、コンパイラ装置は、命令ｄと、命令ｄによる処理結果を命令ｇに与える処理との集合を、同一のレジスタを用いることのできる命令の集合であるＬ４として検出する。
【００３５】
図７（ｂ）は、第１の他の例において、命令の複数の集合が、レジスタを共有することができるか否かを示すグラフを示す。コンパイラ装置１０は、命令の集合をノードとして表し、レジスタを共有することのできない関係をエッジで表した干渉グラフを生成する。例えば、Ｌ１中の命令列は、Ｌ２、Ｌ３、及びＬ４の何れにおいて用いられるレジスタをも、用いることができない。また、Ｌ２の命令列は、Ｌ４において用いられるレジスタを用いることができるものの、Ｌ３において用いられるレジスタを用いることができない。また、Ｌ３の命令列は、Ｌ４において用いられるレジスタを用いることができない。
【００３６】
コンパイラ装置は、本図で示したグラフに対して、互いに接続されたノードに同一の彩色を行うことなく、グラフ全体を最小種類の色で彩色するグラフ彩色処理を行う。この結果、コンパイラ装置は、Ｌ２及びＬ４に同一のレジスタを用いさせることにより、対象プログラム全体で用いられるレジスタの総数を３とすることができる旨を検出する。例えば、コンパイラ装置は、Ｌ２中の全ての命令の実行順序を決定した後に、Ｌ４中の命令の実行順序の決定を開始するか、又は、Ｌ４中の全ての命令の実行順序を決定した後に、Ｌ２中の命令の実行順序の決定を開始することにより、Ｌ２及びＬ４に同一のレジスタを用いさせることができる。
【００３７】
しかしながら、本図に示した情報を用いてもなお、コンパイラ装置は、以下に示すように、規定レジスタ数である３を超えたレジスタ数を必要としてしまう場合がある。一例として、コンパイラ装置が、非特許文献１に示した技術により実行順序を決定する場合について説明する。コンパイラ装置は、図７（ａ）に示した順序制約グラフに基づき、命令ｃ及び命令ｅをこの順で実行させるように実行順序を決定する。続いて、コンパイラ装置は、命令ｄの実行順序の決定を試みるが、本図で示したグラフ彩色処理の結果に基づき、命令ｃの値を用いる処理である命令ｆの実行順序が決定していないので、命令ｄの実行順序を決定することができない。更に、コンパイラ装置は、命令ｂに先行する全ての命令の実行順序が決定していないので、命令ｂの実行順序を決定することもできない。即ち、コンパイラ装置は、必要レジスタ数を規定レジスタ数以下に保持したまま、対象プログラム中の命令の実行順序を決定することができない。
【００３８】
これに対し、本実施形態におけるコンパイラ装置１０は、順序既決定命令を、必要に応じて実行順序が決定されていない状態に変更することにより、必要レジスタ数を規定レジスタ数以下に保持したまま、対象プログラム中の命令の実行順序を決定することができる。
【００３９】
図８は、本実施形態に係るコンパイラ装置１０のハードウェア構成の一例を示す。実施形態又は変形例に係るコンパイラ装置１０は、ホストコントローラ１０８２により相互に接続されるＣＰＵ１０００、ＲＡＭ１０２０、グラフィックコントローラ１０７５、及び表示装置１０８０を有するＣＰＵ周辺部と、入出力コントローラ１０８４によりホストコントローラ１０８２に接続される通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を有する入出力部と、入出力コントローラ１０８４に接続されるＲＯＭ１０１０、フレキシブルディスクドライブ１０５０、及び入出力チップ１０７０を有するレガシー入出力部とを備える。
【００４０】
ホストコントローラ１０８２は、ＲＡＭ１０２０と、高い転送レートでＲＡＭ１０２０をアクセスするＣＰＵ１０００及びグラフィックコントローラ１０７５とを接続する。ＣＰＵ１０００は、ＲＯＭ１０１０及びＲＡＭ１０２０に格納されたコンパイラプログラムに基づいて動作し、各部の制御を行う。グラフィックコントローラ１０７５は、ＣＰＵ１０００等がＲＡＭ１０２０内に設けたフレームバッファ上に生成する画像データを取得し、表示装置１０８０上に表示させる。これに代えて、グラフィックコントローラ１０７５は、ＣＰＵ１０００等が生成する画像データを格納するフレームバッファを、内部に含んでもよい。
【００４１】
入出力コントローラ１０８４は、ホストコントローラ１０８２と、比較的高速な入出力装置である通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を接続する。通信インターフェイス１０３０は、ネットワークを介して他の装置と通信する。ハードディスクドライブ１０４０は、コンパイラ装置１０が使用するコンパイラプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ１０６０は、ＣＤ−ＲＯＭ１０９５からコンパイラプログラム又はデータを読み取り、ＲＡＭ１０２０を介して入出力チップ１０７０に提供する。
【００４２】
また、入出力コントローラ１０８４には、ＲＯＭ１０１０と、フレキシブルディスクドライブ１０５０や入出力チップ１０７０等の比較的低速な入出力装置とが接続される。ＲＯＭ１０１０は、コンパイラ装置１０の起動時にＣＰＵ１０００が実行するブートプログラムや、コンパイラ装置１０のハードウェアに依存するプログラム等を格納する。フレキシブルディスクドライブ１０５０は、フレキシブルディスク１０９０からコンパイラプログラム又はデータを読み取り、ＲＡＭ１０２０を介して入出力チップ１０７０に提供する。入出力チップ１０７０は、フレキシブルディスク１０９０や、例えばパラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各種の入出力装置を接続する。
【００４３】
コンパイラ装置１０に提供されるコンパイラプログラムは、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。コンパイラプログラムは、記録媒体から読み出され、入出力チップ１０７０を介してコンパイラ装置１０にインストールされ、コンパイラ装置１０において実行される。
【００４４】
コンパイラ装置１０にインストールされて実行されるコンパイラプログラムは、順序制約情報取得モジュールと、順序決定モジュールと、レジスタ数解析モジュールと、命令検出モジュールと、順序決定再処理モジュールとを含む。各モジュールがコンパイラ装置１０に働きかけて行わせる動作は、図１から図７において説明したコンパイラ装置１０における、対応する部材の動作と同一であるから、説明を省略する。
【００４５】
以上に示したプログラム又はモジュールは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してコンパイラプログラムをコンパイラ装置１０に提供してもよい。
【００４６】
以上、本発明を実施形態を用いて説明したが、本発明の技術的範囲は上記実施形態に記載の範囲には限定されない。上記実施形態に、多様な変更または改良を加えることができる。そのような変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【００４７】
以上に示した実施形態によると、以下の各項目に示すコンパイラ装置、コンパイラプログラム、記録媒体、及びコンパイル方法を実現できる。
【００４８】
（項目１）  コンパイル対象のプログラムである対象プログラムにおいて、命令が実行される順序を変更することにより前記対象プログラムを最適化するコンパイラ装置であって、前記対象プログラムの複数の命令間に定められた、複数の命令が実行されるべき順序の制約を示す順序制約情報を取得する順序制約情報取得部と、前記複数の命令のそれぞれが実行される実行順序を、前記順序制約情報に基づいて順次決定する順序決定部と、前記複数の命令のうち、前記実行順序が決定された命令を実行した場合に必要となるレジスタの数である必要レジスタ数を解析するレジスタ数解析部と、２つの命令の組合せであって、一方の命令が前記順序決定部により前記実行順序が既に決定されている順序既決定命令であり、他方の命令が前記順序決定部により前記実行順序が未だ決定されていない順序未決定命令であり、かつ前記一方の命令が前記他方の命令より先に実行されるべき順序の制約が前記順序制約情報に含まれない組合せを検出する命令検出部と、前記必要レジスタ数が予め定められた数を超える場合に、前記一方の命令を前記実行順序が決定されていない状態に変更し、前記他方の命令の次に前記一方の命令が実行されるべく前記順序決定部により実行順序を決定させる順序決定再処理部とを備えるコンパイラ装置。
【００４９】
（項目２）  前記命令検出部は、前記他方の命令として、レジスタを解放する解放命令を検出し、前記一方の命令として、レジスタを新たに確保する確保命令を検出する項目１記載のコンパイラ装置。
（項目３）  前記命令検出部は、前記他方の命令として、レジスタを解放する解放命令を検出し、前記一方の命令として、レジスタを新たに確保する順序既決定命令より前に実行されるべき命令を検出し、前記順序決定再処理部は、前記順序制約情報において前記順序既決定命令より後に実行されるべき全ての命令を、前記実行順序が決定されていない状態に更に変更する項目１記載のコンパイラ装置。
（項目４）  前記順序決定再処理部は、前記一方の命令及び前記他方の命令の組合せが前記命令検出部により複数検出された場合に、複数の前記組合せのうち、対象プログラムの開始点から前記他方の命令に至る順序の制約の深さと、前記一方の命令から対象プログラムの終了点に至る順序の制約の深さとの合計が最小となる組合せを選択し、選択した当該組合せに含まれる他方の命令及び一方の命令を用いて、実行順序を前記順序決定部により決定させる項目１記載のコンパイラ装置。
【００５０】
（項目５）  前記順序決定再処理部は、前記必要レジスタ数が予め定められた数を超える場合に、前記順序未決定命令の次に前記順序既決定命令を実行すべきことを示す順序の制約を、前記順序制約情報に追加することにより、前記順序未決定命令の次に前記順序既決定命令が実行される実行順序を、前記順序決定部により決定させる項目１記載のコンパイラ装置。
（項目６）  前記順序制約情報取得部は、前記対象プログラムの各命令をノードで表し、複数の命令が実行されるべき順序の制約を有向エッジで表した順序制約グラフを、前記順序制約情報として取得し、前記順序決定部は、前記順序制約グラフに基づいて、有向エッジの始点のノードとして表された命令を、当該有向エッジの終点のノードとして表された命令より先に実行する前記実行順序を決定し、前記命令検出部は、２つの命令の組合せであって、順序制約グラフにおいて、一方の命令を表すノードから他方の命令を表すノードに到達不能な命令の組合せを検出することにより、一方の命令が他方の命令より先に実行されるべき順序の制約が順序制約情報に含まれない組合せであることを検出し、前記順序決定再処理部は、前記順序未決定命令を示すノードから、前記他方の命令を示すノードへの有向エッジを生成することにより、前記一方の命令の次に前記他方の命令を実行すべきことを示す順序の制約を、前記順序制約情報に追加する項目５記載のコンパイラ装置。
【００５１】
（項目７）  コンパイル対象のプログラムである対象プログラムにおいて、命令が実行される順序を変更することにより前記対象プログラムを最適化するコンパイラ装置としてコンピュータを機能させるコンパイラプログラムであって、前記コンピュータを、前記対象プログラムの複数の命令間に定められた、複数の命令が実行されるべき順序の制約を示す順序制約情報を取得する順序制約情報取得部と、前記複数の命令のそれぞれが実行される実行順序を、前記順序制約情報に基づいて順次決定する順序決定部と、前記複数の命令のうち、前記実行順序が決定された命令を実行した場合に必要となるレジスタの数である必要レジスタ数を解析するレジスタ数解析部と、２つの命令の組合せであって、一方の命令が前記順序決定部により前記実行順序が既に決定されている順序既決定命令であり、他方の命令が前記順序決定部により前記実行順序が未だ決定されていない順序未決定命令であり、かつ前記一方の命令が前記他方の命令より先に実行されるべき順序の制約が前記順序制約情報に含まれない組合せを検出する命令検出部と、前記必要レジスタ数が予め定められた数を超える場合に、前記一方の命令を前記実行順序が決定されていない状態に変更し、前記他方の命令の次に前記一方の命令が実行されるべく前記順序決定部により実行順序を決定させる順序決定再処理部として機能させるコンパイラプログラム。
（項目８）  前記命令検出部は、前記他方の命令として、レジスタを解放する解放命令を検出し、前記一方の命令として、レジスタを新たに確保する確保命令を検出する項目７記載のコンパイラプログラム。
【００５２】
（項目９）  前記順序決定再処理部は、前記必要レジスタ数が予め定められた数を超える場合に、前記他方の命令の次に前記一方の命令を実行すべきことを示す順序の制約を、前記順序制約情報に追加することにより、前記他方の命令の次に前記一方の命令が実行される実行順序を、前記順序決定部により決定させる項目７記載のコンパイラプログラム。
（項目１０）  項目７から項目９の何れかに記載のコンパイラプログラムを記録した記録媒体。
（項目１１）  コンピュータにより、コンパイル対象のプログラムである対象プログラムにおいて、命令が実行される順序を変更することにより前記対象プログラムを最適化するコンパイル方法であって、前記対象プログラムの複数の命令間に定められた、複数の命令が実行されるべき順序の制約を示す順序制約情報を取得する順序制約情報取得段階と、前記複数の命令のそれぞれが実行される実行順序を、前記順序制約情報に基づいて順次決定する順序決定段階と、前記複数の命令のうち、前記実行順序が決定された命令を実行した場合に必要となるレジスタの数である必要レジスタ数を解析するレジスタ数解析段階と、２つの命令の組合せであって、一方の命令が前記順序決定部により前記実行順序が既に決定されている順序既決定命令であり、他方の命令が前記順序決定部により前記実行順序が未だ決定されていない順序未決定命令であり、かつ前記一方の命令が前記他方の命令より先に実行されるべき順序の制約が前記順序制約情報に含まれない組合せを検出する命令検出段階と、前記必要レジスタ数が予め定められた数を超える場合に、前記一方の命令を前記実行順序が決定されていない状態に変更し、前記他方の命令の次に前記一方の命令が実行されるべく前記順序決定部により実行順序を決定させる順序決定再処理段階とを備えるコンパイル方法。
【００５３】
【発明の効果】
上記説明から明らかなように、本発明によればプログラムで用いられるレジスタの数を減らすことができる。
【図面の簡単な説明】
【図１】図１は、コンパイラ装置１０の機能ブロック図を示す。
【図２】図２は、コンパイラ装置１０のフローチャートを示す。
【図３】図３は、順序制約取得部１００により順序制約グラフ格納部１０５に格納される順序制約グラフの一例を示す。
【図４】図４は、順序決定部１１０により追加された順序制約の一例を示す。
【図５】図５は、順序決定部１１０により解析された必要レジスタ数の一例を示す。
【図６】図６（ａ）は、順序決定再処理部１４０により追加された順序制約の一例を示す。
図６（ｂ）は、レジスタを確保する確保命令及びレジスタを解放する解放命令の集合を示す。
【図７】図７（ａ）は、第１の他の例において命令の実行順序が決定される例を示す。
図７（ｂ）は、第１の他の例において、命令の複数の集合が、レジスタを共有することができるか否かを示すグラフを示す。
【図８】図８は、本実施形態に係るコンパイラ装置１０のハードウェア構成の一例を示す。
【符号の説明】
１０  コンパイラ装置
１００  順序制約取得部
１０５  順序制約グラフ格納部
１１０  順序決定部
１２０  レジスタ数解析部
１３０  命令検出部
１４０  順序決定再処理部
【図１】
2004280744.tif 000003
【図２】
2004280744.tif 000004
【図３】
2004280744.tif 000005
【図４】
2004280744.tif 000006
【図５】
2004280744.tif 000007
【図６】
2004280744.tif 000008
【図７】
2004280744.tif 000009
【図８】
2004280744.tif 000010