Compiler Construction Lecture 2/5

基本ブロックとフローグラフ

式の単位での最適化と、式を越えた大域的な最適化を考えるために、基本ブロック(Basic Block)とフローグラフ(Flow Graph)というものが工夫された。

基本単位は、単純に言えば、条件分岐や分岐を含まない逐次計算の部分である。フローグラフは、一つの手続の中で基本ブロックを分岐を結んだものである。

mc.c の reverse() はリストを逆順にするものだが、

   484	reverse(t1)
   485	int t1;
   486	{int t2,t3;
   487		t2=t1;
   488		while(type!=t1)
   489		{	t3=heap[type+1];
   490			heap[type+1]=t2;
   491			t2=type;
   492			type=t3;
   493		}
   494		type=t2;
   495	}

としてよい。

このフローグラフを考えてみよう。このフローグラフ(flow graph)を作るには、まず基本ブロック(basic block) を抜きだす。基本ブロックは、分岐(barch)の入らない部分のまとまりをさす。次に、flow-chart のように基本ブロックを接続する。あと、入力される変数と、出力される変数を記述する。

flow-chart と違い、基本ブロックは最適化の単位となるので、可能な限り一つにまとめなければならない。結果は以下のようになる。

基本ブロック

基本ブロック内部では条件分岐がないので、文(statement)の実行順序(execution order)をプログラムの意味を変えない範囲で変更してコンパイルして良い。これは局所的最適化と呼ばれる。

基本ブロックの間で再利用出来る式、計算する必要のない式、あるいは、使わない変数などを見つけると、それらを共有したり、削ったりすることができる。さらに、簡単なループの場合は内部の基本ブロックの定数などをループの外に出すことも行われる。これらは大域的最適化と呼ばれる。これらが終わると、変数にレジスタを割り当てる(register allocation)。RISCでは、このレジスタの割り当て方法が重要である。

局所的最適化 Local Optimization

局所的最適化の代表的なものは peep hole optimization と呼ばれるものである。これはいったんコードを生成した後に、そのコードを狭い範囲で見て、より良いものに置き換えられるならば置き換えるというものである。共通部分式の置き換えなどはできないが、簡単で効果的であることが知られている。コード生成の時点で行ってしまっても良い。例えば、micro-C ではそうなっている。

mov r3,a(r31); mov r3,a(31) などは後者は必要がない if(0) {...} などの決まった条件分岐を消す
連続した分岐を一つにする
a+0, a*1 などの計算を止める
a*2 などを足し算で置き換える
load and update などのPowerPC独自の機能を使う

より進んだコンパイラ

ターゲット

組み込み用マイクロプロセッサ
RISCプロセッサ
ベクトル計算機
並列計算機

CPU内部でのコンパイル

コードモーフィング (Crusoe)

RISCコードへの変換 (Pentinum II)

RISC での問題

深いパイプライン

スーパースカラ

分岐予測

リーオーダ

VLIW

複数演算を同時に実行する命令 (内積演算、MMX)

SIMD 命令

ソフトウェアパイプライン

ベクトルプロセッサ

添字の干渉の判定(diophantos equation)

ランタイムコンパイラ

問題の持つ文法的構造

音声、画像の持つ文法的構造

ツール自体からくる文法的構造

複雑さを構成する文法構造

   セルオートマトン
   ニューラルネットワーク

問題

記号処理とは文字などで表されたデータを処理することである。これに対して、音声解析や画像処理、ロボットの動作などは、非記号処理と言える。非記号処理におけるコンパイラの役割について、1000-2000字程度で考察せよ。