JPH05257706A - データ依存関係情報処理方法 - Google Patents
データ依存関係情報処理方法Info
- Publication number
- JPH05257706A JPH05257706A JP5402192A JP5402192A JPH05257706A JP H05257706 A JPH05257706 A JP H05257706A JP 5402192 A JP5402192 A JP 5402192A JP 5402192 A JP5402192 A JP 5402192A JP H05257706 A JPH05257706 A JP H05257706A
- Authority
- JP
- Japan
- Prior art keywords
- data dependency
- processing
- data
- intermediate text
- operand
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Landscapes
- Devices For Executing Special Programs (AREA)
Abstract
(57)【要約】
【目的】 計算機におけるコンパイラの処理に関し、デ
ータ依存関係を示す情報を、効率良く保持し、利用でき
るようにしたデータ依存関係情報処理方法を目的とす
る。 【構成】 コンパイラの処理において、処理ステップ１
で中間テキストの各オペランドごとに対応して、所定の
範囲種類のデータ依存関係ごとに対応するデータ依存関
係識別子を設け、処理ステップ３により、該中間テキス
トのプログラム論理上の所定のデータ依存関係を解析
し、処理ステップ４〜９により、該データ依存関係を有
する該オペランドの群ごとに異なる数値を、当該オペラ
ンドの当該範囲種類の該データ依存関係識別子に記録
し、該中間テキストの最適化処理の場合に、該データ依
存関係識別子によって、必要な該オペランド間の該デー
タ依存関係の識別を行うように構成する。
ータ依存関係を示す情報を、効率良く保持し、利用でき
るようにしたデータ依存関係情報処理方法を目的とす
る。 【構成】 コンパイラの処理において、処理ステップ１
で中間テキストの各オペランドごとに対応して、所定の
範囲種類のデータ依存関係ごとに対応するデータ依存関
係識別子を設け、処理ステップ３により、該中間テキス
トのプログラム論理上の所定のデータ依存関係を解析
し、処理ステップ４〜９により、該データ依存関係を有
する該オペランドの群ごとに異なる数値を、当該オペラ
ンドの当該範囲種類の該データ依存関係識別子に記録
し、該中間テキストの最適化処理の場合に、該データ依
存関係識別子によって、必要な該オペランド間の該デー
タ依存関係の識別を行うように構成する。
Description
【０００１】
【産業上の利用分野】本発明は、計算機におけるコンパ
イラの処理において、プログラム上のデータ依存関係を
示す情報を保持し利用するための、データ依存関係情報
処理方法に関する。
イラの処理において、プログラム上のデータ依存関係を
示す情報を保持し利用するための、データ依存関係情報
処理方法に関する。
【０００２】
【従来の技術と発明が解決しようとする課題】原始プロ
グラムから目的プログラムを生成するコンパイラの処理
では、通常先ず原始プログラムを解析して、その後の処
理に都合のよいように規定された中間言語による中間テ
キストに変換する。
グラムから目的プログラムを生成するコンパイラの処理
では、通常先ず原始プログラムを解析して、その後の処
理に都合のよいように規定された中間言語による中間テ
キストに変換する。
【０００３】次に、この中間テキストについて、例えば
共通式の除去、ループの融合整理、メモリアクセスの同
期化等の、いわゆる最適化処理を行って、効率の良い目
的プログラムとなるように修正し、最適化した中間テキ
ストから、目的プログラムを生成する。
共通式の除去、ループの融合整理、メモリアクセスの同
期化等の、いわゆる最適化処理を行って、効率の良い目
的プログラムとなるように修正し、最適化した中間テキ
ストから、目的プログラムを生成する。
【０００４】前記のような最適化を行う場合に、最適化
対象の検出及び最適化の制約として重要な条件に、公知
のいわゆるデータ依存関係がある。ここでデータ依存関
係とは公知のように、例えば中間テキストの各オペレー
ションのオペランドとなるデータについて、プログラム
論理上から、同一のオペランドの参照と定義との間で一
定の時間的な順序関係が保たれなければならない場合の
両オペランド間の関係である。
対象の検出及び最適化の制約として重要な条件に、公知
のいわゆるデータ依存関係がある。ここでデータ依存関
係とは公知のように、例えば中間テキストの各オペレー
ションのオペランドとなるデータについて、プログラム
論理上から、同一のオペランドの参照と定義との間で一
定の時間的な順序関係が保たれなければならない場合の
両オペランド間の関係である。
【０００５】そこでコンパイラは、データに付けられた
名前についてビット位置を割り付けた制御情報を設け
て、プログラム解析結果により、或る名前のデータの参
照によって、或る名前のデータが定義される関係を、該
当ビットのオン／オフで表しておく。
名前についてビット位置を割り付けた制御情報を設け
て、プログラム解析結果により、或る名前のデータの参
照によって、或る名前のデータが定義される関係を、該
当ビットのオン／オフで表しておく。
【０００６】又、以上の情報では、配列データについて
添字を考慮したデータ依存関係を識別できないので、配
列データの添字を意識したデータ依存関係の識別が必要
になった時点で、オペランドの配列データの添字や、ル
ープの制御情報をもとにして、データの定義及び参照状
況を解析する。
添字を考慮したデータ依存関係を識別できないので、配
列データの添字を意識したデータ依存関係の識別が必要
になった時点で、オペランドの配列データの添字や、ル
ープの制御情報をもとにして、データの定義及び参照状
況を解析する。
【０００７】しかし、データ依存関係を前記のように必
要の都度認識するのは、コンパイラの処理効率が悪い。
又、認識したデータ依存関係を、中間テキスト上の該当
するオペレーションに対応して記憶しておくことになる
ので、最適化過程で中間テキストの位置関係や内部情報
が変更されると、同じデータ依存関係についても、再度
プログラムを解析して認識しなければならない場合が生
じて、更に処理効率を害する。
要の都度認識するのは、コンパイラの処理効率が悪い。
又、認識したデータ依存関係を、中間テキスト上の該当
するオペレーションに対応して記憶しておくことになる
ので、最適化過程で中間テキストの位置関係や内部情報
が変更されると、同じデータ依存関係についても、再度
プログラムを解析して認識しなければならない場合が生
じて、更に処理効率を害する。
【０００８】本発明は、データ依存関係を示す情報を、
効率良く保持し、利用できるようにしたデータ依存関係
情報処理方法を目的とする。
効率良く保持し、利用できるようにしたデータ依存関係
情報処理方法を目的とする。
【０００９】
【課題を解決するための手段】図１は、本発明の構成を
示す処理の流れ図である。図は、所定言語の原始プログ
ラムから、所定言語の中間テキストを生成し、該中間テ
キストから目的プログラムを生成するコンパイラの処理
における、データ依存関係情報処理方法の構成である。
示す処理の流れ図である。図は、所定言語の原始プログ
ラムから、所定言語の中間テキストを生成し、該中間テ
キストから目的プログラムを生成するコンパイラの処理
における、データ依存関係情報処理方法の構成である。
【００１０】本処理方法では、処理ステップ１で該中間
テキストの各オペランドごとに対応して、所定の範囲種
類のデータ依存関係ごとに対応するデータ依存関係識別
子を設ける。
テキストの各オペランドごとに対応して、所定の範囲種
類のデータ依存関係ごとに対応するデータ依存関係識別
子を設ける。
【００１１】処理ステップ３により、該中間テキストの
プログラム論理上の所定のデータ依存関係を解析し、処
理ステップ４〜９により、該データ依存関係を有する該
オペランドの群ごとに異なる数値を、当該オペランドの
当該範囲種類の該データ依存関係識別子に記録する。
プログラム論理上の所定のデータ依存関係を解析し、処
理ステップ４〜９により、該データ依存関係を有する該
オペランドの群ごとに異なる数値を、当該オペランドの
当該範囲種類の該データ依存関係識別子に記録する。
【００１２】該中間テキストの最適化処理の場合に、該
データ依存関係識別子によって、必要な該オペランド間
の該データ依存関係の識別を行う。
データ依存関係識別子によって、必要な該オペランド間
の該データ依存関係の識別を行う。
【００１３】
【作用】本発明の処理方法により、中間テキストの各オ
ペランドについて、例えば基本リージョン内、ループ
内、ループ間等の所要の範囲種類ごとにデータ依存関係
識別子が設けられ、各範囲内のデータ依存関係を解析し
て、各関係ごとにユニークな番号が該当の全オペランド
のデータ依存関係識別子に記録される。
ペランドについて、例えば基本リージョン内、ループ
内、ループ間等の所要の範囲種類ごとにデータ依存関係
識別子が設けられ、各範囲内のデータ依存関係を解析し
て、各関係ごとにユニークな番号が該当の全オペランド
のデータ依存関係識別子に記録される。
【００１４】従って、最適化処理の中で、データ依存関
係の識別が必要な場合には、所要のオペランドのデータ
依存関係識別子をみれば、データ依存関係の有無が直ち
に分かり、その詳細は同じ番号をデータ依存関係識別子
に持つオペランドを検索して知ることができる。
係の識別が必要な場合には、所要のオペランドのデータ
依存関係識別子をみれば、データ依存関係の有無が直ち
に分かり、その詳細は同じ番号をデータ依存関係識別子
に持つオペランドを検索して知ることができる。
【００１５】
【実施例】データ依存関係識別子は、例えば中間テキス
トの各オペランドの領域を拡大して、必要な個数のデー
タ依存関係識別子の領域とすることにより設ける。
トの各オペランドの領域を拡大して、必要な個数のデー
タ依存関係識別子の領域とすることにより設ける。
【００１６】各オペランドに設けるデータ依存関係識別
子の個数は、コンパイラの処理上で必要とするプログラ
ム範囲の種類ごとに、異なるデータ依存関係識別子を使
用するように、必要な範囲種類の数に等しくする。
子の個数は、コンパイラの処理上で必要とするプログラ
ム範囲の種類ごとに、異なるデータ依存関係識別子を使
用するように、必要な範囲種類の数に等しくする。
【００１７】この範囲種類としては、例えば基本リージ
ョン内、ループ内、及びループ間等があるが、その他の
範囲を設けてもよい。ここで基本リージョンとは、コン
パイラで処理の都合等から定める最適化処理の最小範囲
をいうものとする。
ョン内、ループ内、及びループ間等があるが、その他の
範囲を設けてもよい。ここで基本リージョンとは、コン
パイラで処理の都合等から定める最適化処理の最小範囲
をいうものとする。
【００１８】ループ内のデータ依存関係とは、ループの
繰り返しの１回の実行の中でのデータ依存関係を解析対
象とする場合をいうものとし、その中に複数の基本リー
ジョンを含む場合もある（図２(b）に示す例で、で示
す範囲が１つのループ内解析対象の範囲の場合に、及
びはそれぞれ基本リージョンであってよい）。又、ル
ープ間とは、ループの繰り返し相互間に存在するデータ
依存関係をいうものとする。
繰り返しの１回の実行の中でのデータ依存関係を解析対
象とする場合をいうものとし、その中に複数の基本リー
ジョンを含む場合もある（図２(b）に示す例で、で示
す範囲が１つのループ内解析対象の範囲の場合に、及
びはそれぞれ基本リージョンであってよい）。又、ル
ープ間とは、ループの繰り返し相互間に存在するデータ
依存関係をいうものとする。
【００１９】データ依存関係識別子に記録する数値は、
例えば「０」を無効（データ依存関係について未解析）
の表示、「１」をデータ依存関係が無いことの表示とす
る。データ依存関係が有る場合には、「２」以上の数値
を使用し、依存関係を持つオペランドの群に、その範囲
種類内でユニークな同じ値を与えるようにする。
例えば「０」を無効（データ依存関係について未解析）
の表示、「１」をデータ依存関係が無いことの表示とす
る。データ依存関係が有る場合には、「２」以上の数値
を使用し、依存関係を持つオペランドの群に、その範囲
種類内でユニークな同じ値を与えるようにする。
【００２０】図２は、以上のように定めるデータ依存関
係識別子の設定例を示し、図２(a)は基本リージョン内
の例、(b)はループ内の例、(c)はループ間の例である。
図には、説明のために中間テキストに代えて、FORTRAN
言語の原始プログラム形式でプログラムを示し、各変数
の後に付けた長方形枠で、オペランドに対応して設ける
データ依存関係識別子を表す。
係識別子の設定例を示し、図２(a)は基本リージョン内
の例、(b)はループ内の例、(c)はループ間の例である。
図には、説明のために中間テキストに代えて、FORTRAN
言語の原始プログラム形式でプログラムを示し、各変数
の後に付けた長方形枠で、オペランドに対応して設ける
データ依存関係識別子を表す。
【００２１】各枠内の３数値は基本リージョン内，ルー
プ内，ループ間の順に、各データ依存関係識別子を表す
ものとする。図２(b)においてデータＣ（Ｉ）について
は、基本リージョン内の関係として捕らえられるので、
図示のようにループ内の関係で示す必要は無いが、処理
の便宜上両者に重複して示してもよい。
プ内，ループ間の順に、各データ依存関係識別子を表す
ものとする。図２(b)においてデータＣ（Ｉ）について
は、基本リージョン内の関係として捕らえられるので、
図示のようにループ内の関係で示す必要は無いが、処理
の便宜上両者に重複して示してもよい。
【００２２】図１に示す処理の流れを、詳細に説明する
と、処理ステップ１の初期設定で、中間テキストの各オ
ペランドについてデータ依存関係識別子の領域を取り、
それらをすべて「０」に設定する。
と、処理ステップ１の初期設定で、中間テキストの各オ
ペランドについてデータ依存関係識別子の領域を取り、
それらをすべて「０」に設定する。
【００２３】処理ステップ２で解析対象の範囲種類を決
める。処理ステップ３で中間テキストについて解析し、
現処理対象の範囲種類のデータ依存関係識別子が「０」
であるオペランドについて、データ依存関係を持つオペ
ランドを通常の方法で解析し検索する処理を行う。
める。処理ステップ３で中間テキストについて解析し、
現処理対象の範囲種類のデータ依存関係識別子が「０」
であるオペランドについて、データ依存関係を持つオペ
ランドを通常の方法で解析し検索する処理を行う。
【００２４】この場合に基本リージョン内、及びループ
内ではプログラム上の上から下の方向の依存関係を求め
る。その結果そのオペランドについて、データ依存関係
が検出されれば、処理ステップ４を経て処理ステップ５
で「２」から始める番号を、使用するごとに＋１して更
新して現在の番号値を得、検出したデータ依存関係の全
オペランドのデータ依存関係識別子に、処理ステップ６
で現在の番号値を記録する。
内ではプログラム上の上から下の方向の依存関係を求め
る。その結果そのオペランドについて、データ依存関係
が検出されれば、処理ステップ４を経て処理ステップ５
で「２」から始める番号を、使用するごとに＋１して更
新して現在の番号値を得、検出したデータ依存関係の全
オペランドのデータ依存関係識別子に、処理ステップ６
で現在の番号値を記録する。
【００２５】又、データ依存関係を持たないオペランド
であることが判った場合には、処理ステップ４を経て処
理ステップ７で「１」を、そのオペランドのデータ依存
関係識別子に記録する。
であることが判った場合には、処理ステップ４を経て処
理ステップ７で「１」を、そのオペランドのデータ依存
関係識別子に記録する。
【００２６】以上の後、処理ステップ８で識別して、現
処理対象の範囲種類のデータ依存関係識別子に０を持つ
オペランドがあれば、処理ステップ３に戻って以上の処
理を行う。
処理対象の範囲種類のデータ依存関係識別子に０を持つ
オペランドがあれば、処理ステップ３に戻って以上の処
理を行う。
【００２７】或る範囲種類について処理が終われば、処
理ステップ９で識別して、未処理の範囲種類があれば処
理ステップ２に戻り、以上の処理を繰り返すものとす
る。
理ステップ９で識別して、未処理の範囲種類があれば処
理ステップ２に戻り、以上の処理を繰り返すものとす
る。
【００２８】
【発明の効果】以上の説明から明らかなように本発明に
よれば、計算機におけるコンパイラの処理において、デ
ータ依存関係を示す情報を、効率良く保持し、利用でき
るようになるので、コンパイラの最適化処理の処理効率
を向上するという著しい工業的効果がある。
よれば、計算機におけるコンパイラの処理において、デ
ータ依存関係を示す情報を、効率良く保持し、利用でき
るようになるので、コンパイラの最適化処理の処理効率
を向上するという著しい工業的効果がある。
【図１】 本発明の構成を示す処理の流れ図
【図２】 データ依存関係識別子の設定例を示す図
１〜９ 処理ステップ
Claims (1)
- 【請求項１】 所定言語の原始プログラムから、所定言
語の中間テキストを生成し、該中間テキストから目的プ
ログラムを生成するコンパイラの処理において、 該中間テキストの各オペランドごとに対応して、所定の
範囲種類のデータ依存関係ごとに対応するデータ依存関
係識別子を設け(1)、 該中間テキストのプログラム論理上の所定のデータ依存
関係を解析して(3) 、該データ依存関係を有する該オペ
ランドの群ごとに異なる数値を、当該オペランドの当該
範囲種類の該データ依存関係識別子に記録し(2、４〜
9)、 該中間テキストの最適化処理の場合に、該データ依存関
係識別子によって、必要な該オペランド間の該データ依
存関係の識別を行うように構成されていることを特徴と
するデータ依存関係情報処理方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP05402192A JP3156343B2 (ja) | 1992-03-13 | 1992-03-13 | データ依存関係情報処理方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP05402192A JP3156343B2 (ja) | 1992-03-13 | 1992-03-13 | データ依存関係情報処理方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH05257706A true JPH05257706A (ja) | 1993-10-08 |
| JP3156343B2 JP3156343B2 (ja) | 2001-04-16 |
Family
ID=12958935
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP05402192A Expired - Fee Related JP3156343B2 (ja) | 1992-03-13 | 1992-03-13 | データ依存関係情報処理方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3156343B2 (ja) |
-
1992
- 1992-03-13 JP JP05402192A patent/JP3156343B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JP3156343B2 (ja) | 2001-04-16 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH02264329A (ja) | プログラム自動生成装置 | |
| US11301218B2 (en) | Graph-based vectorization for software code optimization references | |
| CN112631925B (zh) | 一种单变量原子违背缺陷的检测方法 | |
| US11256488B1 (en) | Graph-based vectorization for software code optimizations | |
| JP3156343B2 (ja) | データ依存関係情報処理方法 | |
| JPH0887417A (ja) | コンパイラ装置 | |
| US8402445B2 (en) | Program translation method and notifying instruction inserting method | |
| JP2924882B1 (ja) | 論理シミュレーションモデルの作成方法および装置ならびに記録媒体 | |
| JP2001125793A (ja) | コンパイラシステム及びコンパイル方法並びに記録媒体 | |
| JP2820184B2 (ja) | ロードモジュール単体テスト支援装置 | |
| JP3008483B2 (ja) | リンク処理装置 | |
| JP2845478B2 (ja) | 論理回路の遅延時間解析装置 | |
| JPH0721031A (ja) | 言語処理方法 | |
| JP2723805B2 (ja) | シミュレーションプログラム生成方式 | |
| JPH05224944A (ja) | アラインメント整合方法 | |
| JPH06119156A (ja) | プログラム自動生成方法 | |
| JPH01228031A (ja) | ストール時の障害解析方式 | |
| JPH0553782A (ja) | 特定部分の動的特性解析情報取得方式 | |
| JPH0358144A (ja) | プログラム走行覆歴情報収集方式 | |
| JPH04160433A (ja) | 情報編集方式 | |
| JP2001142716A (ja) | ループ内条件分岐削除最適化方式 | |
| JP2002229787A (ja) | プログラム生成装置 | |
| JPH05204699A (ja) | デバッグ時識別子探索方式 | |
| JPH11259281A (ja) | 情報システム設計方法及び装置及び情報システム設計プログラムを格納した記憶媒体 | |
| JPH03230220A (ja) | ソート処理方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20010109 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080209 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090209 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090209 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100209 Year of fee payment: 9 |
|
| LAPS | Cancellation because of no payment of annual fees |