同じ結果、より安いプログラム — CFG と SSA

一言でいうと

最適化は、プログラムを同じ結果を出す、より安いプログラムに変えることです。木では、定数をあらかじめ計算し、決まっている枝を取り除き、命令の並びでは、基本ブロックと制御フローグラフ(CFG)を組み立てて、入り込む道のないコードを消します。そのグラフ上でドミネーターを求めると、実務のコンパイラーの中間表現であるSSAが、φをどこに置くかまで計算できます。

なぜ必要なのか

人は、読みやすく書きます。60 * 60 * 24と書いて86400とは書かず、デバッグ用のif (false) { … }を残し、returnのあとに行を残すこともあります。モジュール6のコンパイラーはこれを書かれたまま移すので、ループの中の60 * 60 * 24は、回るたびに乗算2回になります。コンパイラーが代わりにあらかじめ計算できれば、人は読みやすいコードを書いたまま、速いプログラムを得られます。

ただし、最適化には超えてはならない線が1つあります。結果が変わってはいけません。7 / (3 - 3)を「定数だから先に計算」しようとして、コンパイラーが落ちたり、エラーをなくしてしまったりしてはいけません。その行は、実行されたときにその場で0による除算のエラーを出す必要があります。最適化器は、できることよりもしてはいけないことを先に知っているほうが、よい最適化器です。

どう動くのか

定数畳み込み。木を下から上へたどりながら、両側がリテラルの演算を計算して、リテラル1つに置き換えます。64ビットの折り返しと0方向への除算はインタプリターとまったく同じに守り、実行するとエラーになる式(0による除算、負の指数、型が合わない演算)は、畳まずに残します。畳んだリテラルは、元の演算子の位置を受け継ぎます。false && f()は右が実行されないので、丸ごとfalseで、true && eはeになります。if (true)はその枝(ブロックのまま。スコープが残るように)に、while (false)は丸ごと消えます。

基本ブロックとCFG。命令の並びで、最初の命令、ジャンプの行き先、ジャンプ・RETURNの直後を「リーダー」として印を付けると、リーダーから次のリーダーの手前までが基本ブロックです。ブロックの中へは最初の命令からだけ入り、最後の命令からだけ出ます。ブロックごとに次のブロック(流れ落ちる側、ジャンプする側)を書いたものがCFGです。入口からCFGをたどって届かないブロックは、消してかまいません。このコースのコンパイラーは、すべての関数の末尾にCONST 0 · RETURNを付けるので、returnで終わる関数ごとに、その2つの命令が届かないコードとして残っています。消したあとは、残ったジャンプのオフセットを新しい位置で測り直す必要があります。

fn pos(v) { if (v < 0) { return 0; } return v; }

 B0  0 GET_LOCAL 0         B0 → B1(흘러내림), B2(점프)
     1 CONST 0   ; 0
     2 LT
     3 JUMP_IF_FALSE 2 ; → 6
 B1  4 CONST 0   ; 0       B1 → 없음(RETURN)
     5 RETURN
 B2  6 GET_LOCAL 0         B2 → 없음
     7 RETURN
 B3  8 CONST 0   ; 0       ← 입구에서 닿지 않는다(컴파일러가 붙인 꼬리): 지운다
     9 RETURN

支配とSSA。ブロックdがブロックbを支配するとは、入口からbへ行くすべての道がdを通るということです。すべてのブロックのドミネーターの集合は、「bのドミネーター = {b} ∪ (前のブロックたちのドミネーターの共通部分)」を、もう変わらなくなるまで繰り返して求めます。これがなぜ必要かというと、実務のコンパイラー(LLVM・GCC)の中間表現はSSAで、すべての変数がちょうど1回だけ代入される形式だからです。x = 1; if (c) x = 2; print x;をSSAにすると、x1 = 1、x2 = 2、そして2つの道が合流する場所にx3 = φ(x1, x2)ができます。φは「どの道から来たかによって選ぶ」という意味です。

      B0: x1 = 1; if c
       /          \
  B1: x2 = 2       |
       \          /
      B2: x3 = φ(x1, x2); print x3        ← B2 는 B1 의 지배 경계

φをどこに置くかは、支配境界(dominance frontier)が教えてくれます。ブロックbの支配境界は、bが支配する場所から1歩出て、最初に支配が途切れるブロックたち、つまりbから来た値と、別の道から来た値が最初に出会う場所です。変数が代入されるブロックたちの支配境界にφを置き、新しく置いたφも代入とみなして、もう増えなくなるまで広げます(反復支配境界)。

現場での姿

-O2の処理のほとんどは、このグラフの上で行われます。定数伝播、デッドコード除去、共通部分式の除去、ループの外への巻き上げが、すべてSSAとCFGの上の計算です。SSAでは、変数ごとに定義が1つなので、「この値はどこから来たのか」が一目でわかるからです。モジュール10でclangのLLVM IRを開くと、phi命令を直接目にします。
最適化がバグを露呈させるとき。「-O0では動くのに、-O2では結果が違う」は、ほとんどが最適化器のバグではなく、プログラムの未定義動作(符号付き整数のオーバーフローなど)を、最適化器が「起こらないこと」と信じて消した結果です。結果を変えないという約束は、定義された動作についてだけ守られます。
デバッグが難しくなる理由。最適化されたコードで、変数が「optimized out」と表示されるのは、その変数がSSAの複数の値に分割され、一部が消えたからです。

次のラボですること

opt.pyに、式の畳み込み、プログラムの畳み込み(決まっている枝の除去)、基本ブロック、CFG、届かないブロックの削除(ジャンプの測り直し)、ドミネーターと直近のドミネーター、支配境界とφの位置、そして畳み込み → コンパイル → 削除のパイプラインを作ります。採点ツールは、木・チャンク・グラフを基準と突き合わせ、最適化したプログラムが同じ結果を出しながら命令の実行が少ないかを、VMで確認します。