JPH02214974A

JPH02214974A - ベクトル化処理方式

Info

Publication number: JPH02214974A
Application number: JP3587889A
Authority: JP
Inventors: Katsumi Yamamoto; 克己山本; Takayuki Nakatomi; 中富　孝幸
Original assignee: NEC Corp; NEC Solution Innovators Ltd
Current assignee: NEC Corp; NEC Solution Innovators Ltd
Priority date: 1989-02-15
Filing date: 1989-02-15
Publication date: 1990-08-27

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明はベクトル処理プロセッサに供給する目的プログ
ラムを生成するコンパイラにおけるベクトル化処理方式
に関するものである。

〔従来の技術〕

記憶域上に規則的に並んでいるデータに対して一度に演
算を行うベクトル命令をもっベクトル処理プロセッサに
おいては、−船釣に目的プログラムのうちのベクトル命
令によって実行される部分の割合を大きくすればするほ
どプログラムの実行時間を短縮することができる。従っ
て、このようなベクトル処理プロセッサに対するコンパ
イラでは、与えられた原始プログラムを可能な限りベク
トル命令による並列実行可能な形で目的プログラムに変
換することが望まれる。

ところで、ベクトル処理プロセッサに対する従来のコン
パイラは、高級言語（例えばＦＯＲＴＲＡＮ）で記述さ
れた原始プログラムを読み込み、構文解析を行って第１
中間テキストを生成する構文解析部と、第１中間テキス
トから原始プログラム中のループ構造を検出してベクト
ル化可能部分の認識を行い、ベクトル処理用の第２中間
テキストを生成するベクトル化処理部と、第２中間テキ
ストから目的プログラムを生成して出力するコード生成
部とから、その主要部が構成されていた。

このような従来のコンパイラは、例えば第１２図に示す
ような原始プログラムが与えられた場合には、構文解析
部がこの原始プログラムを読み込んで第１３図の流れ図
に示すような第１中間テキスト（ステップ３２１〜５２
４）を生成し、ベクトル化処理部が第１中間テキストを
変形した第１４図の流れ図に示すような第２中間テキス
ト（ステップＳ２５，５２６）を生成し、コード生成部
が第２中間テキストを読み込んで並列実行可能部分をベ
クトル化した目的プログラムを生成していた。

〔発明が解決しようとする課題〕

ところが、従来のこの種のコンパイラでは、第４図に示
すような原始プログラムが与えられた場合には、配列Ａ
に対する定義参照関係がＤＯループ内およびＤｏループ
の直前だけの情報では不明であるため、この範囲をベク
トル化不可能な文群として処理し、その部分をスカラ命
令により順次実行することを余儀なくされていた。

このように従来のコンパイラでは、Ｄｏループ内および
ＤＯループの直前だけの情報では定義参照関係が確定で
きない配列要素の引用のある部分は一般的にはベクトル
化できず、並列実行不可能として処理されていたので、
目的プログラムのうちスカラ命令で実行される部分が多
くなり、プログラムの実行時間を大幅に短縮することが
できないという欠点があった。

本発明は上記の点に鑑み提案されたものであり、その目
的とするところは、ＤＯループ内およびＤＯループの直
前だけの情報では定義参照関係が確定できない配列要素
の引用のある部分であっても、原始プログラムをＤｏル
ープの入口から遡って定義参照関係が定められるものに
ついてはベクトル化を行い、プログラムの実行時間の短
縮化を一層向上することのできるベクトル化処理方式を
提供することにある。

〔課題を解決するための手段〕

本発明は上記の目的を達成するため、記憶域上に規則的
に並んでいるデータに対して一度に演算を行うベクトル
命令をもつベクトル処理プロセッサに対して、与えられ
た原始プログラムから目的プログラムを生成し出力する
コンパイラにおけるベクトル化処理方式において、前記原始プログラムを読み込み構文解析を行って第１中
間テキストを生成する構文解析部と、前記第１中間テキ
ストから前記原始プログラムの制御の流れを解析する構
造解析手段、ループの入口での変数の定義状態を解析す
る入口変数解析手段、前記入口変数解析手段の結果を利用して添字および指標
変数の情報を変形すると共に、ループ中に並列実行に矛
盾するデータ依存関係があるか否かを判定するデータ依
存関係判定手段、および、前記データ依存関係判定手段
により並列実行可能と判定された部分のベクトル化処理
用の文を含む第２中間テキストを生成するベクトルテキ
スト生成手段を備えたベクトル化処理部と、前記第２中
間テキストから目的プログラムを生成して出力するコー
ド生成部とを備えるようにしている。

〔作用〕

本発明のベクトル化処理方式にあっては、構文解析部が
原始プログラムを読み込み構文解析を行って第１中間テ
キストを生成し、ベクトル化処理部の構造解析手段が前
記第１中間テキストから前記原始プログラムの制御の流
れを解析し、入口変数解析手段がループの入口での変数
の定義状態を解析し、データ依存関係判定手段が前記入
口変数解析手段の結果を利用して添字および指標変数の
情報を変形すると共にループ中に並列実行に矛盾するデ
ータ依存関係があるか否かを判定し、ベクトルテキスト
生成手段が前記データ依存関係判定手段により並列実行
可能と判定された部分のベクトル化処理用の文を含む第
２中間テキストを生成し、コード生成部が前記第２中間
テキストから目的プログラムを生成して出力する。

〔実施例〕

次に、本発明の実施例につき図面を参照して説明する。

第１図は本発明のベクトル化処理方式を適用したコンパ
イラの一実施例を示す構成図である。第１図において、
コンパイラ２は、記憶域上に規則的に並んでいるデータ
に対して一度に演算を行うベクトル命令をもつベクトル
処理プロセッサに対して、与えられた高級言語で記述さ
れた原始プログラム１から目的プログラム３を生成して
出力する機能を有したものであり、原始プログラム１を
読み込んで構文解析を行い、第１中間テキスト２４を生
成する構文解析部２１と、第１中間テキスト２４から原
始プログラム１中のループ構造を検出してヘクトル化可
能部分の認識を行い、ベクトル処理用の第２中間テキス
ト２５を生成するベクトル化処理部２２と、第２中間テ
キスト２５から目的プログラム３を生成して出力するコ
ード生成部２３とから構成されている。

また、ベクトル化処理部２２は、第１中間テキスト２４
を読み込んで原始プログラム１の制御の流れを解析する
構造解析手段２２１と、ループの入口での変数の定義状
態を解析する入口変数解析手段２２２と、入口変数解析
手段２２２の結果を利用して添字および指標変数の情報
を変形すると共に、ループ中に並列実行に矛盾するデー
タ依存関係があるか否かを判定するデータ依存関係判定
手段２２３と、データ依存関係判定手段２２３によりベ
クトル化可能と判定された部分のベクトル処理用の文を
含む第２中間テキスト２５を生成するベクトルテキスト
生成手段２２４とを含んで構成されている。

第２図および第３図は第１図の入口変数解析手段２２２
において変数の解析のために作成され、データ依存関係
判定手段２２３で参照される入口変数情報テーブル５お
よびトライアトロの論理的構成を示したものであり、入
口変数情報テーブル５は、・次の入口変数情報テーブルへのポインタ・変数テーブ
ルへのポインタ・右辺の情報を示すトライアトへのポインタを含んでお
り、また、右辺の情報を示すトライアトロは、・演算子・第１オペランドへのポインタ・第２オペランドへのポインタを含んで構成されている。なお、第１番目の入口変数情
報テーブル５（５１）を参照するためのポインタ４、な
らびに入口変数情報テーブル５（５１，５２，５３，・
・・）およびトライアトロ（６１゜６２．６３．・・・
）により指定される変数テーブル７　（７１，７２，７
３，７４，・・・）および定数テーブル８（８１，・・
・）が設けられている（第６図ないし第８図参照）。

ここで、入口変数情報テーブル５とは、ループの入口以
前において出現する変数（入口変数）の情報を管理する
テーブルであり、ループの入口から逆順に出現する順番
で作成され、ポインタ４および各入口変数情報テーブル
５の次の入口変数情報テーブルへのポインタで相互に連
結されている。

また、変数テーブルへのポインタにより入口変数が変数
テーブルと関連付けられる。更に、右辺の情報を示すポ
インタによりトライアトロが指定される。

トライアトロは定義式の右辺の状態を示すものであり、
第１オペランドへのポインタが示す変数あるいは定数と
、第２オペランドへのポインタが示す変数あるいは定数
とが、演算子の示す演算で結合されていることを表現す
る。例えば、Ｌ＝に＋１をトライアトロで表現する場合、・演算子−」− ・第１オペランドへのポインター変数にの変数テーブルへのポインタ・第２オペランドへのポインタ一定数１の定数テーブルへのポインタとなる。また、Ｊ＝にの場合、・演算子→ＡＳＧＮ　（Ａｓｓ　ＩＯＮ　、代入）・第
１オペランドへのポインタ →１ｔｌｋＫの変数テーブルへのポインタ・第２オペラ
ンドへのポインタ→ＮＵＬ　Ｌとなる。

以下、上記の実施例の動作について説明する。

なお、従来のコンパイラではベクトル化できなかった第
４図の原始プログラムを具体例として説明する。

第１図において、原始プログラム１が与えられてコンパ
イラ２が起動されると、先ず構文解析部２１が原始プロ
グラム１を読み込んで第１中間テキスト２４を生成する
。第４図の原始プログラムに対しては第５図に示すよう
な構造の第１中間テキスト（ステップ８１〜５１０）が
出力される。

次いで、ベクトル化処理部２２は第１中間テキスト２４
を入力し、構造解析手段２２１を起動する。

起動された構造解析手段２２１は以下の処理を行う。

■第１中間テキスト２４を分岐を単位としたブロックに
分割する。

■対象となるループ部分を文単位のブロックに分割する
。

■第１中間テキスト２４からプログラム全体の制御の流
れを解析して各ブロックの関係を求める。

■各々のブロックで定義参照されている変数に対して、
その生死情報を収集する。

構造解析手段２２１の処理が終了すると入口変数解析手
段２２２が起動され、入口変数解析手段２２２は以下の
処理を行う。

■ループが実行されるときに必ず実行されるブ０ツクを
ＤＯ小ループ入口から逆順に取り出し、その中で定義さ
れている変数を出現の逆順に取り出す。

■取り出した変数を定義している代入文の右辺に引用さ
れている変数の生死情報より、取り出した変数を入口変
数情報として登録できるか否か調べる。ＤＯ小ループ入
口ブロックから定義文のあるブロックまでどの経路を通
っても右辺に現れる変数は定義されていない場合には登
録できる。

■既に登録された入口変数情報テーブル等を検索して、
右辺のトライアトに登録しようとしている変数の引用が
ある場合、その変数引用を登録しようとした変数の右辺
のトライブトで置換する。

■登録可能な場合、同一変数に対する入口変数情報テー
ブルが作成されていなければ、作成する。

ここで、第５図の第１中間テキストの場合には、代入文
Ｊ＝Ｋ　（ステップ３４）について解析した状態で第６
図のように入口変数情報テーブル５１およびトライアト
ロ１が作成され、変数テーブル７１．７２との対応付け
が行われる。また、代入文Ｌ＝に＋１　　（ステップ３
３）について解析した状態で第７図のような状態となり
、代入文に＝Ｍ＋１　（ステップＳｌ）について解析し
た状態で第８図のような状態となる。

次いで、入口変数解析手段２２２の処理が終了するとデ
ータ依存関係判定手段２２３が起動され、データ依存関
係判定手段２２３は以下の処理を行う。

■入口変数情報テーブルの情報を利用して添字および指
標変数の情報を変形する。

［相］ループ中に並列実行に矛盾するデータ依存関係が
あるか否かを判定する。

ここで、第４図の原始プログラム（第５図の第１中間テ
キスト）の場合には、第９図の状態を経て第１０図のよ
うに概念的に変形され、その結果、ループ中に並列実行
に矛盾するデータ依存関係が存在しないので、データ依
存関係なしと判定される。

次いで、データ依存関係判定手段２２３の処理が終了す
るとベクトルテキスト生成手段２２４が起動され、ベク
トルテキスト生成手段２２４は以下の処理を行う。

■並列実行可能部分をベクトル処理するために必要とな
るベクトル長設定用の文を第２中間テキスト２５中に生
成する。

■並列実行可能部分に対するベクトル処理用の文を第２
中間テキスト２５中に生成する。

０ループ中の並列実行可能な部分をベクトル処理したと
きの指標変数の終値を保証するための文を第２中間テキ
スト２５中に生成する。

ここで、第１０図のように変形されたプログラムに対し
ては、第１１図に示すような構造の第２中間テキスト（
ステップＳｌｌ〜５２０）が生成される。すなわち、ベ
クトル長設定用の文として、ループの繰り返し数をベク
トル長として設定するｖｌ＝Ｍ（ステップ８１６）が生
成され、ベクトル処理用の文として、ステップＳ１７，
３１８が生成され、指標変数１の終値を保証するための
文としてＩ＝１＋Ｍ（ステップ５２０）が生成され、指
標変数ＪについてはＪ＝Ｊ＋２＊Ｍ　（ステップ５１９
）が生成される。

次いで、ベクトル化処理部２２のベクトルテキスト生成
手段２２４における処理が終了すると、コード生成部２
３が起動され、コード生成部２３は第２中間テキスト２
５の各文を対応するコードに変換し、目的プログラム３
が生成・出力される。

このようにして生成された目的プログラム３はベクトル
処理プロセッサに供給され、プログラムの実行が行われ
る。しかして、ベクトル処理プロセッサは、従来定義参
照関係が確定できずにスカラ命令で実行していた部分を
ベクトル命令で高速に実行することができ、プログラム
の実行時間が短縮されるものである。

〔発明の効果〕

以上説明したように、本発明のベクトル化処理方式にあ
っては、ＤＯループの入口での変数の定義状態を解析す
ることにより、ＤＯループ内およびＤＯループの直前だ
けの情報では定義参照関係が確定できない配列要素の添
字に対しても確定を可能とし、ベクトル化を行うことが
できるため、ベクトル処理プロセッサにおけるプログラ
ムの実行時間を大幅に短縮できるという効果がある。

【図面の簡単な説明】

第１［ｆｆｌは本発明のベクトル化処理方式を適用した
コンパイラの一実施例を示す構成図、第２図は変数の解
析に用いられる入口変数情報テーブルの論理的構成図、第３図は変数の解析に用いられるトライアトの論理的構
成図、第４図は原始プログラムの例を示す図、第５図は第４図
の原始プログラムに対応した第１中間テキストの概念図
、第６図ないし第８図は変数の解析結果の表現の例を示す
図、第９図および第１０図は変形の加えられたプログラムの
概念図、第１１図は第４図の原始プログラムに対応した第２中間
テキストの概念図、第１２図は原始プログラムの例を示す図、第１３図は第
１２図の原始プログラムに対応した第１中間テキストの
概念図および、第１４図は第１２図の原始プログラムに対応した第２中
間テキストの概念図である。図において、１・・・原始プログラム２・・・コンパイラ２１・・・構文解析部２２・・・ベクトル化処理部２２１・・・構造解析手段２２２・・・入口変数解析手段２２３・・・データ依存関係判定手段２２４・・・ベクトルテキスト生成手段２３・・・コー
ド生成部２４・・・第１中間テキスト２５・・・第２中間テキスト３・・・目的）゛ログラム４・・・ポインタ１〜５３・・・入口変数情報テーブル１〜６３・・・トライアト１〜７４・・・変数テーブルト・・定数テーブル

Claims

【特許請求の範囲】記憶域上に規則的に並んでいるデータに対して一度に演
算を行うベクトル命令をもつベクトル処理プロセッサに
対して、与えられた原始プログラムから目的プログラム
を生成し出力するコンパイラにおけるベクトル化処理方
式において、前記原始プログラムを読み込み構文解析を行って第１中
間テキストを生成する構文解析部と、前記第１中間テキ
ストから前記原始プログラムの制御の流れを解析する構
造解析手段、ループの入口での変数の定義状態を解析する入口変数解
析手段、前記入口変数解析手段の結果を利用して添字および指標
変数の情報を変形すると共に、ループ中に並列実行に矛
盾するデータ依存関係があるか否かを判定するデータ依
存関係判定手段、および、前記データ依存関係判定手段
により並列実行可能と判定された部分のベクトル化処理
用の文を含む第２中間テキストを生成するベクトルテキ
スト生成手段を備えたベクトル化処理部と、前記第２中間テキストから目的プログラムを生成して出
力するコード生成部とを備えたことを特徴とするベクト
ル化処理方式。