作って学ぶコンパイラの最適化

作って学ぶ コンパイラの最適化 しーぴー (@__cp20__) M3 Tech Talk No.280 @2025-08-22

自己紹介 しーぴー / 永田 直希 (Nagata Naoki) 所属 東京科学大学 (traP代表) 好きなもの プログラミング、ゲーム、散歩 好きなプログラミングの分野 Web全般、言語処理系 最近やってるゲーム ぷよぷよテトリス２・PEAK

• https://store.steampowered.com/app/1259790/_2/?l=japanese
• https://store.steampowered.com/app/3527290/PEAK/?l=japanese

おことわり 「作って学ぶ」というタイトルですが ハンズオンはありません🙇

一般的なコンパイラの構成 (前提知識) - Lexer (字句解析器) ソースコード → トークン列 - Parser (構文解析器) トークン列 → AST (抽象構文木) - Semantic Analyzer (意味解析器) AST のチェック - Code Generator (コード生成器) AST → コンパイルターゲット

最適化の余地 - Lexer (字句解析器) 不要なトークン (e.g. コメント) を削るなど - Parser (構文解析器) 定数を畳み込むなど - Semantic Analyzer (意味解析器) 到達不可能コードを削るなど - Code Generator (コード生成器) レジスタ割り付けを工夫するなど

最適化の余地 - Lexer (字句解析器) 不要なトークン (e.g. コメント) を削るなど - Parser (構文解析器) 定数を畳み込むなど - Semantic Analyzer (意味解析器) 到達不可能コードを削るなど - Code Generator (コード生成器) レジスタ割り付けを工夫するなど

レジスタ割り付けを理解するための前提知識 - メモリ (主記憶) の読み書きに対してレジスタの読み書きは非常に高速 - キャッシュにもよるが、3〜300倍程度高速 - なるべくメモリへのアクセスを減らすことが高速化に繋がる - CPU (アセンブリ) で使えるレジスタの数は限られている - 例えば x86_64 の汎用レジスタは16個

レジスタ割り付けの例 square(int): int square(int num) { return num * num; pushq %rbp movq %rsp, %rbp movl %edi, -4(%rbp) movl -4(%rbp), %eax imull -4(%rbp), %eax popq %rbp O0 retq } square(int): movl %edi, %eax imull %edi, %eax retq O3

レジスタ割り付けの例 square(int): int square(int num) { return num * num; pushq %rbp movq %rsp, %rbp movl %edi, -4(%rbp) movl -4(%rbp), %eax imull -4(%rbp), %eax popq %rbp O0 retq } square(int): movl %edi, %eax imull %edi, %eax retq O3

レジスタ割り付けの例 メモリアクセスが発生！ square(int): int square(int num) { return num * num; pushq %rbp movq %rsp, %rbp movl %edi, -4(%rbp) movl -4(%rbp), %eax imull -4(%rbp), %eax popq %rbp O0 retq } square(int): movl %edi, %eax imull %edi, %eax retq O3

最適なレジスタ割り付け #とは 1. メモリへのアクセスが少ない - レジスタだけで完結するのが最適 2. mov が少ない - データ移動を最適化する

レジスタを割り付ける対象 int mod(int p, int r) { return p - p / r * r; }

レジスタを割り付ける対象 仮想レジスタ int mod(int p, int r) { return p - p / r * r; }

レジスタ割り付けに必要な情報 - どの仮想レジスタ同士が干渉しているのか - 干渉している仮想レジスタに同じ物理レジスタを割り付けてしまうとバグる - その他物理レジスタに関する制約 - 例: 関数の引数には決められたレジスタを渡す必要がある - 例2: 関数呼び出し時に caller-save register は破壊される可能性がある

レジスタ割り付けに必要な情報 - どの仮想レジスタ同士が干渉しているのか - 干渉している仮想レジスタに同じ物理レジスタを割り付けてしまうとバグる - その他物理レジスタに関する制約 - 例: 関数の引数には決められたレジスタを渡す必要がある - 例2: 関数呼び出し時に caller-save register は破壊される可能性がある

仮想レジスタの干渉を検出する クイズ: どの仮想レジスタ同士が干渉しているでしょうか？ int mod(int p, int r) { return p - p / r * r; }

仮想レジスタの干渉を検出する 正解 int mod(int p, int r) { return p - p / r * r; } int p & int r int p & p / r int p & p / r * r int r & p / r

どうやって干渉を検出する？

中間言語の導入 int mod(int p, int r) { return p - p / r * r; }

中間言語の導入 i32 mod(i32 %0, i32 %1) { %2 = sdiv i32 %0, %1 int mod(int p, int r) { %3 = mul i32 %2, %1 return p - p / r * r; %4 = sub i32 %0, %3 } ret i32 %4 }

liveness range (生存期間) を考える %0 i32 mod(i32 %0, i32 %1) { %2 = sdiv i32 %0, %1 %3 = mul i32 %2, %1 %4 = sub i32 %0, %3 ret i32 %4 } %1 %2 %3 %4

liveness range (生存期間) を考える %0 %1 %2 %3 i32 mod(i32 %0, i32 %1) { %2 = sdiv i32 %0, %1 %3 = mul i32 %2, %1 %4 = sub i32 %0, %3 ret i32 %4 } 干渉している部分 %4

必要な情報は集まった - 同じ物理レジスタを割り付けてはいけない仮想レジスタの組は分かった - 関数呼び出しなどの物理レジスタに関するれ制約も適当に考えれば良い - さて、どうやって割り付けを決める？

条件を整理すると - ある仮想レジスタの組は同じ物理レジスタに割り付けてはいけない - 例: %0 と %1 は同じ物理レジスタに割り付けてはいけない - ある仮想レジスタは特定の物理レジスタに割り付ける必要がある - 例: %0 は %rdi に割り付ける必要がある

Pre-colored Interference Graph (事前彩色済み干渉グラフ) - ノード: それぞれの仮想レジスタ - エッジ: 干渉している仮想レジスタの組 - 制約がついている仮想レジスタは事前に彩色 (割り付けを決定) しておく

Pre-colored Interference Graph (事前彩色済み干渉グラフ) %rdi %0 i32 mod(i32 %0, i32 %1) { %2 = sdiv i32 %0, %1 %3 = mul i32 %2, %1 %rax %rsi %4 %1 %4 = sub i32 %0, %3 ret i32 %4 } %3 %2

Pre-colored Interference Graph (事前彩色済み干渉グラフ) %rdi %0 i32 mod(i32 %0, i32 %1) { %2 = sdiv i32 %0, %1 %3 = mul i32 %2, %1 %rax %rsi %4 %1 %4 = sub i32 %0, %3 ret i32 %4 } %3 %2 %rax %rax

高度なトピック - グラフの次数が物理レジスタの数を越えるとスピルが発生する - スピル = レジスタの値を一時的にメモリに退避させること - スピル対象を適切に選択することでメモリアクセスの回数を抑えることが肝心 - なるべく同じ物理レジスタを割り付けた方が効率的な場合がある - 例: %3 = sub %1, %2 は %1 と %3 に同じ物理レジスタを割り付けると1命令で済む - 関数呼び出し前後で保存したい caller-save レジスタはスピルする必要がある - そういう場合は callee-save レジスタを使った方が高速であることが多い - ただし自分が定義した関数ならどのレジスタを使うか分かるのでスピルが必要ない場合も

というのを、実装した https://github.com/cp-20/pocc

• https://github.com/cp-20/pocc

自作コンパイラのアーキテクチャ Lexer 字句解析 → Parser 構文解析 → IRGenerator IR (中間言語) を生成 → IROptimizer IR の範囲で最適化 (定数畳み込み、関数のインライン化) → LifetimeAnalyzer 生存期間の解析 → RegisterAllocator レジスタ割り付け → CodeGenerator コード生成

デモ

をやろうと思ってたんですが、 Linux向けなのでMacで動かなかった😢

O3の1/3ぐらい！

コンパイラ自作のすすめ Q. なぜコンパイラを作るのか

コンパイラ自作のすすめ Q. なぜコンパイラを作るのか A. 本能です。

• https://trap.jp/post/1638/