(57)【特許請求の範囲】
【請求項１】
記憶装置に記憶されたプログラムを読み出して当該プログラムの解析と解析結果の出力を行うコンピュータシステムであって、
解析対象プログラムから中間語を生成し記憶装置に出力する構文解析手段と、
記憶装置から上記中間語を読み出し該中間語に基づき階層的制御フローグラフを生成して記憶装置に出力する階層的制御フローグラフ作成手段と、
ユーザによる上記解析対象プログラム上の解析対象ループと解析対象参照点の指定を受け付け、受け付けた指定内容に対応して解析対象ファイルを生成して記憶装置に出力する解析対象指定手段と、
記憶装置から上記解析対象ファイルおよび上記階層的制御フローグラフを読み出し、上記解析対象ファイルで示される解析対象を上記階層的制御フローグラフに書き込み、解析対象ループから解析対象参照点に至る呼び出し手続列を表す解析対象リストを生成して記憶装置に出力する解析対象入力手段と、
記憶装置から上記階層的制御フローグラフを読み出し、解析対象参照点を含む文へ分岐するノードおよび解析対象参照点を含む文から分岐するノードで、最も内側にあるループ入口以外のノードと分岐に対応するエッジを検出し、該エッジに制御フローが通過しないように第１のフラグを立てて記憶装置に出力する最内分岐解析手段と、
記憶装置から上記階層的制御フローグラフを読み出し、各ノードが解析対象参照点を含むか否かを解析し、解析対象参照点の内、上記第１のフラグで通過しないことを指定した解析対象参照点を含まないノードに第２のフラグを立てて記憶装置に出力する包含関係解析手段と、
記憶装置から上記解析対象リストと上記第１，第２のフラグを立てた階層的制御フローグラフを読み出し、ユーザ指定の解析対象参照点を接続する制御フローを解析し、該制御フローを制御フローリストとして記憶装置に出力すると共に、該制御フローリストを入力して、当該制御フロー上のプログラム中の文もしくはプログラムスライスを解析し、解析結果を文情報ファイルとして記憶装置に出力する制御フロー解析手段と、
記憶装置から上記文情報ファイルと上記解析対象プログラムとを読み出して入力し、表示装置の画面において、上記文情報ファイルにおける文情報を上記解析対象プログラム上で強調表示する文情報表示手段と
を有することを特徴とするプログラム解析システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、プログラム中の、指定された文や参照点などに対する解析情報を出力する技術に係わり、特に、並列コンピュータ用プログラムのチューニングの高効率化等に好適な技術に関するものである。
【０００２】
【従来の技術】
並列コンピュータの性能を引き出すためには、プログラムのチューニングが必要であるが、このチューニングには手作業が必要であり時間がかかる。例えば、ループ並列化のチューニングにおいては、変数・配列のプライベート化が重要となっているが、このためのプログラム解析は特に難しい。
【０００３】
このような並列化コンピュータ用のプログラムのチューニングに係わる従来技術としては、例えば、シー  ウェイ  リィアオ、アマー  ダイワン、  ロバートピー  ボッシュ  ジュニア、アンワォー  ギュロウム、  モニカ  エス  ラム著の「スイフ  エクスプローラー：アン  インターラクティブ  アンド  インタープロシージュアル  パラレライザー」（ピーピーオーピーピー９９、第３７頁から第４８頁、１９９９）（Shih-Wei Liao, Amer Diwan, Robert P. Bosch Jr., Anwar Ghuloum, Monica S. Lam, SUIF Explorer: An Interactive and Interprocedural Parallelizer, PPoPP '99, pp. 37-48, 1999）で論じられているものがある。
【０００４】
この技術では、コンパイラが、プログラム上のループ中の２つの配列参照間にデータ依存関係があるか否か決定できず、そのためループ並列化ができない場合、システムにおいて対象プログラムを解析し、それらの配列添字の値に影響を与える文（「プログラムスライス」）を表示し、ユーザはこれをもとに上記ループの並列性調査をしていた
【０００５】
しかし、この場合、ユーザは、表示されたプログラムスライスを目で追いながら、ループ並列化対象変数のプライベート化の必要性と可能性等を調査しなければならず、調査対象のプログラムが複雑な制御フローを持つものであれば、ユーザの負荷か大きく、調査に時間もかかり、また、間違いを引き起こしやすいとの問題があった。
【０００６】
【発明が解決しようとする課題】
解決しようとする問題点は、従来の技術では、ループ並列化の調査用の情報として、システムは、プログラムスライスのみしか表示することができない点である。
【０００７】
本発明の目的は、これら従来技術の課題を解決し、ユーザの、対象変数のプライベート化判定等に要する時間を削減することを可能とすることである。
【０００８】
【課題を解決するための手段】
上記目的を達成するため、本発明では、記憶装置に記憶されたプログラムを読み出して当該プログラムの解析と解析結果の出力を行う際、解析対象として指定されたループのループ入口とこのループ内で定義される変数の定義点および使用点のいずれか一つから、ループのループ出口および変数の定義点と使用点のいずれか一つへ到達する制御フローを検出し、検出した制御フローからループの繰り返しをまたがらない制御フローを抽出し、抽出した制御フロー上の文情報を、プログラム実行順もしくは逆順で、ファイルに、もしくは、表示装置画面上でソースプログラム上に強調表示等して出力する。このように出力した情報は、「対象変数の定義点が実行される」および「対象変数の使用点が実行されるとき、同じループイタレーション内でその実行より前にその変数の定義点が実行される」といったプライベート化の可否判定の条件を示しており、ユーザの当該情報の調査負荷が軽減される。
【０００９】
【発明の実施の形態】
以下、本発明の実施の形態を、図面により詳細に説明する。
【００１０】
図１は、本発明に係わるプログラム解析システムの構成例を示すブロック図であり、図１４は、図１におけるプログラム解析システムの解析対象となるプログラムの指定操作例を示す説明図、図２０は、図１におけるプログラム解析システムの図１４のプログラムに対応する解析結果例を示す説明図である。
【００１１】
図１におけるプログラム解析システムは、ＣＰＵ（Central Processing Unit）や主メモリ、表示装置、入力装置、外部記憶装置からなるコンピュータシステムであり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣＰＵで処理する内容が、各処理部の機能として実現される。
【００１２】
すなわち、本例のプログラム解析システムは、解析処理部１００と解析対象指定部１９１、情報表示部１９２の各処理部からなり、解析処理部１００は、さらに、構文解析部１１０と階層的制御フローグラフ作成部１２０、解析対象入力部１３０、最内分岐解析部１４０、および、包含フラグ設定部１５１と通過フラグ設定部１５２からなる包含関係解析部１５０、そして、制御フロー解析部１６０により構成されている。
【００１３】
このような構成により、本例のプログラム解析システムでは、図１４の入力プログラム表示画面１４０１に示すループプログラムの解析指示に対応して、当該プログラムを解析し、その解析結果として、図２０に示すようにして、所定の文情報を表示装置の画面上に強調表示する。
【００１４】
すなわち、プログラム解析システムでは、プライベート化に関しての解析指定がなされたプログラムの解析および解析結果の出力を行う際、解析対象のループ、および、ループ内の変数の定義点と使用点に対する識別情報を入力し、解析対象ループのループ入口と変数の定義点および使用点のいずれか１つから、ループ出口と変数の定義点および使用点のいずれか１つへ到達し、かつ、解析対象ループの繰り返しをまたがらない制御フローを検出・抽出し、検出・抽出した制御フロー上の文情報を、ファイルに出力、または、ソースプログラム上で強調表示する。
【００１５】
例えば、解析対象ループのループ入口から変数の定義点および使用点の内の一方を通らずに他方へ到達する制御フロー、または、変数の定義点および使用点の内の一方から他方を通らずに解析対象ループのループ出口に到達する制御フローを検出・抽出し、その文情報をプログラム実行順またはその逆順に表示・出力する。
【００１６】
尚、変数の定義点あるいは使用点における配列添字またはスカラ変数に対する、検出・抽出した制御フローに沿うプログラムスライスを文情報とする。もしくは、変数の定義点あるいは使用点における配列添字またはスカラ変数に対するプログラムスライスと、検出・抽出した制御フローとの交わりを文情報とする。
【００１７】
このようにして、プログラム解析システムでは、ループ入口点からある変数の定義点へ至るループ独立な制御フロー上の文、または、その制御フローに沿ったプログラムスライスを、あるいは、ループ入口点からある変数の定義点を通らずにその変数の使用点へ至るループ独立な制御フロー上の文、または、その制御フローに沿ったプログラムスライスを、プログラム実行順または逆順に表示する。
【００１８】
この表示では、「対象変数の定義点が実行される」という条件、および、「対象変数の使用点が実行される時、同じループイタレーション内で、その実行より前にその変数の定義点が実行される」という条件を表しており、これらの条件は、ユーザが、対象変数のプライベート化の必要性およびプライベート化可能性を調査する場合に用いるものであり、本例のプログラム解析システムによる表示により、ユーザはその条件を自分で調査する必要がなくなるので、負荷が軽減される。
【００１９】
以下、図１におけるプログラム解析システムの構成および動作の詳細を説明する。
【００２０】
図１において、解析対象指定部１９１は、外部記憶装置等に記憶された入力プログラム１８１を読み出して入力し、図１４に示す操作画面において、プログラム中の解析対象ループと解析対象参照点をユーザに指定させて解析対象ファイル１８２を出力する。
【００２１】
この解析対象ファイル１８２を含め、後述の中間語１７１、階層的制御グラフ１７２、解析対象リスト１７３、制御フローリスト１７４、文情報ファイル１８３のそれぞれは外部記憶装置に格納される。
【００２２】
解析処理部１００において、構文解析１１０は、入力プログラム１８１を入力して中間語１７１を生成して出力し、階層的制御フローグラフ作成部１２０は、中間語１７１を入力して階層的制御フローグラフ１７２を作成する。
【００２３】
また、解析対象入力部１３０は、解析対象ファイル１８２を入力し、解析対象を階層的制御フローグラフ１７２に書き込み、解析対象ループから解析対象参照点に至る呼び出し手続き列を表わす解析対象リスト１７３を生成して出力する。
【００２４】
また、最内分岐解析部１４０は、階層的制御フローグラフ１７２を入力して、解析対象参照点を含む文へ分岐するノードおよび解析対象参照点を含む文から分岐するノードで、最も内側にあるループ入口以外のノードと分岐に対応するエッジを検出し、それらのエッジに制御フローが通過しないようにフラグを立てる。
【００２５】
また、包含関係解析部１５０は、階層的制御フローグラフ１７２を入力して、各ノードが解析対象参照点を含むか否かを解析し、解析対象参照点のうち、通過しないことを指定した解析対象参照点を含まないノードにフラグを立てる。
【００２６】
また、制御フロー解析部１６０は、解析対象リスト１７３と階層的制御フローグラフ１７２を入力して、ユーザ指定の解析対象参照点を接続する制御フローを解析し、その制御フローを制御フローリスト１７４として出力し、さらに、その制御フローリスト１７４を入力して、当該制御フロー上のプログラム中の文またはプログラムスライスを解析し、その解析結果を文情報ファイル１８３に出力する。
【００２７】
そして、文情報表示部１９２は、このようにして解析処理部１００が格納した文情報ファイル１８３と入力プログラム１８１とを記憶装置から読み出して入力し、表示装置の画面において、解析処理部１００で得られた文情報を入力プログラム１８１上で強調表示する。
【００２８】
解析処理部１００における包含関係解析部１５０は、包含フラグ設定部１５１において、階層的制御フローグラフ１７２を入力して各ノードが解析対象参照点を含むか否かを表わすフラグを立て、通過フラグ設定部１５２において、解析対象参照点のうち、通過しないことを指定した解析対象参照点を含まないノードにフラグを立てる。
【００２９】
次に、このような構成のプログラム解析システムの動作および表示を、図２から図２０を用いて、具体的に説明する。
【００３０】
図１４においては、解析対象指定部１９１の具体的な操作例を示しており、この解析対象指定部１９１は、入力プログラム表示画面１４０１、解析対象行番号表示部１４０２、解析対象行表示部１４０３、文番号表示部１４０４からなる操作画面を表示する。入力プログラム表示画面１４０１に表示してあるのは入力プログラム１８１の具体例である。
【００３１】
ユーザが入力プログラム表示画面１４０１上で行番号「１１」、「１３」、「１７」に対応する３つの行を選択すると、その行番号と行（の文内容）が解析対象行番号表示部１４０２および解析対象行表示部１４０３に表示される。
【００３２】
ユーザが解析対象行表示部１４０３上で解析対象参照点１４０５を選択することによりそれ（「ｘ（ｊ）」）は強調表示される。また、ユーザは、項目欄１４０６における「start」、「skip」、「end」のそれぞれに各々文を指定することにより、「start」で示された文から「skip」で示された文を通過せずに「end」で示された文に至る制御フローを指定することができる。
【００３３】
尚、「skip」に対応する文は省略することができる。また、解析対象参照点（１４０５）の指定は制御フロー上のプログラムスライスを計算するためのものであり、単に制御フロー上の文のみを表示したい場合は、解析対象参照点（１４０５）の指定を省略することができる。
【００３４】
図１５は、図１における解析対象ファイルの内容例を示す説明図である。
【００３５】
本例は、図１４で示された内容に基づき図１の解析対象指定部１９１が出力した解析対象ファイル１８２の内容である。この図１５の内容を説明する前に解析対象ファイルのタグ構造とタグフォーマットを図９に基づき説明する。
【００３６】
図９は、解析対象ファイルのタグ構造例を示す説明図である。
【００３７】
図９に示す例では、全部で１４個のタグがある。各タグは記号「#」で始まり改行で終わる。対になって使用されるタグ同士は、図中、それらの間を左側の曲線で結んで表示している。
【００３８】
例えば、タグ９０１とタグ９１４は対になって使用される。対になって使用されるタグの一方は記号「#」で始まり、他方は記号「#/」で始まる。尚、図９では表示してないが、引数を伴うタグもある。また、記号「#/」で始まるタグは引数を持たない。
【００３９】
図１０は、図９における解析対象ファイルのタグフォーマット例を示す説明図である。
【００４０】
図１０（ａ）では、タグ毎のタグフォーマット１００１を示しており、「#LINE」の引数の[カラム]は参照点が指定された場合の、そのカラムを表わす。参照点が指定されない場合は省略される。
【００４１】
図１０（ｂ）では、図９におけるタグ「#KIND」９０３の引数である解析方法の種別１００２を示し、図１０（ｃ）および図１０（ｄ）では、図９におけるタグ「#LINE」９０５．９０８．９１１の引数である文種別１００３と対象種別１００４を示している。
【００４２】
次に図１５の説明に戻り、図１５において、行１５０１は解析対象ループを含む手続き名が「test」であることを示し、行１５０２は解析対象ループのDO文の文番号が１０であることを示している。
【００４３】
また、行１５０３は、解析方法の種別がタグ「ST」で示された文からタグ「SK」で示された文を通らずにタグ「EN」で示された文に至るものであることを示し、行１５０４〜１５０６は、開始の文が、手続き名「test」の行番号「１１」で文種別が手続き呼出し文やループ以外の文であり、解析対象であることを示す。
【００４４】
また、行１５０７〜１５１０は、ユーザが通らないことを指定した文の情報を示し、そのうちの行１５０８，１５０９は、その文を手続きやループを階層とみなした時の、上位の階層から下位の階層へ解析対象となる文に至るまでの文の列を示している。
【００４５】
ここで、行１５０８は、「DOループ」の「DO文」を示し、これは解析対象ではなく、解析対象の文の上位の階層にあるだけなので、タグの引数である対象種別は「NO」となる。また、行１５０９は解析対象であり、タグの引数である対象種別は「YES」となる。
【００４６】
また、行１５１１〜１５１４は、終了の文を示しており、これらも文の列となっている。
【００４７】
以上の、タグ「ST」（行１５０４〜１５０６）、タグ「SK」（行１５０７〜１５１０）、タグ「EN」（行１５１１〜１５１４）で示された文は、各々、図１４における欄１４０６の「start」、「skip」、「end」で示された文（１４０３）に対応している。
【００４８】
次に、この解析対象ファイル１８２を入力した図１の解析処理部１００における各処理部の動作を説明する。
【００４９】
構文解析部１１０は、図１４の入力プログラム表示画面１４０１に表示された入力プログラム１８１を入力し、中間語１７１を生成して出力する。ここで、中間語１７１は入力プログラムをツリー状に表現したものであるが、内容は入力プログラム１８１とほぼ同じであるので、以降の説明では入力プログラム表示画面１４０１に表示された入力プログラムを中間語１７１と見なす。
【００５０】
階層的制御フローグラフ作成部１２０は、中間語１７１を入力して、図１６に例示する階層的制御フローグラフ１７２を作成する。
【００５１】
図１６は、図１における階層的制御フローグラフの構造例を示す説明図である。
【００５２】
本図１６に示す階層的制御フローグラフ１７２は、図１４の入力プログラム表示画面１４０１に表示された入力プログラムを中間語１７１と見なし、この中間語を入力して作成されたものである。
【００５３】
階層的制御フローグラフ１７２のノードは、入口ノード（図１６では「Ｓ」と表示）、出口ノード（同「Ｅ」）、ループノード（同「ＬＯＯＰ」）、基本ブロックノード（同「ＢＢ」）、分岐ノード（同「ＢＲ」）、合流ノード（同「ＪＯＩＮ」）、手続き呼び出しノードからなる。また、各ノードは制御フローに従ったエッジで接続される。
【００５４】
このように、階層的制御フローグラフでは、ループおよび手続きを１つの階層とする。各階層は入口ノードから始まり、出口ノードで終わるバックエッジのない有向グラフである。ここで、バックエッジとは入口ノードのある方を向いたエッジのことである。図中の１６１０、１６２０、１６３０が各々、階層となる。
【００５５】
本図１６において、ループノード１６０１は、そのループボディに対応する階層１６１０と接続される。さらに、階層１６１０の中のループノード１６１４，１６１６には、各々のループボディに対応する階層１６２０，１６３０が接続される。
【００５６】
以降では、階層的制御フローグラフを略して「ＬＣＦグラフ」と呼び、その一つの階層を「部分ＬＣＦグラフ」と呼ぶ。また、ループノード１６０１を部分ＬＣＦグラフの中に含まれる任意のノードの上位ノード、逆に、部分ＬＣＦグラフの中に含まれる任意のノードをループノード１６０１の下位ノードと呼ぶ。
【００５７】
解析対象入力部１３０は、解析対象ファイル１８２を入力して解析対象を階層的制御フローグラフ１７２に書き込み、解析対象ループから解析対象参照点に至る呼び出し手続き列を表わす解析対象リスト１７３を作成して出力する。ｃ
【００５８】
図２は、図１における解析対象入力部の処理動作例を示すフローチャートである。
【００５９】
図１における解析対象入力部１３０では、まず、ステップ２０１において、図１５に示された解析対象ファイル１８２を入力し、次に、ステップ２０２において、図１５の解析対象ファイル１８２中で、タグ「ＳＴ」，「ＳＫ」，「ＥＮ」で示された参照点または文を「st」,「sk」,「en」で指し示す。そして、ステップ２０３において、図１７に示す内容の解析対象リスト１７３を作成する。
【００６０】
図１７は、図１における解析対象リストの構成例を示す説明図である。
【００６１】
本図の解析対象リスト１７３は、図１における解析対象入力部１３０の処理結果で得られたものである。上から順に、「st」,「sk」,「en」に対応する。ここで、リストを構成する各テーブルの各フィールドを図１３に基づき説明する。
【００６２】
図１３は、図１における解析対象リストのテーブル構成例を示す説明図である。
【００６３】
本図１３では、図１７に示した構成の解析対象リスト１７３のテーブルの各フィールドの内容を示しており、１３０１は次のテーブルへのポインタ、１３０２は直前のテーブルへのポインタを表わす。
【００６４】
また、１３０３はテーブルが表わす文の文番号、１３０４は文に対応するノードのノード種別を表わす。ノード種別は１３１０に示した４つである。そして、１３０５はＬＣＦグラフの対応するノードへのポインタである。
【００６５】
図１７において、各リストの開始テーブル１７０１，１７０３，１７０６は解析対象ループに対応する。よって、文番号は「１０」であり、ノード種別は「ＬＯＯＰ」となる。「st」,「sk」,「en」の開始テーブル以降のテーブルついても、リスト中の各テーブルの文番号は図１５の対応するタグの文番号に対応する。
【００６６】
次に、図２において、解析対象入力部１３０は、ステップ２０４で、解析対象リストからＬＣＦグラフlcfのノードへのポインタを張る。図１７における、解析対象ループに対応する各リストの開始テーブル１７０１，１７０３，１７０６では、ＬＣＦグラフのノード１６０１に対応する。
【００６７】
また、「st」,「sk」,「en」の開始テーブル以降のテーブルでは、ＬＣＦグラフへのポインタは、各々、図１７における１６１２、１６１４と１６２２、１６１６と１６３２に対応する。
【００６８】
そして、図２において、解析対象入力部１３０は、ステップ２０５で、ＬＣＦグラフlcfのノードにフラグを立てる。これらのフラグは、図１６では１６１２、１６２２、１６３２の横に「st」,「sk」,「en」と示している。
【００６９】
図１の最内分岐解析部１４０では、このような階層的制御フローグラフ１７２を入力し、解析対象参照点を含む文へ分岐するノード、および、解析対象参照点を含む文から分岐するノードで、最も内側にあるループ入口以外のノードと、分岐に対応するエッジを検出し、それらのエッジに制御フローが通過しないようにフラグを立てる。このような最内分岐解析部１４０の処理動作を図３に基づき説明する。
【００７０】
図３は、図１における最内分岐解析部の処理動作例を示すフローチャートである。
【００７１】
本例は図１の最内分岐解析部１４０の図１６に示す階層的制御フローグラフに基づく処理動作（アルゴリズム）例を示したものであり、まず、ステップ３０１は、図１６に示す階層的制御フローグラフにおいては「sk」が指定されているので、「Ｙ」となり、次のステップ３０２以降の処理に移る。
【００７２】
このステップ３０２では、「sk」を含むノード１６２２を「node」とし、ステップ３０３において、「node」１６２２を含むＬＣＦグラフ１６２０をlcfとする。そして、「node」１６２２は、lcf（ＬＣＦグラフ）１６２０内で、lcf１６２０の出口１６２３を支配しているので、ステップ３０４では「Ｙ」となる。
【００７３】
lcf（ＬＣＦグラフ）１６２０は、「st」も「en」も含まないので、ステップ３０５では「Ｎ」となり、ステップ３０８において、lcf（ＬＣＦグラフ）１６２０の上位ノードであるノード１６１４を「node」とする。
【００７４】
ステップ３０９において、lcf（ＬＣＦグラフ）１６２０は解析対象ループに対応してないので、「Ｎ」となり、ステップ３０３での処理に戻り、node１６１４を含む部分ＬＣＦグラフ１６１０をlcfとする。
【００７５】
次のステップ３０４においては、node１６１４は、lcf１６１０内でlcf１６１０の出口ノード１６１７を支配しないので、「Ｎ」となり、ステップ３１０およびステップ３１１での処理へ進む。
【００７６】
ステップ３１０では、node１６１４からlcf１６１０の入り口方向へたどって、node１６１４が後支配しない最初のノードを見つけ、そのノードとその直後のノードとの間のエッジに非通過フラグを立てる。図１６に示す例では、このステップ３１０での処理で得られるノードとエッジは１６１３と１６４０である。
【００７７】
また、ステップ３１１では、node１６１４からlcf１６１０の出口方向へたどって、node１６１４が支配しない最初のノードを見つけ、そのノードとその直前のノードとの間のエッジに非通過フラグを立てる。図１６に示す例では、このステップ３１１での処理で得られるノードとエッジは１６１５と１６５０である。以上のようにして、２つのエッジ１６４０，１６５０に非通過フラグを立てる。
【００７８】
尚、ステップ３０５において、lcf（ＬＣＦグラフ）が、「st」もしくは「en」を含む場合には、ステップ３０６の処理に進み、「sk」（もしくは「en」）が「st」（もしくは「sk」）より出口方向に有るか否かを判別し、無ければステップ３０７において、lcf（ＬＣＦグラフ）と解析対象ループの間にループが有るか否かを判別する。
【００７９】
ステップ３０６において「Ｙ」（「sk」もしくは「en」が「st」もしくは「sk」より出口方向に有る）、および、ステップ３０７において、「Ｎ」（lcfと解析対象ループの間にループが無い）であれば、あるいは、ステップ３０９において「Ｙ」（lcfは解析対象ループに対応した部分ＬＣＦフラグ）であれば、ステップ３１２での処理に進み、「条件を満たすパスは存在しない」と出力して本ツールでの処理を終了する。
【００８０】
このようにして作成された階層的制御フローグラフ１７２は、図１における包含関係解析部１５０に入力され、図４に示す処理が施される。
【００８１】
図１における包含関係解析部１５０は、包含フラグ設定部１５１と通過フラグ設定部１５２よりなる。包含フラグ設定部１５１は、図１および図１６における階層的制御フローグラフ１７２を入力して、各ノードが解析対象参照点を含むか否かを表わすフラグを立てる。この包含フラグ設定部１５１のアルゴリズムを図４に基づき説明する。
【００８２】
図４は、図１における包含フラグ設定部の処理動作例を示すフローチャートである。
【００８３】
本例では、プログラムスライスを求める最大範囲を解析対象ループとし、ステップ４００では、ＬＣＦの開始ノードとして解析対象ループのループボディに対応する部分ＬＣＦグラフの入口ノード１６１１を取る。以下、ノード１６１１に対して、処理Ａ（ステップ４０１〜４１１）を呼ぶ。
【００８４】
処理Ａでは、ノード１６１１は、ステップ４０３において「Ｙ」となり、ステップ４０８に進み、現階層（図１６における階層１６１０）内の全ノードに対して処理Ａを順に呼ぶ。
【００８５】
この処理において、次のノード１６１２は「st」を含むので、ステップ４０４において「Ｙ」となり、ステップ４０９の処理で、上位ノード１６０１の「st」フラグを「ＯＮ」にする。
【００８６】
次の分岐ノード１６１３はステップ４０１〜４０４のいずれにも該当せず、処理は行なわれない。次のループノード１６１４は、ステップ４０１において「Ｙ」となり、そのループ入口ノード１６２１に対して処理Ａを呼ぶ。
【００８７】
この入口ノード１６２１に対しては、ステップ４０３からステップ４０８に進み、その階層１６２０内の全ノードに対して処理Ａを呼ぶ。まず、ノード１６２２は「sk」を含むので、ステップ４０４からステップ４０９の処理に進み、その上位ノード１６１４に「sk」フラグを設定する。
【００８８】
次の出口ノード１６２３はステップ４０１〜４０４のいずれにも該当せず、処理は行なわれず、以上で、ステップ４０６でのループノード１６１４に対する処理が終了し、次のステップ４１１において、上位ノード１６０１の「sk」フラグを、現ノード１６１４の「sk」フラグによりＯＮに設定する。
【００８９】
ノード１６１４の次の合流ノード１６１５はステップ４０１〜４０４のいずれにも該当せず処理は行なわれない。
【００９０】
次のループノード１６１６に対しては、ループノード１６１４と同様の処理を行い、このループノード１６１６と上位のループノード１６０１に「en」フラグを設定する。
【００９１】
以上の処理により設定された「st」,「sk」,「en」フラグは、図１６において、ノード１６０１，１６１４，１６１６の横に下線をつけて表示している。
【００９２】
このような包含フラグ設定部１５１に対して通過フラグ設定部１５２は、解析対象参照点のうち、通過しないことを指定した解析対象参照点を含まないノードにフラグを立てる。以下、通過フラグ設定部１５２の処理動作を図５を用いて説明する。
【００９３】
図５は、図１における通過フラグ設定部の処理動作例を示すフローチャートである。
【００９４】
本図５では、図１の通過フラグ設定部１５２のアルゴリズムを説明するものであり、通過フラグ設定部１５２は、まず、ステップ５００において、ＬＣＦの開始ノードとして、解析対象ループのループボディに対応する部分ＬＣＦグラフの入口ノード（図１６におけるノード１６１１）を取り、このノード１６１１に対して処理Ｂを施す。
【００９５】
処理Ｂでは、ノード１６１１は、ステップ５０１において「Ｎ」、ステップ５０５において「Ｙ」となり、現階層１６１０内の全ノードに対して処理Ｂを呼ぶ（ステップ５０６）。
【００９６】
現階層１６１０内のノード１６１２，１６１３は共に、ステップ５０１，５０５のいずれでも「Ｎ」となり処理されない。次のノード１６１４は、ステップ５０１において「Ｙ」となる。そして、前述の包含フラグ設定部１５１の処理により、ノード１６１４には「sk」フラグが設定されているので、ステップ５０２において「Ｎ」となり、下位の階層の入口ノード１６２１に対して処理Ｂを呼ぶ（ステップ５０４）。
【００９７】
このノード１６２１は、ステップ５０１において「Ｎ」、ステップ５０５において「Ｙ」となり、現階層１６２０内の全ノードに対して処理Ｂを呼ぶ。しかし、現階層１６２０内のノード１６２２，１６２３は共に、ステップ５０１，５０５のいずれでも「Ｎ」となり処理されない。
【００９８】
階層１６２０の処理を終了し、上位階層１６１０の処理に戻り、まず、ノード１６１５は、ステップ５０１，５０５のいずれでも「Ｎ」となり処理されないが、次のノード１６１６はループノードであり、ステップ５０１において「Ｙ」となり、ステップ５０２においては、「sk」フラグは「ＯＦＦ」であり「Ｙ」となり、ステップ５０３において、ノード１６１６に通過フラグを設定する。
【００９９】
その後、ステップ５０４において、下位階層の入口ノード１６３１に対して処理Ｂを呼ぶが、ノード１６１４の場合と同様にして、下位階層に対する処理は行われない。
【０１００】
以上の処理により設定された通過フラグは、図１６において、ノード１６１６の横に下線をつけて「pass」と表示した。
【０１０１】
このようにして、包含フラグ設定部１５１および通過フラグ設定部１５２におりフラグが設定された階層的制御フローグラフは、図１の制御フロー解析部１６０に入力される。
【０１０２】
制御フロー解析部１６０は、階層的制御フローグラフ１７２と解析対象リスト１７３とを入力して、ユーザ指定の解析対象参照点を接続する制御フローを解析し、その制御フローを制御フローリスト１７４として出力し、再度、制御フローリスト１７４を入力してその制御フロー上のプログラム中の文またはプログラムスライスを解析し、その解析結果を文情報ファイル１８３に出力する。このような制御フロー解析部１６０を図６，７を用いて説明する。
【０１０３】
図６は、図１における制御フロー解析部の第１の処理動作例を示すフローチャートであり、図７は、図１における制御フロー解析部の第２の処理動作例を示すフローチャートである。
【０１０４】
これらの図６および図７は、図１における制御フロー解析部１６０のアルゴリズムを説明したものであり、ここでは、図１６に示す階層的制御フローグラフ１７２に関連する処理のみを説明する。
【０１０５】
制御フロー解析部１６０は、まず、図６のステップ６００において、「st」を含むノード（図１６におけるノード１６１２）に対して図７に示す処理Ｃを呼ぶ。このノード１６１２に関しては、図７のステップ７００において「Ｙ」となり、ステップ７２１において、図１６に示す次のノード１６１３に対して処理Ｃを呼ぶ。
【０１０６】
ノード１６１３は分岐ノードであり、ステップ７０５において「Ｙ」となり、ステップ７１６での処理に進む。このステップ７１６の処理においては、エッジ１６４０は非通過フラグが「ＯＮ」であり、合流ノード１６１５に向かうエッジが選択され、合流ノード１６１５に対して処理Ｃを呼ぶ。
【０１０７】
この合流ノード１６１５に関しては、ステップ７０６において「Ｙ」となり、ステップ７１７において、合流直前のノード１６１３中の最後の文である図１４の入力プログラム表示画面１４０１に表示されたプログラムにおける文番号「１１」の文の文番号を文番号として持ち、ノード種別が「ＪＯＩＮ」のテーブルを作成して、制御フローリスト（１７４）の最初のノードとし、次のノード１６１６に対して処理Ｃを呼ぶ。
【０１０８】
このノード１６１６はループノードであり、ステップ７０４において「Ｙ」となり、「sk」を含まないので、ステップ７１２では「Ｎ」となり、「en」を含むのでステップ７１３において「Ｙ」となり、制御フローリスト（１７４）に、現ループノード１６１６から「en」までの解析対象リスト（１７３）を追加する（ステップ７１４）。図１８に、この結果、得られた制御フローリストを示す。
【０１０９】
図１８は、図１における制御フローリストの構成例を示す説明図である。
【０１１０】
図１８において、１８０１は図７におけるステップ７１７での制御フロー解析部１６０による処理で作成されたテーブルであり、１８０２，１８０３は図７におけるステップ７１４での処理で作成されたテーブルである。これらの２つのテーブル１８０２，１８０３は、図１７におけるテーブル１７０７，１７０８と同じである。
【０１１１】
次に、こうして得られた制御フローリスト（１７４）に対して、ステップ７１５ａにおけるスライス解析を行う。このスライス解析について図８を用いて説明する。
【０１１２】
図８は、図７におけるスライス解析の詳細例を示すフローチャートである。
【０１１３】
本図８は、スライス解析のアルゴリズムを示したものであり、ステップ８０１において、図１８に示した制御フローリスト１７４のテーブル１８０１〜１８０３で表現された制御フローに沿ってプログラムスライスを解析する。
【０１１４】
このプログラムスライス解析の詳細は、シー  ウェイ  リィアオ、アマー  ダイワン、  ロバート  ピー  ボッシュ  ジュニア、アンワォー  ギュロウム、  モニカ  エス  ラム著「スイフ  エクスプローラー：アン  インターラクティブアンド  インタープロシージュアル  パラレライザー」（ピーピーオーピーピー９９、第３７頁から第４８頁、１９９９）（Shih-Wei Liao, Amer Diwan, Robert P. Bosch Jr., Anwar Ghuloum, Monica S. Lam, SUIF Explorer: An Interactive and Interprocedural Parallelizer, PPoPP '99, pp. 37-48, 1999）で論じられているので説明は省略する。
【０１１５】
プログラムスライスは、図１および図１５における解析対象ファイル１８２として指定された参照点を基点に解析する。図１５に示す解析対象ファイル１８２では、１５１３で「１７」行目で指定された図１４における参照点１４０５に対して解析される。
【０１１６】
次のステップ８０２においては、一連番号numを０から１だけ増加させ、「１」とする。そして、ステップ８０３において、numを一連番号とし、出力ファイルフォーマットに従って、プログラムスライス上の文の文番号を図１の文情報ファイル１８３に出力する。この文情報ファイル１８３について、図１１と図１２および図１９を用いて説明する。
【０１１７】
図１１は、図１における文情報ファイルのタグ構造例を示す説明図であり、図１２は、図１１の文情報ファイルにおけるタグフォーマット例を示す説明図、図１９は、図７におけるスライス解析で出力された文情報ファイルの構成例を示す説明図である。
【０１１８】
図１１に示すように、本例では、文情報ファイル１８３には、全部で４個のタグがある。各タグは記号「#」で始まり改行で終わる。対になって使用されるタグ同士は、図中、それらの間を左側の曲線で結んで表示している。例えば、タグ１１０１とタグ１１０３は対になって使用される。
【０１１９】
対になって使用されるタグの一方は記号「#」で始まり、他方は記号「#/」で始まる。尚、本図１１では表示してないが引数を伴うタグもある。記号「#/」で始まるタグは引数を持たない。
【０１２０】
図１１において、１１０２はタグからなる集合であり、それは１１０４〜１１０９で定義される。１１０２は、その定義において自分自身である１１０７を含んでいる。これにより、ある手続き中から別の手続きが呼び出されることを表現する。
【０１２１】
図１２において、１２０１はタグフォーマットをタグ毎に表示したものである。ここで、「#LINE」と「#CALL」は、１つの「#PROC」内では、行番号順にソートされる。「#CALL」直後には呼び出し先手続きの手続き情報「#PROC」が続く。また、「#LINE」が示す文の並びには「CALL」文は含まない。
【０１２２】
図１９に示す文情報ファイル１８３は、図１における制御フロー解析部１６０により、図７におけるステップ７１５ａ，７１８でのスライス解析処理で出力されるものである。
【０１２３】
図１９において、行１９０１〜１９０６の内、行１９０３は文番号「１１」からなる１つの文を、行１９０４は文番号「１５」から「１８」までの４つの連続した文の集まりを表わす。
【０１２４】
図１における文情報表示部１９２は、このような文情報ファイル１８３と入力プログラム１８１を入力し、図２０に示すようにして、解析処理部１００で得られた文情報を入力プログラム１８１上に表示する。
【０１２５】
図２０は、図１における文情報表示部による表示結果例を示す説明図である。
【０１２６】
本図２０に示す表示画面２０００の例では、図１９における内容で文情報ファイル１９２に出力された文が網掛け表示されている。これにより、ループ入口である文番号「１１」の文から、文番号「１３」の文を通過せずに、分番号「１７」に至る制御フローは唯一であり、その制御フロー上の文のプログラムスライスが網掛けで表示されることにより容易に判読することができる。
【０１２７】
尚、図２０の例では、全文を一度に表示しているが、文情報ファイル１８３には文が実行順に並べられているので、その順またはその逆順に表示することでも良い。
【０１２８】
以上のようにして、配列「x」に対して、ループの１イタレーションで、ループ入口から配列「x」の定義点を通らず、配列「x」の使用点に至る制御フローが示される。この制御フローは「ｉ」の値が「１」でも「５」でもない時に実行されるので、文番号「１０」において「m」の値が「２」以上なら、実行される。従って、この時、変数「x」に対してプライベート化は適用できないことがわかる。
【０１２９】
以上、図１〜図２０を用いて説明したように、本例のプログラム解析技術では、プログラム中の解析対象を指定する解析対象指定情報を入力してそれに対する解析情報を出力するコンピュータシステムにおいて、解析対象ループ、ある変数の定義点および使用点に対する識別情報を入力し、解析対象ループのループ入口、変数の定義点、および使用点のいずれか１つから、ループ出口、変数の定義点、および使用点のいずれか１つへ到達し、かつ、解析対象ループの繰り返しをまたがらない制御フローを検出・抽出し、この制御フロー上の文情報をファイルに出力、または、文情報をソースプログラム上で強調表示する。
【０１３０】
あるいは、解析対象ループのループ入口から変数の定義点および使用点の内の一方を通らずに他方へ到達する、または、変数の定義点および使用点の内の一方から他方を通らずに解析対象ループのループ出口に到達する制御フローを検出・抽出し、この制御フロー上の文情報をファイルに出力、または、文情報をソースプログラム上で強調表示する。
【０１３１】
尚、変数の定義点あるいは使用点における配列添字またはスカラ変数に対する、検出・抽出した制御フローに沿うプログラムスライスを文情報とする。もしくは、変数の定義点あるいは使用点における配列添字またはスカラ変数に対するプログラムスライスと、検出・抽出した制御フローとの交わりを文情報とし、このような文情報を、プログラム実行順またはその逆順に表示する。
【０１３２】
このことにより、ユーザは、プライベート化の第１条件「対象変数の定義点が実行される」を、プログラム中の少ない文を見ることで容易に検証することができるので、対象変数のプライベート化の必要性を知る時間を削減することができる。
【０１３３】
また、プライベート化の第２条件「対象変数の使用点が実行される時、同じループイタレーション内で、その実行より前にその変数の定義点が実行される」をプログラム中の少ない文を見ることで容易に検証することができるので、ユーザが、対象変数がプライベート化可能であることを知る時間を削減することができる。
【０１３４】
また、プライベート化の第１条件またはプライベート化の第２条件をプログラム実行順またはその逆順に文を表示しながら検証することができるので、ユーザは、複雑な制御フローを持つプログラムでも短時間で、確実に調査を行なうことができる。
【０１３５】
尚、本発明は、図１〜図２０を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本発明は、本実施例で説明した変数のプライベート化可能性をユーザに検証させる目的以外にも使うことができる。
【０１３６】
例えば、ある変数に対する２つの参照点の間にループ運搬フロー依存があるとそのループは並列化できないことが知られている。このデータ依存を引き起こす可能性のある制御フローをユーザに表示することで、コンパイラによる静的解析では確定的に判定できなかったループ運搬フロー依存をユーザが検証することが可能となる。
【０１３７】
このため、コンパイラがデータ依存の可能性があると見なした２つの参照点に対して、変数に対する一方の定義点からループ出口に至る制御フローをその上の文またはプログラムスライスを使って表示する。さらに、ループ入口からその変数に対するの使用点に至る制御フローを同様に表示する。これら２つを逐一、または、同時に２つの画面を使って表示することにより、ユーザによるデータ依存の存在の検証、すなわち、ループ並列化の検証が可能となる。
【０１３８】
また、本例では、記録媒体としてＣＤ−ＲＯＭを用いることを記載しているが、ＦＤ（Flexible Disk）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【０１３９】
【発明の効果】
本発明によれば、与えられたループに対して、ループ入口点からある変数の定義点へ至るループ独立な制御フロー、または、ループ入口点からある変数の定義点を通らずにその変数の使用点へ至るループ独立な制御フローを、その上の文、または、その制御フローに沿ったプログラムスライスを使って、プログラム実行順または逆順に表示するので、従来は、対象変数がプライベート化可能か否かをユーザが調査する場合、システムは「対象変数の使用点が実行される時、同じループイタレーション内で、その実行より前にその変数の定義点が実行される」という情報を表示しないのでユーザは自分でそれを調べなければならず、ユーザの負荷が大きかったとの問題を解決できる。すなわち、本発明により、ユーザは自分でそれを調べる必要がなくなり、ユーザの、対象変数のプライベート化判定等に要する時間を削減すること、および、ユーザの負荷を軽減することが可能となる。
【図面の簡単な説明】
【図１】本発明に係わるプログラム解析システムの構成例を示すブロック図である。
【図２】図１における解析対象入力部の処理動作例を示すフローチャートである。
【図３】図１における最内分岐解析部の処理動作例を示すフローチャートである。
【図４】図１における包含フラグ設定部の処理動作例を示すフローチャートである。
【図５】図１における通過フラグ設定部の処理動作例を示すフローチャートである。
【図６】図１における制御フロー解析部の第１の処理動作例を示すフローチャートである。
【図７】図１における制御フロー解析部の第２の処理動作例を示すフローチャートである。
【図８】図７におけるスライス解析の詳細例を示すフローチャートである。
【図９】解析対象ファイルのタグ構造例を示す説明図である。
【図１０】図９における解析対象ファイルのタグフォーマット例を示す説明図である。
【図１１】図１における文情報ファイルのタグ構造例を示す説明図である。
【図１２】図１１の文情報ファイルにおけるタグフォーマット例を示す説明図である。
【図１３】図１における解析対象リストのテーブル構成例を示す説明図である。
【図１４】図１におけるプログラム解析システムの解析対象となるプログラムの指定操作例を示す説明図である。
【図１５】図１における解析対象ファイルの内容例を示す説明図である。
【図１６】図１における階層的制御フローグラフの構造例を示す説明図である。
【図１７】図１における解析対象リストの構成例を示す説明図である。
【図１８】図１における制御フローリストの構成例を示す説明図である。
【図１９】図７におけるスライス解析で出力された文情報ファイルの構成例を示す説明図である。
【図２０】図１におけるプログラム解析システムの図１４のプログラムに対応する解析結果例を示す説明図である。
【符号の説明】
１００：解析処理部、１１０：構文解析、１２０：階層的制御フローグラフ作成部、１３０：解析対象入力部、１４０：最内分岐解析部、１５０：包含関係解析部、１５１：包含フラグ設定部、１５２：通過フラグ設定部、１６０：制御フロー解析部、１７１：中間語、１７２：階層的制御フローグラフ、１７３：解析対象リスト、１７４：制御フローリスト、１８１：入力プログラム、１８２：解析対象ファイル、１８３：文情報ファイル、１９１：解析対象指定部、１９２：文情報表示部、９０１〜９１４：タグ、１００１：タグフォーマット、１００２：解析方法の種別、１００３：文種別、１００４：対象種別、１１０１〜１１０９：タグ、１２０１：タグフォーマット、１３０１，１３０２：ポインタ、１３０３：文番号、１３０４：ノード種別、１３０５：ポインタ、１３１０：ノード種別、１４０１：入力プログラム表示画面、１４０２：解析対象行番号表示部、１４０３：解析対象行表示部、１４０４：文番号表示部、１４０５：解析対象参照点、１４０６：項目欄、１５０１〜１５１６：行、１６０１，１６１１〜１６１７，１６２１〜１６２３，１６３１〜１６３３：ループノード、１６１０，１６２０，１６３０：階層、１７０１，１７０３，１７０６：開始テーブル、１７０２，１７０４，１７０５，１７０７．１７０８，１８０１〜１８０３：テーブル、１９０１〜１９０６：行、２０００：表示画面。
【図１】
0003648710.tif 000002
【図２】
0003648710.tif 000003
【図３】
0003648710.tif 000004
【図４】
0003648710.tif 000005
【図５】
0003648710.tif 000006
【図６】
0003648710.tif 000007
【図７】
0003648710.tif 000008
【図８】
0003648710.tif 000009
【図９】
0003648710.tif 000010
【図１０】
0003648710.tif 000011
【図１１】
0003648710.tif 000012
【図１２】
0003648710.tif 000013
【図１３】
0003648710.tif 000014
【図１４】
0003648710.tif 000015
【図１５】
0003648710.tif 000016
【図１６】
0003648710.tif 000017
【図１７】
0003648710.tif 000018
【図１８】
0003648710.tif 000019
【図１９】
0003648710.tif 000020
【図２０】
0003648710.tif 000021