最適化コンパイラへのいざない (4) プログラムの構造

記事一覧

1. はじめに
2. マルチパスコンパイラ
3. 定数に関する最適化
4. プログラムの構造(この記事)
5. SSAとか...?
6. ...

TL;DR

基本ブロック，制御フローグラフ，支配木など．

対象読者

• コンパイラの内部構造について興味がある方
• コンパイラに関して精通している方（批評お待ちしております）

プログラムの構造

最適化に関する記事を書く上で，最も重要ともいえるプログラムの構造についてまだ解説していませんでした．
すでに定数畳み込みなどについて解説してしまっていますが，ここで一度立ち止まって，プログラムがどんな構造を持っているのかを考えます．

また，世の中には関数型や命令型など様々なプログラミングパラダイムがありますが，これ以降は基本的に命令型プログラムについて扱います．
関数型ではデータの流れ方がはっきりしていることが多く，処理（＝最適化）も行いやすいことが多いです．ですが，私自身，あまり関数型言語に対する最適化に詳しくありません．
加えて，関数型言語も最終的には命令列（＝機械語など低レベルなもの）として実行がなされるので，自然と命令型の考え方を使った最適化が介入してきます．
最適化手法も，これから解説するCFGや基本ブロックに対するものが多く，必然的に命令型プログラムを考えることになります．

制御フローグラフ (Control Flow Graph, CFG)

**制御フローグラフ(Control Flow Graph, CFG)**とは，**基本ブロック(Basic Block, BB)**をノードとして持つ有向グラフです．プログラムはよくCFGとして表されます．
CFGは，プログラムを実行したときに通る可能性のある経路のすべてをグラフとして表したもの，とも言えます．

... ? という方もいると思います．基本ブロックについてもまだ説明してませんからね．
とりあえず，以下にCFGの例を示します．

とりあえず，基本ブロック(Basic Block, BB)をノードとして持つ有向グラフであることが理解できれば大丈夫です．
CFGがどれほど基本的でかつ重要なものなのかは，すぐに自然とわかると思います．

用語

• 入口ブロック

  • プログラムの始めに実行される基本ブロック．今までのCFGの図で，一番上に描かれているBBです．

• 出口ブロック

  • プログラムの最後に実行される基本ブロック．今までのCFGの図で，一番下に描かれているBBです．

基本ブロック (Basic Block, BB)

**基本ブロック(Basic Block, BB)**とは，簡単に説明すると，分岐や合流のない命令の列です．

例えば，以下のようなコードがあるとします．

a = 1
if a < 2 {
 a = 2
} else {
 a = 3
}
b = a

これを，より低レベルな命令の列として書き表すと，以下のようになります

BB1:
    a = 1
    goto BB2 if a < 2
    goto BB3
BB2:
    a = 2
    goto BB4
BB3: 
    a = 3
    goto BB4
BB4:
    b = a

CFGとして表すとこうなります．黒枠の四角1つが1つの基本ブロックを示します．

1つのBBの中には 分岐 も 合流 もありません．
BB1からBB2,BB3へは分岐があります．BB2,BB3からBB4へは合流がありますね．

用語

• 先行ブロック

  • 基本ブロックA, Bを考えます．AからBへの有向辺(経路)が存在するとき，AはBの先行ブロックといいます．

• 後続ブロック

  • 基本ブロックA, Bを考えます．AからBへの有向辺(経路)が存在するとき，BはAの後続ブロックといいます．

拡張基本ブロック （おまけ）

拡張基本ブロックは，以下の性質を満たす基本ブロックの集まりのうち最大のものです．
たまに使いますが，今はあまり気にしなくてもいいと思います．

• 先頭の基本ブロックのみが複数の先行ブロックを持つ
• 先頭以外の基本ブロックは1つの先行ブロックを持ち，その先行ブロックは当該拡張基本ブロック内にある

支配木 (Dominator Tree)

CFGに対して，**支配木(Dominator Tree)**と呼ばれるものを考えることができます．

これを理解するためには，まずは**支配(dominate)**とは何なのかを理解しなければなりません．

支配 (Dominate)

基本ブロックA, Bを考えます．このとき，入口ブロックからBへのすべての経路がAを通る時，AがBを支配すると言います．よく $ A \ dom \ B $ と書かれます．また，$ A \ dom \ A $ です．

特に $A \ dom \ B $ かつ $ A \ne B $ の時に，A は B を**厳密に支配する (strictly dominate, sdom)**と
言います．

また特に $B \ sdom \ A$ かつ，$x \ sdom \ A \quad (x \ne B)$ であるすべての $x$ について $B \ not \ sdom \ x$ であるとき，この $B$ は $A$ を**直接支配する(immediately dominate, idom)**と言います．$B = idom \ A$ です．$B$は$A$に対して1つだけ存在します．

支配木上での親ノードと子ノードの関係は，CFG上での支配関係となります．これを心に留めておくと，先ほどの図の意味がわかるのではないでしょうか．

支配辺境 (Dominance Frontier)

基本ブロックAを考えます．CFG上で，Aの支配関係から初めて外れた基本ブロックを，Aの**支配辺境 (dominance frontier)**と言います．

...? となっている方も多いと思います．これは私も例外ではなく，初めて支配辺境のことを知ったときは，何に使うんだ...? となっていました．

一応例を示すと，以下の図の青色で示したものが，ある基本ブロックの支配辺境となります．

CFGを眺めているとわかるように，合流地点にある基本ブロックは支配辺境となりえます．

支配木の計算

支配木の計算方法には様々あります．
Lengauer-Tarjan アルゴリズムという，高速に動作するものもありますが，ここでは簡単(でも遅い)な例を示します．

$D(A)$ : 基本ブロック $A$ を支配する基本ブロックの集合
$s_0$ : 入口ノード
$pred(A)$ : 基本ブロック $A$ の先行ブロックの集合

このとき

$$ D(s_0) = \{s_0\}$$

$$ D(A) = \{A\} \ \cup \ \left(\bigcap_{p \in pred(A)} D(p)\right) \quad \mbox{ただし} A \ne s_0$$

である．

支配辺境の計算

以下のようにして，効率的に計算することが出来ます．

$DF(A)$ : $A$の支配辺境
$DF_{local}(A)$ : $A$ の後続ブロックのうち， $A$ によって厳密に支配されないもの
$DF_{up}(A)$ : $A$の支配辺境にある基本ブロックのうち，$A$を直接支配する基本ブロックによって支配されないもの
$children(A)$ : $A$が直接支配する基本ブロックの集合

このとき

$$ DF(A) = DF_{lcoal}(A) \ \cup \ \left( \bigcup_{c \in children(A)} \ DF_{up}(c) \right)$$

である．

使用用途

ここまでの話を聞いても，支配という考え方や支配辺境が何に使えるのかよくわからないかもしれません．これらはこの記事以降で説明する最適化手法で役に立ちますが，今の時点では説明が難しいです．

自分で調べたい方向けにいくつか語を紹介しておきます.
Keywords: SSA (Static Single Assignment), (SSAにおいて) phi function (φ関数), mem2reg, CSE (Common Subexpression Elimination), PRE (Partial Redundancy Elimination), LCM (Lazy Code Motion), Loop Detection

簡単な例

今の段階でも支配や支配辺境が役に立つことを理解するために，簡単な例を考えます．

下のようなコードがあるとします．ifは式です．

... (aへの代入など) ...
if a < 2 { 1 } else { 2 }

ifが式でなければ，これは下のように書き直すことが出来ますね.

t := undefined
if a < 2 {
  t = 1
} else {
  t = 2
}
... (元々のif式の値はtである) ...

tは適当な方法で定義しておいて，1や2を記憶しておくために使っています．
これを命令列へ翻訳すると，例えば以下のようになります．

BB1:
  t := undefined
  goto BB2 if a < 2
  goto BB3
BB2:
  t = 1
  goto BB4
BB3:
  t = 2
  goto BB4
BB4:
  ...

上の命令列をCFGとして考えると，BB1が入口ノード，BB4が出口ノードですね．（まだこの後に続く可能性もありますが）

ここで，tについて考えます．tには1か2が代入されますが，tの値はもちろん最終的に1つに定まります．BB2 と BB3 のどちらかは通らない可能性があるのですから，当たり前です．
では，tの値は，いつ1つに定まるのでしょう?

ここで役に立つのが支配辺境です．
まずもって，1や2という値がどの基本ブロックで現れているのかというと，BB2 や BB3ですね．
そして，BB2 や BB3 の支配辺境は BB4 です．ここから，BB2 や BB3 で定義された値は BB4 で合流するとわかります．
したがって，tの値が1つに定まるのは，BB4 が実行される時だとわかりますね．

このような場合に支配辺境が役に立ちます．実はこのことが様々な最適化手法で使われています．
今後の記事をお楽しみに．

#次の記事

coming soon

SSAの話をしたい