JPH10116197A - プログラム解析方法 - Google Patents

Abstract

(57)【要約】 【課題】プレディケートが付加されたコードを含むプロ
グラムに対して、正しいデータフロー解析の結果を得る
ことができ、さらにその解析の精度を高めることができ
るプログラム解析方法を提供する。 【解決手段】到達定義設定ステップは、参照を順に辿
り、使用に対する処理では、到達定義リストの中で使用
と定義に付加されたプレディケートが排他関係にないも
のをその使用の到達定義に加える。定義が現われたとき
に行う到達定義リスト更新処理では、到達定義リスト中
の定義に対して、それ以降に現われた定義の集合に対応
するプレディケート集合が到達定義のプレディケートを
包含する場合にその定義を到達定義リストからはずす。 【効果】プレディケートが付加されたコードを含むプロ
グラムに対して、正しいデータフロー解析の結果を得る
ことができ、さらにその解析の精度を高めることができ
る。その結果、冗長な依存を削減でき、命令スケジュー
リングなどの最適化の効果を高めて、プログラムの実行
性能を向上させることができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、プログラム解析方
法に関し、特に条件付き実行コードのデータフロー解析
方法に関する。

【０００２】

【従来の技術】スーパースカラやＶＬＩＷ（Very Long
Instruction Word）などの命令レベル並列を目的と
するマシンにおいて、高速な実行コードを生成するため
に、コンパイラは命令スケジューリングなどの技法を用
いた最適化を実施する。分岐を越えて大域的な命令スケ
ジューリングを実施するための１つの方法に条件付実行
がある。これはプレディケートと呼ばれる真理値を実行
条件として命令中に保持し、プレディケートが真の場合
だけその命令を実行する機構を備えたアーキテクチャに
よるものである。

【０００３】このような条件付実行のコードを生成する
方法は、例えば、マールケ：「イフェクティブ・コンパ
イラ・サポート・フォー・プレディケーティド・エグセ
キューション・ユージング・ザ・ハイパーブロック」、
マイクロ２５、１９９２年、第４５頁から第５４頁(Sco
tt A. Mahlke: Effective Compiler Support for Predi
cated Execution Using the Hyperblock. Proceedings
of the 25th Annual Internattional Symposium on Mic
roarchitecture, MICRO 25, 1992, pp.45-54)に記載さ
れている。上記論文で述べられている方法によれば、ハ
イパーブロックと呼ばれる領域を選択し、ハイパーブロ
ック内の各基本ブロック内に属する命令を条件付実行命
令に変換することにより、ハイパーブロック内の基本ブ
ロック間の分岐を削除する。

【０００４】一般にコンパイラにおいては、多くの最適
化は変数のデータフロー情報を利用する。上述の条件付
実行コードへの変換後にこのような最適化を適用するた
めには、条件付実行コードのデータフロー解析が必要で
ある。データフロー解析に関連する従来技術に関して以
下に記述する。

【０００５】第１の従来技術は、上記マールケの論文に
記載されているもので、ハイパーブロック内の命令をス
ケジューリングする際の解析について述べられている。
ハイパーブロック内の命令をスケジューリングする際に
は、プレディケート変数の関係解析が役に立つ。排他に
実行される２つの命令間には依存がないので、２つの命
令は同時に実行できる。２つの命令が排他に実行される
のは、プレディケートが同時に真とならない場合（この
ような場合にプレディケートが排他であると呼ぶことに
する）である。そこで、命令スケジューリングにあたっ
て、プレディケートが排他関係にあるかどうかを解析す
ることが必要となる。本論文の方法では、プレディケー
トの成立条件を得るために、ハイパーブロック内で定義
されるプレディケート変数に対してプレディケート階層
グラフ（ＰＨＧ）と呼ばれるグラフを生成する。そし
て、２つのプレディケートの条件式の積を計算し、その
結果が０であれば排他と判定する。

【０００６】上記の方法ではハイパーブロックと呼ばれ
る非循環な領域を対象としているが、一般にコンパイラ
は、より広い範囲を対象に最適化および必要な情報の解
析を行う。

【０００７】第２の従来技術は、従来より用いられてい
る条件付実行コードを含まないプログラムの大域的なデ
ータフロー解析に関するものである。大域的なデータフ
ロー解析では、プログラムの制御フローの情報に基づ
き、変数の流れを解析する。大域的なデータフロー解析
の方法については、例えばエイホ：「コンパイラ：原理
・技法・ツール」、アジソン−ウェズレー社、１９８６
年(A. V. Aho: Compilers: Principles, Techniques, a
nd Tools. Addison-Wesley, 1986)に記載されている。
このような解析においては、ある基本ブロックが実行さ
れる場合にはその基本ブロック内の各文は必ず実行さ
れ、制御依存は制御フローのエッジにより表現されると
して扱う。

【０００８】大域的なデータフロー解析の例として、図
４のソースプログラムに対する変数ｖの到達定義解析を
考える。図中に示すように、ｖの各定義をｄ１、ｄ２、
ｄ３、各使用をｕ１、ｕ２、ｕ３とする。本プログラム
に対応する中間語の例を図５に示している。解析の結
果、各使用へ到達する定義の集合は、ｕ１：｛ｄ１｝、
ｕ２：｛ｄ２｝、ｕ３：｛ｄ２，ｄ３｝となる。なお、
ｕ１：｛ｄ１｝は、使用ｕ１へ到達する定義の集合が
｛ｄ１｝であることを示す。

【０００９】

【発明が解決しようとする課題】上記第１の従来技術に
よれば、ハイパーブロック内の命令スケジューリングに
おいて排他命令を検出することができるが、ハイパーブ
ロックを越えたより広い範囲を対象とする最適化に関し
てデータフロー情報を与えることができない。また、プ
レディケートを付加された複数の定義に対して、定義が
キルされるかどうかを解析する手段が提供されていな
い。その結果、本来はキルされているはずの定義との間
に余分な依存が発生し、最適化の妨げになることがあ
る。

【００１０】上記第２の従来技術は、プレディケートの
ないコードを大域的に解析するには有効であるが、同じ
方法をプレディケートを付加されたコードに対して適用
すると不正な結果を得る。この点について例を用いて説
明する。図５の中間語に対してプレディケート付きコー
ドへの変換を実施した中間語の例を図６に示す。ループ
本体のコードは、変換前には複数の基本ブロックによっ
て表現され、基本ブロック間のエッジによって制御依存
が表現されていたが、変換後には単一の基本ブロックと
なり、制御依存がエッジで表現されなくなっている。こ
の中間語に対して従来の方法によるデータフロー解析を
適用すると、各使用へ到達する定義の集合は、ｕ１：
｛ｄ１｝、ｕ２：｛ｄ３｝、ｕ３：｛ｄ３｝となり、不
正な結果が得られる。これは基本ブロック内の文はすべ
て同じ条件で実行されると仮定したためである。実際に
は各文はプレディケートで示される条件に基づき実行さ
れるので、基本ブロック内の文はすべて同じ条件で実行
されるという仮定のもとで従来の方法によるデータフロ
ー解析を適用すると、不正な結果となってしまう。

【００１１】本発明の目的は、プレディケートが付加さ
れたコードを含むプログラムに対して、正しいデータフ
ロー解析の結果を得ることができ、さらにその解析の精
度を高めることができるプログラム解析方法を提供する
ことにある。

【００１２】

【課題を解決するための手段】本発明の目的は、解析対
象の参照に付けられたプレディケートを解析し、プレデ
ィケートの関係を調べるステップによって達成される。

【００１３】即ち本発明の請求項１に係るプログラム解
析方法は、実行文に真偽値による実行条件であるプレデ
ィケートをそれぞれ付加することができ、プレディケー
トが真の場合にだけ通常の実行を行い、偽の場合には実
行結果を無効化または命令発行を無効化する制御を行う
コードを対象にデータフロー解析を行うためのプログラ
ム解析方法であって、解析対象の実行文にプレディケー
トが付加されているかを判定するプレディケート判定ス
テップと、２つの定義ｄ１およびｄ２に対して、定義ｄ
１が定義ｄ２の直前に到達した場合に、定義ｄ１が定義
ｄ２の直後に到達しないかどうか、即ち定義ｄ１が定義
ｄ２でキルされるかどうかを、判定するキル判定ステッ
プとを有し、上記キル判定ステップでは、上記プレディ
ケート判定ステップにより定義ｄ２にプレディケートが
付加されているかどうかを判定し、プレディケートが付
加されている場合には、定義ｄ１が定義ｄ２でキルされ
ないと判定することを特徴とする。

【００１４】請求項２に係るプログラム解析方法は、請
求項１のプログラム解析方法であって、前記キル判定ス
テップでは、前記プレディケート判定ステップにより定
義ｄ１と定義ｄ２にプレディケートが付加されているか
どうかを判定し、共にプレディケートが付加されている
場合には、定義ｄ１のプレディケートｐ１が真の場合に
常に定義ｄ２のプレディケートｐ２が真であるかどう
か、即ちｐ１がｐ２に包含されるかどうかを、判定し、
包含されない場合には定義ｄ１が定義ｄ２でキルされな
いと判定することを特徴とする。

【００１５】請求項３に係るプログラム解析方法は、請
求項１のプログラム解析方法であって、前記キル判定ス
テップでは、定義ｄ２に付加されたプレディケートおよ
び定義ｄ１から定義ｄ２へ至るパス上に現われた定義に
付加されたプレディケートの集合を生成し、定義ｄ１の
プレディケートが真となる条件が、上記プレディケート
集合内の各プレディケートが真となる条件の和に包含さ
れるかどうかを判定し、包含されない場合には、定義ｄ
１が定義ｄ２でキルされないと判定することを特徴とす
る。

【００１６】また、プレディケートを考慮した大域的な
解析を実施するために、基本ブロック内を解析する局所
属性設定ステップと、基本ブロック間で情報を伝播する
データフロー方程式解法ステップと、データフロー方程
式の結果に基づき基本ブロック内の情報を設定するデー
タフロー情報設定ステップとを設ける。局所属性設定ス
テップおよびデータフロー情報設定ステップは、解析対
象の参照に付けられたプレディケートを解析し、プレデ
ィケートの関係を調べる。

【００１７】即ち請求項４に係るプログラム解析方法
は、実行文に真偽値による実行条件であるプレディケー
トをそれぞれ付加することができ、プレディケートが真
の場合にだけ通常の実行を行い、偽の場合には実行結果
を無効化または命令発行を無効化する制御を行うコード
を対象にデータフロー解析を行うためのプログラム解析
方法であって、解析対象のプログラムの各基本ブロック
に対して、基本ブロック内の解析によって得られる情報
を設定する、局所属性設定ステップと、上記局所属性ス
テップで設定された情報を制御フローの上で伝播させる
ことにより、各基本ブロックの入口および出口に対する
情報を求める、データフロー方程式解法ステップとを有
し、上記局所属性設定ステップでは、基本ブロック内に
存在する変数ｖの各定義に付加されたプレディケートの
集合を生成し、上記プレディケートの集合の成立条件が
常に成立するかどうかを判定し、成立する場合には、基
本ブロックの入口に到達したｖの全定義が基本ブロック
出口まで到達できない、即ちｖの全定義はキルされると
してキル属性を設定することを特徴とする。

【００１８】請求項５に係るプログラム解析方法は、請
求項４のプログラム解析方法において、データフロー方
程式解法ステップで得られた、各基本ブロック入口に到
達する定義集合に基づき、基本ブロック内の参照に到達
定義を設定するステップをさらに有し、上記到達定義を
設定するステップは、到達定義集合内の定義を参照の到
達定義に登録する登録ステップと、到達定義集合を更新
する更新ステップとから成り、上記登録ステップでは、
定義と参照に付加されたプレディケートが同時に真にな
らないと判定した場合には、到達定義にその定義の登録
は行わなず、また上記更新ステップでは、到達定義集合
内の定義に付加されたプレディケートと、その定義以降
に現われた定義に付加されたプレディケートの集合との
包含関係を判定することを特徴とする。

【００１９】さらに、定義間のキル関係を解析するため
に、プレディケートの包含関係を解析する。また、複数
の定義によるキルを解析するためには、それらの定義に
付いているプレディケートの集合を生成し、集合内の各
プレディケートの成立条件の和を解析する。

【００２０】即ち請求項６に係るプログラム解析方法
は、請求項１〜５のプログラム解析方法において、プレ
ディケートを付加されたプレディケートの定義文に対
し、定義されるプレディケートとその定義文に付加され
たプレディケートの関係を有向エッジで表現したグラフ
を作成するステップと、２つのプレディケート間に上記
エッジによる経路が存在するかどうかを調べるステップ
とをさらに有し、これらのステップによりプレディケー
ト間の包含関係を解析することを特徴とする。

【００２１】請求項７に係るプログラム解析方法は、請
求項１〜５のプログラム解析方法において、定義される
プレディケートとその定義文に付加されたプレディケー
トの関係を包含関係エッジと呼ぶ有向エッジで表現し、
プレディケートとそのプレディケートの真偽値を反転す
る否定プレディケートとの関係を補集合関係エッジと呼
ぶエッジで表現したグラフを作成するステップと、一方
のプレディケートと補集合関係エッジで結ばれたプレデ
ィケートと、他方のプレディケートとの間に、上記包含
関係エッジによる経路が存在するかどうかを調べるステ
ップとをさらに有し、これらのステップにより、２つの
プレディケートが同時に真になることがないかどうかを
解析することを特徴とする。

【００２２】上記請求項１〜７に記載の解析方法は、コ
ンパイラに適用することにより具現化される。

【００２３】

【発明の実施の形態】以下、図面を用いて本発明の実施
の形態について説明する。

【００２４】図２は、本発明のプログラム解析方法を適
用したコンパイラが稼働する計算機システムの構成図で
ある。この計算機システムは、ＣＰＵ２０１、ディスプ
レイ装置２０２、キーボード２０３、主記憶装置２０
４、および外部記憶装置２０５より構成されている。キ
ーボード２０３により、ユーザからのコンパイラ起動命
令を受け付ける。コンパイラ終了メッセージやエラーメ
ッセージは、ディスプレイ装置２０２に表示される。外
部記憶装置２０５には、ソースプログラム２０６とオブ
ジェクトプログラム２０７が格納される。主記憶装置２
０４には、コンパイラ２０８、コンパイル過程で必要と
なる中間コード２０９、およびプレディケートグラフ２
１０が格納される。コンパイル処理はＣＰＵ２０１によ
って制御され実行される。

【００２５】図３に、図２のシステムで稼動するコンパ
イラ２０８の処理手順を示す。構文解析３０１では、ソ
ースプログラム２０６を入力として字句解析及び構文解
析を行い中間コード２０９を出力する。データフロー解
析３０２では、到達定義の解析やライブ変数の解析など
以下のコンパイラの処理に必要なデータフロー情報の収
集を行う。ｉｆ変換３０３では、中間コード２０９を入
力し、プレディケート付きコードへの変換を行う。プレ
ディケートグラフ作成３０４では、ｉｆ変換３０３で生
成されたプレディケート付きコードを解析し、プレディ
ケートの関係を示すプレディケートグラフ２１０を作成
する。プレディケート付きデータフロー解析３０５で
は、このグラフ２１０を利用したデータフロー解析を実
施する。プレディケートグラフ作成３０４およびプレデ
ィケート付きデータフロー解析３０５は本発明の特徴と
なる部分であるので、後に詳細に説明する。最適化３０
６では、プレディケート付きデータフロー解析３０５で
得られた情報に基づき、レジスタ割り付けや命令スケジ
ューリングなどの最適化を実施する。コード生成３０７
では、中間コード２０９をオブジェクトプログラム２０
７に変換し、出力する。

【００２６】図５に、コンパイラ２０８が出力する中間
コード２０９の例を示す。これは図４のソースプログラ
ムの例に対応している。中間コード２０９は、構文解析
３０１によって生成される。図５の中間コードは、基本
ブロックをエッジで結んだグラフで表現されている。こ
のようなグラフは制御フローグラフと呼ばれている。５
０１から５０９はそれぞれ基本ブロックであり、エッジ
は基本ブロック間の遷移を表している。各基本ブロック
は文の集合により構成されている。

【００２７】図６に、図５の中間コードに対してｉｆ変
換３０３を実施した結果の一例を示す。ｉｆ変換３０３
では、変換の対象領域として、制御フローグラフ上の複
数の基本ブロックから成る非循環な部分を選択する。本
例では、図５の基本ブロックＢ３（５０４）、Ｂ４（５
０５）、Ｂ５（５０７）、Ｂ６（５０６）、Ｂ７（５０
８）を選択する。ｉｆ変換後、これらの基本ブロック
は、図６に示すように１つの基本ブロックＢ３（６０
４）となる。この基本ブロックＢ３（６０４）におい
て、プレディケートが出現する文について説明する。文
６０８では、条件式ｘ＞０を判定し、その結果の真理値
をプレディケートｐ１に設定する。文６０９では、プレ
ディケートｐ１の値が真の場合にｖへの代入を実行す
る。ｐ１の値が偽の場合には代入は実行されない。文６
１０では、プレディケート！ｐ１が真、即ちｐ１が偽の
場合にだけｖへの代入が実行される。文６１１では、プ
レディケートｐ１が真の場合には条件式ｙ＞０の判定結
果の真理値をプレディケートｐ２に設定する。プレディ
ケートｐ１が偽の場合には、プレディケートｐ２に偽を
設定する。文６１２では、プレディケートｐ２の値が真
の場合にａへの代入を実行する。

【００２８】以下、本発明の特徴であるプレディケート
グラフ作成３０４およびプレディケート付きデータフロ
ー解析３０５の処理手順について詳細に説明する。

【００２９】ここではプレディケートの定義文は「ｂ＝
（条件式） ｉｆ ａ」という形（例えば文６１１）で
各プレディケートについて定義は１箇所にしか現われな
いものとする。「ｉｆ ａ」の部分はない場合もある
（例えば文６０８）。この場合には、「ｉｆ ＴＲＵ
Ｅ」という、値が常に１のプレディケートが付いている
と考える。

【００３０】図７に、プレディケートグラフ作成３０４
で作成したプレディケートグラフ２１０の例を示す。本
例は図６の変換結果に対応している。図７において、プ
レディケートグラフの各ノードはプレディケートに対応
する。ノード７０１は値が１のＴＲＵＥプレディケート
を表す。これは、文６０６などのようにプレディケート
をもたない実行文に対するプレディケートと考える。グ
ラフのエッジは２種類あり、包含関係および補集合関係
を表す。プレディケートの組（ａ，ｂ）が包含関係にあ
る、またはａがｂに含まれるとは、プレディケートａが
真の場合には必ずプレディケートｂも真であることを意
味する。このときグラフ上にｂ→ａのエッジを張る。ｂ
をａの包含関係の親と呼ぶ。プレディケートの定義文が
「ｂ＝（条件式） ｉｆ ａ」という形であるとき、ｂ
が真となるのはａが真の場合に限るからａはｂに含まれ
る。図７では、定義文６１１に対応してｐ１→ｐ２のエ
ッジ、即ちノード７０２から７０４へ包含関係エッジが
張られている。補集合関係のエッジはｐと！ｐの間に張
るエッジである。

【００３１】このようなプレディケートグラフを作成し
てプレディケート付きデータフロー解析を行うことによ
りプレディケートの関係が分かれば、その情報は、後に
行う最適化で命令スケジューリングや他の目的に使用で
きる。これにより、プレディケート付きのコードを含む
プログラムに対しても、正しいデータフロー解析の結果
を高精度で得ることができ、その解析結果を用いるレジ
スタ割り付けや命令スケジューリングなどの最適化の効
果が上がる。

【００３２】図８に、プレディケートグラフ作成３０４
の処理手順を示す。

【００３３】ステップ８０１では、ＴＲＵＥプレディケ
ートを示すノードを作成する。このノードは、プレディ
ケートグラフのルートノードとなる。ステップ８０２で
は、未処理の文があるかどうかを判定し、なければ処理
を終了する。あればステップ８０３に進み、次の文を取
り出して処理対象とする。ステップ８０４では、処理中
の文がプレディケートの定義かどうか、即ち代入文で左
辺がプレディケートであるかどうかを判定する。プレデ
ィケートの定義でなければプレディケートグラフ作成の
処理対象とならないのでステップ８０２に戻り、次の文
の処理を行う。プレディケートの定義であればステップ
８０５に進み、その定義文の左辺のプレディケートをｐ
とする。

【００３４】ステップ８０６で、いま処理対象としてい
る定義文がプレディケート付きかどうかを判定する。プ
レディケート付きならばそのプレディケートをｑとし、
ステップ８０７へ進んで、プレディケートグラフ上のｑ
のノードを親ノードとする。このときｑのノードは既に
作成済みであることが必要で、図８の処理手順ではその
ような順序で文が処理されることを仮定している。文の
処理順序がそのような条件を満たしていない場合には、
ｑのノードが未作成ならばこの文の処理を中止してｑの
定義文の処理後に再び処理対象とすればよい。ステップ
８０６でプレディケート付きでない場合にはステップ８
０８へ進み、ＴＲＵＥプレディケートのノードを親ノー
ドとする。ステップ８０９では、プレディケートグラフ
上でｐのノードを作成する。ステップ８１０では、ステ
ップ８０７または８０８で定義した親ノードから、ｐの
ノードへ包含関係エッジを張る。

【００３５】ステップ８１１では、処理対象のプログラ
ムを辿り、！ｐの使用があるかどうかを調べる。使用が
あればプレディケートグラフにノードを作成する必要が
あるので、ステップ８１２で！ｐのノードを作成し、ス
テップ８１３でｐのノードと！ｐのノードとの間に補集
合関係エッジを張る。ステップ８１１で！ｐの使用が無
い場合あるいはステップ８１３の後は、処理対象のプレ
ディケートの定義文に対する処理が終了したので、ステ
ップ８０２に戻り、次の文を処理対象として処理を続け
る。

【００３６】以上で図８の処理手順の説明を終了する。
本処理手順に従い、図６の中間語に対して図７のプレデ
ィケートグラフを作成する処理について説明する。

【００３７】まず、ステップ８０１でルートノード７０
１を作成する。その後、各文を順に調べていくが、文６
０１〜６０７はプレディケートの定義ではないのでステ
ップ８０５には進まない。文６０８の処理で、ステップ
８０４でプレディケートの定義であると判定する。ステ
ップ８０６ではプレディケート付きでないと判定するの
で、ステップ８０８、８０９と進み、ｐ１のノード７０
２を作成し、ステップ８１０でノード７０１からノード
７０２への包含関係エッジが張られる。ステップ８１１
で！ｐ１の使用があるかどうかを調べ、文６１０に使用
があるのでステップ８１２に進み、！ｐ１のノード７０
３を作成する。ステップ８１３でノード７０２とノード
７０３の間に補集合関係エッジを張る。

【００３８】さらに各文の処理を続け、文６１１の処理
で、ステップ８０４でプレディケートｐ２の定義である
と判定する。ステップ８０６でプレディケートｐ１付き
であると判定されるので、ステップ８０７へ進み、ｐ１
のノード７０２を親ノードとする。そしてステップ８０
９でｐ２のノード７０４を作成し、ステップ８１０でｐ
１のノード７０２からｐ２のノード７０４へ包含関係エ
ッジを張る。残りの文の処理を続け、処理を終了する。
この結果、図７のプレディケートグラフが作成される。

【００３９】以上でプレディケートグラフ作成３０４に
関する説明を終了する。

【００４０】次に、プレディケート付きデータフロー解
析３０５の処理手順について詳細に説明する。ここでは
プレディケート付きデータフロー解析の一例として、到
達定義解析について説明する。他のデータフロー解析の
手法に関しても同様に適用可能である。

【００４１】図９に、到達定義解析の処理手順を示す。

【００４２】ステップ９０１では、各基本ブロックＢに
対して、局所属性ｇｅｎ（Ｂ）、ｋｉｌｌ（Ｂ）を設定
する。ｇｅｎ（Ｂ）は当該基本ブロックＢにおいて生成
される定義の集合、ｋｉｌｌ（Ｂ）は当該基本ブロック
Ｂにおいて消滅される定義の集合である。通常の到達定
義解析と異なり、本ステップではプレディケートを考慮
して局所属性を設定する。本ステップの詳細は後述す
る。

【００４３】ステップ９０２では、図中に示したデータ
フロー方程式の解法により、各基本ブロックＢに対して
ｉｎ（Ｂ）を求める。本ステップは通常のデータフロー
方程式の解法と同様である。即ち、各基本ブロックＢに
対してエッジを辿りながら、各基本ブロックＢの入口に
到達する定義の集合であるｉｎ（Ｂ）と出口に到達する
定義の集合であるｏｕｔ（Ｂ）とを順次求めていく。Ｐ
ＲＥＤ（Ｂ）は、基本ブロックＢの直前の基本ブロック
の集合である。ｉｎ（Ｂ）は、基本ブロックＢの直前の
基本ブロックＰのｏｕｔ（Ｐ）の和集合になる。ｏｕｔ
（Ｂ）は、ｇｅｎ（Ｂ）と（ｉｎ（Ｂ）−ｋｉｌｌ
（Ｂ））との和集合になる。

【００４４】ステップ９０３では、各基本ブロックＢに
対して、ステップ９０２で求めたｉｎ（Ｂ）を基に、基
本ブロックＢ内の各使用に到達定義を設定する。この
際、プレディケートを考慮した解析を実施する。本ステ
ップの詳細は後述する。

【００４５】図１０に、ステップ９０１の詳細な手順を
示す。特に図１０は、１つの基本ブロックＢへの局所属
性設定の処理手順を示したものである。図１０の各ステ
ップについて説明する。

【００４６】ステップ１００１では定義の集合であるｇ
ｅｎ（Ｂ）およびｋｉｌｌ（Ｂ）、並びに、プレディケ
ートの集合ｐｓｅｔを空集合に初期化する。

【００４７】ステップ１００２で、処理対象の基本ブロ
ックＢの先頭文を取り出す。ステップ１００３では、処
理中の文が変数ｖの定義文であるかどうかを判定する。
一般に到達定義解析は全変数について同時に実施できる
が、ここでは簡単のため、１つの変数ｖの解析について
説明している。他の変数の解析も同様に行えばよい。ス
テップ１００３でｖの定義でない場合にはこの文の処理
を終了し、ステップ１００９に進む。ｖの定義である場
合にはその定義をｄとし、ステップ１００４に進む。ス
テップ１００４では、ｇｅｎ（Ｂ）に定義ｄを追加す
る。ステップ１００５では、ｖの定義文がプレディケー
ト付きであるかどうかを判定する。そうであればステッ
プ１００６に進み、そうでない場合にはステップ１００
９に進む。

【００４８】ステップ１００６では、ｖの定義文に付い
ているプレディケートを集合ｐｓｅｔに追加する。ステ
ップ１００７では、ｐｓｅｔが恒真（ｐｓｅｔが恒真と
はｐｓｅｔの成立条件が常に成立する場合をいう。恒真
かどうかは、ｐｓｅｔ中の各プレディケートの成立条件
の和が１になるかどうかを調べればよい。）であるかど
うかを判定する。本判定の詳細については後で説明す
る。恒真であれば、ステップ１００８に進み、そうでな
い場合にはステップ１００９に進む。

【００４９】ステップ１００８では、ｋｉｌｌ（Ｂ）に
ｖの全ての定義の集合を設定し、ステップ１００９に進
む。ｖの全ての定義とは、いま処理対象にしているプロ
グラム全体中にあるｖの全ての定義のことである。取り
出した文がプレディケート付きでない場合、およびプレ
ディケート付きだがｐｓｅｔが恒真の場合は、他の全定
義はキルされるものとしてｋｉｌｌ（Ｂ）に設定すると
いうことである。ステップ１００５でプレディケートが
付加されていると判定した場合であってｐｓｅｔが恒真
で無い場合は、処理対象であるｖの定義の直前に到達し
た定義はキルされないことになる。

【００５０】ステップ１００９では、次の文があるかど
うかを判定し、なければ処理を終了する。あればステッ
プ１０１０に進み、次の文を取り出し、ステップ１００
３に戻って処理を続ける。

【００５１】図１は、ステップ９０３の到達定義設定の
処理手順の詳細を示したものである。特に図１は、１つ
の基本ブロックＢに対する到達定義設定の処理手順を示
したものであり、ここでも１つの変数ｖに着目して説明
する。以下、図１の各ステップについて説明する。

【００５２】ステップ１０１では、ｄｅｆｌｉｓｔをｉ
ｎ（Ｂ）により初期化する。ステップ１０２では、基本
ブロックＢの先頭文を取り出す。ステップ１０３では、
取り出した文中に変数ｖの使用があるかどうかを調べ
る。ある場合にはその使用をｕｓｅとし、ステップ１０
４に進む。ない場合にはステップ１０９に進む。

【００５３】ステップ１０４からステップ１０８は、処
理中の使用に対して到達定義を設定する処理である。プ
レディケート付きでないコードからなるプログラムの解
析では、ある定義ｄｅｆが使用ｕｓｅに到達するとその
ｕｓｅとｄｅｆとの間に依存があるということになり到
達定義集合に入れる必要があるが、ここではプレディケ
ート付きのものの解析であるので、プレディケートの関
係を考慮して到達定義を設定する必要がある。即ち、ｕ
ｓｅとｄｅｆの両方にプレディケートが付いておりそれ
らが排他のときは実際には依存が無いということだから
到達定義に入れる必要が無い。ステップ１０４〜１０８
はそのような処理で到達定義集合を設定している。

【００５４】まずステップ１０４では、ｄｅｆｌｉｓｔ
中に未処理の定義があるかどうかを調べる。ある場合に
はその未処理の定義を１つ取り出してｄｅｆとし、ステ
ップ１０５に進む。ない場合にはステップ１０９に進
む。ステップ１０５では、ｕｓｅがプレディケート付き
の使用であるか、即ち処理中の文がプレディケート付き
かどうかを調べる。そうである場合にはそのプレディケ
ートをｐ１として、ステップ１０６に進む。そうでない
場合にはステップ１０８に進む。ステップ１０６では、
ｄｅｆｌｉｓｔ中の定義ｄｅｆがプレディケート付きか
どうかを調べる。そうである場合にはそのプレディケー
トをｐ２として、ステップ１０７に進む。そうでない場
合にはステップ１０８に進む。

【００５５】ステップ１０７では、２つのプレディケー
トｐ１とｐ２が排他であるかどうかを調べる。排他であ
るかどうかの判定方法については後で説明する。排他で
あればステップ１０４に戻り、次の定義を取り出して処
理を続ける。そうでなければステップ１０８に進む。ス
テップ１０８では、ｕｓｅの到達定義リストにｄｅｆを
追加し、ステップ１０４に戻って次の定義の処理を続け
る。

【００５６】ステップ１０９では、処理中の文が変数ｖ
の定義文であるかどうかを判定する。そうである場合に
はステップ１１０に進み、その後ステップ１１１に進
む。そうでない場合にはステップ１１１に進む。ステッ
プ１１０では、到達定義のリストであるｄｅｆｌｉｓｔ
を更新する。ステップ１１０に進むのは、変数ｖの定義
文にｄｅｆｌｉｓｔが到達した場合である。この場合、
新しい定義が現れたので今までの定義はキルされること
になり、通常の解析ではｄｅｆｌｉｓｔを空集合にす
る。しかし、ここではプレディケート付きのものの解析
であるので、そのプレディケートの関係を見ながらｄｅ
ｆｌｉｓｔを更新する必要がある。その処理が図１１の
手順である。

【００５７】図１１に、ステップ１１０の処理手順の詳
細を示す。以下、図１１の各ステップを説明する。

【００５８】ステップ１１０１では、処理対象であるｖ
の定義をｎｅｗｄｅｆとする。ステップ１１０２では、
ｎｅｗｄｅｆがプレディケート付きかどうかを判定す
る。プレディケート付きである場合には、そのプレディ
ケートをｐとしてステップ１１０３に進む。そうでない
場合には、ステップ１１０７へ進む。ステップ１１０３
では、ｄｅｆｌｉｓｔに未処理の要素があるかどうかを
調べ、あればその１つをｄｅｆとしてステップ１１０４
に進む。なければステップ１１０８に進む。

【００５９】ｄｅｆｌｉｓｔに属する各定義ｄｅｆは、
それぞれプレディケート集合を保持している。各定義の
プレディケート集合は、（自分に付いていたプレディケ
ートではなく）自分より後に現われた定義たちのプレデ
ィケートを集めたものである。ステップ１１０４では、
ｄｅｆのプレディケート集合にｐを加える。このプレデ
ィケート集合は、ｄｅｆよりも後に現われた定義に付く
プレディケートの集合である。ステップ１１０５では、
ステップ１１０４で更新したｄｅｆのプレディケート集
合が、ｄｅｆのプレディケートを包含するかどうかを判
定する。プレディケート集合とプレディケートの間の包
含関係の判定については後で説明する。包含する場合に
はステップ１１０６に進み、そうでない場合にはステッ
プ１１０３に戻る。ステップ１１０６では、ｄｅｆｌｉ
ｓｔからｄｅｆをはずす。ｄｅｆのプレディケート集合
がｄｅｆのプレディケートを包含するなら、ｄｅｆｌｉ
ｓｔからｄｅｆをはずしてよい。これは、ｄｅｆよりも
後に現れた定義のプレディケートを集めたプレディケー
ト集合の方がｄｅｆのプレディケートより大きいので、
後から現れた定義のうちのどれかは１回は実行されたと
いうことになり、ｄｅｆはキルされたとして良いからで
ある。ステップ１１０６の後、ステップ１１０３に戻
る。

【００６０】ステップ１１０７では、ｄｅｆｌｉｓｔを
空リストにする。ステップ１１０８では、ｎｅｗｄｅｆ
をｄｅｆｌｉｓｔに追加する。図１１の処理では、ステ
ップ１１０２でｎｅｗｄｅｆがプレディケート付きであ
る場合であって、ステップ１１０５でＮｏに進む場合
は、ｎｅｗｄｅｆの直前に到達した定義（ｄｅｆｌｉｓ
ｔの要素）はキルされないことになる。

【００６１】以上で図１１の処理手順の説明を終了し、
図１の処理手順の説明に戻る。

【００６２】ステップ１１１では、基本ブロック内に次
の文があるかどうかを判定する。なければ処理を終了す
る。あればステップ１１２に進み、次の文を取り出し、
ステップ１０３に戻り処理を続ける。

【００６３】以上で図１の到達定義設定の処理手順の説
明を終える。

【００６４】以上で説明した、図１０、図１、および図
１１の処理手順の中で、プレディケートに関する関係を
判定した。ステップ１００７ではプレディケート集合が
恒真かどうかの判定、ステップ１０７では２つのプレデ
ィケートが排他かどうかの判定、ステップ１１０５では
プレディケートとプレディケート集合の間の包含関係の
判定を実施する。以下、これらの関係を解析する方法に
ついて説明する。一般にプレディケートの関係を判定す
る方法としては、プレディケートの成立条件式の演算に
よる方法があるが、ここではプレディケートグラフ２１
０のエッジを利用した解析方法を述べる。

【００６５】まず最初に２つのプレディケートの排他関
係について述べる。２つのプレディケートｐ１、ｐ２に
対して、「ｐ１が真ならばｐ２は偽」かつ「ｐ２が真な
らばｐ１は偽」が常に成り立つ場合にｐ１とｐ２とは排
他関係にあるという。条件式による解析の場合、ｐ１の
成立条件とｐ２の成立条件の共通範囲がない場合、排他
関係にある。

【００６６】図１２に、排他関係検出の処理手順を示
す。本処理では２つのプレディケートｐ１とｐ２が排他
であるかどうかを判定する。判定はプレディケートグラ
フ２１０を利用する。各ステップについて説明する。

【００６７】ステップ１２０１では、ｐ１とｐ２が補集
合関係であるかどうかを調べる。プレディケートグラフ
上のｐ１とｐ２のノードを見つけ、２つのノード間に補
集合関係エッジが張られているかどうかで判定する。補
集合関係である場合にはステップ１２１０に進み、排他
関係であると判定して処理を終了する。そうでない場合
にはステップ１２０２に進む。

【００６８】ステップ１２０２では、ｐ１をｐとする。
ステップ１２０３では、ｐを包含する親があるか、即ち
グラフ上でｐのノードへの包含関係エッジが張られてい
るかを調べる。あればステップ１２０４に進み、その親
をｐとする。なければステップ１２０６に進む。ステッ
プ１２０５ではｐとｐ２が補集合関係であるかを調べ
る。そうである場合にはステップ１２１０に進み、排他
関係であると判定して処理を終了する。そうでない場合
にはステップ１２０３に戻り、包含関係の親を辿る処理
を繰り返す。

【００６９】ステップ１２０６から１２０９までは、ス
テップ１２０２から１２０５までの処理のｐ１とｐ２と
を入れ替えたもので、同様の処理を行う。但し、ステッ
プ１２０７で包含関係の親がなくなったらステップ１２
１１へ進み、ｐ１とｐ２は排他関係でないと判定して処
理を終了する。

【００７０】以上で図１２の処理手順の説明を終了す
る。

【００７１】次に、プレディケート集合について説明す
る。プレディケート集合ｐｓｅｔ＝｛ｐ１，．．．，ｐ
ｎ｝に対する成立条件として、各要素の成立条件の和を
対応させる。ｐｓｅｔの成立条件が満たされていると
き、ｐｓｅｔは真であると呼ぶ。

【００７２】図１３は、恒真プレディケート集合検出の
処理手順を示している。集合ｐｓｅｔが恒真とは、ｐｓ
ｅｔの成立条件が常に成立する場合を指す。条件式の解
析により恒真集合を判定する方法としては、各プレディ
ケートの成立条件の和が１になるかどうかを調べればよ
い。本処理手順ではプレディケートグラフの補集合エッ
ジを利用した方法を示している。

【００７３】ステップ１３０１では、プレディケート集
合内の２つの要素の組合せを対象に、それらの要素が補
集合関係にあるか、即ち２つのノード間に補集合関係エ
ッジがあるかどうかを調べる。補集合関係にある組が見
つかったらステップ１３０２へ進み、恒真であると判定
して処理を終了する。全ての組合せを調べた結果、補集
合関係の組が見つからなかった場合にはステップ１３０
３へ進み、恒真でないと判定して処理を終了する。

【００７４】図１４は、プレディケートｐがプレディケ
ート集合に包含されるかどうかを判定する処理手順を示
している。プレディケートとプレディケート集合の包含
関係については、成立条件の演算により判定することも
できるが、ここではプレディケートグラフを用いた簡易
的な判定を示している。

【００７５】ステップ１４０１では、図１３の処理手順
に従い、プレディケート集合が恒真かどうかを判定す
る。恒真ならばあらゆるプレディケートを包含するか
ら、ステップ１４０８へ進み、包含関係にあると判定し
て処理を終了する。恒真でない場合にはステップ１４０
２へ進む。

【００７６】ステップ１４０２では、未処理の集合要素
があるかどうかを判定する。ある場合にはステップ１４
０３へ進む。ない場合にはステップ１４０９に進み、包
含関係にないと判定して処理を終了する。

【００７７】ステップ１４０３では、プレディケート集
合の未処理の要素を１つ取り出し、ｑとする。

【００７８】ステップ１４０４からステップ１４０７
は、２つのプレディケート間の包含関係、即ちｑがｐを
包含するか否かを判定する処理である。まずステップ１
４０４で、ｐのノードをｐ１と置く。ステップ１４０５
では、ｐ１への包含エッジがあるかどうかを判定する。
ない場合にはステップ１４０２に戻り、次の要素を対象
に処理を行う。ある場合はステップ１４０６に進む。ス
テップ１４０６では、包含エッジの親ノードをｐ１とす
る。ステップ１４０７では、ｐ１がｑと等しいかどうか
を判定する。そうである場合にはｑはｐの包含エッジを
辿ったパス上にあり、ｑはｐを包含するので、ステップ
１４０８へ進み包含関係にあると判定する。そうでない
場合にはステップ１４０５へ戻り、さらに包含エッジの
親を辿る。

【００７９】以上でプレディケートの関係解析の方法の
説明、および本発明の実施の形態の処理手順の説明を終
了する。

【００８０】次に、図４のプログラムを例に、以上で説
明した到達定義の解析の処理過程を述べる。解析対象と
なる中間語は図６に示したものである。ｖを解析対象の
変数とする。図６中のｄ１、ｕ１などは、ｖの各定義、
使用に対応している。

【００８１】図９のステップ９０１では、図１０の処理
手順に従い、局所属性の設定を行う。図６のＢ３以外の
基本ブロックについては、ｖが参照されないので、ｇｅ
ｎおよびｋｉｌｌは空集合となる。基本ブロックＢ３の
処理について、図１０に従い説明する。

【００８２】ステップ１００１で初期化を行い、ステッ
プ１００２で先頭の文６０６を取り出す。ステップ１０
０３の判定で、文６０６はｖの定義であるので、ステッ
プ１００４に進み、ｇｅｎ（Ｂ３）に定義ｄ１を追加す
る。この結果、ｇｅｎ（Ｂ３）＝｛ｄ１｝となる。ステ
ップ１００５で文６０６はプレディケート付きでないと
判定されるので、ステップ１００８へ進み、ｋｉｌｌ
（Ｂ３）＝｛ｄ１，ｄ２，ｄ３｝とする。

【００８３】以上で文６０６の処理が終了するので、引
き続き文６０７、６０８と処理を行い、文６０９でステ
ップ１００４に達する。ここでｇｅｎ（Ｂ３）＝｛ｄ
１，ｄ２｝となる。文６０９はプレディケート付きであ
るので、ステップ１００６に進み、ｐｓｅｔ＝｛ｐ１｝
となる。ステップ１００７では、図７のプレディケート
グラフを利用して図１３の処理手順に従い、ｐｓｅｔが
恒真かどうかを判定する。ｐｓｅｔは要素が１つなの
で、ステップ１３０１で補集合関係の組は存在せず、恒
真でないと判定され、ステップ１００９へ進む。

【００８４】次に文６１０の処理を行う。ステップ１０
０４で、ｇｅｎ（Ｂ３）＝｛ｄ１，ｄ２，ｄ３｝とな
る。ステップ１００６でｐｓｅｔ＝｛ｐ１，！ｐ１｝と
なり、ステップ１００７で恒真かどうかを判定する。図
１３のステップ１３０１で補集合関係の組（ｐ１，！ｐ
１）を見つけるので、ｐｓｅｔは恒真集合と判定され
る。ステップ１００８では、ｋｉｌｌ（Ｂ３）＝｛ｄ
１，ｄ２，ｄ３｝が再設定される。

【００８５】以下、各文の処理を続けるがｖの定義は現
われない。従って、変数ｖに対する局所属性設定の結果
は、ｇｅｎ（Ｂ３）＝｛ｄ１，ｄ２，ｄ３｝、ｋｉｌｌ
（Ｂ３）＝｛ｄ１，ｄ２，ｄ３｝となる。

【００８６】次に、ステップ９０２でデータフロー方程
式を解く。基本ブロックＢ３についてはｉｎ（Ｂ３）＝
｛ｄ１，ｄ２，ｄ３｝が求められる。

【００８７】次に、ステップ９０３で、図１および図１
１の処理手順に従い、到達定義を設定する。基本ブロッ
クＢ３の処理過程を説明する。

【００８８】ステップ１０１では、ｄｅｆｌｉｓｔ＝
｛ｄ１，ｄ２，ｄ３｝が設定される。

【００８９】先頭の文６０６はｖの定義文であるので、
ステップ１１０でｄｅｆｌｉｓｔの更新を行う。ステッ
プ１１０１で、定義ｄ１をｎｅｗｄｅｆとおく。ｎｅｗ
ｄｅｆはプレディケート付きでないので、ステップ１１
０７へ進み、ｄｅｆｌｉｓｔ＝｛｝となる。さらにステ
ップ１１０８により、ｄｅｆｌｉｓｔ＝｛ｄ１｝とな
る。

【００９０】次に文６０７の処理に進む。文６０７には
ｖの使用ｕ１があるのでステップ１０４に進み、ｄｅｆ
ｌｉｓｔ中の定義ｄ１を取り出してステップ１０５へ進
む。文６０７はプレディケート付きでないのでステップ
１０８へ進み、ｕ１の到達定義は｛ｄ１｝となる。ステ
ップ１０４に戻り、ｄｅｆｌｉｓｔに未処理の定義がな
いのでステップ１０９へ進み、文６０７の処理を終了す
る。

【００９１】次にｖが現われる文は文６０９である。こ
の文はｖの定義文であるので、ステップ１１０でｄｅｆ
ｌｉｓｔの更新を行う。ステップ１１０１でｄ２をｎｅ
ｗｄｅｆとおく。ステップ１１０２でプレディケート付
きと判定し、ステップ１１０３へ進む。ステップ１１０
３ではｄｅｆｌｉｓｔ中のｄ１を取り出す。ステップ１
１０４で、ｄ１のプレディケート集合に文６０９のプレ
ディケートｐ１を加える。ｄ１のプレディケート集合は
｛ｐ１｝となる。ｄ１はプレディケート付きでないの
で、ｄ１のプレディケートをＴＲＵＥと考え、ステップ
１１０５ではＴＲＵＥが｛ｐ１｝に包含されるかどうか
を判定する。図１４の処理手順に従い、包含されないと
判定するので、ステップ１１０３へ戻る。ｄｅｆｌｉｓ
ｔに未処理の要素がないので、ステップ１１０８へ進
む。ｄ２をｄｅｆｌｉｓｔに加え、ｄｅｆｌｉｓｔ＝
｛ｄ１，ｄ２｝となる。

【００９２】次に文６１０の処理を行う。この文はｖの
定義文であるので、ステップ１１０でｄｅｆｌｉｓｔの
更新を行う。ｄ３はプレディケート付きであるので、ス
テップ１１０１、１１０２を経てステップ１１０３へ進
む。ｄｅｆｌｉｓｔ中の定義ｄ１を取り出す。ステップ
１１０４でｄ１のプレディケート集合にｄ３のプレディ
ケート！ｐ１を加える。ｄ１のプレディケート集合は
｛ｐ１，！ｐ１｝となる。ステップ１１０５でｄ１のプ
レディケートＴＲＵＥが｛ｐ１，！ｐ１｝に含まれるか
どうかを判定する。ステップ１４０１でプレディケート
集合が恒真集合と判定され、包含関係にあると判定され
るので、ステップ１１０６に進む。ステップ１１０６
で、ｄｅｆｌｉｓｔからｄ１をはずし、ｄｅｆｌｉｓｔ
＝｛ｄ２｝とする。ステップ１１０３へ戻り、ｄｅｆｌ
ｉｓｔ中の定義ｄ２を取り出して処理を続ける。ステッ
プ１１０４でｄ２のプレディケート集合は｛！ｐ１｝と
なり、ステップ１１０５では包含しないと判定する。ス
テップ１１０３に戻り、ｄｅｆｌｉｓｔに未処理の定義
はないのでステップ１１０８へ進む。ｄｅｆｌｉｓｔに
ｄ３を追加し、ｄｅｆｌｉｓｔ＝｛ｄ２，ｄ３｝とな
る。

【００９３】次に文６１２の処理を説明する。ステップ
１０４でｄｅｆｌｉｓｔ中の定義ｄ２を取り出す。ステ
ップ１０５でｕ２のプレディケートはｐ２、ステップ１
０６でｄ２のプレディケートはｐ１が付いていることを
判定し、ステップ１０７へ進む。ステップ１０７では図
１２に従い、ｐ２とｐ１とは排他関係でないと判定す
る。ステップ１０８へ進み、ｕ２の到達定義にｄ２を加
える。次にステップ１０４へ戻り、ｄｅｆｌｉｓｔ中の
定義ｄ３を取り出す。ステップ１０７で、ｕ２のプレデ
ィケートｐ２とｄ３のプレディケート！ｐ１が排他かど
うかを調べる。図１２の処理手順において、ステップ１
２０１で２つのプレディケートは補集合関係でないの
で、ステップ１２０２に進む。ステップ１２０３でｐ２
を包含する親プレディケートｐ１を見つける。ステップ
１２０５でｐ１と！ｐ１は補集合関係にあると判定し、
ｐ２と！ｐ１は排他関係であると判定する。従って、ス
テップ１０７で排他関係と判定するので、ｄ３は到達定
義には加えられず、ステップ１０４へ戻り、ｄｅｆｌｉ
ｓｔ中の定義は処理済みであるので、ステップ１０９へ
進む。この結果、ｕ２の到達定義は｛ｄ２｝となる。

【００９４】次に文６１３の処理を説明する。ｄｅｆｌ
ｉｓｔ中の定義ｄ２、ｄ３に対する処理において、ステ
ップ１０５でｕ３はプレディケート付きでないと判定
し、ステップ１０８でこれらの定義をｕ３の到達定義に
加える。この結果、ｕ３の到達定義は｛ｄ２，ｄ３｝と
なる。

【００９５】以上に説明した処理の結果、ｖの各使用へ
の到達定義は、ｕ１：｛ｄ１｝、ｕ２：｛ｄ２｝、ｕ
３：｛ｄ２，ｄ３｝となる。これは、図５に示したｉｆ
変換前の中間語に対してプレディケートを考慮しない通
常の解析を行った場合に得られる結果と同じである。こ
のように、プレディケート付きコードを含むプログラム
に対しても正しい到達定義を求めることができるので、
求めた結果を用いて命令スケジューリングなどの最適化
を効率良く行うことができる。

【００９６】以上で図６の中間語に対する処理過程の説
明を終了する。

【００９７】

【発明の効果】本発明によれば、プレディケート付きの
コードを含むプログラムのデータフロー解析において、
プレディケートを考慮した解析を実施するので、正しい
データフロー解析の結果を得ることができる。また、２
つのプレディケート間の関係や、複数のプレディケート
の集合と１つのプレディケートの間の関係を解析するこ
とにより、解析の精度を高めることができる。

【００９８】解析の精度向上の結果、解析結果を用いる
レジスタ割り付けや命令スケジューリングなどの最適化
の効果が上がり、オブジェクトコードの実行性能向上に
つながる。

【図面の簡単な説明】

【図１】本発明に係る解析方法における到達定義設定の
処理手順を示す。

【図２】本発明に係る解析方法を用いたコンパイラが稼
働するシステムの構成図を示す。

【図３】本発明に係る解析方法を用いたコンパイラの処
理手順を示す。

【図４】ソースプログラムの一例である。

【図５】図４のプログラムに対する中間語の一例であ
る。

【図６】図５のプログラムに対してｉｆ変換を適用し、
プレディケート付きコードへの変換を行った後の中間語
の一例である。

【図７】プレディケートの関係を解析するためのプレデ
ィケートグラフの一例である。

【図８】本発明に係る解析方法におけるプレディケート
グラフ作成の処理手順を示す。

【図９】本発明に係る解析方法における到達定義解析の
処理手順を示す。

【図１０】本発明に係る解析方法の到達定義解析におけ
る局所属性設定の処理手順を示す。

【図１１】本発明に係る解析方法の到達定義解析におけ
る到達定義リスト更新の処理手順を示す。

【図１２】本発明に係る解析方法におけるプレディケー
トの排他関係を検出する処理手順を示す。

【図１３】本発明に係る解析方法において、プレディケ
ートの集合に対して恒真かどうかを判定する処理手順を
示す。

【図１４】本発明に係る解析方法におけるプレディケー
トの包含関係を検出する処理手順を示す。

【符号の説明】

１０５、１０６・・・プレディケートのチェック、１０
７・・・プレディケートの排他チェック、２１０・・・
プレディケートグラフ、３０５・・・プレディケート付
きデータフロー解析、９０１・・・局所属性の設定、９
０３・・・到達定義の設定、１１０５・・・プレディケ
ートの包含関係のチェック。

Claims (7)

【特許請求の範囲】
1. 【請求項１】実行文に真偽値による実行条件であるプレ
   ディケートをそれぞれ付加することができ、プレディケ
   ートが真の場合にだけ通常の実行を行い、偽の場合には
   実行結果を無効化または命令発行を無効化する制御を行
   うコードを対象にデータフロー解析を行うためのプログ
   ラム解析方法であって、 解析対象の実行文にプレディケートが付加されているか
   を判定するプレディケート判定ステップと、 ２つの定義ｄ１およびｄ２に対して、定義ｄ１が定義ｄ
   ２の直前に到達した場合に、定義ｄ１が定義ｄ２の直後
   に到達しないかどうか、即ち定義ｄ１が定義ｄ２でキル
   されるかどうかを、判定するキル判定ステップとを有
   し、 上記キル判定ステップでは、上記プレディケート判定ス
   テップにより定義ｄ２にプレディケートが付加されてい
   るかどうかを判定し、プレディケートが付加されている
   場合には、定義ｄ１が定義ｄ２でキルされないと判定す
   ることを特徴とするプログラム解析方法。
2. 【請求項２】請求項１のプログラム解析方法であって、 前記キル判定ステップでは、 前記プレディケート判定ステップにより定義ｄ１と定義
   ｄ２にプレディケートが付加されているかどうかを判定
   し、共にプレディケートが付加されている場合には、定
   義ｄ１のプレディケートｐ１が真の場合に常に定義ｄ２
   のプレディケートｐ２が真であるかどうか、即ちｐ１が
   ｐ２に包含されるかどうかを、判定し、包含されない場
   合には定義ｄ１が定義ｄ２でキルされないと判定するこ
   とを特徴とするプログラム解析方法。
3. 【請求項３】請求項１のプログラム解析方法であって、 前記キル判定ステップでは、 定義ｄ２に付加されたプレディケートおよび定義ｄ１か
   ら定義ｄ２へ至るパス上に現われた定義に付加されたプ
   レディケートの集合を生成し、 定義ｄ１のプレディケートが真となる条件が、上記プレ
   ディケート集合内の各プレディケートが真となる条件の
   和に包含されるかどうかを判定し、 包含されない場合には、定義ｄ１が定義ｄ２でキルされ
   ないと判定することを特徴とするプログラム解析方法。
4. 【請求項４】実行文に真偽値による実行条件であるプレ
   ディケートをそれぞれ付加することができ、プレディケ
   ートが真の場合にだけ通常の実行を行い、偽の場合には
   実行結果を無効化または命令発行を無効化する制御を行
   うコードを対象にデータフロー解析を行うためのプログ
   ラム解析方法であって、 解析対象のプログラムの各基本ブロックに対して、基本
   ブロック内の解析によって得られる情報を設定する、局
   所属性設定ステップと、 上記局所属性ステップで設定された情報を制御フローの
   上で伝播させることにより、各基本ブロックの入口およ
   び出口に対する情報を求める、データフロー方程式解法
   ステップとを有し、 上記局所属性設定ステップでは、 基本ブロック内に存在する変数ｖの各定義に付加された
   プレディケートの集合を生成し、 上記プレディケートの集合の成立条件が常に成立するか
   どうかを判定し、成立する場合には、基本ブロックの入
   口に到達したｖの全定義が基本ブロック出口まで到達で
   きない、即ちｖの全定義はキルされるとしてキル属性を
   設定することを特徴とするプログラム解析方法。
5. 【請求項５】請求項４のプログラム解析方法において、 データフロー方程式解法ステップで得られた、各基本ブ
   ロック入口に到達する定義集合に基づき、基本ブロック
   内の参照に到達定義を設定するステップをさらに有し、 上記到達定義を設定するステップは、到達定義集合内の
   定義を参照の到達定義に登録する登録ステップと、到達
   定義集合を更新する更新ステップとから成り、 上記登録ステップでは、定義と参照に付加されたプレデ
   ィケートが同時に真にならないと判定した場合には、到
   達定義にその定義の登録は行わなず、 また上記更新ステップでは、到達定義集合内の定義に付
   加されたプレディケートと、その定義以降に現われた定
   義に付加されたプレディケートの集合との包含関係を判
   定することを特徴とするプログラム解析方法。
6. 【請求項６】請求項１〜５のプログラム解析方法におい
   て、 プレディケートを付加されたプレディケートの定義文に
   対し、定義されるプレディケートとその定義文に付加さ
   れたプレディケートの関係を有向エッジで表現したグラ
   フを作成するステップと、 ２つのプレディケート間に上記エッジによる経路が存在
   するかどうかを調べるステップとをさらに有し、 これらのステップによりプレディケート間の包含関係を
   解析することを特徴とするプログラム解析方法。
7. 【請求項７】請求項１〜５のプログラム解析方法におい
   て、 定義されるプレディケートとその定義文に付加されたプ
   レディケートの関係を包含関係エッジと呼ぶ有向エッジ
   で表現し、プレディケートとそのプレディケートの真偽
   値を反転する否定プレディケートとの関係を補集合関係
   エッジと呼ぶエッジで表現したグラフを作成するステッ
   プと、 一方のプレディケートと補集合関係エッジで結ばれたプ
   レディケートと、他方のプレディケートとの間に、上記
   包含関係エッジによる経路が存在するかどうかを調べる
   ステップとをさらに有し、 これらのステップにより、２つのプレディケートが同時
   に真になることがないかどうかを解析することを特徴と
   するプログラム解析方法。