(57)【要約】      （修正有）【課題】開発者がプログラムのパフォーマンスの解析を行う場合、メソッド単位での解析では、思うような効果が得られない場合がある。そこで、プログラムの文脈に基づいて類似するロジックを検出することを可能にする方法を提供する。【解決手段】プログラムに含まれるアルゴリズムをグループ化し、該プログラムの解析を支援するための方法である。該方法は、上記アルゴリズムを有向グラフに変換するステップと、上記変換された有向グラフがコンピュータ・システムの記憶部に記憶されている代表有向グラフに類似しているかどうかを判定するステップと、上記類似しているかどうかの判定に応じて、上記記憶部に記憶されているグループのうちから、上記変換された有向グラフの属するグループを決定するステップとを含む。【選択図】図２
2010140434.tif 000002
【特許請求の範囲】
【請求項１】
プログラムに含まれるアルゴリズムをグループ化し、該プログラムの解析を支援するための方法であって、
前記アルゴリズムを有向グラフに変換するステップであって、該有向グラフは複数のノードと該ノードを接続するエッジとを含む、前記変換するステップと、
前記変換された有向グラフがコンピュータ・システムの記憶部に記憶されている代表有向グラフに類似しているかどうかを判定するステップであって、該代表有向グラフは、前記グループに属する有向グラフのうち、前記ノードの数が最も少ない有向グラフである、前記判定するステップと、
前記類似しているかどうかの判定に応じて、前記記憶部に記憶されているグループのうちから、前記変換された有向グラフの属するグループを決定するステップと
を含む、前記方法。
【請求項２】
前記判定するステップが、
前記変換された有向グラフが、少なくとも２以上のノードを含み、並びに第１のノード、第２のノード、及び前記第１のノードから前記第２のノードへの経路を含むこと、且つ
前記代表有向グラフが、少なくとも２以上のノードを含み、並びに第３のノード、第４のノード、及び前記第３のノードから前記第４のノードへの経路を含むこと、且つ
前記第３のノードは前記第１のノードに対応すること、且つ
前記第４のノードは前記第２のノードに対応すること
に応じて、
前記変換された有向グラフが前記代表有向グラフに類似していると判定するステップを含む、請求項１に記載の方法。
【請求項３】
前記判定するステップが、
前記変換された有向グラフ及び前記代表有向グラフのいずれか一方の有向グラフが、他方の有向グラフに含まれるノードに対応するノード全てを含むこと、且つ前記他方の有向グラフに含まれるノード間の全ての経路が、前記一方の有向グラフに含まれるノード間の一部又は全部の経路に対応することに応じて、
前記変換された有向グラフが前記代表有向グラフに類似していると判定するステップを含む、請求項１に記載の方法。
【請求項４】
前記判定するステップが、
前記類似していると判定された前記変換された有向グラフ及び前記代表有向グラフの類似度を計算し、該類似度が閾値を超えた場合、前記変換された有向グラフが前記代表有向グラフにより類似していると判定するステップを含む、請求項３に記載の方法。
【請求項５】
前記類似度を計算することが、
前記類似していると判定された前記変換された有向グラフ及び前記代表有向グラフの両方に含まれる同一のノード及び該ノード間の経路の少なくとも１つの数と、
前記変換された有向グラフ又は前記代表有向グラフのどちらか一方に含まれるノード及び該ノードを始点又は終点とする経路の少なくとも１つの数と
に基づいて計算することを含む、請求項４に記載の方法。
【請求項６】
前記類似度を計算することが、Ｎ１÷（Ｎ１＋Ｎ２）×１００によって計算することを含み、
ここで、Ｎ１は、前記類似していると判定された前記変換された有向グラフ及び前記代表有向グラフの両方に含まれる同一のノード及び該ノード間の経路の少なくとも１つの数であり、
Ｎ２は、前記変換された有向グラフ又は前記代表有向グラフのどちらか一方に含まれるノード及び該ノードを始点又は終点とする経路の少なくとも１つの数である、請求項５に記載の方法。
【請求項７】
前記判定するステップが、
前記変換された有向グラフ及び前記代表有向グラフそれぞれに含まれるノード及びエッジの少なくとも１つをビットマップに変換するステップと、
前記ビットマップ間に包含関係がないことに応じて、類似していないと判定するステップと
を含む、請求項１に記載の方法。
【請求項８】
前記記憶部に記憶されている前記決定されたグループの実行頻度と前記変換された有向グラフの実行頻度とに基づきグループの実行頻度を計算するステップ
をさらに含む、請求項１に記載の方法。
【請求項９】
前記計算するステップが、前記記憶部に記憶されている前記決定されたグループの実行頻度から計算される値と前記変換された有向グラフの実行頻度から計算される値とから前記グループの実行頻度を計算するステップを含む、請求項８に記載の方法。
【請求項１０】
前記グループごとに、前記代表有向グラフに対応するアルゴリズムと該代表有向グラフの属するグループの実行頻度とを表示するステップをさらに含む、請求項８に記載の方法。
【請求項１１】
前記グループごとに、前記実行頻度の降順で、前記代表有向グラフに対応するアルゴリズムを表示するステップをさらに含む、請求項１０に記載の方法。
【請求項１２】
前記表示するステップが、前記グループごとに代表有向グラフに対応する識別子をさらに表示するステップをさらに含む、請求項１１に記載の方法。
【請求項１３】
前記変換された有向グラフが前記代表有向グラフに類似していることに応じて、該変換された有向グラフの実行頻度を前記決定されたグループに登録するステップをさらに含む、請求項１に記載の方法。
【請求項１４】
前記変換された有向グラフ及び前記決定されたグループに属する前記代表有向グラフのうち、前記ノードの数が最も少ない有向グラフを前記決定されたグループに属する代表有向グラフとして更新するステップをさらに含む、請求項１３に記載の方法。
【請求項１５】
前記登録するステップが、
前記変換された有向グラフが前記代表有向グラフに類似していないことに応じて、前記変換された有向グラフ及び該変換された有向グラフの実行頻度を新たなグループの代表有向グラフ及び該新たなグループの実行頻度とするステップをさらに含む、請求項１３に記載の方法。
【請求項１６】
前記登録するステップが、
前記新たなグループの代表有向グラフ及び実行頻度を前記記憶部に記憶するステップをさらに含む、請求項１５に記載の方法。
【請求項１７】
前記判定するステップが、前記記憶部に記憶されている第１のグループに属する代表有向グラフ（以下、第１の代表有向グラフ）が前記記憶部に記憶されている第２のグループに属する代表有向グラフ（以下、第２の代表有向グラフ）に類似しているかどうかをさらに判定する、請求項１に記載の方法。
【請求項１８】
前記第１の代表有向グラフが前記第２の代表有向グラフに類似していることに応じて、前記第１のグループと前記第２のグループとを併合するステップをさらに含む、請求項１７に記載の方法。
【請求項１９】
前記第１の代表有向グラフが前記第２の代表有向グラフに類似していることに応じて、前記第１のグループと前記第２のグループとを併合し、前記第１の代表有向グラフ及び前記第２の代表有向グラフのうち、前記ノードの数が最も少ない代表有向グラフを併合されたグループに属する代表有向グラフとするステップと、
前記第１のグループの実行頻度と、前記第２のグループの実行頻度とに基づき、前記併合されたグループの実行頻度を計算するステップと
をさらに含む、請求項１７に記載の方法。
【請求項２０】
前記グループの数が所定の値になることに応じて、前記記憶部に記憶されている第１のグループと第２のグループとを併合するステップをさらに含む、請求項１に記載の方法。
【請求項２１】
前記グループの数が所定の値になることに応じて、グループの実行頻度が最小であるグループを前記記憶部から削除するステップをさらに含む、請求項８に記載の方法。
【請求項２２】
前記変換するステップが、前記有向グラフを前記アルゴリズムにさらに変換するステップを含む、請求項１に記載の方法。
【請求項２３】
プログラムに含まれるアルゴリズムをグループ化し、該プログラムの解析を支援するための方法であって、
前記アルゴリズムを有向グラフに変換するステップであって、該有向グラフは複数のノードと該ノードを接続するエッジとを含む、前記変換するステップと、
前記変換された有向グラフがコンピュータ・システムの記憶部に記憶されている代表有向グラフに類似しているかどうかを判定するステップであって、該代表有向グラフは、前記グループに属する有向グラフのうち、前記ノードの数が最も少ない有向グラフである、前記判定するステップと、
前記類似しているかどうかの判定に応じて、前記記憶部に記憶されているグループのうちから、前記変換された有向グラフの属するグループを決定するステップと、
前記記憶部に記憶されている前記決定されたグループの実行頻度と前記変換された有向グラフの実行頻度とに基づきグループの実行頻度を計算するステップと、
前記グループごとに、前記代表有向グラフに対応するアルゴリズムと該代表有向グラフの属するグループの実行頻度とを表示するステップと、
を含む、前記方法。
【請求項２４】
コンピュータ・システムに、請求項１〜２３のいずれか一項に記載の方法の各ステップを実行させるコンピュータ・プログラム。
【請求項２５】
プログラムに含まれるアルゴリズムをグループ化し、該プログラムの解析を支援するためのコンピュータ・システムであって、
前記アルゴリズムを有向グラフに変換する変換部であって、該有向グラフは複数のノードと該ノードを接続するエッジとを含む、前記変換部と、
少なくとも１のグループに属する少なくとも１の有向グラフを記憶する記憶部と、
前記変換された有向グラフが代表有向グラフに類似しているかどうかを判定する判定部であって、該代表有向グラフは、前記グループに属する有向グラフのうち、前記ノードの数が最も少ない有向グラフである、前記判定部と、
前記類似しているかどうかの判定に応じて、前記記憶部に記憶されているグループのうちから、前記変換された有向グラフの属するグループを決定する決定部と
を含む、前記コンピュータ・システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラムの解析を支援するための方法、並びにそのコンピュータ・プログラム及びコンピュータ・システムに関する。
【背景技術】
【０００２】
プログラムが巨大化するにつれて、プログラムのパフォーマンス改善が望まれている。
開発者がプログラムのパフォーマンスの解析を行う方法として、実行頻度の高いメソッドを目視で調査する方法が用いられている。しかし、上記したように最近のプログラムは巨大化しているので、実行頻度が飛び抜けて高いメソッドがないという状況がよく見られる。また、上記方法の問題点の１つは、開発者がメソッド単位でプログラムを調査しているということである。
【０００３】
これに対して、プログラム中の似ているコードを収集し、最適化の解析を行う方法がある。プログラム中の似ているコードを解析する方法として、下記の２つの方法が挙げられる。
Ａ．プログラムの実行特性に基づいて類似度を判定する方法。
プログラムの実行特性は、例えば、ＣＰＩ（Cycles Per Instruction）、命令の数及び分岐の特性である。
Ｂ．ソースコードの特性に基づく方法。
ソースコードの特性は、例えば、行数、変数の数、演算子の数である。
ソースコードの特性に基づく方法として、例えば、ソースコードをトークンに分割し、ユーザ定義名及び定数を特定の記号に置き換え、一致部分を検出する方法がある。該方法の代表的な例は、ＣＣＦｉｎｄｅｒである。
【０００４】
下記非特許文献１は、ＣＣＦｉｎｄｅｒを記載する。ＣＣＦｉｎｄｅｒでは、ソースコードをトークンごとに判別しているので、名前及び定数値などのパラメータの違いに対応できる。しかし、ＣＣＦｉｎｄｅｒでは、ロジックの違いには対応できない。例えば、ＣＣＦｉｎｄｅｒでは、forループで書かれたプログラムがwhileループを使って書き換えられた場合、違うロジックとして扱われる。
【０００５】
【非特許文献１】神谷年洋、“コードクローンをテンプレートとして用いて識別子のバリエーションを求める手法の提案”、[online]、平成２０年５月３０日、独立行政法人産業技術総合研究所、[平成２０年１１月２５日検索]、インターネット＜ＵＲＬ：http://www.ccfinder.net/doc/vaci/sigss-20080530.pdf＞
【発明の開示】
【発明が解決しようとする課題】
【０００６】
開発者がプログラムのパフォーマンスの解析を行う場合、メソッド単位での解析では、思うような効果が得られない場合がある。そこで、プログラムの文脈（context）に基づいて類似するロジックを検出することを可能にする方法が求められている。
【課題を解決するための手段】
【０００７】
本発明は、プログラムに含まれるアルゴリズムをグループ化し、該プログラムの解析を支援するための方法を提供する。該方法は、コンピュータ・システムに下記ステップを実行させる。該ステップは、
上記アルゴリズムを有向グラフに変換するステップであって、該有向グラフは複数のノードと該ノードを接続するエッジとを含む、上記変換するステップと、
上記変換された有向グラフが上記コンピュータ・システムの記憶部に記憶されている代表有向グラフに類似しているかどうかを判定するステップであって、該代表有向グラフは、上記グループに属する有向グラフのうち、上記ノードの数が最も少ない有向グラフである、上記判定するステップと、
上記類似しているかどうかの判定に応じて、上記記憶部に記憶されているグループのうちから、上記変換された有向グラフの属するグループを決定するステップと
を含む。
【０００８】
本発明の１つの実施態様では、上記判定するステップが、
上記変換された有向グラフが、少なくとも２以上のノードを含み、並びに第１のノード、第２のノード、及び上記第１のノードから上記第２のノードへの経路を含むこと、且つ
上記代表有向グラフが、少なくとも２以上のノードを含み、並びに第３のノード、第４のノード、及び上記第３のノードから上記第４のノードへの経路を含むこと、且つ、
上記第３のノードは上記第１のノードに対応すること、且つ
上記第４のノードは上記第２のノードに対応すること
に応じて、
上記変換された有向グラフが上記代表有向グラフに類似していると判定するステップを含む。
【０００９】
本発明の１つの実施態様では、上記判定するステップが、
上記変換された有向グラフ及び上記代表有向グラフのいずれか一方の有向グラフが、他方の有向グラフに含まれるノードに対応するノード全てを含むこと、且つ上記他方の有向グラフに含まれるノード間の全ての経路が、上記一方の有向グラフに含まれるノード間の一部又は全部の経路に対応することに応じて、
上記変換された有向グラフが上記代表有向グラフに類似していると判定するステップを含む。
【００１０】
本発明の１つの実施態様では、上記判定するステップが、
上記類似していると判定された上記変換された有向グラフ及び上記代表有向グラフの類似度を計算し、該類似度が閾値を超えた場合、上記変換された有向グラフが上記代表有向グラフにより類似していると判定するステップを含む。
【００１１】
本発明の１つの実施態様では、上記類似度を計算することが、
上記類似していると判定された上記変換された有向グラフ及び上記代表有向グラフの両方に含まれる同一のノード及び該ノード間の経路の少なくとも１つの数と、
上記変換された有向グラフ又は上記代表有向グラフのどちらか一方に含まれるノード及び該ノードを始点又は終点とする経路の少なくとも１つの数と
に基づいて計算することを含む。
【００１２】
本発明の１つの実施態様では、上記類似度を計算することが、Ｎ１÷（Ｎ１＋Ｎ２）×１００によって計算することを含む。ここで、Ｎ１は、上記類似していると判定された上記変換された有向グラフ及び上記代表有向グラフの両方に含まれる同一のノード及び該ノード間の経路の少なくとも１つの数であり、Ｎ２は、上記変換された有向グラフ又は上記代表有向グラフのどちらか一方に含まれるノード及び該ノードを始点又は終点とする経路の少なくとも１つの数である。
【００１３】
本発明の１つの実施態様では、上記判定するステップが、
上記変換された有向グラフ及び上記代表有向グラフそれぞれに含まれるノード及びエッジの少なくとも１つをビットマップに変換するステップと、
上記ビットマップ間に包含関係がないことに応じて、類似していないと判定するステップと
を含む。
【００１４】
本発明の１つの実施態様では、上記方法は、コンピュータ・システムに下記ステップをさらに実行させることを含む。該ステップは、上記記憶部に記憶されている上記決定されたグループの実行頻度と上記変換された有向グラフの実行頻度とに基づきグループの実行頻度を計算するステップを含む。
【００１５】
本発明の１つの実施態様では、上記計算するステップが、上記記憶部に記憶されている上記決定されたグループの実行頻度から計算される値と上記変換された有向グラフの実行頻度から計算される値とから上記グループの実行頻度を計算するステップを含む。
【００１６】
本発明の１つの実施態様では、上記方法は、コンピュータ・システムに下記ステップをさらに実行させることを含む。該ステップは、上記グループごとに、上記代表有向グラフに対応するアルゴリズムと該代表有向グラフの属するグループの実行頻度とを表示するステップを含む。
【００１７】
本発明の１つの実施態様では、上記方法は、コンピュータ・システムに下記ステップをさらに実行させることを含む。該ステップは、上記グループごとに、上記実行頻度の降順で、上記代表有向グラフに対応するアルゴリズムを表示するステップを含む。
【００１８】
本発明の１つの実施態様では、上記表示するステップが、上記グループごとに代表有向グラフに対応する識別子をさらに表示するステップをさらに含む。
【００１９】
本発明の１つの実施態様では、上記方法は、コンピュータ・システムに下記ステップをさらに実行させることを含む。該ステップは、上記変換された有向グラフが上記代表有向グラフに類似していることに応じて、該変換された有向グラフの実行頻度を上記決定されたグループに登録するステップを含む。
【００２０】
本発明の１つの実施態様では、上記方法は、コンピュータ・システムに下記ステップをさらに実行させることを含む。該ステップは、上記変換された有向グラフ及び上記決定されたグループに属する上記代表有向グラフのうち、上記ノードの数が最も少ない有向グラフを上記決定されたグループに属する代表有向グラフとして更新するステップを含む。
【００２１】
本発明の１つの実施態様では、上記登録するステップが、
上記変換された有向グラフが上記代表有向グラフに類似していないことに応じて、上記変換された有向グラフ及び該変換された有向グラフの実行頻度を新たなグループの代表有向グラフ及び該新たなグループの実行頻度とするステップをさらに含む。
【００２２】
本発明の１つの実施態様では、上記登録するステップが、
上記新たなグループの代表有向グラフ及び実行頻度を上記記憶部に記憶するステップをさらに含む。
【００２３】
本発明の１つの実施態様では、上記判定するステップが、上記記憶部に記憶されている第１のグループに属する代表有向グラフ（以下、第１の代表有向グラフ）が上記記憶部に記憶されている第２のグループに属する代表有向グラフ（以下、第２の代表有向グラフ）に類似しているかどうかをさらに判定する。
【００２４】
本発明の１つの実施態様では、上記第１の代表有向グラフが上記第２の代表有向グラフに類似していることに応じて、上記第１のグループと上記第２のグループとを併合するステップをさらに含む。
【００２５】
本発明の１つの実施態様では、上記方法は、コンピュータ・システムに下記ステップをさらに実行させることを含む。該ステップは、
上記第１の代表有向グラフが上記第２の代表有向グラフに類似していることに応じて、上記第１のグループと上記第２のグループとを併合し、上記第１の代表有向グラフ及び上記第２の代表有向グラフのうち、上記ノードの数が最も少ない代表有向グラフを併合されたグループに属する代表有向グラフとするステップと、
上記第１のグループの実行頻度と、上記第２のグループの実行頻度とに基づき、上記併合されたグループの実行頻度を計算するステップと
を含む。
【００２６】
本発明の１つの実施態様では、上記方法は、コンピュータ・システムに下記ステップをさらに実行させることを含む。該ステップは、上記グループの数が所定の値になることに応じて、上記記憶部に記憶されている第１のグループと第２のグループとを併合するステップをさらに含む。
【００２７】
本発明の１つの実施態様では、上記グループの数が所定の値になることに応じて、グループの実行頻度が最小であるグループを上記記憶部から削除するステップをさらに含む。
【００２８】
本発明の１つの実施態様では、上記方法は、コンピュータ・システムに下記ステップをさらに実行させることを含む。該ステップは、上記変換するステップが、上記有向グラフを上記アルゴリズムにさらに変換するステップを含む。
【００２９】
本発明はまた、プログラムに含まれるアルゴリズムをグループ化し、該プログラムの解析を支援するための方法を提供する。該方法は、コンピュータ・システムに下記ステップを実行させる。該ステップは、
上記アルゴリズムを有向グラフに変換するステップであって、該有向グラフは複数のノードと該ノードを接続するエッジとを含む、上記変換するステップと、
上記変換された有向グラフが上記コンピュータ・システムの記憶部に記憶されている代表有向グラフに類似しているかどうかを判定するステップであって、該代表有向グラフは、上記グループに属する有向グラフのうち、上記ノードの数が最も少ない有向グラフである、上記判定するステップと、
上記類似しているかどうかの判定に応じて、上記記憶部に記憶されているグループのうちから、上記変換された有向グラフの属するグループを決定するステップと、
上記記憶部に記憶されている上記決定されたグループに属する有向グラフ全ての実行頻度と上記変換された有向グラフの実行頻度とに基づきグループの実行頻度を計算するステップと、
上記グループごとに、上記代表有向グラフに対応するアルゴリズムと該代表有向グラフの属するグループの実行頻度とを表示するステップと、
を含む。
【００３０】
本発明はまた、コンピュータ・システムに、上記方法のいずれか一つに記載の方法の各ステップを実行させるコンピュータ・プログラムを提供する。
【００３１】
本発明はまた、プログラムに含まれるアルゴリズムをグループ化し、該プログラムの解析を支援するためのコンピュータ・システムを提供する。該コンピュータ・システムは、
上記アルゴリズムを有向グラフに変換する変換部と、
少なくとも１のグループに属する少なくとも１の有向グラフを記憶する記憶部であって、該有向グラフは複数のノードと該ノードを接続するエッジとを含む、上記記憶部と、
上記変換された有向グラフが上記代表有向グラフに類似しているかどうかを判定する判定部であって、該代表有向グラフは、上記グループに属する有向グラフのうち、上記ノードの数が最も少ない有向グラフである、上記判定部と、
上記類似しているかどうかの判定に応じて、上記記憶部に記憶されているグループのうちから、上記変換された有向グラフの属するグループを決定する決定部と
を含む。
【００３２】
本発明の１つの実施態様では、上記判定部が、
上記変換された有向グラフが、少なくとも２以上のノードを含み、並びに第１のノード、第２のノード、及び上記第１のノードから上記第２のノードへの経路を含むこと、且つ
上記代表有向グラフが、少なくとも２以上のノードを含み、並びに第３のノード、第４のノード、及び上記第３のノードから上記第４のノードへの経路を含むこと、且つ
上記第３のノードは上記第１のノードに対応すること、且つ
上記第４のノードは上記第２のノードに対応すること
に応じて、
上記変換された有向グラフが上記代表有向グラフに類似していると判定する。
【００３３】
本発明の１つの実施態様では、上記判定部が、
上記変換された有向グラフ及び上記代表有向グラフのいずれか一方の有向グラフが、他方の有向グラフに含まれるノードに対応するノード全てを含むこと、且つ上記他方の有向グラフに含まれるノード間の全ての経路が、上記一方の有向グラフに含まれるノード間の一部又は全部の経路に対応することに応じて、
上記変換された有向グラフが上記代表有向グラフに類似していると判定する。
【００３４】
本発明の１つの実施態様では、上記判定部が、
上記類似していると判定された上記変換された有向グラフ及び上記代表有向グラフの類似度を計算し、該類似度が閾値を超えた場合、上記変換された有向グラフが上記代表有向グラフにより類似していると判定する。
【００３５】
本発明の１つの実施態様では、上記類似度が、 
上記類似していると判定された上記変換された有向グラフ及び上記代表有向グラフの両方に含まれる同一のノード及び該ノード間の経路の少なくとも１つの数と、
上記変換された有向グラフ又は上記代表有向グラフのどちらか一方に含まれるノード及び該ノードを始点又は終点とする経路の少なくとも１つの数と
に基づいて計算される。
【００３６】
本発明の１つの実施態様では、上記類似度が、Ｎ１÷（Ｎ１＋Ｎ２）×１００によって求められる。ここで、Ｎ１は、上記類似していると判定された上記変換された有向グラフ及び上記代表有向グラフの両方に含まれる同一のノード及び該ノード間の経路の少なくとも１つの数であり、Ｎ２は、上記変換された有向グラフ又は上記代表有向グラフのどちらか一方に含まれるノード及び該ノードを始点又は終点とする経路の少なくとも１つの数である。
【００３７】
本発明の１つの実施態様では、上記判定部が、
上記変換された有向グラフ及び上記代表有向グラフそれぞれに含まれるノード及びエッジの少なくとも１つをビットマップに変換し、
上記ビットマップ間に包含関係がないことに応じて、類似していないと判定する。
【００３８】
本発明の１つの実施態様では、上記コンピュータ・システムは、上記記憶部に記憶されている上記決定されたグループの実行頻度と上記変換された有向グラフの実行頻度とに基づきグループの実行頻度を計算する計算部
をさらに含む。
【００３９】
本発明の１つの実施態様では、上記計算部が、上記記憶部に記憶されている上記決定されたグループの実行頻度から計算される値と上記変換された有向グラフの実行頻度から計算される値とから上記グループの実行頻度を計算する。
【００４０】
本発明の１つの実施態様では、上記コンピュータ・システムは、上記代表有向グラフに対応するアルゴリズムと該代表有向グラフの属するグループの実行頻度とを表示する表示部をさらに含む。
【００４１】
本発明の１つの実施態様では、上記コンピュータ・システムは、上記グループごとに、上記実行頻度の降順で、上記代表有向グラフに対応するアルゴリズムを表示する表示部をさらに含む。
【００４２】
本発明の１つの実施態様では、上記表示部が、上記グループに代表有向グラフに対応する識別子をさらに表示する。
【００４３】
本発明の１つの実施態様では、上記コンピュータ・システムは、上記変換された有向グラフが上記代表有向グラフに類似していることに応じて、該変換された有向グラフの実行頻度を上記決定されたグループに登録する登録部をさらに含む。
【００４４】
本発明の１つの実施態様では、上記コンピュータ・システムは、上記変換された有向グラフ及び上記決定されたグループに属する上記代表有向グラフのうち、上記ノードの数が最も少ない有向グラフを上記決定されたグループに属する代表有向グラフとして更新する更新部をさらに含む。
【００４５】
本発明の１つの実施態様では、上記登録部が、上記変換された有向グラフが上記代表有向グラフに類似していないことに応じて、上記変換された有向グラフ及び該変換された有向グラフの実行頻度を新たなグループの代表有向グラフ及び該新たなグループの実行頻度とする。
【００４６】
本発明の１つの実施態様では、上記登録部が、上記新たなグループの代表有向グラフ及び実行頻度を上記記憶部に記憶する。
【００４７】
本発明の１つの実施態様では、上記判定部が、上記第１の代表有向グラフが上記第２の代表有向グラフに類似しているかどうかをさらに判定する。
【００４８】
本発明の１つの実施態様では、上記第１の代表有向グラフが上記第２の代表有向グラフに類似していることに応じて、上記第１のグループと上記第２のグループとを併合する併合部をさらに含む。
【００４９】
本発明の１つの実施態様では、上記併合部が、
上記第１の代表有向グラフ及び上記第２の代表有向グラフのうち、上記ノードの数が最も少ない代表有向グラフを併合されたグループに属する代表有向グラフとし、
上記計算部が、
上記第１のグループに属する有向グラフ全ての実行頻度と、上記第２のグループに属する有向グラフ全ての実行頻度とに基づき、上記併合されたグループの実行頻度を計算する。
【００５０】
本発明の１つの実施態様では、上記グループの数が所定の値になることに応じて、上記記憶部に記憶されている第１のグループと第２のグループとを併合する併合部をさらに含む。
【００５１】
本発明の１つの実施態様では、上記グループの数が所定の値になることに応じて、グループの実行頻度が最小であるグループを上記記憶部から削除する削除部をさらに含む。
【００５２】
本発明の１つの実施態様では、上記変換部が、上記有向グラフを上記アルゴリズムにさらに変換する。
【発明の効果】
【００５３】
本発明の実施態様によると、プログラムの文脈に基づいて、類似するロジックが抽出される。該抽出により、開発者がプログラムのパフォーマンスの解析する場合に大きく役立つ。
【発明を実施するための最良の形態】
【００５４】
本発明の実施態様において、「アルゴリズム」は、ある特定の目的を達成するための処理手順である。該処理手順は、コードを用いて記述される。本発明の実施態様では、「アルゴリズム」は、上記コードの一部分も含む。コードの一部分は、例えば、ループをするコード及び条件分岐をするコードを含む。ループをするコードは、例えば、for及びwhileである。条件分岐をするコードは、例えば、if及びcaseである。
【００５５】
本発明の実施態様において、「アルゴリズムをグループ化」とは、構造が似ているコード同士をまとめて、グループ化することである。
上記グループは、構造体で表される。上記構造体は、グループを代表する有向グラフ（以下、代表有向グラフ）及びグループの実行頻度を要素として有する。さらに、上記構造体は、グループに属する全ての有向グラフを、オプションの要素として有することができる。
また、本発明の実施態様において、上記グループの集合をグループ・テーブルという。
【００５６】
本発明の実施態様において、「有向グラフ」とは、ノード及び該ノードを結ぶエッジを有するグラフである。該エッジには方向があり、ノード間の遷移の方向を示す。上記アルゴリズムは、有向グラフに変換される。なお、ノード及びエッジが上記アルゴリズムに含まれる何に対応するかは、有向グラフの種類によって異なる。
有向グラフは、例えば、制御フローグラフ（ＣＦＧ：Control  flow  graph）、抽象構文木（ＡＳＴ：Abstract  syntax  tree）及びプログラム依存グラフ（ＰＤＧ：Program  dependence  graph）を含む。
制御フローグラフは、プログラムを実行したときに通る可能性のある全経路を表す有向グラフである。制御フローグラフの詳細については、以下のＵＲＬを参照されたい（URL：http://ja.wikipedia.org/wiki/%E5%88%B6%E5%BE%A1%E3%83%95%E3%83%AD%E3%83%BC%E3%82%B0%E3%83%A9%E3%83%95）。
抽象構文木は、有限なラベル付き木構造である。抽象構文木の詳細については、以下のＵＲＬを参照されたい（URL：http://ja.wikipedia.org/wiki/%E6%8A%BD%E8%B1%A1%E6%A7%8B%E6%96%87%E6%9C%A8）。
プログラム依存グラフは、プログラム中の依存関係の階層的分析のために設計される有向グラフである。ノードは、例えば、ステートメント、述語表現、演算子又はオペランドを表す。エッジは、例えば、ノードに付随する操作要求データの値、又は及び実行要求の制御状況を表す。プログラム依存グラフの詳細については、下記文献を参照されたい（Jeanne Ferrante et al," The program dependencegraph and its use in optimization, ACM Transactions on Programming Languagesand Systems", TOPLAS, Vol. 9, No. 3, pages 319 &#8211; 349, July 1987）。
【００５７】
本発明の実施態様において、「代表有向グラフ」とは、上記有向グラフの属するグループを代表する有向グラフである。上記代表有向グラフは、上記グループに属する有向グラフのうち、上記ノードの数が最も少ない有向グラフである。
【００５８】
本発明の実施態様において、「類似する」とは、２つの有向グラフが、共に所定の特徴を有することである。本発明の１つの実施態様では、第１の有向グラフが、第１のノード及び第２のノード、並びに上記第１のノードから上記第２のノードへの経路を含み、第２の有向グラフが、第３のノード及び第４のノード、並びに上記第３のノードから上記第４のノードへの経路を含み、且つ上記第３のノードが上記第１のノードに対応し、且つ上記第４のノードが上記第２のノードに対応する場合、上記第１の有向グラフと上記第２の有向グラフとは類似する。また上記経路があるとは、例えば、上記第１の有向グラフにおいて、上記第１のノードからエッジの示す方向に従ってノードをたどると上記第２のノードにたどり着くことをいう。ここで、上記第１のノードと上記第２のノードとが直接結ばれている必要はない。例えば、上記第１のノードから第５のノードに経路があり且つ上記第５のノードから上記第２のノードに経路がある場合においても、上記第１のノードから上記第２のノードへの経路がある。
上記ノードが対応するとは、ノードの性質が同じであることを示す。本発明の実施態様では、ノードの性質が同じであれば、対応するノードは、同じノードとみなされる。ノードの性質とは、例えば、ノードが変数に対応する場合におけるデータ型である。変数に対応する２つのノードの変数名が異なっていたとしても、データ型が同じであれば、２つのノードは同じノードとみなされうる。逆に変数名が同じであってもデータ型が異なる場合、２つのノードは、違うノードとみなされうる。
【００５９】
また、本発明の実施態様において、「類似度」とは、２つの有向グラフがどれだけ類似しているかを表す度合いである。類似度は、２つの有向グラフが、前段落に記載されている類似する条件を満たす場合にのみ有効になる。類似度は、上記類似している２つの有向グラフの両方に含まれる同一のノード及び該ノード間の経路の少なくとも１つの数と、上記類似している２つの有向グラフのどちらか一方に含まれるノード及び該ノードを始点又は終点とする経路の少なくとも１つの数とから求められる。
例えば、上記類似度は、Ｎ１÷（Ｎ１＋Ｎ２）×１００によって求めることができる。ここで、Ｎ１は、上記類似している２つの有向グラフの両方に含まれる同一のノード及び該ノード間の経路の少なくとも１つの数である。また、Ｎ２は、上記類似している２つの有向グラフのどちらか一方に含まれるノード及び該ノードを始点又は終点とする経路の少なくとも１つの数である。例えば、上記類似している２つの有向グラフの両方に含まれる同一のノードが２つであるとする。また、上記２つのノード間の経路が１つであるとする。さらに、上記類似している２つの有向グラフのどちらか一方に含まれるノードは１つであるとする。また、上記１つのノードを始点又は終点とする経路は２つであるとする。すると、ノードに注目した場合の類似度は、２÷（２＋１）×１００≒６６．７である。また、経路に注目した場合の類似度は、１÷（１＋２）×１００≒３３．３である。また、ノード及び経路に注目した場合の類似度は、３÷（３＋３）×１００＝５０である。
別の例では、上記類似度は、上記類似している２つの有向グラフの両方に含まれるノードの総和を、上記類似している２つの有向グラフに含まれる全てのノードの総和で割った値に１００をかけたものである。
本発明の実施態様では、類似度がある閾値以下の場合、上記類似している２つの有向グラフを「類似していない」と扱うことができる。ここで、類似度が、例えば上記ノードに注目した場合の類似度であるとする。このとき、上記閾値は、上記２つのグラフに含まれるノードの個数が多い場合は７０〜８０パーセントに、上記ノード数が少ない場合は５０〜６０パーセントに設定してもよい。
【００６０】
また、上記とは本発明の他の１つの実施態様として、上記類似を、例えば、上記非特許文献１に記載されているような従来の方法によって判定してもよい。
【００６１】
本発明の実施態様において、「実行頻度」とは、プログラムの実行時において、上記アルゴリズムを用いた処理が実行される頻度である。本発明の１つの実施態様では、実行頻度は、プロファイラ又は静的技術（コンパイラー）から取得される値を利用して求めることができる。プロファイラ又は静的技術から実行頻度を求める方法は、下記文献２を参照されたい（Tim A. Wagner, et al., "Accurate static estimators for program optimization", ACM 1994）。本発明の他の実施態様では、実行頻度は、プログラムのテストランの結果に基づいて、ユーザによる見積もりによって決定されてもよい。
【００６２】
本発明の実施態様において、「実行頻度」は、例えば、プロファイルから又は静的技術によって見積もりされうる。プロファイルは、結局のところ使用されるプログラムと（プログラムを実行することから得られる。例えば、以下のＵＲＬは、ＧＮＵのコンパイラ群であるGNU Compiler Collection（ＧＣＣ）における上記プロファイルの例を示す
（URL：http://gcc.gnu.org/onlinedocs/gccint/Profile-information.html）。
静的技術による見積もりは、プログラムの構造、例えばループネストの構造を検査し、この情報を使用して、動的振る舞いの要素を予測することによって得られる。
本発明の実施態様において、「グループの実行頻度」とは、上記グループに属する有向グラフの実行頻度から求められる値である。上記グループの実行頻度は、例えば、上記グループに属する有向グラフの実行頻度を合計したものである。上記グループに属する有向グラフが、例えば、実行頻度が１０である第１の有向グラフと実行頻度が５０である第２の有向グラフとであれば、上記グループの実行頻度は、６０である。
また別の例では、上記グループの実行頻度は、上記グループに属する有向グラフの実行頻度に係数を乗じて合計したものである。上記グループに属する有向グラフが、例えば、実行頻度が１０である第１の有向グラフと実行頻度が５０である第２の有向グラフとであり、上記係数が０．５ならば、上記グループの実行頻度は、３０である。
【００６３】
以下、図面に従って、本発明の実施態様を説明する。本実施態様は、本発明の好適な態様を説明するためのものであり、本発明の範囲をここで示す態様に限定する意図はないことを理解されたい。また、以下の図を通して、特に断らない限り、同一の符号は、同一の対象を指す。
【００６４】
図１Ａは、本発明の実施態様である、アルゴリズムから変換された有向グラフの一例を示す。
有向グラフ（１００）は、開始ノード（１０１）、ノードＡ（１０２Ａ）、ノードＢ（１０２Ｂ）、終了ノード（１０３）及びエッジ（１０４）を含む。
開始ノード（１０１）は、有向グラフ（１００）の開始を示す。開始ノード（１０１）は、上記アルゴリズムの開始に対応する。アルゴリズムが有向グラフに変換されたときに、対応する開始ノードが生成されない場合がある。
ノードＡ及びＢ（１０２Ａ、１０２Ｂ）それぞれは、有向グラフ（１００）の処理のまとまりを示す。ノードＡ及びＢ（１０２Ａ、１０２Ｂ）が上記アルゴリズムに含まれる何に対応するかは、有向グラフの種類によって異なる。
終了ノード（１０３）は、有向グラフ（１００）の終了を示す。終了ノード（１０３）は、上記アルゴリズムの終了に対応する。アルゴリズムが有向グラフに変換されたときに、対応する終了ノードが生成されない場合がある。
エッジ（１０４）は、ノード同士のつながりとつながりの方向とを示す。エッジ（１０４）が上記アルゴリズムに含まれる何に対応するかは、有向グラフの種類によって異なる。
有向グラフ（１００）において、開始ノード（１０１）とノードＡ（１０２Ａ）とは、開始ノード（１０１）からノードＡ（１０２Ａ）の方向につながっている。ノードＡ（１０２Ａ）とノードＢ（１０２Ｂ）とは、ノードＡ（１０２Ａ）からノードＢ（１０２Ｂ）の方向につながっている。ノードＢ（１０２Ｂ）と終了ノード（１０３）とは、ノードＢ（１０２Ｂ）から終了ノード（１０３）の方向につながっている。
【００６５】
図１Ｂは、本発明の実施態様である、有向グラフ間の類似の例を示す。
有向グラフ（１１１）は、ノードＸ及びノードＹを含む。ノードＸ及びノードＹは、ノードＸからノードＹの方向へのエッジで結ばれている。よって、有向グラフ（１１１）は、ノードＸからノードＹへの経路を含む。
有向グラフ（１１２）は、ノードＸ、ノードＹ及びノードＺを含む。ノードＸ及びノードＹは、ノードＸからノードＹへの方向のエッジで結ばれている。ノードＹ及びノードＺは、ノードＹからノードＺの方向へのエッジで結ばれている。そのため、有向グラフ（１１２）では、ノードＸ、ノードＹ及びノードＺの順でノードをたどることができる。ここで、有向グラフ（１１２）は、ノードＸからノードＹへの経路を含む。よって、有向グラフ（１１１）に含まれる全てのノード（ノードＸ及びノードＹ）とその経路（ノードＸからノードＹへの経路）が有向グラフ（１１２）に含まれる。従って、有向グラフ（１１２）は、有向グラフ（１１１）と類似する。
有向グラフ（１１３）は、ノードＸ、ノードＺ及びノードＹを含む。ノードＸ及びノードＺは、ノードＸからノードＺへの方向のエッジで結ばれている。ノードＺ及びノードＹは、ノードＺからノードＹの方向へのエッジで結ばれている。そのため、有向グラフ（１１３）では、ノードＸ、ノードＺ及びノードＹの順でノードをたどることができる。よって、有向グラフ（１１３）は、ノードＸからノードＹへの経路を含む。ここで、有向グラフ（１１１）に含まれる全てのノード（ノードＸ及びノードＹ）とその経路（ノードＸからノードＹへの経路）が有向グラフ（１１３）に含まれる。従って、有向グラフ（１１３）は、有向グラフ（１１１）と類似する。
有向グラフ（１１４）は、ノードＹ、ノードＺ及びノードＸを含む。ノードＹ及びノードＺは、ノードＹからノードＺへの方向のエッジで結ばれている。ノードＺ及びノードＸは、ノードＺからノードＸへの方向のエッジで結ばれている。そのため、有向グラフ（１１４）では、ノードＹ、ノードＺ及びノードＸの順でノードをたどることができる。よって、有向グラフ（１１４）は、ノードＹからノードＸへの経路を含むが、ノードＸからノードＹに経路を含まない。よって、有向グラフ（１１４）は、有向グラフ（１１１）と類似しない。
このように、有向グラフ（１１２）及び有向グラフ（１１３）は、ともに有向グラフ（１１１）と類似する。しかし、有向グラフ（１１２）と有向グラフ（１１３）とは類似しない。なぜなら、有向グラフ（１１２）は、有向グラフ（１１３）に含まれるノードＺからノードＹへの経路を含まず、有向グラフ（１１３）は、有向グラフ（１１２）に含まれるノードＹからノードＺへの経路を含まないからである。
【００６６】
上記例では、２つの有向グラフのいずれか一方の有向グラフが、他方の有向グラフに含まれるノードに対応するノード全てを含むこと、且つ上記他方の有向グラフに含まれるノード間の全ての経路が、上記一方の有向グラフに含まれるノード間の一部又は全部の経路に対応する場合、類似するとした。
ここで、上記一方の有向グラフが、少なくとも２以上のノードを含み、並びに第１のノード、第２のノード、及び上記第１のノードから上記第２のノードへの経路を含むこと、且つ上記他方の有向グラフが、少なくとも２以上のノードを含み、並びに第３のノード、第４のノード、及び上記第３のノードから上記第４のノードへの経路を含むこと、且つ上記第３のノードは上記第１のノードに対応すること、且つ上記第４のノードは上記第２のノードに対応する場合、類似するとしてもよい。例えば、有向グラフ（１１２）及び有向グラフ（１１３）は、ノードＸ、ノードＹ及びノードＺを含む。そして、有向グラフ（１１２）及び有向グラフ（１１３）は、ノードＸからノードＹへの経路及びノードＸからノードＺへの経路を含む。よって、有向グラフ（１１２）と有向グラフ（１１３）とは類似するとしてもよい。この類似判定により、例えば、ノード間の全ての経路が対応しない場合、対応する経路の数の多い有向グラフを類似すると判定することで、類似する有向グラフが０になることを防ぐことができる。
【００６７】
図１Ｃは、本発明の実施態様における、分岐を含む有向グラフ間の類似判定の例を示す。
有向グラフ（１１５）は、ノードＸ、ノードＹ及びノードＺを含む。ノードＸ及びノードＺは、ノードＸからノードＺの方向へのエッジで結ばれている。ノードＹ及びノードＺは、ノードＹからノードＺの方向へのエッジで結ばれている。よって、有向グラフ（１１５）は、ノードＸ及びノードＹそれぞれからノードＺへの経路を含む。
有向グラフ（１１６）は、ノードＸ及びノードＺを含む。ノードＸ及びノードＺは、ノードＸからノードＺの方向へのエッジで結ばれている。有向グラフ（１１６）は、ノードＸからノードＺへの経路を含む。よって、有向グラフ（１１６）に含まれる全てのノード（ノードＸ及びノードＺ）とその経路（ノードＸからノードＺへの経路）が有向グラフ（１１５）に含まれる。従って、有向グラフ（１１６）は、有向グラフ（１１５）と類似する。
有向グラフ（１１７）は、ノードＺ、ノードＸ及びノードＹを含む。ノードＺ及びノードＸは、ノードＺからノードＸの方向へのエッジで結ばれている。ノードＺ及びノードＹは、ノードＺからノードＹの方向へのエッジで結ばれている。よって、有向グラフ（１１７）は、ノードＺからノードＸへの及びノードＹへの経路を含む。ここで、有向グラフ（１１７）は、ノードＸ及びノードＹそれぞれからノードＺへの経路を含まない。一方、有向グラフ（１１５）は、ノードＺからノードＸへの及びノードＺからノードＹへの経路を含まない。よって、有向グラフ（１１７）は、有向グラフ（１１５）と類似しない。
有向グラフ（１１８）は、ノードＷ、ノードＸ、ノードＹ及びノードＺを含む。ノードＷ及びノードＺは、ノードＷからノードＺの方向へのエッジで結ばれている。ノードＸ及びノードＺは、ノードＸからノードＺの方向へのエッジで結ばれている。ノードＹ及びノードＺは、ノードＹからノードＺの方向へのエッジで結ばれている。よって、有向グラフ（１１８）は、ノードＷ〜ＹからノードＺへの経路を含む。よって、有向グラフ（１１５）に含まれる全てのノード(ノードＸ〜Ｚ)とその経路（ノードＸからノードＺへの経路及びノードＹからノードＺへの経路）が有向グラフ（１１８）に含まれる。従って、有向グラフ（１１８）は、有向グラフ（１１５）と類似する。
【００６８】
図１Ｄは、本発明の実施態様における、ループを含む有向グラフ間の類似判定の例を示す。
有向グラフ（１１９）は、ノードＸ、ノードＹ及びノードＺを含む。ノードＸ及びノードＹは、ノードＸからノードＹへの方向のエッジで結ばれている。ノードＹ及びノードＺは、ノードＹからノードＺへの方向のエッジで結ばれている。ノードＺ及びノードＸは、ノードＺからノードＸへの方向のエッジで結ばれている。そのため、有向グラフ（１１９）では、ノードＸ、ノードＹ、ノードＺ、そしてノードＸ、・・・（繰り返し）の順でノードをたどることができる。よって、有向グラフ（１１９）は、ノードＸ〜Ｚの任意のノードから、ノードＸ〜Ｚの任意のノードへの経路を含む。
有向グラフ（１２０）は、ノードＺ、ノードＸ及びノードＹを含む。ノードＺ及びノードＸは、ノードＺからノードＸへの方向のエッジで結ばれている。ノードＸ及びノードＹは、ノードＸからノードＹへの方向のエッジで結ばれている。ノードＹ及びノードＺは、ノードＹからノードＺへの方向のエッジで結ばれている。そのため、有向グラフ（１２０）では、ノードＺ、ノードＸ、ノードＹ、そしてノードＺ、・・・（繰り返し）の順でノードをたどることができる。よって、有向グラフ（１２０）は、ノードＸ〜Ｚの任意のノードから、ノードＸ〜Ｚの任意のノードへの経路を含む。よって、有向グラフ（１２０）は、有向グラフ（１１９）と類似する。
有向グラフ（１２１）は、ノードＺ、ノードＹ及びノードＸを含む。ノードＺ及びノードＹは、ノードＺからノードＹへの方向のエッジで結ばれている。ノードＹ及びノードＸは、ノードＹからノードＸへの方向のエッジで結ばれている。ノードＸ及びノードＺは、ノードＸからノードＺへの方向のエッジで結ばれている。そのため、有向グラフ（１２１）では、ノードＺ、ノードＹ、ノードＸ、そしてノードＺ、・・・（繰り返し）の順でノードをたどることができる。よって、有向グラフ（１２１）もまた、ノードＸ〜Ｚの任意のノードから、ノードＸ〜Ｚの任意のノードへの経路を含む。よって、有向グラフ（１２１）は、有向グラフ（１１９）と類似する。
このように、ループを含む有向グラフでは、ループに含まれるノードは、ループに含まれる他の全てのノードに経路がある。よって、ループに含まれるノードが全て同じである上記有向グラフ（１１９〜１２１）同士は、全て類似する。
【００６９】
図２は、本発明の実施態様における、システム構成図の例を示す。
コンピュータ・システム（２００）は、変換部（２０１）、判定部（２０２）、決定部（２０３）、計算部（２０４）、表示部（２０５）、登録部（２０６）、更新部（２０７）、併合部（２０８）、削除部（２０９）、及び記憶部（２１０）を含む。記憶部（２１０）は、上記コンピュータ・システム（２００）の内部にあっても外部にあってもよい。記憶部（２１０）はまた、該コンピュータ・システム（２００）に接続されているネットワーク上の記憶装置又は他のコンピュータ・システム内にある記憶装置であってよい。また、記憶部（２１０）は、グループ０〜ｎ（２１１）を格納する。
ユーザは、プログラムと、該プログラムに含まれる解析対象のアルゴリズムの実行頻度とを、コンピュータ・システム（２００）の入力情報（２１２）として与える。入力情報（２１２）は、あらかじめ記憶部（２１０）に格納されていてもよい。
変換部（２０１）は、入力情報（２１２）として与えられたプログラム内の解析対象のアルゴリズムを有向グラフに変換する。ここで、該変換を実行するコンピュータは以降の処理を実行するコンピュータと分けてもよい。その場合、該変換された有向グラフは、記憶部（２１０）に格納される。
判定部（２０２）は、上記有向グラフを変換部（２０１）から取得する。なお、上記有向グラフが記憶部（２１０）に格納されている場合、判定部（２０２）は、記憶部（２１０）から上記有向グラフを取得する。また判定部（２０２）は、グループ（２１１）を記憶部（２１０）から取得する。判定部（２０２）は、上記変換された有向グラフがグループ（２１１）に含まれている代表有向グラフに類似しているかどうかを判定する。該判定は、上記有向グラフと類似する代表有向グラフを含むグループ（２１１）が見つかるまで、ないしは全てのグループ（２１１）についての類似性の判定が終了するまで行われる。
決定部（２０３）は、上記判定の結果を上記判定部（２０２）から取得する。決定部（２０３）は、記憶部に記憶されているグループのうちから、上記変換された有向グラフの属するグループを決定する。
計算部（２０４）は、決定されたグループの実行頻度と上記変換された有向グラフの実行頻度とに基づきグループの実行頻度を計算する。計算部（２０４）は、例えば、上記決定された上記有向グラフの属するグループの実行頻度に、入力情報（２１２）として与えられた上記有向グラフに対応するアルゴリズムの実行頻度を加える。
更新部（２０７）は、上記変換された有向グラフ及び上記類似する代表有向グラフのうち、ノードの数が最も小さい有向グラフを、上記類似する代表有向グラフが属するグループの新たな代表有向グラフとして更新する。登録部（２０６）は、変更が加えられた上記決定された有向グラフの属するグループを、記憶部（２１０）に登録する。ここで登録部（２０６）は、上記変換された有向グラフを、上記決定された有向グラフの属するグループに加えてもよい。
なお、上記判定において上記有向グラフと類似性のある代表有向グラフを含むグループ（２１１）が見つからなかった場合、登録部（２０６）は、上記有向グラフを新たなグループの代表有向グラフとして、記憶部（２１０）に格納する。また、登録部（２０６）は、上記有向グラフの実行頻度を新たなグループの実行頻度として、記憶部（２１０）に格納する。
表示部（２０５）は、記憶部（２１０）からグループ（２１１）を取得する。本発明の１つの実施態様では、表示部（２０５）は、代表有向グラフに対応するアルゴリズムと該代表有向グラフの属するグループの実行頻度とを表示する。表示部（２０５）はまた、グループごとに、実行頻度順で、例えば実行頻度の降順で、代表有向グラフに対応するアルゴリズムを表示してもよい。表示部（２０５）はまた、上記グループに代表有向グラフに対応する識別子をさらに表示してもよい。
本発明の他の実施態様では、表示部（２０５）は、グループ（２１１）に含まれる代表有向グラフ及び実行頻度を表示する。該表示は、全てのグループ（２１１）について行われてもよいし、ユーザまたはコンピュータ・システムによって任意に選択されたグループ（２１１）について行われてもよい。また、上記グループ（２１１）がグループに属する全てのグラフを有する場合、全ての上記グラフを表示してもよい。さらに表示部（２０５）は、上記代表有向グラフ及びグループに属する全てのグラフを、アルゴリズムに変換して表示してもよい。
併合部（２０８）は、記憶からグループ（２１１）を取得し、類似性のあるグループ同士を併合する。該併合は、例えば、表示部（２０５）が上記表示を実行する前または上記グループ（２１１）の数があらかじめ設定された上限Ｎ（Ｎは整数である）に達した場合に実行される。
削除部（２０９）は、記憶部（２１０）から、グループの実行頻度が少ないグループを記憶部（２１０）から削除する。該削除は、例えば、上記グループ（２１１）の数があらかじめ設定された上限Ｎに達した場合に実行される。
【００７０】
図３Ａは、本発明の実施態様における、プログラムの解析を支援するためのフローチャートの例を示す。
ステップ３０１は、ループ処理の開始である。
ステップ３０１では、コンピュータ・システムは、入力情報として、プログラムを記憶装置から取得する。該プログラムは、１又は複数のアルゴリズムを含む。該アルゴリズムは、１又は複数のループ又はメソッドを含む。コンピュータ・システムはまた、該アルゴリズムの実行頻度を受け取る。プログラムが複数のアルゴリズムを含む場合、コンピュータ・システムは、アルゴリズムごとに実行頻度を受け取る。コンピュータ・システムは、任意の入力情報として、上記アルゴリズムから変換される有向グラフに含まれるノードの種類を受け取ることができる。ノードの種類は、使用する有向グラフの種類によって異なる。例えば、使用する有向グラフの種類がＣＦＧ又はＡＳＴの場合、ノードの種類は、例えば、ロード、ストア及び同期である。また、コンピュータ・システムは、上記ノードの種類の代わりに、プログラムコードにおいて一般的に使用される予約語又は演算子などを受け取ることができる。後者の場合、ユーザは、予約語及び演算子それぞれとノードとの対応関係を記述した対応テーブルを予め用意しておく。コンピュータ・システムは、上記テーブルを参照することによって、予約語及び演算子を上記ノードの種類に変換することができる。
【００７１】
コンピュータ・システムは、上記入力情報を取得することに応じて、ステップ３０２〜３０４を、上記プログラムに含まれる解析対象のアルゴリズム全てについて実行する。
なお、以下では、上記プログラムに含まれる解析対象であるアルゴリズムが、上記プログラムに含まれるメソッド内のループ構造である場合を例として説明する。メソッド内にループ構造が含まれていない場合、上記プログラムに含まれる解析対象であるアルゴリズムは、メソッド自身である。
【００７２】
ステップ３０２では、変換部は、上記メソッド内のループ構造を有向グラフ（以下、グラフＴ）に変換する。上記グラフＴは、例えばＣＦＧ又はＡＳＴに従いアルゴリズムから変換されたグラフである。上記メソッド内にループ構造が含まれていない場合、変換部は、該ループ構造が含まれないメソッドをグラフＴに変換する。上記ループ構造を含むメソッドをグラフＴに変換する方法及び上記ループ構造が含まれないメソッドをグラフＴに変換する方法は後述する。
また、入力情報として、ノードの種類がコンピュータ・システムに渡されている場合、変換部は、上記ループ構造が含まれているメソッド又は上記ループ構造が含まれていないメソッドをグラフＴに変換するかどうかを判断する。変換部は、上記ループ構造が含まれているメソッド又は上記ループ構造が含まれていない上記メソッドが、上記ノードの種類で指定されたノードに変換される対象を含まない場合に、上記ループ構造が含まれているメソッド又は上記ループ構造が含まれていないメソッドをグラフＴに変換しない。また、変換部が、上記グラフＴに上記ノードの種類で指定されたノードが含まれていない場合、上記グラフＴを削除してもよい。
【００７３】
ステップ３０３では、判定部は、グループ・テーブル内の各グループに属するグループを代表する有向グラフ（以下、グラフＰ）及びグラフＴに対して、後述する位相埋め込みアルゴリズム（Topological Embedding Algorithm、以下、ＴＥＡ）を双方向で適用する。双方向で適用するとは、判定部が、上記ＴＥＡの第１の引数にグラフＰを指定し且つ第２の引数にグラフＴを指定して（以下、{Ｐ、Ｔ}）、ＴＥＡを適用することと、判定部が、ＴＥＡの第１の引数にグラフＴを指定し且つ第２の引数にグラフＰを指定して（以下、{Ｔ、Ｐ}）、ＴＥＡを適用することの両方を実行することである。
【００７４】
ＴＥＡは、引数に設定された２つのグラフについて、該２つのグラフに含まれるノード同士の関係を求めるためのアルゴリズムである。ＴＥＡは、引数として、第１のパラメータ及び第２のパラメータを受け付ける。上記第１のパラメータ及び第２のパラメータに、有向グラフを設定する。ＴＥＡは、上記第１のパラメータに設定された有向グラフが、上記第２のパラメータに埋め込み可能かどうかを判定する。埋め込み可能とは、上記第２のパラメータに設定された有向グラフが、上記第１のパラメータに設定された有向グラフに含まれる全てのノードを含み、且つ上記全てのノード間に上記第１のパラメータに設定された有向グラフと同じ経路があることを指す。
ＴＥＡの詳細については、以下の文献を参考にされたい（James JianghaiFu,”DirectedGraph Pattern Matching and Topological Embedding”, Journal of Algorithms,Vol22, p 372-391, 1997）。
【００７５】
判定部は、ＴＥＡによって求められるノード同士の関係から、類似度を求めてもよい。ノードは、必ずしも１対１に対応するわけではない。判定部は、ノードが１対多に対応する場合、上記２つのグラフの両方に含まれる同一のノードの数と、上記２つのグラフのどちらか一方に含まれるノードの数とに基づいて類似度を求める。判定部は、類似度が閾値より小さい場合、ＴＥＡから求められた結果である埋め込み可能であるという判定を、埋め込み可能ではないという判定に変更してもよい。
【００７６】
ステップ３０４では、最初に、決定部が、ＴＥＡから求められた結果に基づいて、グラフＴの属するグループを決定する。次に、登録部、計算部及び更新部が、上記グループ・テーブルを更新する。
{Ｐ、Ｔ}の組をＴＥＡに適用した結果、グラフＰはグラフＴに埋め込み可能であると判断された場合、計算部は、グラフＰの属するグループの実行頻度に、入力情報に含まれるグラフＴの実行頻度を加える。そして登録部が、上記加えられた実行頻度をグラフＰの属するグループに登録する。ここで登録部は、グラフＴをグラフＰの属するグループのオプションの要素（all_graph）に登録してもよい。
{Ｐ、Ｔ}の組をＴＥＡに適用した結果、グラフＰはグラフＴに埋め込み可能ではないと判断され、且つ｛Ｔ、Ｐ｝の組をＴＥＡに適用した結果、グラフＴはグラフＰに埋め込み可能であると判断された場合、更新部は、グラフＰの属するグループのグラフＰをグラフＴに置き換えてグループを更新する。また、計算部は、グラフＰの属するグループの実行頻度に、入力情報に含まれるグラフＴの実行頻度を加える。そして、登録部が、上記加えられた実行頻度をグラフＰの属するグループに登録する。ここで登録部は、グラフＴをグラフＰの属するグループのオプションの要素（all_graph）に登録してもよい。
上記{Ｐ、Ｔ}の組をＴＥＡに適用した結果及び上記｛Ｔ、Ｐ｝の組をＴＥＡに適用した結果、グラフＰはグラフＴに埋め込み可能ではないと判断され、且つグラフＴもグラフＰに埋め込み可能ではないと判断された場合、登録部は、グラフＴ及びグラフＴの実行頻度を新たなグループとしてグループ・テーブルに追加する。
【００７７】
ステップ３０５は、ループ処理であるステップ３０１の終了である。
【００７８】
ステップ３０６では、表示部は、上記プログラム解析の終了又は何らかのイベントに応じて以下の出力処理を行う。上記イベントは、例えば、ユーザによるキーボード又はマウスからの入力である。
出力処理において、判定部は、グループ・テーブルに登録された各グループに属する代表有向グラフ同士の類似性判定を行う。上記類似性判定は、ステップ３０３における判定と同一の判定でよい。代表有向グラフ同士が類似していると判定された場合、併合部は、上記類似していると判定された代表有向グラフが属するグループ（以下、類似するグループ）同士を併合する。ここで、上記類似するグループに属する代表有向グラフのうち、ノードの数が最も少ない代表有向グラフが、上記併合されたグループの代表有向グラフになる。また、上記類似するグループに属する有向グラフ全ての実行頻度の合計値が、上記併合されたグループに属する有向グラフ全ての実行頻度になる。さらに、上記類似するグループに属する有向グラフ全てが、上記併合されたグループに属する有向グラフになる。
表示部は、グループ・テーブルの各グループを上記グループの実行頻度でソートする。そして、表示部は、上記グループの実行頻度が高い順に上記グループに属する要素を表示する。
【００７９】
図３Ｂは、本発明の実施態様における、解析処理をして処理を行う場合のフローチャートの例を示す。
本発明の実施態様では、コンピュータ・システムで実行される解析プログラムを、上記グラフＴへの変換を行うプログラム（以下、第１のプログラム）と、類似性を判定しグループを表示させるプログラム（以下、第２のプログラム）とに分割してもよい。該分割されたプログラムは、異なるコンピュータ上で実行されるようにしてよい。
【００８０】
フローチャート（３１０）は、上記第１のプログラムを使用してプログラムの解析を行うためのフローチャートを示す。
ステップ３１１は、ループ処理の開始である。
ステップ３１１では、コンピュータ・システムは、上記第１のプログラムの入力情報として、プログラムと、該プログラムに含まれる解析対象のアルゴリズムの実行頻度を受け取る。
【００８１】
コンピュータ・システムは、上記入力情報を取得すると、ステップ３１２〜３１３を、上記プログラムに含まれる解析対象のアルゴリズム全てについて実行する。
なお、以下では、上記プログラムに含まれる解析対象であるアルゴリズムが、上記プログラムに含まれるメソッド内のループ構造である場合を例として説明する。メソッド内にループ構造が含まれていない場合、上記プログラムに含まれる解析対象であるアルゴリズムは、メソッド自身である。
【００８２】
ステップ３１２では、変換部は、上記メソッド内のループ構造を有向グラフ（以下、グラフＴ）に変換する。上記グラフＴは、例えばＣＦＧ又はＡＳＴに従いアルゴリズムから変換されたグラフである。上記メソッド内にループ構造が含まれていない場合、変換部は、該ループ構造が含まれないメソッドをグラフＴに変換する。上記ループ構造を含むメソッドをグラフＴに変換する方法及び上記ループ構造が含まれないメソッドをグラフＴに変換する方法は後述する。
また、入力情報として、ノードの種類がコンピュータ・システムに渡されている場合、変換部は、上記ループ構造が含まれているメソッド又は上記ループ構造が含まれていないメソッドをグラフＴに変換するかどうかを判断する。変換部は、上記ループ構造が含まれているメソッド又は上記ループ構造が含まれていない上記メソッドが、上記ノードの種類で指定されたノードに変換される対象を含まない場合に、上記ループ構造が含まれているメソッド又は上記ループ構造が含まれていないメソッドをグラフＴに変換しない。また、変換部が、上記グラフＴに上記ノードの種類で指定されたノードが含まれていない場合、上記グラフＴを削除してもよい。
【００８３】
ステップ３１３では、登録部は、上記グラフＴ、及び該グラフＴに対応する実行頻度を記憶装置に登録する。
【００８４】
ステップ３１４は、ループ処理であるステップ３１１の終了である。
コンピュータ・システムは、上記プログラムに含まれる解析対象のアルゴリズム全てについて、ステップ３１２〜３１３が実行されたら上記第１のプログラムを終了する。表示部は、上記終了の前に、例えばモニタ又は紙媒体に上記グラフＴを出力してもよい。
【００８５】
フローチャート（３２０）は、上記第２のプログラムを使用してプログラムの解析を行うためのフローチャートを示す。
ステップ３２１は、ループ処理の開始である。
ステップ３２１では、コンピュータ・システムは、入力情報として、グラフＴに含む必要のあるノードの種類を受け取ることができる。ノードの種類は、グラフＴの種類によって異なる。例えば、使用する有向グラフの種類がＣＦＧ又はＡＳＴの場合、ノードの種類は、例えば、ロード、ストア及び同期である。また、コンピュータ・システムは、上記ノードの種類の代わりに、プログラムコードにおいて一般的に使用される予約語又は演算子などを受け取ることができる。後者の場合、ユーザは、予約語及び演算子それぞれとノードとの対応関係を記述した対応テーブルを予め用意しておく。コンピュータ・システムは、上記テーブルを参照することによって、予約語及び演算子を上記ノードの種類に変換することができる。
コンピュータ・システムは、上記第２のプログラムの入力情報として、上記第１のプログラムで登録されたグラフＴと、該グラフＴに対応する実行頻度とを、記憶装置から取得する。
コンピュータ・システムは、上記取得したグラフＴについてステップ３２２及び３２３を実行する。但し、コンピュータ・システムは、上記入力オプションで指定された上記ノードの種類を含まない上記グラフＴについて、ステップ３２２〜３２３を実行しない。
【００８６】
ステップ３２２では、判定部は、グループ・テーブル内の各グループに属するグループを代表する有向グラフ（グラフＰ）及び上記グラフＴに対して、ＴＥＡを双方向で適用する。
ステップ３２３では、最初に、決定部が、ＴＥＡから求められた結果に基づいて、グラフＴの属するグループを決定する。次に、登録部、計算部及び更新部が、上記グループ・テーブルを更新する。
{Ｐ、Ｔ}の組をＴＥＡに適用した結果、グラフＰはグラフＴに埋め込み可能であると判断された場合、計算部は、グラフＰの属するグループの実行頻度に、上記記憶部より取得したグラフＴに対応する実行頻度を加える。そして登録部が、上記加えられた実行頻度をグラフＰの属するグループに登録する。ここで登録部は、グラフＴをグラフＰの属するグループのオプションの要素（all_graph）に登録してもよい。
{Ｐ、Ｔ}の組をＴＥＡに適用した結果、グラフＰはグラフＴに埋め込み可能ではないと判断され、且つ｛Ｔ、Ｐ｝の組をＴＥＡに適用した結果、グラフＴはグラフＰに埋め込み可能であると判断された場合、更新部は、グラフＰの属するグループのグラフＰをグラフＴに置き換えてグループを更新する。また、計算部は、グラフＰの属するグループの実行頻度に、上記記憶部より取得したグラフＴに対応する実行頻度を加える。そして、登録部が、上記加えられた実行頻度をグラフＰの属するグループに登録する。ここで登録部は、グラフＴをグラフＰの属するグループのオプションの要素（all_graph）に登録してもよい。
上記{Ｐ、Ｔ}の組をＴＥＡに適用した結果及び上記｛Ｔ、Ｐ｝の組をＴＥＡに適用した結果、グラフＰはグラフＴに埋め込み可能ではないと判断され、且つグラフＴもグラフＰに埋め込み可能ではないと判断された場合、登録部は、グラフＴ及びグラフＴに対応する実行頻度を新たなグループとしてグループ・テーブルに追加する。
【００８７】
ステップ３２４は、ループ処理であるステップ３２１の終了である。
【００８８】
ステップ３２５では、表示部は、上記プログラム解析の終了又は何らかのイベントに応じて以下の出力処理を行う。上記イベントは、例えば、ユーザによるキーボード又はマウスからの入力である。
出力処理において、判定部は、グループ・テーブルに登録された各グループに属する代表有向グラフ同士の類似性判定を行う。上記類似性判定は、ステップ３２２における判定と同一の判定でよい。代表有向グラフ同士が類似していると判定された場合、併合部は、上記類似していると判定された代表有向グラフが属するグループ（以下、類似するグループ）同士を併合する。ここで、上記類似するグループに属する代表有向グラフのうち、ノードの数が最も少ない代表有向グラフが、上記併合されたグループの代表有向グラフになる。また、上記類似するグループに属する有向グラフ全ての実行頻度の合計値が、上記併合されたグループに属する有向グラフ全ての実行頻度になる。さらに、上記類似するグループに属する有向グラフ全てが、上記併合されたグループに属する有向グラフになる。
表示部は、グループ・テーブルの各グループを上記グループの実行頻度でソートする。そして、表示部は、上記グループの実行頻度が高い順に上記グループに属する要素を表示する。
【００８９】
図４Ａは、本発明の実施態様における、入力情報のプログラムの例を示す。
入力情報のプログラム（４００）は、メソッド１（４０１）、メソッド２（４０２）、メソッド３（４０３）及びメソッド４（４０４）を含む。
メソッド１（４０１）は、ループ１（４１１）を含む。また、ループ１（４１１）の実行頻度は２０である。メソッド２（４０２）は、ループ２（４１２）を含む。また、ループ２（４１２）の実行頻度は２５である。メソッド３（４０３）は、ループ３（４１３）を含む。また、ループ３（４１３）の実行頻度は２０である。メソッド４（４０４）は、ループ４（４１４）を含む。ループ４（４１４）の実行頻度は５である。以上のように、ループ１〜４（４１１〜４１４）は、同一のループでない。
【００９０】
コンピュータ・システムは、メソッド１〜４（４０１〜４０４）に含まれるループ１〜４（４１１〜４１４）を有向グラフに変換する。以下の例では、コンピュータ・システムは、ループ１〜４（４１１〜４１４）をＡＳＴ及びＣＦＧの２種類の有向グラフに従うグラフに変換する。なお、本発明の実施態様は、ＣＦＧのみへの変換でも実施可能である。
ＡＳＴは、有向木構造である。上記ＡＳＴでは、上記木構造における節点に演算子、葉に該演算子についてのオペランドを対応させる。上記ＡＳＴを有向グラフとする場合、上記節点及び葉それぞれをノードとする。また、エッジは、上記節点から葉の方向に向かう。
ＣＦＧは、プログラムを実行したときに通る可能性のある全経路をグラフで表したものである。上記ＣＦＧでは、分岐を含まない処理のまとまりをノードとする。さらに、上記ＣＦＧでは、グラフ全体の入口となる開始及びグラフ全体の出口となる終了それぞれをノードとする。また、上記処理から次の処理への遷移がエッジになる。
【００９１】
以下に、ループ１〜４（４１１〜４１４）をＡＳＴによるグラフに変換する手順を示す。
コンピュータ・システムは、ループ１〜４（４１１〜４１４）を１行ずつ精査する。コンピュータ・システムは、該精査において、演算子と該演算子についてのオペランドとを抽出する。例えば、コンピュータ・システムは、上記精査する行に含まれる演算を抽出する。ここで、演算とは、例えば、メモリからのデータの読み出し、メモリへのデータの保存、加減算などの計算、変数への値の割り当て及びif文やfor文における判定である。コンピュータ・システムは、例えば、上記演算に対応するプログラム言語における予約語を記憶部に格納する。コンピュータ・システムは、該精査において、上記格納された予約語を発見したならば、上記発見された予約語及び上記発見された予約語のオペランドそれぞれを、ＡＳＴのノードとする。また、コンピュータ・システムは、上記発見された予約語のノードから上記発見された予約語のオペランドのノードの方向にエッジを引く。
【００９２】
以下に、ループ１〜４（４１１〜４１４）をＣＦＧによるグラフに変換する手順を示す。
本例では、ＣＦＧのノードとして、上記ＡＳＴにおける節点に対応するノードを利用する。コンピュータ・システムは、ループ１〜４（４１１〜４１４）を１行ずつ実行される順に精査する。ループ１〜４（４１１〜４１４）に分岐が存在する場合、コンピュータ・システムは、それぞれの分岐について実行される順に精査する。コンピュータ・システムは、該精査において、上記ＡＳＴにおける節点に対応するノードに変換された個所を発見することに応じて、上記発見された個所それぞれをノードとする。また、コンピュータ・システムは、上記ノードが発見された順にエッジを引いていく。さらに、コンピュータ・システムは、開始ノードから上記ループにおいて最初に発見されたノードにエッジを引く。さらに、コンピュータ・システムは、ループから抜ける処理及びループの最後に実行される処理に対応するノードから終了ノードへのエッジを引く。
別の変換する手順として、コンピュータ・システムは、ループ１〜４（４１１〜４１４）を１行ずつ実行される順に精査する。上記ループに分岐が存在する場合、コンピュータ・システムは、それぞれの分岐について実行される順に精査する。コンピュータ・システムは、該精査において、処理のまとまりを抽出する。コンピュータ・システムは、例えば、上記精査する行に含まれるプログラム言語の予約語を抽出する。コンピュータ・システムは、例えば、上記予約語と上記処理のまとまりとの対応付けを記憶部に格納する。コンピュータ・システムは、該精査において、上記対応付けられた予約語を発見したならば、上記発見された予約語それぞれをＣＦＧのノードとする。また、コンピュータ・システムは、上記ノードが発見された順にエッジを引いていく。さらに、コンピュータ・システムは、開始ノードから上記ループにおいて最初に発見されたノードにエッジを引く。さらに、コンピュータ・システムは、ループから抜ける処理のまとまり及びループの最後に実行される処理のまとまりに対応するノードから終了ノードへのエッジを引く。
【００９３】
図４Ｂは、本発明の実施態様における、ループを有向グラフに変換した例を示す。
有向グラフ１〜４（４２１〜４２４）は、ループ１〜４（図４Ａ、４１１〜４１４）を上記手順で変換した有向グラフである。また、有向グラフ１〜４（４２１〜４２４）は、ＡＳＴ及びＣＦＧの２種類の有向グラフに従うグラフである。なお、有向グラフ１〜４（４２１〜４２４）では、ＡＳＴにおいて演算子を表すノード及びＣＦＧのノードを四角形で囲われたノードで表す。ＡＳＴにおいて演算子についてのオペランドを表すノードは、円で囲われたノードで表す。ＡＳＴのエッジは、破線の矢印で表す。ＣＦＧのエッジは、実線の矢印で表す。
【００９４】
以下に、ループ１〜４（４１１〜４１４）を有向グラフ１〜４（４２１〜４２４）に変換する手順を示す。
最初に、ループ１〜４（４１１〜４１４）がＡＳＴによるグラフに変換される過程を説明する。
ループ１（４１１）の１行目のコードは、右のオペランドが大きいかどうかを判定する演算を含む。また、上記右のオペランドが大きいかどうかを判定する演算の対象は、ｉ及びｅｎｄである。よって、コンピュータ・システムは、上記右のオペランドが大きいかどうかを判定する演算（「ｉｆ  ＜」）を、節点に対応するノードとする。また、コンピュータ・システムは、右のオペランドが大きいかどうかを判定する演算の対象であるｉ及びｅｎｄそれぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ｉｆ  ＜」のノードから、ｉのノード及びｅｎｄのノードにエッジを引く。
ループ１（４１１）の２行目のコードは、配列ａｒｒａｙのｉ番目の要素をメモリから読み出す演算である、読出演算（「ｌｏａｄ」）を含む。よって、コンピュータ・システムは、上記読出演算を、節点に対応するノードとする。また、コンピュータ・システムは、上記読出演算の対象である配列ａｒｒａｙ及びｉそれぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ｌｏａｄ」のノードから、ｉのノード及びａｒｒａｙのノードにエッジを引く。ここでループ１（４１１）の２行目のコードは、さらに左右のオペランドが等しいかどうかを判定する演算を含む。また、上記左右のオペランドが等しいかどうかを判定する演算の対象は、上記読出演算の結果及び定数０ｘ０ｄである。よって、コンピュータ・システムは、上記左右のオペランドが等しいかどうかを判定する演算（「ｉｆ  ＝＝」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記左右のオペランドが等しいかどうかを判定する演算の対象である上記読出演算の結果及び定数０ｘ０ｄそれぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ｉｆ  ＝＝」のノードから、上記読出演算を表す「ｌｏａｄ」のノード及び０ｘ０ｄのノードにエッジを引く。
ループ１（４１１）の３行目のコードは、ｉに１を加算する演算である加算演算を含む。よって、コンピュータ・システムは、加算演算（「ａｄｄ」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記加算演算の対象であるｉ及び定数１それぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ａｄｄ」のノードから、ｉのノード及び１のノードにエッジを引く。ここでループ１（４１１）の３行目のコードは、さらに上記加算演算の結果をｉに割り当てる演算である割当演算を含む。また、上記割当演算の対象は、上記加算演算の結果及びｉである。よって、コンピュータ・システムは、割当演算（「ａｓｓｉｇｎ」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記割当演算の対象である上記加算演算の結果及びｉそれぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ａｓｓｉｇｎ」のノードから、上記加算演算を表す「ａｄｄ」のノード及びｉのノードにエッジを引く。
【００９５】
ループ２（４１２）の１行目のコードは、右のオペランドが大きいかどうかを判定する演算を含む。また上記右のオペランドが大きいかどうかを判定する演算の対象は、ｉ及びｅｎｄである。よって、コンピュータ・システムは、上記右のオペランドが大きいかどうかを判定する演算（「ｉｆ  ＜」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記右のオペランドが大きいかどうかを判定する演算の対象であるｉ及びｅｎｄそれぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ｉｆ  ＜」のノードから、ｉのノード及びｅｎｄのノードにエッジを引く。ここでループ２（４１２）の１行目のコードは、さらにｉに１を加算する演算である加算演算を含む。よって、コンピュータ・システムは、加算演算（「ａｄｄ」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記加算演算の対象であるｉ及び定数１それぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ａｄｄ」のノードから、ｉのノード及び１のノードにエッジを引く。ここでループ２（４１２）の１行目のコードは、さらに上記加算演算の結果をｉに割り当てる演算である割当演算を含む。また、上記割当演算の対象は、上記加算演算の結果及びｉである。よって、コンピュータ・システムは、割当演算（「ａｓｓｉｇｎ」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記割当演算の対象である上記加算演算の結果及びｉそれぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ａｓｓｉｇｎ」のノードから、上記加算演算を表す「ａｄｄ」のノード及びｉのノードにエッジを引く。
ループ２（４１２）の２行目のコードは、配列ａｒｒａｙ１のｉ番目の要素に定数０を格納する演算である格納演算を含む。よって、コンピュータ・システムは、上記格納演算（第１の「ｓｔｏｒｅ」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記格納演算の対象である配列ａｒｒａｙ１、ｉ及び定数０それぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、第１の「ｓｔｏｒｅ」のノードから、ａｒｒａｙ１のノード、ｉのノード及び０のノードにエッジを引く。
ループ２（４１２）の３行目のコードは、配列ａｒｒａｙ２のｉ番目の要素に定数０を格納する演算である格納演算を含む。よって、コンピュータ・システムは、上記格納演算（第２の「ｓｔｏｒｅ」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記格納演算の対象である配列ａｒｒａｙ２、ｉ及び定数０それぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、第２の「ｓｔｏｒｅ」のノードから、ａｒｒａｙ２のノード、ｉのノード及び０のノードにエッジを引く。
【００９６】
ループ３（４１３）の１行目のコードは、右のオペランドが大きいかどうかを判定する演算を含む。また、上記右のオペランドが大きいかどうかを判定する演算の対象は、ｉ及びｅｎｄである。よって、コンピュータ・システムは、上記右のオペランドが大きいかどうかを判定する演算（「ｉｆ  ＜」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記右のオペランドが大きいかどうかを判定する演算の対象であるｉ及びｅｎｄそれぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ｉｆ  ＜」のノードから、ｉのノード及びｅｎｄのノードにエッジが引く。
ループ３（４１３）の２行目のコードは、ｉに１を加算する演算である加算演算を含む。よって、コンピュータ・システムは、加算演算（「ａｄｄ」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記加算演算の対象であるｉ及び定数１それぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ａｄｄ」のノードから、ｉのノード及び１のノードにエッジを引く。ここでループ３（４１３）の２行目のコードは、さらに上記加算演算の結果をｉに割り当てる演算である割当演算を含む。また、上記割当演算の対象は、上記加算演算の結果及びｉである。よって、コンピュータ・システムは、割当演算（「ａｓｓｉｇｎ」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記割当演算の対象である上記加算演算の結果及びｉそれぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ａｓｓｉｇｎ」のノードから、上記加算演算を表す「ａｄｄ」のノード及びｉのノードにエッジを引く。
ループ３（４１３）の３行目のコードは、配列ａｒｒａｙのｉ番目の要素をメモリから読み出す演算である読出演算を含む。よって、コンピュータ・システムは、上記読出演算（「ｌｏａｄ」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記読出演算の対象である配列ａｒｒａｙ及びｉそれぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ｌｏａｄ」のノードから、ｉのノード及びａｒｒａｙのノードにエッジを引く。ここでループ３（４１３）の３行目のコードは、さらに左右のオペランドが等しいかどうかを判定する演算を含む。また、上記左右のオペランドが等しいかどうかを判定する演算の対象は、上記読出演算の結果及び定数０ｘ０ｄである。よって、コンピュータ・システムは、上記左右のオペランドが等しいかどうかを判定する演算（「ｉｆ  ＝＝」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記左右のオペランドが等しいかどうかを判定する演算の対象である上記読出演算の結果及び定数０ｘ０ｄそれぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ｉｆ  ＝＝」のノードから、上記読出演算を表す「ｌｏａｄ」のノード及び０ｘ０ｄのノードにエッジを引く。
【００９７】
ループ４（４１４）の１行目のコードは、右のオペランドが大きいかどうかを判定する演算を含む。また上記右のオペランドが大きいかどうかを判定する演算の対象は、ｉ及びｅｎｄである。よって、コンピュータ・システムは、上記右のオペランドが大きいかどうかを判定する演算（「ｉｆ  ＜」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記右のオペランドが大きいかどうかを判定する演算の対象であるｉ及びｅｎｄそれぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ｉｆ  ＜」のノードから、ｉのノード及びｅｎｄのノードにエッジを引く。ここでループ４（４１４）の１行目のコードは、さらにｉに１を加算する演算である加算演算を含む。よって、コンピュータ・システムは、加算演算（「ａｄｄ」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記加算演算の対象であるｉ及び定数１それぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ａｄｄ」のノードから、ｉのノード及び１のノードにエッジを引く。ここでループ４（４１４）の１行目のコードは、さらに上記加算演算の結果をｉに割り当てる演算である割当演算を含む。また、上記割当演算の対象は、上記加算演算の結果及びｉである。よって、コンピュータ・システムは、割当演算（「ａｓｓｉｇｎ」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記割当演算の対象である上記加算演算の結果及びｉそれぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ａｓｓｉｇｎ」のノードから、上記加算演算を表す「ａｄｄ」のノード及びｉのノードにエッジを引く。
ループ４（４１４）の２行目のコードは、配列ａｒｒａｙのｉ番目の要素に定数０を格納する演算である格納演算を含む。よって、コンピュータ・システムは、上記格納演算（「ｓｔｏｒｅ」）を、節点に対応するノードとする。また、コンピュータ・システムは、上記格納演算の対象である配列ａｒｒａｙ、ｉ及び定数０それぞれを、葉に対応するノードとする。さらに、コンピュータ・システムは、「ｓｔｏｒｅ」のノードから、ａｒｒａｙのノード、ｉのノード及び０のノードにエッジを引く。
【００９８】
次に、ループ１〜４（４１１〜４１４）がＣＦＧによるグラフに変換される過程を説明する。ここで、ＣＦＧのノードは、上記ＡＳＧにおける節点に対応するノードと共通のノードとする。
ループ１（４１１）では、最初に「ｉｆ  ＜」が実行される。よって、コンピュータ・システムは、開始のノードから「ｉｆ  ＜」のノードにエッジを引く。ここで「ｉｆ  ＜」の結果が偽ならば、ループは終了する。よって、コンピュータ・システムは、「ｉｆ  ＜」のノードから終了のノードにエッジを引く。
「ｉｆ  ＜」の結果が真ならば、「ｌｏａｄ」が実行される。よって、コンピュータ・システムは、「ｉｆ  ＜」のノードから「ｌｏａｄ」のノードにエッジを引く。次に「ｉｆ  ＝＝」が実行される。よって、コンピュータ・システムは、「ｌｏａｄ」のノードから「ｉｆ  ＝＝」のノードにエッジを引く。ここで「ｉｆ  ＝＝」の結果が真ならば、メソッドの終了を示すｒｅｔｕｒｎ命令が実行されるため、ループが終了する。よって、コンピュータ・システムは、「ｉｆ  ＝＝」のノードから終了のノードにエッジを引く。
「ｉｆ  ＝＝」の結果が偽ならば、「ａｄｄ」が実行される。よって、コンピュータ・システムは、「ｉｆ  ＝＝」のノードから「ａｄｄ」のノードにエッジを引く。次に「ａｓｓｉｇｎ」が実行される。よって、コンピュータ・システムは、「ａｄｄ」のノードから「ａｓｓｉｇｎ」のノードにエッジを引く。
「ａｓｓｉｇｎ」が実行されると、ループの先頭に戻る。よって、コンピュータ・システムは、「ａｓｓｉｇｎ」のノードから「ｉｆ  ＜」のノードにエッジを引く。
【００９９】
ループ２（４１２）では、最初に「ｉｆ  ＜」が実行される。よって、コンピュータ・システムは、開始のノードから「ｉｆ  ＜」のノードにエッジを引く。ここで「ｉｆ  ＜」の結果が偽ならば、ループは終了する。よって、コンピュータ・システムは、「ｉｆ  ＜」のノードから終了のノードにエッジを引く。
「ｉｆ  ＜」の結果が真ならば、第１の「ｓｔｏｒｅ」が実行される。よって、コンピュータ・システムは、「ｉｆ  ＜」のノードから第１の「ｓｔｏｒｅ」のノードにエッジを引く。次に第２の「ｓｔｏｒｅ」が実行される。よって、コンピュータ・システムは、第１の「ｓｔｏｒｅ」のノードから第２の「ｓｔｏｒｅ」のノードにエッジを引く。次に「ａｄｄ」が実行される。よって、コンピュータ・システムは、第２の「ｓｔｏｒｅ」のノードから「ａｄｄ」のノードにエッジを引く。次に「ａｓｓｉｇｎ」が実行される。よって、コンピュータ・システムは、「ａｄｄ」のノードから「ａｓｓｉｇｎ」のノードにエッジを引く。
「ａｓｓｉｇｎ」が実行されると、ループの先頭に戻る。よって、コンピュータ・システムは、「ａｓｓｉｇｎ」のノードから「ｉｆ  ＜」のノードにエッジを引く。
【０１００】
ループ３（４１３）では、最初に「ｉｆ  ＜」が実行される。よって、コンピュータ・システムは、開始のノードから「ｉｆ  ＜」のノードにエッジを引く。ここで「ｉｆ  ＜」の結果が偽ならば、ループは終了する。よって、コンピュータ・システムは、「ｉｆ  ＜」のノードから終了のノードにエッジを引く。
「ｉｆ  ＜」の結果が真ならば、「ａｄｄ」が実行される。よって、コンピュータ・システムは、「ｉｆ  ＜」のノードから「ａｄｄ」のノードにエッジを引く。次に「ａｓｓｉｇｎ」が実行される。よって、コンピュータ・システムは、「ａｄｄ」のノードから「ａｓｓｉｇｎ」のノードにエッジを引く。次に「ｌｏａｄ」が実行される。よって、コンピュータ・システムは、「ａｓｓｉｇｎ」のノードから「ｌｏａｄ」のノードにエッジを引く。次に「ｉｆ  ＝＝」が実行される。よって、コンピュータ・システムは、「ｌｏａｄ」のノードから「ｉｆ  ＝＝」のノードにエッジを引く。ここで「ｉｆ  ＝＝」の結果が真ならば、メソッドの終了を示すｒｅｔｕｒｎ命令が実行されるため、ループは終了する。よって、コンピュータ・システムは、「ｉｆ  ＝＝」のノードから終了のノードにエッジを引く。
「ｉｆ  ＝＝」の結果が偽ならば、ループの先頭に戻る。よって、コンピュータ・システムは、「ｉｆ  ＝＝」のノードから「ｉｆ  ＜」のノードにエッジを引く。
【０１０１】
ループ４（４１４）では、最初に「ｉｆ  ＜」が実行される。よって、コンピュータ・システムは、開始のノードから「ｉｆ  ＜」のノードにエッジを引く。ここで「ｉｆ  ＜」の結果が偽ならば、ループは終了する。よって、コンピュータ・システムは、「ｉｆ  ＜」のノードから終了のノードにエッジを引く。
「ｉｆ  ＜」の結果が真ならば、「ｓｔｏｒｅ」が実行される。よって、コンピュータ・システムは、「ｉｆ  ＜」のノードから「ｓｔｏｒｅ」のノードにエッジを引く。次に「ａｄｄ」が実行される。よって、コンピュータ・システムは、「ｓｔｏｒｅ」のノードから「ａｄｄ」のノードにエッジを引く。次に「ａｓｓｉｇｎ」が実行される。よって、コンピュータ・システムは、「ａｄｄ」のノードから「ａｓｓｉｇｎ」のノードにエッジを引く。
「ａｓｓｉｇｎ」が実行されると、ループの先頭に戻る。よって、コンピュータ・システムは、「ａｓｓｉｇｎ」のノードから「ｉｆ  ＜」のノードにエッジを引く。
以上の過程で、ループ１〜４（４１１〜４１４）は、有向グラフ１〜４（４２１〜４２４）に変換される。
【０１０２】
以下に、上記入力情報のプログラム（図４Ａ、４００）を入力とした場合を例として、本発明の実施態様を具体的に示す。なお、グループ・テーブルのオプション項目である「グループに属する全てのグラフ（以下、所属グラフ）」もグループ・テーブルに登録することとする。
【０１０３】
最初に、コンピュータ・システムは、上記入力情報のプログラム（４００）に含まれるループ１〜４（４１１〜４１４）をグラフ表現に変換する。ここで、コンピュータ・システムは、ループ１〜４（４１１〜４１４）をＡＳＴ及びＣＦＧの２種類の有向グラフに従うグラフで表すこととする。該変換によって、有向グラフ１〜４（４２１〜４２４）が作成される。
【０１０４】
次に、コンピュータ・システムは、有向グラフ１（４２１）から順に、各グループの代表有向グラフと類似しているかどうかの判定を行う。そして、コンピュータ・システムは、上記判定に応じて、有向グラフ１〜４（４２１〜４２４）をグループ・テーブルに登録する。なお、上記判定には、ＴＥＡを用いる。ここで、有向グラフ１〜４（４２１〜４２４）は、ＡＳＴのエッジ及びＣＦＧのエッジの２種類のエッジを含む。コンピュータ・システムは、ＴＥＡをＡＳＴのエッジのみを用いた場合の有向グラフ及びＣＦＧのエッジのみを用いた場合の有向グラフそれぞれについて用いる。コンピュータ・システムは、ＡＳＴのエッジのみを用いた場合の有向グラフ１〜４及びＣＦＧのエッジのみを用いた場合の有向グラフ１〜４それぞれのグラフが、ＡＳＴのエッジのみを用いた場合の代表有向グラフ及びＣＦＧのエッジのみを用いた場合の代表有向グラフそれぞれに類似していると認められた場合、有向グラフが代表有向グラフに類似していると判断する。
【０１０５】
以下に、上記判定及び登録の詳細な手順を示す。
初期状態では、グループ・テーブルは空である。よって、有向グラフ１（４２１）と比較される代表有向グラフはない。そのため、コンピュータ・システムは、有向グラフ１（４２１）を新たなグループの代表有向テーブルとして、グループ・テーブルの１番目に登録する。また、コンピュータ・システムは、さらに、上記ループ１（４１１）の実行頻度である２０及び有向グラフ１（４２１）をグループ・テーブルの１番目に登録する。
グループ・テーブルの１番目の要素は、上記登録によって以下のようになる。
グループ・テーブル(１)
代表有向グラフ  ：有向グラフ１
実行頻度        ：２０
所属グラフ      ：有向グラフ１
【０１０６】
次に、コンピュータ・システムは、有向グラフ２（４２２）について類似しているかどうかの判定を行う。
コンピュータ・システムは、有向グラフ２（４２２）とグループ・テーブルに登録された各代表有向グラフとを比較する。ここで比較される上記代表有向グラフは、上記有向グラフ１（４２１）である。コンピュータ・システムは、該比較にＴＥＡを適用する。コンピュータ・システムは、｛有向グラフ１、有向グラフ２｝の組をＴＥＡのパラメータに適用し検証する。有向グラフ２（４２２）は有向グラフ１（４２１）の全てのノードを含んでいないため、上記検証の結果は失敗となる。次に、コンピュータ・システムは、｛有向グラフ２、有向グラフ１｝の組をＴＥＡのパラメータに適用し検証する。有向グラフ１（４２１）は有向グラフ２（４２２）の全てのノードを含んでいないため、上記検証の結果もまた失敗となる。よって、コンピュータ・システムは、有向グラフ２（４２２）を新たなグループの代表有向グラフとして、グループ・テーブルの２番目に登録する。また、コンピュータ・システムは、さらに、上記ループ２（４１２）の実行頻度である２５及び有向グラフ２（４２２）をグループ・テーブルの２番目に登録する。
該グループ・テーブルの２番目の要素は、上記登録によって以下のようになる。
グループ・テーブル(２)
代表有向グラフ  ：有向グラフ２
実行頻度      ：２５
所属グラフ    ：有向グラフ２
【０１０７】
次に、コンピュータ・システムは、有向グラフ３（４２３）について類似しているかどうかの判定を行う。
コンピュータ・システムは、有向グラフ３（４２３）とグループ・テーブルに登録された各代表有向グラフとを比較する。ここで比較される上記代表有向グラフは、有向グラフ１（４２１）及び有向グラフ２（４２２）である。最初に、コンピュータ・システムは、上記有向グラフ３（４２３）と上記グループ・テーブルの１番目の要素の代表有向グラフである有向グラフ１（４２１）とを比較する。コンピュータ・システムは、該比較にＴＥＡを適用する。コンピュータ・システムは、｛有向グラフ１、有向グラフ３｝の組をＴＥＡのパラメータに適用し検証する。有向グラフ３（４２３）は、有向グラフ１（４２１）に含まれる全てのノードを含み、且つ上記全てのノード間に有向グラフ１（４２１）と同じ経路があるため、上記検証の結果は成功となる。なお、ループ１（４１１）及びループ３（４１３）は同一のループではなく、違うアルゴリズムである。よって、コンピュータ・システムは、グループ・テーブルの１番目の要素を更新する。該更新では、コンピュータ・システムは、上記ループ３（４１３）の実行頻度である２０をグループ・テーブルの１番目の要素の実行頻度に加える。さらに、コンピュータ・システムは、有向グラフ３（４２３）をグループ・テーブルの１番目の要素に登録する。
グループ・テーブルの１番目の要素は、上記登録によって以下のようになる。
グループ・テーブル(１)
代表有向グラフ  ：有向グラフ１
実行頻度        ：４０
所属グラフ      ：有向グラフ１、有向グラフ３
なお、有向グラフ３（４２３）がグループ・テーブルに登録されたため、コンピュータ・システムは、上記グループ・テーブルの２番目の要素以降の代表有向グラフと有向グラフ３（４２３）とを比較する必要はない。
【０１０８】
次に、コンピュータ・システムは、有向グラフ４（４２４）について類似しているかどうかの判定を行う。
コンピュータ・システムは、有向グラフ４（４２４）とグループ・テーブルに登録された各代表有向グラフとを比較する。ここで比較される上記代表有向グラフは、有向グラフ１（４２１）及び有向グラフ２（４２２）である。最初に、コンピュータ・システムは、上記有向グラフ４（４２４）と上記グループ・テーブルの１番目の要素の代表有向グラフである有向グラフ１（４２１）とを比較する。コンピュータ・システムは、該比較にＴＥＡを適用する。コンピュータ・システムは、｛有向グラフ１、有向グラフ４｝の組をＴＥＡのパラメータに適用し検証する。有向グラフ４（４２４）は有向グラフ１（４２１）の全てのノードを含んでいないため、上記検証の結果は失敗となる。次に、コンピュータ・システムは、有向グラフ４（４２４）と上記グループ・テーブルの２番目の要素の代表有向グラフである有向グラフ２（４２２）とを比較する。コンピュータ・システムは、該比較にＴＥＡを適用する。コンピュータ・システムは、｛有向グラフ２、有向グラフ４｝の組をＴＥＡのパラメータに適用し検証する。有向グラフ４（４２４）は有向グラフ２（４２２）の全てのノードを含んでいないため、上記検証の結果は失敗となる。次に、コンピュータ・システムは、上記有向グラフ４（４２４）と上記グループ・テーブルの１番目の要素の代表有向グラフである有向グラフ１（４２１）とを比較する。コンピュータ・システムは、該比較にＴＥＡを適用する。コンピュータ・システムは、｛有向グラフ４、有向グラフ１｝の組をＴＥＡのパラメータに適用し検証する。有向グラフ１（４２１）は有向グラフ４（４２４）の全てのノードを含んでいないため、上記検証の結果は失敗となる。次に、コンピュータ・システムは、上記有向グラフ４（４２４）と上記グループ・テーブルの２番目の要素の代表有向グラフである有向グラフ２（４２２）とを比較する。コンピュータ・システムは、該比較にＴＥＡを適用する。コンピュータ・システムは、｛有向グラフ４、有向グラフ２｝の組をＴＥＡのパラメータに適用し検証する。有向グラフ２（４２２）は、有向グラフ４（４２４）に含まれる全てのノードを含み、且つ上記全てのノード間に有向グラフ４（４２４）と同じ経路があるため、上記検証の結果は成功となる。よって、コンピュータ・システムは、グループ・テーブルの２番目の要素を更新する。該更新では、コンピュータ・システムは、グループ・テーブルの２番目の要素の代表有向グラフを有向グラフ４（４２４）に置き換える。さらに、コンピュータ・システムは、上記ループ４（４１４）の実行頻度である５をグループ・テーブルの２番目の要素の実行頻度に加える。さらに、コンピュータ・システムは、有向グラフ４（４２４）をグループ・テーブルの２番目の要素に登録する。
該グループ・テーブルの２番目の要素は、上記更新によって以下のようになる。
グループ・テーブル(２)
代表有向グラフ  ：有向グラフ４
実行頻度        ：３０
所属グラフ      ：有向グラフ２、有向グラフ４
以上の処理により、上記有向グラフ１〜４（４２１〜４２４）が、グループ・テーブルに登録される。
上記有向グラフ１〜４（４２１〜４２４）の登録が全て終わった時点でのグループ・テーブルは、以下のようになる。
グループ・テーブル(１)
代表有向グラフ  ：有向グラフ１
実行頻度        ：４０
所属グラフ      ：有向グラフ１、有向グラフ３
グループ・テーブル(２)
代表有向グラフ  ：有向グラフ４
実行頻度        ：３０
所属グラフ      ：有向グラフ２、有向グラフ４
ループ１〜４（４１１〜４１４）それぞれの単独の実行頻度を見ると、ループ２（４１２）の実行頻度が一番大きい。しかし、似たようなループをまとめてみると、実はループ１（４１１）及びループ３（４１３）のようなパターンのループのほうが、他のパターンのループに比べて実行頻度が大きいという結果を得られる。これが、似たようなアルゴリズムをひとまとまりとすることによって、得られる効果である。
【０１０９】
最後に、コンピュータ・システムは、例えば、上記グループ・テーブルの要素ごとに、代表有向グラフに対応するループ及び実行頻度を降順に表示する。
【０１１０】
図４Ｃは、本発明の実施態様における、表示結果の例を示す。
上記登録が全て終わった時点でのグループは、グループ・テーブル（１）に登録されたグループ（以下、第１のグループ）及びグループ・テーブル（２）に登録されたグループ（以下、第２のグループ）の２つである。ここで、第１のグループの実行頻度は４０であり、第２のグループの実行頻度は３０である。よって、実行頻度の降順にグループを表示する場合、グループ１、そしてグループ２の順で表示される。
表示例（４３１）では、１行目に、グループ１の実行頻度、２〜５行目にグループ１の代表有向グラフである有向グラフ１に対応するアルゴリズムが表示される。そして、６行目に、グループ２の実行頻度、７〜９行目にグループ２の代表有向グラフである有向グラフ４に対応するアルゴリズムが表示される。
表示例（４３２）では、１行目に、グループ１の代表有向グラフに対応する識別子である「ループ１」が表示される。２行目に、グループ１の実行頻度、３〜６行目にグループ１の代表有向グラフである有向グラフ１に対応するアルゴリズムが表示される。７行目に、グループ１に属するグラフに対応する識別子である「ループ１」及び「ループ３」が表示される。そして、８行目に、グループ２の代表有向グラフに対応する識別子である「ループ４」が表示される。９行目に、グループ２の実行頻度、１０〜１２行目にグループ２の代表有向グラフである有向グラフ４に対応するアルゴリズムが表示される。１３行目に、グループ１に属するグラフに対応する識別子である「ループ２」及び「ループ４」が表示される。
上記表示により、ユーザは、出現頻度が高いループのパターンを見つけることが容易になる。そして、ユーザは、優先的に最適化する必要のあるプログラムを見つけることができる。
【０１１１】
本発明の１つの実施態様では、コンピュータ・システムは、有向グラフに含まれるノード及びエッジの少なくとも１つをビットマップとして表現する。以下の例では、命令を表すノードをビットマップとして表現する。ここで、命令を表すノードとは、例えば、上記ＡＳＴにおける演算子を表すノード又はＣＦＧにおけるノードである。
コンピュータ・システムは、類似性の判定において、上記ビットマップ間の包含関係を最初に調べる。コンピュータ・システムは、包含関係のないビットマップで表される有向グラフの組を、ＴＥＡを適用する対象の有向グラフの組から外すことができる。これにより、プログラムの解析時間が短縮される。
【０１１２】
図５は、本発明の実施態様におけるビットマップの例を示す。
表（５０１）は、有向グラフ１〜４（図４Ｂ、４２１〜４２４）に含まれる命令を表すノードをビットマップで表現したものである。表（５０１）の行は、各有向グラフを表す。表（５０１）の列は、各命令を表すノードを表す。表（５０１）の各セルには、有向グラフに命令を表すノードが含まれる場合１が設定され、含まれていない場合０が設定される。
例えば、有向グラフ（４２１）は、「Ｉｆ＜」、「ｌｏａｄ」、「Ｉｆ＝＝」、「ａｄｄ」及び「ａｓｓｉｇｎ」を含む。有向グラフ（４２１）は、「ｓｔｏｒｅ」を含まない。
【０１１３】
コンピュータ・システムは、上記ビットマップを使用することによって、ある有向グラフ（以下、有向グラフＡ）に含まれる全ての命令が、他の有向グラフ（以下、有向グラフＢ）に全て含まれているかを高速に判定できる。
コンピュータ・システムは、上記高速で判定をするために、有向グラフＡのビットマップと有向グラフＢのビットマップとの論理積（ＡＮＤ）をとる。コンピュータ・システムは、上記有向グラフＡのビットマップと論理積の結果のビットマップとを比較する。上記有向グラフＡのビットマップと上記論理積の結果のビットマップが同一であれば、コンピュータ・システムは、有向グラフＡに含まれる全ての命令が有向グラフＢに全ての含まれていると判断する。上記有向グラフＡのビットマップと上記論理積の結果のビットマップが異なれば、コンピュータ・システムは、上記有向グラフＡに含まれる全ての命令が有向グラフＢに全て含まれていないと判断する。なお、後者の判断がされた場合、コンピュータ・システムは、｛有向グラフＡ、有向グラフＢ｝の組について、ＴＥＡを適用する必要がなくなる。
例えば、有向グラフ（４２１）のビットマップと有向グラフ（４２２）のビットマップとの論理積の結果のビットマップは、１００１０１である。１００１０１は、有向グラフ（４２１）のビットマップ１１１１０１と異なる。よって、有向グラフ（４２２）は、有向グラフ（４２１）に含まれる命令の全てを含んでいない。よって、｛有向グラフ（４２１）、有向グラフ（４２２）｝の組は、ＴＥＡによる解析の対象外である。
また、有向グラフ（４２１）のビットマップと有向グラフ（４２３）のビットマップとの論理積の結果のビットマップは、１１１１０１である。１１１１０１は、有向グラフ（４２１）のビットマップ１１１１０１と同じである。よって、有向グラフ（４２３）は、有向グラフ（４２１）に含まれる命令の全てを含む。よって、｛有向グラフ（４２１）、有向グラフ（４２３）｝の組は、ＴＥＡによる解析の対象である。
このように、ビットマップを用いて包含関係を調べることにより、類似する候補を高速に選別することが可能となる。
【０１１４】
本発明の実施態様によれば、ユーザがグループ数の上限Ｎを設定することによって、プログラムの解析時間が短縮される。ユーザが上記上限Ｎを設定する場合、コンピュータ・システムは、有向グラフ全ての実行頻度が大きいグループを上記グループ・テーブルに優先的に残すようにする。
本発明の１つの実施態様として、グループ数が上限Ｎになった場合、コンピュータ・システムが、有向グラフ全ての実行頻度が１番小さいグループをグループ・テーブルから削除するようにしてもよい。
さらに別の実施態様として、グループ数が上限Ｎになった場合、コンピュータ・システムが、代表有向グラフ同士が類似するグループ同士を併合するようにしてもよい。上記併合では、コンピュータ・システムは、各グループに属する代表有向グラフ同士の類似性判定を行う。上記類似性判定は、判定部における判定と同一の判定でよい。代表有向グラフ同士が類似していると判定された場合、コンピュータ・システムは、上記類似していると判定された代表有向グラフが属するグループ（以下、類似するグループ）同士を併合する。ここで、上記類似するグループに属する代表有向グラフのうち、ノードの数が最も少ない代表有向グラフが、上記併合されたグループの代表有向グラフになる。また、上記類似するグループに属する有向グラフ全ての実行頻度の合計値が、上記併合されたグループに属する有向グラフ全ての実行頻度になる。さらに、上記類似するグループに属する有向グラフ全てが、上記併合されたグループに属する有向グラフになる。
【０１１５】
本発明の実施態様によれば、コンピュータ・システムは、有向グラフをアルゴリズムに戻すことができる。
本発明の１つの実施態様では、有向グラフをアルゴリズムに戻すために、ポインタを用いてもよい。コンピュータ・システムは、上記アルゴリズムを上記有向グラフに変換するときに、プログラム上の上記アルゴリズムがある場所を指すポインタを保存する。コンピュータ・システムは、上記有向グラフとともに上記ポインタをグループ・テーブルに格納する。コンピュータ・システムは、上記格納されたポインタを参照することによって、上記有向グラフに対応するアルゴリズムを取得することができる。
【０１１６】
図６は、本発明の実施態様における、コンピュータ・ハードウェアのブロック図を示す。
コンピュータ・システム（６０１）は、ＣＰＵ（６０３）とメイン・メモリ（６０２）と含み、これらはバス（６１４）に接続されている。ＣＰＵ（６０３）は好ましくは、３２ビット又は６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のＸｅｏｎ（商標）シリーズ、Ｃｏｒｅ（商標）シリーズ、Ａｔｏｍ（商標）シリーズ、Ｐｅｎｔｉｕｍ（商標）シリーズ、Ｃｅｌｅｒｏｎ（商標）シリーズ、ＡＭＤ社のＰｈｅｎｏｍ（商標）シリーズ、Ａｔｈｌｏｎ（商標）シリーズ、Ｔｕｒｉｏｎ（商標）シリーズ及びＳｅｍｐｒｏｎ（商標）などを使用することができる。バス（６１４）には、ディスプレイ・コントローラ（６０７）を介して、ＬＣＤモニタなどのディスプレイ（６１２）が接続される。ディスプレイ（６１２）は、コンピュータ・システムの管理のために、通信回線を介してネットワークに接続されたコンピュータ・システムについての情報と、そのコンピュータ・システム上で動作中のソフトウェアについての情報を、適当なグラフィック・インターフェースで表示するために使用される。バス（６１４）にはまた、ＩＤＥ又はＳＡＴＡコントローラ（６０４）を介して、ハードディスク又はシリコン・ディスク（６０５）と、ＣＤ−ＲＯＭ、ＤＶＤドライブ又はＢＤドライブ（６０６）が接続される。
【０１１７】
ハードディスク（６０５）には、オペレーティング・システム、プログラム及びデータが、メイン・メモリにロード可能に記憶されている。
【０１１８】
ＣＤ−ＲＯＭ、ＤＶＤ又はＢＤドライブ（６０６）は、必要に応じて、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ又はＢＤからプログラムをハードディスクに追加導入するために使用される。バス（６１４）には更に、キーボード・マウスコントローラ（６０９）を介して、キーボード（６１０）及びマウス（６１１）が接続されている。
【０１１９】
通信インタフェース（６１３）は、例えばイーサネット（商標）・プロトコルに従う。通信インタフェース（６１３）は、通信コントローラ（６０８）を介してバス（６１４）に接続され、コンピュータ・システム及び通信回線（６１５）を物理的に接続する役割を担い、コンピュータ・システムのオペレーティング・システムの通信機能のＴＣＰ／ＩＰ通信プロトコルに対して、ネットワーク・インターフェース層を提供する。なお、通信回線は、有線ＬＡＮ環境、或いは例えばＩＥＥＥ８０２．１１ａ／ｂ／ｇ／ｎなどの無線ＬＡＮ接続規格に基づく無線ＬＡＮ環境であってもよい。
【図面の簡単な説明】
【０１２０】
【図１Ａ】本発明の実施態様である、アルゴリズムから変換された有向グラフの一例を示す。
【図１Ｂ】本発明の実施態様である、有向グラフ間の類似の例を示す。
【図１Ｃ】本発明の実施態様における、分岐を含む有向グラフ間の類似判定の例を示す。
【図１Ｄ】本発明の実施態様における、ループを含む有向グラフ間の類似判定の例を示す。
【図２】本発明の実施態様における、システム構成図の例を示す。
【図３Ａ】本発明の実施態様における、プログラムの解析を支援するためのフローチャートの例を示す。
【図３Ｂ】本発明の実施態様における、解析処理を分割して処理を行う場合のフローチャートの例を示す。
【図４Ａ】本発明の実施態様における、入力情報のプログラムの例を示す。
【図４Ｂ】本発明の実施態様における、ループを有向グラフに変換した例を示す。
【図４Ｃ】本発明の実施態様における、表示結果の例を示す。
【図５】本発明の実施態様におけるビットマップの例を示す。
【図６】本発明の実施態様における、コンピュータ・ハードウェアのブロック図を示す。
【図１Ａ】
2010140434.tif 000003
【図１Ｂ】
2010140434.tif 000004
【図１Ｃ】
2010140434.tif 000005
【図１Ｄ】
2010140434.tif 000006
【図２】
2010140434.tif 000007
【図３Ａ】
2010140434.tif 000008
【図３Ｂ】
2010140434.tif 000009
【図４Ａ】
2010140434.tif 000010
【図４Ｂ】
2010140434.tif 000011
【図４Ｃ】
2010140434.tif 000012
【図５】
2010140434.tif 000013
【図６】
2010140434.tif 000014