(57)【要約】【課題】繰り返し実行されるタスクを含むプログラムでも高精度なデータフローグラフを生成できるデータフローグラフ生成装置、データフローグラフ生成方法及びデータフローグラフ生成プログラムを提供することを課題とする。【解決手段】手続き型言語によって記述され、繰り返し実行されるタスクを含むプログラムの到達定義に基づくデータフローグラフの生成において、プログラムからコントロールフローグラフを生成し（Ｓ２）、コントロールフローグラフにおいて終了ノードから開始ノードまでのエッジを仮定し（Ｓ３）、エッジが仮定されたコントロールフローグラフの到達定義を算出するとともに到達定義を算出する際に仮定されたエッジに従って到達定義を伝播させかつその伝播させた到達定義を前回値の到達定義として区別し（Ｓ４）、算出された到達定義に基づいてデータフローグラフを生成する（Ｓ５）。【選択図】図２
2012155605.tif 000002
【特許請求の範囲】
【請求項１】
手続き型言語によって記述され、繰り返し実行されるタスクを含むプログラムの到達定義に基づくデータフローグラフを生成するデータフローグラフ生成装置であって、
前記プログラムからコントロールフローグラフを生成するコントロールフローグラフ生成手段と、
前記コントロールフローグラフ生成手段で生成されたコントロールフローグラフにおいて終了ノードから開始ノードまでのエッジを仮定するエッジ仮定手段と、
前記エッジ仮定手段でエッジが仮定されたコントロールフローグラフの到達定義を算出するとともに、該到達定義を算出する際に前記エッジ仮定手段で仮定されたエッジに従って到達定義を伝播させ、該伝播させた到達定義を前回値の到達定義として区別する到達定義算出手段と、
前記到達定義算出手段で算出された到達定義に基づいてデータフローグラフを生成するデータフローグラフ生成手段と、
を備えることを特徴とするデータフローグラフ生成装置。
【請求項２】
手続き型言語によって記述され、繰り返し実行されるタスクを含むプログラムの到達定義に基づくデータフローグラフを生成するデータフローグラフ生成方法であって、
前記プログラムからコントロールフローグラフを生成するコントロールフローグラフ生成ステップと、
前記コントロールフローグラフ生成ステップで生成されたコントロールフローグラフにおいて終了ノードから開始ノードまでのエッジを仮定するエッジ仮定ステップと、
前記エッジ仮定ステップでエッジが仮定されたコントロールフローグラフの到達定義を算出するとともに、該到達定義を算出する際に前記エッジ仮定ステップで仮定されたエッジに従って到達定義を伝播させ、該伝播させた到達定義を前回値の到達定義として区別する到達定義算出ステップと、
前記到達定義算出ステップで算出された到達定義に基づいてデータフローグラフを生成するデータフローグラフ生成ステップと、
を含むことを特徴とするデータフローグラフ生成方法。
【請求項３】
手続き型言語によって記述され、繰り返し実行されるタスクを含むプログラムの到達定義に基づくデータフローグラフを生成するためのデータフローグラフ生成プログラムであって、
コンピュータに、
前記プログラムからコントロールフローグラフを生成するコントロールフローグラフ生成機能と、
前記コントロールフローグラフ生成機能で生成されたコントロールフローグラフにおいて終了ノードから開始ノードまでのエッジを仮定するエッジ仮定機能と、
前記エッジ仮定機能でエッジが仮定されたコントロールフローグラフの到達定義を算出するとともに、該到達定義を算出する際に前記エッジ仮定機能で仮定されたエッジに従って到達定義を伝播させ、該伝播させた到達定義を前回値の到達定義として区別する到達定義算出機能と、
前記到達定義算出機能で算出された到達定義に基づいてデータフローグラフを生成するデータフローグラフ生成機能と、
を実現させることを特徴とするデータフローグラフ生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、手続き型言語によって記述され、繰り返し実行されるタスクを含むプログラムの到達定義に基づくデータフローグラフを生成するデータフローグラフ生成装置、データフローグラフ生成方法及びデータフローグラフ生成プログラムに関する。
【背景技術】
【０００２】
手続き型言語（例えば、Ｃ言語）で記述されたプログラムは、人間にとってはデータの依存関係や計算過程等を理解するのが難しい。そこで、このようなプログラムを人間が直感的に理解できるようにするために、プログラムの演算をノード、変数をエッジで表現したグラフとしてモデリングしたデータフローグラフ[Data flow graph]を生成し、データフローグラフを用いてプログラムの解析を行っている。データフローグラフを生成する方法としては、解析対象のプログラムからコントロールフローグラフ[Controlflow graph]を生成し、コントロールフローグラフに対して出力変数に関係する変数に関して到達定義解析を行い、到達定義解析で得られる情報から出力変数を出力とするデータフローグラフを生成する。また、特許文献１には、プログラムの処理アルゴリズムを表現するデータフローグラフの作成方式において、そのプログラムを実際に実行することにより、実行した命令の情報を外部記憶にトレースデータとして格納し、その格納したトレースデータに対して演算を施すことによりデータフローグラフを作成することが開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開昭６３−２１４８３８号公報
【特許文献２】特開２００３−５０７２２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
時間やイベントに同期してタスク（関数）を繰り返し実行するプログラムの場合、変数としてグローバル変数を参照する演算では、グローバル変数に前回実行時に演算された前回値がストアされているときには前回値に依存して演算を行う。しかし、従来の生成方法によるデータフローグラフには、グローバル変数にストアされた前回値に依存する演算が正確に反映されていない。
【０００５】
そこで、本発明は、繰り返し実行されるタスクを含むプログラムでも高精度なデータフローグラフを生成できるデータフローグラフ生成装置、データフローグラフ生成方法及びデータフローグラフ生成プログラムを提供することを課題とする。
【課題を解決するための手段】
【０００６】
本発明に係るデータフローグラフ生成装置は、手続き型言語によって記述され、繰り返し実行されるタスクを含むプログラムの到達定義に基づくデータフローグラフを生成するデータフローグラフ生成装置であって、プログラムからコントロールフローグラフを生成するコントロールフローグラフ生成手段と、コントロールフローグラフ生成手段で生成されたコントロールフローグラフにおいて終了ノードから開始ノードまでのエッジを仮定するエッジ仮定手段と、エッジ仮定手段でエッジが仮定されたコントロールフローグラフの到達定義を算出するとともに、該到達定義を算出する際にエッジ仮定手段で仮定されたエッジに従って到達定義を伝播させ、該伝播させた到達定義を前回値の到達定義として区別する到達定義算出手段と、到達定義算出手段で算出された到達定義に基づいてデータフローグラフを生成するデータフローグラフ生成手段とを備えることを特徴とする。
【０００７】
このデータフローグラフ生成装置では、コントロールフローグラフ生成手段によって、繰り返し実行されるタスクを含むプログラムのコントロールフローグラフを生成する。データフローグラフ生成装置では、エッジ仮定手段によって、コントロールフローグラフにおいて終了ノードから開始ノードまでのエッジを仮定する。そして、データフローグラフ生成装置では、到達定義計算手段によって、そのエッジが仮定されたコントロールフローグラフの到達定義を算出する。特に、到達定義を算出する際に、仮定されたエッジに従って終了ノードの到達定義を開始ノードに伝播させるとともにその伝播させた到達定義を前回値の到達定義として区別し、前回値の到達定義も反映させる。そして、データフローグラフ生成装置では、データフローグラフ生成手段によって、算出された到達定義に基づいてデータフローグラフを生成する。このように、データフローグラフ生成装置では、繰り返し実行されるタスクを含むプログラムでも、到達定義計算時に終了ノードの到達定義を開始ノードに前回値として伝播させることにより、前回値に依存する演算も正確に反映することができ、高精度なデータフローグラフを生成できる。
【０００８】
本発明に係るデータフローグラフ生成方法は、手続き型言語によって記述され、繰り返し実行されるタスクを含むプログラムの到達定義に基づくデータフローグラフを生成するデータフローグラフ生成方法であって、プログラムからコントロールフローグラフを生成するコントロールフローグラフ生成ステップと、コントロールフローグラフ生成ステップで生成されたコントロールフローグラフにおいて終了ノードから開始ノードまでのエッジを仮定するエッジ仮定ステップと、エッジ仮定ステップでエッジが仮定されたコントロールフローグラフの到達定義を算出するとともに、該到達定義を算出する際にエッジ仮定ステップで仮定されたエッジに従って到達定義を伝播させ、該伝播させた到達定義を前回値の到達定義として区別する到達定義算出ステップと、到達定義算出ステップで算出された到達定義に基づいてデータフローグラフを生成するデータフローグラフ生成ステップとを含むことを特徴とする。このデータフローグラフ生成方法によれば、各ステップの処理を行うことにより、上記データフローグラフ生成装置の作用及び効果を奏する。
【０００９】
本発明に係るデータフローグラフ生成プログラムは、手続き型言語によって記述され、繰り返し実行されるタスクを含むプログラムの到達定義に基づくデータフローグラフを生成するためのデータフローグラフ生成プログラムであって、コンピュータに、プログラムからコントロールフローグラフを生成するコントロールフローグラフ生成機能と、コントロールフローグラフ生成機能で生成されたコントロールフローグラフにおいて終了ノードから開始ノードまでのエッジを仮定するエッジ仮定機能と、エッジ仮定機能でエッジが仮定されたコントロールフローグラフの到達定義を算出するとともに、該到達定義を算出する際にエッジ仮定機能で仮定されたエッジに従って到達定義を伝播させ、該伝播させた到達定義を前回値の到達定義として区別する到達定義算出機能と、到達定義算出機能で算出された到達定義に基づいてデータフローグラフを生成するデータフローグラフ生成機能とを実現させることを特徴とする。このデータフローグラフ生成プログラムによれば、このプログラムをコンピュータに実行させることによって、上記データフローグラフ生成装置の作用及び効果を奏する。
【発明の効果】
【００１０】
本発明によれば、繰り返し実行されるタスクを含むプログラムでも、到達定義計算時に終了ノードの到達定義を開始ノードに前回値として伝播させることにより、前回値に依存する演算も正確に反映することができ、高精度なデータフローグラフを生成できる。
【図面の簡単な説明】
【００１１】
【図１】本実施の形態に係るデータフローグラフ生成装置の構成図である。
【図２】本実施の形態に係るデータフローグラフ生成装置での処理の流れを示すフローチャートである。
【図３】手続き型言語で記述されたプログラムの一例である。
【図４】従来のデータフローグラフの生成過程の一例であり、（ａ）がコントロールフローグラフ生成過程であり、（ｂ）が到達定義算出過程であり、（ｃ）が到達定義追跡過程であり、（ｄ）がデータフローグラフ生成過程である。
【図５】本実施の形態に係るデータフローグラフ生成装置でのデータフローグラフの生成過程の一例であり、（ａ）がエッジ付加過程であり、（ｂ）が付加エッジ伝播前の到達定義算出過程であり、（ｃ）が付加エッジ伝播過程である。
【図６】本実施の形態に係るデータフローグラフ生成装置でのデータフローグラフの生成過程の一例であり、（ａ）が付加エッジ伝播後の到達定義算出過程であり、（ｂ）が到達定義追跡過程であり、（ｃ）がデータフローグラフ生成過程である。
【発明を実施するための形態】
【００１２】
以下、図面を参照して、本発明に係るデータフローグラフ生成装置、データフローグラフ生成方法及びデータフローグラフ生成プログラムの実施の形態を説明する。なお、各図において同一又は相当する要素については同一の符号を付し、重複する説明を省略する。
【００１３】
本実施の形態では、本発明を、データフローグラフ生成装置に適用する。本実施の形態に係るデータフローグラフ生成装置は、解析対象のプログラム（ソースコード）とデータフローグラフの出力変数が決定されて入力されると、プログラムからコントロールフローグラフを生成し、コントロールフローグラフに対する到達定義解析で得られる情報からデータフローグラフを生成し、出力変数を出力とするデータフローグラフを生成する。本実施の形態に係るデータフローグラフ生成装置は、データフローグラフの生成だけを行う専用装置でもよいし、あるいは、汎用コンピュータでデータフローグラフ生成用のアプリケーションを実行することによって構成されてもよい。
【００１４】
なお、プログラムは、手続き型言語で記述されたプログラムである。特に、本実施の形態に係るデータフローグラフ生成装置は、時間やイベントに同期して繰り返し実行するタスク（関数）を含むプログラムが入力された場合でも、精度の高いデータフローグラフを生成できる。プログラムとしては、プログラムの中の一部のタスクだけが繰り返し実行されるものでもよいし、プログラム（タスク）全体が繰り返し実行されるものでもよい。繰り返し実行されるタスクは変数として少なくともグローバル変数を用いており、タスクが繰り返し実行される毎に演算された変数がグローバル変数にストアされる。そして、このグローバル変数にストアされた前回値が、次にタスクが実行されるときに各演算で用いられる。
【００１５】
図３には、手続き型言語で記述されたプログラムの一例を示しており、ｔａｓｋ（）が繰り返し実行され、ｘ，ｙ，ｚがグローバル変数である。図３に示すｔａｓｋ（）では、ステップ４の演算（ｘ＝ｘ＋１）とステップ６の演算（ｙ＝ｘ）でグローバル変数ｘにストアされた前回値が用いられる場合がある。なお、図３に示すプログラムではグローバル変数に関連する演算のみを具体的に示しており、ステップ１，３，９，１２における「・・・」は任意の演算である。
【００１６】
本実施の形態に係るデータフローグラフ生成装置を具体的に説明する前に、図３のプログラムを例として、図４を参照して、従来のデータフローグラフの生成方法を説明しておく。ここでは、出力変数をｇｏｕｔとしたデータフローグラフを生成する。図４は、従来のデータフローグラフの生成過程の一例であり、（ａ）がコントロールフローグラフ生成過程であり、（ｂ）が到達定義算出過程であり、（ｃ）が到達定義追跡過程であり、（ｄ）がデータフローグラフ生成過程である。
【００１７】
まず、プログラムの構文を解析する。図３に示すプログラムの構文を解析すると、ステップ１で任意の演算を実行し、ステップ２でｉｆの条件式Ｐの判定を行い、条件式Ｐが「Ｔｒｕｅ」の場合にはステップ３で任意の演算を実行し、条件式Ｐが「Ｆａｌｓｅ」の場合にはステップ４でｘ＝ｘ＋１を実行し、ステップ６でｙ＝ｘを実行し、ステップ７でｉｆの条件式Ｑの判定を行い、条件式Ｑが「Ｔｒｕｅ」の場合にはステップ８でｘ＝ｇｉｎを実行し、条件式Ｑが「Ｆａｌｓｅ」の場合にはステップ９で任意の演算を実行し、ステップ１１でｚ＝ｙを実行し、ステップ１２で任意の演算を実行し、ステップ１３でｇｏｕｔ＝ｚを実行し、この処理過程が繰り返し実行される。
【００１８】
次に、プログラムの構文解析結果に基づいて、プログラムのコントロールフローグラフを生成する。コントロールフローグラフは、プログラムを実行したときに通る可能性のある全経路がグラフで表され、ノード及びノードとノードとを繋ぐエッジで構成される。図４（ａ）に示すように、図３に示すプログラムから生成されたコントロールフローグラフＣＦＧは、ノードＮ１がステップ１の任意の演算であり、ノードＮ１からノードＮ２へエッジＥ１２で繋がれ、ノードＮ２がステップ２のｉｆの条件式Ｐによる分岐であり、ノードＮ２からノードＮ３とノードＮ４へエッジＥ２３，Ｅ２４でそれぞれ繋がれ、ノードＮ３がステップ３の任意の演算であり、ノードＮ３からノードＮ５へエッジＥ３５で繋がれ、ノードＮ４がステップ４のｘ＝ｘ＋１の演算であり、ノードＮ４からノードＮ５へエッジＥ４５で繋がれ、ノードＮ５からノードＮ６へエッジＥ５６で繋がれ、ノードＮ６がステップ６のｙ＝ｘの演算であり、ノードＮ６からノードＮ７へエッジＥ６７で繋がれ、ノードＮ７がステップ７のｉｆの条件式Ｑによる分岐であり、ノードＮ７からノードＮ８とノードＮ９へエッジＥ７８，Ｅ７９でそれぞれ繋がれ、ノードＮ８がステップ８のｘ＝ｇｉｎの演算であり、ノードＮ８からノードＮ１０へエッジＥ８１０で繋がれ、ノードＮ９がステップ９の任意の演算であり、ノードＮ９からノードＮ１０へエッジＥ９１０で繋がれ、ノードＮ１０からノードＮ１１へエッジＥ１０１１で繋がれ、ノードＮ１１がステップ１１のｚ＝ｙの演算であり、ノードＮ１１からノードＮ１２へエッジＥ１１１２で繋がれ、ノードＮ１２がステップ１２の任意の演算であり、ノードＮ１２からノードＮ１３へエッジＥ１２１３で繋がれ、ノードＮ１３がステップ１３のｇｏｕｔ＝ｚの演算である。
【００１９】
次に、コントロールフローグラフを用いて、グローバル変数についての到達定義を算出する。本実施の形態では、到達定義については、ノードｉにおいてグローバル変数ｖが定義されていることをｖｉで表し、任意のノードに到達している定義の集合を｛ｖｉ，ｖｊ，・・・｝と表す。図４（ｂ）に示すように、ノードＮ４で演算されたグローバル変数ｘがｘ４と定義され、ノードＮ６で演算されたグローバル変数ｙがｙ６と定義され、ノードＮ８で演算されたグローバル変数ｘがｘ８と定義され、ノードＮ１１で演算されたグローバル変数ｚがｚ１１と定義される。これらのグローバル変数の定義をパスに従って伝播させると、最終的には、ノードＮ４からノードＮ５を経由してノードＮ６に到達定義集合｛ｘ４｝が到達し、ノードＮ６からノードＮ７を経由してノードＮ８とノードＮ９に到達定義集合｛ｘ４，ｙ６｝が到達し、ノードＮ８からノードＮ１０に到達定義集合｛ｘ８，ｙ６｝が到達するとともにノードＮ９からノードＮ１０に到達定義集合｛ｘ４，ｙ６｝が到達し、ノードＮ１０からノードＮ１１に到達定義集合｛ｘ４，ｘ８，ｙ６｝が到達し、ノードＮ１１からノードＮ１２を経由してノードＮ１３に到達定義集合｛ｘ４，ｘ８，ｙ６，ｚ１１｝が到達する。なお、タスク内にループが存在する場合、一回の伝播では決定できないので、伝播を何度か繰り返し、到達定義集合に変化が無くなったときに終了する。
【００２０】
次に、各ノードの到達定義集合を用いて、出力変数から到達定義を逆順に追跡する。図４（ｃ）に示すように、出力変数ｇｏｕｔが演算されるノードＮ１３を起点とし、ｇｏｕｔはノードＮ１３でグローバル変数ｚを参照して演算されるので、ノードＮ１３に到達している到達定義集合｛ｘ４，ｘ８，ｙ６，ｚ１１｝内の到達定義ｚ１１を追跡する。到達定義ｚ１１はノードＮ１１でグローバル変数ｙを参照して演算されるので、ノードＮ１１を経由して、ノードＮ１１に到達している到達定義集合｛ｘ４，ｘ８，ｙ６｝内の到達定義ｙ６を追跡する。到達定義ｙ６はノードＮ６でグローバル変数ｘを参照して演算されるので、ノードＮ６を経由して、ノードＮ６に到達している到達定義集合｛ｘ４｝内の到達定義ｘ４を追跡する。到達定義ｘ４はノードＮ４でグローバル変数ｘを参照して演算されるので、ノードＮ４に到達する。
【００２１】
次に、出力変数から到達定義を逆順に追跡した結果に基づいて、出力変数のデータフローグラフを生成する。データフローグラフは、入出力変数を楕円で表し、演算を四角形で表し、データセレクタをひし形で表し、エッジには変数が付加される。図４（ｄ）に示すように、生成されたｇｏｕｔを出力変数とするデータフローグラフＤＦＧ０では、演算ノードＡ４で変数ｘと１を参照してｘが演算され、その演算されたｘがエッジＥｘ４で演算ノードＡ６に伝播され、演算ノードＡ６でそのｘを参照してｙが演算され、その演算されたｙがエッジＥｙ６で演算ノードＡ１１に伝播され、演算ノードＡ１１でそのｙを参照してｚが演算され、その演算されたｚがエッジＥｚ１１で演算ノードＡ１３に伝播され、演算ノードＡ１３でそのｚを参照してｇｏｕｔが演算され、ｇｏｕｔが出力される。なお、データフローグラフにはプログラム中の分岐条件の表現等もグラフ化した様々なバリエーションがあるが、本実施の形態では、表現を簡単化するために、それら分岐条件等（例えば、図３のプログラムにおけるＰの分岐条件）を省略するものとする。データフローグラフの構成については、それら分岐条件等を含むものに拡張できる。
【００２２】
上記したように図３に示すｔａｓｋ（）ではステップ４の演算（ｘ＝ｘ＋１）とステップ６の演算（ｙ＝ｘ）においてグローバル変数ｘにストアされた前回値を参照して演算を行う場合がある。しかし、図４（ｄ）に示すデータフローグラフＤＦＧ０では、演算ノードＡ４及び演算ノードＡ６で参照しているｘについては、前回の実行で演算された前回値のｘを参照するような関係になっていない。そのため、従来の方法で生成されたデータフローグラフＤＦＧ０は、図３に示すプログラムを正確に表すものではない。
【００２３】
それでは、図１及び図２を参照して、本実施の形態に係るデータフローグラフ生成装置１について説明する。図１は、本実施の形態に係るデータフローグラフ生成装置の構成図である。図２は、本実施の形態に係るデータフローグラフ生成装置での処理の流れを示すフローチャートである。
【００２４】
データフローグラフ生成装置１は、解析対象のプログラム（ソースコード）Ｐと出力変数Ｖｏｕｔが入力されると、プログラムＰ内に繰り返し実行されるタスクが含まれているか否かを判断する。プログラムＰ内に繰り返し実行されるタスクが含まれていない場合、データフローグラフ生成装置１は、上記した従来の生成方法によって出力変数Ｖｏｕｔを出力とするデータフローグラフＤＦＧを生成する。プログラムＰ内に繰り返し実行されるタスクが含まれている場合、データフローグラフ生成装置１は、上記した従来の生成方法に加えて、繰り返し実行されるタスクのコントロールフローグラフにおいてｅｘｉｔノード（終了ノード）からｅｎｔｒｙノード（開始ノード）までのエッジ（ｅｘｉｔ−ｅｎｔｒｙエッジ）を仮定し、ｅｘｉｔ−ｅｎｔｒｙエッジに従ってｅｘｉｔノードの到達定義集合を前回値（前回値として区別するためにラベリング）としてｅｎｔｒｙノードに伝播させて到達定義計算を行い、出力変数Ｖｏｕｔを出力とするデータフローグラフＤＦＧを生成する。なお、以下の説明では、データフローグラフ生成装置１におけるプログラムＰ内に繰り返し実行されるタスクが含まれている場合の処理についてのみ説明する。
【００２５】
データフローグラフ生成装置１では、まず、繰り返し実行されるタスクを含むプログラムＰの構文解析を行う（Ｓ１）。そして、データフローグラフ生成装置１では、その構文解析結果に基づいて、プログラムＰのコントロールフローグラフを生成する（Ｓ２）。このＳ１、Ｓ２の各処理については、上記で説明した従来の方法と同様の処理である。なお、本実施の形態では、このＳ２の処理が特許請求の範囲に記載するコントロールフローグラフ生成手段、コントロールフローグラフ生成ステップ、コントロールフローグラフ生成機能に相当する。
【００２６】
次に、データフローグラフ生成装置１では、コントロールフローグラフにおいてｅｘｉｔノードからｅｎｔｒｙノードまでを繋ぐｅｘｉｔ−ｅｎｔｒｙエッジを付加（仮定）する（Ｓ３）。このｅｘｉｔ−ｅｎｔｒｙエッジが、到達定義の前回値の伝播路となる。なお、本実施の形態では、このＳ３の処理が特許請求の範囲に記載するエッジ仮定手段、エッジ仮定ステップ、エッジ仮定機能に相当する。
【００２７】
次に、データフローグラフ生成装置１では、コントロールフローグラフを用いて、グローバル変数についての到達定義を算出する（Ｓ４）。この到達定義算出は、前回値の到達定義を反映しておらず、上記で説明した従来の方法と同様の計算である。そして、データフローグラフ生成装置１では、ｅｘｉｔノードに伝播されている到達定義集合をｅｘｉｔ−ｅｎｔｒｙエッジに従ってｅｎｔｒｙノードまで伝播し、その伝播させた到達定義集合を前回値として区別するためにラベル付けを行う（Ｓ４）。さらに、データフローグラフ生成装置１では、そのｅｘｉｔ−ｅｎｔｒｙエッジで伝播させた前回値の到達定義も含めて、到達定義が収束するまで実行中の今回値の到達定義と前回値の到達定義とを区別して伝播を繰り返し行い、最終的な到達定義を計算する（Ｓ４）。この最終的に計算された到達定義は、前回値の依存関係も反映されたものとなる。なお、本実施の形態では、このＳ４の処理が特許請求の範囲に記載する到達定義算出手段、到達定義算出ステップ、到達定義算出機能に相当する。
【００２８】
そして、データフローグラフ生成装置１では、各ノードの到達定義集合を用いて、入力された出力変数Ｖｏｕｔから到達定義を逆順に追跡し、その到達定義の逆順追跡結果に基づいて出力変数Ｖｏｕｔのデータフローグラフを生成する（Ｓ５）。なお、本実施の形態では、このＳ５の処理が特許請求の範囲に記載するデータフローグラフ生成手段、データフローグラフ生成ステップ、データフローグラフ生成機能に相当する。
【００２９】
図３のプログラムを例として、図５及び図６を参照して、データフローグラフ生成装置１におけるデータフローグラフの具体的な生成過程を説明する。ここでは、プログラムＰとして図３に示すプログラムが入力され、出力変数Ｖｏｕｔとしてｇｏｕｔが入力され、ｇｏｕｔを対象とした計算過程やデータの依存関係を表すデータフローグラフが生成される。図５は、本実施の形態に係るデータフローグラフ生成装置でのデータフローグラフの生成過程の一例であり、（ａ）がエッジ付加過程であり、（ｂ）が付加エッジ伝播前の到達定義算出過程であり、（ｃ）が付加エッジ伝播過程である。図６は、本実施の形態に係るデータフローグラフ生成装置でのデータフローグラフの生成過程の一例であり、（ａ）が付加エッジ伝播後の到達定義算出過程であり、（ｂ）が到達定義追跡過程であり、（ｃ）がデータフローグラフ生成過程である。なお、出力変数Ｖｏｕｔについては、ｚ等の他の変数でもよい。
【００３０】
まず、データフローグラフ生成装置１では、上記で説明した従来の方法と同様にプログラムの構文解析を行う。そして、データフローグラフ生成装置１では、その構文解析結果に基づいて、上記で説明した従来の方法と同様にコントロールフローグラフを生成する。したがって、上記と同様に、図４（ａ）に示すコントロールフローグラフＣＦＧが得られる。
【００３１】
次に、データフローグラフ生成装置１では、図５（ａ）に示すように、コントロールフローグラフＣＦＧにおいてｅｘｉｔノードＮ１３からｅｎｔｒｙノードＮ１までのｅｘｉｔ−ｅｎｔｒｙエッジＥ１３１を付加にする。
【００３２】
次に、データフローグラフ生成装置１では、コントロールフローグラフＣＦＧを用いて、上記で説明した従来の方法と同様に、グローバル変数ｘ，ｙ，ｚについての到達定義を算出する。したがって、図５（ｂ）に示すように、到達定義集合としては、図４（ｂ）に示す到達定義集合と同じものが得られる。この図５（ｂ）に示す到達定義集合は、前回値の到達定義が未だ反映されていない。
【００３３】
次に、データフローグラフ生成装置１では、図５（ｃ）に示すように、ｅｘｉｔ−ｅｎｔｒｙエッジＥ１３１に従って、ｅｘｉｔノードＮ１３に伝播されている到達定義集合｛ｘ４，ｘ８，ｙ６，ｚ１１｝をｅｎｔｒｙノードＮ１に伝播し、伝播した到達定義集合｛ｘ４，ｘ８，ｙ６，ｚ１１｝を前回値として区別するために到達定義集合｛ｘ４’，ｘ８’，ｙ６’，ｚ１１’｝に変更する。本実施の形態では、前回値のラベル付けとして、前回値の到達定義にはアポストロフィ「’」を付加している。なお、前回値を区別するためのラベル付けについては、どのようなものでもよい。
【００３４】
次に、データフローグラフ生成装置１では、ｅｎｔｒｙノードＮ１に伝播された前回値の到達定義集合｛ｘ４’，ｘ８’，ｙ６’，ｚ１１’｝も用いて、到達定義が収束するまで到達定義の伝播を繰り返す。これによって、図６（ａ）に示す到達定義集合が最終的に得られ、ノードＮ１からノードＮ２を経由してノードＮ３とノードＮ４に到達定義集合｛ｘ４’，ｘ８’，ｙ６’，ｚ１１’｝が到達し、ノードＮ３からノードＮ５に到達定義集合｛ｘ４’，ｘ８’，ｙ６’，ｚ１１’｝が到達し、ノードＮ４からノードＮ５に到達定義集合｛ｘ４，ｙ６’，ｚ１１’｝が到達し、ノードＮ５からノードＮ６に到達定義集合｛ｘ４，ｘ４’，ｘ８’，ｙ６’，ｚ１１’｝が到達し、ノードＮ６からノードＮ７を経由してノードＮ８とノードＮ９に到達定義集合｛ｘ４，ｘ４’，ｘ８’，ｙ６，ｚ１１’｝が到達し、ノードＮ８からノードＮ１０に到達定義集合｛ｘ８，ｙ６，ｚ１１’｝が到達し、ノードＮ９からノードＮ１０に到達定義集合｛ｘ４，ｘ４’，ｘ８’，ｙ６，ｚ１１’｝が到達し、ノードＮ１０からノードＮ１１に到達定義集合｛ｘ４，ｘ４’，ｘ８，ｘ８’，ｙ６，ｚ１１’｝が到達し、ノードＮ１１からノードＮ１２を経由してノードＮ１３に到達定義集合｛ｘ４，ｘ４’，ｘ８，ｘ８’，ｙ６，ｚ１１｝が到達する。
【００３５】
次に、データフローグラフ生成装置１では、各ノードの到達定義集合を用いて、出力変数のｇｏｕｔから到達定義を逆順に追跡する。図６（ｂ）に示すように、出力変数ｇｏｕｔが演算されるノードＮ１３を起点とし、ｇｏｕｔはノードＮ１３でグローバル変数ｚを参照して演算されるので、ノードＮ１３に到達している到達定義集合｛ｘ４，ｘ４’，ｘ８，ｘ８’，ｙ６，ｚ１１｝内の到達定義ｚ１１を追跡する。到達定義ｚ１１はノードＮ１１でグローバル変数ｙを参照して演算されるので、ノードＮ１１を経由して、ノードＮ１１に到達している到達定義集合｛ｘ４，ｘ４’，ｘ８，ｘ８’，ｙ６，ｚ１１’｝内の到達定義ｙ６を追跡する。到達定義ｙ６はノードＮ６でグローバル変数ｘを参照して演算されるので、ノードＮ６を経由して、ノードＮ６に到達している到達定義集合｛ｘ４，ｘ４’，ｘ８’，ｙ６’，ｚ１１’｝内の到達定義ｘ４，ｘ４’，ｘ８’を追跡する。つまり、ノードＮ６の演算ではこの３つの到達定義ｘ４，ｘ４’，ｘ８’のいずれか１つを参照して演算を行うので、ノードＮ６の演算で参照する可能性のある３つの到達定義ｘ４，ｘ４’，ｘ８’を追跡する必要がある。したがって、データフローグラフを生成する際に、ノードＮ６の演算の前にこの３つの値から１つの値を選択するためのセレクタが必要となる。
【００３６】
到達定義ｘ４はノードＮ４でグローバル変数ｘを参照して演算されるので、ノードＮ４を経由して、ノードＮ４に到達している到達定義集合｛ｘ４’，ｘ８’，ｙ６’，ｚ１１’｝内の到達定義ｘ４’，ｘ８’を追跡する。つまり、ノードＮ４の演算ではこの２つの到達定義ｘ４’，ｘ８’のいずれか１つを参照して演算を行うので、ノードＮ４の演算で参照する可能性のある２つの到達定義ｘ４’，ｘ８’を追跡する必要がある。したがって、データフローグラフを生成する際に、ノードＮ４の演算の前にこの２つの値から１つの値を選択するためのセレクタが必要となる。到達定義ｘ４’の追跡は、到達定義ｘ４の追跡と同様であり、到達定義ｘ４’，ｘ８’を追跡する。到達定義ｘ８’はノードＮ８でｇｉｎを参照して演算されるので、ノードＮ８に到達する。
【００３７】
次に、データフローグラフ生成装置１では、出力変数ｇｏｕｔから到達定義を逆順に追跡した結果に基づいて、出力変数ｇｏｕｔのデータフローグラフＤＦＧ１を生成する。本実施の形態では、データフローグラフにおいて点線のエッジで前回値の参照を示している。図６（ｃ）に示すように、生成されたｇｏｕｔを出力変数とするデータフローグラフＤＦＧ１では、ノードとしては、演算ノードＡ４，Ａ６，Ａ８，Ａ１１，Ａ１３以外に、演算ノードＡ４で参照するｘの値を選択するためのセレクタノードＳ１が付加されるとともに、演算ノードＡ６で参照するｘの値を選択するためのセレクタノードＳ２が付加される。前回実行時に演算ノードＡ８で入力変数ｇｉｎを参照してｘ（前回値）が演算され、その前回演算されたｘ（前回値）がエッジＥｘ８’Ｓ１でセレクタノードＳ１に伝播されるとともにエッジＥｘ８’Ｓ２でセレクタノードＳ２に伝播される。セレクタノードＳ１には演算ノードＡ８で前回演算されたｘ（前回値）と演算ノードＡ４で前回演算されたｘ（前回値）が伝播され、セレクタノードＳ１でその２つのｘから１つのｘが選択され（実際には、プログラムのｔａｓｋ（）の前回実行時のステップ８のｘ＝ｇｉｎで演算されたｘ値又は前回実行時のステップ４のｘ＝ｘ＋１で演算されたｘ値がストアされたグローバル変数ｘの値である）、その選択されたｘがエッジＥｘＳ１で演算ノードＡ４に伝播される。今回実行時に演算ノードＡ４でそのセレクタノードＳ１からのｘと１を参照してｘ（今回値）が演算され、その演算されたｘ（今回値）がエッジＥｘ４Ｓ２でセレクタノードＳ２に伝播される。また、前回実行時に演算ノードＡ４でそのセレクタノードＳ１からのｘと１を参照してｘ（前回値）が演算され、その前回演算されたｘ（前回値）がエッジＥｘ４’Ｓ２でセレクタノードＳ２に伝播されるとともにエッジＥｘ４’Ｓ１でセレクタノードＳ１に伝播される。セレクタノードＳ２には演算ノードＡ８で前回演算されたｘ（前回値）と演算ノードＡ４で前回演算されたｘ（前回値）と演算ノードＡ４で今回演算されたｘ（今回値）が伝播され、セレクタノードＳ２でその３つのｘから１つのｘが選択され（実際には、プログラムのｔａｓｋ（）の前回実行時のステップ８のｘ＝ｇｉｎで演算されたｘ値又は前回実行時のステップ４のｘ＝ｘ＋１で演算されたｘ値又は今回実行時のステップ４のｘ＝ｘ＋１で演算されたｘ値がストアされたグローバル変数ｘの値である）、その選択されたｘがエッジＥｘＳ２で演算ノードＡ６に伝播される。そして、演算ノードＡ６でそのｘを参照してｙが演算され、その演算されたｙがエッジＥｙ６で演算ノードＡ１１に伝播され、演算ノードＡ１１でそのｙを参照してｚが演算され、その演算されたｚがエッジＥｚ１１で演算ノードＡ１３に伝播され、演算ノードＡ１３でそのｚを参照してｇｏｕｔが演算され、ｇｏｕｔが出力される。
【００３８】
このデータフローグラフＤＦＧ１には、演算ノードＡ４におけるグローバル変数ｘの参照として、演算ノードＡ４で前回演算されたｘ（前回値）、演算ノードＡ８で前回演算されたｘ（前回値）のうちの何れかのｘが参照される関係がグラフ化されている。また、データフローグラフＤＦＧ１には、演算ノードＡ６におけるグローバル変数ｘの参照として、演算ノードＡ４で今回演算されたｘ（今回値）、演算ノードＡ４で前回演算されたｘ（前回値）、演算ノードＡ８で前回演算されたｘ（前回値）のうちの何れかのｘが参照される関係がグラフ化されている。このように、データフローグラフＤＦＧ１は、図４（ｄ）に示す従来の生成方法によるデータフローグラフＤＦＧ０では表されないグローバル変数ｘの前回値に依存する演算も反映されており、図３に示すプログラムを正確に表している。
【００３９】
このデータフローグラフ生成装置１によれば、繰り返し実行されるタスクを含むプログラムでも、到達定義計算時にｅｘｉｔノードの到達定義をｅｎｔｒｙノードに前回値として伝播させることにより、グローバル変数にストアされる前回値に依存する演算も正確に反映することができ、高精度なデータフローグラフを生成できる。また、データフローグラフ生成装置１によれば、ｅｘｉｔノードからｅｎｔｒｙノードに伝播させた到達定義に対して前回値としてのラベル付けを行うことにより、今回値の到達定義と前回値の到達定義とを区別しながら、到達定義が収束するまで容易かつ正確に伝播させることができる。
【００４０】
以上、本発明に係る実施の形態について説明したが、本発明は上記実施の形態に限定されることなく様々な形態で実施される。
【００４１】
例えば、本実施の形態ではデータフローグラフを生成するデータフローグラフ生成装置に適用したが、ＣＤ−ＲＯＭ等の記憶媒体に格納されたプログラムやインタネット等のネットワークを介して利用可能なプログラム等に適用し、このようなプログラムをコンピュータ上で実行することによってデータフローグラフを生成する構成としてもよい。
【符号の説明】
【００４２】
１…データフローグラフ生成装置。
【図１】
2012155605.tif 000003
【図２】
2012155605.tif 000004
【図３】
2012155605.tif 000005
【図４】
2012155605.tif 000006
【図５】
2012155605.tif 000007
【図６】
2012155605.tif 000008