JPH04352036A - コンパイラにおける並列化処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、密結合マルチプロセ
ッサシステムに係り、特に並列実行を意図せずに設計さ
れた高級言語で書かれたソースコードを解析して、並列
実行可能なオブジェクトコードを生成する処理装置に関
するものである。

【０００２】

【従来の技術】コンパイラの最適化において、ループの
繰り返しごとに必ず一定の値が増加又は減少する変数を
誘導変数と呼んでいる。ＦＯＲＴＲＡＮ（フォートラン
−科学技術計算用の高水準プログラム言語）のＤＯルー
プを並列に実行するには、ループ中の誘導変数を検出し
、それらの参照を全てループ制御変数の多項式で置き換
えた後、誘導変数の定義式を削除して個々の繰り返しを
独立に実行することができるようにする必要がある。

【０００３】図８は従来のコンパイラにおいて誘導変数
の検出と削除の処理を説明するための説明図、図９は従
来のコンパイラにおいて誘導変数の検出ができない場合
の処理を説明するための説明図である。例えば図８（ａ
）に示されるサンプルプログラムのループでは、誘導変
数ＪはＩ＊２と、誘導変数ＫはＩ＋２と等しいので、実
行文４６における誘導変数Ｊ，Ｋの参照をそれぞれＩ＊
２，Ｉ＋２で置き換え、誘導変数Ｊ，Ｋの定義式の実行
文４３，４４，４５を削除することにより図８（ｂ）に
示される変換結果が得られる。

【０００４】上記のような誘導変数の検出と削除につい
ては、ＡＬＦＲＥＤ　　Ｖ．ＡＨＯ他２名共著の「Ｃｏ
ｍｐｒｉｌｅｒｓ（コンパイラ）−Ｐｒｉｎｃｉｐｌｅ
ｓ，Ｔｅｃｈｎｉｑｕｅｓ，ａｎｄ　Ｔｏｏｌｓ（原理
・技法・ツール）」のＰ．６４３“Ｅｌｉｍｉｎａｔｉ
ｏｎ　ｏｆ　Ｉｎｄｕｃｔｉｏｎ　Ｖａｒｉａｂｌｅｓ
（誘導変数の削除）”として述べられている。誘導変数
は帰納的な定義式の実行文４４あるいは他の誘導変数を
参照する定義式の実行文４５がループ中に少なくとも１
つ存在する。従ってこのような形式の定義式の実行文を
検出することにより誘導変数を検出することができるが
、逆にこのようにして検出される変数が全て誘導変数に
なるとは限らない。例えば、図９に示されるようにルー
プ中に誘導変数Ｊの帰納的な定義式の実行文が存在して
いるが、誘導変数ＪについてＩを使用して定式化するこ
とはできない。そのために、従来ではループ中の制御フ
ローグラフを考慮して誘導変数を検出するための有効的
な手法は知られていない。

【０００５】

【発明が解決しようとする課題】上記した従来のコンパ
イラにおいて誘導変数を検出す手法は以上のようにして
処理されるものであり、誘導変数の検出手法の適用範囲
はループの内部が単一の基本ブロックで構成されている
場合に限定されるために、内部に分岐や非構造的なルー
プを含んでいる場合には、誘導変数を検出することがで
きないという問題点があった。

【０００６】この発明は上記のような問題点を解決する
ためになされたもので、内部に複雑な制御構造を持つル
ープにおいても確実に誘導変数を検出する機能を有する
コンパイラにおける並列化処理装置を得ることを目的と
する。

【０００７】

【課題を解決するための手段】この発明に係るコンパイ
ラにおける並列化処理装置は、制御フローグラフをもと
に、支配木生成部で解析対象ループの支配木を生成し、
バックエッジ検出部で解析対象ループ中の非構造的なル
ープを検出し、非制御依存ブロック検出部でループの繰
り返しの都度確実に１回だけ実行される基本ブロックで
ある非制御依存ブロックを検出し、誘導変数定義文検出
部で非制御依存ブロックを対象として誘導変数の定義文
を検出するようにしたものである。

【０００８】

【作用】この発明におけるコンパイラにおける並列化処
理装置は、ループ中の基本ブロック間の制御フローグラ
フをもとに、ループの繰り返しにおいて制御に依存しな
い基本ブロックを検出し、このような基本ブロックに含
まれ、かつループ内で単一の代入文を持つ変数を検出す
ることにより、複数の基本ブロックによって構成される
ループにおいても確実に誘導変数を検出することが可能
となる。

【０００９】

【実施例】この発明に係るコンパイラにおける並列化処
理装置は、以下に述べるような機能を有する誘導変数検
出部を設けることにより達成される。なお、この発明で
は検出する誘導変数は次のような形式のもの、すなわち
「並列化対象ループ中にただ１つの定義文を持ち、その
定義文が必ずループの繰り返しの都度１回だけ実行され
る変数」に限定する。実際のプログラムでは、ほとんど
全ての誘導変数がこのような形式で定義されている。 （１）先立つ処理によって求められている制御フローグ
ラフをもとに、解析対象ループの支配木を生成する。２
つの基本ブロックＢ１とＢ２において、「制御がＢ２に
到達する時には必ずＢ１を通っている」場合に「Ｂ１は
Ｂ２を支配する」と云い、“Ｂ１　ｄｏｍ　　Ｂ２”と
記述する。このような支配関係を木構造で表現したもの
が支配木である。ループの出口を支配する基本ブロック
はループ内を実行するたびに必ず１回実行されるが、こ
のような基本ブロックの集合は支配木において、ループ
の入口となる基本ブロックから出口となる基本ブロック
に至る経路上のノードの集合として求めることができる
。この集合をＡとする。 （２）解析対象ループ中の非構造的なループを検出する
。このようなループに含まれる基本ブロックは、解析対
象としているループの１回の繰り返しにつき複数回実行
される可能性があるため、上述した集合Ａから除外しな
ければならない。そのために制御フローグラフ中のバッ
クエッジを検出する。このバックエッジによって作られ
るループ内で、制御に依存することなく必ず実行される
基本ブロックは、バックエッジの両端の基本ブロックに
よって形成される支配木の経路上の集合として求められ
る。この集合をＢとする。 （３）ループの繰り返しの都度確実に１回だけ実行され
る基本ブロックを検出する。このような基本ブロックを
非制御依存ブロックと呼ぶ。このような基本ブロックの
集合は上述した２つの集合を用いて“Ａ−Ｂ”として求
められる。 （４）このようにして求められた非制御依存ブロックを
対象として誘導変数の定義文を検出する。

【００１０】図１はこの発明の実施例であるコンパイラ
における並列化処理装置が適用するコンパイラの全体構
成を示すブロック図である。図において、ソースコード
１１はソースコード解釈部１４により中間コード１２に
変換される。中間コード１２は最適化処理部１５により
並列化の容易な形式に変換され、並列化処理部１６では
並列実行可能な部分を検出したりあるいは必要に応じて
コードを変更する。このように解析された情報をもとに
、コード生成部１７は並列化オブジェクトコード１３を
出力する。この発明におけるコンパイラにおける並列化
処理装置では、誘導変数を検出する処理を特徴としてい
るが、この処理を行うのが誘導変数検出部であり、これ
は最適化処理部１５の一部分として実現される。

【００１１】図２は図１の誘導変数検出部の構成を示す
ブロック図である。図において、１は誘導変数検出部、
２は支配木生成部、３はバックエッジ検出部、４は非制
御依存ブロック検出部、５は誘導変数定義文検出部、７
は解析情報、１２は中間コードである。

【００１２】上記のように構成された誘導変数検出部１
において、制御フローグラフをもとに、支配木生成部２
で解析対象ループの支配木を生成する。バックエッジ検
出部３で解析対象ループ中の非構造的なループを検出す
る。非制御依存ブロック検出部４でループの繰り返しの
都度確実に１回だけ実行される基本ブロックを検出する
。このような基本ブロックは支配木においてループの出
口を支配し、かつ内部の非構造的なループに含まれない
基本ブロックである非制御依存ブロックとして求まる。 誘導変数定義文検出部５で非制御依存ブロックを対象と
して誘導変数の定義文を検出する。

【００１３】図３は図１の誘導変数検出部の動作を説明
するためのフローチャート、図４はこの発明の実施例で
あるコンパイラにおける並列化処理装置の処理を説明す
るための説明図であり、図４（ａ）は入力となるソース
コード、図４（ｂ）はループ内部の制御フローグラフ、
図４（ｃ）は支配木、図４（ｄ）は誘導変数の除去後の
コードをそれぞれ示す。図５はこの発明の実施例である
コンパイラにおける並列化処理装置の処理を説明するた
めの説明図であり、図５（ａ）は入力となるソースコー
ド、図５（ｂ）はループ内部の制御フローグラフ、図５
（ｃ）は支配木をそれぞれ示す。図６はこの発明の実施
例であるコンパイラにおける並列化処理装置の処理を説
明するための説明図であり、図６（ａ）はループ内部の
制御フローグラフ、図６（ｂ）は支配木をそれぞれ示す
。図７はこの発明の実施例であるコンパイラにおける並
列化処理装置の処理を説明するための説明図であり、図
７（ａ）はループ内部の制御フローグラフ、図７（ｂ）
は支配木をそれぞれ示す。図において、３１〜４２は処
理ステップ、５１〜５９，６１〜６６は実行文、１０１
〜１０４は制御フローグラフのエッジ、１０５，１０７
，１０９，１１０は制御フローグラフのバックエッジ、
１０６，１０８，１１２，１１３は非構造ループに含ま
れる基本ブロックである。

【００１４】次に、この発明の実施例であるコンパイラ
における並列化処理装置を適用し、２つのサンプルプロ
グラムに対して誘導変数を検出する処理について説明す
る。図４（ａ）に示されるプログラム中のＤＯループが
並列化処理対象の時に、ループ中のコードはＢ１からＢ
４の４つの基本ブロックに分割でき、図４（ｂ）に示さ
れる制御フローグラフが得られる（処理ステップ３１）
。ここで、説明の便宜上ループの処理の入口となる基本
ブロックをＨ、ループの処理の出口となる基本ブロック
をＴとし、制御フローグラフに含めておく（処理ステッ
プ３２）。この制御フローグラフをもとに、図４（ｃ）
に示される支配木が生成される（処理ステップ３３）。 次に制御フローグラフの各エッジ１０１〜１０４に対応
するフラグを用意してすべてをｏｆｆに初期化する（処
理ステップ３４，３５）。これはバックエッジ検出の前
処理であるが（処理ステップ３６）、この制御フローグ
ラフにはバックエッジが存在しないため（処理ステップ
３７）、処理ステップ３６でフラグがｏｎになるエッジ
は存在しない。そのために処理ステップ３８〜４１に至
る部分は実行されることなく処理ステップ４２に移り、
図４（ｃ）に示される支配木において基本ブロックのＨ
からＴに至る経路上でフラグがｏｆｆの基本ブロック、
すなわちＢ１，Ｂ４がループの繰り返しにおいて制御に
依存しない部分として検出される。その結果を図４（ａ
）に示されるソースコードと比べて確認して見る。基本
ブロックＢ１，Ｂ４はループの繰り返しの都度必ず実行
されるのに対し、基本ブロックＢ２，Ｂ３は条件文であ
る実行文５３によっていずれか一方だけが実行される。 誘導変数Ｊはループ中で制御に依存しない基本ブロック
Ｂ１においてのみ値が定義される実行文５２、及びその
代入文の形式から、ループの繰り返しの都度１づつ増加
する誘導変数であり、ループの実行前の初期化による実
行文５１より、ループ中の誘導変数ＪをＩで置き換えて
誘導変数Ｊの定義式の実行文５１，５２を除去して図４
（ｄ）に示されるコードを得る。

【００１５】次に、図５のプログラムをもとに、ループ
中にバックエッジを含む場合の処理について説明する。 上述した前例と同様に、処理ステップ３１〜３５の処理
において図５（ｂ）に示される制御フローグラフと図５
（ｃ）に示される支配木が得られる。制御フローグラフ
より基本ブロックＢ２の末尾から先頭に至るバックエッ
ジ１０５が検出される（処理ステップ３６）。そこで、
このバックエッジ１０５によって形成される内部の非構
造的なループを検出するために、処理ステップ３８〜４
１の処理を行う。バックエッジ１０５は同一の基本ブロ
ックＢ２を起点と終点にしているために、処理ステップ
３８では基本ブロックがＢＳ＝ＢＥ＝Ｂ２となる。処理
ステップ３９において、ＢＥがＢＳを支配していること
（ＢＥ　ｄｏｍ　ＢＳ）を確認する。支配関係を考える
場合に、通常各ノードは自分自身を支配しているものと
解釈するので、ここでは“Ｂ２　　ｄｏｍＢ２”が成立
して処理ステップ４０に分岐する。処理ステップ４０で
は「Ｂ２からＢ２に至る全ての基本ブロック」、すなわ
ちＢ２のフラグをｏｎにする。処理ステップ４１ではバ
ックエッジ１０５のフラグをｏｆｆにする。これでフラ
グがｏｎのエッジがなくなるために、処理ステップ３７
から処理ステップ４２に分岐する。図５（ｃ）に示され
る支配木では基本ブロックＨからＴに至る経路ではＢ１
，Ｂ２，Ｂ３の３つの基本ブロックがあるが、このうち
フラグがｏｎのものＢ２（基本ブロック１０６）を取り
除きループ中の制御に依存しない基本ブロックＢ１，Ｂ
３を得る。その結果を図５（ｃ）に示されるソースコー
ドと比較すると、基本ブロックＢ１中の実行文６３で定
義される変数Ｊは誘導変数であるが、基本ブロックＢ２
中の実行文６４で定義される変数Ｋは、ＤＯループの１
回以上の繰り返しにつき２回以上実行される可能性があ
るために、変数Ｋは誘導変数にならないことが分かる。

【００１６】上述した２つの実施例では、ソースコード
から制御フローグラフと支配木を使用して、ループ中で
変数を定義している誘導変数を検出する仮定を示してい
る。この出願の発明では、基本ブロックを単位として並
列化対象ループを解析し、ループの繰り返しの都度ルー
プ内の制御構造に依存することなく確実に１回だけ実行
される基本ブロックを検出する機能を特徴としている。 そこでさらに、２つの制御フローグラフを例として制御
に依存しない基本ブロックを検出する過程について説明
する。

【００１７】図６（ａ）に示されるループ中の制御フロ
ーグラフの場合に、図３に示される処理ステップ３３で
図６（ｂ）に示される支配木が生成され、処理ステップ
３５でバックエッジ１０７が検出される。処理ステップ
３８では基本ブロックがＢＳ＝Ｂ５，ＢＥ＝Ｂ２となり
、図６（ｂ）に示される支配木でＢ２からＢ５に至る経
路上の基本ブロック１０８、すなわちＢ２とＢ５のフラ
グをｏｎにする。処理ステップ４２では支配木でＨから
Ｔに至る基本ブロックのうちでフラグがｏｆｆのもの、
すなわちＢ１とＢ６が制御に依存することがない基本ブ
ロックとして検出される。図６（ａ）を見ると、基本ブ
ロックＨからＴまでの制御フローグラフで制御に依存し
ない基本ブロックがＢ１とＢ６の２つであることが容易
に確認することができる。

【００１８】次に、図７（ａ）に示されるループ中の制
御フローグラフの場合について考える。図３で示される
処理ステップ３３で図７（ｂ）に示される支配木が生成
され、処理ステップ３６で１０９及び１１０の２つのバ
ックエッジが検出される。バックエッジ１０９は基本ブ
ロックＢ４を終点、Ｂ２を起点としているため、図７（
ｂ）に示される支配木では、Ｂ２からＢ４に至る経路、
すなわち基本ブロック１１２で示したＢ２，Ｂ３，Ｂ４
の３つの基本ブロックのフラグをｏｎにする。さらにバ
ックエッジ１１０はＢ５を終点、Ｂ３を起点としている
ため、同様に図７（ｂ）に示されるＢ３からＢ５に至る
経路、すなわち基本ブロック１１３で示したＢ３，Ｂ４
，Ｂ５の３つの基本ブロックのフラグをｏｎにする。以
上の処理のうち、処理ステップ４２において図７（ｂ）
に示されるＨからＴに至る基本ブロックの経路上で、フ
ラグがｏｆｆの基本ブロックＢ１，Ｂ６，Ｂ８が制御に
依存しないものとして検出される。この解析により制御
に依存しない基本ブロックが正しく検出されていること
は、図７（ａ）に示される制御フローグラフにより確認
することができる。

【００１９】

【発明の効果】以上説明したように、この発明のコンパ
イラにおける並列化処理装置によれば、制御フローグラ
フをもとに、支配木生成部で解析対象ループの支配木を
生成し、バックエッジ検出部で解析対象ループ中の非構
造的なループを検出し、非制御依存ブロック検出部でル
ープの繰り返しの都度確実に１回だけ実行される基本ブ
ロックである非制御依存ブロックを検出し、誘導変数定
義文検出部で非制御依存ブロックを対象として誘導変数
の定義文を検出するようにしたので、ループにおける制
御構造に依存することなく、１回のループの繰り返しの
都度１回だけ実行される実行文を検出することができ、
その結果ループ中の任意の制御構造に対する誘導変数を
容易に、かつ確実に検出することができるという優れた
効果を奏する。

【図面の簡単な説明】

【図１】この発明の実施例であるコンパイラにおける並
列化処理装置が適用するコンパイラの全体構成を示すブ
ロック図である。

【図２】図１の誘導変数検出部の構成を示すブロック図
である。

【図３】図１の誘導変数検出部の動作を説明するための
フローチャートである。

【図４】この発明の実施例であるコンパイラにおける並
列化処理装置の処理を説明するための説明図である。

【図５】この発明の実施例であるコンパイラにおける並
列化処理装置の処理を説明するための説明図である。

【図６】この発明の実施例であるコンパイラにおける並
列化処理装置の処理を説明するための説明図である。

【図７】この発明の実施例であるコンパイラにおける並
列化処理装置の処理を説明するための説明図である。

【図８】従来のコンパイラにおいて誘導変数の検出と削
除の処理を説明するための説明図である。

【図９】従来のコンパイラにおいて誘導変数の検出がで
きない場合の処理を説明するための説明図である。

【符号の説明】

１　　　　誘導変数検出部 ２　　　　支配木生成部 ３　　　　バックエッジ検出部 ４　　　　非制御依存ブロック検出部 ５　　　　誘導変数定義文検出部 ７　　　　解析情報 １１　　　　ソースコード １２　　　　中間コード １３　　　　並列化オブジェクトコード１４　　　　ソ
ースコード解釈部 １５　　　　最適化処理部 １６　　　　並列化処理部 １７　　　　コード生成部 ３１〜４２　　　　処理ステップ ４３〜４６，５１〜５９，６１〜６６　　　　実行文１
０１〜１０４　　　　制御フローグラフのエッジ１０５
，１０７，１０９，１１０　　　　制御フローグラフの
バックエッジ １０６，１０８，１１２，１１３　　　　非構造ループ
に含まれる基本ブロック

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　ソースコードを入力として並列実行可
   能な箇所を検出するか、あるいは等価性を損うことなく
   ソースコードを書き換えることにより並列実行可能な部
   分を生成し、密結合マルチプロセッサ上で実行可能なオ
   ブジェクトコードを出力するコンパイラにおいて、制御
   フローグラフをもとに、解析対象ループの支配木を生成
   する支配木生成部と、上記解析対象ループ中の非構造的
   なループを検出するバックエッジ検出部と、ループの繰
   り返しの都度確実に１回だけ実行される基本ブロックで
   ある非制御依存ブロックを検出する非制御依存ブロック
   検出部と、上記非制御依存ブロックを対象として誘導変
   数の定義文を検出する誘導変数定義文検出部とから構成
   される誘導変数検出部を備えたことを特徴とするコンパ
   イラにおける並列化処理装置。