(57)【特許請求の範囲】
【請求項１】
少なくとも１つのコードを含むプログラム実行単位であるノードと、該ノードの制御の流れを示す情報とを含むプログラムグラフの入力を受付けるグラフ入力受付手段と、
任意の区間における開始時に実行されたノードであるスタートノードと、終了時に実行されたノードであるゴールノードと、前記スタートノードから前記ゴールノードまでの実行時間とを含む実行ログの入力を受付けるログ入力受付手段と、
前記グラフ入力受付手段が受付けた前記プログラムグラフと、前記ログ入力受付手段が受付けた前記実行ログに含まれる前記スタートノードと前記ゴールノードと前記実行時間とに基づいて、前記区間内に実行された可能性のあるノードの範囲を表す経路範囲情報を実行情報として算出する経路範囲情報算出手段と、
を備えたことを特徴とする実行情報推定装置。
【請求項２】
前記ログ入力受付手段が受付けた前記実行ログに含まれる前記スタートノードと前記ゴールノードと前記実行時間と、前記経路範囲情報算出手段が算出した前記経路範囲情報とに基づいて、前記区間内に実行されたノードであるドミナントノードの範囲を表すドミナント情報を算出するドミナント情報算出手段をさらに備えたことを特徴とする請求項１に記載の実行情報推定装置。
【請求項３】
前記ドミナント情報算出手段は、前記経路範囲情報算出手段が算出した前記経路範囲情報に含まれるノードから選択したノードを前記プログラムグラフから削除したときに、前記スタートノードと前記ゴールノードとを前記実行時間で結ぶ経路が存在しない場合に、前記選択したノードを前記ドミナントノードとすることを特徴とする請求項２に記載の実行情報推定装置。
【請求項４】
前記経路範囲情報算出手段が算出した前記経路範囲情報と、前記ドミナント情報算出手段が算出した前記ドミナント情報とに基づいて、ノードの実行頻度の情報を含むプロファイル情報を算出するプロファイル情報算出手段をさらに備えたことを特徴とする請求項２または３に記載の実行情報推定装置。
【請求項５】
前記プロファイル情報算出手段は、前記ドミナント情報に含まれるノードの実行頻度の値を、前記ドミナントノードに含まれないが前記経路範囲情報に含まれるノードの実行頻度の値より大きく設定して前記プロファイル情報を算出することを特徴とする請求項４に記載の実行情報推定装置。
【請求項６】
前記経路範囲情報算出手段は、前記プログラムグラフに含まれる関数の呼び出し元ノードと、該呼び出し元ノードに対応する関数の戻り先ノードとを有向辺で短絡し、呼び出し元の関数に戻る処理を表すノードと、該呼び出し元の関数に戻る処理を表すノードに対応する関数の戻り先ノードとを結ぶ有向辺を削除した情報である短絡グラフを作成し、該短絡グラフ上で前記スタートノードと前記ゴールノードとを前記実行時間以内で結ぶ経路を前記経路範囲情報として算出し、算出した前記経路範囲情報に含まれるノードから呼び出される関数または戻り先となる関数内において、前記スタートノードと前記ゴールノードとを前記実行時間以内で結ぶ経路を算出して前記経路範囲情報に追加することを特徴とする請求項１に記載の実行情報推定装置。
【請求項７】
前記ログ入力受付手段は、任意の区間における前記スタートノードと前記ゴールノードと前記実行時間と関数の呼び出し元の履歴の情報であるスタック情報とを含む実行ログの入力を受付け、
前記経路範囲情報算出手段は、前記グラフ入力受付手段が受付けた前記プログラムグラフと、前記ログ入力受付手段が受付けた前記実行ログに含まれる前記スタートノードと前記ゴールノードと前記実行時間と前記スタック情報とに基づいて、前記経路範囲情報を算出することを特徴とする請求項１〜６のいずれか１つに記載の実行情報推定装置。
【請求項８】
前記ログ入力受付手段は、任意の区間における前記スタートノードと前記ゴールノードと前記実行時間と前記区間の開始時における関数の呼び出し元の履歴の情報であるスタート時スタック情報とを含む実行ログの入力を受付け、
前記経路範囲情報算出手段は、前記プログラムグラフに含まれる関数の呼び出し元ノードと、該呼び出し元ノードに対応する関数の戻り先ノードとを有向辺で短絡し、呼び出し元の関数に戻る処理を表すノードと、該呼び出し元の関数に戻る処理を表すノードに対応する関数の戻り先ノードとを結ぶ有向辺を削除した情報である短絡グラフを作成し、該短絡グラフ上で前記スタートノードと前記ゴールノードとを前記実行時間以内で結ぶ経路を前記経路範囲情報として算出し、算出した前記経路範囲情報に含まれるノードからの戻り先となる関数を前記スタート時スタック情報から選択し、選択した関数内において前記スタートノードと前記ゴールノードとを前記実行時間以内で結ぶ経路を算出して前記経路範囲情報に追加することを特徴とする請求項７に記載の実行情報推定装置。
【請求項９】
前記ログ入力受付手段は、任意の連続する区間における前記スタートノードと前記ゴールノードと前記実行時間とを含む実行ログの入力を受付け、
前記経路範囲情報算出手段は、前記連続する区間のうち前の区間の終了時点における関数の呼び出し元の候補であるスタック候補情報を算出し、該スタック候補情報を、前記前の区間の次の区間の前記スタート時のスタック情報として前記経路範囲情報を算出することを特徴とする請求項８に記載の実行情報推定装置。
【請求項１０】
前記ログ入力受付手段は、任意の区間における前記スタートノードと前記ゴールノードと前記実行時間と前記区間の開始時における関数の呼び出し元の履歴の情報であるスタート時スタック情報と前記区間の終了時における関数の呼び出し元の履歴の情報であるゴール時スタック情報とを含む実行ログの入力を受付け、
前記経路範囲情報算出手段は、前記ログ入力受付手段が受付けた前記実行ログに含まれる前記スタートノードから、前記スタート時スタック情報に含まれるノード、および、前記ゴール時スタック情報に含まれるノードを経由し、前記ゴールノードまでを結ぶ経路を算出し、算出した経路を前記グラフ入力受付手段が受付けた前記プログラムグラフに含まれる関数ごとに分解して少なくとも１つの経路区間を算出し、該経路区間ごとに、前記スタートノードと前記ゴールノードとを前記実行時間以内で結ぶ経路を前記経路範囲情報として算出することを特徴とする請求項７に記載の実行情報推定装置。
【請求項１１】
少なくとも１つのコードを含むプログラム実行単位であるノードと、該ノードの制御の流れを示す情報とを含むプログラムグラフの入力を受付けるグラフ入力受付手順と、
任意の区間における開始時に実行されたノードであるスタートノードと、終了時に実行されたノードであるゴールノードと、前記スタートノードから前記ゴールノードまでの実行時間とを含む実行ログの入力を受付けるログ入力受付手順と、
前記グラフ入力受付手順が受付けた前記プログラムグラフと、前記ログ入力受付手順が受付けた前記実行ログに含まれる前記スタートノードと前記ゴールノードと前記実行時間とに基づいて、前記区間内に実行された可能性のあるノードの範囲を表す経路範囲情報を実行情報として算出する経路範囲情報算出手順と、
をコンピュータに実行させる実行情報推定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、プログラムの実行ログからプログラムの実行情報を推定する実行情報推定装置および実行情報推定プログラムに関するものである。
【背景技術】
【０００２】
従来から、プログラムの性能チューニングのための手法として、プロファイルを利用した方法が広く知られている。プロファイルとは、プログラムの実行時に実行ログの一部を収集することにより、プログラムの実行時の情報の概略を利用者に提示するための情報をいう（以下、収集した実行ログのことを間欠実行ログ、または単に実行ログという）。例えば、ＵＮＩＸ（登録商標）などにおけるプロファイルツールの１つであるgprofを用いると、実行時の関数呼び出し頻度や、各関数の呼び出し元の関数などの情報を得ることができる。
【０００３】
これらの情報から、プログラムのホットスポットと呼ばれる最も頻繁に実行されるコード等を検出することができる。プログラムの性能チューニングを行う場合、このホットスポットを重点的にチューニングすることが最も効果的なため、プロファイル情報を効率的に生成する技術に対する要求は大きい。
【０００４】
一般に、実行ログの収集方式は、侵襲収集方式と非侵襲収集方式に大別される。侵襲収集方式とは、プログラムのコードに実行ログ出力のためのプローブを埋めこむことにより実行情報を得る収集方式である。上述のgprofは侵襲収集方式によりプログラムの実行ログを収集している。
【０００５】
侵襲収集方式では、プログラムの実行ファイル自体を再作成するため、当該プログラム自身を用いて実行ログの収集を行うことができる。そのためＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）やハードウェアなどに監視を行うための仕組みを作り込む必要がないという利点がある。また侵襲収集方式では、例えばプログラムの分岐や手続きの呼び出しに相当する部分全てにプローブを挿入することにより、想定外のポインタ演算等に起因する異常な動作を除くと、プログラムの実行情報を完全に再構成することができる。
【０００６】
しかし実際には、全ての分岐を決定できるようにプローブを挿入すると実行ログ収集のオーバーヘッドが過大となるため、完全な再構成性を犠牲にして、オーバーヘッドを小さくする場合がある。例えば、上述のgprofでは、関数レベルのプロファイル情報の収集を目的としているため、挿入するプローブが制限されている。このため、関数内の分岐などの詳細なプロファイル情報は得られない。従って、侵襲収集方式の場合であっても、より詳細なレベルのプロファイル情報を得るためには、出力された実行ログにおける制御の流れの追跡が必要となる。
【０００７】
一方、非侵襲収集方式とは、プログラムのコード自体にプローブを埋め込まず、実行時の動作を外部から監視することにより実行情報を得る収集方式のことである。非侵襲収集方式は、ＯＳやハードウェアなどに組み込まれた機能によりプログラムを監視し、所定の間隔で実行ログの記録を行い、間欠実行ログ情報を収集する。
【０００８】
例えば、ソフトウェア開発においてミドルウェアを外部から導入する場合などにおいては、ソースコードの入手が困難なケースが想定される。このようなケースでは、ソースコードにプローブを埋め込む侵襲収集方式が採用できないため、非侵襲収集方式のプロファイル技術が必須となる。非侵襲収集方式においては、収集した実行ログからできるだけ正確な推定実行情報を構成することが求められる。
【０００９】
特許文献１においては、通算実行命令数のカウンタ専用のレジスタを有する特殊なＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を用い、レジスタのカウンタが一定値に達すると割り込みを発生させ、割り込み時点において実行されている命令に関するプログラムカウンタなどの情報を実行ログとして収集する技術が提案されている。
【００１０】
非侵襲収集方式では、プログラム自身を改変しないため、実行時間のオーバーヘッドが小さく、また実際の実行時により近い動作を追跡できるという利点がある。また、ソースコードを入手できず、実行コードのみを入手可能な場合であっても、ＯＳやＣＰＵなどの監視によりプロファイル情報を得ることが可能であるという利点がある。
【００１１】
非侵襲収集方式は、実行ログの収集位置をコード上には指定できないため、収集した実行ログの情報からプログラムの実際の制御の流れを推定する必要がある。上述の特許文献１においては、大量の実行ログ情報の統計的な性質を利用し、個々の命令の実行情報を推定する技術が提案されている。
【００１２】
【特許文献１】特開平１０−２５４７００号公報
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかしながら、特許文献１の方法では、大量の実行ログ情報の統計的な性質を利用しているため、注目するコード領域に関する収集した実行ログが少ない場合に、必ずしも精度の高い実行情報の推定値が得られないという問題があった。
【００１４】
特に、近年、計算機のプロセッサの高速化や記憶領域の大容量化にともない、ソフトウェアの大規模化、複雑化、マルチレイヤ化が進むとともに、例えば携帯電話用ソフトウェアに代表されるように、ソフトウェアの開発サイクルは短くなっており、プログラム開発現場において大規模プログラムの迅速な性能チューニングに対する要求は大きい。
【００１５】
ところが、大規模プログラムの性能解析においては、長時間の性能解析を行ったとしても、必ずしも注目するコード領域全般に対する大量の実行ログ情報が得られるとは限らないため、特許文献１の方法では、精度の高い実行情報の推定値が得られないという問題があった。
【００１６】
また、プログラムの動作がモードにより切り替わるような場合、実行ログを収集するタイミングにより実行モードが異なる可能性があるので、特定の期間に限定したプロファイルを行う必要がある。しかし、この期間が短期間である場合は、当該期間内に収集される間欠実行ログは少数になる。したがって、この場合も、大量の実行ログを必要とする特許文献１の方法では、精度の高い実行情報の推定値が得られないという問題があった。
【００１７】
本発明は、上記に鑑みてなされたものであって、収集した実行ログが少数であっても、精度を低減させずに実行情報を推定することができる実行情報推定装置および実行情報推定プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
上述した課題を解決し、目的を達成するために、本発明は、実行情報推定装置において、少なくとも１つのコードを含むプログラム実行単位であるノードと、該ノードの制御の流れを示す情報とを含むプログラムグラフの入力を受付けるグラフ入力受付手段と、任意の区間における開始時に実行されたノードであるスタートノードと、終了時に実行されたノードであるゴールノードと、前記スタートノードから前記ゴールノードまでの実行時間とを含む実行ログの入力を受付けるログ入力受付手段と、前記グラフ入力受付手段が受付けた前記プログラムグラフと、前記ログ入力受付手段が受付けた前記実行ログに含まれる前記スタートノードと前記ゴールノードと前記実行時間とに基づいて、前記区間内に実行された可能性のあるノードの範囲を表す経路範囲情報を実行情報として算出する経路範囲情報算出手段と、を備えたことを特徴とする。
【００１９】
また、本発明は、上記装置を実行することができる実行情報推定プログラムである。
【発明の効果】
【００２０】
本発明によれば、プログラムグラフと実行ログとから、実行ログが出力された期間において実行された可能性のあるノードの範囲を表す経路範囲情報を実行情報として推定することができる。このため、少なくとも１つのログ出力期間における実行ログが得られればプログラムの実行情報を推定することができるという効果を奏する。
【発明を実施するための最良の形態】
【００２１】
以下に添付図面を参照して、この発明にかかる実行情報推定装置、実行情報推定方法および実行情報推定プログラムの最良な実施の形態を詳細に説明する。
【００２２】
（第１の実施の形態）
第１の実施の形態にかかる実行情報推定装置は、プログラムグラフと実行ログとの入力を受付け、受付けたプログラムグラフと実行ログとから、当該実行ログが出力された期間において実行された可能性のあるノードの経路を表す経路範囲情報を実行情報として推定するものである。
【００２３】
ここで、ノードとは、少なくとも１つのコードを含むプログラムの実行単位をいい、プログラムの分岐や合流が存在しない部分が１つのノードとなる。また、経路範囲情報とは、ログが出力された期間（以下、ログ出力区間という）内に実行された可能性のあるノードの範囲をいう。具体的には、ログ出力区間の開始時に実行されたノード（以下、スタートノードという）と終了時に実行されたノード（以下、ゴールノードという）の間をログ出力区間の実行時間以内で結ぶ実行経路を考えた場合に、通過し得るノード全体の集合のことをいう。
【００２４】
図１は、第１の実施の形態にかかる実行情報推定装置１００の構成を示すブロック図である。同図に示すように、実行情報推定装置１００は、プログラム解析装置１２０と、プログラム実行装置１３０と、実行ログ収集装置１４０と、実行情報出力装置１５０と連動して、プログラム記憶部１３１に記憶されたプログラムを実行したときのプログラムの実行情報を推定して出力するものである。
【００２５】
プログラム記憶部１３１は、プログラムのコードを、ソースコード１３１ａ、およびソースコード１３１ａをコンパイルして得られるオブジェクトコード１３１ｂ、およびオブジェクトコード１３１ｂをリンクして得られる実行コード１３１ｃの形式で格納する記憶手段であり、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）、光ディスク、メモリカードなどの一般的に利用されているあらゆる記憶手段により構成することができる。
【００２６】
プログラム解析装置１２０は、オブジェクトコード１３１ｂを入力し、ノードの制御の流れを表した有向グラフであるプログラムグラフをプログラムグラフ記憶部１２１に出力するものである。
【００２７】
通常、プログラムは、実行コード１３１ｃとして実行される。また、ソースコード１３１ａをコンパイルすることにより、オブジェクトコード１３１ｂが得られ、このオブジェクトコード１３１ｂをリンクすることにより実行コード１３１ｃが得られる。また実行コード１３１ｃを、逆アセンブルすることにより、オブジェクトコード１３１ｂを得ることもできる。従って、プログラム解析装置１２０の入力は、オブジェクトコード１３１ｂに限るものではなく、ソースコード１３１ａ、オブジェクトコード１３１ｂ、実行コード１３１ｃのいずれを入力するように構成してもよい。
【００２８】
プログラムグラフ記憶部１２１は、プログラム解析装置１２０がプログラムを解析して出力したプログラムグラフを格納する記憶手段である。プログラムグラフ記憶部１２１は、ＨＤＤ、光ディスク、メモリカードなどの一般的に利用されているあらゆる記憶手段により構成することができる。図２は、プログラムグラフ記憶部１２１に格納されたプログラムグラフの構成要素を示す説明図である。
【００２９】
プログラムグラフは、ノードの間を分岐や合流、あるいは関数の呼び出し（ＣＡＬＬ）、関数からの戻り（ＲＥＴＵＲＮ）を表す有向辺で結んだ有向グラフである。プログラムグラフのノードは、図２に示すように、［ENTRY］、［EXIT］、［BRANCH］、［JOIN］、［CALL］、［CALL_BACK］の６種類の構成要素を含んでいる。
【００３０】
ENTRYノード２０１は、関数が呼び出された際の最初の処理を表すノードである。EXITノード２０２は、元の関数に戻る処理を表すノードである。BRANCHノード２０３は、分岐処理のため出力辺が複数存在するノードである。JOINノード２０４は、分岐処理やループ処理などに関連して入力辺が複数存在するノードである。CALLノード２０５は、ある関数から他の関数を呼び出す処理を表すノードである。CALLBACKノード２０６は、CALLノード２０５により呼び出された先の関数から戻る位置を表すノードである。
【００３１】
ノードには、ノードを一意に識別するためのノード識別子が付与されている。同図においては、数値によりノード識別子が付与されている例が示されている。以下では、例えば、ノード識別子が１のノードのことを、単にノード［1］と表す。また、各ノードは点線または実線の有向辺で結合されている。点線の有向辺は、関数間の呼び出しおよび戻り関係を表すものである。実線の有向辺は、関数内における制御関係を表すものである。
【００３２】
図３は、プログラムグラフ記憶部１２１に格納されたプログラムグラフのデータ構造の一例を示す説明図である。同図に示すように、プログラムグラフは、プログラムに含まれる関数と、各関数内のノードおよび有向辺と、各関数の呼び出し関係を示す点線の有向辺とによって表される。また実線の有向辺には、直前のノードから直後のノードまでの実行時間に相当する数値が付されている。
【００３３】
このように、プログラムグラフは、プログラムの関数ごとの処理の制御の流れを表すために一般的に用いられている制御フローグラフ（control flow graph）と、関数間の呼び出しグラフ（call graph）を組合せ、さらに各有向辺に実行時間に相当する値を付加した有向グラフである。
【００３４】
なお、実行時間は、プログラムの静的解析により見積もることができる。例えば、オブジェクトコードを解析すれば、各命令あたりのクロック数が分かる。ノード内の全ての命令に関して、この命令あたりのクロック数を合計することにより、各有向辺に対応する実行時間を見積もることが可能となる。なお、以下では簡単のため数値に単位を付けない。また、各関数の呼び出し関係を示す点線の有向辺に対応する実行時間を簡単のため１とする。
【００３５】
ここで、プログラムグラフ上で表される実行経路について説明する。図４は、プログラムの実行経路をプログラムグラフ上で表した例を示す説明図である。同図においては、関数ｆｕｎｃ３のENTRYノードであるノード［12］から、EXITノードであるノード［17］までの実行経路の例が示されている。なお、実行経路を表す有向辺は、太線の点線または実線で示されている。
【００３６】
同図においては、ノード［12］からノード［17］までの実行経路として、ノード［12］-［13］-［1］-［2］-［5］-［6］-［14］-［15］-［7］-［8］-［18］-［19］-［21］-［22］-［23］-［9］-［10］-［11］-［16］-［17］を順に通過する経路の例が示されている。
【００３７】
なお、EXITノードから複数のCALLBACKノードに戻ることができる場合（EXITノードが複数の出力辺をもつ場合）、遷移先はEXITノードが属する関数を呼び出したCALLノードと対になるCALLBACKノードであることに注意する。つまり戻り先は、実行経路の履歴に依存する。
【００３８】
例えば、図４のプログラムグラフ上の実行経路において、ノード［11］からの戻り先は、プログラムグラフ上ではノード［4］、［16］、［28］の３個の候補が存在する。しかし実行経路を遡ると、ノード［11］が属する関数ｆｕｎｃ２を呼び出したノードは、ノード［15］であるため、ノード［15］と対になるCALLBACKノードであるノード［16］に戻ることが特定できる。
【００３９】
プログラム実行装置１３０は、プログラム記憶部１３１に格納されているプログラムの実行コード１３１ｃを実行する装置である。プログラム実行装置１３０は、実際にプログラムを実行する基板が組み込まれた計算機（実機）でもよいし、エミュレーションによりプログラムを実行するホストコンピュータや、シミュレーションを実行する計算機であってもよい。
【００４０】
実行ログ収集装置１４０は、プログラム実行装置１３０と接続され、プログラムの実行時の情報を表す実行ログを収集し、実行ログ記憶部１４１に出力するものである。例えば、プログラムをシミュレータにより模擬実行する場合は、模擬実行環境上のカウンタなどを用いて実行ログの収集を行う。また実機上で実行する場合にも、ＩＣＥ（In-Circuit Emulator）などのエミュレータを用いる場合には、内部に専用のカウンタを設けるなどの手法により、実行ログを得ることができる。
【００４１】
また、ＣＰＵに接続されたバスを監視し、プログラムカウンタの値を推定することにより、実行ログを得るように構成してもよい。ここで、プログラムカウンタとは、実行する命令のアドレスを示す情報をいう。なお、一般に、プログラムカウンタは、コンパイル時やリンク時の情報を用いて、オブジェクトコードやソースコード上の実行位置に対応付けることができる。
【００４２】
上述の方法は、非侵襲方式による実行ログ収集方法であるが、侵襲収集方式の場合は、プログラム自体が実行ログを出力するため、この出力をそのまま実行ログとして利用することができる。このように、本実施の形態は、非侵襲収集方式、侵襲収集方式などの実行ログの収集方法を問わずに適用することができる。
【００４３】
実行ログ記憶部１４１は、実行ログ収集装置１４０が出力した実行ログを記憶する記憶手段である。実行ログ記憶部１４１は、ＨＤＤ、光ディスク、メモリカードなどの一般的に利用されているあらゆる記憶手段により構成することができる。図５は、実行ログ記憶部１４１に格納された実行ログのデータ構造の一例を示す説明図である。
【００４４】
同図に示すように、実行ログは任意の時刻におけるプログラムの実行時刻情報５１１と、実行状態情報５１２とを対応付けて格納している。実行時刻情報５１１は、実行ログを収集した時刻をいい、例えば、実行ログを収集した計算機が内蔵する時刻を用いて設定する。実行状態情報５１２には、実行時刻情報５１１で示される時刻に実行されていたノードのノード識別子が格納される。実行ログは間欠的に出力されるものであるため、実行状態情報５１２は、図４に示すような実行経路を間引いた情報（ノード）が出力されることになる。
【００４５】
実行ログがノード内の各命令に対応するプログラムカウンタとして収集される場合は、プログラムカウンタをノードの先頭命令で置換し、実行時刻情報５１１をその差分だけ補正するとともに、当該プログラムカウンタが含まれるノードのノード識別子を実行状態情報５１２に格納する。
【００４６】
本実施の形態において経路範囲情報を算出するために必要な実行ログの情報は、時刻ｔ１から時刻ｔ２までの区間におけるスタートノードと、ゴールノードと、スタートノードからゴールノードまでの実行時間である。これらは、図５に示すような実行ログから求めることができる。
【００４７】
すなわち、例えば、時刻ｔ１の実行時刻情報と時刻ｔ２の実行時刻情報との差分から、実行時間を求めることができる。また、時刻ｔ１のノード識別子に対応するノードをスタートノード、時刻ｔ２のノード識別子に対応するノードをゴールノードとして求めることができる。
【００４８】
実行情報推定装置１００は、グラフ入力受付部１０１と、ログ入力受付部１０２と、経路範囲情報算出部１０３と、推定実行情報記憶部１１０とを備えている。
【００４９】
グラフ入力受付部１０１は、プログラムグラフ記憶部１２１に記憶されているプログラムグラフの入力を受付けるものである。ログ入力受付部１０２は、実行ログ記憶部１４１に記憶されている実行ログの入力を受付けるものである。
【００５０】
経路範囲情報算出部１０３は、グラフ入力受付部１０１が受付けたプログラムグラフを関数の呼び出し関係を除いて簡略化したグラフを作成し、当該グラフとログ入力受付部１０２が受付けた実行ログとから経路範囲情報を算出するとともに、算出した経路範囲情報を基にして関数の呼び出し関係を考慮してされに経路範囲情報を算出するものである。経路範囲情報算出処理の詳細については後述する。
【００５１】
推定実行情報記憶部１１０は、経路範囲情報算出部１０３が算出した経路範囲情報１１１を記憶する記憶手段である。推定実行情報記憶部１１０は、ＨＤＤ、光ディスク、メモリカードなどの一般的に利用されているあらゆる記憶手段により構成することができる。図６は、推定実行情報記憶部１１０に格納された経路範囲情報１１１のデータ構造の一例を示す説明図である。
【００５２】
同図に示すように、経路範囲情報１１１は、ログ出力区間を一意に識別するためのログ出力区間ＩＤと、当該区間において算出された経路範囲とを対応付けて格納している。経路範囲は、当該区間において実行された可能性のあるノードのノード識別子をカンマで区切って格納する。
【００５３】
実行情報出力装置１５０は、実行情報推定装置１００が出力した経路範囲情報１１１を含むプログラムの実行情報を、ディスプレイなどの出力装置に出力するものである。実行情報は、プログラムグラフ上のノードの情報として得られるが、ノードの情報は、コンパイルやリンク時に得られるマッピング情報を用いると、容易にソースコード上の対応する部分の情報に変換することができる。従って、実行情報出力装置１５０は、ソースコード上の該当する部位を強調または抽出するなどの手法により、経路範囲情報１１１を実行情報の推定結果として出力する。
【００５４】
次に、このように構成された第１の実施の形態にかかる実行情報推定装置１００による実行情報推定処理について説明する。図７は、第１の実施の形態における実行情報推定処理の全体の流れを示すフローチャートである。
【００５５】
まず、グラフ入力受付部１０１が、プログラムグラフ記憶部１２１に記憶されているプログラムグラフ（以下、Ｇと表す）の入力を受付ける（ステップＳ７０１）。なお、プログラムグラフは、プログラム解析装置１２０により事前に解析され、プログラムグラフ記憶部１２１に記憶されているものとする。
【００５６】
次に、ログ入力受付部１０２が、実行ログ記憶部１４１に記憶されている実行ログの入力を受付ける（ステップＳ７０２）。なお、実行ログは、実行ログ収集装置１４０により事前に収集され、実行ログ記憶部１４１に記憶されているものとする。また、実行ログには図５に示すような情報が出力されるが、上述の方法により、スタートノード（以下、Ｖｓと表す）と、ゴールノード（以下、Ｖｇと表す）と、実行時間（以下、Ｔと表す）とを得ることができるため、これらの値の入力を受付けるものとする。
【００５７】
次に、経路範囲情報算出部１０３が、経路範囲情報算出の前処理を実行し（ステップＳ７０３）、その後、経路範囲情報算出処理を実行する（ステップＳ７０４）。経路範囲情報算出の前処理、および経路範囲情報算出処理の詳細については後述する。
【００５８】
次に、ステップＳ７０３における経路範囲情報算出の前処理の詳細について説明する。図８は、経路範囲情報算出の前処理の全体の流れを示すフローチャートである。
【００５９】
まず、経路範囲情報算出部１０３が、プログラムグラフＧから、短絡グラフ（以下、Ｇ＊と表す）と、関数ごとの短絡グラフ（以下、Ｇ＊ｆと表す）とを作成する（ステップＳ８０１）。ここで、短絡グラフとは、プログラムグラフＧの全てのCALLノードとCALLBACKノード間を有向辺で短絡し、またＧ上のEXITノードとCALLBACKノードとを結ぶ有向辺全てを消去したグラフのことである。この際、短絡した有向辺には、呼び出し先の関数におけるENTRYノードからEXITノードまでの最短時間に、関数の呼び出し処理、戻り処理にそれぞれ実行時間１がかかると仮定して２を加算した値を付与する。
【００６０】
また、関数ごとの短絡グラフとは、短絡グラフＧを各関数ｆに属するノードのみに制限したグラフをいう。関数ごとの短絡グラフは、短絡グラフを各関数で分割することにより作成することができる。
【００６１】
図９は、短絡グラフの一例を示した説明図である。図９は、図３に示したプログラムグラフＧに対応する短絡グラフＧ＊を示したものである。図９に示すように、例えば、関数ｆｕｎｃ１のノード［3］とノード［4］との間が短絡され、呼び出し先の関数であるｆｕｎｃ２の最短時間３６（２＋６＋４＋２４）に、２を加算した値である３８が、短絡した有向辺に付与されている。
【００６２】
ステップＳ８０１において、短絡グラフＧ、関数ごとの短絡グラフＧ＊ｆを作成した後、経路範囲情報算出部１０３は、各関数内の各ノード［n］について、関数ごとの短絡グラフＧ＊ｆ上においてENTRYノードからの最短時間（以下、distFromEntry（n）と表す）を算出する（ステップＳ８０２）。
【００６３】
図１０は、算出したENTRYノードからの最短時間の値を、各ノードの中に記載したプログラムグラフの一例を表す説明図である。図１０は、図３に示したプログラムグラフＧに対してdistFromEntry（n）の値を算出した場合の例を示したものである。
【００６４】
図１０においては、例えばｆｕｎｃ１のノード［2］のENTRYノードからの最短時間は２（distFromEntry（２）＝２）であることが示されている。また、ｆｕｎｃ１のノード［5］については、ENTRYノードからの最短経路は、ノード［3］およびノード［4］を経由する経路ではなく、ノード［2］から直接遷移する経路であるため、distFromEntry（５）＝１０（２＋８）となる。
【００６５】
ステップＳ８０２において、ENTRYノードからの最短時間を算出した後、経路範囲情報算出部１０３は、各関数内の各ノード［n］について、関数ごとの短絡グラフＧ＊ｆ上においてEXITノードまでの最短時間（以下、distToExit（n）と表す）を算出する（ステップＳ８０３）。
【００６６】
図１１は、算出したEXITノードまでの最短時間の値を、各ノードの中に記載したプログラムグラフの一例を表す説明図である。図１１は、図３に示したプログラムグラフＧに対してdistToExit（n）の値を算出した場合の例を示したものである。
【００６７】
図１１においては、例えばｆｕｎｃ１のノード［5］のEXITノードまでの最短時間は２（distToExit（５）＝２）であることが示されている。また、ｆｕｎｃ１のノード［2］については、EXITノードまでの最短経路は、ノード［3］およびノード［4］を経由する経路ではなく、ノード［5］へ直接遷移する経路であるため、distToExit（２）＝１０（２＋８）となる。
【００６８】
このようにして算出された短絡グラフＧ＊、関数ごとの短絡グラフＧ＊ｆ、ENTRYノードからの最短時間distFromEntry（n）、EXITノードまでの最短時間distToExit（n）は、次に説明する経路範囲情報算出処理において利用される。
【００６９】
なお、最短時間を算出する際には、重み付き有向グラフ上においてある特定のノードから残りのノードまでの最短距離を得るdijkstra法などの一般的に用いられているあらゆる方法を適用することができる。
【００７０】
次に、ステップＳ７０４における経路範囲情報算出処理の詳細について説明する。図１２は、経路範囲情報算出処理の全体の流れを示すフローチャートである。経路範囲情報算出処理は、主に２つの部分に分けられる。１つは、短絡グラフを利用して経路範囲情報を算出する部分であり、もう１つは、短絡グラフから得た経路範囲情報を利用して、関数の呼び出し関係を考慮して経路範囲情報をさらに追加する部分である。
【００７１】
まず、経路範囲情報算出部１０３が、短絡グラフＧ＊上で、スタートノードＶｓからの時間が実行時間Ｔ以内であるすべてのノードｎについて、Ｖｓからの最短時間（以下、distFromVs（n）と表す）を算出する（ステップＳ１２０１）。
【００７２】
図１３は、算出したＶｓからの最短時間の値を、各ノードの中に記載したプログラムグラフの一例を表す説明図である。図１３は、図９に示した短絡グラフＧ＊に対してdistFromVs（n）の値を算出した場合の例を示したものである。また、スタートノードをｆｕｎｃ１のノード［2］とした場合を前提としている。
【００７３】
図１３においては、例えばｆｕｎｃ１のノード［5］のＶｓからの最短時間は８（distFromVs（５）＝８）であることが示されている。また、ｆｕｎｃ３およびｆｕｎｃ５については、短絡グラフ上でｆｕｎｃ１から遷移する有向辺が存在しないため、Ｖｓからの最短時間は算出されていないことが示されている。
【００７４】
ステップＳ１２０１において、Ｖｓからの最短時間を算出した後、経路範囲情報算出部１０３は、短絡グラフＧ＊上で、ゴールノードＶｇまでの時間が実行時間Ｔ以内であるすべてのノードｎについて、Ｖｇまでの最短時間（以下、distToVg（n）と表す）を算出する（ステップＳ１２０２）。
【００７５】
図１４は、算出したＶｇまでの最短時間の値を、各ノードの中に記載したプログラムグラフの一例を表す説明図である。図１４は、図９に示した短絡グラフＧ＊に対してdistToVg（n）の値を算出した場合の例を示したものである。また、ゴールノードをｆｕｎｃ２のノード［10］とした場合を前提としている。
【００７６】
図１４においては、例えばｆｕｎｃ１のノード［2］のＶｇまでの最短時間は１４（distToVg（２）＝１４）であることが示されている。また、ｆｕｎｃ１のノード［5］については、短絡グラフ上でＶｇへ遷移する有向辺が存在しないため、Ｖｇまでの最短時間は算出されていないことが示されている。
【００７７】
ステップＳ１２０２において、Ｖｇまでの最短時間を算出した後、経路範囲情報算出部１０３は、Ｖｓからの最短時間（distFromVs（n））とＶｇまでの最短時間（distToVg（n））とを加算した値が、実行時間Ｔ以下であるノードを経路範囲情報（以下、Ｒと表す）に追加する（ステップＳ１２０３）。
【００７８】
次に、ステップＳ１２０３で算出した経路範囲情報から、関数の呼び出し関係を考慮してさらに経路範囲情報に追加するノードを算出するため、以下の処理を実行する。
【００７９】
まず、経路範囲情報算出部１０３は、スタートノードＶｓの属する関数（以下、ｆと表す）からの戻り先となりうる他の関数のCALLBACKノードのうち、一度もスタートノードＶｓとされていないノード（以下、ｍと表す）を検索する（ステップＳ１２０４）。ここで、一度もＶｓとされていないとは、後述する再帰処理のために、あるノードがスタートノードＶｓに置き換えられたことがないことを意味する。
【００８０】
次に、経路範囲情報算出部１０３は、ノードｍが存在し、かつdistToExit（Ｖｓ）＜Ｔ、かつdistToVg（ｍ）＜Ｔの条件を満たしているか否かを判断する（ステップＳ１２０５）。条件を満たしている場合は（ステップＳ１２０５：ＹＥＳ）、経路範囲情報算出部１０３は、distFromVs（ｎ）＋distToExit（ｎ）≦Ｔ−distToVg（ｍ）−１を満たす関数ｆ上のノードｎを、経路範囲情報Ｒに追加する（ステップＳ１２０６）。
【００８１】
次に、経路範囲情報算出部１０３は、再帰処理のために実行時間ＴおよびスタートノードＶｓの置き換えを行う。具体的には、Ｔ−distToExit（Ｖｓ）−１を新たな実行時間Ｔに、ノードｍを新たなスタートノードＶｓに設定する（ステップＳ１２０７）
【００８２】
次に、経路範囲情報算出部１０３は、新たに設定された実行時間Ｔ、スタートノードＶｓを用いて、経路範囲情報算出処理を再帰的に実行する（ステップＳ１２０８）。これにより、関数の戻り先からゴールノードへ遷移する経路に対して経路範囲情報を算出することが可能となる。
【００８３】
ステップＳ１２０５において、条件を満たさないと判断された場合は（ステップＳ１２０５：ＮＯ）、経路範囲情報算出部１０３は、これまでに算出した経路範囲情報Ｒに含まれるノードの中で、実行時間Ｔ以内に他の関数を呼び出して戻ってくるノードの対を検索する。具体的には、経路範囲情報算出部１０３は、Ｒに属するCALLノード、CALLBACKノードの対のうち、distFromVs（ｍ）＋distFromVg（ｍ＋１）＜Ｔを満たすノードの対（ｍ、ｍ＋１）を検索する（ステップＳ１２０９）。
【００８４】
次に、経路範囲情報算出部１０３は、該当するノードの対が存在するか否かを判断し（ステップＳ１２１０）、存在する場合は（ステップＳ１２１０：ＹＥＳ）、関数間の呼び出し時間を考慮して経路範囲に含まれうるノードを追加する。具体的には、経路範囲情報算出部１０３は、distFromVs（ｎ）＋distToExit（ｎ）≦Ｔ-Ｄ（ｍ）−２である呼び出し先関数（以下、f´と表す）上のノードｎを経路範囲情報（Ｒ）に追加する（ステップＳ１２１１）。ここで、Ｄ（ｍ）＝distFromVs（ｍ）＋distFromVg（ｍ＋１）である。
【００８５】
ステップＳ１２１０において、該当するノードの対が存在しない場合は（ステップＳ１２１０：ＮＯ）、経路範囲情報算出処理を終了する。
【００８６】
次に、上述の処理によって算出される実行情報の具体的な例について説明する。ここでは、図３に示したプログラムグラフが入力され（ステップＳ７０１）、このプログラムグラフについて、スタートノードＶｓがノード［2］、ゴールノードＶｇがノード［10］、実行時間Ｔが２５である実行ログが入力された場合（ステップＳ７０２）を前提として説明する。
【００８７】
まず、経路範囲情報算出の前処理（ステップＳ７０３）において、図９に示す短絡グラフＧ＊が作成され（ステップＳ８０１）、図１０に示すENTRYノードからの最短時間の値と、図１１に示すEXITノードまでの最短時間の値とが算出される（ステップＳ８０２、ステップＳ８０３）。
【００８８】
次に、ステップＳ７０４に示した経路範囲情報算出処理において、図１３に示すＶｓからの最短時間の値（distFromVs（ｎ））と、図１４に示すＶｇまでの最短時間の値（distToVg（ｎ））とが算出される（ステップＳ１２０１、ステップＳ１２０２）。
【００８９】
次に、以上で得たdistFromVs（ｎ）とdistToVg（ｎ）との和が実行時間Ｔ（＝２５）以内であるノードｎを経路範囲情報Ｒに追加する（ステップＳ１２０３）。この時点でＲ＝｛［Vs］、［3］、［7］、［8］、［9］、［Vg］｝となる。ここで［Vs］＝［2］、［Vg］＝［10］を表す。
【００９０】
次に、Ｖｓが属する関数ｆｕｎｃ１からの戻り先となりうるCALLBACKノードの候補として、関数ｆｕｎｃ３のノード［14］およびノード［26］が存在するため（ステップＳ１２０４、ステップＳ１２０５）、それぞれのノードに対して、改めて経路範囲情報算出処理を実行する必要がある（ステップＳ１２０６〜ステップＳ１２０８）。
【００９１】
まず、ノード［14］に戻る場合については、distFromVs（ｎ）＋distToExit（ｎ）≦Ｔ-distToVg（１４）−１（＝２５−１４−１＝１０）を満たす関数ｆｕｎｃ１上のノードとして｛［5］、［6］｝を経路範囲情報Ｒに追加する（ステップＳ１２０６）。
【００９２】
次に、ノード［14］を新たなスタートノードＶｓ、Ｔ−distToExit［Ｖｓ］−１（２５−１０−１＝１４）を新たな実行時間Ｔとして経路範囲情報算出処理を再帰的に実行する（ステップＳ１２０７〜ステップＳ１２０８）。新たなスタートノードであるノード［14］とゴールノードであるノード［10］を実行時間１４以内で結ぶ経路範囲は、｛［7］、［8］、［9］、［Vg］、［14］、［15］、［18］、［19］、［21］、［22］、［23］｝であるので、これらをＲに追加する。
【００９３】
次に、ノード［26］に戻る場合については、同様に、ノード［26］を新たなスタートノードＶｓ、Ｔ−distToExit［Ｖｓ］−１（２５−１０−１＝１４）を新たな実行時間Ｔとして経路範囲情報算出処理を再帰的に実行する（ステップＳ１２０６〜ステップＳ１２０８）。新たなスタートノードであるノード［26］とゴールノードであるノード［10］を実行時間１４以内で結ぶ経路範囲は、｛［7］、［8］、［9］、［Vg］、［18］、［19］、［21］、［22］、［23］、［26］、［27］｝であるので、これらをＲに追加する。
【００９４】
次に、ここまでの処理で得られた経路範囲情報Ｒに属するノードのうち、ノード［8］、ノード［9］がCALLノード、CALLBACKノードの組であるので（ステップＳ１２０９、ステップＳ１２１０）、ステップＳ１２１１の処理を実行する。
【００９５】
ノード［8］の呼び出し先の関数はｆｕｎｃ４であり、distFromVs（８）＝４、distToVg（９）＝４である。そこで、関数ｆｕｎｃ４に属するノードｎの中で、distFromEntry（ｎ）＋distToExit（ｎ）≦Ｔ−distFromVs（８）−distToVg（９）−２（＝１５）を満たすノード｛［18］、［19］、［21］、［22］、［23］｝をＲに追加する（ステップＳ１２１１）。
【００９６】
以上の処理により、ノード［2］とノード［10］とを実行時間２５以内で結ぶ経路範囲として、Ｒ＝｛［Vs］、［3］、［5］、［6］、［7］、［8］、［9］、［Vg］、［14］、［15］、［18］、［19］、［21］、［22］、［23］、［26］、［27］｝が得られる。
【００９７】
図１５は、このようにして得られた経路範囲情報をプログラムグラフ上で表した説明図である。同図においては、スタートノード［2］とゴールノード［10］とを実行時間２５で結ぶ経路の範囲が、ノード内を黒く塗りつぶされたノードとして表されている。
【００９８】
このように、本実施の形態においては、実行ログを大量に必要とする統計的な手法を採用していないため、収集した実行ログ情報の総数が少ない場合であっても、精度を落さずにプログラムの実行情報を得ることができる。また同様の理由により、ソースコードの特定の部位に対する実行ログ情報が少ない場合であっても、当該部位に対し精度を落さずにプログラムの実行情報を得ることができる。
【００９９】
次に、実行情報推定装置１００によって得られた実行情報である経路範囲情報を、実行情報出力装置１５０が出力する処理について説明する。図１６は、実行情報出力装置１５０によって出力される実行情報の表示画面の一例を示す説明図である。
【０１００】
同図に示すように、表示画面１６００は、プログラムグラフ上の経路範囲情報に含まれるノードを黒く塗りつぶしたグラフと、ソースコードとを同時に利用者に提示したＧＵＩ（Ｇｒａｐｈｉｃａｌ  Ｕｓｅｒ  Ｉｎｔｅｒｆａｃｅ）の例を表している。表示画面１６００は、例えば利用者がノードの１つであるノード１６０１（ノード［5］）をクリックすると、対応するソースコードを強調して表示するように構成されている。
【０１０１】
このように、ソースコードの情報が既知である場合は、経路範囲情報とソースコードの情報を統合することにより、実行情報推定装置１００の内部ではプログラムグラフ上のノード情報として表されている実行情報を、ソースコード上の情報として可視化することができる。
【０１０２】
以上のように、第１の実施の形態にかかる実行情報推定装置１００では、プログラムグラフと実行ログとから、ログ出力区間において実行された可能性のあるノードの経路範囲情報を実行情報として推定することができる。このため、少なくとも１つのログ出力区間における実行ログが得られれば、推定精度を低減させることなくプログラムの実行情報を取得することができる。
【０１０３】
（第２の実施の形態）
第２の実施の形態にかかる実行情報推定装置は、ログ出力区間において実行された可能性のあるノードの経路を表す経路範囲情報を実行情報として推定するとともに、当該経路範囲情報から、ログ出力区間において確実に実行されたノードの集合を表すドミナント情報を算出するものである。
【０１０４】
図１７は、第２の実施の形態にかかる実行情報推定装置１７００の構成を示すブロック図である。同図に示すように、実行情報推定装置１７００は、グラフ入力受付部１０１と、ログ入力受付部１０２と、経路範囲情報算出部１０３と、ドミナント情報算出部１７０４と、推定実行情報記憶部１７１０とを備えている。
【０１０５】
第２の実施の形態においては、ドミナント情報算出部１７０４を追加したこと、および推定実行情報記憶部１７１０のデータ構造が第１の実施の形態と異なっている。その他の構成および機能は、第１の実施の形態にかかる実行情報推定装置１００の構成を表すブロック図である図１と同様であるので、同一符号を付し、ここでの説明は省略する。
【０１０６】
ドミナント情報算出部１７０４は、経路範囲情報算出部１０３が算出した経路範囲情報に含まれるノードに対し、そのノードを削除した場合に他の経路が存在するか否かによりドミナントノードを算出し、ドミナントノードの範囲（集合）であるドミナント情報を算出するものである。
【０１０７】
ここで、ドミナントノードとは、ログ出力区間内に実行されたノードをいう。具体的には、ドミナントノードとは、ログ出力区間のスタートノードとゴールノードの間をログ出力区間の実行時間以内で結ぶ実行経路を考えた場合に、必ず通過するノードの全体の集合をいう。すなわち、ドミナント情報は、ログ出力区間内に必ず実行されたノード（ドミナントノード）の範囲を表す点において、ログ出力区間内に実行された可能性のあるノードの範囲を表す経路範囲情報と異なっている。
【０１０８】
推定実行情報記憶部１７１０は、経路範囲情報算出部１０３が算出した経路範囲情報１１１と、ドミナント情報算出部１７０４が算出したドミナント情報１７１２とを記憶する記憶手段である。ドミナント情報１７１２のデータ構造は、図６に示した経路範囲情報１１１のデータ構造と同様であるのでその説明を省略する。
【０１０９】
次に、このように構成された第２の実施の形態にかかる実行情報推定装置１７００による実行情報推定処理について説明する。第２の実施の形態においては、実行情報として経路範囲情報に加えて、ドミナント情報を算出する点が、第１の実施の形態と異なっている。経路範囲情報算出処理は、第１の実施の形態と同様であるので、その説明を省略する。以下では、ドミナント情報算出処理について説明する。
【０１１０】
図１８は、第２の実施の形態におけるドミナント情報算出処理の全体の流れを示すフローチャートである。まず、ドミナント情報算出部１７０４が、経路範囲情報から１つのノードｎを取得する（ステップＳ１８０１）。
【０１１１】
次に、ドミナント情報算出部１７０４は、プログラムグラフＧからノードｎを除いたプログラムグラフ（以下、Ｇ´と表す）を作成する（ステップＳ１８０２）。次に、ドミナント情報算出部１７０４は、作成したＧ´上で、スタートノードＶｓとゴールノードＶｇとを実行時間Ｔ以内で結ぶ実行経路が存在するか否かを判断する（ステップＳ１８０３）。
【０１１２】
この判断は、プログラムグラフＧ´と、スタートノードＶｓ、ゴールノードＶｇ、実行時間Ｔとを入力として、上述した経路範囲情報算出処理を適用することにより実行することができる。この処理の結果、経路範囲情報が得られれば、実行経路が存在すると判断する。
【０１１３】
ステップＳ１８０３において、実行経路が存在しないと判断した場合は（ステップＳ１８０３：ＮＯ）、ドミナント情報算出部１７０４は、ノードｎをドミナント情報（以下、Ｄと表す）に追加する（ステップＳ１８０４）。
【０１１４】
実行経路が存在すると判断した場合（ステップＳ１８０３：ＹＥＳ）、または、ステップＳ１８０４においてドミナント情報Ｄを追加した後、ドミナント情報算出部１７０４は、未処理のノードが存在するか否かの判断処理を実行する（ステップＳ１８０５）。
【０１１５】
未処理のノードが存在する場合は（ステップＳ１８０５：ＹＥＳ）、他のノードを取得して処理を繰り返す（ステップＳ１８０１）。未処理のノードが存在しない場合は（ステップＳ１８０５：ＮＯ）、ドミナント情報算出処理を終了する。
【０１１６】
例えば、上述のように、図３に示したプログラムグラフが入力され、このプログラムグラフについて、スタートノードＶｓがノード［2］、ゴールノードＶｇがノード［10］、実行時間Ｔが２５である実行ログが入力された場合は、経路範囲情報として、Ｒ＝｛［Vs］、［3］、［5］、［6］、［7］、［8］、［9］、［Vg］、［14］、［15］、［18］、［19］、［21］、［22］、［23］、［26］、［27］｝が得られる。
【０１１７】
このうち、例えばノード［3］を除いたグラフＧ´上では、ＶｓとＶｇとを結ぶ経路として、［Vs］-［5］-［6］-［14］-［15］-［7］-［8］-［18］-［19］-［21］-［22］-［23］-［9］-［Vg］が存在するため、ノード［3］はドミナントノードではないと判断される。一方、ノード［8］を除いたグラフＧ´上では、ＶｓとＶｇとを結ぶ経路が存在しないため、ノード［8］はドミナントノードであると判断される。
【０１１８】
図１９は、このようにして得られるドミナント情報の一例をプログラムグラフ上に表した説明図である。同図においては、上述の例において算出されるドミナント情報Ｄとして、Ｄ＝｛［Vs］、［7］、［8］、［9］、［Vg］、［18］、［19］、［21］、［22］、［23］｝が得られることが示されている。
【０１１９】
このように、第２の実施の形態にかかる実行情報推定装置１７００では、経路範囲情報を実行情報として推定するとともに、当該経路範囲情報から、ログ出力区間において確実に実行されたノードの情報を算出することができる。このため、プログラムの性能チューニングを行うためのより有用な情報を得ることができる。
【０１２０】
（第３の実施の形態）
第３の実施の形態にかかる実行情報推定装置は、経路範囲情報を実行情報として推定し、当該経路範囲情報からドミナント情報を算出するとともに、当該経路範囲情報およびドミナント情報から、ノードごとのプロファイル情報を算出して出力するものである。
【０１２１】
ここで、プロファイル情報とは、プログラムの実行状態を示す情報で、ノードの実行頻度の情報を含む情報をいう。ノードごとの実行頻度からは、二次情報として、ノードごとの実行回数の順位付け情報や、関数レベルの実行頻度情報などが得られるが、これらも含めてプロファイル情報という。
【０１２２】
図２０は、第３の実施の形態にかかる実行情報推定装置２０００の構成を示すブロック図である。同図に示すように、実行情報推定装置２０００は、グラフ入力受付部１０１と、ログ入力受付部１０２と、経路範囲情報算出部１０３と、ドミナント情報算出部１７０４と、プロファイル情報算出部２００５と、推定実行情報記憶部２１１０とを備えている。
【０１２３】
第３の実施の形態においては、プロファイル情報算出部２００５を追加したこと、および推定実行情報記憶部２１１０のデータ構造が第２の実施の形態と異なっている。その他の構成および機能は、第２の実施の形態にかかる実行情報推定装置１７００の構成を表すブロック図である図１７と同様であるので、同一符号を付し、ここでの説明は省略する。
【０１２４】
プロファイル情報算出部２００５は、経路範囲情報算出部１０３が算出した経路範囲情報に含まれるノードよりも、ドミナント情報算出部１７０４が算出したドミナント情報に含まれるノードの実行頻度の推定値が大きくなるように重み付けしてプロファイル情報を算出するものである。プロファイル情報算出処理の詳細は後述する。
【０１２５】
推定実行情報記憶部２１１０は、経路範囲情報算出部１０３が算出した経路範囲情報１１１と、ドミナント情報算出部１７０４が算出したドミナント情報１７１２と、プロファイル情報算出部２００５が算出したプロファイル情報２０１３とを記憶する記憶手段である。
【０１２６】
図２１は、プロファイル情報のデータ構造の一例を示す説明図である。同図に示すように、プロファイル情報は、プログラムグラフ上のノードごとに、任意のログ出力区間におけるノードの実行頻度のランク（rank）と、当該区間の総実行時間に占めるノードの実行時間の割合（time）と、実行頻度（calls）と、ノードの属する関数名（funcname）と、ノード識別子（nodeID）とを対応付けて格納している。
【０１２７】
次に、このように構成された第３の実施の形態にかかる実行情報推定装置２０００による実行情報推定処理について説明する。第３の実施の形態においては、実行情報として経路範囲情報およびドミナント情報に加えて、プロファイル情報を算出する点が、第２の実施の形態と異なっている。経路範囲情報算出処理およびドミナント情報算出処理は、第２の実施の形態と同様であるので、その説明を省略する。以下では、プロファイル情報算出処理について説明する。
【０１２８】
図２２は、第３の実施の形態におけるドミナント情報算出処理の全体の流れを示すフローチャートである。まず、プロファイル情報算出部２００５が、各ノードの推定実行重み（以下、Ｗ（ｎ）と表す）の初期化を行う（ステップＳ２２０１）。推定実行重みとは、ノードの実行頻度の推定値を表す情報である。
【０１２９】
次に、プロファイル情報算出部２００５は、実行ログを収集したログ出力区間の１つにおいて算出した経路範囲情報Ｒと、ドミナント情報Ｄとを取得する（ステップＳ２２０２）。次に、プロファイル情報算出部２００５は、プログラムグラフＧから１つのノードｎを取得し（ステップＳ２２０３）、ノードｎがドミナント情報Ｄに含まれるか否かを判断する（ステップＳ２２０４）。
【０１３０】
ドミナント情報Ｄに含まれる場合は（ステップＳ２２０４：ＹＥＳ）、プロファイル情報算出部２００５は、推定実行重みＷ（ｎ）に、ドミナントノードに対して予め定められた重みパラメタの値Ｗｄを加算する（ステップＳ２２０５）。本実施の形態においては、経路範囲情報Ｒに含まれるノードに対して推定実行重みに１を設定するため、１より大きい値をドミナントノードに対する推定実行重みＷｄとして予め定めておく。
【０１３１】
ドミナント情報Ｄに含まれない場合は（ステップＳ２２０４：ＮＯ）、プロファイル情報算出部２００５は、ノードｎが経路範囲情報Ｒに含まれるか否かを判断する（ステップＳ２２０６）。
【０１３２】
経路範囲情報Ｒに含まれる場合は（ステップＳ２２０６：ＹＥＳ）、プロファイル情報算出部２００５は、推定実行重みＷ（ｎ）に１を加算する（ステップＳ２２０７）。なお、経路範囲情報Ｒに含まれるノードに対しても重みパラメタを予め定めておくように構成してもよい。
【０１３３】
ステップＳ２２０６において、ノードｎが経路範囲情報Ｒに含まれないと判断した場合（ステップＳ２２０６：ＮＯ）、または、ステップＳ２２０５およびステップＳ２２０７において推定実行重みの加算処理を実行した後、プロファイル情報算出部２００５は、すべてのノードを処理したか否かを判断する（ステップＳ２２０８）。
【０１３４】
すべてのノードを処理していない場合は（ステップＳ２２０８：ＮＯ）、次のノードを取得して処理を繰り返す（ステップＳ２２０３）。すべてのノードを処理した場合は（ステップＳ２２０８：ＹＥＳ）、プロファイル情報算出部２００５は、すべてのログ出力区間に対して処理を実行したか否かを判断する（ステップＳ２２０９）。
【０１３５】
すべてのログ出力区間に対して処理を実行していない場合は（ステップＳ２２０９：ＮＯ）、次のログ出力区間の経路範囲情報Ｒとドミナント情報Ｄとを取得して処理を繰り返す（ステップＳ２２０２）。すべてのログ出力区間に対して処理を実行した場合は（ステップＳ２２０９：ＹＥＳ）、プロファイル情報算出処理を終了する。
【０１３６】
次に、プロファイル情報算出処理の具体的な例について説明する。例として、図３に示すようなプログラムグラフと、時刻７８にノード［12］、時刻８４にノード［2］、時刻１０９にノード［10］、時刻１３５にノード［17］が出力された実行ログとが入力された場合について説明する。
【０１３７】
上述の４つの時刻で区切られる３つのログ出力区間について、上述の経路範囲情報算出処理およびドミナント情報算出処理により、Ｒ（1）＝Ｄ（1）＝｛［1］、［12］、［13］｝、Ｒ（2）＝｛［2］、［3］、［5］、［6］、［7］、［8］、［9］、［10］、［14］、［15］、［18］、［19］、［21］、［22］、［23］｝、Ｄ（2）＝｛［2］、［7］、［8］、［9］、［10］、［18］、［19］、［21］、［22］、［23］｝、Ｒ（3）＝Ｄ（3）＝｛［11］、［16］、［17］｝が得られる。ここで、Ｒ（ｎ）、Ｄ（ｎ）はそれぞれｎ番目のログ出力区間における経路範囲情報とドミナント情報を表す。
【０１３８】
なお、各区間の境界に存在するノードに関して重複してカウントされるのを避けるため、Ｒ（1）、Ｄ（1）からノード［2］を、Ｒ（3）、Ｄ（3）からノード［10］をそれぞれ除いている。また、予め定めるドミナントノードに対する重みパラメタとしてＷｄ＝２が設定されているものとする。
【０１３９】
この場合、最初の区間に関して重みを計算すると、ドミナント情報Ｄに属するノードに対してＷ（1）＝Ｗ（12）＝Ｗ（13）＝２となり、その他のノードに対する重みは０となる。また、２番目の区間に対して重みを計算すると、ドミナント情報Ｄに属するノードに対してＷ（2）＝Ｗ（7）＝Ｗ（8）＝Ｗ（9）＝Ｗ（10）＝Ｗ（18）＝Ｗ（19）＝Ｗ（21）＝Ｗ（22）＝Ｗ（23）＝２、それ以外の経路範囲情報に属するノードに対して、Ｗ（3）＝Ｗ（5）＝Ｗ（6）＝Ｗ（14）＝Ｗ（15）＝１、それ以外のノードの重みは０となる。最後の区間に対して重みを計算すると、ドミナント情報Ｄに属するノードに対してＷ（11）＝Ｗ（16）＝Ｗ（17）＝２となる。
【０１４０】
各区間の重みを全て足し合わせると、Ｗ（1）＝Ｗ（2）＝Ｗ（7）＝Ｗ（8）＝Ｗ（9）＝Ｗ（10）＝Ｗ（11）＝Ｗ（12）＝Ｗ（13）＝Ｗ（16）＝Ｗ（17）＝Ｗ（18）＝Ｗ（19）＝Ｗ（21）＝Ｗ（22）＝Ｗ（23）＝２、Ｗ（3）＝Ｗ（5）＝Ｗ（6）＝Ｗ（14）＝Ｗ（15）＝１、Ｗ（4）＝Ｗ（20）＝Ｗ（24）＝Ｗ（25）＝Ｗ（26）＝Ｗ（27）＝Ｗ（28）＝Ｗ（29）＝Ｗ（30）＝Ｗ（31）＝０が得られる。これらを重みおよび関数名によりソートすると、図２１に示すようなプロファイル情報が得られる。
【０１４１】
次に、実行情報推定装置２０００によって得られた実行情報であるプロファイル情報を、実行情報出力装置１５０が出力する処理について説明する。図２３は、実行情報出力装置１５０によって出力される実行情報の表示画面の一例を示す説明図である。
【０１４２】
同図に示すように、表示画面２３００は、プロファイル情報と、ソースコードとを同時に利用者に提示したＧＵＩの例を表している。表示画面２３００は、例えば利用者がプロファイル情報上のノードの１つであるノード２３０１（ノード［1］）をクリックすると、対応するソースコードを強調して表示するように構成されている。
【０１４３】
このように、第３の実施の形態にかかる実行情報推定装置２０００では、経路範囲情報を実行情報として推定し、当該経路範囲情報からドミナント情報を算出するとともに、当該経路範囲情報およびドミナント情報から、ノードごとのプロファイル情報を算出することができる。また、算出したプロファイル情報をソースと対応づけて表示することができる。このため、プログラムの性能チューニングを行うためのより有用な情報を得るとともに、その情報を的確に把握することができる。
【０１４４】
（第４の実施の形態）
第４の実施の形態にかかる実行情報推定装置は、ログ出力区間のスタート時のスタック情報が追加された実行ログの入力を受付け、スタート時のスタック情報を利用して経路範囲情報を算出するものである。ここで、スタック情報とは、関数の呼び出し元の履歴の情報をいい、具体的には、関数の呼び出し元のノードのノード識別子を含む情報をいう。
【０１４５】
図２４は、第４の実施の形態にかかる実行情報推定装置２４００の構成を示すブロック図である。同図に示すように、実行情報推定装置２４００は、グラフ入力受付部１０１と、ログ入力受付部１０２と、経路範囲情報算出部２４０３と、ドミナント情報算出部１７０４と、プロファイル情報算出部２００５と、推定実行情報記憶部２１１０とを備えている。
【０１４６】
第４の実施の形態においては、経路範囲情報算出部２４０３の機能が第３の実施の形態と異なっている。また、入力する実行ログを格納する実行ログ記憶部２４４１のデータ構造が第３の実施の形態と異なっている。その他の構成および機能は、第３の実施の形態にかかる実行情報推定装置２０００の構成を表すブロック図である図２０と同様であるので、同一符号を付し、ここでの説明は省略する。
【０１４７】
経路範囲情報算出部２４０３は、グラフ入力受付部１０１が受付けたプログラムグラフと、ログ入力受付部１０２が受付けた実行ログとを用いて、実行ログに含まれるスタート時のスタック情報により関数の戻り先が限定されることを利用して高精度に経路範囲情報を算出するものである。経路範囲情報算出処理の詳細については後述する。
【０１４８】
ここで、スタック情報の一般的な性質について説明する。一般に、プログラムの実行時の状態は、プログラムカウンタやレジスタの値だけでは一意に決定することができず、メモリ上のスタック情報が必要である。また、プログラムをプログラムグラフの経路としてモデル化した場合においても、一般にメモリ上のスタック情報が得られなければ、実行時の状態を一意に決定できない。
【０１４９】
例えば、プログラムの実行時のある時点のプログラムグラフ上の実行位置は、プログラムカウンタにより求めることができる。しかし、当該プログラムカウンタが属する関数をｆとすると、関数ｆを呼び出す他の関数が複数存在するとき、プログラムカウンタの情報だけでは関数ｆからの戻り先の関数を決定することができない。また、仮に最初の戻り先が決定できたとしても、さらにその戻り先の関数から関数に戻る場合には、同様に戻り先を決定できないという問題が生じる。
【０１５０】
すなわち、プログラムグラフ上におけるプログラムの実行状態を一意に決定するためには、メモリに格納されている戻り先の情報が必要である。このメモリ上の戻り先を特定するための情報がスタック情報である。このように、スタック情報とは関数の呼び出しの履歴を表すものである。
【０１５１】
実行ログ記憶部２４４１は、実行ログ収集装置１４０が出力した実行ログを記憶する記憶手段であり、スタック情報またはスタック候補情報を格納する点が第３の実施の形態における実行ログ記憶部１４１と異なっている。
【０１５２】
ここで、スタック候補情報とは、関数の呼び出し元のノードであるスタック情報を特定できないが、スタック情報となりうるノードが限定できる場合に、そのスタック情報の候補をいう。
【０１５３】
図２５は、実行ログ記憶部２４４１に格納された実行ログのデータ構造の一例を示す説明図である。同図に示すように、実行ログは任意の時刻におけるプログラムの実行時刻情報５１１と、実行状態情報２５１２とを対応付けて格納している。実行状態情報２５１２には、実行時刻情報５１１で示される時刻に実行されていたノードのノード識別子と、スタック情報またはスタック候補情報２５１２ａとが格納されている。
【０１５４】
例えば、ある時点におけるスタック情報が、｛［29］、［13］、［3］｝または｛［29］、［15］｝のどちらであるか確定できない場合は、これらを全て列挙した｛｛［29］、［13］、［3］｝、｛［29］、［15］｝｝のような配列の形式でスタック候補情報を保持する。なお、以下では特に明示した場合を除き、スタック情報にはスタック候補情報も含むものとする。
【０１５５】
また、本実施の形態は、スタック情報として少なくともログ出力区間の開始時における関数の呼び出し元の履歴の情報、すなわち、開始時のスタック情報であるスタート時スタックが取得でき、当該スタート時スタックを利用して経路範囲情報を算出するものである。
【０１５６】
スタック情報は、上述のように配列の形式で保存される。例えば、図３に示すプログラムグラフで表されるプログラムのように、ノード［29］から関数ｆｕｎｃ３が呼び出され、関数ｆｕｎｃ３内でノード［13］から関数ｆｕｎｃ１を呼び出している場合、スタック情報をＳＴｓとすると、スタック情報にはＳＴｓ＝｛［29］、［13］｝のようにノード識別子の情報が格納される。このように、スタック情報の配列には、最初のCALLノードから、呼び出した順序に従って昇順にCALLノードを格納するものとする。なお、以下ではスタック情報ＳＴｓを０から始まる配列の添え字を用いて、ＳＴｓ［０］＝［29］、ＳＴｓ［１］＝［13］のように表現する場合がある。
【０１５７】
次に、このように構成された第４の実施の形態にかかる実行情報推定装置２４００による実行情報推定処理について説明する。第４の実施の形態においては、スタック情報を用いて経路範囲情報を算出する点が、第３の実施の形態と異なっている。ドミナント情報算出処理およびプロファイル情報算出処理は、第３の実施の形態と同様であるので、その説明を省略する。
【０１５８】
図２６は、第４の実施の形態における経路範囲情報算出処理の全体の流れを示すフローチャートである。第４の実施の形態においては、スタートノードＶｓの属する関数ｆからの戻り先となりうるCALLBACKノードをすべて対象とするのではなく（図１２のステップＳ１２０４）、スタック情報の配列の末尾に保存されているノードに対応するCALLBACKノードのみに限定して経路範囲情報を算出する点が（ステップＳ２６０４）、第３の実施の形態と異なっている。
【０１５９】
その他の処理（ステップＳ２６０１〜ステップＳ２６０３、ステップＳ２６０６〜ステップＳ２６１１）は、第３の実施の形態と同様であるので（ステップＳ１２０１〜ステップＳ１２０３、ステップＳ１２０６〜ステップＳ１２１１）、その説明を省略する。
【０１６０】
次に、第４の実施の形態における経路範囲情報算出処理の具体的な例について説明する。ここでは、図３に示したプログラムグラフが入力され（ステップＳ７０１）、このプログラムグラフについて、スタートノードＶｓがノード［2］、ゴールノードＶｇがノード［10］、実行時間Ｔが２５、スタート時のスタック情報（以下、ＳＴｓと表す）がＳＴｓ＝｛［29］、［13］｝である実行ログが入力された場合（ステップＳ７０２）を前提として説明する。
【０１６１】
ステップＳ２６０３までは第３の実施の形態と同様であり、経路範囲情報Ｒとして、Ｒ＝｛［Vs］、［3］、［7］、［8］、［9］、［Vg］｝が得られる。
【０１６２】
次に、Ｖｓが属する関数ｆｕｎｃ１からの戻り先となりうるCALLBACKノードの候補として、関数ｆｕｎｃ３のノード［14］およびノード［26］が存在するが、スタック情報として｛［29］、［13］｝が既知であるため、戻り先となるCALLBACKノードはノード［13］に対応するノード［14］に限定することができる（ステップＳ２６０４）。
【０１６３】
従って、ノード［14］のみに対して、経路範囲情報算出処理を再帰的に実行すればよい（ステップＳ２６０６〜ステップＳ２６０８）。この処理により、｛［5］、［6］、［7］、［8］、［9］、［Vg］、［14］、［15］、［18］、［19］、［21］、［22］、［23］｝が経路範囲情報Ｒに追加される。
【０１６４】
この後、第３の実施の形態と同様にして、最終的に、経路範囲情報Ｒとして、Ｒ＝｛［Vs］、［3］、［5］、［6］、［7］、［8］、［9］、［Vg］、［14］、［15］、［18］、［19］、［21］、［22］、［23］｝が得られる。このように、スタック情報が存在しない場合と比較すると、ノード［26］、ノード［27］の分だけ経路範囲を絞り込めている。
【０１６５】
図２７は、このようにして得られた経路範囲情報をプログラムグラフ上で表した説明図である。同図においては、スタートノード［2］とゴールノード［10］とを実行時間２５で結ぶ経路の範囲が、ノード内を黒く塗りつぶされたノードとして表されている。スタック情報が存在しない場合に算出された経路範囲を示す図１５と比較すると、ノード［26］、ノード［27］が経路範囲から除外され、この分だけ経路範囲情報の推定の精度が向上していることが分かる。
【０１６６】
このように、第４の実施の形態にかかる実行情報推定装置２４００では、ログ出力区間のスタート時のスタック情報を利用して経路範囲情報を算出することができるため、より高精度に実行情報を推定することができる。
【０１６７】
（第５の実施の形態）
第５の実施の形態にかかる実行情報推定装置は、ログ出力区間のスタート時だけでなくゴール時のスタック情報が追加された実行ログの入力を受付け、スタート時およびゴール時のスタック情報を利用して経路範囲情報を算出するものである。
【０１６８】
図２８は、第５の実施の形態にかかる実行情報推定装置２８００の構成を示すブロック図である。同図に示すように、実行情報推定装置２８００は、グラフ入力受付部１０１と、ログ入力受付部１０２と、経路範囲情報算出部２８０３と、ドミナント情報算出部１７０４と、プロファイル情報算出部２００５と、推定実行情報記憶部２１１０とを備えている。
【０１６９】
第５の実施の形態においては、経路範囲情報算出部２８０３の機能が第４の実施の形態と異なっている。その他の構成および機能は、第４の実施の形態にかかる実行情報推定装置２４００の構成を表すブロック図である図２４と同様であるので、同一符号を付し、ここでの説明は省略する。
【０１７０】
経路範囲情報算出部２８０３は、グラフ入力受付部１０１が受付けたプログラムグラフと、ログ入力受付部１０２が受付けた実行ログとを用いて、実行ログに含まれるスタート時およびゴール時のスタック情報によりとりうる経路が限定されることを利用して高精度に経路範囲情報を算出するものである。経路範囲情報算出処理の詳細については後述する。
【０１７１】
次に、このように構成された第５の実施の形態にかかる実行情報推定装置２８００による実行情報推定処理について説明する。第５の実施の形態における実行情報推定処理の全体の流れは、第１〜第４の実施の形態における実行情報推定処理の全体の流れを示す図７と同様であるのでその説明を省略する。
【０１７２】
第５の実施の形態においては、図７のステップＳ７０４に示した経路範囲情報算出処理の詳細が、第１〜第４の実施の形態と異なっている。以下では、経路範囲情報算出処理の詳細について説明する。
【０１７３】
まず、第５の実施の形態における経路範囲情報算出方法の基本的な考え方について説明する。スタート時のスタック情報とゴール時のスタック情報（以下、ＳＴｇと表す）が共に既知である場合、ＳＴｓのノード列とＳＴｇのノード列との最初の要素からの共通部分（以下、共通ノードという）に着目することにより、経路範囲を限定することができる。
【０１７４】
共通ノードが存在するということは、スタート時のスタック情報ＳＴｓに含まれるノードのうち、少なくとも共通ノードの次のCALLノードに対応するCALLBACKノードまで戻った状態であると判断することができるためである。
【０１７５】
例えば、図３に示すようなプログラムグラフで表されるプログラムの場合、スタート時スタックがＳＴｓ＝｛［29］、［13］｝、ゴール時スタックがＳＴｇ＝｛［29］、［15］｝であったとすると、ノード［29］から関数ｆｕｎｃ３を呼び出し、関数ｆｕｎｃ３内のノード［13］から関数ｆｕｎｃ１を呼び出した状態でスタート時スタックが記憶され、その後、関数ｆｕｎｃ１から関数ｆｕｎｃ３のノード［14］に戻り、次のノード［15］から関数ｆｕｎｃ２が呼び出された状態でゴール時スタックが記憶されたと判断することができる。
【０１７６】
そこで、まずスタート時スタックとゴール時スタックの最初の要素からの共通の要素数を変数mutualに格納する。次に、スタート時スタックＳＴｓのノードのうち、共通ノードの次のCALLノード（＝ＳＴｓ［mutual］）に対応するCALLBACKノードＶｍｓ（＝ＳＴｓ［mutual］＋1））から、ゴール時スタックＳＴｇのノードのうち、共通ノードの次のCALLノードＶｍｇ（＝ＳＴｇ［mutual］）までの経路を短絡グラフ上で算出する。
【０１７７】
次に、スタートノードＶｓから、ノードＶｍｓ、ノードＶｍｇを経由してゴールノードＶｇに達する経路の最短時間minDistを求める。この経路は、スタートノードＶｓ、スタート時のスタック配列ＳＴｓの降順にＳＴｓ［Ｎｓ−１］からＳＴｓ［mutual］までのノード、ノードＶｍｓ、ゴール時のスタック配列ＳＴｇの昇順にＳＴｇ［mutual］（＝Ｖｍｇ）からＳＴｇ［Ｎｇ−１］までのノードの順に通過する。ここで、Ｎｓはスタート時スタックの要素数を、Ｎｇはゴール時スタックの要素数を表す。
【０１７８】
よってスタートノードＶｓからゴールノードＶｇまでの区間を、上述のノードで区分される区間に分解し、区間ごとの最短時間の総和を得ればよい。分解して得られる区間は、最初のノードと最後のノードが必ず同一関数に属するため、各区間の最短時間は、短絡グラフＧ＊を当該関数に制限したＧ＊ｆ上で求めればよい。
【０１７９】
このようにして得られた区間ごとの最短時間の総和に、関数間の呼び出し時間を加算した時間が求める最短時間の総和minDistとなる。最後に、区間ごとに実行時間Ｔ−minDist＋（各区間の最短時間）で通過可能な経路範囲を算出し、この範囲に含まれるノードを経路範囲情報Ｒに加える。以上の手続きを、mutualを１減算し０に達するまで繰り返すことにより、経路範囲情報Ｒを算出することができる。
【０１８０】
次に、このような経路範囲情報算出処理の流れをフローチャートに従って説明する。図２９は、第５の実施の形態における経路範囲情報算出処理の全体の流れを示すフローチャートである。
【０１８１】
まず、経路範囲情報算出部２８０３が、スタート時スタックと、ゴール時スタックとの間で、共通するノードの個数mutualを算出する（ステップＳ２９０１）。
【０１８２】
次に、経路範囲情報算出部２８０３は、スタートノードＶｓおよびゴールノードＶｇのノード識別子の値を、スタック配列に追加して設定する（ステップＳ２９０２）。後の計算の便宜のためである。具体的には、ＳＴｓ［Ｎｓ］＝Ｖｓ−１、ＳＴｇ［Ｎｇ］＝Ｖｇを設定する。
【０１８３】
例えば、スタート時スタックがＳＴｓ＝｛［29］、［13］｝、スタートノードが［2］である場合、要素数（Ｎｓ）は２であるので、ＳＴｓ［２］＝２−１＝１（ノード［1］）を設定する。
【０１８４】
次に、経路範囲情報算出部２８０３は、スタート時スタックとゴール時スタックとの間の共通ノードの次のCALLノードに対応するCALLBACKノードＶｍｓから、ゴール時スタックのCALLノードＶｍｇまでの経路を確認するためのパラメタの設定を行う。
【０１８５】
具体的には、スタート時スタックとゴール時スタックとの間の共通ノードの次のCALLノードは、ＳＴｓ［mutual］であるため、それに対応するCALLBACKノードとして、ＳＴｓ［mutual］＋１をＶｍｓに設定する。また、ゴール時スタックに含まれるノードのうち、共通ノードの後に呼び出されるCALLノードは、ＳＴｇ［mutual］であるため、この値をＶｍｇに設定する（ステップＳ２９０３）。
【０１８６】
次に、経路範囲情報算出部２８０３は、短絡グラフＧ＊上で、ＶｍｓとＶｍｇとを結ぶ経路が存在するか否かを判断する（ステップＳ２９０４）。経路が存在する場合は（ステップＳ２９０４：ＹＥＳ）、経路範囲情報算出部２８０３は、ログ出力区間を分解する分解処理を実行する（ステップＳ２９０５）。分解処理の詳細については後述する。
【０１８７】
経路が存在しない場合は（ステップＳ２９０４：ＮＯ）、経路範囲情報算出部２８０３は、次の共通ノードの確認のためのパラメタ設定を行う。具体的には、mutualから１を減算する（ステップＳ２９０９）。
【０１８８】
ステップＳ２９０５において、分解処理を実行した後、経路範囲情報算出部２８０３は、短絡グラフＧ＊上における分解した各区間を通過する時間である最短時間（minDist）を算出する（ステップＳ２９０６）。
【０１８９】
次に、経路範囲情報算出部２８０３は、分解した各区間で経路範囲情報Ｒを算出する（ステップＳ２９０７）。具体的には、短絡グラフＧ＊上で、各区間の開始ノードから終了ノードまでを、実行時間Ｔ−minDist＋（各区間の最短時間）に相当する時間以内で結ぶ経路範囲を、経路範囲情報Ｒに追加する。
【０１９０】
次に、経路範囲情報算出部２８０３は、すべての区間を処理したか否かを判断し（ステップＳ２９０８）、すべての区間を処理していない場合は（ステップＳ２９０８：ＮＯ）、経路範囲情報算出部２８０３は、次の区間について経路範囲情報の算出処理を繰り返し実行する（ステップＳ２９０７）。
【０１９１】
すべての区間を処理した場合は（ステップＳ２９０８：ＹＥＳ）、経路範囲情報算出部２８０３は、次の共通ノードの確認のためのパラメタ設定を行う（ステップＳ２９０９）。次に、経路範囲情報算出部２８０３は、パラメタmutualが０以上であるか否かを判断し（ステップＳ２９１０）、０以上である場合は（ステップＳ２９１０：ＹＥＳ）、ステップＳ２９０３に戻り処理を繰り返す。０以上でない場合は（ステップＳ２９１０：ＮＯ）、経路範囲情報算出処理を終了する。
【０１９２】
次に、ステップＳ２９０５における分解処理の詳細について説明する。図３０は、第５の実施の形態における分解処理の全体の流れを示すフローチャートである。分解処理では、ログ出力区間を分解し、各区間のスタートノードとゴールノードとを算出する。算出したスタートノードとゴールノードは、配列の形式で保存する。配列名はそれぞれＰａｒｔＳ、ＰａｒｔＧとする。
【０１９３】
まず、経路範囲情報算出部２８０３が、パラメタの初期化処理を実行する。具体的には、経路範囲情報算出部２８０３は、配列の添え字ＰａｒｔＮｕｍを０に、カウンタＮをＮｓ（スタート時スタックの要素数）に設定する（ステップＳ３００１）。
【０１９４】
次に、経路範囲情報算出部２８０３は、スタート時スタックに格納されている各ノードに対応するCALLBACKノードから、当該CALLBACKノードが属する関数のEXITノードまでをそれぞれ１つの区間として分解するために、ステップＳ３００２からステップＳ３００５までの処理を実行する。
【０１９５】
まず、経路範囲情報算出部２８０３は、カウンタＮがスタックの共通の要素数mutualより大きいか否かを判断する（ステップＳ３００２）。大きい場合は（ステップＳ３００２：ＹＥＳ）、経路範囲情報算出部２８０３は、ＰａｒｔＳ［ＰａｒｔＮｕｍ］の値をＳＴｓ［Ｎ］＋１に、ＰａｒｔＧ［ＰａｒｔＮｕｍ］の値をＳＴｓ［Ｎ］が属する関数のEXITノードに設定する（ステップＳ３００３）。
【０１９６】
次に、経路範囲情報算出部２８０３は、次の区間を設定するために、添え字ＰａｒｔＮｕｍに１を加算するとともに（ステップＳ３００４）、カウンタＮから１を減算し（ステップＳ３００５）、次のスタート時スタックについて処理を繰り返す（ステップＳ３００２）。
【０１９７】
ステップＳ３００２において、カウンタＮがmutualより大きくない場合（ステップＳ３００２：ＮＯ）、経路範囲情報算出部２８０３は、共通ノードの次のノードから、同じ関数上のゴール時スタックに格納されているノードまでを１つの区間として分解する。
【０１９８】
具体的には、経路範囲情報算出部２８０３は、ＰａｒｔＳ［ＰａｒｔＮｕｍ］の値をＳＴｓ［mutual］＋１に、ＰａｒｔＧ［ＰａｒｔＮｕｍ］の値をＳＴｇ［mutual］に設定する（ステップＳ３００６）。また、経路範囲情報算出部２８０３は、次の区間の算出のため、添え字ＰａｒｔＮｕｍに１を加算する（ステップＳ３００７）。
【０１９９】
次に、経路範囲情報算出部２８０３は、ゴール時スタックの共通ノード以降に呼び出された関数のENTRYノードから、ゴールノードまでをそれぞれ１つの区間として分解するために、ステップＳ３００８からステップＳ３０１１までの処理を実行する。
【０２００】
まず、経路範囲情報算出部２８０３は、カウンタＮがゴール時スタックの要素数Ｎｇ以下であるか否かを判断する（ステップＳ３００８）。Ｎｇ以下である場合は（ステップＳ３００８：ＹＥＳ）、経路範囲情報算出部２８０３は、ＰａｒｔＳ［ＰａｒｔＮｕｍ］の値をＳＴｇ［Ｎ］が属する関数のENTRYノードに、ＰａｒｔＧ［ＰａｒｔＮｕｍ］の値をＳＴｓ［Ｎ］に設定する（ステップＳ３００９）。
【０２０１】
次に、経路範囲情報算出部２８０３は、次の区間を設定するために、添え字ＰａｒｔＮｕｍに１を加算するとともに（ステップＳ３０１０）、カウンタＮに１を加算し（ステップＳ３０１１）、次のゴール時スタックについて処理を繰り返す（ステップＳ３００８）。
【０２０２】
ステップＳ３００８において、カウンタＮがＮｇ以下でない場合（ステップＳ３００８：ＮＯ）、分解処理を終了する。
【０２０３】
次に、第５の実施の形態における経路範囲情報算出処理の具体的な例について説明する。ここでは、図３に示したプログラムグラフが入力され（ステップＳ７０１）、このプログラムグラフについて、スタートノードＶｓがノード［2］、ゴールノードＶｇがノード［10］、実行時間Ｔが２５、スタート時のスタック情報ＳＴｓがＳＴｓ＝｛［29］、［13］｝、ゴール時のスタック情報ＳＴｇがＳＴｇ＝｛［29］、［15］｝である実行ログが入力された場合（ステップＳ７０２）を前提として説明する。
【０２０４】
この場合、スタック情報の配列は、ＳＴｓ［０］＝２９、ＳＴｓ［１］＝１３、ＳＴｇ［０］＝２９、ＳＴｇ［１］＝１５、スタート時スタックの要素数Ｎｓ＝2、ゴール時スタックの要素数Ｎｇ＝２である。
【０２０５】
まず、スタート時スタックＳＴｓ＝｛［29］、［13］｝と、ゴール時スタックＳＴｇ＝｛［29］、［15］｝とは、１個目の要素が共通しているので、mutual＝１である（ステップＳ２９０１）。また、ＳＴｓ［２］＝Ｖｓ−１＝１（ノード［1］）、ＳＴｇ［２］＝Ｖｇ＝１０（ノード［10］）を設定する（ステップＳ２９０２）。
【０２０６】
mutual＝１であるので、Ｖｍｓ＝ＳＴｓ［１］＋１＝１４、Ｖｍｇ＝ＳＴｇ［１］＝１５となる（ステップＳ２９０３）。そこで、短絡グラフＧ＊上でノード［14］からノード［15］を結ぶ経路が存在するか否かを判断する（ステップＳ２９０４）。この場合、図３に示すように、ノード［14］からノード［15］までの経路が存在するので（ステップＳ２９０４：ＹＥＳ）、分解処理を実行する。
【０２０７】
分解処理では、スタートノードＶｓおよびゴールノードＶｇの間は、ノード［2］からノード［6］、ノード［14］からノード［15］、ノード［7］からノード［10］の３区間に分解される（ステップＳ２９０５）。これらの各区間の実行時間の最短時間は、順に１０、１、１２であり、各区間の境界のCALL、RETURN辺の長さも考慮すると、ノード［2］−ノード［14］−ノード［15］−ノード［10］を結ぶ最短時間minDistは、minDist＝１０＋１＋１＋１＋１２＝２５である（ステップＳ２９０６）。
【０２０８】
次に、区間ごとの経路範囲を求める。まずノード［2］からノード［6］間においては、Ｔ−minDist＋（各区間の最短時間）（＝２５−２５＋１０＝１０）以内で結ぶ経路である｛［2］、［5］、［6］｝を経路範囲情報Ｒに追加する。次に、ノード［14］からノード［15］間においては、実行時間１（＝２５−２５＋１）以内で結ぶ経路である｛［14］、［15］｝を経路範囲情報Ｒに追加する。最後に、ノード［7］からノード［10］間においては、実行時間１２（＝２５−２５＋１２）以内で結ぶ経路である｛［7］、［8］、［9］、［10］、［18］、［19］、［21］、［22］、［23］｝を経路範囲情報Ｒに追加する（ステップＳ２９０７）。
【０２０９】
次に、mutualから１を減算しmutual＝０とし処理を繰り返す（ステップＳ２９０９、ステップＳ２９１０）。この場合は、Ｖｍｓ＝ＳＴｓ［０］＋１＝３０、Ｖｍｇ＝ＳＴｇ［０］＝２９となり（ステップＳ２９０３）、短絡グラフＧ＊上でノード［30］からノード［29］を結ぶ経路が存在しないため（ステップＳ２９０４：ＮＯ）、経路範囲情報算出処理が終了する。
【０２１０】
以上の処理により、スタートノード［2］、ゴールノード［10］、を実行時間２５以内で結ぶ経路範囲として、Ｒ＝｛［2］、［5］、［6］、［7］、［8］、［9］、［10］、［14］、［15］、［18］、［19］、［21］、［22］、［23］｝が得られる。
【０２１１】
図３１は、このようにして得られた経路範囲情報をプログラムグラフ上で表した説明図である。同図においては、スタートノード［2］とゴールノード［10］とを実行時間２５で結ぶ経路の範囲が、ノード内を黒く塗りつぶされたノードとして表されている。スタート時のスタック情報のみを利用して算出した経路範囲を示す図２７と比較すると、ノード［3］が経路範囲から除外され、この分だけ経路範囲情報の推定の精度が向上していることが分かる。
【０２１２】
このように、第５の実施の形態にかかる実行情報推定装置２８００では、ログ出力区間のスタート時だけでなく、ゴール時のスタック情報も利用して経路範囲情報を算出することができるため、さらに高精度に実行情報を推定することができる。
【０２１３】
（第６の実施の形態）
第６の実施の形態にかかる実行情報推定装置は、連続する区間について実行ログが得られた場合に、先に得られた実行ログの情報から、次の区間のスタート時のスタック情報の候補を算出し、算出したスタック情報の候補を利用して次の区間についての経路範囲情報を算出するものである。
【０２１４】
図３２は、第６の実施の形態にかかる実行情報推定装置３２００の構成を示すブロック図である。同図に示すように、実行情報推定装置３２００は、グラフ入力受付部１０１と、ログ入力受付部１０２と、経路範囲情報算出部３２０３と、ドミナント情報算出部１７０４と、プロファイル情報算出部２００５と、推定実行情報記憶部２１１０とを備えている。
【０２１５】
第６の実施の形態においては、経路範囲情報算出部３２０３の機能が第４の実施の形態と異なっている。その他の構成および機能は、第４の実施の形態にかかる実行情報推定装置２４００の構成を表すブロック図である図２４と同様であるので、同一符号を付し、ここでの説明は省略する。
【０２１６】
経路範囲情報算出部３２０３は、連続する区間の実行ログが得られたときであって、後の区間についてのスタート時のスタック情報が実行ログに含まれない場合であっても、先の区間についての実行ログから、後の区間についてのスタート時のスタック情報の候補を算出し、算出したスタック情報により高精度に経路範囲情報を算出するものである。経路範囲情報算出処理の詳細については後述する。
【０２１７】
次に、このように構成された第６の実施の形態にかかる実行情報推定装置３２００による実行情報推定処理について説明する。第６の実施の形態における実行情報推定処理の全体の流れは、第４の実施の形態における実行情報推定処理の全体の流れを示す図７と同様であるのでその説明を省略する。
【０２１８】
第６の実施の形態においては、図７のステップＳ７０４に示した経路範囲情報算出処理の詳細が、第４の実施の形態と異なっている。以下では、経路範囲情報算出処理の詳細について説明する。
【０２１９】
図３３は、第６の実施の形態における経路範囲情報算出処理の全体の流れを示すフローチャートである。第６の実施の形態においては、スタックに保存されているノードを検索する前に、次の区間のスタート時スタックの候補を取得するスタック候補情報取得処理を追加した点が（ステップＳ３３０４）、第４の実施の形態と異なっている。
【０２２０】
その他の処理（ステップＳ３３０１〜ステップＳ３３０３、ステップＳ３３０５〜ステップＳ３３１２）は、第４の実施の形態と同様であるので（ステップＳ２６０１〜ステップＳ２６０３、ステップＳ２６０４〜ステップＳ２６１１）、その説明を省略する。
【０２２１】
次に、ステップＳ３３０４におけるスタック候補情報取得処理の詳細について説明する。図３４は、スタック候補情報取得処理の全体の流れを示すフローチャートである。
【０２２２】
まず、経路範囲情報算出部３２０３は、経路範囲情報Ｒ上に制限した短絡グラフ（以下、Ｇ＊ｒと表す）上で、スタートノードＶｓとゴールノードＶｇとを実行時間Ｔ以内で結ぶ経路（以下、ｐａｔｈと表す）を検索する（ステップＳ３４０１）。
【０２２３】
次に、経路範囲情報算出部３２０３は、スタート時のスタックＳＴｓをＳＴにコピーし、さらにｐａｔｈに沿ってスタートノードＶｓからゴールノードＶｇをたどり、次のノードがENTRYノードであるCALLノード（ｍ）があれば、順次ＳＴの末尾に追加する（ステップＳ３４０２）。経路範囲情報算出部３２０３は、こうして得られたＳＴをスタック候補情報に追加する（ステップＳ３４０３）。
【０２２４】
次に、経路範囲情報算出部３２０３は、ステップＳ３４０１において検索したすべてのｐａｔｈについての処理が完了したか否かを判断する（ステップＳ３４０４）。
【０２２５】
すべてのｐａｔｈを処理していない場合は（ステップＳ３４０４：ＮＯ）、次のｐａｔｈについて処理を繰り返す（ステップＳ３４０２）。すべてのｐａｔｈを処理した場合は（ステップＳ３４０４：ＹＥＳ）、スタック候補情報取得処理を終了する。
【０２２６】
このようにして得られたスタック候補情報は、次のログ出力区間におけるスタック情報として利用できるため、検索するノードを限定し（ステップＳ３３０５）、経路範囲情報の推定精度を向上させることができる。なお、最初のログ出力区間についてスタート時スタック情報が得られない場合は、第１の実施の形態と同様の手法により、可能性のあるすべてのノードを検索して（ステップＳ１２０４）経路範囲情報を算出すればよい。
【０２２７】
次に、第６の実施の形態におけるスタック候補情報取得処理の具体的な例について説明する。ここでは、図３に示したプログラムグラフが入力され（ステップＳ７０１）、このプログラムグラフについて、スタートノードＶｓがノード［2］、ゴールノードＶｇがノード［10］、実行時間Ｔが２５、スタート時のスタック情報ＳＴｓがＳＴｓ＝｛［29］、［13］｝である実行ログが入力された場合（ステップＳ７０２）を前提として説明する。
【０２２８】
この場合、ステップＳ３３０３の時点において、スタート時スタックがＳＴｓ＝｛［29、［13］｝であり、経路範囲情報ＲとしてＲ＝｛［2］、［3］、［7］、［8］、［9］、［10］｝が得られている。Ｒ＝｛［2］、［3］、［7］、［8］、［9］、［10］｝の場合に、グラフＧ＊ｒ上で、スタートノードＶｓからゴールノードＶｇに実行時間Ｔ（＝２５）以内で結ぶ経路は、ｐａｔｈ＝｛［2］-［3］-［7］-［8］-［9］-［10］｝のみである（ステップＳ３４０１）。
【０２２９】
また、ｐａｔｈ内で次のノードがENTRYノードであるCALLノードはノード［3］のみである。ここで、ノード［8］はCALLノードだが、Ｇ＊ｒ上では次のノード［9］がCALLBACKノードであるため該当しない。従って、スタート時のスタックＳＴｓにノード［3］を加えた｛［29］、［13］、［3］｝がスタック候補情報に追加される（ステップＳ３４０２、ステップＳ３４０３）。
【０２３０】
次に、再帰的に呼ばれた２回目のステップＳ３３０３の時点において、スタート時スタックがＳＴｓ＝［29］であり、経路範囲情報ＲとしてＲ＝｛［14］、［15］、［7］、［8］、［9］、［10］｝が得られている。Ｒ＝｛［14］、［15］、［7］、［8］、［9］、［10］｝の場合に、グラフＧ＊ｒ上で、スタートノードＶｓ（ノード［14］）からゴールノードＶｇを実行時間Ｔ（＝２５）以内で結ぶ経路は、ｐａｔｈ＝［14］-［15］-［7］-［8］-［9］-［10］のみである（ステップＳ３４０１）。
【０２３１】
また、ｐａｔｈ内で次のノードがENTRYノードであるCALLノードはノード［15］のみである。従って、スタート時のスタックＳＴｓにノード［15］を加えた｛［29］、［15］｝がスタック候補情報に追加される（ステップＳ３４０２、ステップＳ３４０３）。この結果、スタック候補情報として｛｛［29］、［13］、［3］｝、｛［29］、［15］｝｝が得られる。
【０２３２】
このように、第６の実施の形態にかかる実行情報推定装置３２００では、連続する区間について実行ログが得られた場合に、先に得られた実行ログの情報から、次の区間のスタート時のスタック情報の候補を算出し、算出したスタック情報の候補を利用して次の区間についての経路範囲情報を算出することができる。このため、スタート時のスタック情報が得られる場合と同様に、スタック情報が得られない場合と比較してより高精度に実行情報を推定することができる。
【０２３３】
第１〜第６の実施の形態にかかる実行情報推定装置は、ＣＰＵなどの制御装置と、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）やＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）などの記憶装置と、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）ドライブ装置などの外部記憶装置と、ディスプレイ装置などの表示装置と、キーボードやマウスなどの入力装置を備えており、通常のコンピュータを利用したハードウェア構成となっている。
【０２３４】
第１〜第６の実施の形態にかかる実行情報推定装置で実行される実行情報推定プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅｃｏｒｄａｂｌｅ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【０２３５】
また、第１〜第６の実施の形態にかかる実行情報推定装置で実行される実行情報推定プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また、第１〜第６の実施の形態にかかる実行情報推定装置で実行される実行情報推定プログラムをインターネット等のネットワーク経由で提供または配布するように構成しても良い。
【０２３６】
また、第１〜第６の実施の形態の実行情報推定プログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。
【０２３７】
第１〜第６の実施の形態にかかる実行情報推定装置で実行される実行情報推定プログラムは、上述した各部（グラフ入力受付部、ログ入力受付部、経路範囲情報算出部、ドミナント情報算出部、プロファイル情報算出部）を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ（プロセッサ）が上記記憶媒体から実行情報推定プログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、上述した各部が主記憶装置上に生成されるようになっている。
【産業上の利用可能性】
【０２３８】
以上のように、本発明にかかる実行情報推定装置、実行情報推定方法および実行情報推定プログラムは、間欠的に出力される実行ログからプログラムの実行情報を推定する実行情報推定装置に適している。
【図面の簡単な説明】
【０２３９】
【図１】第１の実施の形態にかかる実行情報推定装置の構成を示すブロック図である。
【図２】プログラムグラフ記憶部に格納されたプログラムグラフの構成要素を示す説明図である。
【図３】プログラムグラフ記憶部に格納されたプログラムグラフのデータ構造の一例を示す説明図である。
【図４】プログラムの実行経路をプログラムグラフ上で表した例を示す説明図である。
【図５】実行ログ記憶部に格納された実行ログのデータ構造の一例を示す説明図である。
【図６】推定実行情報記憶部に格納された経路範囲情報のデータ構造の一例を示す説明図である。
【図７】第１の実施の形態における実行情報推定処理の全体の流れを示すフローチャートである。
【図８】経路範囲情報算出の前処理の全体の流れを示すフローチャートである。
【図９】短絡グラフの一例を示した説明図である。
【図１０】算出したENTRYノードからの最短時間の値を、各ノードの中に記載したプログラムグラフの一例を表す説明図である。
【図１１】算出したEXITノードまでの最短時間の値を、各ノードの中に記載したプログラムグラフの一例を表す説明図である。
【図１２】経路範囲情報算出処理の全体の流れを示すフローチャートである。
【図１３】算出したＶｓからの最短時間の値を、各ノードの中に記載したプログラムグラフの一例を表す説明図である。
【図１４】算出したＶｇまでの最短時間の値を、各ノードの中に記載したプログラムグラフの一例を表す説明図である。
【図１５】経路範囲情報をプログラムグラフ上で表した説明図である。
【図１６】実行情報出力装置によって出力される実行情報の表示画面の一例を示す説明図である。
【図１７】第２の実施の形態にかかる実行情報推定装置の構成を示すブロック図である。
【図１８】第２の実施の形態におけるドミナント情報算出処理の全体の流れを示すフローチャートである。
【図１９】ドミナント情報の一例をプログラムグラフ上に表した説明図である。
【図２０】第３の実施の形態にかかる実行情報推定装置の構成を示すブロック図である。
【図２１】プロファイル情報のデータ構造の一例を示す説明図である。
【図２２】第３の実施の形態におけるドミナント情報算出処理の全体の流れを示すフローチャートである。
【図２３】実行情報出力装置によって出力される実行情報の表示画面の一例を示す説明図である。
【図２４】第４の実施の形態にかかる実行情報推定装置の構成を示すブロック図である。
【図２５】実行ログ記憶部に格納された実行ログのデータ構造の一例を示す説明図である。
【図２６】第４の実施の形態における経路範囲情報算出処理の全体の流れを示すフローチャートである。
【図２７】経路範囲情報をプログラムグラフ上で表した説明図である。
【図２８】第５の実施の形態にかかる実行情報推定装置の構成を示すブロック図である。
【図２９】第５の実施の形態における経路範囲情報算出処理の全体の流れを示すフローチャートである。
【図３０】第５の実施の形態における分解処理の全体の流れを示すフローチャートである。
【図３１】経路範囲情報をプログラムグラフ上で表した説明図である。
【図３２】第６の実施の形態にかかる実行情報推定装置の構成を示すブロック図である。
【図３３】第６の実施の形態における経路範囲情報算出処理の全体の流れを示すフローチャートである。
【図３４】スタック候補情報取得処理の全体の流れを示すフローチャートである。
【符号の説明】
【０２４０】
１００  実行情報推定装置
１０１  グラフ入力受付部
１０２  ログ入力受付部
１０３  経路範囲情報算出部
１１０  推定実行情報記憶部
１１１  経路範囲情報
１２０  プログラム解析装置
１２１  プログラムグラフ記憶部
１３０  プログラム実行装置
１３１  プログラム記憶部
１３１ａ  ソースコード
１３１ｂ  オブジェクトコード
１３１ｃ  実行コード
１４０  実行ログ収集装置
１４１  実行ログ記憶部
１５０  実行情報出力装置
２０１、２０２、２０３、２０４、２０５、２０６  ノード
５１１  実行時刻情報
５１２  実行状態情報
１６００  表示画面
１６０１  ノード
１７００  実行情報推定装置
１７０４  ドミナント情報算出部
１７１０  推定実行情報記憶部
１７１２  ドミナント情報
２０００  実行情報推定装置
２００５  プロファイル情報算出部
２１１０  推定実行情報記憶部
２３００  表示画面
２３０１  ノード
２４００  実行情報推定装置
２４０３  経路範囲情報算出部
２４４１  実行ログ記憶部
２５１２  実行状態情報
２５１２ａ  スタック候補情報
２８００  実行情報推定装置
２８０３  経路範囲情報算出部
３２００  実行情報推定装置
３２０３  経路範囲情報算出部
【図１】
0004468256.tif 000002
【図２】
0004468256.tif 000003
【図３】
0004468256.tif 000004
【図４】
0004468256.tif 000005
【図５】
0004468256.tif 000006
【図６】
0004468256.tif 000007
【図７】
0004468256.tif 000008
【図８】
0004468256.tif 000009
【図９】
0004468256.tif 000010
【図１０】
0004468256.tif 000011
【図１１】
0004468256.tif 000012
【図１２】
0004468256.tif 000013
【図１３】
0004468256.tif 000014
【図１４】
0004468256.tif 000015
【図１５】
0004468256.tif 000016
【図１６】
0004468256.tif 000017
【図１７】
0004468256.tif 000018
【図１８】
0004468256.tif 000019
【図１９】
0004468256.tif 000020
【図２０】
0004468256.tif 000021
【図２１】
0004468256.tif 000022
【図２２】
0004468256.tif 000023
【図２３】
0004468256.tif 000024
【図２４】
0004468256.tif 000025
【図２５】
0004468256.tif 000026
【図２６】
0004468256.tif 000027
【図２７】
0004468256.tif 000028
【図２８】
0004468256.tif 000029
【図２９】
0004468256.tif 000030
【図３０】
0004468256.tif 000031
【図３１】
0004468256.tif 000032
【図３２】
0004468256.tif 000033
【図３３】
0004468256.tif 000034
【図３４】
0004468256.tif 000035