自作 C コンパイラに SSA 形式の IR を実装する

自作 C コンパイラに SSA 形式の IR を実装する リベンジ編 椎名 @s7tya

gakicc Rust 製の RISC-V ターゲットの自作 C コンパイラ 2kmcc がほぼコンパイルできる @hsjoihs 作の最低限の機能だけでコンパイルできる 2000行のセルフホストされたCコンパイラ

gakicc Rust 製の RISC-V ターゲットの自作 C コンパイラ 2kmcc がほぼコンパイルできる 最適化なし

gakicc Rust 製の RISC-V ターゲットの自作 C コンパイラ 2kmcc がほぼコンパイルできる 最適化なし ベースが compilerbook なので AST から直接アセンブリを吐く プログラム 抽象構文木(AST) なんらかの中間表現(IR) アセンブリ IR なし！ compilerbook

gakicc Rust 製の RISC-V ターゲットの自作 C コンパイラ 2kmcc がほぼコンパイルできる 最適化なし ベースが compilerbook なので AST から直接アセンブリを吐く → IRを作って教科書で読んだ最適化を入れて遊んでみたい

gakicc Rust 製の RISC-V ターゲットの自作 C コンパイラ 2kmcc がほぼコンパイルできる 最適化なし ベースが compilerbook なので AST から直接アセンブリを吐く → IRを作って教科書で読んだ最適化を入れて遊んでみたい という LT をコンパイラのコンパ #1 でやりたかったけど 実装が間に合わずあんまりだったので今回リベンジ！ 滑り込みなのにLT枠をくださった orumin さんありがとうございます🙏

静的単一代入(SSA) 変数への代入を1回にだけに限定した形式 どの変数がどこで定義されたかがわかりやすい いろんな最適化が実装しやすくなる x ← 3 x ← 2 y←x 非 SSA x1 ← 3 x2 ← 2 y ← x2 SSA

静的単一代入(SSA) 変数への代入を1回にだけに限定した形式 どの変数がどこで定義されたかがわかりやすい いろんな最適化が実装しやすくなる 分岐がある場合 x←3 x←2 ? x ← 3 x ← 2 y←x 非 SSA x1 ← 3 x2 ← 2 y ← x2 SSA

静的単一代入(SSA) 変数への代入を1回にだけに限定した形式 どの変数がどこで定義されたかがわかりやすい いろんな最適化が実装しやすくなる 分岐がある場合 x1 ← 3 x2 ← 2 x3 ← phi(x1,x2) phi 関数 x ← 3 x ← 2 y←x 非 SSA 制御フローのどちらのパスを通って きたかをもとに値を決める x1 ← 3 x2 ← 2 y ← x2 SSA

超ざっくり SSA 変換 制御フローグラフ(CFG) を作る phi 関数を挿入 変数名の変更 x = 0 y = 10 if (cond) { x = 1 } z = x + 1 w=y+1

超ざっくり SSA 変換 制御フローグラフ(CFG) を作る phi 関数を挿入 変数名の変更 x = 0 y = 10 x = 0 cond? y = 10 if (cond) { x = 1 x = 1 } z = x + 1 z = x + 1 w=y+1 w=y+1 Basic Block (BB) 分岐や合流を含まない命令の列 (ざっくり) 制御フローグラフ(CFG) Basic Block からなる有向グラフ

超ざっくり SSA 変換 制御フローグラフ(CFG) を作る phi 関数を挿入 変数名の変更 x = 0 y = 10 x = 0 cond? y = 10 if (cond) { x = 1 x = 1 } z = x + 1 z = x + 1 w=y+1 w=y+1 x = 0 y = 10 cond? x=1 x = phi(x,x) y = phi(y,y) z = x + 1 w=y+1

超ざっくり SSA 変換 制御フローグラフ(CFG) を作る phi 関数を挿入 変数名の変更 x = 0 y = 10 x = 0 cond? y = 10 if (cond) { x = 1 x = 1 } z = x + 1 z = x + 1 w=y+1 w=y+1 x1 = 0 y1 = 10 cond? x2 = 1 x3 = phi(x1,x2) y2 = phi(y1,y1) z1 = x3 + 1 w1 = y2 + 1

超ざっくり SSA 変換 制御フローグラフ(CFG) を作る phi 関数を挿入 変数名の変更 x = 0 y = 10 x = 0 cond? y = 10 if (cond) { x = 1 x = 1 } z = x + 1 z = x + 1 w=y+1 w=y+1 ナイーブに変換すると 冗長な phi 関数がたくさん入ってしまう x1 = 0 y1 = 10 cond? x2 = 1 x3 = phi(x1,x2) y2 = phi(y1,y1) z1 = x3 + 1 w1 = y2 + 1

超ざっくり SSA 変換 制御フローグラフ(CFG) を作る phi 関数を挿入 変数名の変更 x = 0 y = 10 x = 0 cond? y = 10 if (cond) { x = 1 x = 1 } z = x + 1 z = x + 1 w=y+1 w=y+1 ナイーブに変換すると 冗長な phi 関数がたくさん入ってしまう → Dominance Frontier でいい感じに x1 = 0 y1 = 10 cond? x2 = 1 x3 = phi(x1,x2) y2 = phi(y1,y1) z1 = x3 + 1 w1 = y2 + 1

超ざっくり SSA 逆変換 phi 関数の前のブロックの末尾に x1 = 0 y1 = 10 cond? x2 = 1 x3 = phi(x1,x2) z1 = x3 + 1 w1 = y1 + 1 <phi関数の代入先> = CFG上のそのパスを通った場合の値 x1 = 0 y1 = 10 cond? x2 = 1 x3 = x2 z1 = x3 + 1 w1 = y1 + 1 を挿入

超ざっくり SSA 逆変換 phi 関数の前のブロックの末尾に x1 = 0 y1 = 10 cond? x2 = 1 x3 = phi(x1,x2) z1 = x3 + 1 w1 = y1 + 1 <phi関数の代入先> = CFG上のそのパスを通った場合の値 BB0 x1 = 0 を挿入 y1 = 10 cond? BB0 の末尾に挿入すると BB1 に影響が出てしまう 青丸で囲ったような edge を x2 = 1 BB1 Critical Edge と呼び、除去する x3 = x2 z1 = x3 + 1 BB2 w1 = y1 + 1

超ざっくり SSA 逆変換 空のブロックを経由するように分割 x1 = 0 y1 = 10 cond? x2 = 1 x3 = x2 z1 = x3 + 1 w1 = y1 + 1

超ざっくり SSA 逆変換 空のブロックを経由するように分割 x1 = 0 y1 = 10 cond? x2 = 1 x3 = x2 z1 = x3 + 1 w1 = y1 + 1 うまく分割できた！🎉 x1 = 0 y1 = 10 cond? x3 = x1 x2 = 1 x3 = x2 z1 = x3 + 1 w1 = y1 + 1

超ざっくり SSA 逆変換 空のブロックを経由するように分割 x1 = 0 y1 = 10 cond? x2 = 1 x3 = x2 z1 = x3 + 1 w1 = y1 + 1 ただし、ここで挿入するコピーは Parallel Copy として処理する必要がある うまく分割できた！🎉 x1 = 0 y1 = 10 cond? x3 = x1 x2 = 1 x3 = x2 z1 = x3 + 1 w1 = y1 + 1

よくある最適化 定数畳み込み x ← 60 * 60 * 24 定数伝播 x ← 3
 z←x コピー伝播 x ← y z←x x ← 86400 x ← 3
 z←3 x ← y
 z←y

よくある最適化 定数畳み込み x ← 60 * 60 * 24 定数伝播 x ← 3
 z←x コピー伝播 x ← y z←x x ← 86400 x ← 3
 z←3 x ← y
 z←y

よくある最適化 定数畳み込み x ← 60 * 60 * 24 x ← 86400 2kmcc をコンパイルしたときの命令数 定数伝播 x ← 3
 x ← 3
 z←x z←3 コピー伝播 x ← y x ← y
 z←x z←y 32366 → 26990

よくある最適化 定数畳み込み x ← 60 * 60 * 24 x ← 86400 2kmcc をコンパイルしたときの命令数 定数伝播 x ← 3
 x ← 3
 z←x z ← 3 約17%削減できた🎉 コピー伝播 x ← y x ← y
 z←x z←y 32366 → 26990

よくある最適化 定数畳み込み x ← 60 * 60 * 24 x ← 86400 2kmcc をコンパイルしたときの命令数 定数伝播 x ← 3
 x ← 3
 z←x z ← 3 約17%削減できた🎉 コピー伝播 x ← y x ← y
 z←x z←y 32366 → 26990 ！ い し れ う