機械語プログラムにおける　　　自動ブロック化について

(1)

機械語プログラムにおける

自動ブロック化について

（昭和48年ユ0月20日原稿受理）

情報工学科安在弘幸

〃重松保弘

電子工学科田中武美

Automatic Block Genration in Machine Language Programs

by Hiroyuki ANZAI

Yasuhiro SHIGEMATSU Takemi TANAKA

This Paper shows the method which arranges instructions of a given machine

language program in such the order that in each loops of its control flow all instruc・

tions are placed adjacently． For this， we adopt the data structure aproach． That is，

the given program is transformed into a directed graph among nodes of which the order corresponding to the sequence of instructions is introduced． Then， the order is changed by means of the loop cleansing algorithm， and at last the directed graph is transformed into the machine language program to be desired．

ラムがコンパイラによって翻訳されるとき，

1・まえがき FORTRANプログラムはコンパ，イラに対するデ

筆者らは，プログラム，特に機械語プログラムークである。

に対して，データ構造論的な立場からの接近をおプログラムは構造をもつデータである。プログこなうことによって，計算機のソフトウエア・シラムから何らかの構造的性質を抽象して陽に表現ステムにおける種々の問題の解法を与えることをしたものを，そのプログラムの抽象的データ構造試みている。本論では，与えられた機械語プログという。抽象的データ構造は，計算機の中で表現ラムに適当なデーク構造を媒介として，制御の流するとき，計算機の記憶方式の構造に依存するよれに関するブロック化を計る方法を述べている。うな何らかの形式をとらなければならない。これ

これは，ドキュメンテーション・自動フローチヤを具体的データ構造という。

一ティング，最適化，セグメント化，ページ分割ところで，以上の三者，すなわちプログラムとおよび並列処理化等に役立てられる。抽象的データ構造と具体的データ構造とにおい電子計算機のプログラムは，ある特定のアルゴて，相互に変換する手続きが存在するとすれば・

リズムを，あるプログラム言語（機械語も含む）われわれはプログラムそのものについて議論し，

で表現したものである。プログラムが計算機で実あるいは処理をする代りに，それらに対応するデ行されるとき，これらの総体を処理系という。あ一ク構造の上で議論をおこない，あるいは処理を

るプログラムが，ある処理系の入力として処理さすればよいことになる。

れるとき，そのプログラムは，この処理系に対すプログラムをデータ構造として表現する利点

るデータである。例えば，FORTRANプログは，われわれにその構造的性質に対する見通しを

(2)

よくさせるばかりではない。われわれ人間は，対

象を処理するのに洞察力を働かせ，大局的に事を 1 運ぶのを好むが，計算機で処理を行なわせるに

は，出来るだけ単純な判断や操作を繰り返し行な 2

わせるようにするのが得策だからである。その意 4000ε6；l LHI 1 0001

味で，データ構造と操作とは密接な関係がある。 400483；8 cLHI 1・oooo 3

とくに具体的データ構造を考えるとき，それに対 4008：言12 BTC 3 4014

4 する操作に十分な考慮を払わねばならない。 400C；♂；l AHI 1 0001

本論では，与えられ繊繍プ・グラムの制御 4°1°1；8： BFC° 蝋 5

の流れにループがあるとき，それが出来るだけ局 401468；？ 5HI 1 0001

所化されるように蹴語プ・グラムを作りかえる 4°18：；92 BFC° 4°°4 6

方法を述べる。これを，制御の流れに関するプロ 401C 5；68 SVC 3 0000

ックイヒという。 7

2．機械語プログラムと有向グラフ 8

一般に，プログラムにおける構造的性質には第1図機械語プログラムと有向グラフの対応

制御の流れ（Control Flow），，と情報の移動

（加工）（Information Flow）の二面がある。を終端節と呼び・先頭節から終端節への糸の機械語プログラムでは，演算，転送および入出力方向を上から下とする。この方向は明らかに・対等の命令は，情報の移動（加工）を行ない，配置応するプログラムの正常な制御の流れの方向であ順に実行されるという制御の流れをもつ。これをる。一般に・条件付分岐命令は二分岐命令であ正常な制御の流れと呼ぶ。条件付飛越し（判り・従って・これに対応する節は2本の矢をもつ断または分岐）命令（以後分岐命令という），おが・そのうち1本は・その命令の条件が満足され

よび無条件飛越し命令（以後飛越し命令という）ない場合の制御の流れの方向であり・通常これはは，このような正常な制御の流れを変える役割を正常な制御の流れ（すなわち・次に配置された命もつ命令であり，制御命令と呼ばれる。令へ）の方向である。以後この方向の矢を・そ本論では，機械語プログラムの構造的性質としての節の主枝・他を副枝と呼ぶ・

制御の流れに注目し，これを陽に表現する抽象的

たロオロロ

御の流れは矢（Arrow）に対応させる（第1

（o）（b）（c）（d）（e）

図参照）・こ暢合鰍件飛越し命令は矢だけ第2図節における糸と矢の関係

に対応させてもよい。なお，個々の節は逆変換の

必要から，対応する命令を記憶しておくようにす第2図は・1本の矢をもつ節・2本の矢をもつ

る。こうして得られた有向グラフの節の間には，節の各々における矢と糸との関係を示したものでプログラムの命令の配置の順序に対応して，自然ある。ここで次のことに注意しておく必要があな順序（全順序）がつけられる。このような有向る。すなわち，飛越し命令を矢のみで表現する場グラフを以後順序つき有向グラフと呼ぶ。な合はすべてが起りうるが，飛越し命令も節に対応お本論では，このような順序を明示するために一づける場合は，（d）と（e）は起りえず，（b）が起

本の線を通し，これを糸と呼ぼう。そして，るのは飛越し命令の場合だけである。

この順序（糸）の最初の節を先頭節，最後の節

(3)

が修飾（指標，間接番地）されている。

3機械語プ・グラムの有向グラフへの変換（2）命令を作ってそれ嫉行する（プ・グラム

本節では，与えられた機械語プログラムから，の自己修飾）。

上述の有向グラフを求める方法について述べる。（3）入力命令でデータが読み込まれるべき領域その原理は，プログラムの先頭番地から制御の流に制御の流れが入る。

れを可能な限り逐次的にたどりながら，これに並以上は，レジスタと記憶領域とからなる広義の行して有向グラフを作成してゆく方法である。分意味のデータ領域とプログラム領域との交点に起岐命令に出合ったときは，正常な制御の流れ，する現象である。

なわち主枝の方向をたどり，副枝は一時スタック（1）の場合は，静的な方法では制御の流れをたしておき，飛越し命令に出合ったときは，その行どることができなくなるので，これを断続点と呼き先も同様にスタックし，以前スタックに一時たぶ。そして，断続点における制御の流れを採集すくわえておいた制御の流れを取り出して，これをるルーチンを別に作り，断続点における命令をこたどる。その際，行き先にある命令がすでに有向のルーチンへの飛越し命令に置きかえ，その命令グラフに対応する節をもっていれば，その節に矢はこのルーチンに保存する。次に，上記の改造をを引いて，その制御の流れはそこで打切り，スタ受けたプログラムを実行することによって・断続

ックから次の制御の流れを同様に取り出す。停止点における制御の流れの情報（断続点の接続番命令は飛び越し命令に準ずるが，スタックに行き地）を採集し，次に，これを先頭番地として静的先をたくわえないことだけが異なる。な方法で有向グラフを作成する。

制御の流れが容易に判断できる場合は上記の方制御の流れが通る領域はプログラム領域であ

法でよいが，機械語プログラムでは実際に与えらる。制御の流れに存在する命令が参照する領域はれたプログラムを実行しなければ，制御の流れをデータ領域である。従って，与えられたプログラたどれない場合がある。そこで次に考えられるのムの制御の流れをたどるに伴い，与えられた言己憶は，実際に与えられたプログラムを実行させなが領域はプログラム領域とデータ領域に繰り込まれら，制御の流れに関する情報を採集する方法であてゆく。書き込みが行なわれたデータ領域にプロる。記憶上の仮想の計算機（シミュレータ）に所グラム領域が侵入する（制御の流れが入る）と与のプログラムの命令を逐次取出し，同系統の場き，（2），（3）の場合が生じる。従って（2）と合はそこで実行し，他系統の計算機ではシミュレ（3）の場合を知るには書き込みが行なわれるデー一タ上で実行させつつグラフを作る。しかし，こタ領域をチェヅクしておかなければならない。しれは実際の実行時間の恐らくは数倍から数十倍のかし，この場合には相当の時間と言［臆領域を必要計算時間と多くの記憶を必要とする。とするため，人間の介入によるか，試行錯誤的に本論では，与えられたプログラムに対して，そ断続点を採集するほうがよいと思われる。ともあ

れを計算機上で実行せずに制御の流れをたどる方れ，記憶領域において制御の流れの部分に対応す法（静的な方法）と，実際に実行しながら（あるる（参照される）データ領域を明らかにしておくいはシミュレートしながら）制御の流れをたどることは，プログラムの解析に極めて有効な情報を方法（動的な方法）とを交互に使い分け，補間さ与えることは明らかである。

せ合いながら効率的に制御の流れをたどる方法を

与える。 4ループ清掃アルゴリズム

すなわち，まず静的な方法で制御の流れを可能有向グラフのある領域で，その領域内の任意の

な限りたどって，対応する有向グラフを作成す節から，同じ領域内のどの節にでも到達可能な径

る。しかし，次のような場合に制御の流れがたど路（Path）が必らず存在するとき・その領域はれなくなる。強連結領域という。プログラムを分割しなければ（1）飛越し命令，分岐命令の番地部（行き先）ならないとき，例えばセグメンテイションやペー

(4)

ジソグにおいて，分割点がより内側の強連結領域こうして得られた順序つき有向グラフでは，制に含まれるほど，時間的損失はより増大するであ御の流れにループが存在すれば，そのループにあろう。この問題を解決するためには，強連結領域るすべての節は糸に連続して存在する。従って，

に対応するプログラム領域をできるだけまとめて糸のこの部分をまとめて1つのブロックとする。

しまい，分割点はその外に置くようにすればよループが重なっているときは階層的なブロックのい。ここでは順序つき有向グラフの節の並びを，構造ができる。一番外側の2つのブロックが互い

強連結領域にある節が糸において連続するようにに交叉しない場合，一一方から他方へ移った制御は

並びかえる手続きを与える。これをループ清掃ア元に戻らない。このことはプログラムを分割するルゴリズムという。場合，できるだけブロック外で分割した方がよいループ清掃アルゴリズムことを明らかに示している。

（i）糸の終端節の1つ上方の節をHとする。

（ii）Hより下方に（終端節まで）糸をたど 5・有向グラフより機械語プログラムへの変換

り・Hに入る矢をもつ節があれば・これを所与のプログラムから導出された有向グラフの Tとする。なければ（v）へ。節の間の順序は上述のアルゴリズムで変更されて（iii）HとTの間の糸が通っている節のなかいる。すなわち有向グラフは元のままであるが，

で・Tに行く径路にある節を残し・そうで糸を通す順序が異なっている。本節では，このよない節をすべて糸における順序は変えずにうな有向グラフに対応する機械語プログラムを得

Tの下方に移す。る方法を示す。勿論新しく得られるプログラム

（iv）Tより下方に糸をたどり・Hに入る矢をは元のプログラムと同じ働きをし，異なるのは命もつ節があれば・これを新らしくTとして令の配置順のみであって，制御の流れは保存され

（iii）へ・なければ（V）へ・ている．ここで述べる方法は，始端節から女台めて

（v）Hが糸の始端節ならば終る。そうでなけ順次下方へ糸をたどりながら各々の節に対応するれば・糸においてHの1つ上方の節を新し命令を次々に配置してゆく。その際，糸の方向とくHとして（ii）へゆく。節の主枝とが常に一致するように対応する命令を次の例は・与えられた有向グラフ（a）に・上与えるということである。すなわち

記のアルゴリズム樋用した結果を示している・（・）節が・本の矢のみをもつ場合

（第3図参照）（・．・）糸と矢が一致するとき，そのまま対応

する命令を置く。

（1−2）糸と矢が一致しないとき，対応する命

11 1， 1

令を置き，次に無条件飛越し命令を置

21 21＿H 2，く・

（2）節が主枝と副枝をもつ場合

3 30 き（2−1）糸が主枝と一致するとき，そのまま対

51…H d…T＼・な命令を置く．

（2−3）糸が主枝，副枝ともに一致しないと

6，； 6、き，命令をそのまま置き，飛越し命令を

l l 続けて置く。飛越し先は主枝の方向と一

〔a）（b）（c）致させる。

第3図ループ清掃アルゴリズムによる順序の変更なお，（1−2）における節が飛越し命令ならば

(5)

1

2

4000 4300 BFC O■4014 3 4000 4200 8TC O，4014 4014 4014

4004 4300 8FC O，4018 4004 4200 BTC O，401C 4018 401C

4008 4230 BTC 3 4000 4 4008 4210 BTC 1●4004

む

むむむ、。。C、28。 BTC 8，4・・4 …C、2・。 BTC。，、。。8 9

4004 4008

4010 El30 SVC 3●0000 5 4010 4230 BTC 3，4000

、。1、2呈96 ，，C。．・・1C 、。1、：9：6 8FC，．、。2。 3

401C 4020

4018 4300 BFC O・400C 6 4018 4200

BTC O，4018

400C 4018 4 401C 4210 8TC 1■4014 401C 4300 8FC O，4014

4014 4014

4020 4300 BFC O●4008 7 4020 ε130 SVC 3●0000

4008 0000 2

8

（a）適用前

^{（b）適用後}

第4図適用例

（1−1）に準ずる。

7．あとがき

6 TOSBAC−40の機械語プログラムにおける以上，与えられた機械語プログラムを，その制実例御の流れに最適に自動ブロック化する方法と実例筆者らは，TOSBAC−40の機械語プログラムを示した。すなわち・制御の流れのループ内にあ

に以上のアルゴリズムを適用してみた。これを第る命令をまとめて配置し・それをブロックとする

4図に示す。有向グラフを計算機で実現するに方法である。セグメンティションやページソグ

は，一般にリストが使われる。リスト要素をどの等プログラムを切断する必要があるとき・できような形にするかについては，かなり任意性があるだけブロックを外すように分断した方が計算時るが，記憶容量とこれに対する操作性とが関係す間に大きな利益をもたらすことは明らかである。

るので一般には決定できない。有向グラフは・プログラムの一般的表現であ本論ではグラフの1つの節に対して第5図のよる。従って・任意の言語（流れ図も含む）で表現

うなリスト要素を割り当てた。各リスト要素はされたプログラムの相互変換のための媒介的役割

糸，主枝副枝および命令のアドレスを指すポイを果たす。また・プログラムー般の性質や構造を

ソタから構成されている。第6図は，第4図に対調べるのに都合がよい。これらに関してはまたの応するリスト表現を出力したものである。機会に報告する。

参考文献

1） C．P． Earnest， K． G． Balke＆J． Anderson：

Analysis of Graphs l）y Ordering of Nodes， J．

ACM， Vo1．1g Jan 72．

2）安在，重松，田中：機械語プログラムのリスト表現化アルゴリズム，昭和47年度電気四学会九州支部連合大会論文集

3）安在，重松，田中：機械語プログラムの制御の流

第5図リスト要素れに関する自動ブロック化について，昭和48年度電

子通信学会全国大会論文集

(6)

THREAO HAIN sUB DEFIM THREAD HA1N sUB DEFINI

− 一一一一 ● 一一 ● ● 一一 ● 一 ● ● 一一一一一一一 ● 一 ● ● ● 一一 ● ● ● ● 一 ● ● 一 ● 一 ● ● 一一

一●●●●一一■白一一一一一一一一■■⇔一一一一一●●一●●■●⇔一●●一一一一●一一一●■■●一一一

I I ／ I I I I I ！ I I I

I 4308 1 ！ 1 4308 1 4°00 1 1 4308 1 ！ 1 4308 1 4000 1

1 1 1 ！ I I I I l I ！ I I I

…一 o…吟……一一 ………一 …一… 一一…｛……一一…一一一…………一一一……

I I I I

THRεAD HAIN 5uB DEFIM THREAD HAIN SuB DEFINI

● ● 一一 ● 一一一一 ● 一 ● 一 ● ● 一 ● 一 ● ● 一 ● 一一 ● 一一 ● 一一 ●■ ⇔ ● 一一一一一一一一一一一

一⇔一●一●●●一●一●一一一一一●一●一一一一一一一烏ロー●●一一一一一■■●一一一一一命●

I I ！ I I I 1 1 ／ 1 1 1

1 4310 1 ！ 1 4310 1 4014 1 1 4310 1 ！ 1 4310 1 4014 1 1 1 1 ！ I I I I I I ！ I I I

−一一一一

P−一一一一一一一一一一一⇔一゜一一一一一一一一一一一一一一一一一一一一一一゜一一一一一1＿一一一．一一一一一一．一一＿．一＿一一一一一一一一一一一一…

I I I I I I

THREAD HAIN SUB DEFINI THREAD HAlN 5UB DEFINI

− ● 一一一一一一一一一一一 ● 一一一一一一一一一一一一一一一一一一一一一一一一一一一一一

一一一一一・一一一一⇔一●●一●一一一●一一一一一一一●一一一一一一一一一一一一一一一一一

1 1 1 1 1 1 1 1 1 1

1 4318 1 4318 1 4308 1 401C I I 4318 1 4318 1 4308 1 401C I

I l I I I I I I I I I I

−一一一一 P−一一一一一一●一一一一一一一一一一一一●一一一一一一一一一一一一一一一一一一一＿一●−1−一一一一一一●一一一，一一一一一一一一一一一＿一●●一一一一一●●●一⇔●■

I I I I I I

THREAD HAIN sUB DEFINI THREAD HAIN sUB DEFINI

− ● ● ● ● 一 ● ● ● ● ● 一 ● 一一一一一一 ● 一 ● ● 一 ● ● 一 ● 一 ● ● ● 一一 ● 一一 ● ● 一 ● 一一 ●

一一一一一●一一一一一一●一一●一一一●一一一一一一一一一一一一●●一●●一唱●●9■■一・司●●●

1 1 ！ 1 1 1 1 1 ！ 1 1 1

1 4320 1 ！ 1 4320 1 4020 1 1 4320 1 ！ 1 4320 1 4020 1

1 1 1 ／ I I ・ I I I I ！ 1 1 1

−●●●− P●●・●一一一●一一一一一●●一一●一一一一一●一一●一●●●●一一一一●● ●一一●−1−＿●一●一一⇔●●一●●一●一一一●●一一一一一一一一一一一●一●●●一●−

I I I I I I

THREAD HAlN sUB DEFINI THREAD HAIN SUB DEFINI

− ● 一 ● 一一 ● ● 一一一 ● 一一一 ● 一 ● 一 ● ● 一一一 ● ● ● ● 一 ● ● ● ● ● 一一一一 ● 一一一 ● ● ●

一一一一一●一●一一一一⇔一一●一一一一一一一一一一一一一一一一一一一●一●●一一一一一●

I I I I I I l I 1 1

1 4328 1 4328 1 4300 1 4008 1 1 4328 1 4328 1 4300 1 4008 1

1 1 1 1 1 1 1 1 1 1 1 1

−一一●● P●一一一一●一一一吟一一 ●一一一一●一一一●●●●一一一一一一一一一一一一一■−1■一一●一一●一●●一一，吟一一一一＿一＿一一一一一一一一一一一一一●一●一●

I I

了HREAD HAIN 5∪8 DEFINI THREAD HAIN sUB DEFINI

− 一一一一一一一一一一一一一一一一一一一一一 ● ● 一 ● ● ● ■ ● ● ● ● 一一一 ● 一 ● 一一一一 ● 一

一一一 ● ● ● 一一一一一 ● 一一 ■ 吟 ● 一一一一一 ● 一 ● 一一一 ● 一一一 ● 一一一一一一一一一 ● ●●

1 1 1 1 1 1 1 1 1 1

1 4330 1 4330 1 4338 1 4。OC I I 4338 1 4330 1 4338 1 40。C I

I I I I I I I I I I I I

−一 − P−一一一一一一一一一一一一 ⇔ 一一一゜一一一一一一一…一一一・・一一．−1−＿一一一，一一一一一一．一＿∈＿一一．一一一一一一一一一一一一一

I I

I I I l

THREAD HAIN 5uB DεFINI THREAD HAIN SU8 DEF、IM

− ● ■● ● 一一一命 ● 一一一 ● 一 ● ● 句白 ● 一一 ● 一一一一 ● ● 一一 ● 一 ● 一 ● ● ● 一 ● ● 一 ● ● ●

● 一一一 ● 一 ● 一一一 ● 一白一 ● 一 ● 一一一一一一一鴫一 ● 一一一 ● 一一一一一一一一一 ● 一 ● − 1 1 ／ 1 ／ I I I I ！ 1 1 1

1 4338 1 ！ 1 ／ 1 4°10 1 1 4340 1 ！ 14340 1 4004 1

三一一一一L−一一一三一一∠一一一一＿＿三＿一∠一＿＿＿一＿三一＿＿＿＿一一＿一＿三三＿一＿−L＿一一＿三一一∠一一＿一一一：一＿一＿一，＿一一＿二＿一＿＿＿＿＿一＿：

I I I I I l

THREAD HAIN SUB DEFINI THREAD HAIN SUB DEFINI

− ● 一一 ● 一 ● ● ● ● 一一 ● ● 一 ● 一 ● 一一一白 ● 一一一一一 ● 一一一一一 ● ● 一一一一一一一一一一 ● 一 ● 一一 ● 一口 ● ● 一一 ● 一 ⇔ 一 ● ● 巳 ● ● 一一 ● 一 ● ● 一一 ● 一 ● ● 一一 ●■ 一 ● 一 ● ● ●

1 1 ！ I I I I I ／ I I I

I 4340 1 ／ 1 4340 1 4004 1 1 4330 1 ！ 1 4328 1 4018 1

1 1 1 ！ 1 工 I I I I ／ I I I

●一一一一 P−一●一一●●一一一一一一一一一一一一一一●一一一一一一一一一一工●●一一⇒一一一一1−＿一一一一●一一●●一一一●●一一一一一一一⇔一一一一一一一●●一一一一一＿

I I I I I l

I I

THREAD 閻AIN 5UB DEFINI THREAD HAIN SUB DEFINI

− 一一一一一一一一一一一一一一一一一 ● 一一一一一一一一一一一一唱 ● ● ● ● ● ● ● 吟 ■ 一 ● 一

● ^{一一}^一一一一一一 ● ● ● 一一 ● ● 一一一一一 ● 一一一可 ● 一一一一一 ● ● ● 一 ● 一一一一一一一一 1 ／ 1 ！ I I I I ！ 1 ！ 1 ！ 1 1

1 ！ 1 ！ 1 4328 1 4018 1 1 ！ 1 ！ 1 ！ 1 4010 1

1 ！ 1 ！ I I I I ！ 1 1 1 ！ I I

● 一一一 ● 一 ● ● ● ● ● 一一一一一一 ● ● 一一古● 一可 ● ● ● 一 ● ● ● 一一一一一一 ● 一一一一一一一

一一 ● 一一一 ● ● 一一一 ● ● ● 一一一一一 ● 一 ● ● 一一一 ● ， ● 一一 ● ● ● 一一 ● ● 直 ● 一一一

機械語プログラムにおける 自動ブロック化について