定数を畳み込み、CFG を組み、φ の位置を求める

目標

ASTの定数を畳み込んで決まっている枝を取り除き、モジュール6のチャンクから基本ブロックとCFGを組み立てて、届かないコードを消します。そのグラフでドミネーターと支配境界を求め、SSAのφが入るブロックを計算します。最適化したプログラムは、同じ結果を出しながら、命令の実行が少なくなければなりません。

なぜ重要なのか

最適化は、「できること」よりも「してはいけないこと」が先です。0による除算を先に計算してしまったり、コードを消したあとでジャンプをつなぎ直さなかったりすると、速いけれど間違ったプログラムになります。そして、CFG・ドミネーター・SSAは、実務のコンパイラーの最適化がすべて土台にしているデータ構造なので、ここで手で計算してみたことが、モジュール10でLLVM IRを読む目になります。

ルール

fold(식)          양쪽이 리터럴이면 계산해 리터럴 하나로(64비트 감기·0 쪽 나눗셈은 인터프리터와 같다).
                  0 으로 나누기·나머지, 음수 지수, 타입이 다른 ==, 타입이 맞지 않는 연산은 접지 않는다.
                  접은 값은 원래 노드의 위치를 물려받는다. 원래 트리는 바꾸지 않는다(copy 로 새 노드).
                  && 의 왼쪽이 false(|| 는 true)면 그 왼쪽 리터럴, 반대면 오른쪽을 접은 것.
fold_program      식을 모두 접고: if(true) → then 블록, if(false) → else(없으면 문장째 삭제), while(false) → 삭제.
leaders(code)     0, 점프 목적지(코드 끝이 아니면), 점프·RETURN 바로 다음(끝이 아니면) — 오름차순
basic_blocks      [[시작, 끝)] · cfg(code) → {"blocks", "succ"}: 흘러내리는 쪽 먼저, 점프하는 쪽 다음
                  JUMP 는 흘러내리지 않고 RETURN 은 다음이 없다. 코드 끝으로 가는 것은 적지 않는다.
remove_unreachable  입구(블록 0)에서 닿지 않는 블록을 지우고, 남은 점프의 오프셋을 새 자리로 다시 잰다.
                  상수 풀의 함수 청크도 같은 방법으로. 이름·인자 수·상수 풀은 그대로.
dominators(succ)  블록마다 지배자(자기 포함, 오름차순). 닿지 않는 블록은 []. 고정점까지 되풀이.
idom(succ)        직속 지배자(입구와 닿지 않는 블록은 None)
dominance_frontier / phi_blocks(succ, {변수: [정의 블록]})  반복 지배 경계로 φ 가 필요한 블록(오름차순)
optimize_source   (전 청크, 뒤 청크, 오류) = 파싱·의미 분석 → compile(원래) / compile(fold_program) → remove_unreachable

ステップ

/root/mini/opt.pyのfold(n)を埋めます。採点ツールが、固定の式とランダムな式250個の畳んだ木とノードの位置を突き合わせます。
fold_stmt・fold_list・fold_programを埋めます。畳み込みの前後で、実行結果が同じである必要があります。
JUMPS・jump_target・leaders・basic_blocksを埋めます。
cfg(code)を埋めます。
reachable(succ)とremove_unreachable(chunk)を埋めます。
dominators(succ)とidom(succ)を埋めます。
dominance_frontier(succ)とphi_blocks(succ, defs)を埋めます。
optimize_source(src)を埋め、/opt/fixtures/mini/programs/manifest.jsonのoptリストのプログラムごとに、前後のチャンクをVMで動かして、/root/mini/opt_report.jsonに{이름: {"before": 명령 수, "after": 명령 수, "same_output": true/false}}を書きます(プレースホルダーはプログラム名と命令数です)。

参考

python3 /root/mini/mini.py opt /opt/fixtures/mini/programs/const.miniが、最適化の前後の命令数を表示します。
コンパイラー・VMまでのファイルは、ラボを開始するときに置かれています。
よくある間違いは、0による除算を畳もうとしてコンパイラーが落ちる、畳んだ値の位置を捨てる、true && xをtrueに畳む、消したあとでジャンプのオフセットをそのままにする、JUMPも流れ落ちると見なす、φを1回しか広げない、の6つです。
セッションは60分で始まり、＋時間で延ばせます。終わると/root/miniが消えます。

定数を畳む: 畳んではいけないものから

copy.copyでノードをコピーしてから、子を先に畳みます。両側がInt・Boolのリテラルで、型が合うときだけ計算しますが、割る数が0か、指数が負なら、そのままにします。新しいリテラルは、元のノードのline・colで作ります。

決まっている枝を取り除く

文ごとに式をfoldします。ifの条件がBoolリテラルになったら、選ばれた枝(Blockなのでスコープが残ります)をもう一度fold_stmtし、枝がなければNoneで文を消します。fold_listはNoneを捨てます。関数の本体も忘れないでください。

基本ブロック

リーダーの集合に0を入れ、命令ごとに、ジャンプなら行き先(i + 1 + オフセット)がコードの中にあるときに入れ、ジャンプかRETURNなら直後(i + 1)がコードの中にあるときに入れます。並べ替えたリーダーを隣どうしで組にすると、[開始, 終了)です。

制御フローグラフ

ブロックの最後の命令を見ます。RETURNなら次はなく、JUMPなら行き先のブロック1つ、条件ジャンプなら流れ落ちるブロック(終了位置がリーダーのブロック)と行き先のブロックです。同じなら1つだけにします。それ以外は、流れ落ちるブロック1つです。行き先がコードの末尾なら、書きません。

届かないコードを消してジャンプをつなぎ直す

ブロック0からsuccをたどって届くブロックを集めます。残す命令の古い位置 → 新しい位置の表を作り(コードの末尾も新しい末尾に)、ジャンプごとに、新しいオフセット = 新しい行き先 - (新しい位置 + 1)で測り直します。定数プールのdictは、再帰で同じことをします。

ドミネーター

届くブロックごとに、最初は「届くすべてのブロック」にしておき、入口だけ{0}にします。入口でないブロックは、前のブロックたち(届くものだけ)のドミネーターの共通部分に自分を足したものに変えることを、1周のあいだ何も変わらなくなるまで繰り返します。直近のドミネーターは、厳密なドミネーターのうち、いちばん近い(ドミネーターの集合がいちばん大きい)ものです。

支配境界とφの位置

前のブロックが2つ以上あるブロックbごとに、前のブロックpから始めて、bの直近のドミネーターに届くまで、直近のドミネーターの連鎖を上がっていき、通るブロックの境界にbを入れます。φの位置は、定義ブロックたちの境界から始めて、新しく置いたφのブロックも定義とみなし、もう増えなくなるまで広げます。

最適化の前後を測る

optimize_sourceは、同じプログラムを2回コンパイルします。1回はそのまま、1回はfold_programしてからremove_unreachableです。レポートには、2つのチャンクをrun_chunkで動かしたexecutedと、出力・エラーが同じかを書きます。数字は、コードで作って書いてください。