(57)【特許請求の範囲】
【請求項１】
入力されたプログラムを、所定のサイズ制限以内のサイズを有するキャッシュブロックに分割する分割部と、
前記キャッシュブロック単位のオブジェクトコードを生成するコード生成部と、を備え、
前記分割部は、
前記プログラムを構成する命令列の処理順を表す経路において、入口の命令が１つで、かつ出口の命令が１つであるような一連の命令列で構成される部分グラフを検出する部分グラフ検出部と、
前記部分グラフがサイズ制限を超えるサイズを有するか否かを確認し、超える場合、当該部分グラフに含まれる命令列のうち、サイズ制限以内の一部の命令列を新たなキャッシュブロックとして前記部分グラフから切り出し、切り出し元の前記部分グラフに、切り出した命令列を呼び出す命令を挿入する処理を、前記部分グラフがサイズ制限以内となるまで繰り返したうえ、前記部分グラフを新たなキャッシュブロックとして元のプログラムから切り出し、切り出し元のプログラムに、切り出した部分グラフ内の命令列を呼び出す命令を挿入する切り出し部と、
を備えたことを特徴とする情報処理装置。
【請求項２】
前記部分グラフ検出部は、前記切り出し部によって前記部分グラフが切り出された後のプログラムに対し、さらに前記部分グラフを検出し、
前記切り出し部は、前記切り出された後のプログラムがサイズ制限を超えるサイズを有するか否かを確認し、超える場合、サイズ制限以内となるまで前記部分グラフの切り出しを繰り返すことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記情報処理装置は、入力されたプログラムからコントロールフローグラフを生成するコントロールフローグラフ生成部をさらに含み、
前記部分グラフ検出部は、コントロールフローグラフを構成する基本ブロックを少なくとも１つ含むノードの単位で前記部分グラフの範囲を特定し、
前記切り出し部は、前記ノードの単位で切り出しを行い、切り出したノードに含まれる基本ブロックで構成される新たなコントロールフローグラフを生成することを特徴とする請求項１に記載の情報処理装置。
【請求項４】
前記部分グラフ検出部は、プログラムに含まれる前記部分グラフのうち、部分グラフをさらに含まない最小単位の部分グラフを検出することを特徴とする請求項１から３のいずれかに記載の情報処理装置。
【請求項５】
前記切り出し部は、前記部分グラフに含まれる直線状に並んだノード列の範囲を特定し、当該範囲内にあり、当該範囲から選択した一のノードと連続したノード集合であって、合計サイズが前記サイズ制限を超えない最大サイズであるノード集合を切り出すことを特徴とする請求項３に記載の情報処理装置。
【請求項６】
前記部分グラフ検出部が検出した部分グラフ、および前記切り出し部が特定した直線状に並んだノード列の範囲を、それぞれ１つのノードに置き換えるノード置換部をさらに含み、
前記部分グラフ検出部は、前記ノード置換部が置き換えを行った後のコントロールフローグラフに対して、さらに前記部分グラフの検出を行うことを特徴とする請求項３に記載の情報処理装置。
【請求項７】
前記切り出し部は、プログラムに含まれる基本ブロックのそれぞれについて、切り出し対象となった回数をカウントし、新たなノードの切り出しを行う際、含まれる基本ブロックがそれまでに切り出し対象となった回数が少ないノードを優先して切り出すことを特徴とする請求項３に記載の情報処理装置。
【請求項８】
情報処理装置が、プログラムを所定のサイズ制限以内のサイズを有するキャッシュブロックに分割する方法であって、
部分グラフ検出部が、メモリに格納されたプログラムを読み出し、当該プログラムを構成する命令列の処理順を表す経路において、入口の命令が１つで、かつ出口の命令が１つであるような一連の命令列で構成される部分グラフを検出するステップと、
切り出し部が、前記部分グラフを新たなキャッシュブロックとして元のプログラムから切り出し、メモリに格納するステップと、
ノード置換部が、切り出し元のプログラムに、切り出した部分グラフ内の命令列を呼び出す命令を挿入して新たなキャッシュブロックとしてメモリに格納するステップと、
を含み、
前記切り出し部は、前記部分グラフを元のプログラムから切り出しメモリに格納するステップの前に、当該部分グラフがサイズ制限を超えるか否かを確認し、超える場合、
前記切り出し部が、当該部分グラフに含まれる命令列のうち、サイズ制限以内の一部の命令列を新たなプログラムブロックとして前記部分グラフから切り出し、メモリに格納するステップと、
前記ノード置換部が、切り出し元の前記部分グラフに、切り出した命令列を呼び出す命令を挿入するステップと、
を前記部分グラフがサイズ制限以内となるまで繰り返すことを特徴とするプログラム分割方法。
【請求項９】
前記切り出し部が、命令列が切り出し対象となった回数をカウントするステップをさらに含み、
前記切り出し部が、前記一部の命令列を新たなプログラムブロックとして切り出すステップは、それまでに切り出し対象となった回数が少ない命令列を優先して切り出すことを特徴とする請求項８に記載のプログラム分割方法。
【請求項１０】
プログラムを所定のサイズ制限以内のサイズを有するキャッシュブロックに分割する機能をコンピュータに実現させるコンピュータプログラムであって、
プログラムをメモリから読み出す機能と、
読み出したプログラムを構成する命令列の処理順を表す経路において、入口の命令が１つで、かつ出口の命令が１つであるような一連の命令列で構成される部分グラフを検出する機能と、
前記部分グラフがサイズ制限を超えるサイズを有するか否かを確認し、超える場合、当該部分グラフに含まれる命令列のうち、サイズ制限以内の一部の命令列を新たなキャッシュブロックとして前記部分グラフから切り出し、切り出し元の前記部分グラフに、切り出した命令列を呼び出す命令を挿入する処理を、前記部分グラフがサイズ制限以内となるまで繰り返す機能と、
前記部分グラフを新たなキャッシュブロックとして元のプログラムから切り出し、切り出し元のプログラムに、切り出した部分グラフ内の命令列を呼び出す命令を挿入してキャッシュブロックとする機能と、
生成したプログラムブロックをメモリに格納する機能と、
をコンピュータに実現させることを特徴とするコンピュータプログラム。
【請求項１１】
命令列が切り出し対象となった回数をカウントする機能をさらにコンピュータに実現させ、
前記部分グラフがサイズ制限以内となるまで繰り返す機能は、それまでに切り出し対象となった回数が少ない命令列を優先して前記部分グラフから切り出すことを特徴とする請求項１０に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報処理技術に関し、プログラムのコンパイルを行うコンパイラおよびそれに適用されるプログラム分割方法に関する。
【背景技術】
【０００２】
近年の情報処理技術の発展により、ＣＤ−ＲＯＭなどの記録媒体に記録されたソフトウェアやネットワーク上のサーバからダウンロードしたソフトウェアなどを起動させることにより、一の情報処理装置に対して多種多様な機能を発揮させることが容易にできるようになった。そのような状況において、いかに効率よく高速にプログラムを処理していくかは常に重要な課題となってきた。
【０００３】
処理を高速化させるためには、単にプロセッサの処理能力を向上させるばかりでなく、プロセッサユニット間、プロセッサユニットとメモリ間など、情報処理装置内での各ユニット間のデータ転送速度を向上させる必要がある。プロセッサがメモリに格納されたデータやプログラムに高速にアクセスするための技術のひとつがキャッシュメモリによるメモリの階層化である。キャッシュメモリは一般に、メインメモリより容量が小さくアクセスを高速に行うことのできるメモリである。キャッシュメモリにアクセス頻度の高いデータを格納しておくことにより、メインメモリへのアクセス回数を減らし、全体としてデータアクセスに要する時間を削減することができる。複数のプロセッサを備えたマルチプロセッサシステムにおいても、プロセッサごとにローカルメモリを設け、データを一時保存することにより、より多くのデータに対する高速なアクセスを可能にしている。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
プロセッサがプログラムを高速処理するためには、そのマシンコードに対しても高速にアクセスする必要がある。ところが高速アクセスが可能なメモリ、すなわち高速メモリは一般的にその容量が小さいため、プログラムの規模によってはその全体をキャッシュする、すなわち高速メモリに格納することができない場合も多い。この場合、プログラマは手作業でプログラムを複数のモジュールに分割し、さらに、これらのモジュールを適当なタイミングでメインメモリから高速メモリにキャッシュするためのプログラムを記述する必要があった。
【０００５】
本発明はこのような課題に鑑みてなされたものであり、その目的は、プログラマの負担を少なくキャッシュに適した形式のプログラムを生成する技術を提供することにある。
【課題を解決するための手段】
【０００６】
本発明のある態様はコンパイラに関する。このコンパイラは、入力されたプログラムを、所定のサイズ制限以内のサイズを有するキャッシュブロックに分割する分割部と、キャッシュブロック単位のオブジェクトコードを生成するコード生成部と、を備え、分割部は、プログラムを構成する命令列の処理順を表す経路において、入口の命令が１つで、かつ出口の命令が１つであるような一連の命令列で構成される部分グラフを検出する部分グラフ検出部と、部分グラフに含まれる命令列の少なくとも一部を新たなキャッシュブロックとして切り出し、切り出し元の命令列で構成されるキャッシュブロックに新たなキャッシュブロック内の命令列を呼び出す命令を挿入する切り出し部と、を備えたことを特徴とする。
【０００７】
本発明の別の態様はプログラム分割方法に関する。このプログラム分割方法は、プログラムを構成する命令列の処理順を表す経路において、入口の命令が１つで、かつ出口の命令が１つであるような一連の命令列で構成される部分グラフを検出するステップと、部分グラフに含まれる命令列の少なくとも一部を新たなプログラムブロックとして切り出すステップと、切り出し元の命令列で構成されるプログラムブロックに新たなプログラムブロック内の命令列を呼び出す命令を挿入するステップと、を含むことを特徴とする。
【０００８】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【０００９】
本発明によれば、プログラムのキャッシュに適したプログラム分割を容易に行うことができる。
【発明を実施するための最良の形態】
【００１０】
本実施の形態ではキャッシュに適したプログラムを容易に生成する技術を提供する。当該技術は例えばコンパイラの形で実現することができる。ここでは初めに、本実施の形態によって生成されたプログラムを処理する装置の例について説明する。図１は本実施の形態で生成したプログラムを処理する情報処理装置の構造例を示している。情報処理装置１０は、プロセッサ１４、ローカルメモリ１６、レジスタ１８を含むプロセッサユニット１２、メインメモリ２０、記憶装置２２、および入出力装置２４を含み、それぞれがバス２８を介して互いにデータの送受を行う。プロセッサユニット１２は接続したＭＦＣ（Memory Flow Controller）のＤＭＡ（Direct Memory Access）を起動させることによりデータの転送を実現させてもよいが、ここではその図示を省略する。
【００１１】
同図ではプロセッサユニット１２が２つ示されているが、その数は２つに限られず、１つまたは３つ以上でもよい。またプロセッサ１４も各プロセッサユニット１２内に複数設けてもよい。各プロセッサ１４が対等の機能を発揮することにより複数のプロセスまたはスレッドを並列処理してもよいし、グラフィックプロセッサ、Ｉ／Ｏプロセッサなど特定の機能を発揮するものが含まれていてもよい。
【００１２】
プロセッサユニット１２のプロセッサ１４はユーザが起動したアプリケーションソフトウェアなどのプログラムを実行する。ローカルメモリ１６は例えばプロセッサ１４と同一のチップまたは近隣に配置された高速アクセスが可能なＳＲＡＭ（Static Random Access Memory）などで構成し、メインメモリ２０にロードされたプログラムの一部や、処理に必要なデータ、処理結果のデータなどを適宜格納する。レジスタ１８はプロセッサ１４における処理に必要な値を一時的に保持する一般的なレジスタで構成してよい。本実施の形態では特に、ローカルメモリ１６に格納されたプログラムを管理するためのデータ、スタックなども格納する。
【００１３】
メインメモリ２０は例えばＤＲＡＭ（Dynamic Random Access Memory）などで構成し、ユーザが起動したアプリケーションなどのプログラム全体または一部を格納する。メインメモリ２０はその他にも複数のプロセッサユニット１２間でデータをやりとりするための共有メモリやＯＳを動作させるためのシステムメモリなどの機能を果たしてもよい。記憶装置２２はハードディスク装置、ＣＤ−ＲＯＭなどの記録媒体とその読み取り装置など一般的に用いられる記憶装置のいずれかまたは組み合わせでよく、プログラムと処理に必要なデータ、処理の途中や終了時などに保存すべきデータなどを記憶する。入出力装置２４はアプリケーションの起動をはじめとして情報処理装置１０に対しユーザが行う指示入力や処理結果の出力などを行い、キーボード、コントローラ、ポインティングデバイスなどの入力装置、表示装置、スピーカー、プリンターなどの出力装置のいずれかまたは組み合わせでよい。
【００１４】
情報処理装置１０は情報処理に際し、記憶装置２２に記憶されたプログラムなどを、まずメインメモリ２０にロードする。そして各プロセッサユニット１２において実行する処理に応じて、プログラムの一部をメインメモリ２０からローカルメモリ１６にキャッシュする。これにより、プロセッサ１４はプログラムの進捗ごとにメインメモリ２０にアクセスし直す必要がなくなる。アクセスを可能な限りプロセッサユニット１２内で閉じることよって、ソフトウェアの処理を高速化する。このような場合、従来の手法では、プログラムを記述する段階で、当該プログラムをローカルメモリ１６に格納できる大きさのモジュールに分割しておく必要があった。
【００１５】
ローカルメモリ１６へのキャッシュを考慮したプログラムの作成は、ゲームやシミュレーションのソフトウェアなど高度な機能を提供する、長大で複雑なプログラムの場合は特に、プログラマの負担になることが考えられる。そこで本実施の形態では、プログラムをコンパイルする際、コンパイラが当該プログラムを所定のサイズ以下に自動的に分割できるようにする。これにより、プログラマの負担を増大させずにキャッシュに適した形式のプログラムが生成でき、結果的に高速のプログラム参照が可能となる。以後、コンパイラが生成した、分割後のプログラムの１つ１つを「キャッシュブロック」と呼ぶ。
【００１６】
図２はローカルメモリ１６とメインメモリ２０に格納されるデータの構成を模式的に示している。まずメインメモリ２０には、本実施の形態におけるコンパイラによってコンパイルされたプログラムのオブジェクトコードが記憶装置２２からロードされる。上述のとおり、プログラムはコンパイラによってキャッシュブロックに分割されているため、メインメモリ２０には図２に示すように、１つのソフトウェアに対し複数のキャッシュブロック４２が格納される。
【００１７】
ローカルメモリ１６には、メインメモリ２０に格納された複数のキャッシュブロック４２のうち、プロセッサ１４の処理において参照される対象が、キャッシュブロックの単位でキャッシュされ、キャッシュブロック３２として格納される。従って、一のキャッシュブロック４２のサイズは、最大でもローカルメモリ１６内のキャッシュ用の記憶領域の容量を超えない必要がある。さらにキャッシュの手法やメモリ構造などによってもキャッシュブロック４２のサイズの上限は様々に制限される。以後、このように環境によって決定されるサイズの上限を総じて「キャッシュブロックのサイズ制限」と呼ぶ。
【００１８】
キャッシュブロック４２、３２はプログラムの一部であるため、あるキャッシュブロック３２を参照して処理を行っている途中で別のキャッシュブロック中の関数を呼び出したり元のキャッシュブロック中の関数に戻ったりする必要が生じる。このとき参照すべきキャッシュブロックがローカルメモリ１６に存在しなければ、メインメモリ２０より該当するキャッシュブロック４２を特定しローカルメモリ１６にキャッシュする。
【００１９】
図３は情報処理装置１０においてキャッシュブロック間の関数呼び出しおよび戻り処理を実現する手法の例を説明するための図である。この例では、関数呼び出し時に、呼び出し元のキャッシュブロックの戻り先のアドレスをリンクスタックに格納し、戻り時にはそれを参照して元のキャッシュブロックの該当箇所に処理を戻す。同図においてリンクスタック３６ａ〜３６ｅは、レジスタ１８に格納する１つのリンクスタックの時系列変化を示している。キャッシュブロック３２ａ〜３２ｃは、関数呼び出しによって順次参照されるキャッシュブロックであり、キャッシュブロック３２ａ、キャッシュブロック３２ｂ、キャッシュブロック３２ｃの順に参照されるとする。
【００２０】
まずリンクスタック３６ａを初期状態とする。ここでは図示しないキャッシュブロック内の戻り先のアドレスが「Ｅ４」、「Ｅ３」、「Ｅ２」、「Ｅ１」の順で格納されている。この状態においてキャッシュブロック３２ａの処理を実行し、「ｃａｌｌ  Ｃ１」なる命令により、キャッシュブロック３２ｂのアドレス「Ｃ１」からの関数を呼び出す際（Ｓ１０）、キャッシュブロック３２ａの戻り先のアドレス「Ｒ１」をリンクスタック３６ａに追加する（リンクスタック３６ｂ）。続いてキャッシュブロック３２ｂの処理を実行し、「ｃａｌｌ  Ｃ２」なる命令により、キャッシュブロック３２ｃのアドレス「Ｃ２」からの関数を呼び出す際は（Ｓ１２）、キャッシュブロック３２ｂの戻り先のアドレス「Ｒ２」をリンクスタック３６ｂに追加する（リンクスタック３６ｃ）。
【００２１】
次にキャッシュブロック３２ｃの処理を実行し、「ｒｅｔｕｒｎ」なる命令によりキャッシュブロック３２ｂに処理を戻す際は（Ｓ１４）、リンクスタック３６ｃを参照し、先頭のエントリから戻り先のアドレス「Ｒ２」を取得する。結果としてリンクスタック３６ｄの状態になるため、キャッシュブロック３２ｂの処理を実行し、「ｒｅｔｕｒｎ」なる命令によりキャッシュブロック３２ａに戻る際は（Ｓ１６）、リンクスタック３６ｄを参照することによって先頭のエントリから戻り先のアドレス「Ｒ１」を取得できる。同図に示すように、リンクスタック３６ａ〜３６ｅの容量が不足した場合は、最も古いエントリを削除していく。
【００２２】
ところであるキャッシュブロックを処理中に、ローカルメモリ１６にキャッシュしておいた戻り先のキャッシュブロックが、別のキャッシュブロックがキャッシュされることにより上書きされてしまうことが考えられる。そこで、上書きされるキャッシュブロックのアドレスがリンクスタック３６ａ〜３６ｅにエントリされている場合は、当該エントリに無効アドレスを代入する。ここで無効アドレスとは命令が配置されることがない任意のアドレスである。例えばキャッシュブロック３２ｃを実行中に、戻り先のキャッシュブロック３２ｂを上書きする場合、リンクスタック３６ｃの先頭エントリにある「Ｒ２」を「０」などとする。これにより、戻り先のアドレスを含むキャッシュブロック３２ｂが上書きされたことを識別できる。
【００２３】
これまで述べたような情報処理装置１０における動作を実現させるために、本実施の形態では以下に述べるポリシーでのプログラム分割を自動的に行う手法を実現する。
（１）キャッシュブロックのサイズはサイズ制限を超えず、かつ十分に大きくする
（２）サブルーチン化に適した形で命令列を切り出す
【００２４】
上記（１）については上述のとおり、キャッシュブロックが、与えられた環境下でキャッシュできるサイズを有することが必要である。一方で、各キャッシュブロックが細かくなりすぎないことも重要である。プログラムを安易に細かく分割し、小さいサイズのキャッシュブロックが多数生成されると、キャッシュブロックを跨いだ関数の呼び出しや戻り処理の回数が増加する。結果的にそれらの要因がオーバーヘッドを生むことになる。したがってキャッシュブロックのサイズは制限を超えない範囲で大きくすることが望ましい。
【００２５】
上記（２）においてサブルーチン化に適した形とは、関数を構成する命令列のうち、入口が１つ、出口が１つとなっている部分のことである。サブルーチン化に適した形で切り出した部分を１つのキャッシュブロックとすることにより、当該キャッシュブロックに含まれる命令を呼び出す処理や、元のキャッシュブロックに戻る処理が複雑化せず、図３で示したリンクスタックによる呼び出し処理、戻り処理の機構を効果的に利用することができる。
【００２６】
図４は本実施の形態において、情報処理装置１０で起動されるプログラムをコンパイルするコンパイラの構造を示している。図４において、様々な処理を行う機能ブロックとして記載される各要素は、ハードウェア的には、ＣＰＵ、メモリ、その他のＬＳＩで構成することができ、ソフトウェア的には各種演算を行うプログラムなどによって実現される。したがって、これらの機能ブロックがハードウェアのみ、ソフトウェアのみ、またはそれらの組合せによっていろいろな形で実現できることは当業者には理解されるところであり、いずれかに限定されるものではない。例えばコンパイラ１００は対応するソフトウェアをロードした情報処理装置１０の一部によって実現してもよい。
【００２７】
コンパイラ１００は、ソースコードの字句解析などを行いコントロールフローグラフ（以下、「ＣＦＧ」と呼ぶ）を生成するＣＦＧ生成部１０４、ＣＦＧを分割する分割部１０６、分割した各ＣＦＧに対応するオブジェクトコードを生成してキャッシュブロックとするコード生成部１１４、コンパイルや分割に必要なデータ、生成したオブジェクトコードを格納するメモリ１０２を含む。ＣＦＧ生成部１０４は、メモリ１０２に格納したソースコードの字句解析、構文解析などを行い、ＣＦＧを構築する。ここでは、一般的なコンパイラがＣＦＧを構築するために行う処理を、ソースコードを記述する言語などに応じて適宜行う。構築したＣＦＧは分割部１０６に入力する。
【００２８】
分割部１０６は、後述する切り出し可能な部分グラフを検出する部分グラフ検出部１０８、分割のためにノードを切り出す切り出し部１１０、複数のノードを１つのノードにまとめるノード置換部１１２を含む。分割部１０６は、ＣＦＧ生成部１０４から入力されたＣＦＧを、必要に応じて上記ポリシーに則り分割する。このとき、元の関数がサイズ制限を超えていなければ分割は行わないため、入力されたＣＦＧをそのままコード生成部１１４に出力する。分割した場合は、分割する都度、新たに生成したＣＦＧを出力結果としてメモリ１０２に格納していき、コード生成部１１４は当該ＣＦＧを読み出す。コード生成部１１４は、分割部１０６が出力したＣＦＧに基づき、オブジェクトコードを生成する。オブジェクトコードは各ＣＦＧに対応したまとまりを有し、これが最終的なキャッシュブロックとなる。生成したキャッシュブロックはメモリ１０２に格納する。コード生成部１１４は一般的なコンパイラがオブジェクトコードを生成するための処理を、ソースコードを記述する言語などに応じて適宜行ってよい。
【００２９】
次に分割部１０６の部分グラフ検出部１０８、切り出し部１１０、ノード置換部１１２が行うＣＦＧの分割手順の概要について説明する。ＣＦＧとは、プログラムの制御の流れを表現するグラフである。図５は本実施の形態で生成するＣＦＧの例を示している。同図のＣＦＧは次のプログラムに対応する。
int foo(int x)
{
int y = 0;
do {
++y;
if (x < y) {命令列１} else {命令列２}
if (x == y) {命令列３} else {命令列４}
} while (y < 10);
}
【００３０】
ＣＦＧは基本ブロックをノードとして、ノードからノードへの制御の移行を示したものである。ここで基本ブロックとは、末尾以外に分岐命令が存在せず、かつ先頭以外に進入する経路が存在しない命令列のことである。図５のＣＦＧにおいては、基本ブロックは矩形で表されたノードＢ１〜Ｂ８の１つ１つである。ＣＦＧのデータは実際には、当該ＣＦＧを構成する各ノードの識別番号と、それぞれのノードが含む基本ブロックの識別番号リスト、ドミネータ、前のノードの識別番号、次のノードの識別番号、といったデータ列とを対応づけることによって表される。基本ブロックの識別番号は、別途、中身の命令列と対応づけられている。
【００３１】
ここで「前のノード」とは対象ノードへ向かう矢印の起点ノード、「次のノード」とは対象ノードを起点とした矢印が向かう先のノードをいうものとする。図５の例では、例えばノードＢ５の「前のノード」はノードＢ３、Ｂ４であり、「次のノード」はノードＢ６、Ｂ７である。「ドミネータ」については後に説明する。上述したＣＦＧのデータ構造が一般的なＣＦＧにて用いられているものであることは当業者には理解されるところである。
【００３２】
分割部１０６の部分グラフ検出部１０８は、入力されたＣＦＧの分割を行うために、１つのノードを唯一の入口とし、１つのノードを唯一の出口とする一連の命令列で構成される部分を検出する。このような部分は、上記ポリシー（２）のサブルーチン化に適しており、キャッシュブロックとして切り出すのに好適である。以後、このような部分を「切り出し可能な部分グラフ」と呼ぶ。図５の例では、ノードＢ５を通ることなくノードＢ６、Ｂ７へ至る経路はない。また、一旦ノードＢ５を通ると必ずノードＢ８へ至る。すなわち、ノードＢ５はノードＢ５、Ｂ６、Ｂ７からなる部分グラフの唯一の入口であり、ノードＢ８はこの部分グラフの唯一の出口である。従ってノードＢ５、Ｂ６、Ｂ７からなる部分グラフは切り出し可能な部分グラフである。ノードＢ２、Ｂ３、Ｂ４からなる部分グラフも同様である。
【００３３】
ここで部分グラフ検出部１０８が検出するのは、さらに切り出しが可能な部分グラフを含んでいない最小の切り出し可能な部分グラフとする。例えば、ノードＢ２、Ｂ３、Ｂ４、Ｂ５、Ｂ６、Ｂ７からなる部分グラフは、唯一の入口がノードＢ２であり唯一の出口がノードＢ８であるが、ノードＢ５、Ｂ６、Ｂ７からなる切り出し可能な部分グラフを含んでいるため、検出対象の「最小の切り出し可能な部分グラフ」には相当しない。
【００３４】
切り出しはおよそ次のように行われる。まず部分グラフ検出部１０８が検出した切り出し可能な部分グラフのサイズが、メモリ１０２にあらかじめ設定したキャッシュブロックのサイズ制限を超えるか否かを確認する。超える場合は、切り出し部１１０がその部分グラフに含まれる一部のノードを切り出し、切り出した部分のＣＦＧを新たに生成する。このとき元のＣＦＧにおける切り出されたノードには、新たに生成したＣＦＧを呼び出す命令列を挿入する。図５の例で、ノードＢ５、Ｂ６、Ｂ７からなる部分グラフの合計サイズがキャッシュブロックのサイズ制限を超えていて、命令列３を除くとサイズ制限を下回るとする。この場合、ノードＢ６を切り出し、「命令列３」のみを含む新たなＣＦＧを作成する。そして図５のＣＦＧにおけるノードＢ６の命令列３を、新たに生成したＣＦＧを呼び出す命令列に置き換える。
【００３５】
その後、ノード置換部１１２は、検出した切り出し可能な部分グラフ全体を１つのノードに置き換える。図５の例では、ノードＢ５、Ｂ６、Ｂ７の部分グラフをＢ５’なる１つのノードに置き換える。ノードをまとめることにより、当該ノードを含む切り出し可能な部分グラフがさらに検出できる場合がある。その場合は必要に応じて上記と同様の処理を繰り返すことにより、最終的には全てのＣＦＧのサイズがサイズ制限以内となるようにする。
【００３６】
上述のとおり、ＣＦＧは、ＣＦＧを構成するノードの識別番号と、そのノードが含む基本ブロックの識別番号のリストおよびＣＦＧ内での相対的な位置を示す情報とを対応づけたデータ構造を有する構造体である。したがって切り出し部１１０がノードを切り出す際は例えば、新たに生成したＣＦＧの構造体において、切り出したノードの識別番号と、そのノードに元々対応づけられていた基本ブロックの識別番号のリストとを対応づける。一方で、そのように生成したＣＦＧの呼び出し命令を中身とした基本ブロックを新たに生成し、元のＣＦＧにおいて、切り出されたノードの基本ブロックのリストに、生成した基本ブロックの識別番号を代入する。また、ノード置換部１１２が切り出し可能な部分グラフを１つのノードに置き換える際は、元のＣＦＧに新たなノードの識別番号を挿入し、当該ノードが経路に含まれるように、各ノードの相対的な位置を示す情報を更新する。さらに置き換える前の全ノードの基本ブロックのリストを、新たなノードの基本ブロックのリストにまとめる。さらなる詳細は後述する。
【００３７】
次に、上述の処理を基本とする、分割部１０６が行う分割手順の概要を説明する。図６は分割処理が進捗する際のＣＦＧの変化の例を模式的に示している。以後、理解を容易にするために、必要に応じて、各種処理がＣＦＧの図上で行われるように説明するが、実際には上述のようにＣＦＧの構造体の内外で対応づけられたデータが更新されるものである。図６において４つのＣＦＧ７４ａ、７４ｂ、７４ｃ、７４ｄはその順で１つのＣＦＧの経時変化を表している。まず部分グラフ検出部１０８が、ＣＦＧ７４ａにおいて切り出し可能な部分グラフ７６ａを検出する。次に上述のとおり、切り出し可能な部分グラフ７６ａのサイズがキャッシュブロックのサイズ制限を超えるか否かの確認をする。超えている場合、切り出し部１１０はまず、切り出し可能な部分グラフ７６ａに、直線状に並んだノード列が含まれているか否かを確認する。
【００３８】
同図では直線状に並んだノード列７８が切り出し可能な部分グラフ７６ａに含まれている。このような場合、まず直線部分をなすノード列の範囲を特定する。そして当該範囲の合計サイズがキャッシュブロックのサイズ制限を超える場合、直線部分の一部のノードを切り出し、新たなＣＦＧを生成する。このとき、サイズ制限を超えない範囲でできるだけ多くのノードをまとめて切り出すようにする。同図では直線状に並んだノード列７８のうち、ノード列７９がまとめて切り出され、新たなＣＦＧ８０が生成されている。
【００３９】
次にノード置換部１１２は、ＣＦＧ７４ｂに示されるように、直線状に並んだノード列７８をその出口ノード８１を除き１つのノード８２に置き換える。このノード８２には、新たなＣＦＧ８０を呼び出す命令が含まれる。この段階で、切り出し可能な部分グラフ７６ｂのサイズがまだキャッシュブロックのサイズ制限を超える場合、切り出し部１１０は、切り出し可能な部分グラフ７６ｂに含まれるいずれかのノードをさらに切り出して新たなＣＦＧを生成する。同図ではノード８４が切り出され、新たなＣＦＧ８６が生成されている。このとき元のノード８４には、新たなＣＦＧ８６を呼び出す命令が代入される。
【００４０】
切り出し可能な部分グラフ７６ｂのサイズがサイズ制限以内となったら、ノード置換部１１２はＣＦＧ７４ｃに示されるように、切り出し可能な部分グラフ７６ｂを１つのノード８８に置き換える。次にＣＦＧ７４ｃ自体の合計サイズがキャッシュブロックのサイズ制限を超えているか確認し、超えている場合、切り出し部１１０はさらに一部のノードを切り出す。図に示したＣＦＧ７４ｃは直線状のノード列であるため、上述した、切り出し可能な部分グラフ内の直線状のノード列と同様に、サイズ制限を超えない範囲でできるだけ多くのノードをまとめて切り出す。同図ではノード列９０がまとめて切り出され、新たなＣＦＧ９２が生成されている。そしてノード置換部１１２は、直線状に並んだノード列のうち出口ノード９１以外のノードを１つのノード９４に置き換える。このノード９４には、新たなＣＦＧ９２を呼び出す命令が含まれる。
【００４１】
以上の処理を行うことにより、結果的には、元のＣＦＧ７４ａから切り出しを行った結果残ったＣＦＧ７４ｄと、切り出しの結果新たに生成されたＣＦＧ８０、ＣＦＧ８６、ＣＦＧ９２とが出力結果として分割部１０６から出力される。本実施の形態では、まず切り出し可能な部分グラフに着目し、その中から切り出し対象を決定するため、プログラム処理中に別のキャッシュブロックを呼び出す場合でも、サブルーチンの呼び出しの如く、切り出し可能な部分グラフ内で閉じた処理となる。そのため関数の呼び出し元と呼び出し先の主従関係が明確となり、呼び出し処理、戻り処理の管理が容易になる。特に図３で説明したリンクスタックを効果的に利用することができる。さらに、直線状のノード列はまとめて切り出すことにより、同じキャッシュブロックを参照して連続した処理が可能となり、参照先のキャッシュブロックが頻繁に替わることによるオーバヘッドの発生を抑制することができる。
【００４２】
次に、以上述べたＣＦＧの分割手法を実現する具体的な手順について説明する。図７は分割部１０６が行う分割処理の手順を示すフローチャートである。まず、入力されたＣＦＧの基本ブロックの中で、キャッシュブロックのサイズ制限を超えているものを検出し、それを適宜複数のブロックに分割する（Ｓ５０）。この分割は、関数呼び出し時に変更する必要があるレジスタに、有効な値が代入されている期間、すなわちレジスタにある値が代入されてから、その値に対する最後の参照が行われるまでの期間を避けて行う必要がある。当該期間の取得手法については、生存期間解析として種々の提案がなされており、それらをのいずれかを適用することができる。分割した場合は、それにより生成された各ブロックが新たなノードとなる。
【００４３】
次に、各ノードをＣＦＧのポストオーダー順に配列する（Ｓ５２）。ここでポストオーダー順とは、グラフの深さ優先探索において、全ての後続ノードを探索してから各ノードに対する処理を行う際の順序である。ここで深さ優先探索とは、同一ノードを複数回訪れることなく、可能な限り入口ノードから遠ざかるようノードを探索する手法をいう。図８はポストオーダー順を説明するための図である。同図において、各円形はＣＦＧ６０を構成するノード６２、６４、６６、６８、７０、７２を表しており、各円内の数字のうち左の数字は探索順、右の数字はポストオーダー順を示している。同図のＣＦＧ６０の場合、入口ノードはノード６２であり、探索はノード６２、ノード６４、ノード６６、ノード６８、ノード７０、ノード７２の順に行う。これらのノードをポストオーダー順に配列すると、ノード６８、ノード６６、ノード６４、ノード７０、ノード７２、ノード６２の順となる。
【００４４】
ポストオーダー順に切り出し可能な部分グラフを検出していくことにより、最小の部分グラフを検出することができる。図７に戻り、次に変数ｎに配列の大きさ、すなわちノードの数を代入し、変数iに初期値０を代入したうえ（Ｓ５４）、ノード配列の最初（ｉ＝０）から、上述のような切り出し可能な部分グラフの検出および切り出し処理を行う。具体的には、変数ｖｉｃｔｉｍに対象ノードの識別番号を代入し（Ｓ５６）、変数ｖｉｃｔｉｍを引数として検出および切り出し処理の関数を呼び出す（Ｓ５８）。検出および切り出し処理の関数の詳細な手順は後述するが、概ね上述のとおり、変数ｖｉｃｔｉｍが示すノードを入口ノードとする切り出し可能な部分グラフの有無を確認し、検出された場合は必要に応じて一部を切り出し新たなＣＦＧを生成したうえ、新たなノードに置き換える。
【００４５】
次に、Ｓ５８の切り出し可能な部分グラフの検出および切り出し処理の結果、ＣＦＧが変化したかを確認する（Ｓ６０）。ＣＦＧが変化している場合は（Ｓ６０のＹ）、Ｓ５８においてノードの置き換えを行った結果、変数ｖｉｃｔｉｍが示すノードを入口とする最小の切り出し可能な部分グラフがさらに発生した可能性があるため、そのような部分グラフの検出および切り出し処理を行う（Ｓ５８）。Ｓ５８、Ｓ６０を、それ以上ＣＦＧが変化しなくなるまで行い、変化しなくなったら（Ｓ６０のＮ）、変数ｉをインクリメントして、ノード配列における次のノードを入口とした切り出し可能部分グラフの検出および切り出し処理を行う（Ｓ６２、Ｓ６４のＹ、Ｓ５６、Ｓ５８、Ｓ６０）。
【００４６】
上記の処理をｎ個の全ノードに対して行ったら（Ｓ６４のＮ）、元のＣＦＧの合計サイズがキャッシュブロックのサイズ制限を超えているか否かを確認する（Ｓ６６）。超えていたら（Ｓ６６のＹ）、好適な部分でノードの切り出しを行う。具体的には、元のＣＦＧの出口ノード以外のノードの識別番号と出口ノードの識別番号とを引数として切り出し処理の関数を呼び出す（Ｓ６８）。切り出し処理の関数の詳細な手順は後述する。以上の処理により、キャッシュブロックのサイズ制限を超えないサイズのＣＦＧの集合が生成できる。
【００４７】
図９は、図７のＳ５８で呼び出される、部分グラフ検出および切り出し処理の関数における処理手順を示す。この関数は上述のとおり、引数で指定されたノードを入口とする最小の切り出し可能な部分グラフを検出すること、検出した部分グラフの合計サイズがキャッシュブロックのサイズ制限を超過しないように一部のノードの切り出しを行い、新たなＣＦＧを生成すること、切り出し可能な部分グラフを新たなノードに置き換えること、を行う。本関数は、部分グラフ検出部１０８、切り出し部１１０、およびノード置換部１１２によって実行される。
【００４８】
引数で指定されたノードの識別番号を「ｅｎｔｒｙ＿ｎｏｄｅ」とすると、まずｅｎｔｒｙ＿ｎｏｄｅが示すノードのポストドミネータのうち、ｅｎｔｒｙ＿ｎｏｄｅが示すノードから一直線に並んだ形となっていない、最も近いノードを求め、当該ノードの識別番号を「ｅｘｉｔ＿ｎｏｄｅ」とする（Ｓ７０、Ｓ７２のＮ、Ｓ７４、Ｓ７６）。
【００４９】
ここで、ＣＦＧの入口ノードから、あるノードｘへ至る全ての経路上にノードｙが存在するとき、ｙはｘをドミネートする、あるいはｙはｘのドミネータであるという。また、ＣＦＧ内のあるノードｘからＣＦＧの出口ノードへ至る全ての経路上にノードｙが存在するとき、ｙはｘのポストドミネータであるという。ただし、ノードｘから出口ノードに至る経路が存在しない場合は、ノードｘから到達可能なノードのうちＣＦＧの入口ノードから最も遠いノードからＣＦＧの出口ノードへ至る経路があるものとしてポストドミネータを求める。ドミネータ、ポストドミネータなどの探索は、ＣＦＧの解析などにおいて一般的に用いられる手法を適用することができる。
【００５０】
ｅｘｉｔ＿ｎｏｄｅの決定は具体的には次の手順を踏む。まず変数ｌａｓｔ＿ｖｉｓｉｔに変数ｅｎｔｒｙ＿ｎｏｄｅの値を、変数ｅｘｉｔ＿ｎｏｄｅに当該ノードの直近のポストドミネータの識別番号を代入する（Ｓ７０）。このとき変数ｅｘｉｔ＿ｎｏｄｅに代入すべきノードがない場合は、切り出し可能な部分グラフが見つからない、と判断し、部分グラフ検出および切り出し処理の関数を抜ける（Ｓ７２のＹ）。
【００５１】
変数ｅｘｉｔ＿ｎｏｄｅに代入すべきノードが存在した場合で（Ｓ７２のＮ）、変数ｌａｓｔ＿ｖｉｓｉｔが示すノードの次のノードが変数ｅｘｉｔ＿ｎｏｄｅが示すノードのみである場合は（Ｓ７４のＹ）、変数ｅｎｔｒｙ＿ｎｏｄｅが示すノードと現状の変数ｅｘｉｔ＿ｎｏｄｅが示すノードとが一直線上にある。したがって、変数ｌａｓｔ＿ｖｉｓｉｔに変数ｅｘｉｔ＿ｎｏｄｅを代入し、変数ｅｘｉｔ＿ｎｏｄｅに、元の変数ｅｘｉｔ＿ｎｏｄｅのノードの直近のポストドミネータの識別番号を代入することにより、変数ｅｘｉｔ＿ｎｏｄｅの候補を出口に近づける（Ｓ７６）。
【００５２】
そしてＳ７２、Ｓ７４の確認を行い、上記と同様の結果であればＳ７６の処理を行う、というループを繰り返す。そして変数ｌａｓｔ＿ｖｉｓｉｔが示すノードの次のノードの数が１でないか次のノードが変数ｅｘｉｔ＿ｎｏｄｅが示すノードでなくなった場合に（Ｓ７４のＮ）、Ｓ７６の変数ｅｘｉｔ＿ｎｏｄｅの更新処理から抜ける。ここまでの処理により、変数ｅｎｔｒｙ＿ｎｏｄｅが示すノードから直線状に連なるノードが存在する場合に、変数ｅｘｉｔ＿ｎｏｄｅが示すノードを直線の範囲外に移動させたことになる。この探索において、変数ｅｘｉｔ＿ｎｏｄｅが示すノードは常にポストドミネータとなっているため、変数ｅｘｉｔ＿ｎｏｄｅが示す最終的なノードは、求めようとする部分グラフの唯一の出口となっている。したがって、当該ノードを切り出し可能な部分グラフの出口ノードとして決定する。
【００５３】
次に、変数ｅｎｔｒｙ＿ｎｏｄｅが示すノードから、上記処理で決定した出口ノードを途中で通過することなく当該出口ノードへ至る全ての経路において、変数ｅｎｔｒｙ＿ｎｏｄｅが示すノードにドミネートされていないノードが出口ノードを除いて存在するか確認する（Ｓ７８）。出口ノードを除く全てのノードが変数ｅｎｔｒｙ＿ｎｏｄｅが示すノードにドミネートされている場合は（Ｓ７８のＹ）、当該ノードが、検出しようとする部分グラフの唯一の入口である。したがって、当該ノードを切り出し可能な部分グラフの入口ノードと判断し、ドミネートされている全ノードの識別番号を、「ノード集合」の配列とする（Ｓ８０）。検出した切り出し可能な部分グラフに含まれるノードは全て、ノード集合の配列に属することになる。
【００５４】
一方、上記経路において変数ｅｎｔｒｙ＿ｎｏｄｅが示すノードにドミネートされていないノードが存在する場合は、変数ｅｎｔｒｙ＿ｎｏｄｅが示すノードは入口ノードとならない。したがって、当該ノードを入口とする切り出し可能な部分グラフはない、と判断し、部分グラフ検出および切り出し処理の関数を抜ける（Ｓ７８のＮ）。またノード集合の数が１以下であった場合、すなわち入口ノード以外に切り出し可能な部分グラフを構成するノードがなかった場合は、当該部分を新たなノードに置き換える意味がないため、部分グラフ検出および切り出し処理の関数を抜ける（Ｓ８２のＹ）。
【００５５】
ノード集合の数が２以上であった場合は（Ｓ８２のＮ）、ノード集合に属するノードの合計サイズがキャッシュブロックのサイズ制限を超えているか否かを確認する（Ｓ８４）。超えている場合は（Ｓ８４のＹ）、ノード集合の配列と出口ノードの識別番号を引数として、好適な部分でノードの切り出しを行う切り出し処理の関数を呼び出すことによりサイズ制限の超過を解消する（Ｓ８６）。元来サイズ制限を超えていない場合（Ｓ８４のＮ）、および切り出し処理によりサイズ超過を解消した場合（Ｓ８６）、ノード置換処理の関数を呼び出して、切り出し可能な部分グラフを１つのノードに置き換える（Ｓ８８）。
【００５６】
図１０は、図７のＳ６８および図９のＳ８６で呼び出される、ノードの切り出し処理の関数における処理手順を示す。この関数は上述のとおり、引数で与えられたノード集合の合計サイズがサイズ制限を超過しないように一部のノードを切り出し、新たなＣＦＧを生成する。本関数は、切り出し部１１０によって実行される。まず指定されたノード集合の中で、直線に並んだノード列の有無を確認する（Ｓ９０）。この処理は実際には、ノード集合の中から、（１）前のノードの数が１つ、（２）次のノードの数が１つ、（３）前のノードの次のノードの数が１つ、（４）ＣＦＧの入口ノードや出口ノードでない、という条件を全て満たすノードｘを検出することによって実現する。
【００５７】
そのようなノードｘが存在する場合は（Ｓ９０のＹ）、ノードｘの識別番号を引数として、直線部分の特定、切り出し、および置換処理を行う関数を呼び出す（Ｓ９２）。この関数は、ノードの直線部分を特定して、当該直線部分の合計サイズがサイズ制限を超過する場合は一部を切り出して新たなＣＦＧを生成したうえで、１つのノードに置き換える。当該関数の詳細な手順は後述する。指定されたノード集合に直線部分がなくなるまで当該関数による処理を繰り返し（Ｓ９０のＹ、Ｓ９２）、直線部分がなくなったら（Ｓ９０のＮ）、ノード集合の合計サイズがキャッシュブロックのサイズ制限を超えるか否かを確認する（Ｓ９４）。この切り出し処理の関数が呼び出された時点では、引数であるノード集合の合計サイズがサイズ制限を超えているが、Ｓ９２において直線部分の一部が切り出され、合計サイズが削減されている可能性があるため、Ｓ９４において再度確認を行う。
【００５８】
直線部分の切り出しにより、合計サイズがサイズ制限内となっていれば、そのまま処理を抜ける（Ｓ９４のＮ）。サイズ制限を超えている場合は（Ｓ９４のＹ）、ノード集合の中から、例えば最もサイズの大きなノードなど、適切なノードを１つ選択し（Ｓ９６）、当該ノードの識別番号を引数として指定ノード切り出し処理の関数を呼び出す（Ｓ９８）。この関数は、引数で指定されたノードを切り出し、新たなＣＦＧを生成する。詳細な手順は後述する。
【００５９】
図１１は図１０のＳ９２で呼び出される、直線部分の特定、切り出し、および置換処理の関数における処理手順を示す。この関数は上述のとおり、引数で指定されたノードを含む、直線に並んだノード列の範囲を特定する。そして、当該ノード列の合計サイズがキャッシュブロックのサイズ制限を超過している場合は、一部を切り出して新たなＣＦＧを生成する。さらに直線部分のノード列全体を新たな１つのノードに置き換える。本関数は切り出し部１１０、ノード置換部１１２によって実行される。
【００６０】
まず引数で指定されたノードは、直線に並んだノード列に含まれるいずれかのノードであるため、当該ノードを含む直線部分を特定する。具体的には、引数であるノードの識別番号「ｖｉｃｔｉｍ」に対し、当該ノードの１つ前のノードの識別番号を変数「ｈｅａｄ」に代入する（Ｓ１００）。変数ｈｅａｄが示すノードが直線状のノード列の途中であれば（Ｓ１０２のＹ）、変数ｈｅａｄを、元の変数ｈｅａｄが示すノードの一つ前のノードの識別番号とする（Ｓ１０４）。Ｓ１０２とＳ１０４を繰り返し、変数ｈｅａｄが直線状のノード配列の途中でなくなったらループを抜ける（Ｓ１０２のＮ）。これにより、直線状のノード列のうち、最も入口に近いノードの識別番号で変数ｈｅａｄが確定する。
【００６１】
次に「候補ノードリスト」の配列に変数ｈｅａｄをまず代入し、変数「ｐｔｒ」に、変数ｈｅａｄが示すノードの次のノードの識別番号を代入する（Ｓ１０６）。そして変数ｐｔｒが示すノードが直線状のノード列の途中であれば（Ｓ１０８のＹ）、候補ノードリストの配列に変数ｐｔｒの値を追加したうえ、変数ｐｔｒを、元の変数ｐｔｒが示すノードの次のノードの識別番号とする（Ｓ１１０）。Ｓ１０８とＳ１１０を繰り返し、変数ｐｔｒが直線状のノード列の途中でなくなったらループを抜ける（Ｓ１０８のＮ）。これにより、直線状のノード列を構成するノードのうち、最後のノードを除く全ノードの識別番号が候補ノードリストの配列に入り、最後のノードの識別番号で変数ｐｔｒが確定する。
【００６２】
次に後の処理のために変数ｐｔｒの値を変数ｅｘｉｔ＿ｎｏｄｅに代入する（Ｓ１１２）。そして、候補ノードリストの配列に属するノードの合計サイズがキャッシュブロックのサイズ制限を超えているか否かを確認する（Ｓ１１４）。超えている場合は（Ｓ１１４のＹ）、候補ノードリストの配列を引数として、直線状のノード列の一部の切り出しを行う直線部分切り出し処理の関数を呼び出すことにより、サイズ制限の超過を解消する（Ｓ１１６）。元来サイズ制限を超えていない場合（Ｓ１１４のＮ）、および切り出し処理によりサイズ超過を解消した場合（Ｓ１１６）、ノード置換処理の関数を呼び出し、候補ノードリストの配列に属するノードを新たな１つのノードに置き換える（Ｓ１１８）。
【００６３】
図１２は図１１のＳ１１６で呼び出される、直線部分切り出し処理の関数における処理手順を示す。この関数は、図１１の処理で特定した直線状のノード列のうち、最後のノード以外のノードの識別番号からなる候補ノードリストの配列を引数として、当該直線状のノード列の一部を切り出し、新たなＣＦＧを生成することにより、直線状のノード列のサイズ超過を解消する。同処理で切り出す対象は直線部分であるため、サイズ制限を超過しない範囲でできるだけ大きいサイズでの切り出しを行う。これにより、キャッシュブロックが細分化されることによる上述したオーバヘッドの発生を抑制できる。本関数は、切り出し部１１０およびノード置換部１１２によって実行される。
【００６４】
まず、引数で指定された直線状のノード列のうち、サイズが最大のノードの識別番号を変数「ｃｏｒｅ」に代入する（Ｓ１２０）。次に変数ｃｏｒｅが示すノードを始点として、切り出す範囲の前方伸長、または後方伸長が可能かを確認する（Ｓ１２２）。前方伸長が可能とは、変数ｃｏｒｅが示すノードが候補ノードリストで指定されるノード集合の先頭のノードでなく、かつ、変数ｃｏｒｅが示すノードとその前のノードの合計サイズがキャッシュブロックのサイズ制限を超えないことが条件となる。後方伸長が可能とは、変数ｃｏｒｅが示すノードが候補ノードリストで指定されるノード集合の末尾のノードでなく、かつ、変数ｃｏｒｅが示すノードとその次のノードの合計サイズがキャッシュブロックのサイズ制限を超えないことが条件となる。
【００６５】
前方伸長のみが可能であれば（Ｓ１２２のＹ、Ｓ１２４の「前方伸長のみ可能」）、変数ｃｏｒｅのノードとその前のノードとを１つのノードとするようにノード置換処理の関数を呼び出す（Ｓ１２８）。後方伸長のみが可能であれば（Ｓ１２２のＹ、Ｓ１２４の「後方伸長のみ可能」）、変数ｃｏｒｅのノードとその次のノードとを１つのノードとするようにノード置換処理の関数を呼び出す（Ｓ１３０）。前方伸長および後方伸長のいずれも可能であれば（Ｓ１２２のＹ、Ｓ１２４の「両方可能」）、前のノードのサイズが次のノードのサイズより大きければ（Ｓ１２６のＹ）、前のノードと１つのノードとするようにノード置換処理の関数を呼び出す（Ｓ１２８）。次のノードのサイズの方が大きければ（Ｓ１２６のＮ）、次のノードと１つのノードとするようにノード置換処理の関数を呼び出す（Ｓ１３０）。すなわち、前後に連なるノードのうち大きいサイズのノードとまとめて１つのノードとする。
【００６６】
Ｓ１２２、Ｓ１２４、Ｓ１２６、Ｓ１２８、Ｓ１３０の処理を、前方伸長、後方伸長のいずれも不可能となるまで繰り返す。これにより、変数ｃｏｒｅが示すノードを起点に、キャッシュブロックのサイズ制限を超えない範囲で最大サイズのまとまりを作り、それを１つのノードに置き換えることができる。ここではノード置換処理の関数によって、置き換えられた１つのノードの識別番号が変数ｃｏｒｅに代入される。前方伸長、後方伸長のいずれも不可能となったら（Ｓ１２２のＮ）、置き換えられた１つのノードの識別番号を示す変数ｃｏｒｅを引数として、指定ノード切り出し処理の関数を呼び出す（Ｓ１３２）。この関数により、当該ノードが切り出され、新たなＣＦＧが生成される。
【００６７】
次に、候補ノードリストの配列に属するノードの合計サイズが、まだキャッシュブロックのサイズ制限を超過するか否かを確認する（Ｓ１３４）。なお上述の切り出し処理では、ノードを切り出した後も元のノードの識別番号はそのまま残し、各ノードに含まれる基本ブロックのリストあるいは基本ブロックの中身である命令列が更新されるようにする。従って、サイズ超過の確認には、引数である候補ノードリストの配列をそのまま使用することができる。
【００６８】
合計サイズがサイズ制限を超過する場合は（Ｓ１３４のＹ）、候補ノードリストの配列に属するノードのうち、その時点でサイズが最大のノードの識別番号を変数ｃｏｒｅに代入し、上述と同様の処理、すなわちサイズ制限を超過しない最大限のノード列を１つにまとめ、切り出しを行う処理を繰り返す（Ｓ１２０〜Ｓ１３２）。以上の処理を、候補ノードリストが示すノードの合計サイズがサイズ制限を超過しなくなるまで繰り返す（Ｓ１３４のＹ、Ｓ１２０〜Ｓ１３２）。超過が解消されたら（Ｓ１３４のＮ）、処理を終了する。
【００６９】
図１３は図１０のＳ９８および図１２のＳ１３２で呼び出される指定ノード切り出し処理の関数における処理手順を示す。この関数は、引数で指定されたノードを切り出し、新たなＣＦＧへ移す。本関数は切り出し部１１０によって実行される。まず、新たなＣＦＧの構造体を準備する（Ｓ１４０）。次に引数で指定されたノードの次のノードの数が１か否かを確認する（Ｓ１４２）。引数で指定されたノードが、それまでの処理で複数のノードを１つにまとめたものである場合は、必ず次の出口ノードを１つとしている。したがって次のノードの数が１でないということは、引数で指定されたノードが、複数の基本ブロックをまとめたものではなく、元々存在する１つの基本ブロックであることを意味している。また、次のノードの数が１でないということは、指定されたノードの末尾に分岐命令を含むことを意味する。
【００７０】
このような場合は（Ｓ１４２のＮ）、まず準備した新たなＣＦＧの構造体に、新たな基本ブロックの識別番号をエントリする（Ｓ１４４）。そして指定されたノードに対応する元の基本ブロックに含まれる命令列のうち分岐命令以外の命令列を、当該新たな基本ブロックの命令列として移動する（Ｓ１４６）。このとき、元のＣＦＧの指定されたノードに対応する基本ブロックにおいては、分岐命令以外の命令列がない状態となるため、その直前に新たなＣＦＧを呼び出す命令列を挿入する（Ｓ１４８）。
【００７１】
一方、指定されたノードの次のノードの数が１である場合、すなわち少なくとも次のノードまで直線状のノード列であった場合（Ｓ１４２のＹ）、指定されたノードに含まれる全基本ブロックを、それぞれ新たなノードとして、新たなＣＦＧの構造体に移す（Ｓ１５０）。このとき元のＣＦＧでは、指定されたノードが基本ブロックを１つも含まない状態となる。そこで元のＣＦＧにおける指定されたノードに、新たな基本ブロックの識別番号をエントリする（Ｓ１５２）。そして当該新たな基本ブロックの命令列として、新たなＣＦＧを呼び出す命令列と、次のノードへのジャンプ命令を記述する（Ｓ１５４）。Ｓ１４８、Ｓ１５４の処理の後、このようにして生成した新たなＣＦＧを出力結果に追加する（Ｓ１５６）。
【００７２】
図１４は図９のＳ８８、図１１のＳ１１８、図１２のＳ１２８、Ｓ１３０で呼び出されるノード置換処理の関数における処理手順を示す。この関数は、引数で指定された「ノードリスト」の配列に含まれるノードを１つのノードに置き換える。本関数はノード置換部１１２によって実行される。まずＣＦＧに新たなノードの識別番号をエントリする（Ｓ１６０）。次に、ＣＦＧの構造体に含まれる、ノードの相対的な位置、すなわちノード間のつながりを表す情報において、ノードリストの配列に含まれるノードを経路としていたものを、それに代わり新たなノードを経路とするように更新する（Ｓ１６２）。例えば図５において、ノードＢ３の次のノードはノードＢ５であるが、この指定をノードＢ５’に置き換える。次に、ノードリストの配列に含まれるノードの基本ブロックのリストを全てまとめて、新たなノードの基本ブロックのリストとすることで、元の複数のノードを新たなノードの構成要素とする（Ｓ１６４）。
【００７３】
以上述べた本実施の形態によれば、コンパイルの対象である関数からＣＦＧを作成し、１つのノードを唯一の入口とし、１つのノードを唯一の出口とする最小の切り出し可能な部分グラフを検出する。そして当該切り出し可能な部分グラフに着目して、そのサイズがキャッシュブロックのサイズ制限を超えている場合は、当該部分グラフの中から切り出す対象のノードを決定する。決定した切り出し対象は別の新たなＣＦＧとし、元のＣＦＧには新たなＣＦＧを呼び出す命令を代入する。最終的にはＣＦＧ単位でキャッシュブロックとなるオブジェクトコードを生成する。
【００７４】
これにより、関数の一部をサブルーチンとして切り出すのと同様の切り出しを行うことができ、キャッシュブロックを跨いだ関数の呼び出しおよび戻り処理が、切り出し可能な部分グラフを構成する命令列内で閉じる。結果的に、関数呼び出しおよび戻り処理の管理が簡素化でき、リンクスタックを用いて容易に処理を遂行することができる。
【００７５】
また、直線状に並んだノード列は、キャッシュブロックのサイズ制限を超えない範囲でまとめて切り出す。これにより、小さいサイズのキャッシュブロックが多数ある場合に比べ、プログラム処理中に参照先のキャッシュブロックを変更せずに連続した処理を行える頻度が高くなる。結果的に、キャッシュブロックを跨いだ関数の呼び出しや戻り処理に起因して発生するオーバヘッドを軽減することができる。
【００７６】
以上の処理は、コンパイラによって全て自動で行えるため、プログラム上で分割箇所を設定したり、高速アクセスに有利となるようにプログラムの構造を検討したり、といったプログラマが行う作業の負荷を軽減することができる。また、元のＣＦＧの生成や、分割結果のＣＦＧに基づくキャッシュブロックの生成などは、既存の技術を適用することができるため、導入コストを抑えることができる
【００７７】
以上、本発明を実施の形態をもとに説明した。上記実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００７８】
例えば、ノードの切り出しを行う際、以前に切り出したノードの呼び出しを含むノードはできるだけ切り出さないようにしてもよい。これは、関数呼び出し時、キャッシュブロックを跨いで呼び出した関数がさらにキャッシュブロックを跨いで別の関数を呼び出す、というように、１度の関数呼び出しが複数のキャッシュブロックを跨いだ関数呼び出しに派生するのをできるだけ防ぐためである。図３で示したリンクスタックを利用して関数呼び出しおよび戻り処理の管理をしている場合、リンクスタックの容量を考慮すると、ネスティングが深くならないことが望ましい。
【００７９】
このような態様を実現するためには、切り出し部１１０は、切り出し処理の都度、基本ブロックごとに切り出し回数をカウントしてメモリ１０２または図示しないレジスタに記憶させておく。そして、図１０のＳ９６や図１２のＳ１２８、Ｓ１３０などにおいて切り出し候補のノードを決定する際、ノードに含まれる基本ブロックのそれまでの切り出し回数を参照して、切り出し回数の少ない基本ブロックを含むノードを優先的に切り出し候補とするようにする。
【図面の簡単な説明】
【００８０】
【図１】本実施の形態で生成したプログラムを処理する情報処理装置の構造例を示す図である。
【図２】図１の情報処理装置においてローカルメモリとメインメモリに格納されるデータの構成を模式的に示す図である。
【図３】図１の情報処理装置においてキャッシュブロック間の関数呼び出しおよび戻り処理を実現する手法の例を説明するための図である。
【図４】本実施の形態において、プログラムをコンパイルするコンパイラの構造を示す図である。
【図５】本実施の形態で生成するＣＦＧの例を示す図である。
【図６】本実施の形態において分割処理が進捗する際のＣＦＧの変化の例を模式的に示す図である。
【図７】本実施の形態における分割部が行う分割処理の手順を示すフローチャートである。
【図８】ポストオーダー順を説明するための図である。
【図９】本実施の形態における部分グラフ検出および切り出し処理の関数の処理手順を示すフローチャートである。
【図１０】本実施の形態におけるノードの切り出し処理の関数の処理手順を示すフローチャートである。
【図１１】本実施の形態における直線部分の特定、切り出し、および置換処理の関数の処理手順を示すフローチャートである。
【図１２】本実施の形態における直線部分切り出し処理の関数の処理手順を示すフローチャートである。
【図１３】本実施の形態における指定ノード切り出し処理の関数の処理手順を示すフローチャートである。
【図１４】本実施の形態におけるノード置換処理の関数の処理手順を示すフローチャートである。
【符号の説明】
【００８１】
１００  コンパイラ、  １０２  メモリ、  １０４  ＣＦＧ生成部、  １０６  分割部、  １０８  部分グラフ検出部、  １２０  切り出し部、  １１２  ノード置換部、  １１４  コード生成部。
【図１】
0005244421.tif 000002
【図２】
0005244421.tif 000003
【図３】
0005244421.tif 000004
【図４】
0005244421.tif 000005
【図５】
0005244421.tif 000006
【図６】
0005244421.tif 000007
【図７】
0005244421.tif 000008
【図８】
0005244421.tif 000009
【図９】
0005244421.tif 000010
【図１０】
0005244421.tif 000011
【図１１】
0005244421.tif 000012
【図１２】
0005244421.tif 000013
【図１３】
0005244421.tif 000014
【図１４】
0005244421.tif 000015