Software Transactional Memo

STM関係のことをメモっていこうと思います。

LLVMやるならgodbolt

この記事は pyspa advent calendar 2023の11日目の記事です。

godboltをご存知だろうか。

godbolt.org

ブラウザから誰でもアクセスできる無料サービスでコンパイラの挙動について学ぶ事ができる。

 

例えば簡単に「渡された数Nに対し1+2+....+Nを返す関数sum」を例にすると

こんな感じにコンパイル結果のアセンブリを表示してくれる。

アセンブリはマウスカーソルを置くとそれが元のコードのどの場所に対応したものなのかを逐一ハイライト表示してくれる。この機能を実現するために必要な労力は並では無いと思うが詳細はわからない。アセンブリ側も複数色あるのは元のコードの1行が同じ背景色のブロックになった事を表している。

これがすごいのはコンパイラの選択肢の豊富さである。gccはもちろんのことclang, zig c++, msvc, nvc++(なにそれ?), ellcc(??), 6502-c++(???)など様々なコンパイラが選べる。しかもコンパイラのバージョンの選択肢も豊富で、ターゲットとしてx86やARMはもちろんのことRISC-V, SPARC, atari, mips, m68kの他聞いたこと無いものまでたくさんのターゲットが選べる。コンパイルオプションも-O2など指定し放題なので最適化オプションごとのアセンブリの違いも一目瞭然のとっても便利なツールである。ここまでの話ならコンパイラ愛好家の皆さんなら当然知っていた情報だと思う。

だがしばらく見ないうちにLLVM関連の機能が超強化されていたので紹介したい。

LLVM-IR出力

LLVM-IRとはLLVMの中間表現(Intermediate Representation)の事でコンパイラ内部でいったん独自言語に置き換えることでCPU固有の問題(レジスタ割付等)を後回しにして最適化を行い、その後で各CPU固有のコード出力を行うまでの間に使う仮想的なアセンブリ言語である。見たところはアセンブリに似ているがレジスタの数に制限が無いので%1などと名付けられているレジスタは必要に応じてどこまでも大きくなりうるし、一度代入されたレジスタは書き換える事ができない。機械語に落とす際にCPUの台所事情に合わせて適宜物理レジスタに割り付け直す事で最適なコードを出力する。この辺は静的単一代入とかで検索すれば多分解説している記事がある。

Control Flow Graph

LLVMの出力は分岐命令で区切られたBB(Basic Block)という単位で管理されている。ラベル名が for.body.preheader とかで目で追いかけるのが辛いこともあるのでこのようにエッジを張ったグラフとして可視化してくれる。これはLLVMに限らず普通のアセンブリのも出せる。以下のはx86のもの。

Control Flow Graph

LLVMのAST表現も出せる。これはLLVM使ってコンパイラ作ってる人には嬉しい

LLVMの最適化は「LLVM-IRで表現されたコード」を入力として「LLVM-IRで表現されたコード」を出力とする最適化パイプラインを通り抜ける事で最適化が実行される。つまり入力と出力の型が一致している。この方法の優れた点は

  • 最適化ロジックを新規追加する際にはパイプラインを長くするだけなので既存の最適化ロジックに一切触らなくて良い
  • 個々の最適化ロジックについて入力前と出力後のコードが明らかなので単体テストしやすい
  • パイプラインを組み替えれば特定のバグがどの最適化ロジックによってもたらされたかを簡単に見つけられる

などが挙げられる。つまりスケーラブルなソフトウェアアーキテクチャをしている。

そして何よりびっくりしたのがその可視化である。

左端が最適化パイプラインに並ぶロジック名、中央がそのステップでの最適化前コード、右が最適化後コード

これはかなりすごい。かなり前に「等差数列の和の公式をコンパイラが使ってループを自動で潰してくれる」という話は一部で話題になったが、この最適化パイプラインを追いかけるとどこでそれが起きたか一目瞭然である。緑色のロジックがコードの最適化に成功したロジックなのでそれを上から順番にクリックしていけばアセンブリ上でループが消えた瞬間がわかる。

ここで紹介した機能は「+Add New」のドロップダウンリストから選択できる。ここで紹介していない機能や僕には理解できなかった機能も山ほどあるのでコンパイラ好きの各位は是非いろいろ探して共有して欲しい。