(57)【特許請求の範囲】
【請求項１】
ＣＰＵが、変数を参照する命令について、この命令に到達する定義命令との間に参照定義連鎖を設定する参照定義連鎖設定ステップと、
変数を定義する命令について、この命令に到達する参照命令との間に定義参照連鎖を設定する定義参照連鎖ステップと、
前記参照定義連鎖と前記定義参照連鎖から、対応する連鎖を連鎖対と判定する連鎖対判定ステップと、
前記連鎖対判定ステップで連鎖対と判定されなかった連鎖を取り除き、連鎖対と判定された連鎖をメモリに格納する連鎖削除ステップとを実行し、
前記連鎖対判定ステップでは、参照定義連鎖元の変数を参照する命令が参照する変数と定義参照連鎖元の前記変数を定義する命令が定義する変数が一致する、もしくは、別名関係にあり、前記参照定義連鎖元の前記変数を参照する命令が前記定義参照連鎖先の前記定義される値を参照する可能性のある命令と一致し、且つ、前記定義参照連鎖元の前記変数を定義する命令が前記参照定義連鎖先の前記参照される値を定義する可能性のある命令と一致する場合に、前記参照定義連鎖が前記定義参照連鎖と対応すると判定するプログラム解析方法。
【請求項２】
ＣＰＵが、変数を参照する命令について、この命令に到達する定義命令との間に参照定義連鎖を設定する参照定義連鎖設定ステップと、前記変数を参照する命令の参照が曖昧である場合には、前記到達する定義命令の定義が曖昧か否かを判定し、曖昧でない場合には、前記到達する定義命令について、前記変数を参照する命令との間に定義参照連鎖を設定しメモリに格納する定義参照連鎖設定ステップとを実行し、
前記参照定義連鎖設定ステップでは、変数を参照する命令が非曖昧参照の場合には、前記変数を参照する命令の参照変数が前記命令に到達する定義命令の定義変数と一致する場合のみ参照定義連鎖を設定しメモリに格納し、前記変数を参照する命令が曖昧参照の場合には、前記変数を参照する命令の参照変数が前記命令に到達する定義命令の定義変数と別名関係にある場合も参照定義連鎖を設定しメモリに格納するプログラム解析方法。
【請求項３】
ＣＰＵが、変数を定義する命令について、この命令に到達する参照命令との間に定義参照連鎖を設定する定義参照連鎖設定ステップと、前記変数を定義する命令の定義が曖昧である場合には、前記到達する参照命令の参照が曖昧か否かを判定し、曖昧でない場合には、前記到達する参照命令について、前記変数を定義する命令との間に参照定義連鎖を設定しメモリに格納する参照定義連鎖設定ステップとを実行し、
前記定義参照連鎖設定ステップでは、変数を定義する命令が非曖昧定義の場合には、前記変数を定義する命令の定義変数が前記命令に到達する参照命令の参照変数と一致する場合のみ定義参照連鎖を設定しメモリに格納し、前記変数を定義する命令が曖昧定義の場合には、前記変数を定義する命令の定義変数が前記命令に到達する参照命令の参照変数と別名関係にある場合も定義参照連鎖を設定しメモリに格納するプログラム解析方法。
【請求項４】
請求項２記載のプログラム解析方法を含む請求項３記載のプログラム解析方法。
【請求項５】
変数を参照する命令について、この命令に到達する定義命令との間に参照定義連鎖を設定する参照定義連鎖設定ステップと、
変数を定義する命令について、この命令に到達する参照命令との間に定義参照連鎖を設定する定義参照連鎖ステップと、
前記参照定義連鎖と前記定義参照連鎖から、対応する連鎖を連鎖対と判定する連鎖対判定ステップと、
前記連鎖対判定ステップで連鎖対と判定されなかった連鎖を取り除き、連鎖対と判定された連鎖をメモリに格納する連鎖削除ステップをコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記連鎖対判定ステップは、参照定義連鎖元の変数を参照する命令が参照する変数と定義参照連鎖元の前記変数を定義する命令が定義する変数が一致する、もしくは、別名関係にあり、前記参照定義連鎖元の前記変数を参照する命令が前記定義参照連鎖先の前記定義される値を参照する可能性のある命令と一致し、且つ、前記定義参照連鎖元の前記変数を定義する命令が前記参照定義連鎖先の前記参照される値を定義する可能性のある命令と一致する場合に、前記参照定義連鎖が前記定義参照連鎖と対応すると判定する記録媒体。
【請求項６】
変数を参照する命令について、この命令に到達する定義命令との間に参照定義連鎖を設定する参照定義連鎖設定ステップと、前記変数を参照する命令の参照が曖昧である場合には、前記到達する定義命令の定義が曖昧か否かを判定し、曖昧でない場合には、前記到達する定義命令について、前記変数を参照する命令との間に定義参照連鎖を設定しメモリに格納する定義参照連鎖設定ステップとをコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記参照定義連鎖設定ステップは、変数を参照する命令が非曖昧参照の場合には、前記変数を参照する命令の参照変数が前記命令に到達する定義命令の定義変数と一致する場合のみ参照定義連鎖を設定しメモリに格納し、前記変数を参照する命令が曖昧参照の場合には、前記変数を参照する命令の参照変数が前記命令に到達する定義命令の定義変数と別名関係にある場合も参照定義連鎖を設定しメモリに格納する記録媒体。
【請求項７】
変数を定義する命令について、この命令に到達する参照命令との間に定義参照連鎖を設定する定義参照連鎖設定ステップと、前記変数を定義する命令の定義が曖昧である場合には、前記到達する参照命令の参照が曖昧か否かを判定し、曖昧でない場合には、前記到達する参照命令について、前記変数を定義する命令との間に参照定義連鎖を設定しメモリに格納する参照定義連鎖設定ステップとをコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記定義参照連鎖設定ステップは、変数を定義する命令が非曖昧定義の場合には、前記変数を定義する命令の定義変数が前記命令に到達する参照命令の参照変数と一致する場合のみ定義参照連鎖を設定しメモリに格納し、前記変数を定義する命令が曖昧定義の場合には、前記変数を定義する命令の定義変数が前記命令に到達する参照命令の参照変数と別名関係にある場合も定義参照連鎖を設定しメモリに格納する記録媒体。
【請求項８】
請求項６記載の記録媒体のプログラムを記録した請求項７記載の記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、プログラム解析方法及び記録媒体に関するものであり、詳しくは高級言語からオブジェクトコードを生成するコンパイラにおいて、特に命令間のデータの流れを解析するデータフロー解析技術に関する。
【０００２】
【従来の技術】
コンパイラは高級言語からオブジェクトコードを生成するが、この際に冗長な命令を削減する最適化を行なう。コンパイラでは、最適化を行なう為に種々のプログラム解析を行なうが、この中に命令間のデータの流れを解析する連鎖情報解析がある。連鎖情報とは各変数の参照と定義を連鎖で結んだものであり、例えば、
命令１        ＭＯＶ  １００，Ｄ０
（レジスタＤ０に定数１００を書き込む。）
命令２        ＡＤＤ  Ｄ０、Ｄ１
（レジスタＤ１にレジスタＤ０の内容を加える。）
と言うコードがあった場合、命令２でのレジスタＤ０の値は命令１で定義された値（１００）であり、この時連鎖情報は、命令１について、
ＤＵ連鎖（命令１：レジスタＤ０）＝｛命令２｝
命令２について、
ＵＤ連鎖（命令２：レジスタＤ０）＝｛命令１｝
と表現できる。ここでＤＵ連鎖とは定義参照連鎖を意味し、各変数の定義について、そこで定義された値がどの命令で参照される（可能性がある）かを命令の集合として表現したものであり、ＵＤ連鎖とは、逆に、各変数の参照について、そこで参照される値がどの命令で定義される（可能性がある）かを命令の集合として表現したものであり、参照定義連鎖を意味する。
【０００３】
この連鎖情報は、一般に到達する定義を解析し、この情報を用いて設定される。これは例えばコンパイラ２（サイエンス社）に詳しく述べられている。
【０００４】
【発明が解決しようとする課題】
しかしながら、従来の技術では変数に別名が存在した場合の解析に非常に多くの解析時間、メモリを必要としていた。すなわち、変数に別名が存在する場合には、まず各変数がどの様な別名を持つかを解析し、各変数の定義があった場合には該変数の定義の他に全ての別名変数の定義があるとして解析を行なう必要がある。図２、図１７、図１８を参照して例を示す。図２のコードの場合、完全な連鎖情報は図１７の様になる。これを到達する定義のみから解析する場合には、別名を持つ定義については、別名定義も含めて到達する定義解析を行なう必要がある為、間接指定（Ａ０）定義については（８、ＳＰ）、（４、ＳＰ）も定義があるとして解析を行なう。つまり、各命令行での到達する定義は図１８の様になる。到達する定義及び連鎖情報についてはレジスタに関するものは簡単の為省略した。従って別名が多数存在した場合には、各変数定義毎に膨大な数の別名変数の定義が発生し、解析時間、解析に必要なメモリ量の増大を招いていた。
【０００５】
本発明は、かかる問題点に鑑みてなされたものであり、別名変数が多数存在した場合においても効率的な連鎖情報解析を行なうことのできるプログラム解析方法、解析装置及び記録媒体を提供することを目的とする。
【０００６】
【課題を解決するための手段】
請求項１記載のプログラム解析方法は、ＣＰＵが、変数を参照する命令について、この命令に到達する定義命令との間に参照定義連鎖を設定する参照定義連鎖設定ステップと、
変数を定義する命令について、この命令に到達する参照命令との間に定義参照連鎖を設定する定義参照連鎖ステップと、
前記参照定義連鎖と前記定義参照連鎖から、対応する連鎖を連鎖対と判定する連鎖対判定ステップと、
前記連鎖対判定ステップで連鎖対と判定されなかった連鎖を取り除き、連鎖対と判定された連鎖をメモリに格納する連鎖削除ステップとを実行し、
前記連鎖対判定ステップでは、参照定義連鎖元の変数を参照する命令が参照する変数と定義参照連鎖元の前記変数を定義する命令が定義する変数が一致する、もしくは、別名関係にあり、前記参照定義連鎖元の前記変数を参照する命令が前記定義参照連鎖先の前記定義される値を参照する可能性のある命令と一致し、且つ、前記定義参照連鎖元の前記変数を定義する命令が前記参照定義連鎖先の前記参照される値を定義する可能性のある命令と一致する場合に、前記参照定義連鎖が前記定義参照連鎖と対応すると判定するものである。
【０００７】
請求項１記載のプログラム解析方法によれば、別名変数が多数存在する場合にも高速に連鎖情報を解析することができ、別名定義の存在に伴うメモリ使用量を削減することができる。
【００１２】
請求項２記載のプログラム解析方法は、ＣＰＵが、変数を参照する命令について、この命令に到達する定義命令との間に参照定義連鎖を設定する参照定義連鎖設定ステップと、前記変数を参照する命令の参照が曖昧である場合には、前記到達する定義命令の定義が曖昧か否かを判定し、曖昧でない場合には、前記到達する定義命令について、前記変数を参照する命令との間に定義参照連鎖を設定しメモリに格納する定義参照連鎖設定ステップとを実行し、
前記参照定義連鎖設定ステップでは、変数を参照する命令が非曖昧参照の場合には、前記変数を参照する命令の参照変数が前記命令に到達する定義命令の定義変数と一致する場合のみ参照定義連鎖を設定しメモリに格納し、前記変数を参照する命令が曖昧参照の場合には、前記変数を参照する命令の参照変数が前記命令に到達する定義命令の定義変数と別名関係にある場合も参照定義連鎖を設定しメモリに格納するものである。
【００１３】
請求項２記載のプログラム解析方法によれば、到達する定義情報により定義参照連鎖を設定でき、連鎖の対応を確認する必要がないため、請求項１に比べてさらに高速に連鎖情報を解析できる。
【００１６】
請求項３のプログラム解析方法は、ＣＰＵが、変数を定義する命令について、この命令に到達する参照命令との間に定義参照連鎖を設定する定義参照連鎖設定ステップと、前記変数を定義する命令の定義が曖昧である場合には、前記到達する参照命令の参照が曖昧か否かを判定し、曖昧でない場合には、前記到達する参照命令について、前記変数を定義する命令との間に参照定義連鎖を設定しメモリに格納する参照定義連鎖設定ステップとを実行し、
前記定義参照連鎖設定ステップでは、変数を定義する命令が非曖昧定義の場合には、前記変数を定義する命令の定義変数が前記命令に到達する参照命令の参照変数と一致する場合のみ定義参照連鎖を設定しメモリに格納し、前記変数を定義する命令が曖昧定義の場合には、前記変数を定義する命令の定義変数が前記命令に到達する参照命令の参照変数と別名関係にある場合も定義参照連鎖を設定しメモリに格納するものである。
【００１７】
請求項３記載のプログラム解析方法によれば、到達する参照情報により参照定義連鎖を設定でき、連鎖の対応を確認する必要がないため、請求項１に比べてさらに高速に連鎖情報を解析できる。
【００２０】
請求項４記載のプログラム解析方法は、請求項３において、請求項２記載のプログラム解析方法を含むものである。
【００２１】
請求項４記載のプログラム解析方法によれば、到達する定義情報、及び、到達する参照情報から確実な参照定義連鎖及び定義参照連鎖を設定でき、連鎖の対応を確認する必要がないため、請求項１に比べてさらに高速に連鎖情報を解析できる。
【００３８】
請求項５記載の記録媒体は、変数を参照する命令について、この命令に到達する定義命令との間に参照定義連鎖を設定する参照定義連鎖設定ステップと、
変数を定義する命令について、この命令に到達する参照命令との間に定義参照連鎖を設定する定義参照連鎖ステップと、
前記参照定義連鎖と前記定義参照連鎖から、対応する連鎖を連鎖対と判定する連鎖対判定ステップと、
前記連鎖対判定ステップで連鎖対と判定されなかった連鎖を取り除き、連鎖対と判定された連鎖をメモリに格納する連鎖削除ステップをコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記連鎖対判定ステップは、参照定義連鎖元の変数を参照する命令が参照する変数と定義参照連鎖元の前記変数を定義する命令が定義する変数が一致する、もしくは、別名関係にあり、前記参照定義連鎖元の前記変数を参照する命令が前記定義参照連鎖先の前記定義される値を参照する可能性のある命令と一致し、且つ、前記定義参照連鎖元の前記変数を定義する命令が前記参照定義連鎖先の前記参照される値を定義する可能性のある命令と一致する場合に、前記参照定義連鎖が前記定義参照連鎖と対応すると判定するものである。
【００３９】
請求項５記載の記録媒体によれば、請求項１と同様な効果がある。
【００４４】
請求項６記載の記録媒体は、変数を参照する命令について、この命令に到達する定義命令との間に参照定義連鎖を設定する参照定義連鎖設定ステップと、前記変数を参照する命令の参照が曖昧である場合には、前記到達する定義命令の定義が曖昧か否かを判定し、曖昧でない場合には、前記到達する定義命令について、前記変数を参照する命令との間に定義参照連鎖を設定しメモリに格納する定義参照連鎖設定ステップとをコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記参照定義連鎖設定ステップは、変数を参照する命令が非曖昧参照の場合には、前記変数を参照する命令の参照変数が前記命令に到達する定義命令の定義変数と一致する場合のみ参照定義連鎖を設定しメモリに格納し、前記変数を参照する命令が曖昧参照の場合には、前記変数を参照する命令の参照変数が前記命令に到達する定義命令の定義変数と別名関係にある場合も参照定義連鎖を設定しメモリに格納するものである。
【００４５】
請求項６記載の記録媒体によれば、請求項２と同様な効果がある。
【００４８】
請求項７記載の記録媒体は、変数を定義する命令について、この命令に到達する参照命令との間に定義参照連鎖を設定する定義参照連鎖設定ステップと、前記変数を定義する命令の定義が曖昧である場合には、前記到達する参照命令の参照が曖昧か否かを判定し、曖昧でない場合には、前記到達する参照命令について、前記変数を定義する命令との間に参照定義連鎖を設定しメモリに格納する参照定義連鎖設定ステップとをコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記定義参照連鎖設定ステップは、変数を定義する命令が非曖昧定義の場合には、前記変数を定義する命令の定義変数が前記命令に到達する参照命令の参照変数と一致する場合のみ定義参照連鎖を設定しメモリに格納し、前記変数を定義する命令が曖昧定義の場合には、前記変数を定義する命令の定義変数が前記命令に到達する参照命令の参照変数と別名関係にある場合も定義参照連鎖を設定しメモリに格納するものである。
【００４９】
請求項７記載の記録媒体によれば、請求項３と同様な効果がある。
【００５２】
請求項８記載の記録媒体は、請求項７において、請求項６記載の記録媒体のプログラムを記録したものである。
【００５３】
請求項８記載の記録媒体によれば、請求項４と同様な効果がある。
【００５４】
【発明の実施の形態】
〔用語の説明〕
まず用語について、説明する。
【００５５】
変数は、値を記憶する領域である。例えばレジスタ、メモリ等を指す。
【００５６】
レジスタ変数は、記憶場所がレジスタである変数である。
【００５７】
メモリ変数は、記憶場所が明示された特定のメモリ領域である変数である。具体的には、絶対アドレス指定されたメモリを指す。データ解析の範囲でスタックポインタやベースレジスタの値が変化しない場合には、スタックポインタ相対やベースレジスタ相対で指定されるメモリもこれに含まれる。
【００５８】
間接指定変数は、記憶場所が他の変数によって間接的に指定されたメモリである変数である。例えば下記の命令の場合、（Ａ０）は記憶場所はレジスタＡ０の内容によって指定されるメモリとなるので（Ａ０）は間接指定変数となる。
【００５９】
ＭＯＶ  Ｄ１、（Ａ０）
非曖昧定義（参照）は、ある記憶場所を特定した際に、その記憶場所に確実に値を書き込むことである。例えば、
ＭＯＶ  Ｄ１、（＿Ｘ）
は、記憶場所（＿Ｘ）に確実に値（Ｄ１）を書き込む為、非曖昧定義である。同様に参照の場合について、非曖昧参照がある。
【００６０】
曖昧定義（参照）は、ある記憶場所を特定した際に、その記憶場所に値を書き込むかもしれないことである。例えば、
ＭＯＶ  Ｄ１、（Ａ０）
はＡ０が＿Ｘを指す場合には、＿Ｘへ値を書き込むが、そうでない場合には＿Ｘへ値を書き込まない。このためこの定義は曖昧定義と言う。同様に参照の場合について、曖昧参照がある。
【００６１】
以下、本発明に係るプログラム解析方法、解析装置及び記録媒体について図面を参照しながら説明する。
【００６２】
［実施の形態１］
図１（ａ）は、実施の形態１におけるコンパイラの構成図である。コンパイラは、コンパイラ上流ステップ１０、プログラム解析ステップ２０、コンパイラ下流ステップ３０から構成される。またコンパイラ上流ステップ１０は入力としてソースプログラム５０を受け取り、出力として内部形式コード２００を生成する。プログラム解析ステップ２０は、内部形式コード２００を入力として受け取り、連鎖情報２４０を生成する。コンパイラ下流ステップ３０は内部形式コード２００及び連鎖情報２４０を受け取り、最終的な目的プログラム６０を生成する。
【００６３】
図１（ｂ）は、実施の形態１におけるプログラム（データ）解析方法の構成及び関連するデータを示すブロック図である。
【００６４】
本プログラム解析方法は、命令間のデータの流れを解析する方法であって、別名解析ステップ１００、ＵＤ連鎖解析ステップ１１０、ＤＵ連鎖解析ステップ１２０、連鎖対解析・削除ステップ１３０から構成される。またデータ解析ステップはコンパイラの一部を成し、その入力としてコンパイラ内部形式コード２００を受け取り、出力として連鎖情報２４０を生成する。図２に、データ解析方法に入力として渡される内部形式コードの一例を示す。以後、この図２の内部形式コードに対する動作を具体例として示す。
【００６５】
（別名解析ステップ）
別名解析ステップ１００は、内部形式コード２００に含まれる変数毎の別名変数を解析し、別名情報２１０として出力する。別名情報２１０は内部形式コード２００に含まれる全ての変数毎にその別名となる可能性のある変数の集合を対応付けたものである。別名解析ステップ１００の動作は通常のコンパイラに含まれるものと同等である為詳細は省略する。簡単の為に以下では、レジスタ変数は別名を持たない、メモリ変数は間接指定変数を別名として持つ、間接指定変数は全てのメモリ変数を別名として持つとする。また間接指定変数は唯一であるとする。つまり内部形式コード２００中の全ての間接指定変数は同一のものとして扱う。また、レジスタに関する到達する定義・参照及び連鎖情報についても簡単の為省略するが、同様の解析でレジスタに関する連鎖情報も設定できることは言うまでもない。
【００６６】
図２の内部形式コード２００が入力されると、別名解析ステップ１００は内部形式コード２００に含まれる全ての変数の別名解析を行ない、図３で示される別名情報を出力する。
【００６７】
（ＵＤ連鎖解析ステップ）
ＵＤ連鎖解析ステップ１１０は内部形式コード２００を読み込み、別名情報２１０を参照しながら、ＵＤ連鎖情報２２０を出力する。図４はＵＤ連鎖情報解析ステップ１１０の動作アルゴリズムをフローチャートとして記述したものである。
【００６８】
ステップｕ１はステップｕ９と対になり、ステップｕ２〜ｕ８を内部形式コード２００の全ての命令について繰り返す。
【００６９】
まずステップｕ２で命令に変数の参照があるか否かを判定する。ある場合にはステップｕ３に移り、現在の到達定義情報に該変数もしくは該変数の別名変数の定義命令が登録されているか否かを判定する。登録されている場合には、現在の命令のＵＤ連鎖情報として、
ＵＤ連鎖（現在の命令：該変数）＝該変数もしくは別名変数の定義命令
を追加する（ステップｕ４）。
【００７０】
次にステップｕ５で命令に変数の定義があるか否かを判定する。ある場合にはステップｕ６に移り、その定義が非曖昧定義か否かを判定する。非曖昧定義の場合にはステップｕ７に移り、到達定義情報に含まれる同一変数の定義を全て取り除く。曖昧、非曖昧に関わらず変数の定義があった場合にはステップｕ８に移り、該定義を、
定義命令（命令：変数）
として到達定義情報に追加する。
【００７１】
図２の内部形式コード２００に対して図５のＵＤ連鎖情報２２０が出力される。図５のＵＤ連鎖情報２２０では、連鎖元命令、連鎖に関する変数、連鎖先命令を組として表形式で表しているが、これは表現の一形態であるのはいうまでもない。図５のＵＤ１は、
ＵＤ連鎖（命令４：（４、ＳＰ））＝｛命令２｝
に相当し、命令４で参照される（４、ＳＰ）は命令２で定義された可能性があることを示している。
【００７２】
（ＤＵ連鎖解析ステップ）
ＤＵ連鎖解析ステップ１２０は内部形式コード２００を読み込み、別名情報２１０を参照しながら、ＤＵ連鎖情報２３０を出力する。図６はＤＵ連鎖情報解析ステップ１２０の動作アルゴリズムをフローチャートとして記述したものである。
【００７３】
ステップｄ１はステップｄ９と対になり、ステップｄ２〜ｄ８を内部形式コード２００の全ての命令について逆順に繰り返す。
【００７４】
まずステップｄ２で命令に変数の定義があるか否かを判定する。ある場合にはステップｄ３に移り、現在の到達参照情報に該変数もしくは該変数の別名変数の参照命令が登録されているか否かを判定する。登録されている場合には、現在の命令のＤＵ連鎖情報として、
ＤＵ連鎖（現在の命令：該変数）＝該変数もしくは別名変数の参照命令
を追加する（ステップｄ４）。更にステップｄ５でその定義が非曖昧定義か否かを判定する。非曖昧定義の場合にはステップｄ６に移り、到達参照情報に含まれる同一変数の参照を全て取り除く。
【００７５】
次にステップｄ７で命令に変数の参照があるか否かを判定する。ある場合にはステップｄ８に移り、該参照を、
参照命令（命令：変数）
として到達参照情報に追加する。
【００７６】
図２の内部形式コード２００に対して図７のＤＵ連鎖情報２３０が出力される。
【００７７】
（連鎖対解析・削除ステップ）
連鎖対解析・削除ステップ１３０は、ＵＤ連鎖情報２２０及びＤＵ連鎖情報２３０を読み込み、不要な連鎖情報を取り除いて最終的な連鎖情報２４０を生成する。図８は連鎖対解析ステップ１３０の動作アルゴリズムをフローチャートとして記述したものである。
【００７８】
ステップｐ１はステップｐ４と対となり、ステップｐ２、ｐ３をＵＤ連鎖情報全てについて繰り返す。
【００７９】
まずステップｐ２でＵＤ連鎖情報に対応するＤＵ連鎖情報が存在するか否かを判定する。対応する連鎖情報とは命令Ａの変数Ｂに対するＵＤ連鎖情報の定義命令がＣであった場合に、命令Ｃの変数Ｂに対するＤＵ連鎖情報として参照命令がＡのものを指す。命令Ａと命令Ｂの変数が別名関係にある場合にはこれも対応するとして取り扱う。対応するＤＵ連鎖情報が存在しない場合にはステップｐ３で該ＵＤ連鎖情報を取り除く。
【００８０】
ステップｐ５はステップｐ８と対となり、ステップｐ６、ｐ７をＤＵ連鎖情報全てについて繰り返す。
【００８１】
まずステップｐ６でＤＵ連鎖情報に対応するＵＤ連鎖情報が存在するか否かを判定する。対応するＤＵ連鎖情報が存在しない場合にはステップｐ７で該ＤＵ連鎖情報を取り除く。
【００８２】
図５のＵＤ連鎖情報及び図７のＤＵ連鎖情報に対して解析した場合、対は図９の対１〜対６となる。このうち、対１〜対３は変数が同一の場合、対４〜対６が別名変数としての対である。図５のＵＤ１のＵＤ連鎖情報には対応するＤＵ連鎖情報が無いため、これを取り除く。結果図９が最終的なＵＤ、ＤＵ連鎖情報となる。
【００８３】
以上構成により、別名変数を考慮した到達定義または到達参照解析を行なうこと無しに連鎖情報を求めることができ、高速解析かつメモリ使用量の抑制が実現できる。また、図８のステップｐ２、ステップｐ６での処理を上記連鎖対解析・削除ステップ１３０に記述した方法で行なうことにより、連鎖対の解析を精度良く行なうことができ、連鎖情報を用いた最適化の効率を向上することができる。
【００８４】
［実施の形態２］
図１０（ａ）は、実施の形態２におけるコンパイラの構成図である。コンパイラは、コンパイラ上流ステップ１０、プログラム解析ステップ２０、コンパイラ下流ステップ３０から構成される。またコンパイラ上流ステップ１０は入力としてソースプログラム５０を受け取り、出力として内部形式コード２００を生成する。プログラム解析ステップ２０は、内部形式コード２００を入力として受け取り、連鎖情報２４０を生成する。コンパイラ下流ステップ３０は内部形式コード２００及び連鎖情報２４０を受け取り、最終的な目的プログラム６０を生成する。
【００８５】
図１０（ｂ）は、実施の形態２におけるデータ解析方法の構成及び関連するデータを示すブロック図である。
【００８６】
本データ解析方法は、別名解析ステップ１００、第一連鎖解析ステップ３００、第二連鎖解析ステップ３１０、から構成される。またデータ解析ステップはコンパイラの一部を成し、その入力としてコンパイラ内部形式コード２００を受け取り、出力として連鎖情報４００を生成する。実施の形態１と同様、図２の内部形式コードをデータ解析方法の入力の一例とする。以後、この図２の内部形式コードに対する動作を具体例として示す。
【００８７】
（別名解析ステップ）
別名解析ステップ１００は内部形式コード２００に含まれる変数毎の別名変数を解析し、別名情報２１０として出力する。別名解析ステップ１００は実施の形態１の別名解析ステップ１００と同一機能であるので詳細は省略する。機能が同一であるので、図２の内部形式コードが入力に対しては、実施の形態１と同様、図３で示される別名情報を出力する。
【００８８】
（第一連鎖解析ステップ）
第一連鎖解析ステップ３００は内部形式コード２００を読み込み、大部分のＵＤ連鎖情報及び一部のＤＵ連鎖情報を出力する。大部分のＵＤ連鎖情報とは、
（１）参照命令が非曖昧参照の場合には、該非曖昧参照変数が該参照命令に到達する定義命令で定義されている変数と一致するとき、
（２）参照命令が曖昧参照の場合には、該曖昧参照変数が該参照命令に到達する定義命令で定義されている変数と一致又は別名関係にあるとき、に設定されるＵＤ連鎖情報を言う。
【００８９】
また一部のＤＵ連鎖情報とは、
（１）参照命令が曖昧参照で、該曖昧参照変数が該参照命令に到達する定義命令で定義されている変数と一致又は別名関係にあり、且つ、該参照命令に到達する定義の定義変数が非曖昧定義の場合、に設定されるＤＵ連鎖情報を言う。
【００９０】
図１１は第一連鎖情報解析部３００の動作アルゴリズムをフローチャートとして記述したものである。
【００９１】
ステップａ１は、ステップａ１４と対になりステップａ２〜ａ１３を内部形式コード２００の全ての命令について繰り返す。
【００９２】
まずステップａ２で命令に変数の参照があるか否かを判定する。ある場合にはステップａ３に移り、該参照が曖昧参照か否かを判定する。曖昧参照でない場合にはステップａ４に移り、現在の到達定義情報に該変数が登録されているか否かを判定する。登録されている場合には、現在の命令のＵＤ連鎖情報として、
ＵＤ連鎖（現在の命令：該変数）＝該変数の定義命令
を追加する（ステップａ５）。
【００９３】
該参照が曖昧参照の場合には、ステップａ６に移り、現在の到達定義情報に該変数もしくは該変数の別名変数の定義命令が登録されているか否かを判定する。登録されている場合には、現在の命令のＵＤ連鎖情報として、
ＵＤ連鎖（現在の命令：該変数）＝該変数もしくは別名変数の定義命令
を追加する（ステップａ７）。更にステップａ８で、ステップａ６で判定した到達定義情報の変数が非曖昧定義か否かを判定する。非曖昧定義の場合には、該到達定義命令のＤＵ連鎖情報として、
ＤＵ連鎖（該到達定義命令：到達定義変数）＝現在の命令
を追加する（ステップａ９）
次にステップａ１０で命令に変数の定義があるか否かを判定する。ある場合にはステップａ１１に移り、その定義が非曖昧定義か否かを判定する。非曖昧定義の場合にはステップａ１２に移り、到達定義情報に含まれる同一変数の定義を全て取り除く。曖昧、非曖昧に関わらず変数の定義があった場合にはステップａ１３に移り、該定義を、
定義命令（命令：変数）
として到達定義情報に追加する。図２の内部形式コードに対して図１２の連鎖情報が出力される。到達する定義は各命令時点で図１３の様になる。
【００９４】
（第二連鎖解析ステップ）
第二連鎖解析ステップ３１０は内部形式コード２００を読み込み、大部分のＤＵ連鎖情報及び一部のＵＤ連鎖情報を出力する。大部分のＵＤ連鎖情報とは、
（１）定義命令が非曖昧定義の場合には、該非曖昧定義変数が該定義命令に到達する参照命令で参照されている変数と一致するとき、
（２）定義命令が曖昧定義の場合には、該曖昧定義変数が該定義命令に到達する参照命令で参照されている変数と一致又は別名関係にあるとき、に設定されるＤＵ連鎖情報を言う。
【００９５】
また一部のＵＤ連鎖情報とは、
（１）定義命令が曖昧定義で、該曖昧定義変数が該定義命令に到達する参照命令で参照されている変数と一致又は別名関係にあり、且つ、該定義命令に到達する参照の参照変数が非曖昧参照の場合、に設定されるＵＤ連鎖情報を言う。
【００９６】
図１４は、第二連鎖情報解析ステップ３１０の動作アルゴリズムをフローチャートとして記述したものである。
【００９７】
ステップｂ１はステップｂ１３と対になりステップｂ２〜ｂ１２を内部形式コード２００の全ての命令について逆順に繰り返す。
【００９８】
まずステップｂ２で命令に変数の定義があるか否かを判定する。ある場合にはステップｂ３に移り、該定義が曖昧定義か否かを判定する。曖昧定義でない場合にはステップｂ４に移り、現在の到達参照情報に該変数が登録されているか否かを判定する。登録されている場合には、現在の命令のＤＵ連鎖情報として、
ＤＵ連鎖（現在の命令：該変数）＝該変数の参照命令
を追加する（ステップｂ５）。次にステップｂ６に移り、到達参照情報に含まれる同一変数の参照を全て取り除く。
【００９９】
該参照が曖昧参照の場合には、ステップｂ７に移り、現在の到達参照情報に該変数もしくは該変数の別名変数の参照命令が登録されているか否かを判定する。登録されている場合には、現在の命令のＤＵ連鎖情報として、
ＤＵ連鎖（現在の命令：該変数）＝該変数もしくは別名変数の参照命令
を追加する（ステップｂ８）。更にステップｂ９で、ステップｂ７で判定した到達参照情報の変数が非曖昧参照か否かを判定する。非曖昧参照の場合には、該到達参照命令のＵＤ連鎖情報として、
ＵＤ連鎖（該到達参照命令：到達参照変数）＝現在の命令
を追加する（ステップｂ１０）
次にステップｂ１１で命令に変数の参照があるか否かを判定する。ある場合にはステップｂ１２に移り、該参照を、
参照命令（命令：変数）
として到達参照情報に追加する。図２の内部形式コードに対して図１５の連鎖情報が出力される。５００が第一連鎖解析部３００で生成された連鎖情報、５１０が第二連鎖解析部３１０で追加された連鎖情報である。到達する参照は各命令時点で図１６の様になる。
【０１００】
以上の構成により、別名変数を考慮した到達定義または到達参照解析を行なうこと無しに連鎖情報を求めることができ、高速解析かつメモリ使用量の抑制が実現できる。また、実施の形態２の構成では、連鎖情報を求めた後で不要な連鎖情報を除く必要がない為、更に高速解析が行なえる。また、図１１のステップａ３、図１４のステップｂ３での処理を上記に記述した方法で行なうことにより、曖昧定義・参照が存在する場合にも、連鎖情報の解析を精度良く行なうことができ、連鎖情報を用いた最適化の効率を向上することができる。
【０１０１】
［実施の形態３］
本実施の形態１および実施の形態２で示されるプログラム（データ）解析方法をフレキシブルディスク、ハードディスク、ＣＤ―ＲＯＭ、ＭＯ、ＤＶＤなどの記録媒体に格納し、記録媒体がプログラムを読み出し可能なコンピュータで実行することで、本実施の形態で示されるデータ解析装置を、コンピュータ上で実現できる。
【０１０２】
なお、上記実施の形態の解析方法における各ステップを手段により構成し、解析装置を実現することが可能である。
【０１０３】
【発明の効果】
請求項１記載のプログラム解析方法によれば、別名変数が多数存在する場合にも高速に連鎖情報を解析することができ、別名定義の存在に伴うメモリ使用量を削減することができる。
【０１０６】
請求項２記載のプログラム解析方法によれば、到達する定義情報により定義参照連鎖を設定でき、連鎖の対応を確認する必要がないため、請求項１に比べてさらに高速に連鎖情報を解析できる。
【０１０８】
請求項３記載のプログラム解析方法によれば、到達する参照情報により参照定義連鎖を設定でき、連鎖の対応を確認する必要がないため、請求項１に比べてさらに高速に連鎖情報を解析できる。
【０１１０】
請求項４記載のプログラム解析方法によれば、到達する定義情報、及び、到達する参照情報から確実な参照定義連鎖及び定義参照連鎖を設定でき、連鎖の対応を確認する必要がないため、請求項１に比べてさらに高速に連鎖情報を解析できる。
【０１１５】
請求項５記載の記録媒体によれば、請求項１と同様な効果がある。
【０１１６】
請求項６記載の記録媒体によれば、請求項２と同様な効果がある。
【０１１７】
請求項７記載の記録媒体によれば、請求項３と同様な効果がある。
【０１１８】
請求項８記載の記録媒体によれば、請求項４と同様な効果がある。
【図面の簡単な説明】
【図１】（ａ）は本発明の実施の形態１におけるコンパイラ及び関連するデータを示すブロック図である。（ｂ）は本発明の実施の形態１におけるプログラム解析方法の構成及び関連するデータを示すブロック図である。
【図２】内部形式コードの一例である。
【図３】図２に対応する別名情報である。
【図４】ＵＤ連鎖解析ステップ１１０の処理手順を示すフローチャートである。
【図５】図２に対応するＵＤ連鎖情報である。
【図６】ＤＵ連鎖解析ステップ１２０の処理手順を示すフローチャートである。
【図７】図２に対応するＤＵ連鎖情報である。
【図８】連鎖対解析・削除ステップ１３０の処理手順を示すフローチャートである。
【図９】図２に対応する最終的な連鎖情報である。
【図１０】（ａ）は本発明の実施の形態２におけるコンパイラ及び関連するデータを示すブロック図である。（ｂ）は本発明の実施の形態２におけるプログラム解析方法の構成及び関連するデータを示すブロック図である。
【図１１】第一連鎖解析ステップ３００の処理手順を示すフローチャートである。
【図１２】図２に対応する第一連鎖解析ステップ３００の解析結果である。
【図１３】図２に対応する到達する定義である。
【図１４】第二連鎖解析ステップ３１０の処理手順を示すフローチャートである。
【図１５】図２に対応する第一連鎖解析ステップ３００、及び第二連鎖解析ステップ３１０の解析結果である。
【図１６】図２に対応する到達する参照である。
【図１７】従来の連鎖情報の一例である。
【図１８】従来の到達する定義の一例である。
【符号の説明】
１０  コンパイラ上流ステップ
２０  プログラム解析ステップ
３０  コンパイラ上流ステップ
５０  ソースプログラム
６０  目的プログラム
１００  別名解析ステップ
１１０  ＵＤ連鎖解析ステップ
１２０  ＤＵ連鎖解析ステップ
１３０  連鎖対解析ステップ
２００  内部形式コード
２１０  別名情報
２２０  ＵＤ連鎖情報
２３０  ＤＵ連鎖情報
２４０  連鎖情報
３００  第一連鎖解析ステップ
３１０  第二連鎖解析ステップ
４００  連鎖情報
ＵＤ１  対のないＵＤ連鎖情報
対１  ＵＤ連鎖―ＤＵ連鎖対
対２  ＵＤ連鎖―ＤＵ連鎖対
対３  ＵＤ連鎖―ＤＵ連鎖対
対４  ＵＤ連鎖―ＤＵ連鎖対
対５  ＵＤ連鎖―ＤＵ連鎖対
対６  ＵＤ連鎖―ＤＵ連鎖対
【図１】
0003749451.tif 000002
【図２】
0003749451.tif 000003
【図３】
0003749451.tif 000004
【図４】
0003749451.tif 000005
【図５】
0003749451.tif 000006
【図６】
0003749451.tif 000007
【図７】
0003749451.tif 000008
【図８】
0003749451.tif 000009
【図９】
0003749451.tif 000010
【図１０】
0003749451.tif 000011
【図１１】
0003749451.tif 000012
【図１２】
0003749451.tif 000013
【図１３】
0003749451.tif 000014
【図１４】
0003749451.tif 000015
【図１５】
0003749451.tif 000016
【図１６】
0003749451.tif 000017
【図１７】
0003749451.tif 000018
【図１８】
0003749451.tif 000019