molecular coordinates

/var/log/coord_e.log

cccコンパイラのバックエンド

この記事は言語実装 Advent Calendar 2019の23日目です。

おはようございます!!!coord_eです、よろしくどうぞ。

はじめに

実は、この記事の大半の文章は以前に別の目的で執筆したものです。 そういえばcccについて記事を書いていないな、ということで、少し内容を変更しつつ体裁を整えて公開することにしました。 なお、ブログやスライドなどで散々「セルフホストする」「gcc -O1に勝つ」と豪語しておりましたが、そのどちらも達成できていません。残念。

この記事にはPDF版があります。以下のリンクからダウンロードできます。

元が \LaTeXなので多分PDFの方が読みやすいです。基本的にはPDFとはてなブログの内容は同一ですが、長いアルゴリズムなどは省略してPDFにのみ載せていることがあります*1。また、内容が同じ二つの文書を同時にup-to-dateに保つのは大変そうなので、何か変更する必要が生じたときは僕のやる気によってはPDF版のみ更新してはてなブログの内容が古くなる可能性があります。

この記事の \LaTeXソースはGitHubに公開しています。 また、誤字や誤謬を発見された方は@coord_eまでご連絡いただくかリポジトリにIssueやPull Requestを送ってくださると幸いです。

概要

cccは、自分がセキュリティ・キャンプ2019に参加した際に開発したコンパイラだ。 C11のサブセットをコンパイルする事ができ、暗黙の型変換や初期化子、宣言子に代表される複雑な言語機能を規格に忠実に実装している。 さて、cccは効率の良いコードに効率よくコンパイルすることをテーマに開発を行った。 そのテーマのもと、出力コードの効率を高めるためにcccに実装した技術についてこの記事では説明する。 最後にベンチマークの結果を示し、実装の効果を確かめる。

cccコンパイラの構成

cccコンパイラはCのソースコードを受け取りアセンブリのコードを出力する。cccではワンパスでは行えないと思われる変形や最適化を用いているため、コンパイルの段階に応じて複数の中間表現を用いている。

一つ目の中間表現が抽象構文木(Abstract Syntax Tree, AST)だ。これは構文解析の結果を木構造で表現したもので、この上で意味解析が行われる。 もう一つの中間表現はIRと名付けた*2。これはASTよりもアセンブリに近い構造を持っており、この上で最適化やレジスタ割り当てが行われる。IRについては次節で詳しく説明している。

f:id:coorde:20191211223754p:plain
図1: cccコンパイラ全体の構成

図1はコンパイラ全体の構成を表している。cccコンパイラの内部パスはソースコードからASTを扱うフロントエンド(front end)と、IRを扱うバックエンド(back end)に概念上分類することができる。 フロントエンドではソースコードに対して字句解析と構文解析を行ってASTを生成し、ASTの上で意味解析を行ったのちIRを生成する。バックエンドは生成されたIRの上でコード変形や最適化を行い、最終的に一般的なアセンブラで処理可能な形式のx86_64アセンブリを生成する。

なお、バックエンドは今日ではLLVMに代表されるようなコンパイラ基盤で置き換える事ができる。 しかしcccでは低レイヤ・オタク特有のいわゆる“一から作りたい欲求”に身を任せ、バックエンドを既存のフレームワークを使用せずに自作している。 この記事では主にcccコンパイラのバックエンドに焦点を絞って説明する。

この記事では構文解析に代表されるようなフロントエンドについては説明しない。理論的な側面については[1]が詳しい。また、フロントエンドに限らないが、実装から入る場合は[2]が非常に良いオンラインブックであるとして有名だ。

IR

IRは出力先のネイティブコードに近い構造を持つように設計した。IR内では関数が単位となっており*3、これを関数IRと呼ぶことにする。IRに対する操作も基本的に関数IR単位で行われる。 関数IRはメタデータを除けばIR命令(IR instruction)の列である。IR命令は命令の種類であるオペコード(opcode)*4と命令の引数であるオペランド(operand)で構成されている。また、cccのIR命令列は基本ブロック(basic block)に分割されており、各基本ブロックは後続節(predecessors)と先行節(successors)の情報を保持している。 これらの情報から基本ブロックは制御フローグラフ(Control Flow Graph, CFG)を構成する(図2)。

IR命令はレジスタオペランドにとる。cccのIR上のレジスタには以下の3つの種類がある。

IRを表す図中では、n番目の仮想レジスタvn、n番目の物理レジスタrnrnに割り当てられるm番目の固定レジスタf(vm:rn)と表記する。

さて、IR命令の命令セットを表1に示す。 なお、今後の表やアルゴリズムでは命令の出力オペランド rd、n番目の入力オペランド ra[n]と表記する。*5

表には記載がないが、これらの他にBIN_IMMといった片方のオペランドに定数をとる命令やBR_CMPといった複合命令が実装されている。これらは主にレジスタ上のデータの流れを用いた最適化であるデータフロー最適化で効率的なアセンブリを出力するために用いている。

IRはASTから生成され、IRの上で最適化やレジスタ割り当てが行われたのちにコード生成パスでx86_64のアセンブリに変換される。

f:id:coorde:20191211223835p:plain
図2: cccが出力するIR (CFG) の例

f:id:coorde:20191211223855p:plain
表1: cccのIR命令セット (一部)

ターゲット固有IRへの変換

アーキテクチャやABI(ここでは二つをまとめてターゲットと呼ぶ)によっては、命令がある決まったレジスタを使用することがある。 例えばx86_64アーキテクチャにおいて除算命令divは被除数をraxにとり、商をraxに格納する。 またSystem V ABIにおいてcall命令はrdi, rsi, rdx, rcx, r8, r9に引数をとり戻り値をraxを格納する。 こういった特別に扱われるレジスタをここでは特殊レジスタと呼ぶことにする。 また、x86_64ではadd, subなどのいくつかの命令において演算の左辺と演算結果が同じレジスタでなければならないという制約がある。

一方で、cccのIRでは表1からわかる通りオペランドレジスタに特に制限を設けていない。 そのため、単純な実装ではコード生成時に適切にmov命令を挿入して決まったレジスタを使うようにすることになる。 しかし、この方法では特殊レジスタを汎用的に使うことができず、レジスタ割り当てに使えるレジスタの数が制限されてしまう。 また、一つのIR命令に対応するアセンブリ命令が多くなってしまうと最適化の効果が制限されてしまうことも予想された。

そこで、cccではレジスタ割り当て前にIR上でターゲット特有の変換を行うことでこれらの問題を解決している。 図1では「Target Conversion」と表記している。 これはIR上で固定レジスタへのMOV命令を生成することでコード生成時に正しいレジスタが使用されていることを保証しながらIR上で特殊レジスタの使用を表現するものだ。 こうすることでレジスタ割り当ての時点で特殊レジスタの使用が把握できるため、特殊レジスタが使われていない部分では通常のレジスタとして割り当てに使用できるようになる。 図3にこの変換の例を示す。関数呼び出しや除算が固定レジスタを使うように変換されているのが見て取れる。

f:id:coorde:20191211223918p:plain
図3: ターゲット固有IRへの変換前後のIRの変化例

最適化

効率の良いコードを出力するため、最適化を行う。 cccではデッドコード削除やコピー伝播に代表されるデータフロー最適化やAST上の定数畳み込みなどを実装しているが、ここではそれらについては説明しない。 特にデータフロー最適化について、技術書展8にOtakuAssemblyで記事を出す予定なので、ぜひそちらを楽しみにしていてください。

さて、ここではLOAD/STORE以外の操作を受けていないスタック上の領域をレジスタで置き換える最適化について説明する。 この最適化パスをmem2regと名付けた*6。 mem2regで使用および実装したアルゴリズムアルゴリズム1に示す。

f:id:coorde:20191211223942p:plain
アルゴリズム1

ここではアドレスとして用いられているレジスタアドレスレジスタ(address register)と呼ぶ。 LOAD/STORE命令のアドレスの位置にあるオペランドとして使われているレジスタがアドレスレジスタである。

CollectUses(アルゴリズム2)でアドレスレジスタのうち、置き換え可能なものを求める。 ここではアドレスレジスタcandidatesに集めながら、LOAD/STORE以外の操作を受けているレジスタexcludedに集めている。 また、STACK_ADDR命令で代入されているレジスタを個別にin_stackに集めている。

さて、置き換え可能なアドレスレジスタは、以下の3条件を満たしているものである。

  1. スタックのアドレスを保持している
  2. LOAD/STORE以外の操作を受けていない
  3. 置き換え不可能なアドレスレジスタと同じスタック位置を共有していない

1., 2.を満たすアドレスレジスタの集合は、 (\texttt{candidates} - \texttt{excluded}) \cap {\texttt{in_stack}}で求められる*7。 そして3.を満たさないものを除外するために、置き換え不可能なアドレスレジスタのスタック位置の集合を求め、そのあとにそれを共有しているものを除外するというナイーブな方法をとった。

そして、置き換え可能なアドレスレジスタが求められたのち、ReplaceInstructions(アルゴリズム3、PDF版に掲載)で命令をレジスタを使うように書き換えている。

f:id:coorde:20191211225905p:plain
アルゴリズム2

図4にこの最適化による変形の例を示す。一部のスタックに対する操作がレジスタに置き換わっていることが見て取れる。 この最適化による出力コードの効率の変化についてはこの記事の後半で検討する。

f:id:coorde:20191211224017p:plain
図4: mem2reg最適化前後のIRの変化例

レジスタ割り当て

cccでは出力の実行効率を意識し、入力をレジスタマシンにコンパイルする。 そのために、レジスタ割り当て(register allocation)を行う。一般的なプロセッサにおいてレジスタは有限だ。例えばx86_64においては16本、そのうち汎用的に使えるのは14本しかない。 すなわち、全ての値をレジスタに保存しておくことはできない。値を保存するレジスタが足りなくなった時に、レジスタの代わりにスタックの領域を使う。これをspillと呼ぶ。 spillされたレジスタは使用時にスタックから読み込まれ、値の変更時にスタックに書き戻される。 レジスタへのアクセスはメモリへのアクセスと比べて非常に高速であるため、頻繁にアクセスされる値をレジスタに、そうでない値をメモリに配置することが出力コードの効率向上に繋がる。

一方で最適なレジスタの割り当てを求める問題はNP完全であることが知られている。そこで、コンパイル時間と実行時の効率のバランスが取れたアルゴリズムが考案されてきた。 そのよく知られた例の一つが、レジスタ割り当てをグラフ彩色問題とみなす方法[3]である。しかしこの方法はコンパイル時間が長くかかるほか、実装が複雑になることが予想されたため今回は採用しなかった。

cccでは、linear scan register allocationを使用した。これはPolettoらによって[4]で使われたレジスタ割り当てアルゴリズムだ。 これはグラフ彩色による手法に比べて割り当てにかかる計算量が少なくて済む上に、ほとんどの場合で同程度に効率の良いコードを出力できる。

cccの実装では、まずIR上でbackward data-flow analysis[1]を行い、仮想レジスタの生存区間を求めたのち、レジスタ割り当てを行う。 生存区間解析の実装はほぼ[5]で使われているアルゴリズムの通りである。 レジスタ割り当てのアルゴリズム[6]を元にしたが、固定レジスタを扱うために一部変更を加えている。 実際に使用したアルゴリズムアルゴリズム4に示す。

f:id:coorde:20191211224045p:plain
アルゴリズム4

このアルゴリズムでは、割り当てに際して三つのグローバルな変数を持っている。

  • availableは現在利用可能な物理レジスタのリスト*8で、後に述べる優先度でソートされている。
  • activeは現在使われている仮想レジスタのリストで、生存区間の終了が遅い順にソートされている。
  • resultは仮想レジスタから割り当てられた物理レジスタへの写像*9

これらの変数に対する操作は、AllocSpecificReg(アルゴリズム8、PDF版に掲載)とReleaseReg(アルゴリズム9、PDF版に掲載)の二つの操作に抽象化されている。 アルゴリズム本体ではこれら二つの操作とspillを適切な条件で行うことで、割り当てを行なっている。 また、availableは次の条件もとソートされている。(アルゴリズム5) なお、関数呼び出しで保存されないレジスタ*10のことをscratch registerと呼ぶ。

  1. 現在の関数内の固定レジスタで使用されている物理レジスタより、そうでない物理レジスタを優先する。
  2. 現在の関数が関数呼び出しを含むならば、scratch registerでない物理レジスタを優先する。そうでないならばscratch registerを優先する。

AllocSpecificReg(アルゴリズム8、PDF版に掲載)からわかる通り、割り当てる物理レジスタavailableの先頭から選ばれる。これにより、アルゴリズム5で優先されているものから順に割り当てられる物理レジスタが選出されることになる。

f:id:coorde:20191211224105p:plain
アルゴリズム5

さて、linear scan register allocationは、生存区間に対する一回の走査によって行われる。 アルゴリズム6に走査部分のアルゴリズムを示す。また、spill関連のアルゴリズムをPDF版のアルゴリズム7に示してある。 固定レジスタの割り当てでは、必要な物理レジスタがすでに割り当てられていた場合にそれをspillすることで物理レジスタを確保する。また、spillの対象のレジスタを選ぶ際に固定レジスタを避けるようにしている。それ以外はほぼ[6]の通りである。

f:id:coorde:20191211225939p:plain
アルゴリズム6

図5にレジスタ割り当ての例を示す。全て仮想レジスタが物理レジスタに割り当てられているだけでなく、変換前に固定レジスタだったレジスタは、正しく指定されたレジスタに割り当てられていることが見て取れる。

f:id:coorde:20191211224127p:plain
図5: レジスタ割り当て前後のIRの変化例

評価

ターゲット固有IRへの変換や最適化の効果を確かめるために、ベンチマークを行った。 ベンチマーク環境は以下の通り。

  • CPU: AMD Ryzen 7 2700
  • RAM: 32GB
  • kernel: 5.2.8-arch1-1-ARCH
  • OS: Arch Linux
  • gcc: 9.1.0

今回は三種類のプログラムをベンチマークに用いた。それぞれ次の通り。

  • 14queen - N-queen問題のn=14の場合の全ての解を求める
  • sort - 30000000個のランダムな要素からなる配列のマージソート
  • pi - 円周率を200000桁求める

以下の5種のコンパイラにこれらのプログラムをコンパイルさせ、コンパイル時間と実行時間、および出力コードの行数を計測した。 計測はそれぞれ8回行い*11、平均値を算出した。

  1. 固定レジスタを導入する前のccc (naive)
  2. 固定レジスタを導入し14本のレジスタを活用できるようになったccc (better_alloc)
  3. 2.にmem2reg最適化を導入したccc (mem2reg)
  4. gcc -O0
  5. gcc -O1

コンパイル時間

コンパイル時間のベンチマーク結果を表2と図6に示す。

f:id:coorde:20191211224203p:plain
表2: ベンチマーク結果: コンパイル時間

f:id:coorde:20191211224220p:plain
図6: コンパイラごとのコンパイル時間の比較

実行時間

実行時間のベンチマーク結果を表3と図7に示す。なお、naiveのsortについてはその時点でのcccの実装にバグがあり実行時エラーが生じているため正常な計測ができていない。

f:id:coorde:20191211224243p:plain
表3: ベンチマーク結果: 実行時間

f:id:coorde:20191211224259p:plain
図7: コンパイラごとの実行時間の比較

出力コード行数

出力コード行数のベンチマーク結果を表4に示す。

f:id:coorde:20191211224435p:plain
表4: ベンチマーク結果: 出力コード行数

考察と展望

当然ながらcccはどのベンチマークにおいてもgccよりも速くコンパイルできている。 cccの方が高速なコードを出力しているケースにおいても、最適化を行っていないgcc -O0と比べて最適化を行ったcccの方が高速にコンパイルできている。 効率よくコンパイルするという目標はよく達成できていると思う。*12

その一方で実行時間については、ほとんどのベンチマークgcc -O0より遅いという結果になった。しかしmem2regがpiでgcc -O0より高速なコードを出力できている。 これは14queenとsortが配列に対する操作が基本となるベンチマークであるのに対し、piはスカラ変数に対する操作が中心であることに起因すると考えている。 配列操作はどうしてもメモリアクセスが必要となってしまうが、スカラ変数に対する操作はmem2regでレジスタ操作に置き換えることができる。そのためpiではmem2reg最適化の効果が強く出たのではないかと考えられる。

また、表4を見ると実行時間が遅い項目は出力コード行数も多くなっていることがわかる。 したがって、cccをより高性能なコンパイラにするために、今後は出力命令数を減らすためにIR命令セットの再検討を行いたい。 また、まだ実装していないloop unwindingや末尾再帰などの最適化パスも実装し、最終的にgcc -O1に主要なベンチマークで勝利できるコンパイラを目指す。

結論

本記事ではcccコンパイラの実装について紹介した。 効率の良いコードに効率よくコンパイルするという目標を念頭に、cccのバックエンドにおける最適化やレジスタ割り当てのアルゴリズム、および実装上の工夫について説明した。 最後にベンチマークを示し、本記事で説明したアルゴリズムの実装によってcccの出力コードの効率が向上することを確かめた。

参考文献

  • [1] AV エイホ. コンパイラ: 原理・技法・ツール. サイエンス社, 2009.
  • [2] Rui Ueyama. 低レイヤを知りたい人のための c コンパイラ作成入門. https://www.sigbus.info/compilerbook. (Accessed on 12/11/2019).
  • [3] Gregory J Chaitin, Marc A Auslander, Ashok K Chandra, John Cocke, Martin E Hopkins, and Peter W Markstein. Register allocation via coloring. Computer languages, Vol. 6, No. 1, pp. 47–57, 1981.
  • [4] Massimiliano Poletto, Dawson R Engler, and M Frans Kaashoek. tcc: A system for fast, flexible, and high-level dynamic code generation. In ACM SIGPLAN Notices, Vol. 32, pp. 109–121. ACM, 1997.
  • [5] Christian Wimmer. Linear scan register allocation for the java hotspottm client compiler. Master’s thesis, Johannes Kepler University Linz, 2004.
  • [6] Massimiliano Poletto and Vivek Sarkar. Linear scan register allocation. ACM Transactions on Programming Languages and Systems (TOPLAS), Vol. 21, No. 5, pp. 895–913, 1999.

*1:それについてはその都度記載しています

*2:もちろんIntermediate Representationなのだが、中間表現全体を指すわけではなく特定の段階の中間表現を指してIRと呼んでいる。「名付けた」と言っているのもそのためである。

*3:翻訳単位に対応するIRは、翻訳単位内で定義された複数の関数IRが集まったものである

*4:ここでは“命令の種類”の意味で使っており、cccのIRで書く命令に対応する自然数があるというわけではない

*5:入力オペランドの表記としてrsが一般的だと気づいたのはある程度cccを実装し終えた後でした...

*6:LLVMに同じような名前の最適化パスがあり、実際それから名前は着想を得たが、最適化の内容については関連はないものとする

*7:集合の実装にBit Vectorと呼ばれるデータ構造を使用しており、集合の演算が非常に効率的に行える

*8:availableとactiveには先頭と末尾へのポインタを保持した双方向リンクリストを用い、要素の挿入/取得が定数時間で行えるようにしている

*9:物理レジスタと仮想レジスタには自然数のインデックスがついているので、レジスタからの写像は配列で実装されている

*10:System V ABIではrax, rdi, r9など

*11:なんで8回にしたかまるで記憶がない

*12:自己満足の話であり、gccより効率が良いと言いたいわけではない。