CPU実験の記録（byコンパイラ係）

はじめに

この記事は、僕のコンパイラ係としての活動をまとめたものです。

CPU実験の紹介

東京大学理学部情報科学科の３年後期（Aセメスター）には、「プロセッサ・コンパイラ実験」（通称「CPU実験」）という名物授業があります。この実験はざっくりというと「CPUを自作しよう！」というものです。学科の30人が各３～４人の班に分かれて、それぞれが「コア係」「FPU係」「シミュレータ係」「コンパイラ係」を担当することになります。

それぞれの係の詳細な説明は他の記事に譲りますが、大まかにはコア係がいわゆる中央演算装置（命令を読み込んで、演算して、結果をレジスタやメモリに書き戻す回路）を作ります。FPU係はこれに組み込むFPU（浮動小数点演算装置）を作ります。シミュレータ係はこのコアにおける命令列（プログラム）の実行結果をC++等（に限らず好きな言語）でシミュレートするソフトウェアを書きます。*1

そしてコンパイラ係の仕事は、大まかには次のようなものです。

• MinCamlという言語*2で書かれたソースコードを読み込んで、自分たちのISA（CPUが読み込む命令列のフォーマット）に則ったアセンブリを生成する
• 動作を変えない範囲でできる限り効率の良いコードを作成するよう最適化する
• コンパイラ実験の課題をやる*3

コンパイラを書くのに使う言語はなんでもよいですが、 OCamlで書かれたMinCamlコンパイラが公開されているので、これをベースに、自班ISAへの変更、種々の最適化、等の改造を加えていく人が多いです。僕もその方針をとりました。また、RustとかPythonとかを使って一から全部自分で書く（フルスクラッチ）していた人もいました。

なお、対象とするプログラムはレイトレーシング*4を実行するプログラム（minrt）です。完全に正しく動く（いわゆる完動）と次のような画像が出ます。

アセンブラについて

なお、これら４つの係のほかにも、どの係にも属さない（よって誰がやってもいい）仕事として、アセンブリを吐いた後に、それをCPUが読める形式である機械語に直すという仕事（アセンブラの作成）があります。うちの班では、これは神たるシミュレータ係にお任せすることになりました。

この判断は次の理由から大成功だったと思っています。

第一に、コンパイラ係としては、アセンブリさえ吐けば、その後の機械語への変換は気にしなくてよくなりました。もしコンパイラ係がアセンブラも書いていたら、「シミュレータ上でうまく動かない」理由がコンパイラのせいなのかアセンブラのせいなのかがわからず、デバッグ作業が大変になっていたでしょう。（コンパイラ係はアセンブラのバグを踏まなかったので、実際にバグったらどうなったかについては何とも言えないですが……）

第二に、機械語に「もとのアセンブリの何行目か」という情報を埋め込むことで、シミュレータの実行時「現在実行している場所やブレークポイントは、もとのアセンブリの何行目か」という情報が得られるようになりました。この作業も死ぬほど面倒だったようなので、シミュレータ係以外がアセンブラを書いていたらなおさら面倒だったでしょう。

やったこと（時系列順）

日記のようなものです。

シミュレータ上完動まで（～11月上旬）

第１週の班の顔合わせの時、コア係がいきなりISAを持ってきました。びっくりしたのですが、今思えばこれが相当のアドバンテージで、第１週からもう自班ISA向けの改造を始めることができました。また、前述のとおりアセンブラをシミュレータ係にお願いしていました。そのおかげでコンパイラに集中できたのも大きいです。

種々の最適化（コンパイラ実験の課題）と並行して改造を進め、第１週終了時にはデバッグ段階に至り、第２週終了時にはレイトレのコードをエラー落ちせずにコンパイルできるようになりました（結果はもちろんまだ正しくない）。そこからアセンブラが文法エラーを出さないようなコードを生成できるようになるまでが長く*5、結局第５週までかかりました。

アセンブラに通ってからは、運のいいことにデバッグが素直に終わり（クロージャ回りが相当の闇でしたが…）11/7にシミュレータ上で完動させることができました。

中間コードの出力と、中間コードや出力コードと元のプログラムの対応関係の明示

第１週に、コンパイラ実験第１回課題として実装しました。MinCamlコンパイラのプログラムを初めて読んだ段階で全体をいじらなきゃいけないため、死ぬほど大変な作業でした。が、以降のデバッグにものすごく役に立ちました。

ついでに、コンパイルオプション-kindとして指定することで、（ほぼ）任意の最適化の直後の中間コードを出力することができるようにもしています。これは第３週くらいに実装しました。

コンパイルオプション

ここでついでにコンパイルオプションについて述べます。もともとmin-camlにも、インライン展開する関数のサイズ-inline、最適化適用の繰り返しの回数-iterを指定するオプションがあったのですが、コンパイラを使いやすくするため、上述の中間コード出力を含め、他にもいろいろコンパイルオプションを実装しました。

たとえば、-id XX と指定することで、出力ファイルの末尾にXXという文字列を追加できます。適用する最適化の種類や条件を変えて出力結果を比較するときに便利でした。また、-on XX -off YYとすることで、最適化XXを適用し、最適化YYを適用しないことができるようになります。「特定の最適化の組み合わせによりバグが生まれることもあるので、原因を切り分けるため最適化をオンオフすることができるとよい」と先輩のブログにあったので、実装してみたところ、非常に助けられました。

これらのオプションを駆使して、

./min-caml minrt -kind Logic -iter 3 -off Tuple -id 3
./min-caml minrt -kind Logic -iter 2 -off Tuple -id 2 

などと指定し、吐き出されたminrt_Logic_3, minrt_Logic_2を眺めて、３回目の最適化でバグった最適化Logicを修正していました。

共通部分式削除

初出はコンパイラ実験第２回課題でした。

特筆すべきこととしては、副作用の扱いです。副作用のある共通部分式を削除してしまうとプログラムの意味が変わってしまいます。たとえば、極端な話

let _ = print_int 1 in
let _ = print_int 1 in
...

のprint_int 1は共通部分式ですが、当然これを削除するとまずいです。しかし、副作用の有無は判定不能なので、ある程度保守的な判断をせざるを得ません。

同様の判定はElim.f（MinCaml組み込みの不要定義削除）でも必要となりますが、これを流用すると「関数呼び出しや配列への書き込みはすべて削除しない」ことになってしまいます。例えば、

let rec fib x = if x <= 2 then 1 else (fib (x-1)) + (fib (x-2)) in
let a = fib 10 in 
let b = fib 10 in ...
let _ = arr.(0) <- a in
let _ = arr.(0) <- a in
...

のような場合は共通部分式削除が実際にはできるのに、「できない」と判断されてしまうことになります。

そこでより厳しい判定条件として、「関数間解析とエイリアス解析により副作用のありなしをより厳格に判断する」という方針の実装をしました。

• 関数は、その本体とその関数が呼び出す関数の中で両方副作用がないならば、副作用がない。

• 配列への書き込みは、値の同一性が保証されている限りは副作用がない。

ということです。

この工夫によっては、実装時点ではコンパイル結果に影響を与えませんでした。しかしその後第１２週に、shadow_check_one_or_matrixの中のshadow_check_one_or_groupの呼び出しが一部無駄であることに気づきました。shadow_check_one_or_groupは実質的には副作用がないのに、下手に配列の書き込みをやっているせいで「副作用がある」と判定されてしまっていました。単純化すれば

let rec f x = arr.(0) <- x; fib x in ...

みたいな構造です*6。

これをうまく「共通部分式削除できる」と判定することで共通部分式削除ができるようになり、１億命令ほど削減できました。

ただし、結局エイリアス解析は完全に嘘実装で実質的には機能していませんでした。これによりバグを踏んでしまったので、配列書き込みそのものの共通部分式削除は無効化してしまいました。

あとは、あんまり離れた共通部分式を削除してしまうと、レジスタ負荷が高まって逆によくないという話があり、その制御も実装しています。

ラムダリフティング

第３週に、コンパイラ実験第３回課題として実装しました。が、グローバル変数のメモリ番地固定化を導入すると、関数から自由変数が全部消えるため、結局実装の必要はそんなになかったです。

タプル平坦化

第４週～第５週に、コンパイラ実験第４回課題として実装しました。これが相当の曲者でした。

まず、実装方針が非常に面倒です。本当は必要なタプルだけを展開するのが望ましいのですが、よくよく考えるとこのタプルを展開するとこれも展開しなきゃいけなくなり、これも展開して……となってしまい、結局「すべてのタプルを展開する」のが一番楽になってしまいます。

しかし、すべてのタプルを展開すると、今度は異常にレジスタ負荷が大きくなってしまいます。さらに関数引数のタプルを展開した場合、引数がレジスタの個数（32個）に収まらなくなったりしてしまいます。そこで、「要素数n以下のタプルのみを展開する」という方針に移行しました。これもまた面倒で、たとえばn=2のとき(((1, 2, 3), (4, 5, 6)), 7)をどこまで展開するか？とか、いろいろ大量のコーナーケースが生じるので、これらを矛盾することなく処理する必要がありました。

また、タプルの配列の扱いについて、コンパイラ実験では

let arr = create_array 5 (1, 2) in ...

を

for(int i=0; i++; i<5){
  arr[2*i] = 1;
  arr[2*i+1] = 2;
}

に書き換える方針が示されていましたが、これでは配列アクセスのたびにindexに2を掛ける必要があって非効率なことに気づきました。なので、

let arr1 = create_array 5 1 in 
let arr2 = create_array 5 2 in ...

に書き換えるという効率化も行いました。

ここまでやっても、実行命令数自体はタプル平坦化を導入するほうが多くなってしまいました。その原因は、実装時点ではレジスタ負荷の問題だろうか、とか考えていました。これはある意味正解で、実行命令数は後述のグローバルレジスタ割り当てを実装してやっと減りました。関数呼び出し時生きている変数をstoreしなければいけないのが相当悪影響を与えていたようです。

完動からA1ターム終了まで（11月）

このあたりの無限最適化編が一番楽しかったです。まず共通部分式削除とインライン展開のパラメータをいじって50億命令くらいになりました。論理に関する最適化や、(float_of_int x) *. (float_of_int 2^n) をshift_left x nに置き換えたりするようなこまごました最適化を実装したりして40億命令にまで減らしました。さらに即値の利用（addiとかlw 4, 4(x4)とか）により、40億命令→30億命令くらいにまで減りました。この瞬間は本当に気持ちよかったです。

その後なんやかんやで25億命令まで減り、グローバル変数の導入で21億命令まで減りました。

論理に関する最適化

let b = if x = y then 1 else 0 in
let x = if b = 0 then e3 else e4 in ...

は

let x = if x = y  then e4 else e3 in ...

に置き換えたほうがお得です。より一般に、「then 1 else 0」ではなく「then e1 else e2」とかでも

let x = 
    if x = y then 
        if e1 = 0 then e4 else e3
    else
        if e2 = 0 then e4 else e3

とかにしたほうがお得です。then 1 else 0の場合より単純化できるという話も、MinCamlデフォルトの定数畳み込みがよしなにやってくれます。

なお、あんまりやりすぎるとコードサイズ爆発を招く最適化ですが、minrtの場合は動くのでヨシ！

即値の利用

特筆すべきことはそんなにないのですが、

addi tmp, x0, 8   # tmp = 8;  
add  b, a, tmp    # b = a + tmp;

を

addi tmp, x0, 8    
addi  b, a, 8  

に置き換えた結果不要になるtmp, どこに行ったんだろうなーとか思っていたのですが、MinCamlデフォルトのSimm18で消えていました。すごいなと思いました。

グローバル変数の導入

これも先述の先輩のブログが詳しいですが、minrtではプログラムの最初（というかglobals.ml）でグローバル配列を確保しており、レイトレ本体の中ではこれに対してload/storeを行っています。これを「変数に格納されたアドレスへのload/store」とみなすと関数内に自由変数が大量発生し大変なことになります。しかし、変数を確保するタイミングがプログラムの先頭であることを利用すればこれらのグローバル配列のメモリ上の位置は確定するので、グローバル変数をすべて定数に置き換えてやれば、「定数アドレスへのload/store」とみなすことができます。すると、自由変数はなくなるわ、アドレス計算等の定数畳み込みは促進されるわで幸せになれます。

年末まで（11月下旬～12月）

グラフ彩色によるレジスタ割り当て

このあたりでできる最適化が少なくなってきて、グラフ彩色によるレジスタ割り当てを実装しようと試みます。しかし、これが相当の地獄でした。

そもそもMinCamlにデフォルトで入っている貪欲なレジスタ割り当ては、単純な割にそんなに効率が悪いものではないです。一方グラフ彩色レジスタ割り当ての実装として参照するのはタイガーブックのアルゴリズムですが、これはかなり複雑です。まず生存解析の実装に２週間かかってしまいました*7。そのうえで彩色問題を解いたりSpillやCoalescingを考えつつうまいレジスタ割り当てを考えたり、callee save register*8を導入したり…などと考えると、効率の良いレジスタ割り当てにはかなりの時間的コストがかかります。

結局、「最適化だけを考えるならほかの部分に注力したほうがよい」という判断を下してしまい、グラフ彩色をあきらめてしまいました。

命令スケジューリング

グラフ彩色を凍結した後、コンパイラ実験第８週の課題として実装しました。lwの結果が返ってくるまでにaddiなどの別の命令を実行しておこう！というやつです。

単純なコアにおける命令スケジューリングについてはコンパイラ実験のスライドが割と詳しいのですが、うちの班ではコア係がスーパースカラプロセッサを作ってくれたので、資源制約の部分が少し特殊で、スーパースカラプロセッサをシミュレートするようなスケジューラを作成しました。すなわち、「現在発行できる命令」や「今実行しているこの命令は結果が返ってきているか」等を管理しておき、できる限り２命令を同時発行できるようにスケジューリングしています。

このときに同時発行できる命令の条件についてコア係さんに聞いてみたのですが、かなり複雑でびっくりしたのを覚えています。OCamlでもけっこうきついのに、よくVerilogで書けるなあ、と……

スケジューラは（よっぽど変なことをしない限り）命令の優先順位がおかしくても動きはしてしまうため、バグの存在が見えにくいです。実際、実装した時点では40秒のうちの2秒くらいしか変わりませんでした。しかし、コア係に指摘してもらったバグの修正や実装の改善点を取り入れてみたり*9などを2月上旬まで続けていった結果、最終的に20%も実行時間が減っていました。

試験終わりまで（1月）

このあたりで、計算量理論演習や知能システム論の課題がだいぶきつくなってきました。それが終わると試験のための準備が必要になり、CPU実験に回せるリソースが多くなくなってしまいました。

命令スケジューリングの実装も終わり、いよいよやることが見つけにくくなっていた時期でもありました。この時期実装した新しい最適化は連鎖するジャンプの除去くらいでした。それ以外ではもっぱら既存の最適化（論理最適化、共通部分式削除、タプル平坦化）の強化を進めていました。

びっくりしたのが、このあたりでインライン展開を、再帰関数以外はすべて展開するようにしたところ、もともと17億命令だったのが15億命令にまで減りました。２億命令も減ってびっくりしました。

最後の追い込み（～2/15）

ワードアドレッシング

２月に入ったくらいで班全体としてワードアドレッシングへの移行が完了しました。これにより、0.8億命令くらい削減できました。

グローバルレジスタ割り当て

この直後くらいにグローバルレジスタ割り当てが完成し、命令数が13億まで減りました。

関数呼び出しの依存グラフがDAG（つまり相互再帰がない）で、かつminrtの場合クロージャがない（どこに飛ぶかがわかっている）ため、末端の関数から順に「その関数が使うレジスタ」を確定させることができます。すると、レジスタ割り当ての時、関数呼び出し先で使わないレジスタに対して優先的にallocateすることが可能となります。このようなレジスタは関数呼び出し時に破壊されないため退避する必要がなく、結果として関数呼び出しに伴うload/store（スタックアクセス）を60%減らすことに成功しました。残りの40%はおそらくレジスタが足りなかったことによるもので、スタックアクセスは6500万回ほど残ってしまいました。

fabsとfneg

この後しばらくは命令スケジューリングのバグ取りに奔走することになりました。さらに、絶対値を取るとき

    fblt f0, f1, LABEL
    fsub f1, f0, f1
    jal CONT
LABEL:
CONT:
...

みたいな超無駄なことをしていたので、fabs（とついでにfneg）の実装を依頼しました。さらに、直後に飛ぶジャンプ命令の除去を実装しました。これにより12.6億命令まで減らすことができました。このとき2/11でした。

トレーススケジューリング

とうとうやることが見つからなくなり、コンパイラの本を眺めていると、「トレーススケジューリング」なる手法があることがわかりました。ちょうど、スーパースカラなのにIPCが0.7しか出ず、なんじゃこりゃと思っていたので、最後の大仕事としてトレーススケジューリングの実装をすることに決めました。

しかし、この時点で残り３日だったのと、そもそもあまり文献がなくて実装に相当苦労しました。この文献がわかりやすかったので、これを読みつつ実装を進めていました。スケジューリングの宿命として、しょうもないけど非自明なバグに苦しめられました。発表会当日の朝に投機的スケジューラという形でかろうじて部分的に完成したものの、実行時間は0.2s減、IPCは0.75にしかならず、力不足を感じました。

結果

最終結果は、命令数12.6億、実行時間14.5秒でいずれも２位となりました。１位の班はアーキテクチャをかなり工夫していたようです。結果として出てしまうとどうしても悔しいですね。

この半年間相当の労力を注ぎ込んできたので、終わったときはなんともいえない虚脱感でした。部活の引退試合ってこんな感じなのかな、などと思いました。

謝辞

最後になりましたが、プロセッサ・コンパイラ実験担当の先生方、TAの方々、そして何より４班の班員に感謝を申し上げたいと思います。ありがとうございました。

*1:なお今年は担当の先生により「FPU係の単位要件にキャッシュメモリの作成が追加」「シミュレータ係の単位要件に実行時間予測が追加」というコンテンツが追加されました

*2:MLのサブセット

*3:今年は各回「個人課題」に加え「グループ課題の提出」が単位要件でした。グループ課題は先生の意図としては分担してやってほしかったようですが、うちの班ではコンパイラ係が全てやってしまいました……。その分他の係は自分のすべきことに集中するということで…

*4:ざっくりいうとオブジェクトと光源とカメラの位置から３D画像を生成すること

*5:たとえば add f1, f1, f2 みたいなコードが生成されていると、「レジスタの指定が間違っています！」というエラーを出してくれていました。この機能も本当にありがたかった…

*6:まあ配列への書き込みという副作用は実際あるんですが、共通部分式削除に関しては、一度fを呼んだあとは、違う値をarrに書き込むまではfは副作用がないとみなせます

*7:この時期に睡眠習慣が崩壊してしまい進捗を生めなかったのもあるのですが…

*8:MinCamlデフォルトではすべてcaller saveなので、うまいことやれば改善できる余地はあります。ちなみにグローバルレジスタ割り当てを導入するとこの問題が消えます。

*9:命令が逆順にスケジューリングされていたのを修正したり、依存グラフにおいてRAW依存以外のときはレイテンシ（≒優先度）を加算しないようにしたり。本当によくあのスパゲティコードを読んでくれたなということで感謝しかないです