LLVM Backend と CPU実験

adventar.org

こんにちは。クリスマスいかがお過ごしでしょうか?

f:id:uenoku:20181225144600p:plain
プレゼント交換

この記事は ISer Advent Calendar 2018 - Adventarの25日目の記事として書かれました*1。昨日はsatosさんの

satos.hatenablog.jp

でした。self-hosting面白そうですね(Cセルフホスティング勢に煽られたの面白い)。学期始まりにmincamlコンパイラを実装し始めた頃は「self-hostingもできればなあ」みたいな感じだったのですが片手間でできるようなものではなさそうですね。「フルスクラッチ勢として〜」と後書きにありますが、最近はフルスクラッチの対極にありそうなLLVMをずっとやっているので自作コンパイラをやんなきゃなあという感じです(自作バックエンドの方も頑張りたい😺)。

さて僕は今B3でちょうどCPU実験という実験をやっておりコンパイラ係というコンパイラを書く係をしています。そこで今回の記事ではCPU実験でLLVM Backendを書いてみた(書いている)話を感想をメインにしたいと思います。感想が多いポエムですご了承ください。

LLVMについて

f:id:uenoku:20181217133930p:plain

The LLVM Compiler Infrastructure Project

この記事を読んでくださる層にはあまり説明が必要ないと思いますがLLVMとはclangやlldを筆頭に現代のコンパイラ基盤を支える超巨大なOSSです。以下はLLVMを説明するときによく使われる図です。①でLLVM-IRを出力しMiddle-endでLLVMに最適化をしてもらいそこから②で各アーキテクチャ向けにアセンブリやバイナリを出力します。したがって自作言語のコンパイラを実装したいとなったときは①を書くだけで一定以上のパフォーマンスを備えた言語を書くことができます。近年開発された言語でLLVMをBackendとする言語はたくさんありここ2,3年で大きく普及し始めているRust、Appleには欠かせないSwift*2LLVMJITによって高速化を図っているJuliaなどが代表例でしょう。また深層学習のためのコンパイラであるGlowなども最近話題になりましたね。

f:id:uenoku:20181217135931p:plain
よくある図

LLVM Backendを書いた話

さて②に相当するのがLLVM Backendです。

LLVM Backendは何をやってるいるのか?

以下の図のようにLLVM BackendはLLVM-IR -> Selection DAG(命令がDAGになってるやつ) -> MI(かなり低レイヤーな中間表現) -> MC(アセンブリとか)へと変換してくれるものです。 やろうと思えばBackendは本当にいろいろやってくれて(実装すれば) ELF生成とかJITとかまでやってくれます。これらの機能を得るためにどういう命令があるのか、どういった関数呼び出し規約か、保存されるレジスタはどれか、.....といったことを記述する必要があります。

f:id:uenoku:20181225002803p:plain
http://llvm.org/devmtg/2017-10/slides/Braun-Welcome%20to%20the%20Back%20End.pdfからの引用

本題

手元にLLVMが入ってるひとは

$ llc -version

とかで対応するTarget(及びSubtarget)が表示されると思います。ここに僕の班のISAであるCookieMonster(renameするのがめんどくさくて1stのELMOの名をまだ使っていますが)を入れてLLVM-IRをCookieMonsterのアセンブリに変換することが今回やったことです。全然リファクタリングできていないためかなり乱雑な感じになっていて申し訳ないですが以下が実装です。

github.com

雰囲気を掴むため、いくつかコンパイル結果を貼っておきます(ISAについての説明は省きます)(めっちゃアルファ変換されてるけど許して)。

ループに展開されていることが分かる 

これはほとんど住井先生のmincamlと変わらない

もうここまで来るとよくわからんが実行したら早かった

分かりやすくするためにインライン展開はしていない。たぶん20億命令くらい。グローバル変数の静的な領域確保,インライン展開で13億くらいまでは行く。

とまあこんな感じでいい感じにアセンブリに変換してくれます。作り方は基本的に https://llvm.org/docs/WritingAnLLVMBackend.html にある手順に従えば問題ないのですがこれは抽象的な部分が多く、雰囲気をつかむことはできますが、これだけ見て実装出来るというわけではないと思います。なので以下の資料やターゲットが参考になると思います。

参考になる資料

  • きつねさん

motipizza.com

そこそこ昔のLLVMのサンプルなので多少勝手が違いますが日本語で書かれた数少ないBackendについて解説してる本です。分岐命令以外はCPU実験に必要な要素は解説されているので雰囲気を掴むためにも絶対買ったほうがよいです。

これなかったら本当にしんどかった(著者の方ありがとうございます:pray:)

  • CPU0

Table of Contents — Tutorial: Creating an LLVM Backend for the Cpu0 Architecture

step-by-stepに実装が書かれたチュートリアルです。章ごとに別れているのでファイルと役割の関係がつかみやすいです。ただ分量が多くバイナリの生成などの必要ない部分も含まれるので Backend structure, Arithmetic and logic instructions, Control flow statements, Function callを実装するタイミングで見るのが良いと思います。

参考になるターゲット

  • RISCV

最近追加されたアーキテクチャなので他とは違い比較的新しいC++の機能が使われています。またSubtargetが2つだけと少なくコメントも丁寧なので実装に困ったらまずこれを見るのが良いと思います。以下は2018 LLVM Developers’ MeetingでのlowRISCプロジェクトのFounderであるAlex Bradbury 氏のトークですが全体像をコンパクトに纏めてくれているので、実装しようと思ったときはまず最初に見ると良いと思います。

www.youtube.com

  • Lanai

Lanaiは数年前にGoogleが内部のプロジェクトとして開発したプロセッサらしく研究用なのでFPUがないなどかなりミニマムな構成になっておりコードが読みやすいです。*3

実装して思ったこと

  • 最適化は強い

Backendが動くとほとんど何もせずに強めの最適化が動かすことができます(すごい)。 ただminrtに関してはminrtにある程度特化する必要があるため先輩方の命令数(9億くらい?)に到達するにはただLLVMを動かすのみでは難しいと感じました(結構過激なことをする必要がありそうなので)*4

  • 自作CPUでCやRustのコードを走らせることが理論上可能だけど..

ライブラリ等をCで書いてそれをClangでLLVM-IRに変換してそれをリンクして最適化するみたいなことが可能です。例えばRustのmanderblotのコードを動かすことができます*5コンパイル時に32bitアーキテクチャ向けにコンパイルすることが必要です)。

mandelbrot.rs · GitHub

mandelbrot.ll · GitHub

mandelbrot.s · GitHub

コンパイルのOpt-levelを1とかにするとするとデバッグ情報が入ってしまいその辺をLowerすることができないので僕のBackendはエラーを吐きます。Rustはメモリ管理周りのあれこれが渋いため現在はminrtは移植できていないです。 もし余興とかでOS等を書きたいのならmincamlくらいのものでもしんどかったのでclang,rustc等が吐くLLVM-IRに完全に対応するのは結構大変だと思います。 ちなみに現在は自分のコンパイラが吐くLLVM-IRは他のアーキテクチャで動かすことができない仕様になっています(LLVM-IRを吐く前にポインタの足し算とかをしているためWord単位のアドレッシングとなっているからバグる)。

  • calling graph,cfg等の可視化がしやすい

これはbackendのメリットというよりはLLVM-IRに変換することのメリットかも知れません。まあ使う回数はかなり少ないですが...。参考

yutopp.hateblo.jp

f:id:uenoku:20181224180703p:plain
minrtのcalling graphの一部。しょうもない関数を省くとかしないとカオスになってしまい使い物にならない

  • TableGen .. なんだこれは....たまげたなあ

TableGenとはC++を生成するLLVMお手製のDSLです。DAGのパターンマッチの記述とかレジスタの定義とか命令の定義とかでこれをかなり使います。

def: Pat<(or ELMOGRRegs:$l, ELMOGRRegs:$r),
        (XOR (XOR (AND ELMOGRRegs:$l, ELMOGRRegs:$r), $l),$r)>;

めっちゃ適当な例ですが上は簡単に言えば(l or r) がDAG上にあったら ( l & r) ^ l ^ rに変換してくれ〜という記述です*6

これだけ見ると良さそうな感じですが、これマジで意味が分かんなくてしんどいんですよね(エラーメッセージがわかりづらい、てかパターンマッチやりたいなら全部ML likeな構文にしてくれという気持ちがある)。ちゃんと解説したリファレンスが欲しい。

  • 実装するのが大変

これは俗に言うインクリメンタルな開発がしづらいという点にあると思います。自作コンパイラと違って全てのパスを(ある程度)適切に実装して初めてアセンブリが出力することができるので各クラスの依存関係を把握する必要があります。0からやりたくてやったけど,全体の設計の理解に加えてC++とTableGenとかの非本質的な部分でかなり辛くなってしまった。CPU0(の3章まで)とかをコピペしてスタートする選択肢を選んだほうが精神的にも効率も良いと思う。LLVMのコード自体はコメントがかなり丁寧で,ゴリゴリtemplateがたくさん!!みたいな感じでは無いので読みやすいと思います。

これはまた違う話だけど公式にメンテナンスされるミニマムなサンプルのターゲットが存在してほしいなあと思いました。

コンパイラを書くというよりはLLVMC++の勉強をしているという感覚が強いです。正直あまり楽しくない(悲しい)。自分で最適化のパスを実装すれば楽しいかもしれないが先に自作の方の完成度を高めたいという気持ちがある。

こっから下は具体的な話になってしまいhogeかもしれないです。

各実装の知見

RegisterInfo

RegisterInfo.tdは特に詰まるところはなくただCaller-saved,Callee-savedを記述するだけです。

InstrInfo

InstrInfo.tdにISAが持つ命令をつらつら書いていきます。

多くのチュートリアルではInstrFormatを定義して...これを継承して...みたいな流れが多いんですが結局何をしているのかがわかりづらいです。個人的には最初はFormatとかどうでも良いから直接Instructionを継承して書いてみるのが丸いとは思いました。この辺りの話は上に貼ったRISCVの動画のInstrInfo周りの話(7:00 - )で詳しいので聞いておくと良いと思う。

ISelLowering

かなり本質的な部分でLLVM-IRからSelectionDAGに変換する役割を持ちます。レイトレを動かすのに特に必要なのは関数呼び出し周り(これはきつねさんにだいたい書いてあります)と分岐命令のLower等です。

  • 分岐命令のLower

比較命令と分岐命令が別れているならSparcが参考になります。そうでないならRISCVのやり方を参考にすれば良いと思う。

  • 末尾呼び出し最適化

この実装はこれは実装されていないアーキテクチャもLanaiやSparcなどちらほらあります。実装例としてはRISCVの実装がわかりやすいです。

  • Floatの即値

2ndアーキテクチャでは64bit長命令を採用しているためConstantPool(mincamlでいう浮動小数点テーブル)作らない方針でやったのですがどうやっても作られてしまいかなりハマってしまいました。ConstantFPをLegalにして上げれば作られないので命令を追加するだけで良いです。ConstantPoolを作るひとはConstantPoolを普通にLowerすれば良い。

Frontend

github.com

Frontendはそんなに煩雑ではないです。 Backendがメインなのであまり詳しくは説明しませんが, 現在フロントエンドは普通にOCamlで書かれており*7,型検査やクロージャ変換は普通に行いVirtual.tからLLVM-IRを出力しています(src/llvmCodegen.ml)。IRの生成については 素直にLLVMが提供しているbindingを使うのが一番楽だと思います。Kaleidoscopeの7章の実装や https://llvm.moe/ocaml-7.0/Llvm.html を見るとだいたい雰囲気がわかると思います。mincamlのVirtual.tくらいまで行くとほとんどギャップはないです。面倒なのはIf式をphi式に変換するところでこれはKaleidoscopeの実装を参考にすればよいです(非本質的な話ですがUnitの扱いがめんどかったです)。最初はフロントは適当にやっても命令数減るやろと思っていたのですがclang -emit-llvm -O3 と-O2の違いを見る限りループアンローリングなどはフロントエンドでやっている印象があった(ほんまか?)のでこっちを頑張る必要が出てきました。LLVM-IRを吐くことを考えてSSAでゴニョゴニョやるやつを実装していきたいなと思います(正月に)。

CPU実験特有の話

  • 諸々がワード単位

バイト単位ではなくてワード単位でいろいろやることが多いと思います。RegisterInfo::eliminateFrameIndex,FrameLowering::emitPrologue辺りをいじってStackSizeを無理やり1/4にしています(正攻法かどうかは分からない)。

  • sqrt,ftoi,itofとかを組み込みの命令にしたい
declare float  @llvm.sqrt.f32(float %Val)

LLVM-IR上では上のような関数を呼んであげてfsqrtなどの命令をInstrInfo.tdに追加してISelLoweringでLegalにすると内部で勝手にやってくれます。

  • out命令とかをinline asmしたい

print_charのような関数を呼ぶのではなく

 out %r3

としたくなってくる。これをするにはISelLowering::getRegForInlineAsmConstraintを実装してあげれば

define void @print_char(i32 %x)  {
   call void asm sideeffect "out $0" "r"(i32 %x) 
  ;これの"r"が整数レジスタを示すことをgetRegForInlineAsmConstraintで定義している
   ret void
}

のようにprint_charを定義できる。これをインライン展開するとうまくいく。

雑多なトピック

開発のTips

  • ninja,lldを使う

makeしか知らなかったので最初使ったときびっくりしました。現在使ってるのはopt,llcくらいなのでフルビルドする必要はないです。ninja,lldのおかげでビルド時間でストレス溜まることは少なかったです。

  • -view-*-dags

llcにつけるとLowerされる途中過程をdotで見れる。linuxだとxdotが使いやすいと思う。

WithColor::note() << "hoge"; とか dbgs() << "fuga";とかでできる。

試したツール

  • Souper

github.com

Souper: A Synthesizing Superoptimizer – Google AI

SMTソルバを用いて論理的に等価な最適化をしてくれる。手元だとコンパイルを通すのが難しいので公式に配布されているDocker上でコンパイルするのが良いと思う。命令数はほとんど減らなかった(20万くらい)(冗長なコードに対しては強いだろうけどminrtは元から無駄がほとんどないから、まあそれはそうという感じ)。

感想

10月下旬に一応レイトレが実機で動いたので自作コンパイラでの最適化と並列にLLVM Backendを書いてみようというと思いBackendについて調べ始めました。当初2,3週間でできると思っていたのですが結局レイトレのコードをコンパイル出来るようになったのは12中旬になってしまいました(これのせいで自作コンパイラの方のバックエンドは簡易的な実装のままなのでなんとかしたい)。minrtを動かしてみると20億命令でインライン展開のパラメータをいじると13億命令とかになりました。正直10億付近にならないかなあと期待してたのでちょっと凹みました(比較命令と分岐命令を1命令にできると11億まで行けるからしてほしい😺)(まあ逆に考えると多少強めな最適化とレジスタ割当をするとこの辺りまで行けるということなんですかね)。外部のツールに頼りきって命令数減らすのアレな気がするのでLLVMに投げる前段階でもう少し頑張ってみたいなという感じです*8。残り2ヶ月頑張っていきたい。発表3月下旬にならないかなあ。

*1:誰も遅刻してないのウケるな

*2:swiftに関してはSILとかをフロントエンドの参考にするべきなんだよなあ

*3:Lanaiについて全く音沙汰ないんですけどどういった目的で作られたんでしょうね...

*4:CallingGraphのDAGの下からレジスタ割り当てするやつやってみたいんだよなあ

*5:これは半分嘘で生成されるLLVM-IRに含まれるrust_begin_unwindという無限ループする関数があるとBackendがEmitPrologueで死ぬ(なんで)

*6:これは実際にInstrInfo.tdにあってorは数十回しか呼ばれないので乗っているXOR,ANDに変えているやつです

*7:C++を書いた後にOCamlやると幸せになった

*8:ループ周りの処理をすればもうちょっと上がると思ってる