JPH09282173A - プログラムの静的解析方法 - Google Patents

Abstract

(57)【要約】 【課題】本発明は、プログラミング言語の処理系におい
て、プログラムの静的な解析を、より効果的に行うこと
を目的とする。 【解決手段】ソースプログラムの字句解析、構文解析、
意味解析を行い中間コードを生成し、中間コードに対し
て制御及びデータの流れを解析してフロー情報を生成
し、プログラムが停止すると仮定できるかどうかを判定
し、停止できると仮定できるなら停止するための必要条
件を求め、その必要条件を満たすようにフロー情報を更
新する。従来の静的解析方法よりも解析精度が向上す
る。あるいは、従来の解析方法よりも少ない手間で同等
以上の精度の解析を行える。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】プログラミング言語で記述さ
れたソースプログラムにおける制御の流れやデータの流
れを、そのソースプログラムを実行すること無しに解析
する、静的解析方法に関する。

【０００２】

【従来の技術】プログラミング言語で記述されたプログ
ラムの処理系、例えば、最適化コンパイラ・並列化コン
パイラ・プログラムの検証システムなどでは、プログラ
ムの制御の流れ（制御フロー）やデータの流れ（データ
フロー）について、プログラムを実行すること無しに調
べる、静的な解析が行われる。

【０００３】プログラムの静的な解析を行うためには、
まずソースプログラムに対して字句解析・構文解析・意
味解析を行い中間コードを生成し、得られた中間コード
に対して制御フロー解析やデータフロー解析を行い、解
析結果（制御フロー情報やデータフロー情報）を出力す
る。

【０００４】データフロー解析を行うためには、プログ
ラム中の各文で定義または使用される変数を知る必要が
ある。そのために、変数間の別名関係の解析や、手続き
呼び出しの副作用についての解析が行われる。

【０００５】各文で定義または使用される変数を解析し
た後、到達定義や生存変数などの、データの流れに関す
る情報を解析する。別名解析や手続き呼び出しの副作用
の解析の精度が低いと、実際には生じない定義や使用も
あるものと見なされるため、データフロー情報の精度が
低くなる。

【０００６】制御フロー解析及びデータフロー解析につ
いては、例えば次の文献に記されている。

【０００７】コンパイラ 原理・技法・ツール、Ａ．
Ｖ．エイホ、Ｒ．セシィ、Ｊ．Ｄ．ウルマン共著、原田
賢一訳、サイエンス社、１９９０年（文献１）Ｃ言語や
Ｆortran９０のようにポインタを用いるプログラミング
言語では、ポインタによって生じる別名関係の解析が必
要である。ポインタによって生じる別名関係は、ポイン
タの定義文を調べてポインタの指示し得る変数を求める
ことによって、ある程度は解析できる。その方法に例え
ば特開平６−３４８４７５号がある。しかし、ポインタ
によって生じる別名関係を常に正確に解析する方法はな
いことが証明されている。

【０００８】特に、動的なメモリ割り付けによって実現
された再帰的データ構造を用いるプログラムの別名関係
は解析が困難である。再帰的データ構造には、リンクト
リスト、循環リスト、ツリー、グラフなどがあり、様々
な分野のソフトウェアで使用されている。この様なデー
タ構造に対しては、ループや再帰呼び出しによって各要
素を順に処理することがよく行われるため、別名関係の
解析精度はプログラムの実行性能へ大きく影響し得る。

【０００９】再帰的データ構造に対しては、その構造の
各要素間の関係を解析することによって、効果的な別名
解析が行える場合がある。その方法は、例えば次の文献
に述べられている。

【００１０】Ｊoseph Ｈummel，Ｌaurie Ｊ.Ｈendre
n，and Ａlexandru Ｎicolau，ＡＧeneral Ｄata
Ｄependence Ｔest for Ｄynamic，Ｐointer−Ｂase
d Ｄata Ｓtructures，Ｐroceedings of the ＡＣ
Ｍ ＳＩＧＰＬＡＮ '９４Ｃonference on Ｐrogram
ming Ｌanguages Ｄesign and Ｉmplementation，
１９９４（文献２）この様な方法では、リストやツリー
のように規則的な構造の場合には、ポインタの定義文か
ら、作成されるデータ構造を解析することによって、そ
の要素間の関係をある程度正確に解析できる。ただし、
一般にはデータを作成する手続きとデータを利用する手
続きとが異なるため、手続き間解析を行う必要がある。

【００１１】

【発明が解決しようとする課題】再帰的データ構造に対
する別名解析の方法には、以下の欠点がある。

【００１２】１）ポインタの定義文から、作成されるデ
ータ構造を解析する方法では、比較的単純なデータ構造
しか精度の良い解析ができない。

【００１３】２）データの作成と使用が複数の手続きに
またがっていることが多いため、手続き間解析を行わな
いと精度の良い解析は困難である。

【００１４】本発明の目的の一つは、別名解析をはじめ
とする様々な静的解析の問題で、従来の方法よりも精度
の良い解析を行うことにある。本発明のもう一つの目的
は、従来の方法よりも少ない手間で同等以上の精度の解
析を行うことにある。

【００１５】

【課題を解決するための手段】本発明による静的解析方
法は、(ａ)ソースプログラムを読み込み、字句解析・構
文解析・意味解析を行い中間コードを生成するフロント
エンド、(ｂ)中間コードに対して制御の流れ及びデータ
の流れを解析してフロー情報を生成するフロー解析、
(ｃ)プログラムを実行した時に必ず停止すると仮定して
良いかどうかを判定する停止性判定、(ｄ)プログラムが
停止すると仮定できるならば、停止するための必要条件
を求める停止条件解析、(ｅ)前記必要条件が満たされる
ものとして、前記フロー解析を更新するフロー情報更
新、の各ステップによって実現される。

【００１６】ステップ（ａ）とステッブ（ｂ）は従来の
言語処理システムと同様の処理を行う。ステップ（ｃ）
は、解析対象のプログラムを実行した時に、必ず実行が
停止すると仮定できるかどうかを判定し、プログラムの
各部分毎に真（停止すると仮定して良い）または偽（停
止しない可能性がある）の値を出力する。ここでは、実
行時オプションやプログラム中に記述する指示文を元に
判定する。ステップ（ｄ）では、停止性判定部が真を出
力した部分について、その部分の実行が停止するための
必要条件を解析し、出力する。例えば、ループや手続き
の再帰呼び出しのように、無限に繰り返されうる制御機
構に対して、それが実行される際のデータに関する制約
条件として、停止するための必要条件が求められる。ス
テップ（ｅ）では、ステップ（ｄ）でもとめた条件が満
たされるものとしたときのフロー情報を解析し、適当な
形式で出力する。このとき、プログラムが停止するため
の条件をフロー情報に含めてもよい。

【００１７】ステップ（ｅ）で出力されたフロー情報
は、プログラムの検証や最適化、並列化などに利用でき
る。プログラムの検証のためには、プログラムの実行時
に停止条件を満たさなかった場合、実行を停止したり診
断メッセージを出力したりするように、プログラムの変
換を行うことができる。最適化や並列化に利用する際に
は、停止条件が常に成り立つものとして目的コードを生
成する方法と、ステップ（ｃ）の処理を行わずに、停止
条件が成り立つか否かをプログラムの実行時に判定し、
停止条件が成り立つ場合に実行するコードと停止条件が
成り立たない場合に実行するコードのいずれかの実行を
選択するような目的コードを生成する方法がある。

【００１８】なお、本発明で、プログラムの実行が停止
するということは、その実行中に割り込みや例外が発生
しなかった時に、プログラムの終了を示す文に制御が必
ず到達することを意味する。プログラムの終了を示す文
とは、例えばＣ言語ではmain関数のreturn文やexit()関
数、ＦortranのＳＴＯＰ文などである。プログラムのあ
る部分の実行が停止するとは、その部分の次に実行され
る文へ制御が必ず到達することである。例えば、ループ
であればその次の文、手続きであればその呼び出し側の
手続きへの復帰文へ、制御が到達することである。

【００１９】

【発明の実施の形態】以下、本発明の実施例を詳細に説
明する。

【００２０】図１は本発明を静的解析システムに適用し
た場合の一実施例の処理フローを示す図である。

【００２１】フロントエンド（３）は、プログラミング
言語で記述されたソースプログラム（１）を読み込み、
字句解析・構文解析・意味解析を行い、中間コード
（４）を生成する。生成された中間コードに対して、プ
ログラムの意味を変えない範囲で変形してあっても良
い。例えば、静的単一代入形式（Ｓtatic Ｓingle Ａ
ssignment Ｆorm）に変形したり、何らかの最適化を行
っても良い。

【００２２】停止性判定（８）では、解析対象のプログ
ラムが、実行した時に停止すると仮定して良いかどうか
判定する。結果は真（停止すると仮定できる）または偽
（停止しないかも知れない）の論理値によって表され
る。この判定は、静的解析システムの実行時オプション
か、ソースプログラム中に記述された指示文に基づいて
行われる。実行時オプションも指示文も指定されていな
い場合は、システムの既定値を用いる。停止性はプログ
ラム全体に対して指定することも、ループや手続きなど
の各部分毎に指定することもできる。

【００２３】停止条件解析部（９）では、プログラム中
の停止性判定で真を出力した部分に対して、その部分の
実行が停止するための必要条件を解析する。プログラム
が停止するための必要十分条件を解析することは一般に
は不可能であり、停止するための必要条件も常に検出で
きるわけではない。求められた必要条件は、プログラム
中で使用される変数と、定数・算術演算子・関係演算子
・論理演算子を組み合わせた論理式として表される。さ
らに、必要条件を表現するための変数や演算子を導入す
ることもできる。プログラムの実行が停止するならば、
プログラムの実行中にこの論理式が常に真であるものと
見なして良い。プログラムの実行中に変数が論理式が偽
となるような値を取るならば、プログラムの実行が停止
するという仮定は間違っていることになる。

【００２４】フロー情報更新部（１４）では、停止条件
が得られた場合にその条件を満たす時の制御及びデータ
の流れを反映するように、フロー情報（６）を更新し、
得られたフロー情報（１５）を適当な形式で出力する。

【００２５】プログラムが停止するための必要条件を求
められるプログラムの構成要素の例としては、ループと
手続きの再帰呼び出しがある。ループでは、有限回の繰
り返しのうちに繰り返しの終了条件のいずれかが成立し
なければ、そのループは無限に繰り返されることにな
る。手続きの再帰呼び出しでは、有限回の呼び出しのう
ちに再帰的な呼び出しを行わない条件のいずれかが成立
しなければ、再帰呼び出しを無限に続けることになる。

【００２６】以下、具体的なプログラムを例に、ループ
に対する停止条件解析の処理内容を説明する。

【００２７】第一のプログラム例として、本発明をリン
クトリスト（linked list）を処理するプログラムの別
名解析に適用した場合について説明する。

【００２８】リンクトリストを先頭から順にたどり、各
ノードに対して処理を行う関数の例を、図２に示す。リ
ンクトリストは図３に示すように、ノードがポインタで
接続されており、ポインタをたどることによって先頭の
ノードから順にノードを処理していくことができる。そ
の際、同じノードを二度たどることはない。

【００２９】このループ内で参照されるポインタnodeの
指示先が毎回異なるかどうかは、手続き間解析を行えば
解析することができる。その方法は例えば（文献２）に
記されている。

【００３０】手続き内のみを対象にしたデータフロー解
析では、以下のような解析が行われる。まず、リストの
先頭のノードを表す仮引数topの値は、他の手続きで定
義されるため、その値についての情報はない。よって、
ループの各繰り返しで定義・使用されるポインタnodeの
指示先についての情報も得られない。従って、topとnod
eは、手続き外でアドレスを参照可能な任意のデータを
指示している可能性があると見なされる。従って、ルー
プの各繰り返しでnodeの値が同じである可能性があると
考えなければならない。このことから、ある繰り返しで
値の定義されたnode->valueと同じデータが、別の繰り
返しで定義・使用される可能性があると考える必要があ
る。

【００３１】ここで、静的解析システムの出力するフロ
ー情報に、次のような文の間の依存関係が含まれるもの
とする。同一ループ中にない文ＳとＴとの間に依存関係
があるとき、これをベクトル（Ｓ，Ｔ，０）で表す。一
方、同一ループ中の文Ｓとループのｎ回後の繰り返しで
実行される文Ｔとの間に依存があるとしたとき、これを
ベクトル（Ｓ，Ｔ，ｎ）で表す。ただし、ｎは任意の整
数とする。何回後の繰り返しとの依存か特定できない、
言い替えると、全ての繰り返しとの間に依存が有り得る
場合は（Ｓ，Ｔ，＊）で表す。ここでいう依存関係は、
フロー依存・出力依存・逆依存を併せていうものとす
る。

【００３２】従来の静的解析方法では、図２のプログラ
ムで、文Ｓ１３で定義されるnode->valueは他の全ての
繰り返しでも定義され得ると考える必要があったため、
（Ｓ１３，Ｓ１３，＊）という依存関係が検出される。

【００３３】本発明によれば、図２のプログラムのルー
プ内で定義・使用される変数nodeの値が繰り返し毎に異
なり、Ｓ１３と他の繰り返しのＳ１３との間には依存関
係がないことを、手続き内の解析のみで検出することが
できる。

【００３４】図１に示す静的解析方法の各構成要素は、
以下のように構成される。まず、フロントエンド（３）
はＣ言語で記述されたソースプログラム（１）を入力と
して、中間コード（４）を出力する。実行時オプション
（２）が指定されているときには、その内容を中間コー
ドに付加する。次に、フロー解析（５）で制御フローと
データフローを解析する。中間コードや制御フロー解
析、データフロー解析の詳細については例えば（文献
１）に記載されている。

【００３５】図２のプログラムに対する中間コードを図
４に示す。中間コードは基本ブロックをノードとし、基
本ブロック間の制御の流れをエッジとするフローグラフ
で表される。基本ブロック（フローグラフのノード）
は、それに含まれる文のリストを持つ。文はここではソ
ースプログラムの文をそのまま用いているが、実際には
木構造・三つ組・四つ組などで表現される。関数div_li
st()は四つの基本ブロックからなる。基本ブロックＢ２
はwhile文の条件判定部を表しており、Ｂ２から出てい
る二本のエッジにはそれぞれＴＲＵＥとＦＡＬＳＥのラ
ベルが付けられている。これは、while文の条件がそれ
ぞれ成立するとき（ＴＲＵＥ）と成立しないとき（ＦＡ
ＬＳＥ）の分岐方向を表す。

【００３６】フロー解析（５）の際に、手続き中の各ル
ープ毎にループ表（７）を作成する。ループ表の構造を
図５に示す。それぞれのフィールドには以下のような値
が設定される。ループ構成基本ブロック（２１）には、
ループ中に含まれる基本ブロックのリストが設定され、
図２のプログラムではＢ２とＢ３からなる。ループ終了
条件式（２２）は、ループ外への分岐の条件が設定され
る。ループ外への分岐の条件を持たないループや、複数
の条件を持つループもある。図２のプログラムでは、ル
ープ外への分岐はwhile文の条件判定のみであるから、
ループ外へ分岐する条件としてcur==ＮＵＬＬが設定さ
れる。ループが繰り返されている間、このループ終了条
件は常に不成立である。本発明に関連する他のフィール
ドの内容については、使用する都度説明する。

【００３７】停止性判定（８）では、ループ表のループ
停止性（２３）に真（ＴＲＵＥ）または偽（ＦＡＬＳ
Ｅ）の値を、ループ毎に設定する。停止性が真の時、そ
のループは停止すると仮定して良く、偽の時は停止しな
い可能性がある。実行時オプションや指示文で指定する
際には、フロントエンドで中間コードの例えばwhile文
に対して真偽を設定しておく。停止性判定ではその情報
を利用してループ表に値を設定する。ここでは、システ
ムの既定値として、全てのループのループ停止性に真を
設定するものとする。

【００３８】停止条件解析（９）では、ループ停止性
（２３）が真である各ループについて、ループの停止す
る必要条件（停止条件）の検出を試みる。停止条件が求
められたら、ループ表のループ停止条件（２７）に停止
条件を設定する。この必要条件は、プログラム中で使用
される変数と、定数・算術演算子・関係演算子・論理演
算子を組み合わせた論理式として表される。

【００３９】与えられたループの停止条件の解析は、ル
ープ制御変数の検出（１１）、ループ終了条件式の検査
（１２）、ループ停止条件の解析（１３）の三つのステ
ップからなる。

【００４０】ループ制御変数の検出（１１）では、ルー
プの繰り返しを司る、制御変数を求める。以下の三つの
条件を満たす変数をループ制御変数とする。

【００４１】条件１：ループ終了条件式でその変数の値
が使用されている。

【００４２】条件２：ループの繰り返し毎に必ず一度同
じ式で値が更新される。

【００４３】条件３：条件２の更新を行う式の右辺の値
は、ループ不変変数と制御変数の値のみから定まる。

【００４４】ループの終了条件式がないなど、制御変数
を決められない場合には、ループの停止条件も決められ
ず、以下の処理は行われない。図２の例で言うと、変数
nodeがループ制御変数となる。なぜなら、終了条件式no
de==ＮＵＬＬで値が使用され、ループの繰り返し毎にno
de=node->nextという式で更新され、更新式の右辺node-
>nextの値はnodeの値のみから定まるからである。制御
変数が検出できた場合、ループの入り口での制御変数の
値を制御変数の初期値（２５）に設定する。nodeの初期
値はtopである。さらに、上記の条件２を満たす式を制
御変数更新式（２６）に設定する。nodeの更新式はnode
=node->nextである。

【００４５】ループ終了条件式の検査（１２）では、ル
ープの終了を判定する条件式の値が、ループ不変な変数
と制御変数の値のみから決定できるかどうかを調べる。
もし、制御変数の値からは条件式の値を決定できない時
は、ループの停止条件も決められず、以下の処理は行わ
れない。図２の例ではループ終了条件式がnode==ＮＵＬ
Ｌであるから、この式の真偽は制御変数nodeの値のみか
ら決まる。

【００４６】停止条件の解析（１３）では、条件式・制
御変数・制御変数の更新式から、ループの繰り返しが有
限回で停止するための必要条件を求める。

【００４７】一般に、制御変数をvar，varのｉ回目の繰
り返しでの値をvar(i)、条件式をＣond(var)とすると、
停止条件は以下のように決定される。もし、ループの繰
り返しが終了するならば、Ｃond(var(n))が偽となるｎ
(>=1)があるはずである。もし、ｉ＞０かつｊ＞０かつ
ｉ＜ｊ＜ｎである整数ｉとｊについて、var(i)とvar(j)
が等しいとすると、任意のｋ＞０に対してvar(i+k)とva
r(j+k)が等しくなければならない。言い替えると、ルー
プ制御変数の値は、var(i)からvar(j-1)までの値が順に
繰り返されると言うことである。すると、あるｊ＞ｋ＞
ｉに対してvar(k)とvar(n)が等しくなる。このことはｉ
＜ｊ＜ｎであることと矛盾する。従って、ｎ＞ｉ＞ｊ＞
０である任意のｉとｊに対して、var(i)とvar(j)は異な
る値を取らなければならない。このことは、ループの繰
り返しが有限回であるならば、ループ制御変数は二度と
同じ値を取らない、ということである。

【００４８】図２のプログラムで言うと、nodeの値がル
ープの途中で同じ値を取ったとすると、リストが巡回し
てしまうため、このループは無限に繰り返すことにな
る。よってこのループが停止するための必要条件は、no
deの値が毎回異なることである。このことは、ポインタ
nodeの指示先が毎回異なるということでもある。従って
ループの停止条件は、次のように表せる。プログラム中
の変数のみを用いて表すとすると、node!=node->nextと
表せる。しかし、この表現では次の繰り返しとの間の依
存がないことしか表していないため、ループの繰り返し
番号を表す変数ｉとｊを導入して、i==j｜｜node(i)!=n
ode(j)と表す方がより正確である。

【００４９】以上から、次の三つの条件 条件１：ループ制御変数がポインタである。

【００５０】条件２：ループ制御変数（ｐとする）の更
新式が、ｐ＝＊(p+c)の形式である。ただし、ｃは定数
である（node->nextという式はある定数ｃを用いて＊(n
ode+c)と表せる）。

【００５１】条件３：ループ停止条件が、ｐ!=ＮＵＬＬ
の形式である。

【００５２】を満たすとき、ループ表のループ停止条件
（２７）に、i==j｜｜p(i)!=p(j)という論理式を設定す
る。ただし、p(i)はループ制御変数ｐのｉ回目の繰り返
しでの値、ｉとｊはループの繰り返し番号である。ある
いは、ループ停止条件としてp!=*(p+c)という式を設定
しても良い。

【００５３】停止条件解析（９）でループの停止条件が
求められた場合、フロー条件更新（１４）で、停止条件
が満たされるときのフロー情報を解析する。この例で
は、次のような方法でフロー情報を更新する。フロー解
析（５）で検出された各依存関係について、ループ停止
条件（２７）の論理式を満たすか否か調べ、満たされな
いものを削除する。前述の依存関係（Ｓ１３，Ｓ１３，
＊）について調べると、この依存関係を生じさせる変数
node->valueのアドレスは、ループ停止条件からループ
の繰り返し毎に異なることがわかる。従って、異なる繰
返し間のnode->valueの参照の間に依存関係は生じず、
（Ｓ１３，Ｓ１３，＊）を削除することができる。

【００５４】第二のプログラム例として図６のプログラ
ムの場合を説明する。図６のプログラムは図２のプログ
ラムとほとんど同じであるが、文Ｓ２２のループの終了
する条件が異なる。リンクトリストを処理する方法とし
て、図３のようにリストの最後のノードのnextフィール
ドをＮＵＬＬにする方法の他に、最後のノードとしてne
xtフィールドが自分自身を指すノードを追加する方法が
ある。この最後のノードは番兵（sentinel）と呼ばれ
る。番兵を持つリストでは構造が非巡回ではなくなるた
め、図２のプログラムに対しては正確な解析の可能な方
法でも、番兵のあるリストではうまく解析できない場合
がある。本発明では番兵のあるリストに対しても正確な
解析ができる。

【００５５】図２のループの解析との違いは、条件式の
みである。以下、停止条件解析部の処理を説明する。制
御変数の検出（１１）では、制御変数としてnodeが検出
される。終了条件式の検査（１２）では、図６のループ
の条件式node!=node->nextの値は制御変数nodeの値のみ
から決まることが言える。停止条件の解析（１３）で
は、図２のループと全く同じ仮定で同じ結論が得られ
る。実際、以下の理由でこの結論は正しい。ノードの数
をｎとすると、番兵となるノードはnode(n)であり、nod
e(n)->nextとnode(n)は等しい。しかし、node(n)->next
をnodeの値としてループの本体が実行されることはな
い。つまり、node(n)->nextの値は条件式でのみ使用さ
れ、ループ本体では使用されないため、ループ本体で使
用されるnodeの関係には影響しないのである。

【００５６】このことから、停止条件を求めるためのよ
り一般的な方法は以下のようになる。即ち、次の条件 条件１：ループ制御変数がポインタである。

【００５７】条件２：ループ制御変数（ｐとする）の更
新式が、p=*(p+c)の形式である。ただし、ｃは定数であ
る（node->nextという式はある定数ｃを用いて＊(node+
c)と表せる）。

【００５８】条件３：ループ停止条件が、p!=qの形式で
ある。ただしｑはループ不変式である。

【００５９】を満たすとき、ループ表のループ停止条件
（２７）に、i==j｜｜p(i)!=p(j)という論理式を設定す
る。ただし、p(i)はループ制御変数ｐのｉ回目の繰り返
しでの値、ｉとｊはループの繰り返し番号である。上記
の条件は、図２のプログラムの停止条件の解析にも適用
できる。

【００６０】ここでは巡回のあるリストの例として番兵
がある場合を用いたが、その他にもリストの最後のノー
ドが先頭のノードを指している、循環リスト(circular
list)と呼ばれるリストや、ノードがその次のノードと
前のノードへのポインタを持つ、双方リスト(doubly li
nked list)と呼ばれるリストなどもある。これらの場合
にも同様の解析が行える。また、与えられた先頭ノード
が真にリスト先頭である必要はなく、リストを途中から
たどる場合にもここに述べた解析方法が適用できる。

【００６１】以上は、本発明をポインタを制御変数とす
るループに適用した時の実施例である。次に、制御変数
が整数のループに対する実施例を説明する。

【００６２】図８はループを含むプログラムの例であ
る。このループについて図１の処理フローに沿って処理
を行うと、フロー解析（５）でループ表が作成され、ル
ープ構成基本ブロック（２１）とループ終了条件式（２
２）が設定される。ループ終了条件式（２２）はこの場
合i==endとなる。停止性判定（８）でループ停止性に真
（ＴＲＵＥ）が設定されたとすると、停止条件解析
（９）は以下のように行われる。ループ制御変数の検出
（１１）では、変数ｉが制御変数として検出される。こ
のｉの初期値（２５）はstart+1であり、更新式（２
６）はi++である。次にループ終了条件式の検査（１
２）では、終了条件式i==endが制御変数ｉとループ不変
変数endの式であるため、停止条件が解析できるための
条件を満たす。

【００６３】このループの停止条件は以下のように求め
られる。もしループが停止するならば、ｉの初期値star
t+1に１を有限回加えると、endと等しくならなければな
らない。このとき明らかにstart<endでなければならな
い。よって、停止条件の解析（１３）では停止条件（２
７）にstart<endを設定する。ただし、ここでは加算の
結果がオーバーフローした場合は不正な値となり、考慮
する必要はないものとする。フロー情報の更新（１４）
では、start<endという条件が成り立つものとして、フ
ロー情報を更新する。例えば、start<iが常に成り立つ
ため、Ｓ３２で値が書き込まれるarray[i]は、array[st
art]ではありえない、従って、ループ中でarray[start]
が書き換えられることはないことがわかる。

【００６４】これまでの実施例はいずれもループの停止
条件の解析方法を述べた。次に、再帰呼び出しに対する
実施例について説明する。

【００６５】図９は再帰呼び出しを含むプログラムの例
である。このプログラムは非巡回有向グラフ（ＤＡＧ；
Ｄirected Ａcyclic Ｇraph）のノードを重複を許し
てたどる。ただし、非巡回であることとは自明ではな
い。ＤＡＧのデータ構造の例を図１０に示す。図では、
ノードを楕円で表し、フィールドleftが指しているノー
ドをＬというラベルのエッジで表し、フィールドright
が指しているノードをＲというラベルのエッジで表して
いる。ＤＡＧでは一つのノードが複数のノードから指さ
れることがあるため、ＤＡＧのノードを順番にたどった
ときに、異なるエッジをたどると同じノードに達する場
合がある。しかし、非巡回であるならば、あるノードか
らエッジに沿ってノードをたどったときに、再びそのノ
ードを訪れることはない。本発明によれば、手続き内の
みの解析でこのことを解析できる。

【００６６】再帰呼び出しの停止条件を解析する際の処
理フローを図１１に示す。図１との相違点を中心に、ど
のような処理が行われるかを説明する。

【００６７】フロー解析（５）では、手続き呼び出し表
（３１）を作成する。手続き呼び出し表（３１）は図１
２に示すフィールドからなる。手続き呼び出し表は、解
析対象の手続きで呼び出される手続き毎に作成される。
呼び出される手続きには、自分自身も含まれる。図１２
のプログラムでは自分自身の呼び出しがＳ４３とＳ４４
の二ケ所あるが、手続き呼び出し表は一つだけ作成され
る。フロー解析の際に、呼び出し先手続き（４１）には
呼び出し先の手続き名dag_traversal()を設定する。実
引数（４２）には、複数の呼び出しがある場合、それぞ
れの呼び出しの実引数の組からなるリストを設定する。
この例では二つの呼び出しがあるため、node->rightとn
ode->leftの二組の実引数が設定される。さらに、再帰
呼び出しの場合には、再帰呼び出しか（４３）に真（Ｔ
ＲＵＥ）または偽（ＦＡＬＳＥ）を設定する。この例で
は再帰呼び出しであるので、真を設定する。さらに、再
帰呼び出しの場合には、その呼び出しが行われないため
の条件を表す論理式を再帰呼び出し終了条件式（４４）
に設定する。この例では、文Ｓ４１のif文の条件が真の
時、再帰呼び出しが行われないので、node==ＮＵＬＬを
設定する。なお、この終了条件式は常に検出できるわけ
ではない。

【００６８】フロー解析（５）で出力されるフロー情報
（６）には、手続き呼び出しによって値が書き換えられ
得る変数の集合が含まれるものとして説明する。文Ｓで
の手続きｐの呼び出しによって、値が書き換えられ得る
変数の集合をＭＯＤ(p,s)で表す。

【００６９】図９のプログラムでは、文４３と文４４で
のdag_traversal()の呼び出しで値の書き換えられ得る
変数は、自分自身への再帰呼び出しであることを考慮し
て、以下のように求められる。

【００７０】 ＭＯＤ(dag_traversal,Ｓ４３）＝{node->value} ＭＯＤ(dag_traversal,Ｓ４４）＝{node->value} 停止性判定（３２）では、再帰呼び出しが停止すること
が保証されるかどうかを、実行時オプションや指示文か
ら判断する。これらの情報は中間コード（４）に含まれ
ている。ここでは、ソースプログラム中に指示文で、関
数dag_traversal()の停止が保証されていることが記述
されていることにして、再帰呼び出し停止性（４５）に
真を設定する。この指示文は、例えば次のようなもので
ある。

【００７１】 ＃pragma ＴＥＲＭＩＮＡＴＥ dag_traversal これはＣ言語の前処理命令＃pragmaを用いて、処理系に
dag_traversal()という手続きの停止性が保証されるこ
とを示している。

【００７２】停止条件解析（３３）では、再帰呼び出し
停止性（４５）が真である手続きについて、その再帰呼
び出しの停止するための必要条件を解析する。再帰呼び
出し制御変数の検出（３５）では、再帰呼び出しを行う
か否かを決定する変数を求める。

【００７３】以下の三つの条件を満たす変数を、再帰呼
び出し制御変数とする。

【００７４】条件１：再帰呼び出し終了条件式でその変
数の値が使用されている。

【００７５】条件２：手続きの仮引数の値からその変数
の値が定まる。

【００７６】条件３：再帰呼び出しの実引数の値がその
変数の値から定まる。

【００７７】上記の条件を満たす変数を決定できなかっ
た場合は、以下の処理を行わない。図９の例で言うと、
仮引数nodeが上記の条件を満たすので、再帰呼び出し制
御変数（４６）に設定する。

【００７８】再帰呼び出し終了条件式の検査（３６）で
は、再帰呼び出し終了条件式（４４）の値が、再帰呼び
出し制御変数（４６）と、手続き内で値が書き換えられ
ることのない変数の値のみから決定できるかどうかを調
べ、その条件を満たさない場合は以下の処理を行わな
い。図９の例で言うと、終了条件式node==ＮＵＬＬは制
御変数と定数のみからなるため、制御変数の値から決定
できる。

【００７９】再帰呼び出し停止条件の解析（３７）で
は、再帰呼び出しが有限回で停止するための必要条件を
求める。ただし、ここで言う再帰呼び出しの回数は、そ
の手続きの通算の呼び出し回数ではなく、同時に実行状
態にあるものの数である。一般に、制御変数をvar、手
続きのｉ回目の再帰呼び出しでのvarの値をvar(i)とす
る。ただし、着目している呼び出しでのvarの値をvar
(0)とする。var(0)が停止条件を満たしている場合は再
帰呼び出しは行われないため、var(0)では停止条件を満
たさないものとする。すると、ループの場合と同様の理
由から、var(0)!=var(i)、だだしｉ＞０、であることが
停止条件となる。このことは、任意のノードから出発し
たエッジに沿ってノードをたどっていった時に、再び最
初のノードに達することがない、ということである。

【００８０】図９のプログラムの停止条件をプログラム
中の変数を用いて表すと、以下のような無限個の不等式
が得られる。

【００８１】node！=node->right node！=node->left node！=node->right->right node！=node->right->leftなど これらの不等式の右辺は正規表現を用いて、nodeの後に
->rightまたは->leftが１個以上連接されたもの全体の
ように表せる。正規表現は広く使用されているので、具
体的な表現方法は省略する。

【００８２】以上から、次の三つの条件 条件１：再帰呼び出し制御変数がポインタである。

【００８３】条件２：実引数が、制御変数をｐとしたと
き＊(p+c)の形式である（ただしｃは定数）。実引数が
複数ある場合はｃの値がそれぞれ異なっていても良い。

【００８４】条件３：停止条件が、仮引数が特定のアド
レスでないことである。

【００８５】を満たす場合に、停止条件（４７）とし
て、p!=*(p+c)などの式を設定する。

【００８６】フロー情報更新（３８）では、再帰呼び出
し停止条件（４７）が求められた時に、その停止条件が
満たされるものとしてフロー情報を更新する。図９の例
では、関数dag_traversal()の中で定義される変数はnos
e->valueのみであり、Ｓ４３とＳ４４から再帰的に呼び
出されるdag_traversal()では、呼び出し側のnodeとは
異なる値をnodeとすることから、これらの呼び出しによ
って呼び出し側のnode->valueの値が変更されることは
ないことがわかる。従って、手続き呼び出しによって値
が書き換えられ得る変数の集合、ＭＯＤ(dag_traversa
l，Ｓ４３）とＭＯＤ(dag_traversal，Ｓ４４）はいず
れも空集合となる。

【００８７】ここでは手続き内解析のみを行うものとし
て説明したが、手続き間解析を行うことにより、他の手
続きの呼び出しを含む場合でも同様の解析を行えるよう
になる場合がある。

【００８８】以上述べてきた実施例はいずれもプログラ
ムの解析のみを行うものであった。以下ではこの解析結
果を利用して、プログラムの最適化を行う実施例を説明
する。

【００８９】本発明を最適化コンパイラに適用した場合
の、コンパイラの処理フローを図１３に示す。フロント
エンド（３）からフロー情報更新（１４）までの処理は
図１や図１１の場合と同様に行われる。最適化（５１）
では、停止条件が成立するものとして解析されたフロー
情報（１５）を利用して、中間コード（４）を最適化す
る。コード生成（５２）では最適化された中間コード
（４）から目的コード（５３）を生成する。この例で
は、既存の方法を利用して最適化を行うため、従来の最
適化方法と比べると、フロー解析の精度が向上すること
による目的コードの質の向上が期待できる。

【００９０】図９のプログラムを例に従来の最適化との
違いを説明する。なお、目的コードとしては機械語プロ
グラムを生成するものとする。

【００９１】従来のフロー情報（６）を用いて最適化を
行った場合に生成される機械語コードを図１４に示す。
従来方式では次のようなコードが生成される。まず、文
Ｓ４２は定数をレジスタにするコード（６１）になる。
ここでＧＲ１はnode->valueの値を保持するレジスタで
ある。文Ｓ４３に対するコード（６２）は、まず、引数
node->rightの値をロードし、引数レジスタＡＲＧ０へ
設定する。そして、呼び出しの手続きでnode->valueの
値が読み込まれる可能性があるため、ＧＲ１をストアし
てから、手続きdag_traversal()を呼び出す。さらに、n
ode->valueの値と手続き呼び出しの戻り値を加えて新た
なnode->valueの値とする。このとき、手続き呼び出し
の際にnode->valueの値が書き換えられている可能性が
あるため、node->valueの値を再ロードする必要があ
る。文Ｓ４４に対するコード（６３）もＳ４３と同様で
ある。最後に、node->valueの値をストアする（６
４）。

【００９２】一方、本発明によって得られたフロー情報
（１５）を用いて最適化を行った場合に生成される機械
語コードを図１５に示す。図１４のコードとの違いは、
文Ｓ４３とＳ４４に対応するの部分、即ち（７２）と
（７３）である。この場合には、手続き呼び出しによっ
てnode->valueの値が読み込まれたの書き込まれたりす
ることがないとわかっているため、node->valueの値を
ストアしたりロードしたりする必要がない。

【００９３】本発明によって得られたフロー情報を利用
することにより、文Ｓ４３とＳ４４に対して、従来はそ
れぞれ５つの命令が生成されていたのが、３命令に削減
されている。これによって、命令数が減少すると共に、
実行時間の短縮が期待できる。

【００９４】前記の実施例では、プログラムの停止性が
成り立つものとして最適化を行っていた。しかし、プロ
グラムによってはこの停止性が成り立つかどうかを実行
時に判定することができる。

【００９５】停止性を実行時に判定する最適化を行うコ
ンパイラの処理フローを図１６に示す。

【００９６】フロントエンド（８１）では、ソースプロ
グラムを読み込み、中間コード（８２）を作成する。こ
のとき、図１のフロントエンド（３）とは異なり、停止
性を指定するための実行時オプションや指示文の処理を
行う必要はない。

【００９７】フロー解析（８３）では、中間コード（８
２）を読み込み、従来のフロー解析を行い、フロー情報
（８４）を生成する。このとき作成されるループ表（８
５）には、ループ停止性のフィールドがないこと以外は
図１のループ表（７）と同一である。

【００９８】フロー解析の後、停止性判定は行わずに、
停止条件解析（８６）を行う。このとき、全てのループ
について停止性が仮定されているものとして、停止条件
を解析する。

【００９９】フロー情報更新（８７）では、従来のフロ
ー情報（８４）に、ループ停止条件の求められた各ルー
プに対して、ループ停止条件が成立する場合のフロー情
報を解析し、従来のフロー情報に付加したフロー情報
（８８）を出力する。

【０１００】最適化（８９）では、従来の最適化に加え
て、以下のような最適化を行う。まず、以下の条件を満
たすループを見つける。

【０１０１】条件１：停止条件が検出されている。

【０１０２】条件２：停止条件を満たすか否かを、ルー
プの実行前に調べることができる。

【０１０３】条件３：停止条件が成立するか否かで、フ
ロー情報に違いがある。

【０１０４】これらの条件に、フロー情報の違いによっ
て実施し得る最適化が異なる、ループの大きさ（命令
数）が大きすぎない、などの条件を付け加えることもで
きる。条件を満たすループを検出できたら、以下の手順
でコード変換を行う。条件分岐の生成（９１）では、ル
ープの停止条件を満たすか否かを調べる条件分岐を作成
する。ループの複写（９２）では、前記条件を満たすル
ープを複製し、前記条件分岐の分岐先のそれぞれがルー
プが実行されるようにする。フロー情報の複写（９３）
では、複製されてできた二つのループのうち、ループ停
止条件を満たす時に実行されるループに対して、停止条
件が満たされる場合のフロー情報を求める。

【０１０５】上記の最適化を図８のループを例に説明す
る。図８のループの停止条件は、start<endである。こ
のループに対するフロー情報更新（８７）では、停止条
件が成立するか否かによってフロー情報が変化すること
のみをループ表に論理値で記録することにする。

【０１０６】このループの停止条件が成り立つか否か
は、ループの実行前に調べることができる。また、停止
条件が成り立つことによってループ中でarray[start]の
値が変わらないことがわかるため、上記の条件１，２，
３を満たす。

【０１０７】図８のループに対して最適化を行った時の
プログラムを、図１７にＣ言語で示す。これは、この様
な最適化は機械語コードを生成する時だけでなく、ソー
スプログラムから同じ言語で記述されたより実行性能の
良い目的コードを生成するような処理系でも実施できる
ことも示している。図１７のラベルＳ５１は文法的には
正しくないが、説明のために記した。図１７で、文Ｓ５
１は条件分岐の生成（９１）で生成された条件分岐であ
る。Ｓ５１からＳ５５までの型宣言及び文は、ループの
複写（９２）でできた、停止条件を満たす時のコードで
ある。一方、Ｓ５６からＳ５７までの文は、停止条件を
満たさない時のコードである。フロー情報の更新（９
３）によって文Ｓ５５ではarray[start]が定義されるこ
とがないとわかるため、array[start]＊ａrray[start]
という式がループ不変式として認識される。文Ｓ５２で
ループの実行前に一度だけ個の式の値を求め、tmpとい
う変数に代入し、ループ内ではtmpの値を用いている。
これによって、停止条件を満たすならば、ループの繰り
返し毎にarray[start]*array[start]という計算をしな
くて済むため、実行時間が短縮されることが期待でき
る。また、停止条件を満たされない場合でも正しい実行
結果を得ることができる。

【０１０８】以上では本発明の最適化コンパイラへの適
用について説明した。次の実施例では、最適化以外にプ
ログラムの検証にも本発明が適用できることを示す。

【０１０９】図１６の最適化方法では、ループの停止条
件が満たされない場合でも正しい結果が得られるように
コード変換を行った。しかし、図８のプログラムでは、
停止条件が満たされない場合には、ループを繰り返して
いるうちに制御変数ｉがint型で表せる値の最大値に達
してしまう。さらにｉの値を増加させようとすると、実
行するシステムによって、オーバーフローによる割り込
みが発生したり、ｉの値が負数になったりする。このよ
うな場合には元のプログラムと同じ振舞をするとはい
え、プログラマの意図した結果ではないことが多い。そ
こで、停止条件を満たさない時は、診断メッセージを出
力するなどしてプログラマに意図しない状況が生じたこ
とを知らせると、プログラムの検証が行い易くなる。

【０１１０】本発明を利用することにより、最適化の一
種として、このような診断メッセージを出力するコード
を付け加えることができる。そのためのコンパイラは、
図１３に示すような処理フローで実現できる。図１３を
用いて説明した他の実施例との違いは、最適化（５１）
において、停止条件を満たすものとしてコード変換を行
うだけでなく、停止条件を満たさない時に診断メッセー
ジを出力するコードを付け加えることである。

【０１１１】図１８は図８のプログラムに対して上記の
最適化を行った例である。図１８のラベルＳ６１は文法
的に正しくないが、説明のために記した。停止条件star
t<endが成立すると仮定することにより、ループ不変式a
rray[start]*array[start]が検出される。Ｓ６１，Ｓ６
３，Ｓ６４，Ｓ６５が最適化されたループである。さら
に、診断メッセージを出力するために、文Ｓ６２を付け
加える。この文は、Ｃ言語の標準ライブラリの関数asse
rt()を用いることにより、停止条件が成り立たない時に
診断メッセージを表示してプログラムの実行を終える。

【０１１２】以上述べてきたように、本発明による静的
解析方法は、プログラムの静的解析を行うだけでなく、
最適化、並列化や検証に応用することができる。また、
プログラムが停止すると仮定して解析を行うだけでな
く、実行時に停止条件が満たされるかを判断することも
可能である。

【０１１３】

【発明の効果】本発明の効果の一つは、プログラムの静
的解析の精度が向上することである。解析精度が向上す
ることにより、プログラムの誤りを発見しやすくした
り、最適化や並列化の効果を高めることができる。もう
一つの効果は、従来の解析方法よりも少ない手間で同等
以上の精度の解析を行うことができることである。

【図面の簡単な説明】

【図１】静的解析方法の処理フローを示す図（１）であ
る。

【図２】リンクトリストをたどるループの例である。

【図３】リンクトリストのノード間の関係を示す図であ
る。

【図４】中間コードを示す図である。

【図５】ループ表の構成を示す図である。

【図６】番兵のいるリストをたどるループの例である。

【図７】番兵のいるリストのノード間の関係を示す図で
ある。

【図８】制御変数が整数型のループの例である。

【図９】ＤＡＧをたどる再帰呼び出しの例である。

【図１０】ＤＡＧのノード間の関係を示す図である。

【図１１】静的解析方法の処理フローを示す図（２）で
ある。

【図１２】手続き呼び出し表の構成を示す図である。

【図１３】最適化コンパイラの処理フローを示す図
（１）である。

【図１４】従来方式によって生成されるコードを示す図
である。

【図１５】本発明によって生成されるコードを示す図で
ある。

【図１６】最適化コンパイラの処理フローを示す図
（２）である。

【図１７】最適化を行った例（１）である。

【図１８】最適化を行った例（２）である。

【符号の説明】

１…ソースプログラム。２…実行時オプション、３…フ
ロントエンド、４…中間コード、 ５…フロー解
析、 ６…フロー情報。

Claims (8)

【特許請求の範囲】
1. 【請求項１】プログラミング言語で記述されたプログラ
   ムを、実行すること無しに解析する方法であって、(ａ)
   ソースプログラムを読み込み、字句解析・構文解析・意
   味解析を行い中間コードを生成するフロントエンドと、
   (ｂ)前記中間コードに対して制御の流れ及びデータの流
   れを解析してフロー情報を生成するフロー解析と、(ｃ)
   プログラムを実行した時に必ず停止すると仮定して良い
   かどうかを判定する停止性判定と、(ｄ)前記停止性判定
   でプログラムが停止すると判定された時、プログラムが
   停止するための必要条件を求める停止条件解析と、(ｅ)
   前記停止するための必要条件が満たされるものとして、
   前記フロー情報を更新するフロー情報更新、の各ステッ
   プを含むことを特徴とするプログラムの静的解析方法。
2. 【請求項２】前記ステップ（ｃ）において、プログラム
   の全体または特定の範囲に含まれるコードの実行によっ
   てプログラムが停止しなくなる可能性があるか否かを、
   静的解析を行うシステムの実行時オプションとして与え
   ることを特徴とする、請求項１記載のプログラムの静的
   解析方法。
3. 【請求項３】前記ステップ（ｃ）において、プログラム
   の全体または特定の範囲に含まれるコードの実行によっ
   てプログラムが停止しなくなる可能性があるか否かを、
   解析対象となるソースプログラム中に記述された指示文
   によって与えることを特徴とする、請求項１記載のプロ
   グラムの静的解析方法。
4. 【請求項４】前記ステップ（ｄ）において、プログラム
   中のループに対して、(ｄ１)ループの繰り返し毎に規則
   的に値が更新され、(ｄ２)ループの終了条件式に使用さ
   れる、変数があるとき、その変数の値に関する制約を、
   そのループの停止する必要条件とすると、請求項１記載
   のプログラムの静的解析方法。
5. 【請求項５】前記ステップ（ｄ）において、プログラム
   中の手続きの再帰呼び出しに対して、(ｄ１)再帰呼び出
   しの際の実引数が、呼び出し側の仮引数の値によって決
   定され、(ｄ２)その再帰呼び出しを行うか否かが前記仮
   引数の値によって決定される、ことを特徴とする再帰呼
   び出しに対して、前記実引数及び仮引数の値に関する制
   約を、その再帰呼び出しが停止する必要条件とする、請
   求項１記載のプログラムの静的解析方法。
6. 【請求項６】前記プログラムの静的解析方法は、さら
   に、(ｆ)ステップ（ｅ）で生成されたフロー情報を用い
   て中間コードをより小さいまたは効率良く実行できる中
   間コードへ変換する最適化と、(ｇ)ステップ（ｆ）で生
   成された中間コードから目的コードを生成するコード生
   成、の各ステップを含むことを特徴とする請求項１記載
   のプログラムの静的解析方法。
7. 【請求項７】前記ステップ（ｄ）及び（ｃ）は、(ｄ)ス
   テップ（ｃ）で求められた条件が満たされるか否かを実
   行時に判定し、(ｄ１)前記条件が満たされる時は、その
   条件が満たされるときのフロー情報に基づいて最適化を
   行ったコードを実行し、(ｄ２)前記条件が満たされない
   時は、診断メッセージを出力する、ように中間コードの
   変換を行うことを特徴とする最適化と、(ｅ)ステップ
   （ｄ）で生成された中間コードから目的コードを生成す
   るコード生成、の各ステップを含むことを特徴とする請
   求項１記載のプログラムの静的解析方法。
8. 【請求項８】前記ステップ（ｃ），（ｄ）、及び（ｅ）
   は、(ｃ)プログラムが停止するとした時に成立する条件
   を求める停止条件解析と、(ｄ)ステップ（ｃ）で求めら
   れた条件が満たされるか否かを実行時に判定し、(ｄ１)
   前記条件が満たされる時は、その条件が満たされるとき
   のフロー情報に基づいて最適化を行ったコードを実行
   し、(ｄ２)前記条件が満たされない時は、その条件が満
   たされるか否かは不明である時のフロー情報に基づいて
   最適化を行ったコードを実行する、ことを特徴とする中
   間コードの変換を行う最適化と、(ｅ)ステップ（ｄ）で
   生成された中間コードから目的コードを生成するコード
   生成、の各ステップを含むことを特徴とする請求項１記
   載のプログラムの静的解析方法。