(57)【要約】データ依存解析支援装置は、プログラムで使用される全てのポインタに対して、コンテキストセンシティブなポインタ解析を行ってポインタ情報を算出し、解析対象領域と解析対象領域が実行されるときに呼び出される可能性のある全ての文に対して、コンテキストセンシティブなポインタ情報を用いてコンテキストセンシティブなデータフロー解析を行い、文間におけるデータフロー情報を算出し、データフロー情報を用いて、ソースプログラムに含まれる２以上のスレッド化領域において、領域間のデータ依存情報を算出する。
2013105158.tif 000002
【特許請求の範囲】
【請求項１】
ソースプログラムに対してコンテキストセンシティブなデータ依存解析を行うデータ依存解析支援装置であって、
前記ソースプログラムで使用される全てのポインタに対して、コンテキストセンシティブなポインタ解析を行い、ポインタ情報を生成するポインタ情報生成部と、
前記ソースプログラムの一部であって、２以上のスレッド化領域の間に存在するデータ依存を解析するために指定される解析対象領域に対して、前記ポインタ情報を用いて、コンテキストセンシティブなデータフロー解析を行い、データフロー情報を生成するデータフロー情報生成部と、
前記データフロー情報を用いて、前記２以上のスレッド化領域の間に存在するデータ依存について、依存元のスレッド化領域と、依存先のスレッド化領域と、依存の原因である変数とを示す領域間依存情報を生成する領域間依存情報生成部と
を備えることを特徴とするデータ依存解析支援装置。
【請求項２】
前記解析対象領域は、前記２以上のスレッド化領域の全てを含む、単一の関数と前記単一の関数により呼び出される関数との集合である
ことを特徴とする請求項１記載のデータ依存解析支援装置。
【請求項３】
前記データフロー情報生成部は、
前記解析対象領域を含む単一の関数と、前記関数より呼び出される関数とで使用されるポインタについて、前記単一の関数を１つのコンテキストとして前記ポインタ情報を結合し結合ポインタ情報を生成する
ことを特徴とする請求項１記載のデータ依存解析支援装置。
【請求項４】
前記解析対象領域を指定するための情報の入力を受け付ける解析対象領域指定部
をさらに備えることを特徴とする請求項１記載のデータ依存解析支援装置。
【請求項５】
前記スレッド化領域を指定するための情報の入力を受け付ける領域指定部
をさらに備えることを特徴とする請求項１記載のデータ依存解析支援装置。
【請求項６】
前記領域間依存情報を出力する領域間依存情報出力部
をさらに備えることを特徴とする請求項１記載のデータ依存解析支援装置。
【請求項７】
前記データフロー情報生成部は、
前記ポインタ情報生成部が同一のソースプログラムに対するポインタ情報を保持している場合に、前記保持されているポインタ情報を用いてデータフロー情報を生成する
ことを特徴とする請求項１記載のデータ依存解析支援装置。
【請求項８】
前記領域間依存情報生成部は、
前記データフロー解析部が同一の解析対象領域に対するデータフロー情報を保持している場合に、前記保持されているデータフロー情報を用いて領域間依存情報を生成する
ことを特徴とする請求項１記載のデータ依存解析支援装置。
【請求項９】
ソースプログラムに対するコンテキストセンシティブなデータ依存解析をコンピュータに実行させるデータ依存解析支援プログラムであって、
前記コンテキストセンシティブなデータ依存解析は、
前記ソースプログラムで使用される全てのポインタに対して、コンテキストセンシティブなポインタ解析を行い、ポインタ情報を生成するポインタ情報生成ステップと、
前記ソースプログラムの一部であって、２以上のスレッド化領域の間に存在するデータ依存を解析するために指定される解析対象領域に対して、前記ポインタ情報を用いて、コンテキストセンシティブなデータフロー解析を行い、データフロー情報を生成するデータフロー情報生成ステップと、
前記データフロー情報を用いて、前記２以上のスレッド化領域の間に存在するデータ依存について、依存元のスレッド化領域と、依存先のスレッド化領域と、依存の原因である変数とを示す領域間依存情報を生成する領域間依存情報生成ステップと
を含むことを特徴とするデータ依存解析支援プログラム。
【請求項１０】
ソースプログラムに対してコンテキストセンシティブなデータ依存解析を行うデータ依存解析支援方法であって、
前記ソースプログラムで使用される全てのポインタに対して、コンテキストセンシティブなポインタ解析を行い、ポインタとポインタが指し示す変数との対応情報であるポインタ情報を生成するポインタ情報生成ステップと、
前記ソースプログラムの一部であって、２以上のスレッド化領域の間に存在するデータ依存を解析するために指定される解析対象領域に対して、前記ポインタ情報を用いて、コンテキストセンシティブなデータフロー解析を行い、データフロー情報を生成するデータフロー情報生成ステップと、
前記データフロー情報を用いて、前記２以上のスレッド化領域の間に存在するデータ依存について、依存元のスレッド化領域と、依存先のスレッド化領域と、依存の原因である変数とを示す領域間依存情報を生成する領域間依存情報生成ステップと
を含むことを特徴とするデータ依存解析支援方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列処理システムを実現するためのプログラム開発技術に関し、特にソースプログラムをデータ依存解析する技術に関する。
【背景技術】
【０００２】
昨今のデジタルテレビ、ブルーレイレコーダ、携帯電話など、マルチメディア処理の量と質の拡大や、通信速度の拡大、ゲーム機器に代表されるインタフェース処理量の拡大等により、民生用組込機器に搭載されるプロセッサへの性能向上の要望は留まることはない。【０００３】
また、昨今の半導体技術の進歩により、マルチプロセッサ構成によりスレッドを並列実行できるプロセッサや、単一プロセッサで複数スレッドを並列実行できるプロセッサが民生用組込機器に搭載されるようになってきている。【０００４】
一方で、これまでに、単一プロセッサでの実行を前提としたシーケンシャルプログラムが資産として蓄積されている。特に、Ｃ言語やＣ＋＋言語で記述されたシーケンシャルプログラムは膨大である。これらのシーケンシャルプログラムの資産を流用し、並列化によりプログラムの高速化を実現することが切望されている。【０００５】
また、新規のプログラム開発においても、スレッド並列化プログラムの開発や検証は、シーケンシャルプログラムと比較して難しい。このため、スレッド並列化プログラムを直接的に開発するのではなく、シーケンシャルプログラムを開発し検証を完了した後で、シーケンシャルプログラムのスレッド並列化を行うという開発方法が一般的である。【０００６】
シーケンシャルプログラムのスレッド並列化を行う従来例として、特許文献１にプログラム処理装置が開示されている。特許文献１のプログラム処理装置は、シーケンシャルプログラムのソースコードに、指示子ＴＨＲＥＡＤを用いてスレッド化領域を指定したものを並列処理プログラムとして受け付ける。そして、特許文献１のプログラム処理装置は、スレッド化領域の間の依存関係を解析し、スレッド間でデータの授受がある変数について、データの授受を行うためのスレッド間通信コードをスレッド並列化後の各スレッドに挿入することでスレッド並列化を行っている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００７−１９３４２３号公報
【非特許文献】
【０００８】
【非特許文献１】Ａｌｆｒｅｄ  Ｖ．Ａｈｏ，ｅｔ  ａｌ，  ”Ｃｏｍｐｉｌｅｒｓ：Ｐｒｉｎｃｉｐｌｅｓ，  Ｔｅｃｈｎｉｑｕｅｓ＆Ｔｏｏｌｓ  Ｓｅｃｏｎｄ  Ｅｄｉｔｉｏｎ”，  Ａｄｄｉｓｏｎ  Ｗｅｓｌｅｙ，  ２００７
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、特許文献１の技術では、シーケンシャルプログラムには存在しないスレッド間の通信コードをスレッド並列化後の各スレッドに挿入するため、通信コードが新たなオーバヘッドとなる。特に、データ依存解析の精度が低く不必要な通信コードが挿入されると、並列化プログラムの速度が低下する問題がある。【００１０】
その一方で、高精度のデータ依存解析を行うためには、一般に、極めて長時間の解析時間を必要とする。【００１１】
本発明は、スレッド化領域間のデータ依存解析を精度よくかつ短時間に完了するデータ依存解析支援装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記の課題を解決するために、本発明に係るデータ依存解析支援装置は、ソースプログラムに対してコンテキストセンシティブなデータ依存解析を行うデータ依存解析支援装置であって、前記ソースプログラムで使用される全てのポインタに対して、コンテキストセンシティブなポインタ解析を行い、ポインタ情報を生成するポインタ情報生成部と、前記ソースプログラムの一部であって、２以上のスレッド化領域の間に存在するデータ依存を解析するために指定される解析対象領域に対して、前記ポインタ情報を用いて、コンテキストセンシティブなデータフロー解析を行い、データフロー情報を生成するデータフロー情報生成部と、前記データフロー情報を用いて、前記２以上のスレッド化領域の間に存在するデータ依存について、依存元のスレッド化領域と、依存先のスレッド化領域と、依存の原因である変数とを示す領域間依存情報を生成する領域間依存情報生成部とを備えることを特徴とする。
【発明の効果】
【００１３】
上記の構成によれば、データ依存解析支援装置は、データ依存解析の一部の処理であるデータフロー解析をソースプログラム全体ではなく解析対象領域に対してのみ行うことにより解析時間を短縮でき、またデータ依存解析の一部の処理であるポインタ解析とデータフロー解析とについてコンテキストセンシティブな解析を行うので高精度にスレッド化領域間の依存情報を得ることができ、高精度の解析と解析時間の短縮の両立が可能となる。
【図面の簡単な説明】
【００１４】
【図１】実施の形態に係るデータ依存解析支援装置１００の構成を示すブロック図。
【図２】実施の形態に係るデータフロー解析部２０６およびデータフロー情報記憶部２０７の構成を示すブロック図。
【図３】実施の形態に係るソースプログラム１１の例を示す図。
【図４】実施の形態に係るコールグラフ記憶部２０３に格納されるコールグラフの例を示す図。
【図５】実施の形態に係るデータ依存解析支援装置１００の動作を示すフローチャート。
【図６】実施の形態に係るポインタ情報結合部２２０の動作を示すフローチャート。
【図７】実施の形態に係る領域間依存生成部２１０の動作を示すフローチャート。
【図８】実施の形態に係る中間プログラム記憶部２０１に格納される文情報の例を示す図。
【図９】実施の形態に係るポインタ情報記憶部２０５に格納されるポインタ情報の例を示す図。
【図１０】実施の形態に係る結合ポインタ情報記憶部２２１に格納されるポインタ情報の例を示す図。
【図１１】実施の形態に係る定義情報記憶部２２３に格納される定義情報の例を示す図。
【図１２】実施の形態に係る使用情報記憶部２２５に格納される使用情報の例を示す図。
【図１３】実施の形態に係る到達定義情報記憶部２２７に格納される到達定義情報の例を示す図。
【図１４】実施の形態に係る文間依存情報記憶部２０９に格納される文間依存情報の例を示す図。
【図１５】実施の形態に係る領域間依存情報記憶部２１１に格納される領域間依存情報の例を示す図。
【図１６】実施の形態に係るユーザ入力情報４１である、システム終了情報、解析対象領域情報、および、領域指定情報の例を示す図。
【図１７】実施の形態に係るテキストおよびマウスによる領域指定の例を示す図。
【図１８】実施の形態に係るテキストおよびソースプログラム１１上での領域間依存表示の例を示す図。
【図１９】実施の形態に係るスレッド並列化の例を示す図。
【図２０】実施の形態に係るソースプログラム１１中に記述した領域間指定の例を示す図。
【発明を実施するための形態】
【００１５】
＜本発明の概要＞
シーケンシャルプログラムをソースプログラムとしてスレッド並列化プログラムを開発するためには、シーケンシャルプログラムにおいてスレッド並列化を行おうとする領域のデータ依存解析を行う必要がある。特に、データ依存をスレッド間の通信コードによって解決する並列化（パイプライン化）を行うにあたって、不必要な通信コードを挿入しないために、精度の高いデータ依存解析を行うことが望ましい。
【００１６】
しかしながら、コンテキストセンシティブな解析は、各々の関数呼び出し毎に呼び出し先の関数まで含めて解析することである。そのため、一つの関数を一度しか解析しないコンテキストセンシティブでない解析と比較すると解析に要する時間が長く、特にプログラム全体に対してコンテキストセンシティブな解析を行うにはきわめて長時間の解析時間を必要とする。
【００１７】
ここで、シーケンシャルプログラムがＣ言語やＣ＋＋言語で記述されている場合、データ依存解析の手順には、ポインタがどの変数を指し示すのかを解析するポインタ解析と、変数がどのように定義・参照されるか、および参照の際にどの文で定義される値かを解析するデータフロー解析とが含まれる。
【００１８】
ポインタ解析については、ソースプログラム全体に対して行う必要がある。なぜならば、どの変数を指し示すか不明なポインタが存在すると、当該ポインタの間接参照がどの変数の定義または使用に該当するのかが判定できず、精度の高いデータ依存解析ができないからである。
【００１９】
一方で、発明者らはデータフロー解析については、ポインタ解析がソースプログラム全体に対してなされていれば、データ依存解析の対象となるソースプログラムの一部領域にのみ行えばよいことの知見を得た。なぜならば、本来、着目している領域（当該領域が繰り返しや分岐などの制御構造の一部であれば、当該制御構造全体）および当該領域より呼び出される文の集合である被呼び出し領域（以下、着目している領域と被呼び出し領域とをまとめて解析対象領域と呼ぶ）に、領域内のデータ依存を解析するために必要な情報が全て含まれているからであり、唯一不明瞭であるのはポインタと変数との関係である為である。すなわち、ポインタがどの変数を指し示すかが明らかであれば、解析対象領域に対するデータフロー解析を行えばデータ依存解析が可能である。
【００２０】
ここで、コンテキストセンシティブなポインタ解析の解析時間はポインタの総数に依存し、コンテキストセンシティブなデータフロー解析の解析時間は解析対象の文数に依存する。一般的に、プログラムの文数はポインタの総数と比較すればきわめて多く、同一のソースプログラムの全域に対して解析を行う場合、コンテキストセンシティブなデータフロー解析の解析時間はコンテキストセンシティブなポインタ解析のおよそ１０倍程度も要する。
【００２１】
本発明は、コンテキストセンシティブなポインタ解析がソースプログラム全体に渡って行われる必要があるのに対し、スレッド化領域全てを含む解析対象領域にのみコンテキストセンシティブなデータフロー解析を行うことでスレッド化領域間の依存関係が解析できることに着目した。そこで、解析時間の大部分を占めているデータフロー解析の処理対象を限定することで、精度の高いコンテキストセンシティブな解析と解析時間の短縮の両立を実現した。以下に、並列化の手順と解析方法による精度の違いについて説明する。
【００２２】
＜シーケンシャルプログラムの並列化手順＞
ここで、シーケンシャルプログラムのデータ依存解析およびスレッド並列化の、一般的な手順について説明する。シーケンシャルプログラムがＣ言語やＣ＋＋言語で記述されている場合、スレッド化領域間のデータ依存解析を行う解析装置は、次の手順で解析を行う。
【００２３】
まず、解析装置は、ポインタがどの変数が指し示すのかを解析するポインタ解析を行う。
【００２４】
次に、解析装置は、ポインタ解析結果を利用して、変数がどの文で保持する値が更新され、どの文で保持する値が参照されるかを解析するデータフロー解析を行う。ここで「文」（ｓｔａｔｅｍｅｎｔ）とは、プログラムの手続構造の基本単位であり、Ｃ言語やＣ＋＋言語においては、セミコロンで区切られた要素単位である。
【００２５】
以下、説明の簡素化のために、「変数が保持する値」を「変数の値」と言い、「変数が保持する値の更新」を「変数の定義」と言い、「変数が保持する値の参照」を「変数の使用」と言う。ここで、「更新」とは、値が未定義である変数に新たに値を代入することも含む。
【００２６】
次に、解析装置は、データフロー解析から各文間のデータ依存解析を行う。データ依存とは、変数ｘがある場合に、１つの文において変数ｘが定義され、他の文において変数ｘが使用される関係をいう。
【００２７】
次に、解析装置は、スレッド化領域間でデータの授受がある変数を特定する領域間のデータ依存解析を行う。そして解析装置は、スレッド化領域間でデータの授受がある変数が保持する値を領域間で受け渡すために、通信コードをスレッド内に挿入する。
【００２８】
重要なのは、データ依存解析の精度を高めることがスレッド並列化プログラムの高速化に貢献することである。スレッド化領域間にデータ依存が存在するにもかかわらず、通信コードを挿入せずスレッド並列化を行おうとすると、依存先の文が依存元の文と異なるスレッドに存在する場合に、依存先の文を正常に実行できない、またはシーケンシャルプログラムと実行結果が異なるという問題が生じる。そのため、データ依存解析はスレッド化領域間のデータ依存を全て検出しなければならない。
【００２９】
しかしながら、前述したように通信コードはシーケンシャルプログラムには存在しないコードであるから、不必要な通信コードはスレッド並列化プログラムのオーバヘッドの要因となる。したがって、存在するデータ依存を全て検出することを前提としながらも、存在しないデータ依存を誤検出しないデータ依存解析が求められる。
【００３０】
ここで、データ依存解析の手法について、コンテキストセンシティブな解析について説明する。
【００３１】
＜コンテキストセンシティブな解析＞
コンテキストセンシティブな解析とは、非特許文献１の第１２章にあるような、同じ関数の呼び出しであっても、各々の関数呼び出しの状況に応じた解析を行うことである。つまり、ポインタ解析、データフロー解析および文間のデータ依存解析を各々の関数呼び出し毎に、すなわち、同一の関数の呼び出しでも個々の関数呼び出し毎に、呼び出し先の関数まで含めて解析することである。したがって、着目している領域の全体に渡って解析を行うだけでなく、当該領域内で同一関数が複数個所で呼び出されている場合は、呼び出し毎に何度も同一の関数に関して解析を行う。なお、呼び出される関数がさらに関数を呼び出している場合についても同様に、個々の関数の呼び出し毎に、呼び出し先の関数まで含めて解析する。
【００３２】
ここで、図３を用いて、スレッド化領域、通信コード、ポインタ解析、データフロー解析、データ依存解析について説明する。図３は、スレッド並列化の対象とする、Ｃ／Ｃ＋＋言語で記述されたソースプログラムの例である。図３（ａ）はファイル名ｒｅｉ．ｃのファイル、図３（ｂ）はファイル名ｐｒｏｃ．ｃのファイル、図３（ｃ）はファイル名ｃｍｎ．ｃのファイルのそれぞれの内容を表し、先頭の番号は行番号である。また、図中の”文＋番号”は文の識別子を表現しており、番号でもって文を一意に特定するものである。
【００３３】
図３（ａ）に示されるように、ｒｅｉ．ｃにはプログラムの最初に実行される関数ｍａｉｎがある。さらに、関数ｍａｉｎは関数ｓｕｂを呼び出しており、さらに、関数ｓｕｂは、ファイルｐｒｏｃ．ｃ中の関数ｐｒｏｃ、関数ｐｒｏｃ２、関数ｐｒｏｃ３を呼び出す。さらに、図３（ｂ）に示されるように、関数ｐｒｏｃは、ファイルｃｍｎ．ｃ中の関数ｆｕｎ、関数ｇｕｎを呼び出す。
【００３４】
ここで、図３（ｂ）の関数ｐｒｏｃの行番号７のｆｏｒループ中にある行番号８から行番号１９（不図示）までがスレッド化したい領域Ｒ１、同様に、行番号２０から行番号２９（不図示）までがスレッド化したい領域Ｒ２、行番号３０から行番号３９（不図示）までがスレッド化したい領域Ｒ３である。
【００３５】
次にスレッド間で値の授受を行う通信コードについて図３（ｂ）を用いて説明する。領域Ｒ１中の文５７で定義される変数ｓの値を領域Ｒ２中の文６１および文６５で使用しており、領域Ｒ１と領域Ｒ２の間において、変数ｓを原因とするデータ依存が存在する。そのため、領域Ｒ１をスレッド化したスレッド１と、領域Ｒ２をスレッド化したスレッド２の間で、変数ｓの値を授受するために、通信コードをスレッド１およびスレッド２に挿入する必要がある。
【００３６】
次に、図３を用いて、ポインタ解析およびデータ依存解析において、コンテキストセンシティブな解析と、コンテキストセンシティブでない解析との違いを説明する。図３（ｂ）において、関数ｆｕｎの呼び出しが文５７と文６６の２箇所に存在する。文５７の関数ｆｕｎの呼び出しでは変数ｅのアドレスを関数ｆｕｎの仮引数であるポインタｐに引き渡しており、同様に、文６６では変数ｆのアドレスを関数ｆｕｎの仮引数であるポインタｐに引き渡している。以下では、文５７における関数ｆｕｎの呼び出しを用いて説明する。
【００３７】
なお、図３（ｂ）において行番号１１（不図示）〜行番号３９（不図示）では、図示されている行を除いて変数ｅ、変数ｆは定義も使用もされておらず、図３（ｃ）において行番号５（不図示）〜行番号８では、図示されている行を除いてポインタｐは定義も使用もされておらず、ポインタｐの間接参照＊ｐによる、ポインタｐが指し示す変数の定義も使用もされていないものとする。
【００３８】
１．コンテキストセンシティブでないポインタ解析およびデータフロー解析
まず、コンテキストセンシティブでないポインタ解析について説明する。解析装置は、プログラム中の関数ｆｕｎを呼び出している文を検索し、仮引数であるポインタｐに引き渡される値を収集する。解析装置は、文５７と文６６から、ポインタｐに引き渡される値として、変数ｅおよび変数ｆのアドレスを収集する。
【００３９】
これにより、解析装置は、関数ｆｕｎの文１０１において、ポインタｐは変数ｅまたは変数ｆの両方の変数を指すと解析する。
【００４０】
次に、解析装置は、コンテキストセンシティブでないポインタ解析の結果を用いてコンテキストセンシティブでないデータフロー解析を行う。解析装置は、文６１において、変数ｅの使用があると解析し、文６５において、変数ｆの使用があると解析する。また、解析装置は、行番号７〜４０のループから、文５６において、変数ｅの使用があると解析する。
【００４１】
また、関数ｆｕｎの文１０１において、ポインタｐは変数ｅまたは変数ｆの両方を指すので、解析装置は、文１０１において、変数ｅまたは変数ｆの両方の変数が使用され、かつ、定義されると解析する。
【００４２】
これにより、解析装置は、文１０１の呼び出し元である、文５７における関数ｆｕｎの呼び出しにおいて、変数ｅまたは変数ｆの両方の変数が定義されると解析する。
【００４３】
次に、解析装置は、コンテキストセンシティブでないデータフロー解析の結果を用いてデータ依存解析を行う。解析装置は、文５７において変数ｆが定義されると解析し、文６５において変数ｆが使用されると解析するので、文５７から文６５へ、変数ｆに起因するデータ依存があると解析する。
【００４４】
同様に、解析装置は、文５７から文６１および文５６へ、変数ｅに起因するデータ依存があると解析する。
【００４５】
２．コンテキストセンシティブなポインタ解析およびデータフロー解析
コンテキストセンシティブな解析においては、解析装置は、文５７からの関数ｆｕｎの呼び出しと、文６６からの関数ｆｕｎの呼び出しを区別する。
【００４６】
まず、コンテキストセンシティブなポインタ解析について説明する。解析装置は、文５７からの関数ｆｕｎの呼び出しにおいて、関数ｆｕｎの仮引数であるポインタｐは、文５７の関数ｆｕｎの引数である、変数ｅのアドレスであると解析する。これにより、解析装置は、文５７から呼び出される関数ｆｕｎの文１０１のポインタｐが保持する値は、変数ｅのアドレスであると解析する。
【００４７】
次に、解析装置は、コンテキストセンシティブなポインタ解析の結果を用いてコンテキストセンシティブなデータフロー解析を行う。文５７から呼び出される関数ｆｕｎの文１０１においてポインタｐは変数ｅを指しているので、解析装置は、文１０１において変数ｅが定義されると解析する。
【００４８】
また、解析装置は、文１０１で定義される変数ｅが、文６１において使用されると解析する。同様に、解析装置は、行番号７〜４０のループにより、文１０１で定義される変数ｅが、文５６で使用されると解析する。
【００４９】
次に、解析装置は、コンテキストセンシティブなデータフロー解析の結果を用いてデータ依存解析を行う。解析装置は、文１０１で定義される変数ｅが、文５６と文６１とで使用されると解析しているので、文１０１から文５６および文６１へ、変数ｅを原因とするデータ依存が存在すると解析する。
【００５０】
３．データ依存解析結果の検討
上記解析手順によって得られた結果を基に、コンテキストセンシティブな解析とコンテキストセンシティブでない解析とを比較する。
【００５１】
文５７（文５７から呼び出される文１０１）を依存元とする解析結果を比較すると、いずれの場合も、解析装置は、文５７（文５７から呼び出される文１０１）から文５６および文６１へ、変数ｅを原因とするデータ依存が存在すると解析する。
【００５２】
一方、コンテキストセンシティブでない解析においては、解析装置は、上記解析結果に加えて、文５７から文６５へ、変数ｆに起因するデータ依存があると解析する。しかしながら、文５７でポインタｐに引き渡される値は変数ｅのアドレスであるから、呼び出される関数ｆｕｎの文１０１において変数ｆの値は定義されておらず、文５７から文６５へ、変数ｆを原因とするデータ依存は存在しない。このように、コンテントセンシティブでない解析では、実際には依存関係がないにもかかわらず、データ依存が存在するといった誤った解析結果が得られることがある。これは、文５７からの関数ｆｕｎの呼び出しと文６６からの関数ｆｕｎの呼び出しを区別しないので、文６６からの関数ｆｕｎの呼び出しにおける引数ｆを文５７においても関数ｆｕｎの引数として扱うためである。
【００５３】
一方、コンテキストセンシティブな解析では、実際に存在するデータ依存のみが検出されており、結果、精度の高い解析が可能である。
【００５４】
≪実施の形態≫
以下、本発明の実施の形態について、図面を使用しながら説明する。まず、本発明の実施の形態の説明にあたり、理解の容易のため、用語について説明する。
【００５５】
＜用語の説明＞
・コンテキストセンシティブなコールグラフ
コンテキストセンシティブなコールグラフ（以下、単純にコールグラフと言う）とは、各々の関数呼び出し毎にノードが生成され、呼び出す関数のノードから、呼び出される関数のノードへ有向辺を引いたグラフである。ノードは、ノード識別子と、呼び出し関数名と、関数呼び出し文の文識別子とを持つ。
【００５６】
図４は、図３に対するコールグラフである。例えば、ノード識別子が２のノードは、図３（ａ）の行番号２５の関数呼び出し文２５に対応して生成されたノードである。
【００５７】
ノード識別子はノードに固有に付与される番号である。よって、あるノードに着目した時、プログラム開始関数のノードから着目しているノードまでのノード識別子の系列は、唯一の関数呼び出しの系列を表すことになる。逆に言えば、ノードの識別子は、唯一の関数呼び出しの系列を表すことを意味する。例えば、図４のノード識別子６は、ノード識別子１において図３（ａ）の文１１から関数ｓｕｂが呼び出され、次にノード識別子２において図３（ａ）の文２５から関数ｐｒｏｃが呼び出され、次にノード識別子６において図３（ｂ）の文５７から関数ｆｕｎが呼び出されると言うような、唯一の関数呼び出しの系列を表すことを表す。
【００５８】
以下では、関数呼び出しの系列のことをコンテキストと言い、ノード識別子をコンテキストまたはコンテキスト情報とも言うことにする。
【００５９】
なお、関数呼び出しが再帰呼び出しや、相互呼び出しになっている場合は、その先の関数呼び出しに関してはノード生成を行わない。
・サブコールグラフ
コールグラフにおいて、あるノードに着目した時、着目しているノード以下（有向辺の向く方向）のグラフをサブコールグラフと言う。また、着目しているノードをサブグラフの頂点ノードと言う。例えば、図４では、ノード識別子が２のノードを頂点ノードとするサブコールグラフは、ノード識別子が２、６、７、８と、それ以下のノードとそれを結ぶ有向辺となる。
【００６０】
また、呼び出し関数名が同じであるノードを頂点ノードとする任意のサブコールグラフは、ノード数が同じで、かつ有向辺の数も向きも同じである（以下、同形である言う）ことは自明である。さらに、頂点ノード以外のノードは、呼び出し関数名、文識別子が同じである。例えば、図４では、ノード識別子２と４の呼び出し関数名がともにｐｒｏｃであり、識別子２を頂点ノードとするサブグラフと、識別子４を頂点ノードとするサブグラフは同形となっている。また、頂点ノードであるノード識別子２と４のノードを除く、ノード識別子６、７、８とノードの識別子９、１０、１１はそれぞれ対応して、呼び出し関数名と文識別子が同じである。
・コンテキスト情報付き文
コンテキスト情報付き文とは、同一の関数が複数の箇所から呼び出されるとき、呼出し毎に異なる文であることを表現するものである。コンテキスト情報付き文により、コンテキストセンシティブなデータフローの解析が可能となる。例えば、図３（ａ）において、関数ｐｒｏｃは文２５および文２７の２ヶ所から呼ばれており、それぞれの呼び出しは図４のコールグラフではノードの識別子２と４に対応している。つまり、図３（ａ）において、関数ｐｒｏｃの呼び出し文２５のコンテキストは２、文２７のコンテキストは４となる。
【００６１】
そして、”文識別＜コンテキスト＞”によりコンテキスト情報付き文を表現する。例えば図３（ｂ）の関数ｐｒｏｃの中の文５１は、コンテキスト情報付きの文として、５１＜２＞および５１＜４＞として表現され、それぞれ、関数ｐｒｏｃの呼び出し文２５から呼ばれた場合の文５１、および関数ｐｒｏｃの呼び出し文２７から呼ばれた場合の文５１として区別することが可能となる。
【００６２】
＜構成＞
図１は、実施の形態に係るデータ依存解析支援装置１００の構成を示すブロック図である。
【００６３】
データ依存解析支援装置１００は、例えば、パーソナルコンピュータで実現される。
【００６４】
データ依存解析支援装置１００は、中間プログラム生成部２００と、中間プログラム記憶部２０１と、コールグラフ生成部２０２と、コールグラフ記憶部２０３と、ポインタ解析部２０４と、ポインタ情報記憶部２０５と、データフロー解析部２０６と、データフロー情報記憶部２０７と、文間依存解析部２０８と、文間依存情報記憶部２０９と、領域間依存生成部２１０と、領域間依存情報記憶部２１１と、領域間依存表示部２１２と、外部記憶部１０と、入力部４０と、出力部５０とを備える。
【００６５】
外部記憶部１０は、例えば、ハードディスクで実現され、ソースプログラム１１を保持する。
【００６６】
入力部４０は、例えば、キーボードやマウスで実現され、解析対象領域を指定するための情報やスレッド化領域を指定するための情報を含むユーザ入力情報４１の入力を受け付ける。
【００６７】
中間プログラム生成部２００は、非特許文献１に記載されている一般のコンパイラの構文解析技術を用いて、外部記憶部１０に格納されているソースプログラム１１を読み込み、中間プログラムを生成し、生成した中間プログラムを中間プログラム記憶部２０１に格納する。
【００６８】
中間プログラム記憶部２０１は、中間プログラム生成部２００で生成された中間プログラムを保持する。
【００６９】
中間プログラム生成部２００で生成される中間プログラムは、ファイル情報、関数情報、文情報、および関数・文が記載されているソースプログラムファイル中の行番号の情報を含む。また、中間プログラム生成部２００で生成される中間プログラムは、非特許文献１の第６章に記載されている中間プログラムのその他の特徴を含んでいてもよい。
【００７０】
コールグラフ生成部２０２は、中間プログラム記憶部２０１に格納されている中間プログラムを読み込み、全ての関数呼び出しを抽出してコンテキストセンシティブなコールグラフを生成し、コールグラフ記憶部２０３に格納する。
【００７１】
コールグラフ記憶部２０３は、コールグラフ生成部２０２で生成されたコールグラフを保持する。
【００７２】
ポインタ解析部２０４は、中間プログラム記憶部２０１に格納されている中間プログラムと、コールグラフ記憶部２０３に格納されているコールグラフとを読み込み、中間プログラム全体に渡って、コンテキストセンシティブなポインタ解析を行い、解析結果をポインタ情報記憶部２０５に格納する。
【００７３】
ポインタ情報記憶部２０５は、ポインタ解析部２０４で解析されたコンテキストセンシティブなポインタ解析の結果を保持する。
【００７４】
ここで、ポインタ情報は、ポインタが記述されている文（コンテキスト情報付き）と、ポインタと、ポインタが指し示す被ポインタ変数の集合（以下、被ポインタ変数集合と言う）とを一組にしたものである。ポインタ情報記憶部２０５は、ソースプログラム１１に用いられている全てのポインタについてのポインタ情報を保持する。
【００７５】
データフロー解析部２０６は、中間プログラム記憶部２０１に格納されている中間プログラムと、ポインタ情報記憶部２０５に格納されているコンテキストセンシティブなポインタ情報と、コールグラフ記憶部２０３に格納されているコールグラフと、入力部４０から入力されるユーザ入力情報４１とを読み込む。そして、データフロー解析部２０６は、ユーザ入力情報４１に含まれる解析対象領域情報から得られる解析対象領域に対して、コンテキストセンシティブなデータフロー解析を行い、解析結果をデータフロー情報記憶部２０７に格納する。
【００７６】
データフロー情報記憶部２０７は、データフロー解析部２０６で解析されたコンテキストセンシティブなデータフロー解析の結果を保持する。
【００７７】
文間依存解析部２０８は、中間プログラム記憶部２０１に格納されている中間プログラムと、コールグラフ記憶部２０３に格納されているコールグラフと、データフロー情報記憶部２０７に格納されているコンテキストセンシティブなデータフロー情報とを読み込み、コンテキストセンシティブな文単位のデータ依存解析を行い、解析結果を、文間依存情報記憶部２０９に格納する。
【００７８】
文間依存情報記憶部２０９は、文間依存解析部２０８で解析されたコンテキストセンシティブな文間依存情報の解析結果を保持する。
【００７９】
ここで、文間依存情報は、依存元の文（コンテキスト情報付き）と依存先の文（コンテキスト情報付き）と依存の原因となっている変数（以下、起因変数と言う）とを一組にしたものであり、全ての文間依存情報が文間依存情報記憶部２０９に保持される。
【００８０】
領域間依存生成部２１０は、中間プログラム記憶部２０１に格納されている中間プログラムと、コールグラフ記憶部２０３に格納されているコールグラフと、文間依存情報記憶部２０９に格納されているコンテキストセンシティブな文間依存情報と、入力部４０から入力されるユーザ入力情報４１とを読み込む。そして、領域間依存生成部２１０は、ユーザ入力情報４１に含まれる領域指定情報からスレッド化領域を得て、スレッド化領域間に存在する文間依存情報を抽出し、領域間依存情報記憶部２１１に格納する。
【００８１】
領域間依存情報記憶部２１１は、領域間依存生成部２１０で生成された領域間の依存情報の結果を保持する。
【００８２】
ここで、スレッド化領域はユーザ入力情報４１の一部である領域指定情報で指定される。また、各々のスレッド化領域は解析対象領域の一部であり、同一の文が複数の異なるスレッド化領域に属することはない。このスレッド化領域は、キーボードからテキスト形式で行番号を入力、あるいはマウス等のポインティングデバイスにより直接ソースプログラム１１内の特定範囲を選択することにより指定される。
【００８３】
また、領域指定情報は、ファイル名と領域の開始行番号および領域の終了行番号より成る。
【００８４】
また、領域内に含まれる文とは、以下の文Ａ、文Ｂ、文Ｃのいずれかの条件に合う文のことである。
（１）領域指定情報のファイル名と領域内の開始行番号から領域の終了行番号の範囲内に存在する文Ａ。
（２）文Ａが関数Ｆの関数呼び出し文である場合は、関数Ｆ中に存在する文Ｂ。
（３）文Ａが関数Ｆの関数呼び出し文である場合は、関数Ｆの呼び出しによって呼び出される可能性のある全ての関数の中に存在する文Ｃ。
【００８５】
なお、「関数Ｆの呼び出しによって呼び出される可能性のある関数」とは、関数Ｆによって呼び出される関数、およびそのような関数からさらに呼び出される関数のことを指す。この場合において「呼び出される関数」とは、必ず呼び出される関数だけでなく、特定の条件を満たせば呼び出されるなど、呼び出される経路が１つ以上存在する関数も含まれる。
【００８６】
さらに、領域間依存情報は、依存元の領域と依存元の文（コンテキスト情報付き）と、依存先の領域と依存先の文（コンテキスト情報付き）と、起因変数とを一組にしたものであり、全ての領域間依存情報が領域間依存情報記憶部２１１に保持される。
【００８７】
領域間依存表示部２１２は、外部記憶部１０に格納されているソースプログラム１１と、中間プログラム記憶部２０１に格納されている中間プログラムと、コールグラフ記憶部２０３に格納されているコールグラフと、領域間依存情報記憶部２１１に格納されている領域間の依存情報とを読み込み、出力部５０に領域間の依存情報を出力する。
【００８８】
出力部５０は、例えば、ディスプレイで実現され、領域間の依存情報を表示する。
【００８９】
図２は、図１のデータフロー解析部２０６と、データフロー情報記憶部２０７との構成を示すブロック図である。
【００９０】
データフロー解析部２０６は、ポインタ情報結合部２２０と、定義情報生成部２２２と、使用情報生成部２２４と、到達定義情報生成部２２６とを備える。またデータフロー情報記憶部２０７は、結合ポインタ情報記憶部２２１と、定義情報記憶部２２３と、使用情報記憶部２２５と、到達定義情報記憶部２２７とを備える。
【００９１】
ポインタ情報結合部２２０は、中間プログラム記憶部２０１に格納されている中間プログラムと、コールグラフ記憶部２０３に格納されているコンテキストセンシティブなコールグラフと、ポインタ情報記憶部２０５に格納されているコンテキストセンシティブなポインタ情報と、入力部４０から入力されるユーザ入力情報４１とを読み込む。そして、ポインタ情報結合部２２０は、ユーザ入力情報４１に含まれる解析対象領域情報から得られる領域全てを含む関数を頂点ノードとするサブコールツリーを基に、サブコールツリーに関連するポインタ情報を結合し、結合結果を結合ポインタ情報記憶部２２１に格納する。
【００９２】
結合ポインタ情報記憶部２２１は、ポインタ情報結合部２２０で結合されたポインタ情報を保持する。
【００９３】
定義情報生成部２２２は、中間プログラム記憶部２０１に格納されている中間プログラムと、コールグラフ記憶部２０３に格納されているコンテキストセンシティブなコールグラフと、結合ポインタ情報記憶部２２１に格納されている結合ポインタ情報とを読み込み、どのような関数呼び出しの下で各文において定義される変数が何であるかを示すコンテキストセンシティブな定義情報を生成し、生成結果を定義情報記憶部２２３に格納する。
【００９４】
定義情報記憶部２２３は、定義情報生成部２２２で生成されたコンテキストセンシティブな定義情報を保持する。
【００９５】
使用情報生成部２２４は、中間プログラム記憶部２０１に格納されている中間プログラムと、コールグラフ記憶部２０３に格納されているコンテキストセンシティブなコールグラフと、結合ポインタ情報記憶部２２１に格納されている結合ポインタ情報とを読み込み、どのような関数呼び出しの下で各文において使用される変数が何であるかを示すコンテキストセンシティブな使用情報を生成し、生成結果を使用情報記憶部２２５に格納する。
【００９６】
使用情報記憶部２２５は、使用情報生成部２２４で生成されたコンテキストセンシティブな使用情報を保持する。
【００９７】
到達定義情報生成部２２６は、中間プログラム記憶部２０１に格納されている中間プログラムと、コールグラフ記憶部２０３に格納されているコンテキストセンシティブなコールグラフと、定義情報記憶部２２３に格納されているコンテキストセンシティブな定義情報とを読み込み、どのような関数呼び出しの下で各文に到達可能な文が何であるかを示すコンテキストセンシティブな到達定義情報を生成し、生成結果を到達定義情報記憶部２２７に格納する。
【００９８】
到達定義情報記憶部２２７は、到達定義情報生成部２２６で生成されたコンテキストセンシティブな到達定義情報を保持する。
【００９９】
ここで、到達可能な文とは、非特許文献１に記載されているように、ある文Ａで定義される変数をｘとしたとき、文Ａからある文Ｂに至る複数の実行経路において、文Ａ以外には変数ｘを定義する文が存在しない経路が一つでもあるとき、すなわち、変数ｘを定義する文が文Ａのみである経路が存在するとき、文Ａは文Ｂに到達可能な文であると言う。
【０１００】
＜動作＞
以下では、データ依存解析支援装置１００の動作を説明する。
【０１０１】
図５から図７は、データ依存解析支援装置１００によるデータ依存解析支援処理の動作を示すフローチャートである。
【０１０２】
図５を用いてデータ依存解析支援装置１００の動作の概要を説明する。
【０１０３】
データ依存解析支援装置１００は中間プログラム生成部２００を起動する。中間プログラム生成部２００は外部記憶部１０からソースプログラム１１を読み込み、中間プログラムを生成して中間プログラム記憶部２０１に格納する（Ｓ１０）。
【０１０４】
次に、データ依存解析支援装置１００はコールグラフ生成部２０２を起動する。コールグラフ生成部２０２は、中間プログラム記憶部２０１に格納されている中間プログラムを読み込み、中間プログラムから全ての関数呼び出しを抽出してコンテキストセンシティブなコールグラフを生成し、生成したコールグラフをコールグラフ記憶部２０３に格納する（Ｓ２０）。
【０１０５】
次に、データ依存解析支援装置１００は、ポインタ解析部２０４を起動する。ポインタ解析部２０４は、中間プログラム記憶部２０１に格納されている中間プログラムを読み込み、中間プログラム全体に渡って、コンテキストセンシティブなポインタ解析を行い、生成したポインタ情報をポインタ情報記憶部２０５に格納する（Ｓ３０）。
【０１０６】
次に、データ依存解析支援装置１００は、入力部４０から入力されるユーザ入力情報４１を読み込み、ユーザ入力情報４１にシステムの終了指示が含まれる場合はシステムを終了し、そうでない場合はユーザ入力情報４１に含まれる解析対象領域情報を参照する（Ｓ４０）。
【０１０７】
次に、データ依存解析支援装置１００は、解析対象領域情報を新たに得たか、または更新されている場合はＳ６０に進み、前回の解析実行時から更新されていない場合はＳ８０に進む（Ｓ５０）。
【０１０８】
次に、データ依存解析支援装置１００は、データフロー解析部２０６を起動し、中間プログラム記憶部２０１に格納されている中間プログラムと、ポインタ情報記憶部２０５に格納されているコンテキストセンシティブなポインタ情報と、入力部４０から入力されるユーザ入力情報４１とを読み込み、ユーザ入力情報４１に含まれる解析対象領域情報から得られる解析対象領域と、解析対象領域が実行された時に呼び出される可能性のある全ての文に渡って、コンテキストセンシティブなデータフロー解析を行う（Ｓ６０）。
【０１０９】
ここで、データ依存解析支援装置１００は、ポインタ情報結合部２２０、定義情報生成部２２２、使用情報生成部２２４、到達定義情報生成部２２６の順に起動する。
【０１１０】
図６は、ポインタ情報結合部２２０の動作を示すフローチャートである。
【０１１１】
まず、ポインタ情報結合部２２０は、ユーザ入力情報４１に含まれる解析対象領域情報から、解析対象領域全体を含む関数の関数名Ｆを読み込む（Ｓ６１）。
【０１１２】
次に、ポインタ情報結合部２２０は、コールグラフのノードの呼び出し関数名がＦであるノードを取り出す（Ｓ６２）。
【０１１３】
次に、ポインタ情報結合部２２０は、Ｓ６２で取り出したノードを頂点ノードとするサブコールグラフを取り出す（Ｓ６３）。前述したように、ここで取り出されるサブコールグラフが複数ある場合、それらのサブコールグラフは全て互いに同形である。
【０１１４】
次に、ポインタ情報結合部２２０は、Ｓ６３で取り出したサブコールグラフの頂点ノードのノード識別子（コンテキスト）と、ポインタ情報の文に付加されているコンテキスト情報が同じであるポインタ情報を取り出す（Ｓ６４）。
【０１１５】
次に、ポインタ情報結合部２２０は、Ｓ６４で取り出したポインタ情報のうち、文と変数が同じであるポインタ情報同士を結合する（Ｓ６５）。ここで「ポインタ情報を結合する」とは、文に付加されているコンテキスト情報と、被ポインタ変数の集合を結合させることである。
【０１１６】
次に、ポインタ情報結合部２２０は、Ｓ６３で取り出したサブコールグラフの頂点ノード以外のノードについて、ノードの関数呼び出し文が同じであるノードを取り出し、そのノードの識別子を取り出す（Ｓ６６）。
【０１１７】
次に、ポインタ情報結合部２２０は、Ｓ６６で取り出したノードの識別子（コンテキスト）と、ポインタ情報の文に付加されているコンテキスト情報が同じであるポインタ情報を取り出す（Ｓ６７）。
【０１１８】
次に、ポインタ情報結合部２２０は、Ｓ６７で取り出したポインタ情報のうち、文とポインタが同じであるポインタ情報同士を結合する（Ｓ６８）。
【０１１９】
これらの動作により、Ｓ６３で取り出された同形の複数のサブコールグラフに係るポインタ情報が、１つのサブコールグラフに係るポインタ情報として再構成される。解析対象領域のみをデータフロー解析の対象とするので、データフロー解析においては、取り出されたサブコールグラフの頂点ノードの識別子を同じものと見なしてよいからである。
【０１２０】
ポインタ情報が結合された後、定義情報生成部２２２、使用情報生成部２２４、到達定義情報生成部２２６は、コンテキスト情報付き文を用いて、コンテキストセンシティブな中間プログラム解析を行い、変数がどの文で定義されているのかを示す定義情報、変数がどの文で使用されているのかを示す使用情報、文が到達可能であるかどうかを示す到達定義情報を生成する。
【０１２１】
次に、データ依存解析支援装置１００は、文間依存解析部２０８を起動し、中間プログラム記憶部２０１に格納されている中間プログラムと、コールグラフ記憶部２０３に格納されているコールグラフと、定義情報記憶部２２３に格納されている定義情報と、使用情報記憶部２２５に格納されている使用情報と、到達定義情報記憶部２２７に格納されている到達定義情報とを読み込み、コンテキストセンシティブな文単位のデータ依存解析を行う（Ｓ７０）。次に、データ依存解析支援装置１００は、Ｓ９０に進む。
【０１２２】
ここで、解析対象領域情報が前回の解析実行時から更新されていない場合（Ｓ５０でＮＯ）、データ依存解析支援装置１００は、入力部４０から入力されるユーザ入力情報４１を読み込み、ユーザ入力情報４１に含まれる領域指定情報が更新されている場合は、Ｓ９０に進み、更新されていない場合は、Ｓ４０に進む（Ｓ８０）。
【０１２３】
領域指定情報が更新されている場合（Ｓ８０でＹＥＳ）、データ依存解析支援装置１００は、領域間依存生成部２１０を起動し、文間依存情報記憶部２０９に格納されているコンテキストセンシティブな文間依存情報と、入力部４０から入力されるユーザ入力情報４１とを読み込み、ユーザ入力情報４１に含まれる領域指定情報から得られる領域に対して、領域間に存在する領域間依存情報を生成する（Ｓ９０）。
【０１２４】
図７は、領域間依存生成部２１０の動作を示すフローチャートである。
【０１２５】
領域間依存生成部２１０は、ユーザ入力情報４１に含まれる領域指定情報から領域情報を読み込む（Ｓ９１）。
【０１２６】
次に、領域間依存生成部２１０は、Ｓ９１で取得した領域内に含まれる文を取り出す（Ｓ９２）。
【０１２７】
次に、領域間依存生成部２１０は、Ｓ９２で取り出した文が、依存元および依存先の文となっている文間依存情報を取り出す（Ｓ９３）。依存元の文と依存先の文は、Ｓ９２で取り出した文であれば良いので、依存元の文と依存先の文が同一の文であっても良いし、異なる文であってもよい。
【０１２８】
次に、領域間依存生成部２１０は、Ｓ９３で取り出した文を含む文間依存情報の依存元の文が、ある領域１に含まれ、依存先の文がある領域２に含まれている場合、領域１から領域２への領域間依存情報を生成する（Ｓ９４）。このとき、領域１と領域２とは異なる領域である。依存元の文と依存先の文が同じ領域に含まれている場合、当該文間依存情報を領域間依存情報に加えない。
【０１２９】
次に、データ依存解析支援装置１００は、領域間依存表示部２１２を起動する。領域間依存表示部２１２は、外部記憶部１０に格納されているソースプログラム１１と、中間プログラム記憶部２０１に格納されている中間プログラムと、コールグラフ記憶部２０３に格納されているコールグラフと、領域間依存情報記憶部２１１に格納されている領域間の依存情報とを読み込み、出力装置５０に領域間の依存情報を表示する（Ｓ１００）。
【０１３０】
次に、データ依存解析支援装置１００は、Ｓ１００を終了後、Ｓ４０に進む。
【０１３１】
＜具体例＞
以下では、図１のソースプログラム１１が図３に示すプログラムである場合のデータ依存解析支援装置１００の動作を、図５から図７に示すフローチャートを用いて説明する。
【０１３２】
データ依存解析支援装置１００は、中間プログラム生成部２００を起動し、中間プログラム生成部２００は、外部記憶部１０からソースプログラム１１を読み込み、中間プログラムに変換し、中間プログラム記憶部２０１に格納する（Ｓ１０）。
【０１３３】
図３のソースプログラム１１に対する中間プログラムに含まれている、文に関する情報を図８に示す。図８には文識別子と、文が存在するファイルのファイル名およびファイル中の行番号の情報が示されている。例えばＬ１００の行は、図３の文１１の関数ｓｕｂの関数呼び出しを示しており、文識別子が１１、ファイルのファイル名がｒｅｉ．ｃの行番号１０に存在することを示している。
【０１３４】
次に、データ依存解析支援装置１００は、コールグラフ生成部２０２を起動し、コールグラフ生成部２０２は、コンテキストセンシティブなコールグラフを生成する（Ｓ２０）。前述の通り、図３のソースプログラム１１に対して図４に示されるコールグラフが生成される。
【０１３５】
次に、データ依存解析支援装置１００は、ポインタ解析部２０４を起動し、ポインタ解析部２０４は、中間プログラム記憶部２０１に格納されている中間プログラムを読み込み、中間プログラム全体に渡って、コンテキストセンシティブなポインタ解析を行う（Ｓ３０）。
【０１３６】
図３のソースプログラム１１に対するポインタ情報を図９に示す。ポインタ情報には、コンテキスト情報付き文と、ポインタおよび被ポインタ変数集合の情報が含まれる。例えば図９のＬ２０３の行は、図３（ｂ）の文５１かつコンテキストが４の文において、ポインタｒの指す変数がｙであることを示している。
【０１３７】
データ依存解析支援装置１００は、入力部４０から入力されるユーザ入力情報４１を読み込み、ユーザ入力情報４１に含まれるシステム終了情報がシステムの終了を要求する入力であるか否かを判定する（Ｓ４０）。
【０１３８】
システム終了情報を図１６（ａ）に示す。データ依存解析支援装置１００は、システム終了情報がＥＮＤのときシステムを終了し、ＣＯＮＴＩＮＵＥのときはシステムの実行を継続する。ここでは、システム終了情報がＣＯＮＴＩＮＵＥであるので、システムの実行を継続する。
【０１３９】
次に、データ依存解析支援装置１００は、ユーザ入力情報４１に含まれる解析対象領域情報を参照し、解析対象領域情報が新たに取得されたか、または更新されている場合は、処理をＳ６０に進め、更新されていない場合は処理をＳ８０に進める。（Ｓ５０）
解析対象領域情報を図１６（ｂ）に示す。ここでは、ファイル名ｐｒｏｃ．ｃのファイルの行番号１に存在する関数名ｐｒｏｃ関数全体を解析対象領域として指定している。
【０１４０】
次に、データ依存解析支援装置１００は、データフロー解析部２０６を起動し、ユーザ入力情報４１に含まれる解析対象領域情報から得られた解析対象領域である関数ｐｒｏｃと、この関数ｐｒｏｃが実行された時に呼び出される可能性のある全ての文に渡って、コンテキストセンシティブなデータフロー解析を行う（Ｓ６０）。
【０１４１】
以下、データフロー解析部２０６に関してさらに詳しく説明する。
【０１４２】
データ依存解析支援装置１００は、データフロー解析部２０６においてポインタ情報結合部２２０を起動し、ポインタ情報結合部２２０は、解析対象領域情報から解析対象領域全体を含む関数の関数名を読み込む（Ｓ６１）。ここで、解析対象領域は関数ｐｒｏｃ全体であるから、解析対象領域全体を含む関数は、当然に関数ｐｒｏｃである。
【０１４３】
次に、ポインタ情報結合部２２０は、コールグラフのノードの呼び出し関数名が関数ｐｒｏｃであるノード識別子２と４のノードを取り出す（Ｓ６２）。
【０１４４】
次に、ポインタ情報結合部２２０は、ステップＳ６２で取り出したノード識別子２と４のノードを頂点ノードとするサブコールグラフを取り出す（Ｓ６３）。
【０１４５】
次に、ポインタ情報結合部２２０は、Ｓ６３で取り出したサブコールグラフの頂点ノードのノード識別子（コンテキスト）と、ポインタ情報の文に付加されているコンテキスト情報が同じであるポインタ情報を取り出す（Ｓ６４）。
【０１４６】
図４に示されるコールグラフにおける頂点ノードのノード識別子２から図９のポインタ解析情報のＬ２００、Ｌ２０１の行が取り出される。また、同様にノード識別子４から図９のＬ２０２、Ｌ２０３の行が取り出される。
【０１４７】
次に、ポインタ情報結合部２２０は、Ｓ６４で取り出したポインタ情報のうち、文と変数が同じであるポインタ情報同士を結合する（Ｓ６５）。
【０１４８】
結合後のポインタ解析情報を図１０に示す。Ｌ３００の行は、図９から取り出したＬ２００の行とＬ２０２の行を結合したものであり、Ｌ３０１の行は、図９から取り出したＬ２０１の行とＬ２０３の行を結合したものである。
【０１４９】
次に、ポインタ情報結合部２２０は、サブコールグラフの頂点ノード以外のノードについて、ノードの関数呼び出し文が同じであるノードを取り出し、そのノードの識別子を取り出す（Ｓ６６）。
【０１５０】
図４における、ノード識別子２を頂点ノードとするサブコールグラフからは、ノード識別子６、７、８が取り出され、ノード識別子４を頂点ノードとするサブコールグラフからは、ノード識別子９、１０、１１が取り出される。
【０１５１】
次に、ポインタ情報結合部２２０は、ステップＳ６６で取り出したノードの識別子（コンテキスト）と、ポインタ情報の文に付加されているコンテキスト情報が同じであるポインタ情報を取り出す（Ｓ６７）。
【０１５２】
ノード識別子６から、図９のポインタ解析情報のＬ２０４、Ｌ２０５、Ｌ２０６の行が取り出される。同様にノード識別子７から、図９のＬ２０７、Ｌ２０８、Ｌ２０９の行が取り出され、ノード識別子９から、図９のＬ２１０、Ｌ２１１、Ｌ２１２の行が取り出され、ノード識別子１０から、図９のＬ２１３、Ｌ２１４、Ｌ２１５の行が取り出される。
【０１５３】
ノード識別子８および１１については、図３（ｂ）の文７０においてポインタの使用がないので、図９にはコンテキストが８および１１が付いた文情報は存在しない。
【０１５４】
次に、ポインタ情報結合部２２０は、ステップＳ６７で取り出したポインタ情報のうち、文とポインタが同じであるポインタ情報同士を結合する（Ｓ６８）。
【０１５５】
結合後のポインタ解析情報を図１０に示す。Ｌ３０２の行は、図９から取り出したＬ２０４の行とＬ２１０の行を結合したものであり、Ｌ３０３の行は、図９から取り出したＬ２０５の行とＬ２１１の行を結合したものであり、Ｌ３０４の行は、図９から取り出したＬ２０６の行とＬ２１２の行を結合したものである。さらに、Ｌ３０５の行は、図９から取り出したＬ２０７の行とＬ２１３の行を結合したものであり、Ｌ３０６の行は、図９から取り出したＬ２０８の行とＬ２１４の行を結合したものであり、Ｌ３０７の行は、図９から取り出したＬ２０９の行とＬ２１５の行を結合したものである。
【０１５６】
次に、データ依存解析支援装置１００は、データフロー解析部２０６において定義情報生成部２２２と、使用情報生成部２２４と、到達定義情報生成部２２６とを順番に起動し、ユーザ入力情報４１に含まれる解析対象領域に対して、コンテキストセンシティブなデータフロー解析を行う。
【０１５７】
図１１は定義情報であり、例えばＬ４００の行は、コンテキスト２および４において図３（ｂ）の文５１で変数ｅが定義されることを示す。
【０１５８】
図１２は使用情報であり、例えばＬ５００の行は、コンテキスト２および４において図３（ｂ）の文５１で変数ｘおよび変数ｙが使用されることを示す。
【０１５９】
図１３は到達定義情報であり、例えばＬ６０１の行は、コンテキスト２および４において図３（ｂ）の文５６に到達可能な文の中に、コンテキスト２および４における図３（ｂ）の文５１と文５２、および、コンテキスト６、９における図３（ｃ）の文１０１があることを示す。
【０１６０】
ここで、文５６に到達可能な文の中に、コンテキスト６、９における図３（ｃ）の文１０１が含まれるが、理由は以下の通りである。まず、図３（ｂ）の文５７の関数ｆｕｎの呼び出し時に、変数ｅのアドレスが、図３（ｃ）の文１００のポインタｐに引き渡され、図３（ｃ）の文１０１においてポインタｐの間接参照により変数ｅが定義される。次に、ｆｏｒループによって文５７の実行後、図３（ｂ）の行番号７に制御が進むが、図３（ｂ）の行番号１１（不図示）から行番号４０（不図示）の間には、変数ｅを定義する文は存在しない。結果として、図３（ｃ）の文１０１で定義された変数ｅの値が図３（ｂ）の文５６において変数ｅに保持されているからである。
【０１６１】
次に、データ依存解析支援装置１００は、文間依存解析部２０７を起動し、文間依存解析部２０７は、コンテキストセンシティブな文単位のデータ依存解析を行う（Ｓ７０）。
【０１６２】
文間の依存解析情報を図１４に示す。例えば、Ｌ７１１の行は次のようにして求められたものである。まず、図１３のＬ６０３の行から図３（ｂ）のコンテキスト２および４における文６１に到達可能な文として、コンテキスト６および９における図３（ｃ）の文１０１を取り出し、次に、図１１の定義情報のＬ４０８の行において、コンテキスト６および９における文１０１が定義する変数に変数ｅがあることを見つけ出し、次に、図１２の使用情報のＬ５０３の行において、コンテキスト２および４における文６１の使用変数に変数ｅがあることを見つけ出す。結果、起因変数を変数ｅとした、コンテキスト６および９における文１０１から、コンテキスト２および４における文６１へ依存が求められる。これは、（１）文１で変数ｘが定義され、（２）文２で変数ｘが使用され、（３）文１が文２に到達可能である、の３条件の全てを満たしていれば、文１から文２に変数ｘを起因変数とする依存が存在するからである。
【０１６３】
次に、データ依存解析支援装置１００はＳ９０に進むが、ここで領域指定情報について説明する。
【０１６４】
領域指定情報を図１６（ｃ）に示す。図１６（ｃ）において、領域名は領域の名前を、ファイル名は領域が指定されるファイルの名前を、範囲は行番号で領域の範囲をそれぞれ示したものである。例えばＬ９０１は領域の名前がＲ１、ファイル名がｐｒｏｃ．ｃ、範囲が行番号８から行番号１９までであることを示している。その他のＬ９０２、Ｌ９０３も同様である。
【０１６５】
この領域指定は、テキストで入力されてもよいし、マウスにより指定されてもよい。例えば、図１７（ａ）はテキストで入力される場合の例であり、Ｒ１、Ｒ２、Ｒ３が領域名、ｐｒｏｃ．ｃがファイル名、ｒａｎｇｅが範囲を示している。また、図１７（ｂ）は、マウスにより指定される場合であり、マウスのドラッグ動作により直接ソースプログラム１１上で３個の領域Ｒ１、Ｒ２、Ｒ３を指定する例を示している。
【０１６６】
次に、データ依存解析支援装置１００は、領域間依存生成部２１０を起動し、領域間依存生成部２１０は、ユーザ入力情報４１に含まれる領域指定情報から得られる領域に対して、領域間に存在する領域間依存情報を生成する（Ｓ９０）。
【０１６７】
以下、領域間依存生成部２１０の動作に関してさらに詳しく説明する。
【０１６８】
領域間依存生成部２１０は、ユーザ入力情報４１に含まれる領域指定情報から領域情報を読み込む（Ｓ９１）。前述のように、図１６（ｃ）が領域情報である。
【０１６９】
次に、領域間依存生成部２１０は、Ｓ９１で取得した領域内に含まれる文を取り出す（Ｓ９２）。
【０１７０】
図１６（ｃ）のＬ９０１の領域Ｒ１に関しては次の通りとなる。ファイルｐｒｏｃ．ｃの行番号８から行番号１９の中に含まれる文は、図３（ｂ）の文５６、５７である。さらに、前述した通り、領域に含まれる文には呼び出される関数中の文も含まれるので、図３（ｃ）の文１００、１０１、１０２も領域Ｒ１に含まれる。同様に図１６（ｃ）のＬ９０２の領域Ｒ２に含まれる文は、図３（ｂ）の文６１、６５、６６と、図３（ｃ）の文１００、１０１、１０２である。また、同様に図１６（ｃ）のＬ９０３の領域Ｒ３に含まれる文は、図３（ｂ）の文７０と、図３（ｃ）の文２０１である。
【０１７１】
次に、領域間依存生成部２１０は、Ｓ９２で取り出した文が、依存元および依存先の文となっている文間依存情報を取り出す（Ｓ９３）。
【０１７２】
例えば、図１４のＬ７０４の行は、依存元が文５７、依存先が文６１であり、いずれもＳ９２で取り出した文に含まれているので、対象の文間依存情報として取り出される。同様に、図１４のＬ７０５、Ｌ７０６、Ｌ７０７、Ｌ７１０、Ｌ７１１、Ｌ７１２、Ｌ７１３、Ｌ７１４の各行が取り出される。
【０１７３】
次に、領域間依存生成部２１０は、Ｓ９３で取り出した文を含む文間依存情報の依存元の文が、領域１に含まれ、依存先の文が領域２に含まれている場合、領域１から領域２への領域間依存情報を生成する（Ｓ９４）。
【０１７４】
図１５は領域間依存情報である。例えば、Ｌ８０１の行は、図１４のＬ７０４の行から生成されたものである。つまり、図１４のＬ７０４の行の依存元の文が文５７であり領域Ｒ１に含まれており、かつ依存先の文が文６１であり領域Ｒ２に含まれているので、領域間の依存として取り出され、さらに、領域情報を追加した領域間依存情報が生成されている。図１５の他の行についても同様であり、Ｌ８０２、Ｌ８０３、Ｌ８０４、Ｌ８０５の各行は、それぞれ図１４のＬ７０５、Ｌ７１１、Ｌ７０７、Ｌ７０９より生成されたものである。一方、例えば、図１４のＬ７０６の行は、依存元の文である文６１と依存先の文である文６６がともに同一の領域Ｒ２に含まれるので、領域間依存情報としては取り出されない。
【０１７５】
次に、データ依存解析支援装置１００は、領域間依存表示部２１２を起動し、領域間依存表示部２１２は、出力装置５０に領域間の依存情報を表示する（Ｓ１００）。
【０１７６】
図１８に、領域間依存表示の例を示す。図１８（ａ）はテキストによる領域間依存情報の表示例である。例えば、”Ｆｒｏｍ：Ｒ１，  ｐｒｏｃ．ｃ，  １０  −＞  Ｔｏ：  Ｒ２，  ｐｒｏｃ．ｃ，  ２１  ：Ｃｖ：  ｓ”は、領域Ｒ１のファイルｐｒｏｃ．ｃの行番号１０から、領域Ｒ２のファイルｐｒｏｃ．ｃの行番号２１に、変数ｓを原因とする依存があることを示している。この情報は、図１５の領域間依存情報と図８の文情報から求められる。例えば、図１５のＬ８０１の行において、依存元の文は文５７であり、図８のＬ１０９の行から、文５７の存在場所である、ファイルｐｒｏｃ．ｃの行番号１０の情報を取り出し、同様に、図１５のＬ８０１の依存先の文は文６１から、図８のＬ１１０からファイルｐｒｏｃ．ｃの行番号２１の情報を取り出すことにより表示している。
【０１７７】
また、図１８（ｂ）および（ｃ）はソースプログラム１１上に領域間依存情報を表示する例である。図１８（ｂ）および（ｃ）は、図１５のＬ８０３の行の領域間依存の表示の例を示している。図１５のＬ８０３の行において、依存元の文は文１０１であり、図８のＬ１０８の行から、文１０１の存在場所、ファイルｃｍｎ．ｃの行番号１０の情報を取り出し、同様に、依存先の文である文６１からは、ファイルｐｒｏｃ．ｃの行番号２１の情報を取り出す。次に、依存元のファイルｃｍｎ．ｃを表示するウィンドウを開き、行番号１０番を強調する（図１８（ｂ））。さらに、依存先のファイルｐｒｏｃ．ｃを表示するウィンドウを開き、行番号２１番を強調する（図１８（ｃ））。図１５の他の領域間依存についても同様である。但し、依存元および依存先のファイルが同じ場合は、同一のウィンドウ内で依存元および依存先の行番号を強調してもよい。
【０１７８】
次に、データ依存解析支援装置１００は、Ｓ４０に進む。
【０１７９】
データ依存解析支援装置１００は、Ｓ４０において、ユーザ入力情報４１にシステムの終了要求がない間、Ｓ４０からＳ１００を繰り返して実行する。
【０１８０】
データ依存解析支援装置１００は、Ｓ５０で解析対象領域に変更がある場合は、新たな解析対象領域に対してデータフロー解析を行い、領域間依存情報を算出する。この時、Ｓ３０で生成したポインタ情報を再利用するので解析時間を節約できる。
【０１８１】
さらに、データ依存解析支援装置１００は、Ｓ５０で解析対象領域に変更がない場合は、Ｓ８０に進み、さらにＳ８０で領域の更新があった場合、つまり、同じ解析対象領域に関して、異なる領域に対して領域間依存情報を算出する場合は、Ｓ６０およびＳ７０で算出したデータフロー情報および文間依存情報を再利用するので解析時間を節約できる。つまり、ユーザが指定した、様々な領域に関して、領域間依存情報を素早く表示できることが可能となる。
【０１８２】
＜データ依存解析後ソースプログラムのスレッド並列化実施例＞
前述したように、データ依存解析支援装置１００により、図３のソースプログラム１１に対して、図１７に示した領域を設定した場合は、図１８の示した領域間依存情報が得られる。以下では、得られた領域間依存情報の有用性を示すために、図３のソースプログラム１１のスレッド化の例について説明する。
【０１８３】
図１９は図３のプログラムをＯｐｅｎＭＰの記述形式でスレッド化した例である。図１９（ａ）に示すように、プログラム中のＳＴ１、ＳＴ２、ＳＴ３において、”＃ｐｒａｇｍａ  ｏｍｐ  ｓｅｃｔｉｏｎ”と記述することにより３つの領域をスレッド化することが可能である。
【０１８４】
また、図１９（ａ）のＳＴ４の”ｂｕｆｆｅｒ＿ｘ”（ｘはｓ、ｅ、またはａ）は、起因変数ｘ毎にスレッド間のデータ授受のために設けたデータである。例えば、ｂｕｆｆｅｒ＿ｓは、図１５のＬ８０１およびＬ８０２の行の起因変数ｓに対応して設けたデータである。
【０１８５】
さらに、図１９（ａ）におけるＳＴ５のスレッド１中の”ｂｕｆｆｅｒ＿ｓ＿ｓｅｎｄ（ｓ）”の動作は、ｂｕｆｆｅｒ＿ｓに変数ｓの値を送信することであり、ＳＴ６のスレッド２中の”ｂｕｆｆｅｒ＿ｓ＿ｒｅｃｅｉｖｅ（ｓ）”の動作は、ｂｕｆｆｅｒ＿ｓから変数ｓへ値を受信することである。つまり、ｂｕｆｆｅｒ＿ｓ＿ｓｅｎｄ（ｓ）およびｂｕｆｆｅｒ＿ｓ＿ｒｅｃｅｉｖｅ（ｓ）が、領域間に挿入される通信コードとなる。
【０１８６】
なお、図１９（ａ）のＳＴ７に示す通り、ソースプログラム１１をスレッド化した後では、変数ｓは、各スレッドにローカルな変数として宣言されている。つまり、変数ｓはスレッド毎に用意されるため、スレッドを並列に実行する場合に、複数のスレッドから変数ｓへの書き込み競合や、他のスレッドからの変数ｓへの書き込みによる不正な値の参照がないことが保障される。
【０１８７】
他の領域間依存情報に関しても同様にスレッド化に利用される。
【０１８８】
図１９（ｂ）のｂｕｆｆｅｒ．ｈは、通信コードであるＢｕｆｆｅｒクラスの詳細なプログラムの例である。ユーザはスレッド並列化したプログラムからｂｕｆｆｅｒ．ｈをヘッダファイルとしてインクルードすればよく、ソースプログラム１１ごとに異なるヘッダファイルを準備したり、上記挿入される通信コード”ｂｕｆｆｅｒ＿ｘ＿ｓｅｎｄ（ｘ）”、”ｂｕｆｆｅｒ＿ｘ＿ｒｅｃｅｉｖｅ（ｘ）”（ｘは変数名）以外にソースプログラム１１にコードを追加したりする必要はない。
【０１８９】
以上の方法により、ユーザは領域間依存情報を基に容易にスレッド並列化プログラムを作成することが可能である。
【０１９０】
≪補足≫
以上、本発明に係るデータ依存解析支援装置を、実施の形態に基づいて説明したが、本発明は上述した実施の形態のみに限定されないことは勿論である。
【０１９１】
（１）本実施の形態では、解析対象領域情報および領域指定情報は、入力部４０から入力されるユーザ入力情報４１から取り出されるとしているが、本発明は必ずしもこの場合に限定されない。例えば、ソースプログラム１１中に記述された注釈、予め決められたキーワード、または特定の記号などの情報から取り出してもよい。
【０１９２】
例えば、図２０は図３（ｂ）のソースプログラム１１に対して、解析対象領域情報と領域指定情報を”ｐｒａｇｍａ”により記述した例である。図２０のＳＴ１１は解析対象領域情報の例であり、ａｎａｌｙｚｅ＿ｆｕｎｃｔｉｏｎの後に関数名を指定することで、関数ｐｒｏｃ全体が解析対象領域であることを示す。また図２０のＳＴ１２、ＳＴ１３、ＳＴ１４は、領域指定するものであり、”＃ｐｒａｇｍａ  ｒｅｇｉｏｎ  領域名｛．．．｝”により｛．．．｝の内容が「領域名」を持つスレッド化領域であることを指定している。
【０１９３】
（２）本実施の形態では、解析対象領域が領域Ｒ１、Ｒ２およびＲ３の全てを含む一つの関数ｐｒｏｃ全体である場合について説明したが、本発明は必ずしもこの場合に限定されない。例えば、図３のソースプログラム１１と領域Ｒ１、Ｒ２およびＲ３とに対して、領域の全てを含み、かつ領域に係る繰り返し等の制御構造全体を含む「ファイルｐｒｏｃ．ｃの第７行から第４０行」を解析対象領域としてユーザが指定してもよい。このようにすることで、解析対象領域から、領域間依存情報の解析に無関係な文を含まないようにすることができる。なお、このとき解析対象領域に含まれる文のコンテキストが２または４であり、コンテキスト２または４の呼び出し元であるコンテキスト１の文が解析対象領域に含まれないことから、ポインタ情報結合部２２０は、取り出すべきサブコールグラフの頂点ノードの識別子が２と４であることを取得できる。
【０１９４】
（３）本実施の形態では、文間依存情報生成部２１０が解析対象領域内の全ての依存情報を文間依存情報として生成し、領域間依存情報生成部２１２が文間依存情報から領域間に係る依存情報を領域間依存情報として生成する場合について説明したが、本発明は必ずしもこの場合に限定されない。例えば、文間依存情報生成部２１０と文間依存情報記憶部２１１がなく、領域間依存情報生成部２１２が定義情報記憶部２２３から変数の定義情報、使用情報記憶部２２５から変数の使用情報、到達定義情報記憶部２２７から到達定義情報、入力装置４０からユーザ入力情報４１に含まれる領域指定情報をそれぞれ得て、直接領域間依存情報を生成するものとしてもよい。
【０１９５】
（４）本実施の形態では、領域間依存情報として、依存元の文、依存元の文が存在する領域、依存先の文、依存先の文が存在する領域、起因変数が含まれる場合について説明したが、本発明は必ずしもこの場合に限定されない。例えば、領域間依存情報として、依存元の文が存在する領域、依存先の文が存在する領域、起因変数のみが含まれるものとしてもよい。このようにすることで、領域をスレッド並列化するための通信コードを生成するために必要十分な情報を得ることができる。
【０１９６】
（５）本実施の形態では、ポインタ情報結合部２２０が、ポインタ情報記憶部２０５が保持するポインタ情報を結合して結合ポインタ情報記憶部２２１に格納する場合について述べたが、本発明は必ずしもこの場合に限定されない。例えば、ポインタ情報結合部２２０と結合ポインタ情報記憶部２２１がなく、定義情報生成部２２２、使用情報生成部２２４、到達定義情報生成部２２６がポインタ情報記憶部２０５から直接ポインタ情報を得るものとしてもよい。このとき、定義情報、記憶情報および到達定義情報の生成時に変数を結合してもよいし、あるいは文間依存情報または領域間依存情報の生成時に変数を結合してもよい。
【０１９７】
（６）本実施の形態では、ソースプログラム１１をスレッド並列化するため領域間のデータ依存解析を行う場合について述べたが、本発明は必ずしもこの場合に限定されない。例えば、非特許文献１の第９章に記載されているようなソースプログラム１１の最適化を関数間にまたがって実施するために、本発明においてデータフロー情報記憶部２０７に格納されるデータフロー情報を利用してもよい。このようにすることで、本発明に係るデータ依存解析支援装置において、スレッド並列化以外のプログラム最適化方法を用いることが可能となり、ソースプログラム１１の高速化に奏功する。
＜まとめ＞
以下に、実施の形態に係るデータ依存解析支援装置とデータ依存解析支援プログラム、およびデータ依存解析支援方法の構成および効果について説明する。
【０１９８】
（１）実施の形態に係るデータ依存解析支援装置は、ソースプログラムに対してコンテキストセンシティブなデータ依存解析を行うデータ依存解析支援装置であって、前記ソースプログラムで使用される全てのポインタに対して、コンテキストセンシティブなポインタ解析を行い、ポインタ情報を生成するポインタ情報生成部と、前記ソースプログラムの一部であって、２以上のスレッド化領域の間に存在するデータ依存を解析するために指定される解析対象領域に対して、前記ポインタ情報を用いて、コンテキストセンシティブなデータフロー解析を行い、データフロー情報を生成するデータフロー情報生成部と、前記データフロー情報を用いて、前記２以上のスレッド化領域の間に存在するデータ依存について、依存元のスレッド化領域と、依存先のスレッド化領域と、依存の原因である変数とを示す領域間依存情報を生成する領域間依存情報生成部とを備えることを特徴とする。
【０１９９】
また、実施の形態に係るデータ依存解析支援プログラムは、ソースプログラムに対するコンテキストセンシティブなデータ依存解析をコンピュータに実行させるデータ依存解析支援プログラムであって、前記コンテキストセンシティブなデータ依存解析は、前記ソースプログラムで使用される全てのポインタに対して、コンテキストセンシティブなポインタ解析を行い、ポインタ情報を生成するポインタ情報生成ステップと、前記ソースプログラムの一部であって、２以上のスレッド化領域の間に存在するデータ依存を解析するために指定される解析対象領域に対して、前記ポインタ情報を用いて、コンテキストセンシティブなデータフロー解析を行い、データフロー情報を生成するデータフロー情報生成ステップと、前記データフロー情報を用いて、前記２以上のスレッド化領域の間に存在するデータ依存について、依存元のスレッド化領域と、依存先のスレッド化領域と、依存の原因である変数とを示す領域間依存情報を生成する領域間依存情報生成ステップとを含むことを特徴とする。
【０２００】
また、実施の形態に係るデータ依存解析支援方法は、ソースプログラムに対してコンテキストセンシティブなデータ依存解析を行うデータ依存解析支援方法であって、前記ソースプログラムで使用される全てのポインタに対して、コンテキストセンシティブなポインタ解析を行い、ポインタとポインタが指し示す変数との対応情報であるポインタ情報を生成するポインタ情報生成ステップと、前記ソースプログラムの一部であって、２以上のスレッド化領域の間に存在するデータ依存を解析するために指定される解析対象領域に対して、前記ポインタ情報を用いて、コンテキストセンシティブなデータフロー解析を行い、データフロー情報を生成するデータフロー情報生成ステップと、前記データフロー情報を用いて、前記２以上のスレッド化領域の間に存在するデータ依存について、依存元のスレッド化領域と、依存先のスレッド化領域と、依存の原因である変数とを示す領域間依存情報を生成する領域間依存情報生成ステップとを含むことを特徴とする。
【０２０１】
これら上記の構成によれば、データ依存解析支援装置は、データ依存解析の一部の処理であるデータフロー解析をソースプログラム全体ではなく解析対象領域に対してのみ行うことにより解析時間を短縮でき、またデータ依存解析の一部の処理であるポインタ解析とデータフロー解析とについてコンテキストセンシティブな解析を行うので高精度にスレッド化領域間の依存情報を得ることができ、高精度の解析と解析時間の短縮の両立が可能となる。
【０２０２】
（２）また、実施の形態に係る上記（１）のデータ依存解析支援装置は、前記解析対象領域は、前記２以上のスレッド化領域の全てを含む、単一の関数と前記単一の関数により呼び出される関数との集合である、としてもよい。
【０２０３】
このようにすることで、データ依存解析支援装置は、スレッド化領域間の依存情報を得るための解析対象領域がスレッド化領域を解析するために不十分であることを防ぐことができ、かつ解析対象領域を関数名で指定することができるので解析対象領域の指定を簡易に行うことが可能になる。
【０２０４】
（３）また、実施の形態に係る上記（１）のデータ依存解析支援装置は、前記データフロー情報生成部は、前記解析対象領域を含む単一の関数と、前記関数より呼び出される関数とで使用されるポインタについて、前記単一の関数を１つのコンテキストとして前記ポインタ情報を結合し結合ポインタ情報を生成する、としてもよい。
【０２０５】
このようにすることで、データ依存解析支援装置は、解析対象領域についてデータフロー解析を行う際に、解析対象領域の外から解析対象領域に含まれる関数への呼び出しについて、ポインタ情報における当該関数のコンテキストを１つにまとめることにより、ポインタ情報の情報量の削減とともに、不必要なデータフロー解析を回避して解析時間を短縮することが可能である。
【０２０６】
（４）また、実施の形態に係る上記（１）のデータ依存解析支援装置は、前記解析対象領域を指定するための情報の入力を受け付ける解析対象領域指定部をさらに備える、としてもよい。
【０２０７】
このようにすることで、データ依存解析支援装置は、解析対象領域が指定される際にソースプログラムを取得し直す必要がなく、簡易な操作で同一のソースプログラムを連続してデータ依存解析することができる。
【０２０８】
（５）また、実施の形態に係る上記（１）のデータ依存解析支援装置は、前記スレッド化領域を指定するための情報の入力を受け付ける領域指定部をさらに備える、としてもよい。
【０２０９】
このようにすることで、データ依存解析支援装置は、スレッド化領域に関する情報のみを簡易に取得することが可能になり、簡易な操作で同一のソースプログラムの同一の解析対象領域に対してデータ依存解析を行うことができる。
【０２１０】
（６）また、実施の形態に係る上記（１）のデータ依存解析支援装置は、前記領域間依存情報を出力する領域間依存情報出力部をさらに備える、としてもよい。
【０２１１】
このようにすることで、データ依存解析支援装置は、データ依存解析の結果をユーザに好適な方法で提示することができ、ソースプログラムの並列化の支援に奏功する。
【０２１２】
（７）また、実施の形態に係る上記（１）のデータ依存解析支援装置は、前記データフロー情報生成部は、前記ポインタ情報生成部が同一のソースプログラムに対するポインタ情報を保持している場合に、前記保持されているポインタ情報を用いてデータフロー情報を生成する、としてもよい。
【０２１３】
このようにすることで、同一のソースプログラムの異なる解析対象領域についてデータ依存解析を行う場合に、既に生成が行われているポインタ情報を再利用してデータフロー解析と領域間依存情報生成を行えばよく、解析時間の短縮が可能である。
【０２１４】
（８）また、実施の形態に係る上記（１）のデータ依存解析支援装置は、前記領域間依存情報生成部は、前記データフロー解析部が同一の解析対象領域に対するデータフロー情報を保持している場合に、前記保持されているデータフロー情報を用いて領域間依存情報を生成する、としてもよい。
【０２１５】
このようにすることで、同一の解析対象領域についてデータ依存解析を行う場合に、既に生成が行われているデータフロー情報を再利用して領域間依存情報生成を行えばよく、解析時間の短縮が可能である。
【産業上の利用可能性】
【０２１６】
本発明に係るデータ依存解析支援装置は、コンテキストセンシティブな領域間依存情報を参照して、領域レベルでのソースプログラムの並列化を実施したり、コンテキストセンシティブなデータフロー情報を参照して、ソースプログラムの改善を実施するために利用したりすることができる。
【符号の説明】
【０２１７】
１００  データ依存解析支援装置
１０    外部記憶部
１１    ソースプログラム
４０    入力部
４１    ユーザ入力情報
５０    出力部
２００  中間プログラム生成部
２０１  中間プログラム記憶部
２０２  コールグラフ生成部
２０３  コールグラフ記憶部
２０４  ポインタ解析部
２０５  ポインタ情報記憶部
２０６  データフロー解析部
２０７  データフロー情報記憶部
２０８  文間依存解析部
２０９  文間依存情報記憶部
２１０  領域間依存生成部
２１１  領域間依存情報記憶部
２１２  領域間依存表示部
２２０  ポインタ情報結合部
２２１  結合ポインタ情報記憶部
２２２  定義情報生成部
２２３  定義情報記憶部
２２４  使用情報生成部
２２５  使用情報記憶部
２２６  到達定義情報生成部
２２７  到達定義情報記憶部
【図１】
2013105158.tif 000003
【図２】
2013105158.tif 000004
【図３】
2013105158.tif 000005
【図４】
2013105158.tif 000006
【図５】
2013105158.tif 000007
【図６】
2013105158.tif 000008
【図７】
2013105158.tif 000009
【図８】
2013105158.tif 000010
【図９】
2013105158.tif 000011
【図１０】
2013105158.tif 000012
【図１１】
2013105158.tif 000013
【図１２】
2013105158.tif 000014
【図１３】
2013105158.tif 000015
【図１４】
2013105158.tif 000016
【図１５】
2013105158.tif 000017
【図１６】
2013105158.tif 000018
【図１７】
2013105158.tif 000019
【図１８】
2013105158.tif 000020
【図１９】
2013105158.tif 000021
【図２０】
2013105158.tif 000022
【国際調査報告】
2013105158.tif 000023
2013105158.tif 000024