(57)【要約】【課題】  関数呼出しを行う割込み命令の適用箇所を、再帰関数以降で呼出される関数と割込み関数以降で呼出される関数にも広げて、更なるコードサイズの縮小に寄与するコンパイル技術を提供する。【解決手段】  最適な適用箇所を見つけるために、割込みを考慮したコールグラフ、即ち、割込み可能性のある全てのノードから割込み関数に対応するノードへ割込みを表すエッジが繋がれ、さらに割込み優先順位毎にノードを分離したグラフを用いる。最適化を適用する上で守らなければならない制約は、そのコールグラフのルートノードからリーフに至るまでの全ての経路において、最適化を適用するノードを通る回数がレジスタバンク数を超えないことである。この制約を満たす最適化対象の関数の組み合わせの中で、最適化の効果を最大にするものを求める。この組み合わせを求めるための手段としては、線形計画法を用いる。【選択図】図４
2010250721.tif 000002
【特許請求の範囲】
【請求項１】
割込みに応答してレジスタの情報をレジスタバンクへ退避し割込み終了に応答してレジスタバンクの情報をレジスタに復帰する割り込み関係命令を命令セットに有するマイクロプロセッサ向けのオブジェクトコードを生成するコンパイル方法であって、コンピュータ装置が夫々実行する第１処理、第２処理及び第３処理を含み、
前記第1処理は、ソースプログラムの記述に基づいて関数の呼び出し関係を有向グラフで表現したコールグラフを生成する処理であり、
前記第２処理は、前記コールグラフからループを取り除く処理であり、
前記第３処理は、ループが取り除かれたコールグラフにおいて取り除かれたループを構成したノードの前及び後の関数に対して、退避可能なレジスタバンクの数の範囲内で、前記割込み関係命令を用いたコードを生成する処理である、コンパイル方法。
【請求項２】
割込みに応答してレジスタの情報をレジスタバンクへ退避し割込み終了に応答してレジスタバンクの情報をレジスタに復帰する割り込み関係命令を命令セットに有するマイクロプロセッサ向けのオブジェクトコードを生成するコンパイル方法であって、コンピュータ装置が夫々実行する第１処理、第２処理、第３処理、第４処理及び第５処理を含み、
前記第1処理は、ソースプログラムの記述に基づいて関数の呼び出し関係を有向グラフで表現したコールグラフを生成する処理であり、
前記第２処理は、前記コールグラフからループを取り除く処理であり、
前記第３処理は、ループが取り除かれたコールグラフに、割り込み可能性のあるノードから割り込み関数で指定されるノードに割り込みを表すエッジを繋ぐ処理であり、
前記第４処理は、割り込みを表すエッジが繋がれたコールグラフのルートからリーフに至るまでの全経路において、退避可能なレジスタバンクの数の範囲内で前記割込み関係命令を用いることによって削減されるコード量を最大とする関数の組合せを求める処理であり、
前記第５処理は、求まった組合せの関数に対して前記割込み関係命令を用いたコードを生成する処理である、コンパイル方法。
【請求項３】
前記第４処理は、割込みによって呼出しを行うか否かを変数とし、関数の呼出しを割込み経由の呼出しに変更した際のコード量削減効果を求め、その効果と変数の積の総和の式を作成して目的関数とするステップと、呼出し回数と変数の積の総和の式を作成して制約式とするステップと、制約式と目的関数を線形計画法のソルバに入力して、前記ソルバの出力として前記削減されるコード量を最大とする関数の組合せを得るステップと、を含む請求項２記載のコンパイル方法。
【請求項４】
前記第５処理は、前記ソルバの出力に応じて関数の呼出しを割込み経由の呼出しに変更するステップを含む、請求項３記載のコンパイル方法。
【請求項５】
割込みに応答してレジスタの情報をレジスタバンクへ退避し割込み終了に応答してレジスタバンクの情報をレジスタに復帰する割込み関係命令を命令セットに有するマイクロプロセッサ向けのオブジェクトコードを生成するコンパイル方法であって、コンピュータ装置が夫々実行する、
第１のコールグラフに基づいて第２のコールグラフを生成する第１処理と、
生成された前記第２のコールグラフから制約条件を生成する第２処理と、
関数呼出しに割込み関係命令を用いる最適化を個々の関数に適用した場合に得られるコード量削減効果を求める第３処理と、
前記第３処理で求めた効果から目的関数を生成する第４処理と、
前記制約条件と目的関数をソルバに入力し、出力として最適化対象の関数の組合せを得る第５処理と、を含み、
前記第２のコールグラフは、関数の呼出し関係が有向グラフで表現されると共に、割込み可能性のあるノードから割込み関数に対応するノードへ割込みを表すエッジが繋がれ、さらに割込み優先順位毎にノードが分離されたグラフであり、
前記制約条件は、前記第２のコールグラフのルートノードからリーフに至るまでの経路において、最適化を適用するノードを通る回数がレジスタバンク数を超えないことであり、
前記目的関数は、関数に対応する変数と、その関数に前記最適化を適用した場合に得られる効果との積の総和を示すものである、コンパイル方法。
【請求項６】
前記第１処理は、第１のコールグラフを構築する処理と、前記第１のコールグラフからループを取り除く処理と、ループが取り除かれたコールグラフに割込みによる呼出し関係を反映させる処理であり、
前記第１のコールグラフを構築する処理は、ソースプログラムを走査して、プログラム中に存在する関数を見つけ、関数に対応したノードを作成し、ノードの構築が終わったら、次に関数毎に関数内に存在する命令を走査し、呼出している関数を求め、呼出し元の関数に対応するノードから呼出し先の関数に対応するノードへエッジを張る処理であり、
第１のコールグラフからループを取り除く処理は、前記第１のコールグラフを走査し、ループが見つかったら、ノードを１つ新規生成し、次に、ループ上のノードを、新規生成したノードで置き換える処理であり、
ループが取り除かれたコールグラフに割込みによる呼出し関係を反映させる処理は、ソースプログラムを走査し、割込み関数を見つけ、見つかった割込み関数へノードからエッジを張り、割込みを表すエッジを張り終わったら、割込み優先順位に応じてノードを分離したコールグラフを作成する処理である、請求項５記載のコンパイル方法。
【請求項７】
前記第２処理は、前記第２のコールグラフにあるノードのうち、ループを置き換えたノード以外のノードに対応する関数について、個々の関数に対応する変数を作成し、変数の値が０のとき関数は通常の呼出し命令によって呼出され、１のとき割込みによって呼出されるものとし、
割込み関数については、常に割込みによって実行されるので、割込み関数に対応する変数の値を1とする等式を作成して制約条件に追加し、
前記第２のコールグラフのルートからリーフに至る経路について、関数が割込み関数でなく且つ関数に対応する変数の値が１であれば、その関数を最適化の適用対象とするようにして、個々の経路の関数に対応する変数の総和がレジスタバンク数を下回ることを示す不等式を作成する処理である、請求項６記載のコンパイル方法。
【請求項８】
前記第３処理は、ソースプログラムを走査して、個々の関数毎に、関数中にあるレジスタの内容を退避回復するコードのうち、最適化によって除去可能なもの量と、関数の呼出し元の命令を、関数呼出しの命令から割込み関係命令に差替えることによって変化する量を求め、その和をコード量削減効果とする処理である、請求項７記載のコンパイル方法。
【請求項９】
前記第４処理は、関数に対応する変数と、その関数に最適化を適用した場合に得られる前記コード量削減効果との積の総和を示す関数を生成する処理である、請求項８記載のコンパイル方法。
【請求項１０】
第５処理は、制約条件と目的関数を線形計画法のソルバに入力して解を得る処理である、請求項９記載のコンパイル方法。
【請求項１１】
割込みに応答してレジスタの情報をレジスタバンクへ退避し割込み終了に応答してレジスタバンクの情報をレジスタに復帰する割込み関係命令を命令セットに有するマイクロプロセッサ向けのオブジェクトコードを生成するコンパイルプログラムであって、コンピュータ装置が実行することにより、
ソースプログラムの記述に基づいて関数の呼び出し関係を有向グラフで表現したコールグラフを生成する第１処理と、
前記コールグラフからループを取り除く第２処理と、
ループが取り除かれたコールグラフにおいて取り除かれたループを構成したノードの前及び後の関数に対して、退避可能なレジスタバンクの数の範囲内で、前記割込み関係命令を用いたコードを生成する第３処理とを行う、コンパイルプログラム。
【請求項１２】
割込みに応答してレジスタの情報をレジスタバンクへ退避し割込み終了に応答してレジスタバンクの情報をレジスタに復帰する割り込み関係命令を命令セットに有するマイクロプロセッサ向けのオブジェクトコードを生成するコンパイルプログラムであって、コンピュータ装置が実行することにより、
ソースプログラムの記述に基づいて関数の呼び出し関係を有向グラフで表現したコールグラフを生成する第１処理と、
前記コールグラフからループを取り除く第２処理と、
ループが取り除かれたコールグラフに、割り込み可能性のあるノードから割り込み関数で指定されるノードに割り込みを表すエッジを繋ぐ第３処理と、
割り込みを表すエッジが繋がれたコールグラフのルートからリーフに至るまでの全経路において、退避可能なレジスタバンクの数の範囲内で前記割込み関係命令を用いることによって削減されるコード量を最大とする関数の組合せを求める第４処理と、
求まった組合せの関数に対して前記割込み関係命令を用いたコードを生成する第５処理とを行なう、コンパイルプログラム。
【請求項１３】
前記第４処理は、割込みによって呼出しを行うか否かを変数とし、関数の呼出しを割込み経由の呼出しに変更した際のコード量削減効果を求め、その効果と変数の積の総和の式を作成して目的関数とするステップと、呼出し回数と変数の積の総和の式を作成して制約式とするステップと、制約式と目的関数を線形計画法のソルバに入力して、前記ソルバの出力として前記削減されるコード量を最大とする関数の組合せを得るステップと、を含む請求項１２記載のコンパイルプログラム。
【請求項１４】
前記第５処理は、前記ソルバの出力に応じて関数の呼出しを割込み経由の呼出しに変更するステップを含む、請求項１３記載のコンパイルプログラム。
【請求項１５】
割込みに応答してレジスタの情報をレジスタバンクへ退避し割込み終了に応答してレジスタバンクの情報をレジスタに復帰する割込み関係命令を命令セットに有するマイクロプロセッサ向けのオブジェクトコードを生成するコンパイルプログラムであって、コンピュータ装置が実行することにより、
第１のコールグラフに基づいて第２のコールグラフを生成する第１処理と、
生成された前記第２のコールグラフから制約条件を生成する第２処理と、
関数呼出しに割込み関係命令を用いる最適化を個々の関数に適用した場合に得られるコード量削減効果を求める第３処理と、
前記第３処理で求めた効果から目的関数を生成する第４処理と、
前記制約条件と目的関数をソルバに入力し、出力として最適化対象の関数の組合せを得る第５処理とを行い、
前記第２のコールグラフは、関数の呼出し関係が有向グラフで表現されると共に、割込み可能性のあるノードから割込み関数に対応するノードへ割込みを表すエッジが繋がれ、さらに割込み優先順位毎にノードが分離されたグラフであり、
前記制約条件は、前記第２のコールグラフのルートノードからリーフに至るまでの経路において、最適化を適用するノードを通る回数がレジスタバンク数を超えないことであり、
前記目的関数は、関数に対応する変数と、その関数に前記最適化を適用した場合に得られる効果との積の総和を示すものである、コンパイルプログラム。
【請求項１６】
前記第１処理は、第１のコールグラフを構築する処理と、前記第１のコールグラフからループを取り除く処理と、ループが取り除かれたコールグラフに割込みによる呼出し関係を反映させる処理であり、
前記第１のコールグラフを構築する処理は、ソースプログラムを走査して、プログラム中に存在する関数を見つけ、関数に対応したノードを作成し、ノードの構築が終わったら、次に関数毎に関数内に存在する命令を走査し、呼出している関数を求め、呼出し元の関数に対応するノードから呼出し先の関数に対応するノードへエッジを張る処理であり、
第１のコールグラフからループを取り除く処理は、前記第１のコールグラフを走査し、ループが見つかったら、ノードを１つ新規生成し、次に、ループ上のノードを、新規生成したノードで置き換える処理であり、
ループが取り除かれたコールグラフに割込みによる呼出し関係を反映させる処理は、ソースプログラムを走査し、割込み関数を見つけ、見つかった割込み関数へノードからエッジを張り、割込みを表すエッジを張り終わったら、割込み優先順位に応じてノードを分離したコールグラフを作成する処理である、請求項１５記載のコンパイルプログラム。
【請求項１７】
前記第２処理は、前記第２のコールグラフにあるノードのうち、ループを置き換えたノード以外のノードに対応する関数について、個々の関数に対応する変数を作成し、変数の値が０のとき関数は通常の呼出し命令によって呼出され、１のとき割込みによって呼出されるものとし、
割込み関数については、常に割込みによって実行されるので、割込み関数に対応する変数の値を1とする等式を作成して制約条件に追加し、
前記第２のコールグラフのルートからリーフに至る経路について、関数が割込み関数でなく且つ関数に対応する変数の値が１であれば、その関数を最適化の適用対象とするようにして、個々の経路の関数に対応する変数の総和がレジスタバンク数を下回ることを示す不等式を作成する処理である、請求項１６記載のコンパイルプログラム。
【請求項１８】
前記第３処理は、ソースプログラムを走査して、個々の関数毎に、関数中にあるレジスタの内容を退避回復するコードのうち、最適化によって除去可能なもの量と、関数の呼出し元の命令を、関数呼出しの命令から割込み関係命令に差替えることによって変化する量を求め、その和をコード量削減効果とする処理である、請求項１７記載のコンパイルプログラム。
【請求項１９】
前記第４処理は、関数に対応する変数と、その関数に最適化を適用した場合に得られる前記コード量削減効果との積の総和を示す関数を生成する処理である、請求項１８記載のコンパイルプログラム。
【請求項２０】
第５処理は、制約条件と目的関数を線形計画法のソルバに入力して解を得る処理である、請求項１９記載のコンパイルプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイル方法及びコンパイルプログラムに関し、特に、マイクロコントローラのためのソースプログラムをコンパイルするコンパイル技術に関する。
【背景技術】
【０００２】
コンパイラが生成するオブジェクトコードはサイズの小さなものが望まれることがあり、特に組み込み機器製造の分野ではコードサイズ削減が重要視される。コードサイズを小さくすることで製造コストを抑えることが出来るからである。
【０００３】
コードサイズ削減に関する技術の一例として、関数の出入り口においてレジスタの値を退避回復するコードの削減に関するものがある。これに関する従来技術として、特許文献１がある。
【０００４】
特許文献１に記載の技術は割込み命令とレジスタバンクを用いてコードサイズの削減を実現する。ここで、レジスタバンクとはレジスタの内容を退避するための記憶領域である。割込みが発生した場合、ＣＰＵは現在の処理を一時中断し、処理中のレジスタの状態を別の場所に退避し、割込み関数を実行し、割込み関数が終わったら割込み前の元の処理を再開するためにレジスタの状態を回復する。特許文献１に記載の技術は割込み発生時にこのレジスタの退避回復をレジスタバンクに対して自動的に行うアーキテクチャ上で実現されるものであり、関数の呼出しを割込み命令によって実現する。
【０００５】
また、特許文献１に記載の技術は、関数呼出しを行う割込み命令の適用箇所を、コードサイズ縮小化に有効な箇所のみとする。すなわち、通常レジスタバンク数は有限であり、レジスタバンク数を超えて多重に割込みが発生するとレジスタバンクが溢れ、溢れたレジスタバンクの内容をメモリに退避するには処理に時間がかかるので、全ての関数呼出しを割込み命令で実現することは望ましくないからである。特許文献１では、コードサイズ縮小のために関数呼出しを割り込み命令を用いて行う最適化の処理において、上記割り込み命令の適用箇所を見つけるため、コールツリーを用いてソースプログラムを解析する。コールツリーとは関数の呼出し関係を木構造で表現したものであり、関数がノードに、呼出しがエッジとなる。特許文献１記載の技術では、ツリーを深さ方向に経路探索し、ノードが再帰関数か否かまたは割込み関数か否かを判定し、真であったらそれ以降の経路に存在する関数を最適化の適用対象から除く。再帰関数でも割込み関数でもない場合は、呼出し深さがレジスタバンク数を超えるか判定し、超えた場合は最適化の適用対象から除く。全ての経路を探索し終えた後で、最適化の適用対象から除かれなかった関数に最適化を適用する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００１−１３４４４７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
特許文献１に記載の技術においては最適化の効果が必ずしも最大にならないということが本発明者によって見出された。その原因は、次に示す２つの点から、最適化対象の関数が必ずしも最適にならないことにある。
【０００８】
第１に、最適化対象の関数の選択にあたって、個々の関数に最適化を適用した際に得られる効果を考慮していない。この最適化はレジスタバンク数の制約から、全関数に適用するのは適当でない。従って適用対象の関数を選択する必要があるが、選択の結果に応じて最適化の効果が変化することに注意する必要がある。変化の原因は、関数毎に最適化で削減可能なコードの量が違うことにある。従って最適化の効果を最大にするためにはこの違いを考慮すべきだが、特許文献１に記載の技術ではこの違いを考慮していないので最適化の効果が小さくなる。
【０００９】
第２に、再帰関数および割込み関数から呼び出される関数を最適化対象の候補から除外している。ここで除外される関数の中にも最適化対象にできるものが含まれている。それらを除外すると最適化対象の選択の幅が狭まり，最適化の効果が小さくなる。
【００１０】
特許文献１に記載の技術が再帰関数および割込み関数から呼び出される関数を最適化対象から除外している理由は、これらの関数は再帰的に不定回数呼出されうるからである。再帰的に不定回数呼ばれる関数に最適化を適用すると、不定の数のレジスタバンクを消費し、レジスタバンクを溢れさせる虞を生ずる。特許文献１に記載の技術のように再帰関数もしくは割込み関数から直接的あるいは間接的に呼ばれる関数全体を最適化の対象から除外することは必ずしも適当ではない。再帰関数から呼出される関数の中にも呼出される回数が不定にならないものも有り、また、割込み関数の中にも再帰的に呼出されないものも有るからである。アーキテクチャによっては割込みに優先順位を付与し、割込みが発生中には優先順位が同等以下の割り込みの発生を抑止するものがある。このようなアーキテクチャでは割込み要求が不定回数連続で発生しても、割込み関数は再帰的に不定回数呼出されることはない。
【００１１】
本発明の目的は、コンパイラが生成するオブジェクトコードのサイズを縮小することにある。
【００１２】
本発明の前記並びにその他の目的と新規な特徴は本明細書の記述及び添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１３】
本願において開示される発明のうち代表的なものの概要を簡単に説明すれば下記の通りである。
【００１４】
すなわち、関数呼出しを行う割込み命令の適用箇所を、再帰関数以降で呼出される関数と割込み関数以降で呼出される関数にも広げる。
【００１５】
より具体的には、ソースプログラムの記述に基づいて関数の呼び出し関係を有向グラフで表現したコールグラフ（第１のコールグラフ）からループを取り除き、取り除かれたループを構成したノードの前及び後の関数に対して、退避可能なレジスタバンクの数の範囲内で、割込み関係命令を用いたコードを生成する。
【００１６】
更に具体的には、前記最適な適用箇所を見つけるために割込みを考慮したコールグラフ（第２のコールグラフ）を用いて解析を行う。割込みを考慮したコールグラフとは、割込み可能性のあるノードから割込み関数に対応するノードへ割込みを表すエッジが繋がれ、さらに割込み優先順位毎にノードを分離したグラフである。最適化を適用する上で守らなければならない制約は、この第２のコールグラフのルートノードからリーフに至るまでの経路において、最適化を適用するノードを通る回数がレジスタバンク数を超えないことである。ここでは、この制約を満たす最適化対象の関数の組み合わせの中で、最適化の効果を最大にするものを求める。この組み合わせを求めるための手段としては、線形計画法を用いる。制約を線形計画法の制約条件、最適化の効果を目的関数として表現し、既存技術である線形計画法の解を求めるプログラムに入力することで、目的とする関数の組み合わせを得る。
【発明の効果】
【００１７】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば下記のとおりである。
【００１８】
すなわち、コンパイラが生成するオブジェクトコードのサイズを縮小することができる。
【図面の簡単な説明】
【００１９】
【図１】図は本発明の実施形態に係るコンパイル方法を実装したコンパイルプログラムとしてのコンパイラが動作するコンピュータ装置としての計算機と前記コンパイラが生成したオブジェクトコードを実行する計算機とを示すブロック図である。
【図２】図２はコンパイラによる処理を例示するフローチャートである。
【図３】図３は図２のステップ２０５の処理に関する比較例を示すフローチャートである。
【図４】図４は図２のステップ２０５の処理例を示すフローチャートである。
【図５】図５は再帰関数と割込みを含むプログラムのコールグラフを例示する説明図である。
【図６】図６はステップ４０２の処理例を示すフローチャートである。
【図７】図７は図５のループを結合して取り除いたコールグラフの説明図である。
【図８】図８はステップ４０３の処理例を示すフローチャートである。
【図９】図９はステップ８０１の処理例を示すフローチャートである。
【図１０】図１０は図７の割込み関係を反映したコールグラフの説明図である。
【図１１】図１１はステップ８０２の処理例を示すフローチャートである。
【図１２】図１２はステップ８０３の処理例を示すフローチャートである。
【図１３】図１３は図１０を割込み優先順位毎にノードを分離したコールグラフの説明図である。
【図１４】図１４はステップ４０４の詳細処理例を示すフローチャートである。
【図１５】図１５は図１３の関数と変数の対応を示す説明図である。
【図１６】図１６はステップ１４０２の処理例を示すフローチャートである。
【図１７】図１７は図１３の目的関数の係数を記入する表のフォーマット例を示す説明図である。
【図１８】図１８は図１７の表が埋まった例を示す説明図である。
【図１９】図１９は図１８の表を元に作成された目的関数の説明図である。
【図２０】図２０はステップ１４０３の処理例を示すフローチャートである。
【図２１】図２１は図１３のひとつの経路における制約式の係数を記入する表のフォーマット例を示す説明図である。
【図２２】図２２は図１３の各経路について係数を埋めた表を示す説明図である。
【図２３】図２３は図１３の経路毎に作成された制約式を例示する説明図である。
【図２４】図２４はステップ１４０４の処理例を示すフローチャートである。
【図２５】図２５は図１９の目的関数と図２３の制約式をソルバに入力して得られる解を示す説明図である。
【図２６】図２６はコンパイラ１０２に入力するＣ言語によって記述されたソースコードの例を示す説明図である。
【図２７】図２７は退避回復するコードの位置２０４（図２参照）で示される退避回復する命令の数の例を示す説明図である。
【図２８】図２８はコンパイラがターゲットとするアーキテクチャの命令毎のサイズを例示した説明図である。
【発明を実施するための形態】
【００２０】
１．実施の形態の概要
先ず、本願において開示される発明の代表的な実施の形態について概要を説明する。代表的な実施の形態についての概要説明で括弧を付して参照する図面中の参照符号はそれが付された構成要素の概念に含まれるものを例示するに過ぎない。
【００２１】
〔１〕本発明の代表的な実施の形態に係るコンパイル方法は、割込みに応答してレジスタの情報をレジスタバンクへ退避し割込み終了に応答してレジスタバンクの情報をレジスタに復帰する割込み関係命令（割込み命令、復帰命令）を命令セットに有するマイクロプロセッサ向けのオブジェクトコードを生成する方法であって、コンピュータ装置が夫々実行する第１処理、第２処理及び第３処理を含む。前記第1処理は、ソースプログラムの記述に基づいて関数の呼び出し関係を有向グラフで表現したコールグラフを生成する処理である。前記第２処理は、前記コールグラフからループを取り除く処理である。前記第３処理は、ループが取り除かれたコールグラフにおいて取り除かれたループを構成したノードの前及び後の関数に対して、退避可能なレジスタバンクの数の範囲内で、前記割込み関係命令を用いたコードを生成する処理である。
【００２２】
〔２〕本発明の代表的な別の実施の形態に係るコンパイル方法は、割込みに応答してレジスタの情報をレジスタバンクへ退避し割込み終了に応答してレジスタバンクの情報をレジスタに復帰する割り込み関係命令を命令セットに有するマイクロプロセッサ向けのオブジェクトコードを生成する方法であって、コンピュータ装置が夫々実行する第１処理、第２処理、第３処理、第４処理及び第５処理を含む。前記第1処理は、ソースプログラムの記述に基づいて関数の呼び出し関係を有向グラフで表現したコールグラフを生成する処理である。前記第２処理は、前記コールグラフからループを取り除く処理である。前記第３処理は、ループが取り除かれたコールグラフに、割り込み可能性のあるノードから割り込み関数で指定されるノードに割り込みを表すエッジを繋ぐ処理である。前記第４処理は、割り込みを表すエッジが繋がれたコールグラフのルートからリーフに至るまでの全経路において、退避可能なレジスタバンクの数の範囲内で前記割込み関係命令を用いることによって削減されるコード量を最大とする関数の組合せを求める処理である。前記第５処理は、求まった組合せの関数に対して前記割込み関係命令を用いたコードを生成する処理である。
【００２３】
〔３〕項２のコンパイル方法において、前記第４処理は、割込みによって呼出しを行うか否かを変数とし、関数の呼出しを割込み経由の呼出しに変更した際のコード量削減効果を求め、その効果と変数の積の総和の式を作成して目的関数とするステップと、呼出し回数と変数の積の総和の式を作成して制約式とするステップと、制約式と目的関数を線形計画法のソルバに入力して、前記ソルバの出力として前記削減されるコード量を最大とする関数の組合せを得るステップと、を含む。
【００２４】
〔４〕項３のコンパイル方法において、前記第５処理は、前記ソルバの出力に応じて関数の呼出しを割込み経由の呼出しに変更するステップを含む。
【００２５】
〔５〕本発明の代表的な更に別の実施の形態に係るコンパイル方法は、割込みに応答してレジスタの情報をレジスタバンクへ退避し割込み終了に応答してレジスタバンクの情報をレジスタに復帰する割込み関係命令を命令セットに有するマイクロプロセッサ向けのオブジェクトコードを生成する方法であって、コンピュータ装置が夫々実行する、第１のコールグラフに基づいて第２のコールグラフを生成する第１処理と、生成された前記第２のコールグラフから制約条件を生成する第２処理と、関数呼出しに割込み関係命令を用いる最適化を個々の関数に適用した場合に得られるコード量削減効果を求める第３処理と、前記第３処理で求めた効果から目的関数を生成する第４処理と、前記制約条件と目的関数をソルバに入力し、出力として最適化対象の関数の組合せを得る第５処理と、を含む。前記第２のコールグラフは、関数の呼出し関係が有向グラフで表現されると共に、割込み可能性のあるノードから割込み関数に対応するノードへ割込みを表すエッジが繋がれ、さらに割込み優先順位毎にノードが分離されたグラフである。前記制約条件は、前記第２のコールグラフのルートノードからリーフに至るまでの経路において、最適化を適用するノードを通る回数がレジスタバンク数を超えないことである。前記目的関数は、関数に対応する変数と、その関数に前記最適化を適用した場合に得られる効果との積の総和を示すものである。
【００２６】
〔６〕項５のコンパイル方法において、前記第１処理は、第１のコールグラフを構築する処理と、前記第１のコールグラフからループを取り除く処理と、ループが取り除かれたコールグラフに割込みによる呼出し関係を反映させる処理である。前記第１のコールグラフを構築する処理は、ソースプログラムを走査して、プログラム中に存在する関数を見つけ、関数に対応したノードを作成し、ノードの構築が終わったら、次に関数毎に関数内に存在する命令を走査し、呼出している関数を求め、呼出し元の関数に対応するノードから呼出し先の関数に対応するノードへエッジを張る処理である。第１のコールグラフからループを取り除く処理は、前記第１のコールグラフを走査し、ループが見つかったら、ノードを１つ新規生成し、次に、ループ上のノードを、新規生成したノードで置き換える処理である。ループが取り除かれたコールグラフに割込みによる呼出し関係を反映させる処理は、ソースプログラムを走査し、割込み関数を見つけ、見つかった割込み関数へノードからエッジを張り、割込みを表すエッジを張り終わったら、割込み優先順位に応じてノードを分離したコールグラフを作成する処理である。
【００２７】
〔７〕項６のコンパイル方法において、前記第２処理は、（ａ）前記第２のコールグラフにあるノードのうち、ループを置き換えたノード以外のノードに対応する関数について、個々の関数に対応する変数を作成し、変数の値が０のとき関数は通常の呼出し命令によって呼出され、１のとき割込みによって呼出されるものとし、（ｂ）割込み関数については、常に割込みによって実行されるので、割込み関数に対応する変数の値を1とする等式を作成して制約条件に追加し、（ｃ）前記第２のコールグラフのルートからリーフに至る経路について、関数が割込み関数でなく且つ関数に対応する変数の値が１であれば、その関数を最適化の適用対象とするようにして、個々の経路の関数に対応する変数の総和がレジスタバンク数を下回ることを示す不等式を作成する処理である。
【００２８】
〔８〕項７のコンパイル方法において、前記第３処理は、ソースプログラムを走査して、個々の関数毎に、関数中にあるレジスタの内容を退避回復するコードのうち、最適化によって除去可能なもの量と、関数の呼出し元の命令を、関数呼出しの命令から割込み関係命令に差替えることによって変化する量を求め、その和をコード量削減効果とする処理である。
【００２９】
〔９〕項８のコンパイル方法において、前記第４処理は、関数に対応する変数と、その関数に最適化を適用した場合に得られる前記コード量削減効果との積の総和を示す関数を生成する処理である。
【００３０】
〔１０〕項９のコンパイル方法において、第５処理は、制約条件と目的関数を線形計画法のソルバに入力して解を得る処理である。
【００３１】
〔１１〕本発明の代表的な実施の形態に係るコンパイルプログラムは、割込みに応答してレジスタの情報をレジスタバンクへ退避し割込み終了に応答してレジスタバンクの情報をレジスタに復帰する割込み関係命令を命令セットに有するマイクロプロセッサ向けのオブジェクトコードを生成するプログラムであって、コンピュータ装置が実行することにより、ソースプログラムの記述に基づいて関数の呼び出し関係を有向グラフで表現したコールグラフを生成する第１処理と、前記コールグラフからループを取り除く第２処理と、ループが取り除かれたコールグラフにおいて取り除かれたループを構成したノードの前及び後の関数に対して、退避可能なレジスタバンクの数の範囲内で、前記割込み関係命令を用いたコードを生成する第３処理とを行う。
【００３２】
〔１２〕本発明の代表的な別の実施の形態に係るコンパイルプログラムは、割込みに応答してレジスタの情報をレジスタバンクへ退避し割込み終了に応答してレジスタバンクの情報をレジスタに復帰する割り込み関係命令を命令セットに有するマイクロプロセッサ向けのオブジェクトコードを生成するプログラムであって、コンピュータ装置が実行することにより、ソースプログラムの記述に基づいて関数の呼び出し関係を有向グラフで表現したコールグラフを生成する第１処理と、前記コールグラフからループを取り除く第２処理と、ループが取り除かれたコールグラフに、割り込み可能性のあるノードから割り込み関数で指定されるノードに割り込みを表すエッジを繋ぐ第３処理と、割り込みを表すエッジが繋がれたコールグラフのルートからリーフに至るまでの全経路において、退避可能なレジスタバンクの数の範囲内で前記割込み関係命令を用いることによって削減されるコード量を最大とする関数の組合せを求める第４処理と、求まった組合せの関数に対して前記割込み関係命令を用いたコードを生成する第５処理とを行なう。
【００３３】
〔１３〕項１２のコンパイルプログラムにおいて、前記第４処理は、割込みによって呼出しを行うか否かを変数とし、関数の呼出しを割込み経由の呼出しに変更した際のコード量削減効果を求め、その効果と変数の積の総和の式を作成して目的関数とするステップと、呼出し回数と変数の積の総和の式を作成して制約式とするステップと、制約式と目的関数を線形計画法のソルバに入力して、前記ソルバの出力として前記削減されるコード量を最大とする関数の組合せを得るステップと、を含む。
【００３４】
〔１４〕項１３のコンパイルプログラムにおいて、前記第５処理は、前記ソルバの出力に応じて関数の呼出しを割込み経由の呼出しに変更するステップを含む。
【００３５】
〔１５〕本発明の代表的な更に別の実施の形態に係るコンパイルプログラムは、割込みに応答してレジスタの情報をレジスタバンクへ退避し割込み終了に応答してレジスタバンクの情報をレジスタに復帰する割込み関係命令を命令セットに有するマイクロプロセッサ向けのオブジェクトコードを生成するプログラムであって、コンピュータ装置が実行することにより、第１のコールグラフに基づいて第２のコールグラフを生成する第１処理と、生成された前記第２のコールグラフから制約条件を生成する第２処理と、関数呼出しに割込み関係命令を用いる最適化を個々の関数に適用した場合に得られるコード量削減効果を求める第３処理と、前記第３処理で求めた効果から目的関数を生成する第４処理と、前記制約条件と目的関数をソルバに入力し、出力として最適化対象の関数の組合せを得る第５処理とを行う。前記第２のコールグラフは、関数の呼出し関係が有向グラフで表現されると共に、割込み可能性のあるノードから割込み関数に対応するノードへ割込みを表すエッジが繋がれ、さらに割込み優先順位毎にノードが分離されたグラフである。前記制約条件は、前記第２のコールグラフのルートノードからリーフに至るまでの経路において、最適化を適用するノードを通る回数がレジスタバンク数を超えないことである。前記目的関数は、関数に対応する変数と、その関数に前記最適化を適用した場合に得られる効果との積の総和を示すものである。
【００３６】
〔１６〕項１５のコンパイルプログラムにおいて、前記第１処理は、第１のコールグラフを構築する処理と、前記第１のコールグラフからループを取り除く処理と、ループが取り除かれたコールグラフに割込みによる呼出し関係を反映させる処理である。前記第１のコールグラフを構築する処理は、ソースプログラムを走査して、プログラム中に存在する関数を見つけ、関数に対応したノードを作成し、ノードの構築が終わったら、次に関数毎に関数内に存在する命令を走査し、呼出している関数を求め、呼出し元の関数に対応するノードから呼出し先の関数に対応するノードへエッジを張る処理である。第１のコールグラフからループを取り除く処理は、前記第１のコールグラフを走査し、ループが見つかったら、ノードを１つ新規生成し、次に、ループ上のノードを、新規生成したノードで置き換える処理である。ループが取り除かれたコールグラフに割込みによる呼出し関係を反映させる処理は、ソースプログラムを走査し、割込み関数を見つけ、見つかった割込み関数へノードからエッジを張り、割込みを表すエッジを張り終わったら、割込み優先順位に応じてノードを分離したコールグラフを作成する処理である。
【００３７】
〔１７〕項１６のコンパイルプログラムにおいて、前記第２処理は、（ａ）前記第２のコールグラフにあるノードのうち、ループを置き換えたノード以外のノードに対応する関数について、個々の関数に対応する変数を作成し、変数の値が０のとき関数は通常の呼出し命令によって呼出され、１のとき割込みによって呼出されるものとし、（ｂ）割込み関数については、常に割込みによって実行されるので、割込み関数に対応する変数の値を1とする等式を作成して制約条件に追加し、（ｃ）前記第２のコールグラフのルートからリーフに至る経路について、関数が割込み関数でなく且つ関数に対応する変数の値が１であれば、その関数を最適化の適用対象とするようにして、個々の経路の関数に対応する変数の総和がレジスタバンク数を下回ることを示す不等式を作成する処理である。
【００３８】
〔１８〕項１７のコンパイルプログラムにおいて、前記第３処理は、ソースプログラムを走査して、個々の関数毎に、関数中にあるレジスタの内容を退避回復するコードのうち、最適化によって除去可能なもの量と、関数の呼出し元の命令を、関数呼出しの命令から割込み関係命令に差替えることによって変化する量を求め、その和をコード量削減効果とする処理である。
【００３９】
〔１９〕項１８のコンパイルプログラムにおいて、前記第４処理は、関数に対応する変数と、その関数に最適化を適用した場合に得られる前記コード量削減効果との積の総和を示す関数を生成する処理である。
【００４０】
〔２０〕項１９のコンパイルプログラムにおいて、第５処理は、制約条件と目的関数を線形計画法のソルバに入力して解を得る処理である。
【００４１】
２．実施の形態の詳細
実施の形態について更に詳述する。
【００４２】
本発明の実施形態を適用する計算機システムの例を図１に示す。図１のシステムは本実施形態に係るコンパイル方法を実装したコンパイルプログラムとしてのコンパイラ１０２を実行するコンピュータ装置としての計算機１０４と、前記コンパイラ１０２が生成したオブジェクトコード１０３を実行する計算機１１０からなる。コンパイラ１０２はソースコード１０１を入力とし、オブジェクトコード１０３を出力する。計算機１１０はＣＰＵ１０５と、オブジェクトコート１０３を格納するための記憶領域１１１と、メインメモリ１０６と、割込み信号をＣＰＵに送る外部機器１１４を持つ。ＣＰＵ１０５は演算器１０７と、レジスタ１０８と、レジスタバンク１０９と、割込み判定器１１３を持つ。レジスタ１０８は内部にステータスレジスタ１１２を持つ。演算器１０７はオブジェクトコード１０３に記述された演算を行う処理装置であり、レジスタ１０８は演算器１０７が使用する値及び、演算結果の値を格納する記憶領域である。ステータスレジスタ１１２は、現在実行中の割込み優先順位が格納される。割込み判定器１１３は、外部機器１１４または演算器１０７から割込み信号が送られると、その割込みの優先順位がステータスレジスタ１１２に記録されている優先順位よりも大きいかを判定する。割込みの優先順位が大きければ、レジスタ１０８の内容をレジスタバンク１０９に退避し、ステータスレジスタ１１２にこの割込みの優先順位を記録し、割込み関数を実行するよう演算器１０７に通知する。割込み関数の実行が終了すると、レジスタバンク１０９からレジスタの内容を復帰し、割込み発生前に行っていた処理に戻る。手続呼出しでは、通常、汎用レジスタ１０８の内容は退避回復するコード（例えばロード命令、ストア命令、またはムーブ命令など）によってメインメモリ１０６に退避される。本実施形態では汎用レジスタ１０８からメインメモリ１０６への退避回復するコードを削減するために、そのための手続呼出しを割込み命令によって実現する。こうすると退避の処理が割込み命令を実行することによって行われるようになるので、退避のためのコードを挿入する必要がなくなる。
【００４３】
本実施形態を実装するコンパイラ１０２の処理フローを図２に例示する。この例は、まずステップ２０１で字句解析及び構文解析及び中間語生成を行う。次にステップ２０２でレジスタ割付を行う。次にステップ２０３では退避回復したコードを挿入し、挿入したコード位置２０４を出力する。ステップ２０５は退避回復するコードの位置２０４を用いてレジスタバンクを用いたコード削減処理を行う。最後にステップ２０６でオブジェクト生成を行い、オブジェクトコード１０３を出力する。
【００４４】
図２６はコンパイラ１０２に入力するＣ言語によって記述されたソースコードの例である。行２６２０と行２６２５は割込み関数を定義する指示文の例であり、関数gを割り込みの番号0番に登録し、関数hを割込みの番号1番に登録している。この図のプログラムは関数aを起点とし、関数aは関数bを呼出し、関数bは関数cを呼出し、関数cは関数dを呼出し、関数dは関数cと関数eと関数fを呼出す。関数gは非同期の割込み関数であり、関数eを呼出す。行２６０８は同期割込み命令を生成する組み込み関数であり、ここでは割込みの番号1番に登録された関数hを同期割込み命令によって呼出す。従って、関数bは関数hを同期割込み経由で呼出す。尚、この例では割込み関数gへの割込みが関数a, b, c, d, e, fで発生する可能性があるとする。図２７は退避回復するコードの位置２０４（図２参照）で示される退避回復する命令の数の例であり、この表の値は図２６のソースコードを入力したときにコンパイラが生成した退避回復命令の数とする。図２８はコンパイラ１０２がターゲットとするアーキテクチャの命令毎のサイズを示した例である。コンパイラはこの情報を予め内部に持っているものとする。
【００４５】
図２のステップ２０５の処理に関する比較例としてここで先ず特許文献１の従来技術による処理例を図３に示す。図３では、レジスタバンクを用いたコード削減処理として、まずコールツリー作成ステップ３０１を行う。コールツリーの作成が終わったらステップ３０２によって再帰関数及び再帰関数から直接的あるいは間接的に呼出される関数を最適化対象から除外する。次にステップ３０３によって割込み関数及び割込み関数から直接的あるいは間接的に呼出される関数を最適化対象から除外する。そして、ステップ３０４によって呼出し深さがレジスタバンク数を超える関数を最適化対象から除外する。ステップ３０４を終えた時点で、最適化対象から除外されていない関数が従来技術の解析で求めた最適化の適用箇所となるので、ステップ３０５によって最適化を適用し、図３のステップ２０５が終了する。要するに、再帰関数及び割込み関数だけでなくそれらから呼ばれる関数も最適化対象外とするものである。
【００４６】
図２のステップ２０５の本実施形態に係る処理例を図４に示す。これは図３のステップ３０１がステップ４０１に、ステップ３０２がステップ４０２に、ステップ３０３がステップ４０３に、ステップ３０４がステップ４０４に置きかわったものである。
【００４７】
ステップ４０１のコールグラフ作成処理にはコールグラフの構築技術を流用すれば良い。コールグラフの構築技術については、例えばRyder, B.G., "Constructing the Call Graph of a Program," Software Engineering, IEEE Transactions on , vol.SE-5, no.3pp. 216- 226, May 1979に記載がある。このような技術により、ソースコードから作成したコールグラフ（第１のコールグラフ）の例を図５に示す。コールグラフとは、コンピュータプログラムによる処理を規定する関数同士の呼び出し関係を表現した有向グラフである。各ノードが手続きすなわち関数を表現し、エッジは手続きの呼び出しを矢印の向きによって示す。循環したグラフ（環）は再帰的な関数呼び出しを示す。ここで、ノードgとノードhには割込み関数に対応することを示す印として“△”を付与した。
【００４８】
ステップ４０１によってコールグラフを作成した後、ステップ４０２によって環（ループ）をなすノードを最適化対象から除く。コールグラフ中の環を見つけ出す技術は、例えばAlfred.V.Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman. ”The Compilers 2nd edition”, pp. 655-671, Addison Wesley, 2006に記載がある。ステップ４０２の処理例を図６に示す。この処理では、まずステップ６０１でコールグラフ中の環の集合を作る。次に判定６０２で環の集合が空か判定し、空でないならステップ６０３へ行き、集合から環をひとつ取り出す。そして、ステップ６０４で新しいノードをコールグラフに追加し、ステップ６０５で取り出した環に繋がっているエッジを追加したノードに繋ぎ替える。ステップ６０６で追加したノードに環を置き換えたことを示す印をつけ、判定６０２へ戻る。判定６０２で集合が空なら終了する。図５で示すコールグラフに対し、ステップ４０２を実行すると図７のコールグラフが得られる。図５のノードc,dの作る環が図７ではひとつのノードcdに置きかわっている。ここでノードcdには環を置き換えたノードであることを示す印“×”が付いている。
【００４９】
ステップ４０３の処理例を図８に示す。ステップ８０１でコールグラフに非同期割込みによって呼出される割込み関数の呼出し関係を反映する。ステップ８０１の処理例を図９に示す。ステップ８０１は、まずステップ９０１でコールグラフのノードの集合を作成する。判定９０２でこのノードの集合が空か判定する。空でなければステップ９０３へ行き、ノードの集合からノードをひとつ取り出す。そして、ステップ９０４で非同期割込み関数の集合を作成する。判定９０５で非同期割込み関数の集合は空か判定し、空でないなら、ステップ９０６へ行き、非同期割込み関数の集合から関数をひとつ取り出す。そしてステップ９０７で取り出したノードから取り出した割込み関数への割込みを表すエッジを張り、判定９０５に戻る。判定９０５で非同期関数の集合が空なら判定９０２へ戻る。判定９０２でノードの集合が空であれば終了する。図７で示すコールグラフに対し、ステップ８０１を実行すると図１０のコールグラフを得る。図１０において破線が割込みを表すエッジである。
【００５０】
図８に戻り、ステップ８０２では割込み命令による割込み関数の呼出し関係をコールグラフに反映する。ステップ８０２の処理例を図１１に示す。ステップ８０２は最初にステップ１１０１でコールグラフのノードの集合を作る。次に判定１１０２でノードの集合が空か判定する。空でなければステップ１１０３へ行き、このノードの集合からノードをひとつ取り出す。そしてステップ１１０４で取り出したノードに対応する関数の命令の集合を作成する。判定１１０５で命令の集合は空か判定し、空でないならステップ１１０６で命令の集合から命令をひとつ取り出す。そして判定１１０７でこの取り出した命令が割込み命令か判定する。割込み命令でないなら判定１１０５へ戻る。割込み命令ならステップ１１０８へ行き、割込み命令に対応する割込み関数に対応するノードに割込みを表すエッジを張り、判定１１０５へ戻る。判定１１０５で命令の集合が空なら判定１１０２へ戻る。判定１１０２でノードの集合が空であれば、終了する。
【００５１】
図８に戻り、ステップ８０３ではコールグラフに割込み優先順位を反映させる。ステップ８０３の処理例を図１２に示す。この処理例は、ステップ８０２で作成したコールグラフを用いて、割込み優先順位毎にノードを分離した新たなコールグラフを作成することによってコールグラフ（第２のコールフラグ）を得る。具体的には、まずステップ１２０１でエッジの集合と割込み優先順位を入れるスタックを用意する。そしてステップ１２０２で空の新しいコールグラフを作る。ステップ１２０３ではステップ８０２で作成したコールグラフの起点を現在のノードとする。ステップ１２０４で現在のノードと現在の割込み優先順位との組を表すノードを、新しいコールグラフに、重複が無ければ追加する。再帰的な探索によって辿ってきたエッジがあれば、そのエッジも重複が無ければ新しいコールグラフに追加する。ステップ１２０５で現在のノードから出ているエッジの集合を作成し判定１２０６でエッジの集合は空か判定する。空でなければステップ１２０９へ行く。空であれば判定１２０７へ行き、スタックが空か判定する。空であればステップ１２１６へ行き、作成した新しいコールグラフを、第２のコールグラフとして出力し、終了する。スタックが空でなければステップ１２０８へ行き、スタックからエッジの集合と割込み優先順位をポップし、現在のエッジの集合と割込み優先順位とする。次にステップ１２０９へ行き、エッジの集合からエッジをひとつ取り出す。次に、判定１２１０で、ステップ１２０９で取り出したエッジが割込みを表すエッジであるかを判定する。この判定はエッジの指す先のノードに対応する関数が割込み関数であるかを調べることで可能である。割込みを表すエッジでなければ、判定１２１３へ行く。割込みを表すエッジであったなら、判定１２１１へ行き、エッジの指す先のノードに対応する割込み関数の割込み優先順位が現在の割込み優先順位よりも高いかを判定する。高くなければ判定１２０６へ戻る。高ければステップ１２１２へ行き、エッジの優先順位を現在の優先順位にし、判定１２１３へ行く。判定１２１３ではエッジの集合は空かを判定し、空ならステップ１２１５へ行く。空でなければステップ１２１４へ行き、現在のエッジの集合と現在の割込み優先順位をスタックにプッシュし、ステップ１２１５へ行く。ステップ１２１５ではエッジを辿り次のノードへ進み、ステップ１２０４へ戻る。図１０のコールグラフに対し、ステップ８０３を実行すると図１３のコールグラフを得る。ノード名に付されたサフィックスは当該ノードにおける割込み優先レベルである。図１０のノードeが図１３ではノードe0とノードe1に分かれている。すなわち、ノードｇ１から呼び出されるノードｅ１と、非同期割込みによってノードｇ１を呼び出すノードｅ０とが区別される。
【００５２】
図４へ戻り、ステップ４０４で最適化の効果が最大となる適用箇所を、線形計画法を解くことによって求める。ステップ４０４の詳細処理例を図１４に示す。線形計画法はソルバと呼ばれるソフトウェアによって解く事ができ、ソルバへの入力は線形の目的関数と制約式である。まずステップ１４０１で、図１３に示されるような第２のコールグラフ中において、環を置き換えたノード以外のノードに対応する関数毎に変数を作る。ステップ１４０１の処理例の結果を図１５に示す。これは図１３の第２のコールグラフのうち、環を置き換えたノードcd以外の各関数に対応する変数を作成したものである。これらの変数は目的関数と制約式の変数に使われる。
【００５３】
図１４へ戻り、ステップ１４０１の次にステップ１４０２でソルバの入力となる目的関数を作る。ステップ１４０２の処理例を図１６に示す。まずステップ１６０１で関数の集合を作る。次にステップ１６０２で関数毎の得点を記入する表を作る。この表のフォーマット例を図１７に示す。そしてステップ１６０３で表の得点を0に初期化する。判定１６０４で関数の集合は空か判定し、空でないなら、ステップ１６０５で関数の集合から関数をひとつ取り出す。次に判定１６０６では、この取り出した関数に対応するノードに、環を置き換えたノードであることを示す印がついているか判定する。環を置き換えたノードであれば、判定１６０４へ戻る。そうでなければ、ステップ１６０８へ行き、退避回復するコードの位置２０４にある命令の数と図２８の各命令のサイズの積から関数の退避回復するコードサイズを得る。次にステップ１６０９でこのコードサイズを関数の得点に加算する。次に、ステップ１６１０で関数の呼出し元の集合を作り、判定１６１１では関数の呼出し元の集合は空か判定する。空であれば判定１６０４へ戻る。空でなければステップ１６１２へ行き、関数の呼出し元の集合から関数をひとつ取り出す。次にステップ１６１３で最適化を適用するコール命令の数と、コール命令を割込み命令に変換した際のサイズ差分の積から最適化を適用した際の呼出し元の命令のコードサイズの変化量を求める。ステップ１６１４で、求めた変化量を関数の得点に加算し、判定１６１１へ戻る。判定１６０４で関数の集合が空ならステップ１６１５へ行く。ステップ１６１５では表に書き込まれた関数に対応する得点を係数とし、その係数と関数に対応する変数との積の総和で作られる線形式を作成し、それを目的関数として終了する。図１３のコールグラフに対し、図２７で示す退避回復する命令数と、図２８で示す命令サイズが与えられたとき、図１８に示す得点が得られる。この得点を元に作成された目的関数を図１９に示す。例えば、図２７及び図２８を参照するに、関数ｂの場合、退避コードの数が“２”、回復コードの数が“２”、命令サイズ“２”のコール命令を命令サイズ“１”の割込み命令に変えたときの変化量が“１”であるから、関数ｂの得点は５になる。目的関数において例えば変数Ｘｂの係数は対応する関数の得点になっている。
【００５４】
図１４へ戻り、ステップ１４０２の次にステップ１４０３で制約式を作る。ステップ１４０３の処理例を図２０に示す。ステップ２００１でコールグラフのルートからリーフに至る経路の集合を作る。経路の集合は深さ優先探索で求めることができる。深さ優先探索については例えばThomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. “Introduction to Algorithm 2nd edition”, pp. 540-549,  MIT Press and McGraw-Hill, 2001に記載がある。
【００５５】
図１３において、第１経路はａ０，ｇ１，ｅ１、第２経路はａ０，ｂ０，ｇ１，ｅ０、第３経路はａ０，ｂ０，ｃｄ０，ｇ１，ｅ１、第４経路はａ０，ｂ０，ｃｄ０，ｅ０，ｇ１，ｅ１、第５経路はａ０，ｂ０，ｃｄ０，ｆ０，ｇ１，ｅ１、第６経路はａ０，ｂ０，ｈ１である。判定２００２で経路の集合が空か判定し、空でなければ、ステップ２００３へ行き、経路の集合から経路をひとつ取り出す。ステップ２００４で取り出した経路のノードの集合を作る。そしてステップ２００５でそのノードに対応する関数とその関数に対応する線形式の係数を記録するための表を作成する。この表のフォーマット例を図２１に示す。ステップ２００６で表の係数を０に初期化する。判定２００７でノードの集合は空か判定し、空でなければ、ステップ２００８でノードの集合からノードをひとつ取り出す。次にステップ２００９でノードに対応する関数に対応する表の係数を１増やす。そして判定２００７へ戻る。判定２００７でノードの集合が空ならステップ２０１０へ行き、表に書き込まれた係数と、係数に対応する変数との積の総和で作られる線形式を左辺とし、レジスタバンク数を右辺とし、左辺≦右辺となる制約式を作成し判定２００２へ戻る。判定２００２で経路の集合が空であれば、終了する。図１３のコールグラフに対し、ステップ１４０３を実行することで図２１に示す表の列２１０１が埋まる。図１３の各経路について係数を埋めた表を図２２に示す。そして図２２の表を元に作成した制約式を図２３に示す。この制約式はレジスタバンクの数が３組という制約を反映したものであり、非同期割込みである関数ｇ，ｈに関しては夫々１組のレジスタバンクを用いるので制約式の右辺は“１”になっており、そのほかの制約式の右辺は３以下とされる。
【００５６】
図１４へ戻り、ステップ１４０４で適用対象となる関数を求める。ステップ１４０４の処理例を図２４に示す。ステップ２４０１で前の処理で作成した制約式と目的関数を入力としてソルバを実行する。ステップ２４０２でソルバの解の変数の集合を作成し、ステップ２４０３で最適化を適用する関数を入れるための空の集合を作る。次に判定２４０４で変数の集合は空か判定し、空でないなら、ステップ２４０５で集合から変数をひとつ取り出す。次に判定２４０６で変数の値が1か判定し、１でないなら判定２４０４へ戻る。１なら判定２４０７で変数に対応する関数が割込み関数か判定し、割込み関数なら判定２４０４へ戻り、割込み関数でないなら、ステップ２４０８で変数に対応する関数を最適化の適用対象の集合にいれ、判定２４０４へ戻る。判定２４０４で変数の集合が空なら終了する。図１９の目的関数と図２３の制約式をソルバに入力して得られる解を図２５に示す。変数が１にされた関数が最適化の適用対象であることを意味する。この表から、関数e, f, g, hの変数が1であることがわかり、g, hは割込み関数であるので、eとfが最適化の適用対象となる。
【００５７】
図４に戻り、ステップ１４０４で求めた適用対象の関数の集合に対してステップ３０５で最適化を適用し、当該関数に割込み命令を用いる。以上の処理で実現される処理によって、コンパイラの生成するオブジェクトコード１０３のサイズが削減され、計算機１１０でオブジェクトコード１０３を格納するために必要な記憶領域１１１が削減可能となり、計算機１１０の製造コストを抑えることが可能となる。コードサイズを削減することによって、コードを格納するＲＯＭ及びＲＡＭ等の記憶領域の容量を抑え、コードを実行する組込み機器等の製造コストを下げることができる。
【００５８】
以上説明したコンパイル方法によれば、関数呼出しを行う割込み命令の適用箇所を、再帰関数以降で呼出される関数と割込み関数以降で呼出される関数にも広げられ、更なるコードサイズの縮小に寄与することができる。そして、そしてその方法を実現するコンパイラによれば、当該方法を容易に実現することができるという効果を奏する。
【００５９】
以上本発明者によってなされた発明を実施形態に基づいて具体的に説明したが、本発明はそれに限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは言うまでもない。レジスタバンクの数は３に限定されず適宜変更可能である。コンピュータ装置１０４はエンジニアリングワークステーションやパーソナルコンピュータによって実現すればよく、コンピュータ装置１１０はマイクロコントローラを搭載した組込み機器によって実現すればよい。
【符号の説明】
【００６０】
１０１  ソースコード
１０２  コンパイルプログラムとしてのコンパイラ
１０３  オブジェクトコード
１０４  コンピュータ装置としての計算機
１０５  ＣＰＵ
１０６  メインメモリ
１０７  演算器
１０８  レジスタ
１０９  レジスタバンク
１１１  記憶領域
１１２  ステータスレジスタ
１１３  割込み判定器
１１４  外部機器
【図１】
2010250721.tif 000003
【図２】
2010250721.tif 000004
【図３】
2010250721.tif 000005
【図４】
2010250721.tif 000006
【図５】
2010250721.tif 000007
【図６】
2010250721.tif 000008
【図７】
2010250721.tif 000009
【図８】
2010250721.tif 000010
【図９】
2010250721.tif 000011
【図１０】
2010250721.tif 000012
【図１１】
2010250721.tif 000013
【図１２】
2010250721.tif 000014
【図１３】
2010250721.tif 000015
【図１４】
2010250721.tif 000016
【図１５】
2010250721.tif 000017
【図１６】
2010250721.tif 000018
【図１７】
2010250721.tif 000019
【図１８】
2010250721.tif 000020
【図１９】
2010250721.tif 000021
【図２０】
2010250721.tif 000022
【図２１】
2010250721.tif 000023
【図２２】
2010250721.tif 000024
【図２３】
2010250721.tif 000025
【図２４】
2010250721.tif 000026
【図２５】
2010250721.tif 000027
【図２６】
2010250721.tif 000028
【図２７】
2010250721.tif 000029
【図２８】
2010250721.tif 000030