(57)【要約】  プログラムの文および制御の依存関係を表す複数の依存要素で構成されるプログラム解析情報を用いて、可逆的に縮退可能な依存要素群が求められる。次に、求められた依存要素群を縮退することで依存要素が縮退されたプログラム依存グラフが生成される。依存要素の縮退により、プログラム依存グラフの頂点の数および辺の数を減らすことで、粗い粒度を有するプログラム依存グラフを生成できる。この結果、プログラムの並列化処理等の最適化処理に必要な計算量（計算時間）を削減できる。すなわち、可逆性を有する縮退されたプログラム依存グラフを生成することにより、大規模ソフトウエアの解析および最適化を現実的な時間で実現できる。
2007096935.tif 000002
【特許請求の範囲】
【請求項１】
プログラムの文および制御の依存関係を表す複数の依存要素で構成されるプログラム解析情報を用いて、可逆的に縮退可能な依存要素群を求め、求めた依存要素群を縮退することで依存要素が縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析方法。
【請求項２】
請求項１記載のプログラム解析方法において、
プログラム解析情報として制御フローグラフおよびプログラム依存グラフを用い、縮退可能な依存要素群を縮退し、縮退できない依存要素についてハンモックを探索し、探索されたハンモックを縮退することで縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析方法。
【請求項３】
請求項１記載のプログラム解析方法において、
プログラム解析情報としてプログラムの抽象構文木表現およびプログラム依存グラフを用い、抽象構文木表現中の依存要素である頂点集合を探索して、縮退可能な頂点集合を求め、縮退可能な頂点集合に対応するプログラム依存グラフ上の頂点集合を１つの頂点に縮退することで縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析方法。
【請求項４】
請求項１記載のプログラム解析方法において、
プログラム解析情報としてプログラムの抽象構文木表現を用い、抽象構文木表現中の依存要素である頂点集合を探索して、縮退可能な頂点集合を求め、縮退可能な頂点集合を１つの頂点に縮退し、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析方法。
【請求項５】
請求項１記載のプログラム解析方法において、
プログラム解析情報としてプログラム依存グラフを用い、プログラム依存グラフ中の依存要素である頂点間の結合度を探索し、所定の結合度を超える結合度を有する頂点集合を求め、求めた頂点集合のうち縮退可能な頂点集合をそれぞれ１つの頂点に縮退し、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析方法。
【請求項６】
請求項１記載のプログラム解析方法において、
縮退されたプログラム依存グラフにおいて制御の流れを再構成し、縮退された制御フローグラフを生成し、縮退された制御フローグラフから文レベルの制御フローグラフを生成し、文レベルの制御フローグラフからプログラムコードを生成することを特徴とするプログラム解析方法。
【請求項７】
プログラムの文および制御の依存関係を表す複数の依存要素で構成されるプログラム解析情報を用いて、可逆的に縮退可能な依存関係群を求める縮退判定部と、
前記縮退判定部により縮退可能と判定された依存要素群を縮退することで縮退されたプログラム依存グラフを生成するグラフ生成部とを備えていることを特徴とするプログラム解析装置。
【請求項８】
請求項７記載のプログラム解析装置において、
前記縮退判定部は、プログラム解析情報として制御フローグラフおよびプログラム依存グラフを用い、縮退可能な依存要素群を縮退し、縮退できない依存要素についてハンモックを探索し、探索されたハンモックを縮退し、
前記グラフ生成部は、縮退された依存要素群および縮退されたハンモックを用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析装置。
【請求項９】
請求項７記載のプログラム解析装置において、
前記縮退判定部は、プログラム解析情報としてプログラムの抽象構文木表現およびプログラム依存グラフを用い、抽象構文木表現中の依存要素である頂点集合を探索して、縮退可能な頂点集合を求め、縮退可能な頂点集合に対応するプログラム依存グラフ上の頂点集合を１つの頂点に縮退し、
前記グラフ生成部は、縮退された頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析装置。
【請求項１０】
請求項７記載のプログラム解析装置において、
前記縮退判定部は、プログラム解析情報としてプログラムの抽象構文木表現を用い、抽象構文木表現中の依存要素である頂点集合を探索して、縮退可能な頂点集合を求め、縮退可能な頂点集合を１つの頂点に縮退し、
前記グラフ生成部は、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析装置。
【請求項１１】
請求項７記載のプログラム解析装置において、
前記縮退判定部は、プログラム解析情報としてプログラム依存グラフを用い、プログラム依存グラフ中の依存要素である頂点間の結合度を探索し、所定の結合度を超える結合度を有する頂点集合を求め、求めた頂点集合のうち縮退可能な頂点集合をそれぞれ１つの頂点に縮退し、
前記グラフ生成部は、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析装置。
【請求項１２】
請求項７記載のプログラム解析装置において、
縮退されたプログラム依存グラフにおいて制御の流れを再構成する再構成部と、
縮退された制御フローグラフを生成し、縮退された制御フローグラフから文レベルの制御フローグラフを生成する制御フローグラフ生成部と、
文レベルの制御フローグラフからプログラムコードを生成するコード生成部とを備えていることを特徴とするプログラム解析装置。
【請求項１３】
プログラムを解析するために、コンピュータに、
プログラムの文および制御の依存関係を表したプログラム解析情報を用いて、可逆的に縮退可能な依存関係を求める縮退判定処理と、
前記縮退判定処理により縮退可能と判定された依存要素群を縮退することで縮退されたプログラム依存グラフを生成するグラフ生成処理とを実行させるためのプログラム解析プログラム。
【請求項１４】
請求項１３記載のプログラム解析プログラムにおいて、
前記縮退判定処理は、プログラム解析情報として制御フローグラフおよびプログラム依存グラフを用い、縮退可能な依存要素群を縮退し、縮退できない依存要素についてハンモックを探索し、探索されたハンモックを縮退し、
前記グラフ生成処理は、縮退された依存要素群および縮退されたハンモックを用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析プログラム。
【請求項１５】
請求項１３記載のプログラム解析プログラムにおいて、
前記縮退判定処理は、プログラム解析情報としてプログラムの抽象構文木表現およびプログラム依存グラフを用い、抽象構文木表現中の依存要素である頂点集合を探索して、縮退可能な頂点集合を求め、縮退可能な頂点集合に対応するプログラム依存グラフ上の頂点集合を１つの頂点に縮退し、
前記グラフ生成処理は、縮退された頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析プログラム。
【請求項１６】
請求項１３記載のプログラム解析プログラムにおいて、
前記縮退判定処理は、プログラム解析情報としてプログラムの抽象構文木表現を用い、抽象構文木表現中の依存要素である頂点集合を探索して、縮退可能な頂点集合を求め、縮退可能な頂点集合を１つの頂点に縮退し、
前記グラフ生成処理は、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析プログラム。
【請求項１７】
請求項１３記載のプログラム解析プログラムにおいて、
前記縮退判定処理は、プログラム解析情報としてプログラム依存グラフを用い、プログラム依存グラフ中の依存要素である頂点間の結合度を探索し、所定の結合度を超える結合度を有する頂点集合を求め、求めた頂点集合のうち縮退可能な頂点集合をそれぞれ１つの頂点に縮退し、
前記グラフ生成処理は、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析プログラム。
【請求項１８】
請求項１３記載のプログラム解析プログラムにおいて、
コンピュータに、
縮退されたプログラム依存グラフにおいて制御の流れを再構成する再構成処理と、
縮退された制御フローグラフを生成し、縮退された制御フローグラフから文レベルの制御フローグラフを生成する制御フローグラフ生成処理と、
文レベルの制御フローグラフからプログラムコードを生成するコード生成処理とを実行させるためのプログラム解析プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大規模なプログラムの最適化技術に関する。
【背景技術】
【０００２】
一般に、プロセッサの処理能力は、プロセッサの動作周波数を高くすることで向上し、あるいは命令を並列に実行することで向上する。しかし、プロセッサの消費電力は、動作周波数の増加とともに増加する。また、素子の構造は、動作周波数を上げるために微細にする必要がある。プロセッサの処理能力の向上は、消費電力の問題と素子の微細化による物理的な限界の問題とにより頭打ちになってきている。【０００３】
非特許文献１によれば、プロセッサが並列に処理できる命令の数は、２−４程度である。処理を投機的に実行するなどの手法を導入することで、並列性を多少向上できるが、それにも限度があることが知られている。プログラムを、命令レベルより大きな粒度で並列化し、複数のプロセッサで実行することにより、プログラムの実行効率は向上し、上述したプロセッサの処理能力の問題は緩和される。【０００４】
例えば、特許文献１では、プログラムに潜在する並列性を逐次プログラムから抽出する方法が提案されている。この方法では、プログラムの各文間のデータおよび制御の依存関係が抽出され、依存関係に基づいてプログラム依存グラフが生成される。プログラム依存グラフは、プログラムの意味を、文を表現する頂点と、制御の依存関係およびデータ依存関係を表現する辺とで表したグラフである。プログラム依存グラフは、制御の依存関係を扱うため、制御の流れを越える最適化が見込めるという特徴を持つ。また、プログラム依存グラフは、データの依存関係と制御の依存関係を表現しているため、最適化しやすいという特徴を持つ。【０００５】
非特許文献２、３には、プログラム依存グラフがプログラムの意味を表現できることが記載されている。非特許文献２は、2つのプログラムに対して、そのプログラム依存グラフが同形の場合、プログラムが意味的に等価であることを証明している。非特許文献３では、ある制約条件下にあるプログラム依存グラフから意味的に等価な制御フローグラフを作成する技術が明らかにされている。非特許文献４、５には、プログラム依存グラフに関する技術が記載されている。
【特許文献１】特開２００２−１１６９１６号公報
【非特許文献１】Ferrante, J., Ottenstein, K. J., Warren, J. E. (IBM, Michigan Tec., Rice U.): The program dependence graph and its use in optimization, ACM TOPLAS, Vol. 9, No. 3, pp. 319-349 (Jul. 1987).
【非特許文献２】S. Horwitz, J. Prins, and T. Reps: On the Adequacy of Program Dependence Graphs for Representing Programs, 15th POPL, pp. 146-157, 1988
【非特許文献３】S. Horwitz, J. Prins, and T. Reps: Integrating non-interfering versions of programs, ACM Transactions on Programming Languages and Systems, vol. 11, no. 3, pp. 345-387, 1989.
【非特許文献４】A.V. エイホ, R. セシィ, J.D. ウルマン 著: コンパイラ II -原理・技法・ツール-, p.736, サイエンス社, 1990
【非特許文献５】N. Kas'janov. Distinguishing hammocks in a directed graph. Soviet Math. Doklady, 16(5):448-450, 1975.
【非特許文献６】T. Ball, and S. Horwiz: Constructing Control Flow From Control Dependence, R-92-1091, Computer Sciences Department, University of Wisconsin-Madison, June 1992.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
プログラム依存グラフは、文または代入式を頂点としたグラフとなっている。例えば、数個の手続きなどを対象とする場合、頂点数は数十程度であり、プログラム依存グラフによる解析は可能である。しかし、大規模なソフトウェアでは、文または代入式を頂点とする場合、グラフの頂点数が数千から数万となってしまう。一般に、プログラム依存グラフを用いたプログラムの最適化問題は、グラフの規模の指数関数となることが知られている。そのため、文を単位として抽出された従来のプログラム依存グラフでは、プログラム全体を俯瞰した並列性を、現実的なリソース、時間内で抽出することが困難である。【０００７】
さらに、プログラム依存グラフを縮退する場合には、縮退されたプログラム依存グラフから正しいプログラムコードが生成できなくてはならない（可逆性を有する）。可逆性が保証されていないプログラム依存グラフでは、プログラムを最適化することができない。
本発明の目的は、可逆性を有する縮退されたプログラム依存グラフを生成することにより、大規模ソフトウエアの解析および最適化を現実的な時間で実現することである。
【課題を解決するための手段】
【０００８】
本発明の一形態では、まず、プログラムの文および制御の依存関係を表す複数の依存要素で構成されるプログラム解析情報を用いて、可逆的に縮退可能な依存要素群が求められる。次に、求められた依存要素群を縮退することで依存要素が縮退されたプログラム依存グラフが生成される。依存要素の縮退により、プログラム依存グラフの頂点の数および辺の数を減らすことで、粗い粒度を有するプログラム依存グラフを生成できる。この結果、プログラムの並列化処理等の最適化処理に必要な計算量（計算時間）を削減できる。すなわち、可逆性を有する縮退されたプログラム依存グラフを生成することにより、大規模ソフトウエアの解析および最適化を現実的な時間で実現できる。【０００９】
本発明の一形態における好ましい例では、縮退できない依存要素についてハンモックが探索され、探索されたハンモックを縮退することで縮退されたプログラム依存グラフが生成される。あるいは、抽象構文木表現における縮退可能な頂点集合を探索し、探索された頂点集合に対応するプログラム依存グラフ上の頂点集合を縮退することで縮退されたプログラム依存グラフが生成される。あるいは、抽象構文木表現における縮退可能な頂点集合を縮退し、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフが生成される。さらに、プログラム解析情報としてプログラム依存グラフを用い、プログラム依存グラフにおいて所定の結合度を超える頂点集合を求め、求めた頂点集合のうち縮退可能な頂点集合を縮退し、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフが生成される。【００１０】
本発明の一形態における好ましい例では、縮退されたプログラム依存グラフにおいて制御の流れを再構成されて、縮退された制御フローグラフが生成される。次に、縮退された制御フローグラフから文レベルの制御フローグラフが生成される。そして、文レベルの制御フローグラフからプログラムコードが生成される。
【発明の効果】
【００１１】
本発明では、可逆性を有する縮退されたプログラム依存グラフを生成することにより、大規模ソフトウエアの解析および最適化を現実的な時間で実現できる。
【図面の簡単な説明】
【００１２】
【図１】本発明の第１の実施形態を示すブロック図である。
【図２】図１に示したプログラム解析装置により実行される解析プログラムの処理フローの概要を示すフローチャートである。
【図３】図２に示したステップＳ２００の詳細を示すフローチャートである。
【図４】図３に示した処理の詳細を示すフローチャートである。
【図５】図２に示したステップＳ４００の詳細を示すフローチャートである。
【図６】第１の実施形態におけるプログラム依存グラフを縮退する例を示す説明図である。
【図７】本発明の第２の実施形態を示すフローチャートである。
【図８】本発明の第３の実施形態を示すフローチャートである。
【図９】図８のステップＳ２６０のアルゴリズムを示す説明図である。
【図１０】本発明の第４の実施形態を示すフローチャートである。
【図１１】第４の実施形態におけるプログラム依存グラフを縮退する例を示す説明図である。
【図１２】本発明の第５の実施形態を示すフローチャートである。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の実施形態を図面を用いて説明する。
図１は、本発明の第１の実施形態を示している。プログラム解析装置１００は、プログラム解析プログラム等を記憶するメモリ装置ＭＥＭ、プログラム解析プログラムを実行するプロセッサＣＰＵを有している。プログラム解析装置１００は、例えば、パーソナルコンピュータまたはワークステーション等により構成される。メモリ装置ＭＥＭは、例えば、ハードディスクドライブ装置である。プログラム解析装置１００には、ディスプレイＤＩＳＰ、キーボードやマウス等の入力デバイスＩＮＰＵＴ、およびディスクドライブ装置ＤＲＶが接続されている。【００１４】
ディスプレイＤＩＳＰは、入力デバイスＩＮＰＵＴおよびディスクドライブ装置ＤＲＶから入力された情報や、プログラム解析プログラムの実行結果等を表示する。ディスクドライブ装置ＤＲＶには、プログラム解析プログラムや、解析される逐次プログラムが記録されたＣＤ−ＲＯＭ、ＤＶＤ等の記録媒体がセットされる。プログラム解析プログラムおよび解析される逐次プログラムは、ディスクドライブ装置ＤＲＶを介してメモリ装置ＭＥＭにダウンロードされる。なお、ディスクドライブ装置ＤＲＶの代わりに、プログラム解析プログラム等を記憶したメモリカード等のシリコンディスクやハードディスクドライブ装置が、プログラム解析装置１００に接続されてもよい。なお、本発明のプログラム解析方法は、プロセッサＣＰＵがプログラム解析プログラムを実行することにより実現される。【００１５】
図２は、図１に示したプログラム解析装置１００（プロセッサＣＰＵ）により実行されるプログラム解析プログラムの処理フローの概要を示している。
まず、ステップＳ１００において、メモリ装置ＭＥＭに読み込まれた逐次プログラムが解析され、依存関係が抽出される。これにより、プログラム依存グラフＰＤＧ等のプログラム解析情報が生成される。プログラム解析情報は、プログラムの文および制御の依存関係を表す複数の依存要素で構成される。ステップＳ１００の処理は、従来のプログラム依存グラフＰＤＧの生成処理と同じである。【００１６】
次に、ステップＳ２００において、プログラム依存グラフの頂点数および辺数を減らすために、プログラム依存グラフＰＤＧの依存要素（依存関係）が縮退されて、頂点が融合される。この際、縮退されたプログラム依存グラフから正しいプログラムコードを生成するために、可逆的に縮退可能な依存要素のみが縮退される。そして、粗い粒度を有する縮退されたプログラム依存グラフＰＤＧが作成される。【００１７】
この後、ステップＳ３００において、縮退されたプログラム依存グラフＰＤＧの最適化が実行される。最適化では、例えば、グラフの形を変形することで、違う観点から頂点が融合できないかが検討される。最適化は、コード数を減らすことを目的として行われる。あるいは、最適化は、ステップ数を減らす、並列性の向上により処理速度を向上することを目的として行われる。そして、最適化が満足されるまで、ステップＳ２００、Ｓ３００が繰り返し実行され、縮退されたプログラム依存グラフＰＤＧが生成される。グラフの規模は、縮退により元のグラフの１／１０から１／１００になる。【００１８】
次に、ステップＳ４００において、縮退されたプログラム依存グラフＰＤＧからプログラムコードが生成される。例えば、プログラム依存グラフＰＤＧから並列処理が可能な複数のプログラムコードが生成される。すなわち、最適化されたプログラムが生成される。縮退によりグラフの規模が小さくなっているため、プログラムの並列性を抽出するための計算量は、従来に比べて大幅に少ない。この結果、現実的な時間にて、プログラムを最適化できる。【００１９】
図３は、図２に示したステップＳ２００の詳細を示している。まず、ステップＳ５００Ａにおいて、十分に縮退されているかが判定される。縮退が不十分な場合、処理はステップＳ５００に進む。縮退が十分な場合、処理は終了し、縮退したプログラム依存グラフＰＤＧが生成される。次に、ステップＳ５００において、縮退すべき依存要素（依存関係）が特定される。次に、ステップＳ６００において、特定した依存要素が縮退可能かどうかが判定される。ステップＳ５００Ａ、Ｓ５００、Ｓ６００を実行するプロセッサＣＰＵは、プログラムの文および制御の依存関係を表す複数の依存要素で構成されるプログラム解析情報を用いて、可逆的に縮退可能な依存関係群を求める縮退判定部として機能する。次に、ステップＳ７００において、縮退可能と判定された依存要素のみが縮退され、処理はステップＳ５００Ａに戻る。ステップＳ７００を実行するプロセッサＣＰＵは、縮退可能と判定された依存要素群を縮退することで縮退されたプログラム依存グラフＰＤＧを生成するグラフ生成部として機能する。【００２０】
本発明では、プログラムコードは、縮退されたプログラム依存グラフＰＤＧを用いて生成される。このため、縮退されたプログラム依存グラフＰＤＧから正しいプログラムコードが生成できることを、すなわち可逆性を、予め検証する必要がある。この検証を、ステップＳ５００、Ｓ６００で行う。すなわち、ステップＳ５００、Ｓ６００により、縮退されたプログラム依存グラフＰＤＧと元のプログラム依存グラフＰＤＧとの可逆性が保証される。換言すれば、可逆的に縮退可能な依存要素群を求めることで、元の逐次プログラムと、縮退されたプログラム依存グラフＰＤＧから生成された逐次プログラムとの等価性が保証される。【００２１】
非特許文献６より、後述する制御フローグラフＣＦＧ上で次の２つの条件（１）、（２）を満足する場合、そのプログラムのプログラム依存グラフから制御の流れを安全に再構成することができる（可逆性を有する）ことが知られている。
（１）制御フローグラフにおける逆辺(back-edge) ｅ＝（ｖ，ｗ）について、頂点ｗが頂点ｖを支配する(dominant)。
（２）頂点ｖをエントリとする自然なループ(非特許文献４)について、ループ内のいずれの頂点ｗも頂点ｖを後支配(post-dominant)しない。【００２２】
そこで、次の性質を満足する場合、頂点の集合Ｖｘの依存関係を縮退し1つの頂点ｖｘとみなすことができる。
＜性質＞：プログラム依存グラフＰＤＧ上の頂点の集合Ｖｘであって、頂点の集合Ｖｘに属する頂点が、対応する制御フローグラフＣＦＧ上でハンモックＨを形成する。
このように、本実施形態では、まず、縮退したプログラム依存グラフＰＤＧから適切なプログラムのコードを生成可能とするために、元のプログラムにおいて、上述した条件（１）あるいは条件（２）を満足しない部分プログラムについては、適切なハンモックを求め、縮退する。縮退した部分プログラムの制御の流れの情報は、付加情報として保存し、プログラムコードを生成するときに利用する。さらに、プログラム依存グラフＰＤＧの規模を縮小するために、複数の頂点を１つの頂点に縮退する場合、その頂点は制御フローグラフＣＦＧ上で、ハンモックＨを形成することを条件とする（縮退可能な条件）。【００２３】
ここで、ハンモックＨとは、有向グラフＧにおける次の条件（３）−（５）性質を満たす部分グラフである（非特許文献１、非特許文献５）。ハンモックの求め方は、非特許文献５に明らかにされている。
（３）エントリ頂点とイクジット頂点を持つ。
（４）ハンモックＨ外の頂点ｖからハンモックＨ内の頂点ｕを間の有向パスは必ずエントリ頂点を通る。
（５）ハンモックＨ内の頂点ｕからハンモック外の頂点ｗへの有向パスは必ずイクジット頂点を通る。【００２４】
図４は、図３に示した処理の詳細を示している。この例では、プログラム解析情報として、文レベルの制御フローグラフＣＦＧと文レベルのプログラム依存グラフＰＤＧが入力される。ステップＳ５１０、Ｓ５１２は、図３のステップＳ５００Ａに対応する処理である。ステップＳ６１０、Ｓ６１４、Ｓ７１０、Ｓ７１２は、図３のステップＳ５００に対応する処理である。ステップＳ７１０でハンモックを求めているため、頂点集合が縮退可能であることは自明である。このため、図３のステップＳ６００に対応する処理は省略されている。ステップＳ７１１、Ｓ７１３は、図３のステップＳ７００に対応する処理である。ステップＳ５１０、Ｓ６１０、Ｓ７１０、Ｓ７１１では、上述した条件（１）に対応する縮退処理を行う。ステップＳ５１２、Ｓ６１４、Ｓ７１２、Ｓ７１３では、上述した条件（２）に対応する縮退処理を行う。ステップＳ５１０、Ｓ５１２、Ｓ６１０、Ｓ７１０、Ｓ７１１を実行するプロセッサＣＰＵは、縮退判定部として機能する。ステップＳ７１１、Ｓ７１３を実行するプロセッサＣＰＵは、グラフ生成部として機能する。【００２５】
まず、ステップＳ５１０、Ｓ６１０では、制御フローグラフＣＦＧにおける全ての逆辺（ｖ、ｗ）について、上記条件（１）が満足するか否かが判定される。条件（１）を満足する場合、可逆的に縮退可能な依存要素（依存関係）が特定され、縮退される。条件（１）を満足しない逆辺（ｖ、ｗ）については、ステップＳ７１０において、頂点ｖ、ｗ（部分グラフ）を含む最小ハンモックＨＧｖが探索される。そして、ステップＳ７１１において、制御フローグラフＣＦＧおよびプログラム依存グラフＰＤＧに対して、ハンモックに含まれる頂点の集合が、１つの頂点に縮退され、処理はステップＳ５１０に戻る。【００２６】
次に、ステップＳ５１２、Ｓ６１４では、制御フローグラフＣＦＧにおける全ての分岐頂点ｖについて、上記条件（２）が満足するか否かが判定される。条件（２）を満足する場合、可逆的に縮退可能な依存要素（依存関係）が特定され、縮退される。条件（２）を満足しない分岐頂点ｖについては、ステップＳ７１２において、頂点ｖをエントリとする自然なループを含む最小ハンモックＨＧｖが探索される。そして、ステップＳ７１３において、制御フローグラフＣＦＧおよびプログラム依存グラフＰＤＧに対して、ハンモックに含まれる頂点の集合が、１つの頂点に縮退され、処理はステップＳ５１２に戻る。【００２７】
縮退されたプログラム依存グラフＰＤＧの規模は、元のプログラム依存グラフＰＤＧの１／１０−１／１００にすることが可能である。例えば、一般的な動画像圧縮ソフトウェアは、プログラムの行数より、頂点数が６０００程度になる。これを、頂点数が２桁少ない６０程度に縮退することで、定数の６０００乗の問題を、定数の１００乗程度の問題に変えることができる。すなわち、現実的な時間では解を得るのが困難な問題を、時間を多少かければ解ける問題に変えることができる。【００２８】
図５は、図２に示したステップＳ４００の詳細を示している。まず、ステップＳ４１０において、制御の流れが再構成され、縮退された制御フローグラフＣＦＧが生成される。この際、縮退されたプログラム依存グラフＰＤＧは、上記の条件（１）および条件（２）を満足するため、制御の流れを安全に再構成できる。すなわち、可逆性を有している。ステップＳ４１０を実行するプロセッサＣＰＵは、縮退されたプログラム依存グラフＰＤＧにおいて制御の流れを再構成する再構成部として機能する。【００２９】
次に、ステップＳ４２０において、縮退した頂点集合について、図４の処理時に保存された頂点間の制御の流れを用いて、縮退した頂点の制御の流れが展開される。これにより、文レベルの制御フローグラフＣＦＧが得られる。ステップＳ４２０を実行するプロセッサＣＰＵは、縮退された制御フローグラフＣＦＧを生成し、縮退された制御フローグラフから文レベルの制御フローグラフＣＦＧを生成する制御フローグラフ生成部として機能する。ステップＳ４３０において、適切なプログラム言語（プログラムコード）が出力され、最適化された逐次プログラムが得られる。ステップＳ４３０を実行するプロセッサＣＰＵは、文レベルの制御フローグラフＣＦＧからプログラムコードを生成するコード生成部として機能する。【００３０】
図６は、第１の実施形態においてプログラム依存グラフＰＤＧを縮退する例を示している。この例では、do-while文の制御構造に着目し、図中のプログラム内に下線で示した４ステップが縮退される。
以上、第１の実施形態では、プログラム依存グラフＰＤＧの規模（頂点数および辺数）を減らすために、プログラム依存グラフＰＤＧの依存要素（依存関係）を縮退して頂点を融合し、粗粒度のプログラム依存グラフＰＤＧを作成する。これにより、縮退されたプログラム依存グラフＰＤＧの規模を元のプログラム依存グラフＰＤＧに比べて大幅に小さくすることが可能になる。したがって、プログラムの並列化処理等の最適化に必要な計算量（計算時間）を削減できる。すなわち、大規模ソフトウエアの解析および最適化を現実的な時間で実現できる。【００３１】
可逆性を有する縮退を行うことで、縮退されたプログラム依存グラフＰＤＧと元のプログラム依存グラフＰＤＧとの可逆性を保証できる。これにより、縮退されたプログラム依存グラフＰＤＧから正しいプログラムを出力できる。
図７は、本発明の第２の実施形態を示している。第１の実施形態で説明した要素と同一の要素については、同一の符号を付し、これ等については、詳細な説明を省略する。この実施形態では、抽象構文木に基づいてプログラム依存グラフＰＤＧが縮退される。このために、プログラムの抽象構文木表現ＡＳＴ（Abstract Syntax Tree）および文レベルのプログラム依存グラフＰＤＧが入力される。プログラム解析装置が実施する処理は、図２に示したステップＳ２００の処理を除き第１の実施形態と同じである。具体的には、図３に示した処理の代わりに、図７に示した処理が実施される。ステップＳ５２０は、図３のステップＳ５００に対応する処理である。ステップＳ７２０は、図３のステップＳ７００に対応する処理である。ステップＳ５２０を実行するプロセッサＣＰＵは、縮退判定部として機能する。ステップＳ７２０を実行するプロセッサＣＰＵは、グラフ生成部として機能する。その他の構成および処理は、図１および図２と同じである。【００３２】
まず、ステップＳ５２０において、抽象構文木表現ＡＳＴの構文木が深さ優先で探索され、可逆的に縮退可能な頂点集合Ｖｂの集合Ｖが抽出される。次に、ステップＳ７２０において、集合Ｖの各要素Ｖｂについて、プログラム依存グラフＰＤＧ上の対応する頂点集合が探索され、これ等集合に含まれる頂点が１つの頂点に縮退される。すなわち、縮退されたプログラム依存グラフＰＤＧが生成される。【００３３】
以上、第２の実施形態においても、上述した第１の実施形態と同様の効果を得ることができる。さらに、この実施形態では、プログラムの抽象構文木表現ＡＳＴを用いることにより、規模が小さく、かつ可逆性が保証されたプログラム依存グラフＰＤＧを生成できる。
図８は、本発明の第３の実施形態を示している。第１および第２の実施形態で説明した要素と同一の要素については、同一の符号を付し、これ等については、詳細な説明を省略する。この実施形態では、第２の実施形態（図７）の探索および変換の手順を簡略化するために、プログラムの抽象構文木表現ＡＳＴのみが入力される。プログラム解析装置が実施する処理は、図２に示したステップＳ２００の処理を除き第１の実施形態と同じである。具体的には、図３に示した処理の代わりに、図８に示した処理が実施される。ステップＳ５３０は、図３のステップＳ５００に対応する処理である。ステップＳ７３０、Ｓ７３２は、図３のステップＳ７００に対応する処理である。ステップＳ６３０は、図３のステップＳ５００Ａに対応する処理である。ステップＳ５３０、Ｓ６３０を実行するプロセッサＣＰＵは、縮退判定部として機能する。ステップＳ７３０、Ｓ７３２を実行するプロセッサＣＰＵは、グラフ生成部として機能する。その他の構成および処理は、図１および図２と同じである。【００３４】
まず、ステップＳ５３０において、図７のステップＳ５２０と同様に、抽象構文木表現ＡＳＴの構文木が深さ優先で探索され、可逆的に縮退可能な頂点集合Ｖｂの集合Ｖが抽出される。次に、ステップＳ７３０において、抽象構文木上で頂点集合Ｖｂが、１つの頂点に縮退される。ステップＳ６３０において、探索が終了していない場合、ステップＳ５３０、Ｓ７３０が繰り返し実施される。探索が終了した場合、ステップＳ７３２において、図３に示したステップＳ７００と同様に、縮退されたプログラム依存グラフＰＤＧが生成される。【００３５】
図９は、図８のステップＳ２６０のアルゴリズムを示している。すなわち、抽象構文木表現から可逆的に縮退可能な頂点集合を求めるアルゴリズムは、図９のように表現できる。前述の制御の流れを再構成するための条件（１）および条件（２）を満たさないＣ言語の構文として、switch文、do-while文、break文、goto文、関数の末尾以外でのreturn文がある。switch文およびdo-while文については、文全体を1つの頂点に縮退することで、条件（１）および条件（２）を満足させることができる（処理１）。for文、while文内のbreak文については直近の親であるfor文あるいはwhile文全体を1つの頂点に縮退することで、条件（１）および条件（２）を満足させることができる（処理２）。goto文およびreturn文については、構文木表現から適切なハンモックを探索することが困難なため、制御フローグラフに変換した後、ハンモックを探索すればよい（処理３）。抽象構文木に基づくプログラム依存グラフＰＤＧの縮退は、goto文や関数の末尾以外でのreturn文をふくまないプログラムの場合、縮退する範囲の探索が簡単になるという利点がある。【００３６】
以上、第３の実施形態においても、上述した第１および第２の実施形態と同様の効果を得ることができる。
図１０は、本発明の第４の実施形態を示している。第１の実施形態で説明した要素と同一の要素については、同一の符号を付し、これ等については、詳細な説明を省略する。この実施形態は、プログラム依存グラフＰＤＧに基づいてこのプログラム依存グラフＰＤＧを縮退するための基本原理を示している。プログラム解析装置が実施する処理は、図２に示したステップＳ２００の処理を除き第１の実施形態と同じである。具体的には、図３に示した処理の代わりに、図１０に示した処理が実施される。ステップＳ５４０は、図３のステップＳ５００Ａに対応する処理である。ステップＳ５４２、Ｓ５４４は、図３のステップＳ５００に対応する処理である。ステップＳ６４０は、図３のステップＳ６００に対応する処理である。ステップＳ７４０は、図３のステップＳ７００に対応する処理である。ステップＳ５４０、Ｓ５４２、Ｓ５４４、Ｓ６４０を実行するプロセッサＣＰＵは、縮退判定部として機能する。ステップＳ７４０を実行するプロセッサＣＰＵは、グラフ生成部として機能する。その他の構成および処理は、図１および図２と同じである。【００３７】
まず、ステップＳ５４２において、入力された文レベルのプログラム依存グラフＰＤＧに基づいて、プログラム依存グラフＰＤＧ内の頂点間の結合の強さが求められる。結合度（依存要素）は、データ依存辺とその大きさ、および、制御依存辺、処理の大きさから計算される。次に、ステップＳ５４４において、頂点間の結合度が、予め設定された所定の結合度Ｘを超えるか否かが判定される。次に、ステップＳ６４０において、結合度が上記Ｘを超える頂点の依存関係が縮退可能か否かが判定される。縮退可能な場合、ステップＳ７４０において、頂点を結合し依存関係を縮退する。ステップＳ５４２、Ｓ５４４、Ｓ６４０、Ｓ７４０の処理を、プログラム依存グラフＰＤＧの全ての頂点間で実施することにより、縮退されたプログラム依存グラフＰＤＧが生成される。【００３８】
なお、この実施形態では、次の２つの条件（６）、（７）を満たすことが、可逆的に縮退可能な条件になる。
（６）対応する制御フローグラフＣＦＧ上で、頂点集合の外から頂点集合の内への分岐は、頂点集合の先頭頂点へのみである。対応する制御フローグラフＣＦＧ上で、頂点集合の内から頂点集合の外への分岐は、頂点集合の最後の頂点のみである。
（７）頂点間のデータ依存パスに外部の頂点は含まれない。【００３９】
図１１は、第４の実施形態においてプログラム依存グラフＰＤＧを縮退する例を示している。この例では、プログラム依存グラフＰＤＧの構造に着目し、図中のプログラム内に下線で示した２ステップが縮退される。
以上、第４の実施形態においても、上述した第１の実施形態と同様の効果を得ることができる。さらに、この実施形態では、プログラム依存グラフＰＤＧのみを用いることにより、規模が小さく、かつ可逆性が保証されたプログラム依存グラフＰＤＧを生成できる。【００４０】
図１２は、本発明の第５の実施形態を示している。第１および第４の実施形態で説明した要素と同一の要素については、同一の符号を付し、これ等については、詳細な説明を省略する。この実施形態は、第４の実施形態を、さらに具体的に示したものであり、プログラム依存グラフＰＤＧに基づいてこのプログラム依存グラフＰＤＧが縮退される。プログラム解析装置が実施する処理は、図２に示したステップＳ２００の処理を除き第１の実施形態と同じである。具体的には、図３に示した処理の代わりに、図１２に示した処理が実施される。ステップＳ５６０は、図３のステップＳ５００Ａに対応する処理である。ステップＳ５６２、Ｓ５６４、Ｓ５６６、Ｓ５６８、Ｓ５６９は、図３のステップＳ５００に対応する処理である。ステップＳ７５０は、図３のステップＳ６００とステップＳ７００に対応する処理である。ステップＳ７５２は、図３のステップＳ７００に対応する処理である。ステップＳ５６０、Ｓ５６２、Ｓ５６４、Ｓ５６６、Ｓ５６８、Ｓ５６９を実行するプロセッサＣＰＵは、縮退判定部として機能する。ステップＳ７５０、Ｓ７５２を実行するプロセッサＣＰＵは、グラフ生成部として機能する。その他の構成および処理は、図１および図２と同じである。【００４１】
図１２では、制御の流れを再構成するための上記条件（１）および条件（２）を満たすプログラム依存グラフＰＤＧの制御依存部分グラフは木構造になるという規則を用いて、プログラム依存グラフＰＤＧが縮退される。また、可逆的に縮退可能にするために、上述した条件（６）、（７）を満たすことが必要である。図１２に示した処理は、ステップＳ５６０に示すように、プログラム依存グラフＰＤＧの制御依存部分グラフを後順に走査することで実施される。【００４２】
まず、ステップＳ５６２において、頂点Ｖｘがリーフ（木構造の末端）にあるか否かが判定される。頂点Ｖｘがリーフにある場合、ステップＳ５６４において、リーフにある頂点Ｖｘに対して頂点間の結合度が求められる。頂点Ｖｘがリーフにない場合、すなわち、頂点Ｖｘが木構造の途中にある場合、ステップＳ７５０において、結合度が高く、条件（７）を満たす子頂点間が結合され、縮退される。【００４３】
次に、ステップＳ５６６において、頂点Ｖｘと子頂点間の結合度（親子間の結合度）が求められる。結合度が高い場合、ステップＳ７５２において、頂点Ｖｘ以下の制御依存部分木が、頂点に縮退される。次に、ステップＳ５６８において、縮退後の頂点Ｖｘに対して、結合度が求められる。結合度が低い場合、ステップＳ５６９において、頂点Ｖｘ以下の部分木と、部分木以外の頂点間との結合度が、頂点Ｖｘに集積される。これにより、上記条件（６）を満たす範囲で、結合すべき頂点集合を探索できる。そして、全ての探索が終了した時点でプログラム依存グラフＰＤＧが出力される。以上、第５の実施形態においても、上述した第１および第４の実施形態と同様の効果を得ることができる。【００４４】
なお、上述した実施形態では、プロセッサＣＰＵがプログラム解析プログラムを実行することにより、縮退されたプログラム依存グラフＰＤＧを生成し、このプログラム依存グラフＰＤＧに基づいて最適化された逐次プログラム（プログラムコード）を生成する例を述べた。本発明はかかる実施形態に限定されるものではない。例えば、上述した縮退判定部、グラフ生成部、再構成部、制御フローグラフ生成部およびコード生成部は、ハードウエアで実現されてもよい。【００４５】
以上、本発明について詳細に説明してきたが、上記の実施形態およびその変形例は発明の一例に過ぎず、本発明はこれに限定されるものではない。本発明を逸脱しない範囲で変形可能であることは明らかである。
【産業上の利用可能性】
【００４６】
本発明は、大規模なプログラムを最適化するために用いるプログラム依存グラフの生成方法に適用できる。
【図１】
2007096935.tif 000003
【図２】
2007096935.tif 000004
【図３】
2007096935.tif 000005
【図４】
2007096935.tif 000006
【図５】
2007096935.tif 000007
【図６】
2007096935.tif 000008
【図７】
2007096935.tif 000009
【図８】
2007096935.tif 000010
【図９】
2007096935.tif 000011
【図１０】
2007096935.tif 000012
【図１１】
2007096935.tif 000013
【図１２】
2007096935.tif 000014
【手続補正書】
【提出日】平成20年6月26日(2008.6.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
プログラムの文および制御の依存関係を表す複数の依存要素で構成されるプログラム解析情報を用いて、可逆的に縮退可能な依存要素群を求め、求めた依存要素群を縮退することで依存要素が縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析方法。
【請求項２】
請求項１記載のプログラム解析方法において、
プログラム解析情報として制御フローグラフおよびプログラム依存グラフを用い、縮退可能な依存要素群を縮退し、縮退できない依存要素についてハンモックを探索し、探索されたハンモックを縮退することで縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析方法。
【請求項３】
請求項１記載のプログラム解析方法において、
プログラム解析情報としてプログラムの抽象構文木表現およびプログラム依存グラフを用い、抽象構文木表現中の依存要素である頂点集合を探索して、縮退可能な頂点集合を求め、縮退可能な頂点集合に対応するプログラム依存グラフ上の頂点集合を１つの頂点に縮退することで縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析方法。
【請求項４】
請求項１記載のプログラム解析方法において、
プログラム解析情報としてプログラムの抽象構文木表現を用い、抽象構文木表現中の依存要素である頂点集合を探索して、縮退可能な頂点集合を求め、縮退可能な頂点集合を１つの頂点に縮退し、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析方法。
【請求項５】
請求項１記載のプログラム解析方法において、
プログラム解析情報としてプログラム依存グラフを用い、プログラム依存グラフ中の依存要素である頂点間の結合度を探索し、所定の結合度を超える結合度を有する頂点集合を求め、求めた頂点集合のうち縮退可能な頂点集合をそれぞれ１つの頂点に縮退し、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析方法。
【請求項６】
請求項１記載のプログラム解析方法において、
縮退されたプログラム依存グラフにおいて制御の流れを再構成し、縮退された制御フローグラフを生成し、縮退された制御フローグラフから文レベルの制御フローグラフを生成し、文レベルの制御フローグラフからプログラムコードを生成することを特徴とするプログラム解析方法。
【請求項７】
プログラムの文および制御の依存関係を表す複数の依存要素で構成されるプログラム解析情報を用いて、可逆的に縮退可能な依存要素群を求める縮退判定部と、
前記縮退判定部により縮退可能と判定された依存要素群を縮退することで縮退されたプログラム依存グラフを生成するグラフ生成部とを備えていることを特徴とするプログラム解析装置。
【請求項８】
請求項７記載のプログラム解析装置において、
前記縮退判定部は、プログラム解析情報として制御フローグラフおよびプログラム依存グラフを用い、縮退可能な依存要素群を縮退し、縮退できない依存要素についてハンモックを探索し、探索されたハンモックを縮退し、
前記グラフ生成部は、縮退された依存要素群および縮退されたハンモックを用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析装置。
【請求項９】
請求項７記載のプログラム解析装置において、
前記縮退判定部は、プログラム解析情報としてプログラムの抽象構文木表現およびプログラム依存グラフを用い、抽象構文木表現中の依存要素である頂点集合を探索して、縮退可能な頂点集合を求め、縮退可能な頂点集合に対応するプログラム依存グラフ上の頂点集合を１つの頂点に縮退し、
前記グラフ生成部は、縮退された頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析装置。
【請求項１０】
プログラムを解析するために、コンピュータに、
プログラムの文および制御の依存関係を表したプログラム解析情報を用いて、可逆的に縮退可能な依存要素群を求める縮退判定処理と、
前記縮退判定処理により縮退可能と判定された依存要素群を縮退することで縮退されたプログラム依存グラフを生成するグラフ生成処理とを実行させるためのプログラム解析プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大規模なプログラムの最適化技術に関する。
【背景技術】
【０００２】
一般に、プロセッサの処理能力は、プロセッサの動作周波数を高くすることで向上し、あるいは命令を並列に実行することで向上する。しかし、プロセッサの消費電力は、動作周波数の増加とともに増加する。また、素子の構造は、動作周波数を上げるために微細にする必要がある。プロセッサの処理能力の向上は、消費電力の問題と素子の微細化による物理的な限界の問題とにより頭打ちになってきている。
【０００３】
非特許文献１によれば、プロセッサが並列に処理できる命令の数は、２−４程度である。処理を投機的に実行するなどの手法を導入することで、並列性を多少向上できるが、それにも限度があることが知られている。プログラムを、命令レベルより大きな粒度で並列化し、複数のプロセッサで実行することにより、プログラムの実行効率は向上し、上述したプロセッサの処理能力の問題は緩和される。
【０００４】
例えば、特許文献１では、プログラムに潜在する並列性を逐次プログラムから抽出する方法が提案されている。この方法では、プログラムの各文間のデータおよび制御の依存関係が抽出され、依存関係に基づいてプログラム依存グラフが生成される。プログラム依存グラフは、プログラムの意味を、文を表現する頂点と、制御の依存関係およびデータ依存関係を表現する辺とで表したグラフである。プログラム依存グラフは、制御の依存関係を扱うため、制御の流れを越える最適化が見込めるという特徴を持つ。また、プログラム依存グラフは、データの依存関係と制御の依存関係を表現しているため、最適化しやすいという特徴を持つ。
【０００５】
非特許文献２、３には、プログラム依存グラフがプログラムの意味を表現できることが記載されている。非特許文献２は、2つのプログラムに対して、そのプログラム依存グラフが同形の場合、プログラムが意味的に等価であることを証明している。非特許文献３では、ある制約条件下にあるプログラム依存グラフから意味的に等価な制御フローグラフを作成する技術が明らかにされている。非特許文献４、５には、プログラム依存グラフに関する技術が記載されている。
【特許文献１】特開２００２−１１６９１６号公報
【非特許文献１】Ferrante, J., Ottenstein, K. J., Warren, J. E. (IBM, Michigan Tec., Rice U.): The program dependence graph and its use in optimization, ACM TOPLAS, Vol. 9, No. 3, pp. 319-349 (Jul. 1987).
【非特許文献２】S. Horwitz, J. Prins, and T. Reps: On the Adequacy of Program Dependence Graphs for Representing Programs, 15th POPL, pp. 146-157, 1988
【非特許文献３】S. Horwitz, J. Prins, and T. Reps: Integrating non-interfering versions of programs, ACM Transactions on Programming Languages and Systems, vol. 11, no. 3, pp. 345-387, 1989.
【非特許文献４】A.V. エイホ, R. セシィ, J.D. ウルマン 著: コンパイラ II -原理・技法・ツール-, p.736, サイエンス社, 1990
【非特許文献５】N. Kas'janov. Distinguishing hammocks in a directed graph. Soviet Math. Doklady, 16(5):448-450, 1975.
【非特許文献６】T. Ball, and S. Horwiz: Constructing Control Flow From Control Dependence, R-92-1091, Computer Sciences Department, University of Wisconsin-Madison, June 1992.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
プログラム依存グラフは、文または代入式を頂点としたグラフとなっている。例えば、数個の手続きなどを対象とする場合、頂点数は数十程度であり、プログラム依存グラフによる解析は可能である。しかし、大規模なソフトウエアでは、文または代入式を頂点とする場合、グラフの頂点数が数千から数万となってしまう。一般に、プログラム依存グラフを用いたプログラムの最適化問題は、グラフの規模の指数関数となることが知られている。そのため、文を単位として抽出された従来のプログラム依存グラフでは、プログラム全体を俯瞰した並列性を、現実的なリソース、時間内で抽出することが困難である。
【０００７】
さらに、プログラム依存グラフを縮退する場合には、縮退されたプログラム依存グラフから正しいプログラムコードが生成できなくてはならない（可逆性を有する）。可逆性が保証されていないプログラム依存グラフでは、プログラムを最適化することができない。
【０００８】
本発明の目的は、可逆性を有する縮退されたプログラム依存グラフを生成することにより、大規模ソフトウエアの解析および最適化を現実的な時間で実現することである。
【課題を解決するための手段】
【０００９】
本発明の一形態では、まず、プログラムの文および制御の依存関係を表す複数の依存要素で構成されるプログラム解析情報を用いて、可逆的に縮退可能な依存要素群が求められる。次に、求められた依存要素群を縮退することで依存要素が縮退されたプログラム依存グラフが生成される。依存要素の縮退により、プログラム依存グラフの頂点の数および辺の数を減らすことで、粗い粒度を有するプログラム依存グラフを生成できる。この結果、プログラムの並列化処理等の最適化処理に必要な計算量（計算時間）を削減できる。すなわち、可逆性を有する縮退されたプログラム依存グラフを生成することにより、大規模ソフトウエアの解析および最適化を現実的な時間で実現できる。
【００１０】
本発明の一形態における好ましい例では、縮退できない依存要素についてハンモックが探索され、探索されたハンモックを縮退することで縮退されたプログラム依存グラフが生成される。あるいは、抽象構文木表現における縮退可能な頂点集合を探索し、探索された頂点集合に対応するプログラム依存グラフ上の頂点集合を縮退することで縮退されたプログラム依存グラフが生成される。あるいは、抽象構文木表現における縮退可能な頂点集合を縮退し、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフが生成される。さらに、プログラム解析情報としてプログラム依存グラフを用い、プログラム依存グラフにおいて所定の結合度を超える頂点集合を求め、求めた頂点集合のうち縮退可能な頂点集合を縮退し、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフが生成される。
【００１１】
本発明の一形態における好ましい例では、縮退されたプログラム依存グラフにおいて制御の流れを再構成されて、縮退された制御フローグラフが生成される。次に、縮退された制御フローグラフから文レベルの制御フローグラフが生成される。そして、文レベルの制御フローグラフからプログラムコードが生成される。
【発明の効果】
【００１２】
本発明では、可逆性を有する縮退されたプログラム依存グラフを生成することにより、大規模ソフトウエアの解析および最適化を現実的な時間で実現できる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の実施形態を図面を用いて説明する。
【００１４】
図１は、本発明の第１の実施形態を示している。プログラム解析装置１００は、プログラム解析プログラム等を記憶するメモリ装置ＭＥＭ、プログラム解析プログラムを実行するプロセッサＣＰＵを有している。プログラム解析装置１００は、例えば、パーソナルコンピュータまたはワークステーション等により構成される。メモリ装置ＭＥＭは、例えば、ハードディスクドライブ装置である。プログラム解析装置１００には、ディスプレイＤＩＳＰ、キーボードやマウス等の入力デバイスＩＮＰＵＴ、およびディスクドライブ装置ＤＲＶが接続されている。
【００１５】
ディスプレイＤＩＳＰは、入力デバイスＩＮＰＵＴおよびディスクドライブ装置ＤＲＶから入力された情報や、プログラム解析プログラムの実行結果等を表示する。ディスクドライブ装置ＤＲＶには、プログラム解析プログラムや、解析される逐次プログラムが記録されたＣＤ−ＲＯＭ、ＤＶＤ等の記録媒体がセットされる。プログラム解析プログラムおよび解析される逐次プログラムは、ディスクドライブ装置ＤＲＶを介してメモリ装置ＭＥＭにダウンロードされる。なお、ディスクドライブ装置ＤＲＶの代わりに、プログラム解析プログラム等を記憶したメモリカード等のシリコンディスクやハードディスクドライブ装置が、プログラム解析装置１００に接続されてもよい。なお、本発明のプログラム解析方法は、プロセッサＣＰＵがプログラム解析プログラムを実行することにより実現される。
【００１６】
図２は、図１に示したプログラム解析装置１００（プロセッサＣＰＵ）により実行されるプログラム解析プログラムの処理フローの概要を示している。
【００１７】
まず、ステップＳ１００において、メモリ装置ＭＥＭに読み込まれた逐次プログラムが解析され、依存関係が抽出される。これにより、プログラム依存グラフＰＤＧ等のプログラム解析情報が生成される。プログラム解析情報は、プログラムの文および制御の依存関係を表す複数の依存要素で構成される。ステップＳ１００の処理は、従来のプログラム依存グラフＰＤＧの生成処理と同じである。
【００１８】
次に、ステップＳ２００において、プログラム依存グラフの頂点数および辺数を減らすために、プログラム依存グラフＰＤＧの依存要素（依存関係）が縮退されて、頂点が融合される。この際、縮退されたプログラム依存グラフから正しいプログラムコードを生成するために、可逆的に縮退可能な依存要素のみが縮退される。そして、粗い粒度を有する縮退されたプログラム依存グラフＰＤＧが作成される。
【００１９】
この後、ステップＳ３００において、縮退されたプログラム依存グラフＰＤＧの最適化が実行される。最適化では、例えば、グラフの形を変形することで、違う観点から頂点が融合できないかが検討される。最適化は、コード数を減らすことを目的として行われる。あるいは、最適化は、ステップ数を減らす、並列性の向上により処理速度を向上することを目的として行われる。そして、最適化が満足されるまで、ステップＳ２００、Ｓ３００が繰り返し実行され、縮退されたプログラム依存グラフＰＤＧが生成される。グラフの規模は、縮退により元のグラフの１／１０から１／１００になる。
【００２０】
次に、ステップＳ４００において、縮退されたプログラム依存グラフＰＤＧからプログラムコードが生成される。例えば、プログラム依存グラフＰＤＧから並列処理が可能な複数のプログラムコードが生成される。すなわち、最適化されたプログラムが生成される。縮退によりグラフの規模が小さくなっているため、プログラムの並列性を抽出するための計算量は、従来に比べて大幅に少ない。この結果、現実的な時間にて、プログラムを最適化できる。
【００２１】
図３は、図２に示したステップＳ２００の詳細を示している。まず、ステップＳ５００Ａにおいて、十分に縮退されているかが判定される。縮退が不十分な場合、処理はステップＳ５００に進む。縮退が十分な場合、処理は終了し、縮退したプログラム依存グラフＰＤＧが生成される。次に、ステップＳ５００において、縮退すべき依存要素（依存関係）が特定される。次に、ステップＳ６００において、特定した依存要素が縮退可能かどうかが判定される。ステップＳ５００Ａ、Ｓ５００、Ｓ６００を実行するプロセッサＣＰＵは、プログラムの文および制御の依存関係を表す複数の依存要素で構成されるプログラム解析情報を用いて、可逆的に縮退可能な依存関係群を求める縮退判定部として機能する。次に、ステップＳ７００において、縮退可能と判定された依存要素のみが縮退され、処理はステップＳ５００Ａに戻る。ステップＳ７００を実行するプロセッサＣＰＵは、縮退可能と判定された依存要素群を縮退することで縮退されたプログラム依存グラフＰＤＧを生成するグラフ生成部として機能する。
【００２２】
本発明では、プログラムコードは、縮退されたプログラム依存グラフＰＤＧを用いて生成される。このため、縮退されたプログラム依存グラフＰＤＧから正しいプログラムコードが生成できることを、すなわち可逆性を、予め検証する必要がある。この検証を、ステップＳ５００、Ｓ６００で行う。すなわち、ステップＳ５００、Ｓ６００により、縮退されたプログラム依存グラフＰＤＧと元のプログラム依存グラフＰＤＧとの可逆性が保証される。換言すれば、可逆的に縮退可能な依存要素群を求めることで、元の逐次プログラムと、縮退されたプログラム依存グラフＰＤＧから生成された逐次プログラムとの等価性が保証される。
【００２３】
非特許文献６より、後述する制御フローグラフＣＦＧ上で次の２つの条件（１）、（２）を満足する場合、そのプログラムのプログラム依存グラフから制御の流れを安全に再構成することができる（可逆性を有する）ことが知られている。
（１）制御フローグラフにおける逆辺(back-edge) ｅ＝（ｖ，ｗ）について、頂点ｗが頂点ｖを支配する(dominant)。
（２）頂点ｖをエントリとする自然なループ(非特許文献４)について、ループ内のいずれの頂点ｗも頂点ｖを後支配(post-dominant)しない。
【００２４】
そこで、次の性質を満足する場合、頂点の集合Ｖｘの依存関係を縮退し1つの頂点ｖｘとみなすことができる。
＜性質＞：プログラム依存グラフＰＤＧ上の頂点の集合Ｖｘであって、頂点の集合Ｖｘに属する頂点が、対応する制御フローグラフＣＦＧ上でハンモックＨを形成する。
【００２５】
このように、本実施形態では、まず、縮退したプログラム依存グラフＰＤＧから適切なプログラムのコードを生成可能とするために、元のプログラムにおいて、上述した条件（１）あるいは条件（２）を満足しない部分プログラムについては、適切なハンモックを求め、縮退する。縮退した部分プログラムの制御の流れの情報は、付加情報として保存し、プログラムコードを生成するときに利用する。さらに、プログラム依存グラフＰＤＧの規模を縮小するために、複数の頂点を１つの頂点に縮退する場合、その頂点は制御フローグラフＣＦＧ上で、ハンモックＨを形成することを条件とする（縮退可能な条件）。
【００２６】
ここで、ハンモックＨとは、有向グラフＧにおける次の条件（３）−（５）性質を満たす部分グラフである（非特許文献１、非特許文献５）。ハンモックの求め方は、非特許文献５に明らかにされている。
（３）エントリ頂点とイクジット頂点を持つ。
（４）ハンモックＨ外の頂点ｖからハンモックＨ内の頂点ｕを間の有向パスは必ずエントリ頂点を通る。
（５）ハンモックＨ内の頂点ｕからハンモック外の頂点ｗへの有向パスは必ずイクジット頂点を通る。
【００２７】
図４は、図３に示した処理の詳細を示している。この例では、プログラム解析情報として、文レベルの制御フローグラフＣＦＧと文レベルのプログラム依存グラフＰＤＧが入力される。ステップＳ５１０、Ｓ５１２は、図３のステップＳ５００Ａに対応する処理である。ステップＳ６１０、Ｓ６１４、Ｓ７１０、Ｓ７１２は、図３のステップＳ５００に対応する処理である。ステップＳ７１０でハンモックを求めているため、頂点集合が縮退可能であることは自明である。このため、図３のステップＳ６００に対応する処理は省略されている。ステップＳ７１１、Ｓ７１３は、図３のステップＳ７００に対応する処理である。ステップＳ５１０、Ｓ６１０、Ｓ７１０、Ｓ７１１では、上述した条件（１）に対応する縮退処理を行う。ステップＳ５１２、Ｓ６１４、Ｓ７１２、Ｓ７１３では、上述した条件（２）に対応する縮退処理を行う。ステップＳ５１０、Ｓ５１２、Ｓ６１０、Ｓ７１０、Ｓ７１１を実行するプロセッサＣＰＵは、縮退判定部として機能する。ステップＳ７１１、Ｓ７１３を実行するプロセッサＣＰＵは、グラフ生成部として機能する。
【００２８】
まず、ステップＳ５１０、Ｓ６１０では、制御フローグラフＣＦＧにおける全ての逆辺（ｖ、ｗ）について、上記条件（１）が満足するか否かが判定される。条件（１）を満足する場合、可逆的に縮退可能な依存要素（依存関係）が特定され、縮退される。条件（１）を満足しない逆辺（ｖ、ｗ）については、ステップＳ７１０において、頂点ｖ、ｗ（部分グラフ）を含む最小ハンモックＨＧｖが探索される。そして、ステップＳ７１１において、制御フローグラフＣＦＧおよびプログラム依存グラフＰＤＧに対して、ハンモックに含まれる頂点の集合が、１つの頂点に縮退され、処理はステップＳ５１０に戻る。
【００２９】
次に、ステップＳ５１２、Ｓ６１４では、制御フローグラフＣＦＧにおける全ての分岐頂点ｖについて、上記条件（２）が満足するか否かが判定される。条件（２）を満足する場合、可逆的に縮退可能な依存要素（依存関係）が特定され、縮退される。条件（２）を満足しない分岐頂点ｖについては、ステップＳ７１２において、頂点ｖをエントリとする自然なループを含む最小ハンモックＨＧｖが探索される。そして、ステップＳ７１３において、制御フローグラフＣＦＧおよびプログラム依存グラフＰＤＧに対して、ハンモックに含まれる頂点の集合が、１つの頂点に縮退され、処理はステップＳ５１２に戻る。
【００３０】
縮退されたプログラム依存グラフＰＤＧの規模は、元のプログラム依存グラフＰＤＧの１／１０−１／１００にすることが可能である。例えば、一般的な動画像圧縮ソフトウェアは、プログラムの行数より、頂点数が６０００程度になる。これを、頂点数が２桁少ない６０程度に縮退することで、定数の６０００乗の問題を、定数の１００乗程度の問題に変えることができる。すなわち、現実的な時間では解を得るのが困難な問題を、時間を多少かければ解ける問題に変えることができる。
【００３１】
図５は、図２に示したステップＳ４００の詳細を示している。まず、ステップＳ４１０において、制御の流れが再構成され、縮退された制御フローグラフＣＦＧが生成される。この際、縮退されたプログラム依存グラフＰＤＧは、上記の条件（１）および条件（２）を満足するため、制御の流れを安全に再構成できる。すなわち、可逆性を有している。ステップＳ４１０を実行するプロセッサＣＰＵは、縮退されたプログラム依存グラフＰＤＧにおいて制御の流れを再構成する再構成部として機能する。
【００３２】
次に、ステップＳ４２０において、縮退した頂点集合について、図４の処理時に保存された頂点間の制御の流れを用いて、縮退した頂点の制御の流れが展開される。これにより、文レベルの制御フローグラフＣＦＧが得られる。ステップＳ４２０を実行するプロセッサＣＰＵは、縮退された制御フローグラフＣＦＧを生成し、縮退された制御フローグラフから文レベルの制御フローグラフＣＦＧを生成する制御フローグラフ生成部として機能する。ステップＳ４３０において、適切なプログラム言語（プログラムコード）が出力され、最適化された逐次プログラムが得られる。ステップＳ４３０を実行するプロセッサＣＰＵは、文レベルの制御フローグラフＣＦＧからプログラムコードを生成するコード生成部として機能する。
【００３３】
図６は、第１の実施形態においてプログラム依存グラフＰＤＧを縮退する例を示している。この例では、do-while文の制御構造に着目し、図中のプログラム内に下線で示した４ステップが縮退される。
【００３４】
以上、第１の実施形態では、プログラム依存グラフＰＤＧの規模（頂点数および辺数）を減らすために、プログラム依存グラフＰＤＧの依存要素（依存関係）を縮退して頂点を融合し、粗粒度のプログラム依存グラフＰＤＧを作成する。これにより、縮退されたプログラム依存グラフＰＤＧの規模を元のプログラム依存グラフＰＤＧに比べて大幅に小さくすることが可能になる。したがって、プログラムの並列化処理等の最適化に必要な計算量（計算時間）を削減できる。すなわち、大規模ソフトウエアの解析および最適化を現実的な時間で実現できる。
【００３５】
可逆性を有する縮退を行うことで、縮退されたプログラム依存グラフＰＤＧと元のプログラム依存グラフＰＤＧとの可逆性を保証できる。これにより、縮退されたプログラム依存グラフＰＤＧから正しいプログラムを出力できる。
【００３６】
図７は、本発明の第２の実施形態を示している。第１の実施形態で説明した要素と同一の要素については、同一の符号を付し、これ等については、詳細な説明を省略する。この実施形態では、抽象構文木に基づいてプログラム依存グラフＰＤＧが縮退される。このために、プログラムの抽象構文木表現ＡＳＴ（Abstract Syntax Tree）および文レベルのプログラム依存グラフＰＤＧが入力される。プログラム解析装置が実施する処理は、図２に示したステップＳ２００の処理を除き第１の実施形態と同じである。具体的には、図３に示した処理の代わりに、図７に示した処理が実施される。ステップＳ５２０は、図３のステップＳ５００に対応する処理である。ステップＳ７２０は、図３のステップＳ７００に対応する処理である。ステップＳ５２０を実行するプロセッサＣＰＵは、縮退判定部として機能する。ステップＳ７２０を実行するプロセッサＣＰＵは、グラフ生成部として機能する。その他の構成および処理は、図１および図２と同じである。
【００３７】
まず、ステップＳ５２０において、抽象構文木表現ＡＳＴの構文木が深さ優先で探索され、可逆的に縮退可能な頂点集合Ｖｂの集合Ｖが抽出される。次に、ステップＳ７２０において、集合Ｖの各要素Ｖｂについて、プログラム依存グラフＰＤＧ上の対応する頂点集合が探索され、これ等集合に含まれる頂点が１つの頂点に縮退される。すなわち、縮退されたプログラム依存グラフＰＤＧが生成される。
【００３８】
以上、第２の実施形態においても、上述した第１の実施形態と同様の効果を得ることができる。さらに、この実施形態では、プログラムの抽象構文木表現ＡＳＴを用いることにより、規模が小さく、かつ可逆性が保証されたプログラム依存グラフＰＤＧを生成できる。
【００３９】
図８は、本発明の第３の実施形態を示している。第１および第２の実施形態で説明した要素と同一の要素については、同一の符号を付し、これ等については、詳細な説明を省略する。この実施形態では、第２の実施形態（図７）の探索および変換の手順を簡略化するために、プログラムの抽象構文木表現ＡＳＴのみが入力される。プログラム解析装置が実施する処理は、図２に示したステップＳ２００の処理を除き第１の実施形態と同じである。具体的には、図３に示した処理の代わりに、図８に示した処理が実施される。ステップＳ５３０は、図３のステップＳ５００に対応する処理である。ステップＳ７３０、Ｓ７３２は、図３のステップＳ７００に対応する処理である。ステップＳ６３０は、図３のステップＳ５００Ａに対応する処理である。ステップＳ５３０、Ｓ６３０を実行するプロセッサＣＰＵは、縮退判定部として機能する。ステップＳ７３０、Ｓ７３２を実行するプロセッサＣＰＵは、グラフ生成部として機能する。その他の構成および処理は、図１および図２と同じである。
【００４０】
まず、ステップＳ５３０において、図７のステップＳ５２０と同様に、抽象構文木表現ＡＳＴの構文木が深さ優先で探索され、可逆的に縮退可能な頂点集合Ｖｂの集合Ｖが抽出される。次に、ステップＳ７３０において、抽象構文木上で頂点集合Ｖｂが、１つの頂点に縮退される。ステップＳ６３０において、探索が終了していない場合、ステップＳ５３０、Ｓ７３０が繰り返し実施される。探索が終了した場合、ステップＳ７３２において、図３に示したステップＳ７００と同様に、縮退されたプログラム依存グラフＰＤＧが生成される。
【００４１】
図９は、図８のステップＳ５３０のアルゴリズムを示している。すなわち、抽象構文木表現から可逆的に縮退可能な頂点集合を求めるアルゴリズムは、図９のように表現できる。前述の制御の流れを再構成するための条件（１）および条件（２）を満たさないＣ言語の構文として、switch文、do-while文、break文、goto文、関数の末尾以外でのreturn文がある。switch文およびdo-while文については、文全体を1つの頂点に縮退することで、条件（１）および条件（２）を満足させることができる（処理１）。for文、while文内のbreak文については直近の親であるfor文あるいはwhile文全体を1つの頂点に縮退することで、条件（１）および条件（２）を満足させることができる（処理２）。goto文およびreturn文については、構文木表現から適切なハンモックを探索することが困難なため、制御フローグラフに変換した後、ハンモックを探索すればよい（処理３）。抽象構文木に基づくプログラム依存グラフＰＤＧの縮退は、goto文や関数の末尾以外でのreturn文をふくまないプログラムの場合、縮退する範囲の探索が簡単になるという利点がある。
【００４２】
以上、第３の実施形態においても、上述した第１および第２の実施形態と同様の効果を得ることができる。
【００４３】
図１０は、本発明の第４の実施形態を示している。第１の実施形態で説明した要素と同一の要素については、同一の符号を付し、これ等については、詳細な説明を省略する。この実施形態は、プログラム依存グラフＰＤＧに基づいてこのプログラム依存グラフＰＤＧを縮退するための基本原理を示している。プログラム解析装置が実施する処理は、図２に示したステップＳ２００の処理を除き第１の実施形態と同じである。具体的には、図３に示した処理の代わりに、図１０に示した処理が実施される。ステップＳ５４０は、図３のステップＳ５００Ａに対応する処理である。ステップＳ５４２、Ｓ５４４は、図３のステップＳ５００に対応する処理である。ステップＳ６４０は、図３のステップＳ６００に対応する処理である。ステップＳ７４０は、図３のステップＳ７００に対応する処理である。ステップＳ５４０、Ｓ５４２、Ｓ５４４、Ｓ６４０を実行するプロセッサＣＰＵは、縮退判定部として機能する。ステップＳ７４０を実行するプロセッサＣＰＵは、グラフ生成部として機能する。その他の構成および処理は、図１および図２と同じである。
【００４４】
まず、ステップＳ５４２において、入力された文レベルのプログラム依存グラフＰＤＧに基づいて、プログラム依存グラフＰＤＧ内の頂点間の結合の強さが求められる。結合度（依存要素）は、データ依存辺とその大きさ、および、制御依存辺、処理の大きさから計算される。次に、ステップＳ５４４において、頂点間の結合度が、予め設定された所定の結合度Ｘを超えるか否かが判定される。次に、ステップＳ６４０において、結合度が上記Ｘを超える頂点の依存関係が縮退可能か否かが判定される。縮退可能な場合、ステップＳ７４０において、頂点を結合し依存関係を縮退する。ステップＳ５４２、Ｓ５４４、Ｓ６４０、Ｓ７４０の処理を、プログラム依存グラフＰＤＧの全ての頂点間で実施することにより、縮退されたプログラム依存グラフＰＤＧが生成される。
【００４５】
なお、この実施形態では、次の２つの条件（６）、（７）を満たすことが、可逆的に縮退可能な条件になる。
（６）対応する制御フローグラフＣＦＧ上で、頂点集合の外から頂点集合の内への分岐は、頂点集合の先頭頂点へのみである。対応する制御フローグラフＣＦＧ上で、頂点集合の内から頂点集合の外への分岐は、頂点集合の最後の頂点のみである。
（７）頂点間のデータ依存パスに外部の頂点は含まれない。
【００４６】
図１１は、第４の実施形態においてプログラム依存グラフＰＤＧを縮退する例を示している。この例では、プログラム依存グラフＰＤＧの構造に着目し、図中のプログラム内に下線で示した２ステップが縮退される。
【００４７】
以上、第４の実施形態においても、上述した第１の実施形態と同様の効果を得ることができる。さらに、この実施形態では、プログラム依存グラフＰＤＧのみを用いることにより、規模が小さく、かつ可逆性が保証されたプログラム依存グラフＰＤＧを生成できる。
【００４８】
図１２は、本発明の第５の実施形態を示している。第１および第４の実施形態で説明した要素と同一の要素については、同一の符号を付し、これ等については、詳細な説明を省略する。この実施形態は、第４の実施形態を、さらに具体的に示したものであり、プログラム依存グラフＰＤＧに基づいてこのプログラム依存グラフＰＤＧが縮退される。プログラム解析装置が実施する処理は、図２に示したステップＳ２００の処理を除き第１の実施形態と同じである。具体的には、図３に示した処理の代わりに、図１２に示した処理が実施される。ステップＳ５６０は、図３のステップＳ５００Ａに対応する処理である。ステップＳ５６２、Ｓ５６４、Ｓ５６６、Ｓ５６８、Ｓ５６９は、図３のステップＳ５００に対応する処理である。ステップＳ７５０は、図３のステップＳ６００とステップＳ７００に対応する処理である。ステップＳ７５２は、図３のステップＳ７００に対応する処理である。ステップＳ５６０、Ｓ５６２、Ｓ５６４、Ｓ５６６、Ｓ５６８、Ｓ５６９を実行するプロセッサＣＰＵは、縮退判定部として機能する。ステップＳ７５０、Ｓ７５２を実行するプロセッサＣＰＵは、グラフ生成部として機能する。その他の構成および処理は、図１および図２と同じである。
【００４９】
図１２では、制御の流れを再構成するための上記条件（１）および条件（２）を満たすプログラム依存グラフＰＤＧの制御依存部分グラフは木構造になるという規則を用いて、プログラム依存グラフＰＤＧが縮退される。また、可逆的に縮退可能にするために、上述した条件（６）、（７）を満たすことが必要である。図１２に示した処理は、ステップＳ５６０に示すように、プログラム依存グラフＰＤＧの制御依存部分グラフを後順に走査することで実施される。
【００５０】
まず、ステップＳ５６２において、頂点Ｖｘがリーフ（木構造の末端）にあるか否かが判定される。頂点Ｖｘがリーフにある場合、ステップＳ５６４において、リーフにある頂点Ｖｘに対して頂点間の結合度が求められる。頂点Ｖｘがリーフにない場合、すなわち、頂点Ｖｘが木構造の途中にある場合、ステップＳ７５０において、結合度が高く、条件（７）を満たす子頂点間が結合され、縮退される。
【００５１】
次に、ステップＳ５６６において、頂点Ｖｘと子頂点間の結合度（親子間の結合度）が求められる。結合度が高い場合、ステップＳ７５２において、頂点Ｖｘ以下の制御依存部分木が、頂点に縮退される。次に、ステップＳ５６８において、縮退後の頂点Ｖｘに対して、結合度が求められる。結合度が低い場合、ステップＳ５６９において、頂点Ｖｘ以下の部分木と、部分木以外の頂点間との結合度が、頂点Ｖｘに集積される。これにより、上記条件（６）を満たす範囲で、結合すべき頂点集合を探索できる。そして、全ての探索が終了した時点でプログラム依存グラフＰＤＧが出力される。以上、第５の実施形態においても、上述した第１および第４の実施形態と同様の効果を得ることができる。
【００５２】
なお、上述した実施形態では、プロセッサＣＰＵがプログラム解析プログラムを実行することにより、縮退されたプログラム依存グラフＰＤＧを生成し、このプログラム依存グラフＰＤＧに基づいて最適化された逐次プログラム（プログラムコード）を生成する例を述べた。本発明はかかる実施形態に限定されるものではない。例えば、上述した縮退判定部、グラフ生成部、再構成部、制御フローグラフ生成部およびコード生成部は、ハードウエアで実現されてもよい。
【００５３】
上述した実施形態に関して、さらに以下の付記を開示する。
（付記１）
プログラムの文および制御の依存関係を表す複数の依存要素で構成されるプログラム解析情報を用いて、可逆的に縮退可能な依存要素群を求め、求めた依存要素群を縮退することで依存要素が縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析方法。
（付記２）
付記１記載のプログラム解析方法において、
プログラム解析情報として制御フローグラフおよびプログラム依存グラフを用い、縮退可能な依存要素群を縮退し、縮退できない依存要素についてハンモックを探索し、探索されたハンモックを縮退することで縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析方法。
（付記３）
付記１記載のプログラム解析方法において、
プログラム解析情報としてプログラムの抽象構文木表現およびプログラム依存グラフを用い、抽象構文木表現中の依存要素である頂点集合を探索して、縮退可能な頂点集合を求め、縮退可能な頂点集合に対応するプログラム依存グラフ上の頂点集合を１つの頂点に縮退することで縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析方法。
（付記４）
付記１記載のプログラム解析方法において、
プログラム解析情報としてプログラムの抽象構文木表現を用い、抽象構文木表現中の依存要素である頂点集合を探索して、縮退可能な頂点集合を求め、縮退可能な頂点集合を１つの頂点に縮退し、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析方法。
（付記５）
付記１記載のプログラム解析方法において、
プログラム解析情報としてプログラム依存グラフを用い、プログラム依存グラフ中の依存要素である頂点間の結合度を探索し、所定の結合度を超える結合度を有する頂点集合を求め、求めた頂点集合のうち縮退可能な頂点集合をそれぞれ１つの頂点に縮退し、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析方法。
（付記６）
付記１記載のプログラム解析方法において、
縮退されたプログラム依存グラフにおいて制御の流れを再構成し、縮退された制御フローグラフを生成し、縮退された制御フローグラフから文レベルの制御フローグラフを生成し、文レベルの制御フローグラフからプログラムコードを生成することを特徴とするプログラム解析方法。
（付記７）
プログラムの文および制御の依存関係を表す複数の依存要素で構成されるプログラム解析情報を用いて、可逆的に縮退可能な依存要素群を求める縮退判定部と、
前記縮退判定部により縮退可能と判定された依存要素群を縮退することで縮退されたプログラム依存グラフを生成するグラフ生成部とを備えていることを特徴とするプログラム解析装置。
（付記８）
付記７記載のプログラム解析装置において、
前記縮退判定部は、プログラム解析情報として制御フローグラフおよびプログラム依存グラフを用い、縮退可能な依存要素群を縮退し、縮退できない依存要素についてハンモックを探索し、探索されたハンモックを縮退し、
前記グラフ生成部は、縮退された依存要素群および縮退されたハンモックを用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析装置。
（付記９）
付記７記載のプログラム解析装置において、
前記縮退判定部は、プログラム解析情報としてプログラムの抽象構文木表現およびプログラム依存グラフを用い、抽象構文木表現中の依存要素である頂点集合を探索して、縮退可能な頂点集合を求め、縮退可能な頂点集合に対応するプログラム依存グラフ上の頂点集合を１つの頂点に縮退し、
前記グラフ生成部は、縮退された頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析装置。
（付記１０）
付記７記載のプログラム解析装置において、
前記縮退判定部は、プログラム解析情報としてプログラムの抽象構文木表現を用い、抽象構文木表現中の依存要素である頂点集合を探索して、縮退可能な頂点集合を求め、縮退可能な頂点集合を１つの頂点に縮退し、
前記グラフ生成部は、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析装置。
（付記１１）
付記７記載のプログラム解析装置において、
前記縮退判定部は、プログラム解析情報としてプログラム依存グラフを用い、プログラム依存グラフ中の依存要素である頂点間の結合度を探索し、所定の結合度を超える結合度を有する頂点集合を求め、求めた頂点集合のうち縮退可能な頂点集合をそれぞれ１つの頂点に縮退し、
前記グラフ生成部は、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析装置。
（付記１２）
付記７記載のプログラム解析装置において、
縮退されたプログラム依存グラフにおいて制御の流れを再構成する再構成部と、
縮退された制御フローグラフを生成し、縮退された制御フローグラフから文レベルの制御フローグラフを生成する制御フローグラフ生成部と、
文レベルの制御フローグラフからプログラムコードを生成するコード生成部とを備えていることを特徴とするプログラム解析装置。
（付記１３）
プログラムを解析するために、コンピュータに、
プログラムの文および制御の依存関係を表したプログラム解析情報を用いて、可逆的に縮退可能な依存要素群を求める縮退判定処理と、
前記縮退判定処理により縮退可能と判定された依存要素群を縮退することで縮退されたプログラム依存グラフを生成するグラフ生成処理とを実行させるためのプログラム解析プログラム。
（付記１４）
付記１３記載のプログラム解析プログラムにおいて、
前記縮退判定処理は、プログラム解析情報として制御フローグラフおよびプログラム依存グラフを用い、縮退可能な依存要素群を縮退し、縮退できない依存要素についてハンモックを探索し、探索されたハンモックを縮退し、
前記グラフ生成処理は、縮退された依存要素群および縮退されたハンモックを用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析プログラム。
（付記１５）
付記１３記載のプログラム解析プログラムにおいて、
前記縮退判定処理は、プログラム解析情報としてプログラムの抽象構文木表現およびプログラム依存グラフを用い、抽象構文木表現中の依存要素である頂点集合を探索して、縮退可能な頂点集合を求め、縮退可能な頂点集合に対応するプログラム依存グラフ上の頂点集合を１つの頂点に縮退し、
前記グラフ生成処理は、縮退された頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析プログラム。
（付記１６）
付記１３記載のプログラム解析プログラムにおいて、
前記縮退判定処理は、プログラム解析情報としてプログラムの抽象構文木表現を用い、抽象構文木表現中の依存要素である頂点集合を探索して、縮退可能な頂点集合を求め、縮退可能な頂点集合を１つの頂点に縮退し、
前記グラフ生成処理は、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析プログラム。
（付記１７）
付記１３記載のプログラム解析プログラムにおいて、
前記縮退判定処理は、プログラム解析情報としてプログラム依存グラフを用い、プログラム依存グラフ中の依存要素である頂点間の結合度を探索し、所定の結合度を超える結合度を有する頂点集合を求め、求めた頂点集合のうち縮退可能な頂点集合をそれぞれ１つの頂点に縮退し、
前記グラフ生成処理は、縮退した頂点を含む頂点集合を用いて縮退されたプログラム依存グラフを生成することを特徴とするプログラム解析プログラム。
（付記１８）
付記１３記載のプログラム解析プログラムにおいて、
コンピュータに、
縮退されたプログラム依存グラフにおいて制御の流れを再構成する再構成処理と、
縮退された制御フローグラフを生成し、縮退された制御フローグラフから文レベルの制御フローグラフを生成する制御フローグラフ生成処理と、
文レベルの制御フローグラフからプログラムコードを生成するコード生成処理とを実行させるためのプログラム解析プログラム。
【００５４】
以上、本発明について詳細に説明してきたが、上記の実施形態およびその変形例は発明の一例に過ぎず、本発明はこれに限定されるものではない。本発明を逸脱しない範囲で変形可能であることは明らかである。
【産業上の利用可能性】
【００５５】
本発明は、大規模なプログラムを最適化するために用いるプログラム依存グラフの生成方法に適用できる。
【図面の簡単な説明】
【００５６】
【図１】本発明の第１の実施形態を示すブロック図である。
【図２】図１に示したプログラム解析装置により実行される解析プログラムの処理フローの概要を示すフローチャートである。
【図３】図２に示したステップＳ２００の詳細を示すフローチャートである。
【図４】図３に示した処理の詳細を示すフローチャートである。
【図５】図２に示したステップＳ４００の詳細を示すフローチャートである。
【図６】第１の実施形態におけるプログラム依存グラフを縮退する例を示す説明図である。
【図７】本発明の第２の実施形態を示すフローチャートである。
【図８】本発明の第３の実施形態を示すフローチャートである。
【図９】図８のステップＳ５３０のアルゴリズムを示す説明図である。
【図１０】本発明の第４の実施形態を示すフローチャートである。
【図１１】第４の実施形態におけるプログラム依存グラフを縮退する例を示す説明図である。
【図１２】本発明の第５の実施形態を示すフローチャートである。
【国際調査報告】
2007096935.tif 000015
2007096935.tif 000016
2007096935.tif 000017