言語処理工学Ａ補助プリント1
				井上 克郎  
コントロールフロー解析、データフロー解析
  参考図書 Aho, Sethi, Ullman, Compilers: Principles, Techniques, and Tools
		Addison Wesley, 1986   0-201-10088-6 この分野のバイブル

（１）基本ブロックの作成(Basic Block)
基本ブロック：3番地コードの列で、その実行は、一番上の命令のみから始まり、途中の命
令で止まったり、分岐せずに、最後の命令まで到達するもの。最後の命令での分岐は許され
る。途中での飛び込み許さない。
コンパイラで3番地コードを生成後、最適化の最初の段階として、3番地コード列をできる
だけ長い基本ブロックに分割する。

Step 1: Leader(基本ブロックの最初の命令）を求める。以下のいずれかの条件に当てはまる
ものをリーダとする
	条件1； 3番地コード列の最初の命令
	条件2； 条件、無条件分岐の行き先になっている命令（ラベルが付いている）
	条件3； 条件、無条件分岐命令の直後の命令
Step 2: 各リーダを最初の命令とし、次のリーダの直前を最後の命令として基本ブロックを
構成する。もし、次のリーダを見ずにプログラムが終わった場合は最後の命令をその基本ブ
ロックの最後の命令として構成する。

演習問題：教科書171頁の８．3のコードのフローグラフを作れ

各基本ブロックを頂点として、制御の移動の可能性があるばあいに対応する基本ブロック間
に辺をひいたものを、「フローグラフ」と呼ぶ。辺の始点の基本ブロックを終点の基本ブロ
ックに対してPredecessor、逆に終点を始点に対してSuccessorと呼ぶ。
フローグラフの入り口の頂点を開始頂点(initial node)と呼ぶ。

（２）ループの検出
Dominator支配接点: フローグラフ上で開始頂点からある頂点ｎに至るすべての経路が途
中、頂点ｄを経由する場合、ｄはｎのdominatorと呼ぶ。各頂点は、自分自身のdominator
である。
演習：先ほど求めたフローグラフの各頂点のdominatorを求めよ。

dominatorの関係を木で表現したものをdominator木と呼ぶ。また、ある頂点のdominator
のうち、自分自身以外で、もっとも近いものをimmediate dominatorと呼ぶ。

Dominatorの求めかた
n0 --- フローグラフの入り口の頂点
Ｎ --- フローグラフの全頂点
D(n) --- 頂点ｎのdominatorを入れる集合
 1	D(n0) := {n0};
 2	for n  in  N-{n0}  do  D(n):= N;
 3	while changes to any D(n) occur do
 4		for n in N-{n0} do
 5			D(n):= {n} ∪    ∩D(p) ;
					pはｎの親

演習問題：このプログラムは、必ず停止するか？その理由は？

Natural Loop:フローグラフの部分グラフで以下の性質を持つもの。
＊ 他の部分グラフからの唯一の入り口を持ち（この入り口はヘッダーと呼ばれる）、ヘッ
ダーはループのなかの各頂点のdominatorになっている。
＊ 各頂点からヘッダーへ至る一つ以上の経路がある。ヘッダーに入るこの部分グラフの辺
をBack edge後退辺という。

Natural Loop の求めかた
 １ まず、すべてのback edgeを求める。（dominateされる頂点からdominatorに至る辺
を見つける）
 ２ 各back edgeについて以下の手続きを行う。
	stack:= empty;
	loop:={d} ;
	insert(n) ;
	while stack is not empty do begin
		pop m
		for each predecessor p of m do insert(p)
	end

	procedure insert(m);
	if m is not in loop then begin
		loop:= loop ∪ {m};
		push m onto stack
	end;

簡約可能フローグラフReducible Flow Graph
今、フローグラフからback edgeを除いたグラフが、入り口から各頂点が到達可能な閉路無
しのグラフの場合、そのフローグラフを簡約可能と言う。if-then-else, while-do, continue, 
breakなどの制御構造によって作られるプログラムは、簡約可能なフローグラフを作る。




次のテキストへ