JPH0640309B2 - コンパイラにおけるループ内ブロック並び換え処理方式 - Google Patents

コンパイラにおけるループ内ブロック並び換え処理方式

Info

Publication number
JPH0640309B2
JPH0640309B2 JP58226310A JP22631083A JPH0640309B2 JP H0640309 B2 JPH0640309 B2 JP H0640309B2 JP 58226310 A JP58226310 A JP 58226310A JP 22631083 A JP22631083 A JP 22631083A JP H0640309 B2 JPH0640309 B2 JP H0640309B2
Authority
JP
Japan
Prior art keywords
block
loop
rearrangement
processing
order
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.)
Expired - Lifetime
Application number
JP58226310A
Other languages
English (en)
Other versions
JPS60118934A (ja
Inventor
耕一郎 堀田
正孝 山梨
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujitsu Ltd
Original Assignee
Fujitsu Ltd
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Fujitsu Ltd filed Critical Fujitsu Ltd
Priority to JP58226310A priority Critical patent/JPH0640309B2/ja
Publication of JPS60118934A publication Critical patent/JPS60118934A/ja
Publication of JPH0640309B2 publication Critical patent/JPH0640309B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Landscapes

  • Devices For Executing Special Programs (AREA)

Description

【発明の詳細な説明】 (A)発明の技術分野 本発明は、コンパイラにおけるループ内ブロツク並び換
え処理方式、特に、コンパイラにおいて、DOループな
どのループ内でのブロツクの配列順序を処理の流れにし
たがう順に並び換えを行なうようにしたコンパイラにお
けるループ内ブロツク並び換え処理方式に関するもので
ある。
(B)技術の背景と問題点 与えられたソース・プログラムからオブジエクト・プロ
グラムを生成するコンパイラにおいては、上記与えられ
たソース・プログラムに対して最適化処理を行なつた上
で、最適化オブジエクト・プログラムを生成することが
行なわれている。このような最適化処理に当つては、プ
ログラムの構造が複雑な場合、例えばDO拡張範囲など
があつて、論理的には1つのループに属していながら物
理的には不連続になつている如き場合には、ループ単位
に行なう最適化処理(ベクトル化など)が不可能となつ
ていた。
(C)発明の目的と構成 本発明は、上記の点を解決することを目的としており、
論理的に1つのループと認識できる複数のブロツクにつ
いて、実行順序になるようにブロツクの並び換えを行な
い、上述の最適化処理を可能にするようにすることを目
的としている。そしてそのため、本発明のコンパイラに
おけるループ内ブロツク実行順序変更処理方式は、与え
られたソース・プログラムを読込んで最適化処理を含む
処理を実行した上で上記ソース・プログラムに対応する
最適化オブジェクト・プログラムを生成するコンパイラ
にソース・プログラム並び換え処理機構をもうけ, 該ソース・プログラム並び換え処理機構は,上記ソース
・プログラム中のループ取出し部,当該ループ内のブロ
ックに対して処理の実行順序について深さ優先の探索処
理によって認識して順序付けを行う実行順序認識部,お
よび当該実行順序認識部によって上記順序付けの行われ
た当該ループ内のブロックについて物理的な順序並び換
えを上記順序付けの結果にもとづいて行う物理的な順序
並び換え部を少なくともそなえると共に, 上記物理的な順序並び換え部は少なくともブロックの並
び換え結果に伴なう実行論理保障処理,ブロックの物理
位置移動処理および当該ブロックの移動に伴なって生じ
る内部ループの物理位置移動処理を実行するよう構成さ
れ, 上記最適化処理の実行に先立ってブロックが物理的な配
列順序にしたがって実行される形に並び換えるようにし
た ことを特徴としている。以下図面を参照しつつ説明す
る。
(D)発明の実施例 第1図は本発明の問題点を説明する説明図、第2図は本
発明の並び換え処理方式が適用されるコンパイラの一実
施例構成、第3図ないし第5図は夫々本発明による並び
換え処理を説明する説明図、第6図は本発明の一実施例
処理態様を表わすフローチヤート、第7図は第6図図示
の物理的な順序並び換え部における一実施例処理態様を
表わすフローチヤートを示す。
一般にソース・プログラム内のDOループは第1図図示
左側に示す如き形で与えられていることがある。即ち、
当該DOループの場合、ループ内のブロツクを実行して
ゆく間に「GOTO 30」に達したとき図示「30
×××××」なるブロツクにジヤンプし、「 =A
()」なるブロツクにて参照が行なわれ、「GOTO
20」に達したとき図示「20 ×××××」なる
ブロツクにジヤンプし、「A()= 」なるブロ
ツクにて定義が行なわれ、「GOTO 40」なるブロ
ツクにし、図示「40 CONT」にジヤンプし、一
連の処理がループするように与えられている。この場合
には、上記の如く、ループ内で先に参照が行なわれ、次
いで定義が行なわれる形となつているが、第1図図示左
側に示すプログラムの場合にブロツクの物理的配置から
みると先に定義が存在し次いで参照が存在している形と
なつており、コンパイラ内での最適化処理機構における
処理に当つて好ましくない。このために、第1図図示左
側のプログラムの場合には、図示右側の形に即ち物理的
配置順と実行順とが合致するように並び換えを行なうこ
とが望ましい。
第2図は本発明の並び換え処理方式が適用されるコンパ
イラの一実施例構成を示している。図中の符号1はコン
パイラ、2はソース・プログラム、3はオブジエクト・
プログラム、4は本発明におけるプログラム並び換え処
理機構、5はコンパイラ内における最適化処理機構を表
わしている。図において、コンパイラ1は、与えられた
ソース・プログラム2を読込んで並び換え処理機構4に
おいて、第1図図示左側に示す如きループを抽出した上
で後述の如く必要に応じて並び換えを実行し、その上で
最適化処理機構5において最適化を実行し、最適化オブ
ジエクト・プログラム3を生成する。
第1図図示左側に示した如きループにおいて、並び換え
を実行することが望まれる典形的な態様が、第3図およ
び第4図に示されている。図示α,A,B,……は夫々
単一のブロツクあるいは物理的な配列順と実行順とが合
致している複数のブロツク(ブロツク群)を表わしてい
る(以下、α,A,B,……を簡単のためにブロツクと
いう)。ブロツクα,ブロツクA,ブロツクB,……に
は夫々少なくとも次に実行されるブロツクをポイントす
るポインタをそなえており、図示矢印は当該ポインタに
て指示される実行順を表わしている。第3図図示左側の
プログラムの場合、ループの存在に対応するブロツク
(バツク・ターゲツト)αと、ループを構成するブロツ
クA,B,C,Dが存在しているが、この場合には、図
示矢印からも判る如く、ブロツクの配列順と処理の実行
順とが一致していない。このようなケースにおいては、
第1図図示の並び換え処理機構4において、第3図図示
右側のプログラムの如く、ブロツクの並び換えが行なわ
れる。第3図図示の場合には、ブロツクの物理的な位置
の並び換えを行なうだけでも実行論理は保障されてい
る。
第4図図示左側のプログラムの場合には、図示右側に示
す如く、整理すると、ブロツクAからブロツクFまでの
1つのループ内に、いれこ式にブロツクDからブロツク
Eまでに内部ループが存在している態様を示しており、
かつ第4図図示左側のプログラムの場合には見掛け上ブ
ロツクAからブロツクCまでのループの外部に、ブロツ
クα′,D,……E,Fが存在しているように観察され
る形となつている。
第4図図示左側のプログラムは図示右側のプログラムの
如く並び換えが行なわれるが、図示ブロツクα′を並び
換えるに当つては、いれこ式となつている内部ループに
ついても一緒に並び換えが行なわれる。即ち第4図図示
右側のプログラムにおいてはブロツクBとブロツクCと
の間にブロツクα′のみでなくブロツクα′,D,……
E,Fが存在するようにされる。
第5図は、最適化などのために必要に応じて、並び換え
が行なわれる態様を示している。第5図図示左側のプロ
グラムの場合、ブロツクAからブロツクBまたはブロツ
クCに処理が進み、ブロツクBおよびブロツクCからブ
ロツクDに進むようになつている。この場合には、ブロ
ツクBの末尾にブロツクDへの無条件分岐が存在してい
る。当該図示左側のプログラムを図示右側のプログラム
へ変更する必要があつた場合には、実行論理を保障する
ために、上述のブロツクBの末尾の無条件分岐を削除し
かつブロツクCの末尾にブロツクDへの無条件分岐を新
しく附加することが必要となる。
上述の如き並び換え処理を実行する処理は第2図図示の
並び換え処理機構4において実行される。第6図は当該
並び換え処理のための一実施例処理態様を表わすフロー
チヤートを示している。処理が開始されると並び換え処
理機構4は、取出し部6において、ループの存在を摘出
する。当該摘出は、従来公知の如く、プログラム中のい
わゆるバツクターゲツト(第3図図示などのブロツク
α)を摘出することによつて行なわれる。ループが摘出
されると、当該ループ内のブロツクに対して、実行順序
認識部7において処理の実行順序を認識する処理を行な
う。該処理は、DFS(Deapth First Search−深さ優
先の探索)と呼んでいる公知のアルゴリズムを利用し、
順序付けを行なう。該順序付けによつて順序が判明する
と、物理的な順序並び換え部8においてブロツクの並び
換えが行なわれる。このような処理は、すべてのループ
についての処理が終了するまで行なわれる。
第7図は、第6図図示の物理的な順序並び換え部8にお
ける一実施例処理態様を表わすフローチヤートを示して
いる。
図示処理9において上述のバツクターゲツトを把握して
おいて、処理10において現に処理対象となるブロツク
を取出す。当該処理対象ブロツクが例えば第5図図示左
側プログラムにおけるブロツクCの如きものであつた場
合には、第7図図示の実行論理保障処理11において、
上述の如く、ブロツクCからブロツクDへの無条件分岐
を附加するなどの処理が行なわれる。即ち実行論理保障
処理11は、或るブロツクの物理的位置を移動すること
によつてくずれるかも知れない実行論理の乱れを補なう
ようにする。
次いで、ブロツクの物理位置移動処理12において、例
えば第5図図示のブロツクCの場合であれば、当該ブロ
ツクCをブロツクAの次に位置するように配列換えを行
なう。当該物理位置の移動が行なわれるブロツクが第4
図図示のブロツクα′の如く内部ループのバツクターゲ
ツトを構成している場合には、第7図図示の内部ループ
の物理位置移動処理部13において、内部ループ全体が
ブロツクα′と一緒に配置換えされる。そして当該現ブ
ロツクを直前ブロツクとみなすようにして新しい現ブロ
ツクについて同様な処理を行なつてゆく。
(E)発明の効果 以上説明した如く、本発明によれば、ループ内ブロツク
の配置順序が処理実行順序と合致する形となり、コンパ
イラ内での最適化処理機構における処理が可能となる。
また実行論理保障についてや内部ループに対する移動に
ついても、あわせて配慮しているので、並び換え処理の
結果において無理矛盾を生じたりすることがない。
【図面の簡単な説明】
第1図は本発明の問題点を説明する説明図、第2図は本
発明の並び換え処理方式が適用されるコンパイラの一実
施例構成、第3図ないし第5図は夫々本発明による並び
換え処理を説明する説明図、第6図は本発明の一実施例
処理態様を表わすフローチヤート、第7図は第6図図示
の物理的な順序並び換え部における一実施例処理態様を
表わすフローチヤートを示す。 図中、1はコンパイラ、2はソース・プログラム、3は
オブジエクト・プログラム、4は並び換え処理機構、6
はループ取出し部、7はループ内の実行順序認識部、8
は物理的な順序並び換え部、11は実行論理保障処理、
12はブロツクの物理位置移動処理、13は内部ループ
の物理位置移動処理を表わしている。

Claims (1)

    【特許請求の範囲】
  1. 【請求項1】与えられたソース・プログラムを読込んで
    最適化処理を含む処理を実行した上で上記ソース・プロ
    グラムに対応する最適化オブジェクト・プログラムを生
    成するコンパイラにソース・プログラム並び換え処理機
    構をもうけ, 該ソース・プログラム並び換え処理機構は,上記ソース
    ・プログラム中のループ取出し部,当該ループ内のブロ
    ックに対して処理の実行順序について深さ優先の探索処
    理によって認識して順序付けを行う実行順序認識部,お
    よび当該実行順序認識部によって上記順序付けの行われ
    た当該ループ内のブロックについて物理的な順序並び換
    えを上記順序付けの結果にもとづいて行う物理的な順序
    並び換え部を少なくともそなえると共に, 上記物理的な順序並び換え部は少なくともブロックの並
    び換え結果に伴なう実行論理保障処理,ブロックの物理
    位置移動処理および当該ブロックの移動に伴なって生じ
    る内部ループの物理位置移動処理を実行するよう構成さ
    れ, 上記最適化処理の実行に先立ってブロックが物理的な配
    列順序にしたがって実行される形に並び換えるようにし
    た ことを特徴とするコンパイラにおけるループ内ブロック
    並び換え処理方式。
JP58226310A 1983-11-30 1983-11-30 コンパイラにおけるループ内ブロック並び換え処理方式 Expired - Lifetime JPH0640309B2 (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP58226310A JPH0640309B2 (ja) 1983-11-30 1983-11-30 コンパイラにおけるループ内ブロック並び換え処理方式

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP58226310A JPH0640309B2 (ja) 1983-11-30 1983-11-30 コンパイラにおけるループ内ブロック並び換え処理方式

Publications (2)

Publication Number Publication Date
JPS60118934A JPS60118934A (ja) 1985-06-26
JPH0640309B2 true JPH0640309B2 (ja) 1994-05-25

Family

ID=16843195

Family Applications (1)

Application Number Title Priority Date Filing Date
JP58226310A Expired - Lifetime JPH0640309B2 (ja) 1983-11-30 1983-11-30 コンパイラにおけるループ内ブロック並び換え処理方式

Country Status (1)

Country Link
JP (1) JPH0640309B2 (ja)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS6235944A (ja) * 1985-08-09 1987-02-16 Fujitsu Ltd コンパイラ処理方式

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS5833775A (ja) * 1981-08-21 1983-02-28 Hitachi Ltd コンパイル方法

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
岩波講座情報化学12算法表現論(昭57−5−10)株式会社岩波書店,P26〜34

Also Published As

Publication number Publication date
JPS60118934A (ja) 1985-06-26

Similar Documents

Publication Publication Date Title
JPH0640309B2 (ja) コンパイラにおけるループ内ブロック並び換え処理方式
JPS63142431A (ja) パイプライン制御方式
JPH07152694A (ja) マルチプロセッサシステムのバリア同期装置
JPS6323563B2 (ja)
JPH04252336A (ja) プログラム最適化処理装置
JPH0380327A (ja) プログラムの同一箇所検出方式
JP2868127B2 (ja) 字句解析における空白読み飛ばし装置
JPH05297923A (ja) 工具径路データ作成装置
JP2595815B2 (ja) プログラム修正量判定処理装置
JP2797818B2 (ja) バリア同期挿入処理装置
JPH0540640A (ja) プログラム変換方式
JPH0659905A (ja) コンパイラの並列化処理方式
JPH02227703A (ja) プログラマブルコントローラシステム
JPH0377141A (ja) コンパイル処理装置
JPH033045A (ja) 高速ファイル処理方式
JPH08115220A (ja) ループ最適化方法
JPH01295336A (ja) クリティカルセクション最適化方式
JPH022425A (ja) 多方向分岐演算の高速化方法
JPH0776926B2 (ja) ループ制御処理方法
JPH0311466A (ja) 命令スケジューラ
JPH02224167A (ja) コマンドとサブコマンドの一括入力方式
JPH03164937A (ja) 論理型言語プログラム実行処理方式
JPH03161837A (ja) 多重doループ演算高速化ソースプログラム生成方式
JPH04102172A (ja) 情報検索方式
JPH03185522A (ja) 推論エンジン