(57)【要約】【課題】データフローグラフを効率的に生成できるデータフローグラフ生成装置、データフローグラフ生成方法及びデータフローグラフ生成プログラムを提供することを課題とする。【解決手段】手続き型言語によって記述されるプログラムの到達定義に基づくデータフローグラフを生成において、プログラムを解析して変数定義関数テーブルと関数コールグラフを生成し、データフローグラフの出力変数に関係する対象変数毎に、変数定義関数テーブルと関数コールグラフに基づいて対象変数に関連する関数のみを抽出し、その抽出された関数を用いて対象変数に関するコントロールフローグラフを生成し、その生成されたコントロールフローグラフに対して到達定義解析を行い、対象変数毎の到達定義解析結果に基づいてデータフローグラフを生成する。【選択図】図２
2012164024.tif 000002
【特許請求の範囲】
【請求項１】
手続き型言語によって記述されるプログラムの到達定義に基づくデータフローグラフを生成するデータフローグラフ生成装置であって、
プログラムに含まれる全部又は一部の関数を解析し、変数定義関数テーブルと関数コールグラフを生成する関数解析手段と、
データフローグラフの出力変数に関係する対象変数毎に、前記関数解析手段で生成された変数定義関数テーブルと関数コールグラフに基づいて対象変数に関連する関数のみを抽出する関数抽出手段と、
データフローグラフの出力変数に関係する対象変数毎に、前記関数抽出手段で抽出された関数を用いて対象変数に関するコントロールフローグラフを生成するコントロールフローグラフ生成手段と、
データフローグラフの出力変数に関係する対象変数毎に、前記コントロールフローグラフ生成手段で生成されたコントロールフローグラフに対して到達定義解析を行う到達定義解析手段と、
前記到達定義解析手段で解析された対象変数毎の到達定義解析結果に基づいてデータフローグラフを生成するデータフローグラフ生成手段と、
を備えることを特徴とするデータフローグラフ生成装置。
【請求項２】
手続き型言語によって記述されるプログラムの到達定義に基づくデータフローグラフを生成するデータフローグラフ生成方法であって、
プログラムに含まれる全部又は一部の関数を解析し、変数定義関数テーブルと関数コールグラフを生成する関数解析ステップと、
データフローグラフの出力変数に関係する対象変数毎に、前記関数解析ステップで生成された変数定義関数テーブルと関数コールグラフに基づいて対象変数に関連する関数のみを抽出する関数抽出ステップと、
データフローグラフの出力変数に関係する対象変数毎に、前記関数抽出ステップで抽出された関数を用いて対象変数に関するコントロールフローグラフを生成するコントロールフローグラフ生成ステップと、
データフローグラフの出力変数に関係する対象変数毎に、前記コントロールフローグラフ生成ステップで生成されたコントロールフローグラフに対して到達定義解析を行う到達定義解析ステップと、
前記到達定義解析ステップで解析された対象変数毎の到達定義解析結果に基づいてデータフローグラフを生成するデータフローグラフ生成ステップと、
を含むことを特徴とするデータフローグラフ生成方法。
【請求項３】
手続き型言語によって記述されるプログラムの到達定義に基づくデータフローグラフを生成するためのデータフローグラフ生成プログラムであって、
コンピュータに、
プログラムに含まれる全部又は一部の関数を解析し、変数定義関数テーブルと関数コールグラフを生成する関数解析機能と、
データフローグラフの出力変数に関係する対象変数毎に、前記関数解析機能で生成された変数定義関数テーブルと関数コールグラフに基づいて対象変数に関連する関数のみを抽出する関数抽出機能と、
データフローグラフの出力変数に関係する対象変数毎に、前記関数抽出機能で抽出された関数を用いて対象変数に関するコントロールフローグラフを生成するコントロールフローグラフ生成機能と、
データフローグラフの出力変数に関係する対象変数毎に、前記コントロールフローグラフ生成機能で生成されたコントロールフローグラフに対して到達定義解析を行う到達定義解析機能と、
前記到達定義解析機能で解析された対象変数毎の到達定義解析結果に基づいてデータフローグラフを生成するデータフローグラフ生成機能と、
を実現させることを特徴とするデータフローグラフ生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、手続き型言語によって記述されるプログラムの到達定義に基づくデータフローグラフを生成するデータフローグラフ生成装置、データフローグラフ生成方法及びデータフローグラフ生成プログラムに関する。
【背景技術】
【０００２】
手続き型言語（例えば、Ｃ言語）で記述されたプログラムは、人間にとってはデータの依存関係や計算過程等を理解するのが難しい。そこで、このようなプログラムを人間が直感的に理解できるようにするために、プログラムの演算をノード、変数をエッジで表現したグラフとしてモデリングしたデータフローグラフ[Data flow graph]を生成し、データフローグラフを用いてプログラムの解析を行っている。データフローグラフを生成する方法としては、解析対象のプログラムからコントロールフローグラフ[Control flow graph]を生成し、コントロールフローグラフに対して出力変数に関係する変数に関して到達定義解析を行い、到達定義解析で得られる情報から出力変数を出力とするデータフローグラフを生成する。また、特許文献１には、プログラムの処理アルゴリズムを表現するデータフローグラフの作成方式において、そのプログラムを実際に実行することにより、実行した命令の情報を外部記憶にトレースデータとして格納し、その格納したトレースデータに対して演算を施すことによりデータフローグラフを作成することが開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開昭６３−２１４８３８号公報
【特許文献２】特開２００３−５０７２２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、従来の到達定義解析では、解析対象のプログラムの中に含まれる全ての変数や関数（出力変数に関係する変数以外の変数や出力変数に関係する変数に関連する関数以外の関数も含む）を反映してコントロールフローグラフを生成し、そのコントロールフローグラフに対して到達定義解析を行っている。そのため、到達定義解析において出力変数に関係する変数以外の変数の到達定義の計算及び伝播も行うため、計算コスト（メモリ、計算時間等）が大きくなる。特に、プログラムが大規模になると（例えば、時間やイベントに同期して繰り返し実行されるタスクを含むプログラム）、コントロールフローグラフも大規模になり、到達定義解析の計算コストが大きくなる。その結果、効率的にデータフローグラフを生成できない。
【０００５】
そこで、本発明は、データフローグラフを効率的に生成できるデータフローグラフ生成装置、データフローグラフ生成方法及びデータフローグラフ生成プログラムを提供することを課題とする。
【課題を解決するための手段】
【０００６】
本発明に係るデータフローグラフ生成装置は、手続き型言語によって記述されるプログラムの到達定義に基づくデータフローグラフを生成するデータフローグラフ生成装置であって、プログラムに含まれる全部又は一部の関数を解析し、変数定義関数テーブルと関数コールグラフを生成する関数解析手段と、データフローグラフの出力変数に関係する対象変数毎に、関数解析手段で生成された変数定義関数テーブルと関数コールグラフに基づいて対象変数に関連する関数のみを抽出する関数抽出手段と、データフローグラフの出力変数に関係する対象変数毎に、関数抽出手段で抽出された関数を用いて対象変数に関するコントロールフローグラフを生成するコントロールフローグラフ生成手段と、データフローグラフの出力変数に関係する対象変数毎に、コントロールフローグラフ生成手段で生成されたコントロールフローグラフに対して到達定義解析を行う到達定義解析手段と、到達定義解析手段で解析された対象変数毎の到達定義解析結果に基づいてデータフローグラフを生成するデータフローグラフ生成手段とを備えることを特徴とする。
【０００７】
このデータフローグラフ生成装置では、関数解析手段によって、プログラムに含まれる全部又は一部の関数を解析し、変数定義関数テーブルと関数コールグラフを生成する。そして、データフローグラフ生成装置では、データフローグラフの出力変数に関係する処理の対象の変数毎に、関数抽出手段によって変数定義関数テーブルと関数コールグラフに基づいてその対象変数に関連する関数のみを抽出し、コントロールフローグラフ生成手段によってその抽出された関数を用いて対象変数に関するコントロールフローグラフを生成し、到達定義解析手段によってその生成されたコントロールフローグラフに対して到達定義解析を行う。したがって、プログラムに含まれる出力変数に関係する変数以外の変数（処理の対象外の変数）やその処理の対象外の変数のみに関連する関数については、コントロールフローグラフの生成や到達定義解析の対象となっていない。そして、データフローグラフ生成装置では、データフローグラフ生成手段によって、そのデータフローグラフの出力変数に関係する対象変数毎の到達定義解析結果に基づいてデータフローグラフを生成する。このように、このデータフローグラフ生成装置は、テータフローグラフの出力変数に関係する変数毎にコントロールフローグラフを生成して到達定義解析を行い、その到達定義解析結果を統合してデータフローグラフを生成することにより、出力変数に関係する変数やその各変数に関連する関数のみを考慮してデータフローグラフを生成できるので、データフローグラフを効率的に生成できる。
【０００８】
本発明に係るデータフローグラフ生成方法は、手続き型言語によって記述されるプログラムの到達定義に基づくデータフローグラフを生成するデータフローグラフ生成方法であって、プログラムに含まれる全部又は一部の関数を解析し、変数定義関数テーブルと関数コールグラフを生成する関数解析ステップと、データフローグラフの出力変数に関係する対象変数毎に、関数解析ステップで生成された変数定義関数テーブルと関数コールグラフに基づいて対象変数に関連する関数のみを抽出する関数抽出ステップと、データフローグラフの出力変数に関係する対象変数毎に、関数抽出ステップで抽出された関数を用いて対象変数に関するコントロールフローグラフを生成するコントロールフローグラフ生成ステップと、データフローグラフの出力変数に関係する対象変数毎に、コントロールフローグラフ生成ステップで生成されたコントロールフローグラフに対して到達定義解析を行う到達定義解析ステップと、到達定義解析ステップで解析された対象変数毎の到達定義解析結果に基づいてデータフローグラフを生成するデータフローグラフ生成ステップとを含むことを特徴とする。このデータフローグラフ生成方法によれば、各ステップの処理を行うことにより、上記データフローグラフ生成装置の作用及び効果を奏する。
【０００９】
本発明に係るデータフローグラフ生成プログラムは、手続き型言語によって記述されるプログラムの到達定義に基づくデータフローグラフを生成するためのデータフローグラフ生成プログラムであって、コンピュータに、プログラムに含まれる全部又は一部の関数を解析し、変数定義関数テーブルと関数コールグラフを生成する関数解析機能と、データフローグラフの出力変数に関係する対象変数毎に、関数解析機能で生成された変数定義関数テーブルと関数コールグラフに基づいて対象変数に関連する関数のみを抽出する関数抽出機能と、データフローグラフの出力変数に関係する対象変数毎に、関数抽出機能で抽出された関数を用いて対象変数に関するコントロールフローグラフを生成するコントロールフローグラフ生成機能と、データフローグラフの出力変数に関係する対象変数毎に、コントロールフローグラフ生成機能で生成されたコントロールフローグラフに対して到達定義解析を行う到達定義解析機能と、到達定義解析機能で解析された対象変数毎の到達定義解析結果に基づいてデータフローグラフを生成するデータフローグラフ生成機能とを実現させることを特徴とする。このデータフローグラフ生成プログラムによれば、このプログラムをコンピュータに実行させることによって、上記データフローグラフ生成装置の作用及び効果を奏する。
【発明の効果】
【００１０】
本発明によれば、テータフローグラフの出力変数に関係する変数毎にコントロールフローグラフを生成して到達定義解析を行い、その到達定義解析結果を統合してデータフローグラフを生成することにより、出力変数に関係する変数やその各変数に関連する関数のみを考慮してデータフローグラフを生成できるので、データフローグラフを効率的に生成できる。
【図面の簡単な説明】
【００１１】
【図１】本実施の形態に係るデータフローグラフ生成装置の構成図である。
【図２】本実施の形態に係るデータフローグラフ生成装置でのメイン処理の流れを示すフローチャートである。
【図３】本実施の形態に係るデータフローグラフ生成装置でのグローバルコントロールフローグラフ生成処理の流れを示すフローチャートである。
【図４】手続き型言語で記述されたプログラムの一例である。
【図５】図４のプログラムを含む大規模プログラムを関数単位で分割した図である。
【図６】図５に示す大規模プログラムのデータフローグラフを従来の方法で生成する際のコントロールフローグラフである。
【図７】図５の大規模プログラムの関数コールグラと変数定義関数テーブルであり、（ａ）が関数コールグラフであり、（ｂ）が変数定義関数テーブルである。
【図８】図５の大規模プログラムに対する生成途中のデータフローグラフ（出力ポートのみ）である。
【図９】図５の大規模プログラムにおけるグローバル変数ｇｏｕｔに関する処理結果であり、（ａ）がｇｏｕｔに関するグローバルコントロールフローグラフであり、（ｂ）がｇｏｕｔに関する到達定義解析結果である。
【図１０】図５の大規模プログラムに対する生成途中のデータフローグラフ（グローバル変数ｇｏｕｔを定義している演算を追加）である。
【図１１】図５の大規模プログラムにおけるローカル変数ｔに関する到達定義解析結果である。
【図１２】図５の大規模プログラムに対する生成途中のデータフローグラフ（ローカル変数ｔを定義している演算を追加）である。
【図１３】図５の大規模プログラムにおけるグローバル変数ｙに関する到達定義解析結果である。
【図１４】図５の大規模プログラムに対する生成途中のデータフローグラフ（グローバル変数ｙを定義している演算を追加）である。
【図１５】図５の大規模プログラムに対する生成途中のデータフローグラフ（ローカル変数ｔを定義している演算を追加）である。
【図１６】図５の大規模プログラムにおけるグローバル変数ｘに関する到達定義解析結果である。
【図１７】図５の大規模プログラムに対する生成途中のデータフローグラフ（グローバル変数ｘを定義している演算を追加）である。
【図１８】図５の大規模プログラムに対する生成完了のデータフローグラフである。
【図１９】図５の大規模プログラムにおけるグローバル変数ｙに関連する関数のコールグラフ上での抽出結果である。
【図２０】図５の大規模プログラムにおけるグローバル変数ｙに関連する各関数におけるＳＥＳＥ領域であり、（ａ）が関数ｔａｓｋでのＳＥＳＥ領域であり、（ｂ）が関数ＡでのＳＥＳＥ領域であり、（ｃ）が関数ＦでのＳＥＳＥ領域であり、（ｄ）が関数ＧでのＳＥＳＥ領域である。
【図２１】図５の大規模プログラムにおけるグローバル変数ｙに関するグローバルコントロールフローグラフの生成に必要なＳＥＳＥ領域の選択結果である。
【図２２】図５の大規模プログラムにおけるグローバル変数ｙに関するグローバルコントロールフローグラフである。
【図２３】図５の大規模プログラムにおけるグローバル変数ｘに関連する各関数におけるＳＥＳＥ領域であり、（ａ）が関数ｔａｓｋでのＳＥＳＥ領域であり、（ｂ）が関数ＡでのＳＥＳＥ領域であり、（ｃ）が関数ＢでのＳＥＳＥ領域であり、（ｄ）が関数ＣでのＳＥＳＥ領域であり、（ｅ）が関数ＤでのＳＥＳＥ領域であり、（ｆ）が関数ＥでのＳＥＳＥ領域である。
【図２４】図５の大規模プログラムにおけるグローバル変数ｘに関するグローバルコントロールフローグラフの生成に必要なＳＥＳＥ領域の選択結果である。
【図２５】図５の大規模プログラムにおけるグローバル変数ｘに関するグローバルコントロールフローグラフである。
【発明を実施するための形態】
【００１２】
以下、図面を参照して、本発明に係るデータフローグラフ生成装置、データフローグラフ生成方法及びデータフローグラフ生成プログラムの実施の形態を説明する。なお、各図において同一又は相当する要素については同一の符号を付し、重複する説明を省略する。
【００１３】
本実施の形態では、本発明を、データフローグラフ生成装置に適用する。本実施の形態に係るデータフローグラフ生成装置は、解析対象のプログラム（ソースコード）とデータフローグラフの出力変数が決定されて入力されると、プログラムからコントロールフローグラフを生成し、コントロールフローグラフに対する到達定義解析で得られる情報からデータフローグラフを生成し、出力変数を出力とするデータフローグラフを生成する。本実施の形態に係るデータフローグラフ生成装置は、データフローグラフの生成だけを行う専用装置でもよいし、あるいは、汎用コンピュータでデータフローグラフ生成用のアプリケーションを実行することによって構成されてもよい。
【００１４】
なお、プログラムは、手続き型言語で記述されたプログラムである。図４には、手続き型言語で記述されたプログラムの一例を示しており、ｔａｓｋが繰り返し実行され、ｘ，ｙ，ｇｉｎ，ｇｏｕｔがグローバル変数である。ちなみに、繰り返し実行されるタスクの変数としてグローバル変数を含む場合、タスクが繰り返し実行される毎に演算された変数がグローバル変数にストアされる。そして、このグローバル変数にストアされた前回値が、次にタスクが実行されるときに各演算で用いられる。
【００１５】
本実施の形態に係るデータフローグラフ生成装置を具体的に説明する前に、図４のプログラムを一部として含む大規模プログラムを例として、図５及び図６を参照して、従来のデータフローグラフの生成方法を説明しておく。ここでは、データフローグラフの出力変数を、グローバル変数のｇｏｕｔとする。
【００１６】
図５には、図４のプログラムを一部として含む大規模プログラムを、関数単位で分割したものを示している。なお、図５に示すプログラムではグローバル変数ｘ，ｙ，ｇｉｎ，ｇｏｕｔに関連する演算以外の演算は、任意の演算として「・・・」で示している。
【００１７】
データフローグラフを生成する場合、まず、プログラムの構文を解析し、その解析結果に基づいてコントロールフローグラフを生成する。コントロールフローグラフは、プログラムを実行したときに通る可能性のある全経路がグラフで表され、ノード及びノードとノードとを繋ぐエッジで構成される。図６には、図５に示すプログラムに含まれる全ての変数及び全ての関数から生成されたコントロールフローグラフＣＦＧを示す。次に、このコントロールフローグラフＣＦＧを用いて、グローバル変数についての到達定義を算出し、到達定義を伝播させ、各ノードの到達定義集合を求める。そして、各ノードの到達定義集合を用いて出力変数ｇｏｕｔから到達定義を逆順に追跡し、その追跡した結果に基づいて出力変数ｇｏｕｔを出力とするデータフローグラフを生成する。
【００１８】
出力変数ｇｏｕｔのデータフローグラフを生成する場合、コントロールフローグラフＣＦＧにおいて出力変数ｇｏｕｔに関係するグローバル変数としてｘ，ｙ，ｇｉｎの到達定義を追跡する。しかし、コントロールフローグラフＣＦＧは、図５に示す大規模プログラムに含まれる全ての変数や関数を対象として生成されているので、コントロールフローグラフ全体が大規模なものになり、出力変数ｇｏｕｔに関係する変数以外の変数が関連する演算等に対応する多くのノードＮ０，Ｎ０・・・が含まれている。そのため、出力変数ｇｏｕｔのデータフローグラフの生成に関係のない無駄なノードへの到達定義の伝播や関係のない変数の到達定義の計算等により、計算コスト（メモリ、計算時間など）が非常に大きくなる。
【００１９】
それでは、図１〜図３を参照して、本実施の形態に係るデータフローグラフ生成装置１について説明する。図１は、本実施の形態に係るデータフローグラフ生成装置の構成図である。図２は、本実施の形態に係るデータフローグラフ生成装置でのメイン処理の流れを示すフローチャートである。図３は、本実施の形態に係るデータフローグラフ生成装置でのグローバルコントロールフローグラフ生成処理の流れを示すフローチャートである。
【００２０】
データフローグラフ生成装置１は、解析対象のプログラム（ソースコード）Ｐと出力変数Ｖｏｕｔが入力されると、プログラムＰに含まれる関数を解析して変数定義関数テーブルと関数コールグラフを生成し、出力変数Ｖｏｕｔに関係する処理の対象の変数毎に、変数定義関数テーブルと関数コールグラフに基づいて対象変数に関連する関数のみを抽出し、その抽出された関数を用いて対象変数に関するグローバルコントロールフローグラフを生成し、そのグローバルコントロールフローグラフに対して到達定義解析を行い、対象変数毎の到達定義解析結果に基づいてデータフローグラフＤＦＧを生成する。
【００２１】
具体的な処理について説明する前、データフローグラフ生成装置１の処理で用いる変数や関数について説明しておく。処理中のカレント変数を「ｖ」で示し、その処理中の変数ｖに関連するカレント関数を「ｆ」で示す。カレント変数ｖを定義している関数の集合を「Ωｄｅｆ」で示す。カレント変数ｖを参照している関数の集合を「Ωｒｅｆ」で示す。関数コールグラフにおける関数ｆとその上位の関数の集合を「↑ｆ」で示す。カレント変数ｖに関連する関数の集合を「Π」で示し、関数集合Πは下記の式（１）で定義される。出力変数Ｖｏｕｔに関係する変数であり、未だ処理を行っていない未処理変数キューを「ＶＱ」で示す。
【数１】
2012164024.tif 000003
【００２２】
それでは、具体的な処理について説明する。解析者によって解析対象のプログラムＰと出力変数Ｖｏｕｔが決定され、データフローグラフ生成装置１にプログラムＰと出力変数Ｖｏｕｔが入力される。すると、データフローグラフ生成装置１では、プログラムＰの構文を解析し、その解析結果に基づいてグローバル変数についての変数定義関数テーブルを算出（生成）するとともに関数のコールグラフを算出（生成）する（Ｓ１）。変数定義関数テーブルについてはプログラムＰに含まれる全てのグローバル変数についてでもよいし、出力変数Ｖｏｕｔに関係するグローバル変数についてだけでもよい。コールグラフについては、プログラムＰに含まれる全ての関数についてでもよいし、出力変数Ｖｏｕｔに関係するグローバル変数に関連する関数についてだけでもよい。
【００２３】
次に、データフローグラフ生成装置１では、変数定義関数テーブルに基づいて、出力変数Ｖｏｕｔを定義している関数ｆｏｕｔを取得する（Ｓ２）。そして、データフローグラフ生成装置１では、カレント変数ｖとして出力変数Ｖｏｕｔを設定し、カレント関数ｆとして出力変数Ｖｏｕｔを定義している関数ｆｏｕｔを設定する（Ｓ３）。さらに、データフローグラフ生成装置１では、データフローグラフに出力変数Ｖｏｕｔの出力ポートを付加する（Ｓ４）。ここまでの処理で、出力変数Ｖｏｕｔの出力ポートのみからなるデータフローグラフが構成される。
【００２４】
カレント変数ｖ、カレント関数ｆが設定（更新）される毎に、データフローグラフ生成装置１では、カレント変数ｖがグローバル変数か否かを判定する（Ｓ５）。カレント変数ｖは、最初にＳ３の処理で出力変数Ｖｏｕｔが設定され、それ以降はＳ１４の処理で出力変数Ｖｏｕｔに関係する変数が設定される。カレント関数ｆは、最初にＳ３の処理で関数ｆｏｕｔが設定され、それ以降はＳ１４の処理で出力変数Ｖｏｕｔに関係する各変数に関連する関数が設定される。
【００２５】
Ｓ５の判定でカレント変数ｖがグローバル変数でない（すなわち、ローカル変数）と判定した場合、データフローグラフ生成装置１では、カレント関数ｆについての到達定義解析を実行済みか否かを判定する（Ｓ６）。Ｓ６の判定でカレント関数ｆについての到達定義解析を実行していないと判定した場合、データフローグラフ生成装置１では、カレント関数ｆのコントロールフローグラフを生成し、そのコントロールフローグラフにおいてカレント変数ｖについての到達定義解析を実行する（Ｓ７）。そして、データフローグラフ生成装置１では、その到達定義解析結果に基づいて、データフローグラフにカレント変数ｖを定義している演算を追加する（Ｓ１０）。ここまでの処理で、生成途中のデータフローグラフにカレント変数ｖとして設定されたローカル変数を定義している演算に対応するノードとエッジが追加されたデータフローグラフが構成される。Ｓ６の処理で到達定義解析を実行済みと判定した場合又はＳ７の処理が終了した場合、データフローグラフ生成装置１では、カレント変数ｖ（ローカル変数）を定義している演算の右辺で参照されている変数を未処理変数キューＶＱに追加する（Ｓ１１）。参照している変数がない場合、未処理変数キューＶＱには追加されない。
【００２６】
Ｓ５の判定でカレント変数ｖがグローバル変数と判定した場合、データフローグラフ生成装置１では、カレント変数ｖの定義が解析対象のプログラムＰ（ソースコード）に含まれるか否かを判定する（Ｓ８）。カレント変数ｖの定義がプログラムＰに含まれている場合にはそのカレント変数ｖ（グローバル変数）についての到達定義解析が可能であるが、カレント変数ｖの定義がプログラムＰに含まれていない場合にはそのカレント変数ｖはプログラムＰ外で定義されて入力される値であり、到達定義解析ができない。
【００２７】
Ｓ８の判定でカレント変数ｖの定義がプログラムＰに含まれていると判定した場合、データフローグラフ生成装置１では、カレント変数ｖに関するグローバルコントロールフローグラフを生成し、そのグローバルコントロールフローグラフにおいてカレント変数ｖについての到達定義解析を実行する（Ｓ９）。グローバルコントロールフローグラフは、カレント変数ｖ（グローバル変数）に関係する部分だけを抽出し、そのカレント変数ｖに関連する関数をまたがって構成したコントロールフローグラフである。そして、データフローグラフ生成装置１では、その到達定義解析結果に基づいて、データフローグラフにカレント変数ｖを定義している演算を追加する（Ｓ１０）。ここまでの処理で、生成途中のデータフローグラフにカレント変数ｖとして設定されたグローバル変数を定義している演算に対応するノードとエッジが追加されたデータフローグラフが構成される。さらに、データフローグラフ生成装置１では、カレント変数ｖを定義している演算の右辺で参照されている変数を未処理変数キューＶＱに追加する（Ｓ１１）。なお、グローバルコントロールフローグラフの生成処理については、後で、図３のフローチャートに沿って詳細に説明する。
【００２８】
Ｓ８の判定でカレント変数ｖの定義がプログラムＰに含まれていないと判定した場合、データフローグラフ生成装置１では、データフローグラフにカレント変数ｖの入力ポートを付加する（Ｓ１２）。ここまでの処理で、生成途中のデータフローグラフに入力ポートが追加されたデータフローグラフが構成される。
【００２９】
Ｓ１１の処理が終了した場合又はＳ１２の処理が終了した場合、データフローグラフ生成装置１では、未処理変数キューＶＱが空か否かを判定する（Ｓ１３）。Ｓ１３の判定で未処理変数キューＶＱが空でないと判定した場合、データフローグラフ生成装置１では、未処理変数キューＶＱの中に残っている変数の中から一つ変数を取り出してカレント変数ｖとして更新するとともに、その更新されたカレント変数ｖに関連する関数をカレント関数ｆとして更新し（Ｓ１４）、Ｓ５の処理に戻る。Ｓ１３の判定で未処理変数キューＶＱが空と判定した場合、出力変数Ｖｏｕｔに関係する全ての変数についての処理が終了したことになるので、データフローグラフ生成装置１では、処理を終了する。この時点で生成されているデータフローグラフが、生成完了の出力変数Ｖｏｕｔを出力とするデータフローグラフである。
【００３０】
Ｓ９の処理でグローバルコントロールフローグラフを生成する場合、データフローグラフ生成装置１では、まず、変数定義関数テーブルとコールグラフに基づいて、カレント変数ｖ（グローバル変数）に関連する関数集合Πを抽出する（Ｓ２０）。この処理では、カレント変数ｖを定義している関数の集合Ωｄｅｆを抽出し、カレント変数ｖを参照している関数の集合Ωｒｅｆを抽出する。そして、関数集合Ωｄｅｆに含まれる各関数ｆｄｅｆについて、コールグラフから関数ｆｄｅｆとその上位の関数からなる関数集合↑ｆｄｅｆを抽出する。また、関数集合Ωｒｅｆに含まれる各関数ｆｒｅｆについて、コールグラフから関数ｆｒｅｆとその上位の関数からなる関数集合↑ｆｒｅｆを抽出する。そして、上記の式（１）により、関数集合Ωｄｅｆに含まれる各関数ｆｄｅｆの関数集合↑ｆｄｅｆと関数集合Ωｒｅｆに含まれる各関数ｆｒｅｆの関数集合↑ｆｒｅｆの和集合を求め、カレント変数ｖに関連する関数集合Πを抽出する。
【００３１】
次に、データフローグラフ生成装置１では、カレント変数ｖに関連する関数集合Πに含まれる各関数についてのコントロールフローグラフを生成し、その各関数のコントロールフローグラフにおいてＳＥＳＥ[Single Entry Single Exit]領域を算出する（Ｓ２１）。ＳＥＳＥ領域は、一つの入力（入口）と一つの出力（出口）を持つ最小単位である。
【００３２】
次に、データフローグラフ生成装置１では、カレント変数ｖに関連する関数集合Πに含まれる各関数についてのＳＥＳＥ領域の中から、関数集合Πに含まれる各関数をコールしているＳＥＳＥ領域を選択し、カレント変数ｖを定義しているＳＥＳＥ領域を選択し、カレント変数ｖを参照しているＳＥＳＥ領域を選択し、その選択されたＳＥＳＥ領域を包含するＳＥＳＥ領域を選択する（Ｓ２２）。ここで、カレント変数ｖに関連する全てのＳＥＳＥ領域が抽出される。
【００３３】
そして、データフローグラフ生成装置１では、選択されたＳＥＳＥ領域を用いて、そのＳＥＳＥ領域に含まれるノードだけを用いてコントロールフローグラフを構成する（Ｓ２３）。この構成されたコントロールフローグラフが、グローバルコントロールフローグラフである。
【００３４】
なお、本実施の形態では、Ｓ１の処理が特許請求の範囲に記載する関数解析手段、関数解析ステップ、関数解析機能に相当し、Ｓ２０の処理が特許請求の範囲に記載する関数抽出手段、関数抽出ステップ、関数抽出機能に相当し、Ｓ２１〜Ｓ２３の処理が特許請求の範囲に記載するコントロールフローグラフ生成手段、コントロールフローグラフ生成ステップ、コントロールフローグラフ生成機能に相当し、Ｓ９の処理が特許請求の範囲に記載する到達定義解析手段、到達定義解析ステップ、到達定義解析機能に相当し、Ｓ１１の処理が特許請求の範囲に記載するデータフローグラフ生成手段、データフローグラフ生成ステップ、データフローグラフ生成機能に相当する。
【００３５】
次に、図４のプログラムを一部として含む大規模プログラムを例として、図７〜図１８を参照して、データフローグラフ生成装置１におけるデータフローグラフの具体的な生成過程を説明する。図５には、図４のプログラムを一部として含む大規模プログラムを、関数に分割したものを示している。この大規模プログラムがプログラムＰとして決定されるとともにグローバル変数ｇｏｕｔが出力変数Ｖｏｕｔとして決定されると、データフローグラフ生成装置１に、そのプログラムＰの大規模プログラムと出力変数のｇｏｕｔが入力される。ちなみに、出力変数ｇｏｕｔに関係する変数としては、ｇｏｕｔを定義する演算（ｇｏｕｔ＝ｙ＊ｔ）で参照されるグローバル変数ｙとローカル変数ｔ、そのグローバル変数ｙを定義する演算（ｙ＝ｘ＋ｔ）で参照されるグローバル変数ｘとローカル変数ｔ、そのグローバル変数ｘを定義する演算（ｘ＝ｇｉｎ）で参照されるグローバル変数ｇｉｎである。なお、出力変数Ｖｏｕｔについては、ｙ等の他の変数でもよい。
【００３６】
なお、各図で示すデータフローグラフでは、入出力ポートを楕円で表し、演算を四角形で表し、データセレクタをひし形で表し、エッジには変数が付加される。背景が白色のポートは未処理変数であることを意味し、さらなる拡張の可能性があることを示す。背景が黒色のポート、演算、データセレクタは処理済みであることを意味する。点線で示すエッジは、ｔａｓｋが繰り返し実行される場合のグローバル変数の前回値の参照を意味する。
【００３７】
まず、データフローグラフ生成装置１では、上記のＳ１の処理として、プログラムＰの構文を解析し、プログラムＰに含まれる関数のコールグラフとプログラムＰに含まれる各変数についての変数定義関数テーブルを算出する。図７（ａ）には、図５に示す分割された各関数からなるコールグラフを示している。図７（ｂ）には、以下の処理で必要となるグローバル変数ｇｏｕｔ，ｘ，ｙについての変数定義関数テーブルを示している。
【００３８】
次に、データフローグラフ生成装置１では、上記のＳ２の処理として、式（２）に示すように、変数定義関数テーブルから、出力変数Ｖｏｕｔ（＝ｇｏｕｔ）を定義している関数ｆｏｕｔとして関数Ｇを取得する。また、データフローグラフ生成装置１では、上記のＳ３の処理として、式（３）に示すように、カレント変数ｖとして出力変数Ｖｏｕｔ（＝ｇｏｕｔ）を設定する。また、データフローグラフ生成装置１では、上記のＳ３の処理として、式（４）に示すように、カレント関数ｆとして関数ｆｏｕｔ（＝Ｇ）を設定する。
【数２】
2012164024.tif 000004
【００３９】
次に、データフローグラフ生成装置１では、上記のＳ４の処理として、データフローグラフに出力変数Ｖｏｕｔ（＝ｇｏｕｔ）の出力ポートを付加する。ここで、図８に示すように、ｇｏｕｔの出力ポートＯＰのみからなる生成途中のデータフローグラフＤＦＧ１が構成される。
【００４０】
次に、データフローグラフ生成装置１では、上記のＳ５の処理として、カレント変数ｖ（＝ｇｏｕｔ）がグローバル変数か否かを判定する。ここでは、カレント変数ｖはグローバル変数のｇｏｕｔなので、グローバル変数と判定される。データフローグラフ生成装置１では、上記のＳ８の処理として、カレント変数ｖ（＝ｇｏｕｔ）の定義がプログラムＰに含まれているか否かを判定する。ここでは、カレント変数ｖのｇｏｕｔは関数Ｇ内の演算（ｇｏｕｔ＝ｙ＊ｔ）で定義されているので、プログラムＰに含まれていると判定される。データフローグラフ生成装置１では、上記のＳ９の処理として、カレント変数ｖ（＝ｇｏｕｔ）に関するグローバルコントロールフローグラフを生成し、そのグローバルコントロールフローグラフにおいてカレント変数ｖ（＝ｇｏｕｔ）についての到達定義解析を実行する。図９（ａ）には、グローバル変数ｇｏｕｔに関するグローバルコントロールフローグラフＧＣＦＧｇｏｕｔを示しており、グローバルコントロールフローグラフＧＣＦＧｇｏｕｔは、グローバル変数ｇｏｕｔに関連する全てのＳＥＳＥ領域に含まれるノードだけを用いて構成されたコントロールフローグラフである。グローバルコントロールフローグラフＧＣＦＧｇｏｕｔでは、ノード１が関数Ｇのｉｆの条件式Ｒによる分岐であり、ノード１からノード２とノード３へエッジでそれぞれ繋がれ、ノード２がｇｏｕｔを定義する演算（ｇｏｕｔ＝ｙ＊ｔ）であり、ノード２からノード３へエッジで繋がれる。さらに、グローバルコントロールフローグラフＧＣＦＧｇｏｕｔでは、関数Ｇがコールされる関数Ｆ、その関数Ｆがコールされる関数Ａの関係も示している。図９（ｂ）には、そのグローバルコントロールフローグラフＧＣＦＧｇｏｕｔにおいてグローバル変数ｇｏｕｔの到達定義解析を実行した結果を示しており、各エッジにはグローバル変数ｇｏｕｔについての到達定義の集合が付加されている。ｅｎｔｒｙのノード１にはｅｘｉｔのノード３から前回値として到達定義集合｛ｇｏｕｔ２’｝が伝播され、ノード１からノード２とノード３に到達定義集合｛ｇｏｕｔ２’｝が到達し、ノード２からノード３に到達定義集合｛ｇｏｕｔ２｝が到達し、ノード３の到達定義集合が｛ｇｏｕｔ２，ｇｏｕｔ２’｝となる。
【００４１】
なお、プログラムＰには繰り返し実行されるｔａｓｋが含まれており、グローバル変数の場合、ｔａｓｋが繰り返し実行される毎に演算された変数がグローバル変数にストアされ、このグローバル変数にストアされた前回値が次回のｔａｓｋ実行時に各演算で用いられる。そこで、本実施の形態では、この前回値を到達定義解析において反映するために、グローバル変数についてのグローバルコントロールフローグラフにおいて到達定義解析を実行する場合、グローバルコントロールフローグラフのｅｘｉｔノードの到達定義集合をｅｎｔｒｙノードに伝播しており、その伝播された到達定義集合に含まれる各到達定義に前回値を意味するアポストロフィ「’」を付加している。
【００４２】
次に、データフローグラフ生成装置１では、上記のＳ１０の処理として、その到達定義解析結果に基づいて、図８に示す生成途中のデータフローグラフＤＦＧ１にカレント変数ｖ（＝ｇｏｕｔ）を定義している演算を追加する。図１０には、グローバル変数ｇｏｕｔを定義している演算を追加したデータフローグラフＤＦＧ２を示している。データフローグラフＤＦＧ２では、ｇｏｕｔを出力する場合には今回値と前回値の２つのケースが考えられるのでｇｏｕｔの今回値と前回値を選択するためのセレクタノードＳ１が付加され、入力ポートＩＰ１のグローバル変数ｙと入力ポートＩＰ２のローカル変数ｔが演算ノードＡ１３にそれぞれ伝播され、前回実行時に演算ノードＡ１３でグローバル変数ｙとローカル変数ｔを参照してｇｏｕｔ（前回値）が演算され、その前回演算されたｘ（前回値）がセレクタノードＳ１に伝播され、今回実行時に演算ノードＡ１３でグローバル変数ｙとローカル変数ｔを参照してｇｏｕｔ（今回値）が演算され、その今回演算されたｘ（今回値）がセレクタノードＳ１に伝播され、セレクタノードＳ１でその２つのｇｏｕｔから１つのｇｏｕｔが選択され（実際には、プログラムＰのｔａｓｋの前回実行時のステップ１３のｇｏｕｔ＝ｙ＊ｔで演算されたｇｏｕｔ値（前回値）又は今回実行時のステップ１３のｇｏｕｔ＝ｙ＊ｔで演算されたｇｏｕｔ値（今回値）がストアされたグローバル変数ｇｏｕｔの値である）、その選択されたｇｏｕｔが出力ポートＯＰに伝播される。
【００４３】
次に、データフローグラフ生成装置１では、上記のＳ１１の処理として、式（５）に示すように、カレント変数ｖ（＝ｇｏｕｔ）を定義している演算（ｇｏｕｔ＝ｙ＊ｔ）の右辺で参照されている変数｛ｙ，ｔ｝を未処理変数キューＶＱに追加する。そして、データフローグラフ生成装置１では、上記のＳ１３に示す処理として、未処理変数キューＶＱが空か否かを判定する。
【数３】
2012164024.tif 000005
【００４４】
未処理変数キューＶＱは空でないので、データフローグラフ生成装置１では、上記のＳ１４の処理として、式（６）に示すように、未処理変数キューＶＱの中に残っている変数｛ｙ，ｔ｝の中からローカル変数ｔを取り出し、カレント変数ｖとして更新する。取り出す変数は任意の変数でよいが、ここでは、ローカル変数のｔを取り出した。また、データフローグラフ生成装置１では、上記のＳ１４の処理として、式（７）に示すように、その更新されたカレント変数ｖ（＝ｔ）を参照している関数Ｇをカレント関数ｆとして更新する。これによって、未処理変数キューＶＱには、式（８）に示すように、グローバル変数ｙが残る。
【数４】
2012164024.tif 000006
【００４５】
上記のＳ５の処理に戻って、データフローグラフ生成装置１では、カレント変数ｖ（＝ｔ）がグローバル変数か否かを判定する。ここでは、カレント変数ｖはローカル変数のｔなので、グローバル変数でないと判定される。データフローグラフ生成装置１では、上記のＳ６の処理として、カレント関数ｆ（＝Ｇ）の到達定義解析が実行済みか否かを判定する。ここでは、カレント関数ｆ（＝Ｇ）の到達定義解析は実行していないと判定される。データフローグラフ生成装置１では、上記のＳ７の処理として、カレント関数ｆ（＝Ｇ）のコントロールフローグラフを生成し、そのコントロールフローグラフにおいてカレント変数ｖ（＝ｔ）についての到達定義解析を実行する。図１１には、カレント関数ＧのコントロールフローグラフＣＦＧＧを示している。コントロールフローグラフＣＦＧＧは、ノード１がｔを定義する演算（ｔ＝１００）であり、ノード２が関数Ｇのｉｆの条件式Ｒによる分岐であり、ノード２からノード３とノード４へエッジでそれぞれ繋がれ、ノード３がｇｏｕｔを定義する演算（ｇｏｕｔ＝ｙ＊ｔ）であり、ノード３からノード４へエッジで繋がれる。さらに、図１１には、そのコントロールフローグラフＣＦＧＧにおいてローカル変数ｔの到達定義解析を実行した結果を示しており、ノード１からノード２を経由してノード３に到達定義集合｛ｔ１｝が到達する。
【００４６】
そして、データフローグラフ生成装置１では、上記のＳ１０の処理として、その到達定義解析結果に基づいて、図１０に示す生成途中のデータフローグラフＤＦＧ２にカレント変数ｖ（＝ｔ）を定義している演算を追加する。図１２には、ローカル変数ｔを定義している演算を追加したデータフローグラフＤＦＧ３を示している。データフローグラフＤＦＧ３では、データフローグラフＤＦＧ２に対して、入力ポートＩＰ２の代わりに演算ノードＡ１１が追加され、今回実行時に演算ノードＡ１１で１００を参照してｔ（今回値）が演算され、その今回演算されたｔ（今回値）が演算ノードＡ１３に伝播される。
【００４７】
次に、データフローグラフ生成装置１では、上記のＳ１１の処理を行うが、カレント変数ｖ（＝ｔ）を定義している演算（ｔ＝１００）の右辺では変数を参照していないので、未処理変数キューＶＱには変数を追加しない。したがって、式（９）に示すように、未処理変数キューＶＱは変化しない。そして、データフローグラフ生成装置１では、上記のＳ１３に示す処理として、未処理変数キューＶＱが空か否かを判定する。
【数５】
2012164024.tif 000007
【００４８】
未処理変数キューＶＱは空でないので、データフローグラフ生成装置１では、上記のＳ１４の処理として、式（１０）に示すように、未処理変数キューＶＱの中に残っている変数｛ｙ｝の中からグローバル変数ｙを取り出し、カレント変数ｖとして更新する。また、データフローグラフ生成装置１では、上記のＳ１４の処理として、式（１１）に示すように、その更新されたカレント変数ｖ（＝ｙ）を参照している関数Ｇをカレント関数ｆとして更新する。これによって、未処理変数キューＶＱは、式（１２）に示すように、一旦、空となる。
【数６】
2012164024.tif 000008
【００４９】
上記のＳ５の処理に戻って、データフローグラフ生成装置１では、カレント変数ｖ（＝ｙ）がグローバル変数か否かを判定する。ここでは、カレント変数ｖはグローバル変数のｙなので、グローバル変数と判定される。データフローグラフ生成装置１では、上記のＳ８の処理として、カレント変数ｖ（＝ｙ）の定義がプログラムＰに含まれているか否かを判定する。ここでは、カレント変数ｖのｙは関数Ａ内の演算（ｙ＝ｘ＋ｔ）で定義されているので、プログラムＰに含まれていると判定される。データフローグラフ生成装置１では、上記のＳ９の処理として、カレント変数ｖ（＝ｙ）に関するグローバルコントロールフローグラフを生成し、そのグローバルコントロールフローグラフにおいてカレント変数ｖ（＝ｙ）についての到達定義解析を実行する。図１３には、グローバル変数ｙに関するグローバルコントロールフローグラフＧＣＦＧｙを示しており（図２２も参照）、グローバルコントロールフローグラフＧＣＦＧｙは、グローバル変数ｙに関連する全てのＳＥＳＥ領域に含まれるノードだけを用いて構成されたコントロールフローグラフである。グローバルコントロールフローグラフＧＣＦＧｙでは、ノード１がｙを定義する演算（ｙ＝ｘ＋ｔ）であり、ノード１からノード２にエッジで繋がれ、ノード２が関数Ｇのｉｆの条件式Ｒによる分岐であり、ノード２からノード３とノード４へエッジでそれぞれ繋がれ、ノード３がｇｏｕｔを定義する演算（ｇｏｕｔ＝ｙ＊ｔ）であり、ノード３からノード４へエッジで繋がれる。さらに、グローバルコントロールフローグラフＧＣＦＧｙでは、関数Ｇがコールされる関数Ｆ、その関数Ｆがコールされる関数Ａの関係も示している。さらに、そのグローバルコントロールフローグラフＧＣＦＧｙにおいてグローバル変数ｙの到達定義解析を実行した結果を示しており、各エッジにはグローバル変数ｙについての到達定義の集合が付加されている。ｅｎｔｒｙのノード１にはｅｘｉｔのノード４から前回値として到達定義集合｛ｙ１’｝が伝播され、ノード１からノード２に到達定義集合｛ｙ１｝が到達し、ノード２からノード３とノード４に到達定義集合｛ｙ１｝が到達し、ノード３からノード４に到達定義集合｛ｙ１｝が到達する。これによって、ｇｏｕｔを定義する演算（ｇｏｕｔ＝ｙ＊ｔ）で参照されるグローバル変数のｙは今回値ｙ１であることが判る。
【００５０】
そして、データフローグラフ生成装置１では、上記のＳ１０の処理として、その到達定義解析結果に基づいて、図１２に示す生成途中のデータフローグラフＤＦＧ３にカレント変数ｖ（＝ｙ）を定義している演算を追加する。図１４には、グローバル変数ｙを定義している演算を追加したデータフローグラフＤＦＧ４を示している。データフローグラフＤＦＧ４では、入力ポートＩＰ１の代わりに演算ノードＡ６が追加され、入力ポートＩＰ３のグローバル変数ｘと入力ポートＩＰ４のローカル変数ｔが演算ノードＡ６にそれぞれ伝播され、今回実行時に演算ノードＡ６でグローバル変数ｘとローカル変数ｔを参照してｙ（今回値）が演算され、その今回演算されたｙ（今回値）が演算ノードＡ１３に伝播される。
【００５１】
次に、データフローグラフ生成装置１では、上記のＳ１１の処理として、式（１３）に示すように、カレント変数ｖ（＝ｙ）を定義している演算（ｙ＝ｘ＋ｔ）の右辺で参照されている変数｛ｘ，ｔ｝を未処理変数キューＶＱに追加する。そして、データフローグラフ生成装置１では、上記のＳ１３に示す処理として、未処理変数キューＶＱが空か否かを判定する。
【数７】
2012164024.tif 000009
【００５２】
未処理変数キューＶＱは空でないので、データフローグラフ生成装置１では、上記のＳ１４の処理として、式（１４）に示すように、未処理変数キューＶＱの中に残っている変数｛ｘ，ｔ｝の中からローカル変数ｔを取り出し、カレント変数ｖとして更新する。また、データフローグラフ生成装置１では、上記のＳ１４の処理として、式（１５）に示すように、その更新されたカレント変数ｖ（＝ｔ）を参照している関数Ａをカレント関数ｆとして更新する。これによって、未処理変数キューＶＱには、式（１６）に示すように、グローバル変数ｘが残る。
【数８】
2012164024.tif 000010
【００５３】
上記のＳ５の処理に戻って、データフローグラフ生成装置１では、カレント変数ｖ（＝ｔ）がグローバル変数か否かを判定する。ここでは、カレント変数ｖはローカル変数のｔなので、グローバル変数でないと判定される。データフローグラフ生成装置１では、上記のＳ６の処理として、カレント関数ｆ（＝Ａ）の到達定義解析が実行済みか否かを判定する。ここでは、カレント関数ｆ（＝Ａ）の到達定義解析は実行していないと判定される。データフローグラフ生成装置１では、上記のＳ７の処理として、カレント関数ｆ（＝Ａ）のコントロールフローグラフを生成し、そのコントロールフローグラフにおいてカレント変数ｖ（＝ｔ）についての到達定義解析を実行する。
【００５４】
そして、データフローグラフ生成装置１では、上記のＳ１０の処理として、その到達定義解析結果に基づいて、図１４に示す生成途中のデータフローグラフＤＦＧ４にカレント変数ｖ（＝ｔ）を定義している演算を追加する。図１５には、ローカル変数ｔを定義している演算を追加したデータフローグラフＤＦＧ５を示している。データフローグラフＤＦＧ５では、データフローグラフＤＦＧ４に対して、入力ポートＩＰ４の代わりに演算ノードＡ５が追加され、今回実行時に演算ノードＡ５で１０を参照してｔ（今回値）が演算され、その今回演算されたｔ（今回値）が演算ノードＡ６に伝播される。
【００５５】
次に、データフローグラフ生成装置１では、上記のＳ１１の処理を行うが、カレント変数ｖ（＝ｔ）を定義している演算（ｔ＝１０）の右辺では変数を参照していないので、未処理変数キューＶＱには変数を追加しない。したがって、式（１７）に示すように、未処理変数キューＶＱは変化しない。そして、データフローグラフ生成装置１では、上記のＳ１３に示す処理として、未処理変数キューＶＱが空か否かを判定する。
【数９】
2012164024.tif 000011
【００５６】
未処理変数キューＶＱは空でないので、データフローグラフ生成装置１では、上記のＳ１４の処理として、式（１８）に示すように、未処理変数キューＶＱの中に残っている変数｛ｘ｝の中からグローバル変数ｘを取り出し、カレント変数ｖとして更新する。また、データフローグラフ生成装置１では、上記のＳ１４の処理として、式（１９）に示すように、その更新されたカレント変数ｖ（＝ｘ）を参照している関数Ａをカレント関数ｆとして更新する。これによって、未処理変数キューＶＱは、式（２０）に示すように、一旦、空となる。
【数１０】
2012164024.tif 000012
【００５７】
上記のＳ５の処理に戻って、データフローグラフ生成装置１では、カレント変数ｖ（＝ｘ）がグローバル変数か否かを判定する。ここでは、カレント変数ｖはグローバル変数のｘなので、グローバル変数と判定される。データフローグラフ生成装置１では、上記のＳ８の処理として、カレント変数ｖ（＝ｘ）の定義がプログラムＰに含まれているか否かを判定する。ここでは、カレント変数ｖのｘは関数Ａ内の演算（ｘ＝０）、関数Ｃ内の演算（ｘ＝ｘ＋１）、関数Ｅ内の演算（ｘ＝ｇｉｎ）で定義されているので、プログラムＰに含まれていると判定される。データフローグラフ生成装置１では、上記のＳ９の処理として、カレント変数ｖ（＝ｘ）に関するグローバルコントロールフローグラフを生成し、そのグローバルコントロールフローグラフにおいてカレント変数ｖ（＝ｘ）についての到達定義解析を実行する。図１６には、グローバル変数ｘに関するグローバルコントロールフローグラフＧＣＦＧｘを示しており（図２５も参照）、グローバルコントロールフローグラフＧＣＦＧｘは、グローバル変数ｘに関連する全てのＳＥＳＥ領域に含まれるノードだけを用いて構成されたコントロールフローグラフである。グローバルコントロールフローグラフＧＣＦＧｘでは、ノード１が関数Ｂのｉｆの条件式Ｐによる分岐であり、ノード１からノード２とノード３へエッジでそれぞれ繋がれ、ノード２がｘを定義する演算（ｘ＝ｘ＋１）であり、ノード２からノード３へエッジで繋がれ、ノード３からノード４へエッジで繋がれ、ノード４がｙを定義する演算（ｙ＝ｘ＋ｔ）であり、ノード４からノード５へエッジで繋がれ、ノード５が関数Ｂのｉｆの条件式Ｑによる分岐であり、ノード５からノード６とノード７へエッジでそれぞれ繋がれ、ノード６がｘを定義する演算（ｘ＝ｇｉｎ）であり、ノード６からノード８へエッジで繋がれ、ノード７がｘを定義する演算（ｘ＝０）であり、ノード７からノード８へエッジで繋がれる。さらに、グローバルコントロールフローグラフＧＣＦＧｘでは、関数Ｃがコールされる関数Ｂ、その関数Ｂがコールされる関数Ａの関係及び関数Ｅがコールされる関数Ｄ、その関数Ｄがコールされる関数Ａの関係を示している。さらに、そのグローバルコントロールフローグラフＧＣＦＧｘにおいてグローバル変数ｘの到達定義解析を実行した結果を示しており、各エッジにはグローバル変数ｘについての到達定義の集合が付加されている。ｅｎｔｒｙのノード１にはｅｘｉｔのノード８から前回値として到達定義集合｛ｘ６’，ｘ７’｝が伝播され、ノード１からノード２とノード３に到達定義集合｛ｘ６’，ｘ７’｝が到達し、ノード２からノード３に到達定義集合｛ｘ２，ｘ６’，ｘ７’｝が到達し、ノード３からノード４に到達定義集合｛ｘ２，ｘ６’，ｘ７’｝が到達する。これによって、ｙを定義する演算（ｙ＝ｘ＋ｔ）で参照されるグローバル変数のｘは今回値ｘ２、前回値ｘ６’、前回値ｘ７’のいずれかのｘ値であることが判る。
【００５８】
そして、データフローグラフ生成装置１では、上記のＳ１０の処理として、その到達定義解析結果に基づいて、図１５に示す生成途中のデータフローグラフＤＦＧ５にカレント変数ｖ（＝ｘ）を定義している演算を追加する。図１７には、グローバル変数ｘを定義している演算を追加したデータフローグラフＤＦＧ６を示している。データフローグラフＤＦＧ６では、入力ポートＩＰ３の代わりにセレクタノードＳ２、演算ノードＡ３、セレクタノードＳ３、演算ノードＡ８、演算ノードＡ９が追加され、入力ポートＩＰ５のグローバル変数ｇｉｎが演算ノードＡ８に伝播され、前回実行時に演算ノードＡ８でグローバル変数ｇｉｎを参照してｘ（前回値）が演算され、その前回演算されたｘ（前回値）がセレクタノードＳ２及びセレクタノードＳ３に伝播され、前回実行時に演算ノードＡ９で０を参照してｘ（前回値）が演算され、その前回演算されたｘ（前回値）がセレクタノードＳ２及びセレクタノードＳ３に伝播され、セレクタノードＳ３には演算ノードＡ８で前回演算されたｘ（前回値）と演算ノードＡ９で前回演算されたｘ（前回値）が伝播され、セレクタノードＳ３でその２つのｘから１つのｘが選択され（実際には、プログラムのｔａｓｋの前回実行時のステップ８のｘ＝ｇｉｎで演算されたｘ値（前回値）又は前回実行時のステップ９のｘ＝０で演算されたｘ値（前回値）がストアされたグローバル変数ｘの値である）、その選択されたｘが演算ノードＡ３に伝播され、今回実行時に演算ノードＡ３でそのセレクタノードＳ３からのｘと１を参照してｘ（今回値）が演算され、その演算されたｘ（今回値）がセレクタノードＳ２に伝播され、セレクタノードＳ２には演算ノードＡ８で前回演算されたｘ（前回値）と演算ノードＡ９で前回演算されたｘ（前回値）と演算ノードＡ３で今回演算されたｘ（今回値）が伝播され、セレクタノードＳ３でその３つのｘから１つのｘが選択され（実際には、プログラムのｔａｓｋの前回実行時のステップ８のｘ＝ｇｉｎで演算されたｘ値（前回値）又は前回実行時のステップ９のｘ＝０で演算されたｘ値（前回値）又は今回実行時のステップ３のｘ＝ｘ＋１で演算されたｘ値（今回値）がストアされたグローバル変数ｘの値である）、その選択されたｘが演算ノードＡ６に伝播される。
【００５９】
次に、データフローグラフ生成装置１では、上記のＳ１１の処理として、式（２１）に示すように、カレント変数ｖ（＝ｘ）を定義している演算（ｘ＝ｇｉｎ）の右辺で参照されている変数｛ｇｉｎ｝を未処理変数キューＶＱに追加する。そして、データフローグラフ生成装置１では、上記のＳ１３に示す処理として、未処理変数キューＶＱが空か否かを判定する。
【数１１】
2012164024.tif 000013
【００６０】
未処理変数キューＶＱは空でないので、データフローグラフ生成装置１では、上記のＳ１４の処理として、式（２２）に示すように、未処理変数キューＶＱの中に残っている変数｛ｇｉｎ｝の中からグローバル変数ｇｉｎを取り出し、カレント変数ｖとして更新する。また、データフローグラフ生成装置１では、上記のＳ１４の処理として、式（２３）に示すように、カレント関数ｆを更新が、グローバル変数ｇｉｎの定義はプログラムＰ外なので、カレント関数ｆは無しとする。これによって、未処理変数キューＶＱには、式（２４）に示すように、空となる。
【数１２】
2012164024.tif 000014
【００６１】
上記のＳ５の処理に戻って、データフローグラフ生成装置１では、カレント変数ｖ（＝ｇｉｎ）がグローバル変数か否かを判定する。ここでは、カレント変数ｖはグローバル変数のｇｉｎなので、グローバル変数と判定される。データフローグラフ生成装置１では、上記のＳ８の処理として、カレント変数ｖ（＝ｇｉｎ）の定義がプログラムＰに含まれているか否かを判定する。ここでは、カレント変数ｖのｇｉｎの定義はプログラムＰに含まれていないので、プログラムＰに含まれていないと判定される。データフローグラフ生成装置１では、上記のＳ１２の処理として、図１７に示す生成途中のデータフローグラフＤＦＧ６にカレント変数ｖ（＝ｇｉｎ）の入力ポートを付加する。図１７には、グローバル変数ｘを定義している演算を追加したデータフローグラフＤＦＧ６を示している。データフローグラフＤＦＧ７では、入力ポートＩＰ５が追加されたデータフローグラフが構成される。
【００６２】
データフローグラフ生成装置１では、上記のＳ１３の処理として、未処理変数キューＶＱが空か否かを判定する。式（２５）に示すように未処理変数キューＶＱは空なので、出力変数Ｖｏｕｔ（＝ｇｏｕｔ）に関係する全ての変数についての処理が終了したことになり、データフローグラフ生成装置１では、処理を終了する。この時点で生成されているデータフローグラフＤＦＧ７が、最終的な出力変数Ｖｏｕｔ（＝ｇｏｕｔ）を出力とするデータフローグラフＤＦＧである。
【数１３】
2012164024.tif 000015
【００６３】
次に、図１９〜図２５を参照して、データフローグラフ生成装置１におけるグローバルコントロールフローグラフの具体的な生成過程を説明する。ここでは、カレント変数ｖとしてグローバル変数ｙが設定されている場合とグローバル変数ｘが設定されている場合についての生成過程を説明する。
【００６４】
まず、カレント変数ｖとしてグローバル変数ｙが設定されている場合について説明する。上記のＳ２０の処理として、データフローグラフ生成装置１では、式（２６）に示すように、変数定義関数テーブルからカレント変数ｖ（＝ｙ）を定義している関数集合Ωｄｅｆを抽出する。また、データフローグラフ生成装置１では、式（２７）に示すように、カレント変数ｖ（＝ｙ）を参照している関数集合Ωｒｅｆを抽出する。そして、データフローグラフ生成装置１では、式（２８）に示すように、関数集合Ωｄｅｆに含まれる関数Ａについて、コールグラフから関数Ａとその上位の関数の集合↑Ａを抽出する。また、データフローグラフ生成装置１では、式（２９）に示すように、関数集合Ωｒｅｆに含まれる関数Ｇについて、コールグラフから関数Ｇとその上位の関数の集合↑Ｇを抽出する。そして、データフローグラフ生成装置１では、式（３０）に示すように、関数集合↑Ａと関数集合↑Ｇの和集合を求め、カレント変数ｖ（＝ｙ）に関連する関数集合Πを抽出する。図１９には、コールグラフ上に、関数集合Ωｄｅｆ、関数集合Ωｒｅｆ、関数集合↑Ａ、関数集合↑Ｇを示している。
【数１４】
2012164024.tif 000016
【００６５】
次に、データフローグラフ生成装置１では、上記のＳ２１の処理として、カレント変数ｖ（＝ｙ）に関連する関数集合Πに含まれる各関数ｔａｓｋ，Ａ，Ｆ，Ｇについてのコントロールフローグラフを生成し、その各関数ｔａｓｋ，Ａ，Ｆ，ＧのコントロールフローグラフからＳＥＳＥ領域を算出する。図２０（ａ）には、関数ｔａｓｋのコントロールフローグラフを示しており、そのコントロールフローグラフから求められたＳＥＳＥ領域Ｔｔａｓｋ１，Ｔｔａｓｋ２，Ｔｔａｓｋ３，Ｔｔａｓｋ４を示している。また、図２０（ｂ）には、関数Ａのコントロールフローグラフを示しており、そのコントロールフローグラフから求められたＳＥＳＥ領域ＴＡ１，ＴＡ２，ＴＡ３，ＴＡ４，ＴＡ５，ＴＡ６，ＴＡ７，ＴＡ８，ＴＡ９，ＴＡ１０を示している。図２０（ｃ）には、関数Ｆのコントロールフローグラフを示しており、そのコントロールフローグラフから求められたＳＥＳＥ領域ＴＦ１，ＴＦ２を示している。図２０（ｄ）には、関数Ｇのコントロールフローグラフを示しており、そのコントロールフローグラフから求められたＳＥＳＥ領域ＴＧ１，ＴＧ２，ＴＧ３を示している。
【００６６】
次に、データフローグラフ生成装置１では、上記のＳ２２の処理として、カレント変数ｖ（＝ｙ）に関連する関数集合Πに含まれる各関数ｔａｓｋ，Ａ，Ｆ，ＧについてのＳＥＳＥ領域の中から、関数集合Πに含まれる各関数をコールしているＳＥＳＥ領域を選択し、カレント変数ｖ（＝ｙ）を定義しているＳＥＳＥ領域を選択し、カレント変数ｖ（＝ｙ）を参照しているＳＥＳＥ領域を選択し、その選択されたＳＥＳＥ領域を包含するＳＥＳＥ領域を選択する。図２１に示すように、各関数をコールしているＳＥＳＥ領域としてはＳＥＳＥ領域Ｔｔａｓｋ１とＳＥＳＥ領域ＴＡ１０とＳＥＳＥ領域ＴＦ１が選択され、カレント変数ｖ（＝ｙ）を定義しているＳＥＳＥ領域としてはＳＥＳＥ領域ＴＡ５が選択され、カレント変数ｖ（＝ｙ）を参照しているＳＥＳＥ領域としてはＳＥＳＥ領域ＴＧ３が選択され、その選択されたＳＥＳＥ領域を包含するＳＥＳＥ領域としてＳＥＳＥ領域ＴＧ２を選択される。
【００６７】
そして、データフローグラフ生成装置１では、上記のＳ２３の処理として、選択された６個のＳＥＳＥ領域Ｔｔａｓｋ１，ＴＡ１０，ＴＦ１，ＴＡ５，ＴＧ３，ＴＧ２に含まれるノードだけを用いてコントロールフローグラフを構成する。図２２には、その生成されたグローバルコントロールフローグラフＧＣＦＧｙを示しており、ノード１がカレント変数ｖ（＝ｙ）を定義しているＳＥＳＥ領域ＴＡ５のノードで構成され、ノード３がカレント変数ｖ（＝ｙ）を参照しているＳＥＳＥ領域ＴＧ３のノードで構成され、ノード２，３，４の関係が選択されたＳＥＳＥ領域を包含するＳＥＳＥ領域ＴＧ２のノードで構成され、関数Ａ、Ｆ，Ｇの関係が各関数をコールしているＳＥＳＥ領域Ｔｔａｓｋ１，ＴＡ１０，ＴＦ１のノードで構成される。
【００６８】
次に、カレント変数ｖとしてグローバル変数ｘが設定されている場合について説明する。上記のＳ２０の処理として、データフローグラフ生成装置１では、式（３１）に示すように、変数定義関数テーブルからカレント変数ｖ（＝ｘ）を定義している関数集合Ωｄｅｆを抽出する。また、データフローグラフ生成装置１では、式（３２）に示すように、カレント変数ｖ（＝ｘ）を参照している関数集合Ωｒｅｆを抽出する。そして、データフローグラフ生成装置１では、式（３３）に示すように、関数集合Ωｄｅｆ及び関数集合Ωｒｅｆに含まれる関数Ａについて、コールグラフから関数Ａとその上位の関数の集合↑Ａを抽出する。また、データフローグラフ生成装置１では、式（３４）に示すように、関数集合Ωｄｅｆ及び関数集合Ωｒｅｆに含まれる関数Ｃについて、コールグラフから関数Ｃとその上位の関数の集合↑Ｃを抽出する。また、データフローグラフ生成装置１では、式（３５）に示すように、関数集合Ωｄｅｆに含まれる関数Ｅについて、コールグラフから関数Ｅとその上位の関数の集合↑Ｅを抽出する。そして、データフローグラフ生成装置１では、式（３６）に示すように、関数集合↑Ａと関数集合↑Ｃと関数集合↑Ｅの和集合を求め、カレント変数ｖ（＝ｙ）に関連する関数集合Πを抽出する。
【数１５】
2012164024.tif 000017
【００６９】
次に、データフローグラフ生成装置１では、上記のＳ２１の処理として、カレント変数ｖ（＝ｘ）に関連する関数集合Πに含まれる各関数ｔａｓｋ，Ａ，Ｂ，Ｃ，Ｄ，Ｅについてのコントロールフローグラフを生成し、その各関数ｔａｓｋ，Ａ，Ｂ，Ｃ，Ｄ，ＥのコントロールフローグラフにおいてＳＥＳＥ領域を算出する。図２３（ａ）には、図２０（ａ）と同様の関数ｔａｓｋのコントロールフローグラフ及びＳＥＳＥ領域を示している。た、図２３（ｂ）には、図２０（ｂ）と同様の関数Ａのコントロールフローグラフ及びＳＥＳＥ領域を示している。図２３（ｃ）には、関数Ｂのコントロールフローグラフを示しており、そのコントロールフローグラフから求められたＳＥＳＥ領域ＴＢ１，ＴＢ２を示している。図２３（ｄ）には、関数Ｃのコントロールフローグラフを示しており、そのコントロールフローグラフから求められたＳＥＳＥ領域ＴＣ１を示している。図２３（ｅ）には、関数Ｄのコントロールフローグラフを示しており、そのコントロールフローグラフから求められたＳＥＳＥ領域ＴＤ１，ＴＤ２を示している。図２３（ｆ）には、関数Ｅのコントロールフローグラフを示しており、そのコントロールフローグラフから求められたＳＥＳＥ領域ＴＥ１を示している。
【００７０】
次に、データフローグラフ生成装置１では、上記のＳ２２の処理として、カレント変数ｖ（＝ｘ）に関連する関数集合Πに含まれる各関数ｔａｓｋ，Ａ，Ｂ，Ｃ，Ｄ，ＥについてのＳＥＳＥ領域の中から、関数集合Πに含まれる各関数をコールしているＳＥＳＥ領域を選択し、カレント変数ｖ（＝ｘ）を定義しているＳＥＳＥ領域を選択し、カレント変数ｖ（＝ｘ）を参照しているＳＥＳＥ領域を選択し、その選択されたＳＥＳＥ領域を包含するＳＥＳＥ領域を選択する。図２４に示すように、各関数をコールしているＳＥＳＥ領域としてはＳＥＳＥ領域Ｔｔａｓｋ１とＳＥＳＥ領域ＴＡ２とＳＥＳＥ領域ＴＡ７とＳＥＳＥ領域ＴＢ２とＳＥＳＥ領域ＴＤ１が選択され、カレント変数ｖ（＝ｘ）を定義しているＳＥＳＥ領域としてはＳＥＳＥ領域ＴＡ８とＳＥＳＥ領域ＴＣ１とＳＥＳＥ領域ＴＥ１が選択され、カレント変数ｖ（＝ｘ）を参照しているＳＥＳＥ領域としてはＳＥＳＥ領域ＴＡ５とＳＥＳＥ領域ＴＣ１が選択され、その選択されたＳＥＳＥ領域を包含するＳＥＳＥ領域としてはＳＥＳＥ領域ＴＡ６とＳＥＳＥ領域ＴＢ１が選択される。
【００７１】
そして、データフローグラフ生成装置１では、上記のＳ２３の処理として、選択された１１個のＳＥＳＥ領域Ｔｔａｓｋ１，ＴＡ２，ＴＡ７，ＴＢ２，ＴＤ１，ＴＡ８，ＴＣ１，ＴＥ１，ＴＡ５，ＴＡ６，ＴＢ１に含まれるノードだけを用いてコントロールフローグラフを構成する。図２５には、その生成されたグローバルコントロールフローグラフＧＣＦＧｘを示しており、ノード２がカレント変数ｖ（＝ｘ）を定義しているＳＥＳＥ領域ＴＣ１のノードで構成され、ノード１，２，３の関係が選択されたＳＥＳＥ領域を包含するＳＥＳＥ領域ＴＢ１のノードで構成され、ノード４がカレント変数ｖ（＝ｘ）を参照しているＳＥＳＥ領域ＴＡ５のノードで構成され、ノード６がカレント変数ｖ（＝ｘ）を定義しているＳＥＳＥ領域ＴＥ１のノードで構成され、ノード７がカレント変数ｖ（＝ｘ）を定義しているＳＥＳＥ領域ＴＡ８のノードで構成され、ノード５，６，７，８の関係が選択されたＳＥＳＥ領域を包含するＳＥＳＥ領域ＴＡ６のノードで構成され、関数Ａ、Ｂ，Ｃ，Ｄ，Ｅの関係が各関数をコールしているＳＥＳＥ領域Ｔｔａｓｋ１，ＴＡ２，ＴＡ７，ＴＢ２，ＴＤ１のノードで構成される。
【００７２】
このデータフローグラフ生成装置１によれば、テータフローグラフの出力変数Ｖｏｕｔに関係する変数毎にコントロールフローグラフを生成して到達定義解析を行い、その到達定義解析結果を統合してデータフローグラフを生成することにより、テータフローグラフの出力変数Ｖｏｕｔに関係する変数やその各変数に関連する関数のみを考慮してデータフローグラフを生成できるので、データフローグラフを効率的に生成できる。到達定義解析において出力変数Ｖｏｕｔに関係する変数以外の変数の到達定義の計算及び伝播を行わないので、計算コスト（メモリ、計算時間等）を抑制できる。特に、プログラムが大規模になっても、出力変数に関係する各変数についてのコントロールフローグラフだけを生成し、その各コントロールフローグラフにおいてその各変数についての到達定義解析だけを行うので、コントロールフローグラフが大規模にならず、到達定義解析の計算コストも抑制でき、非常に効率的にデータフローグラフを生成できる。
【００７３】
また、データフローグラフ生成装置１によれば、出力変数Ｖｏｕｔに関係する各グローバル変数についてのグローバルコントロールグローグラフを生成する際に、そのグローバル変数に関連する関数のみを抽出し、その抽出された各関数のＳＥＳＥ領域を算出し、そのＳＥＳＥ領域の中からそのグローバル変数に関係するＳＥＳＥ領域だけを選択してグローバルコントロールグローグラフを生成することにより、効率的にグローバルコントロールグローグラフを生成できる。
【００７４】
以上、本発明に係る実施の形態について説明したが、本発明は上記実施の形態に限定されることなく様々な形態で実施される。
【００７５】
例えば、本実施の形態ではデータフローグラフを生成するデータフローグラフ生成装置に適用したが、ＣＤ−ＲＯＭ等の記憶媒体に格納されたプログラムやインタネット等のネットワークを介して利用可能なプログラム等に適用し、このようなプログラムをコンピュータ上で実行することによってデータフローグラフを生成する構成としてもよい。
【００７６】
また、本実施の形態では解析対象のプログラム（ソースコード）に含まれる全ての関数を解析して変数定義関数テーブルと関数コールグラフを生成したが、解析対象に含まれる一部の関数（少なくとも出力変数に関係する各変数に関連する関数を含む）だけを解析して変数定義関数テーブルと関数コールグラフを生成してもよい。
【００７７】
また、本実施の形態ではグローバル変数のグローバルコントロールフローグラフを生成する際に、ＳＥＳＥ領域を用いて生成する手法を適用したが、他の手法によりグローバル変数のグローバルコントロールフローグラフを生成してもよい。
【符号の説明】
【００７８】
１…データフローグラフ生成装置。
【図１】
2012164024.tif 000018
【図２】
2012164024.tif 000019
【図３】
2012164024.tif 000020
【図４】
2012164024.tif 000021
【図５】
2012164024.tif 000022
【図６】
2012164024.tif 000023
【図７】
2012164024.tif 000024
【図８】
2012164024.tif 000025
【図９】
2012164024.tif 000026
【図１０】
2012164024.tif 000027
【図１１】
2012164024.tif 000028
【図１２】
2012164024.tif 000029
【図１３】
2012164024.tif 000030
【図１４】
2012164024.tif 000031
【図１５】
2012164024.tif 000032
【図１６】
2012164024.tif 000033
【図１７】
2012164024.tif 000034
【図１８】
2012164024.tif 000035
【図１９】
2012164024.tif 000036
【図２０】
2012164024.tif 000037
【図２１】
2012164024.tif 000038
【図２２】
2012164024.tif 000039
【図２３】
2012164024.tif 000040
【図２４】
2012164024.tif 000041
【図２５】
2012164024.tif 000042