---
title: 自作 C コンパイラに SSA 形式の IR を実装する
tags: 
author: [Shina](https://image.docswell.com/user/s7tya)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/87DKYG65JG.jpg?width=480
description: Kernel/VM探検隊＠つくば No3
published: March 20, 26
canonical: https://image.docswell.com/s/s7tya/ZX2YW3-2026-03-20-144359
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/87DKYG65JG.jpg)

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


# Page. 2

![Page Image](https://bcdn.docswell.com/page/VJPK63YDE8.jpg)

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


# Page. 3

![Page Image](https://bcdn.docswell.com/page/2EVV34GGEQ.jpg)

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


# Page. 4

![Page Image](https://bcdn.docswell.com/page/57GL3KDDEL.jpg)

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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/4EQY5N1XJP.jpg)

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


# Page. 6

![Page Image](https://bcdn.docswell.com/page/KJ4W9GR271.jpg)

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


# Page. 7

![Page Image](https://bcdn.docswell.com/page/LE1YKDQK7G.jpg)

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


# Page. 8

![Page Image](https://bcdn.docswell.com/page/GEWGDYMPJ2.jpg)

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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/47ZLGXQ6J3.jpg)

静的単一代入(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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/YJ6WY46LJV.jpg)

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


# Page. 11

![Page Image](https://bcdn.docswell.com/page/GJ5MGQ6MJ4.jpg)

超ざっくり 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 からなる有向グラフ


# Page. 12

![Page Image](https://bcdn.docswell.com/page/LE3WRVQ9E5.jpg)

超ざっくり 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


# Page. 13

![Page Image](https://bcdn.docswell.com/page/8EDKY8987G.jpg)

超ざっくり 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


# Page. 14

![Page Image](https://bcdn.docswell.com/page/V7PK68ZWJ8.jpg)

超ざっくり 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


# Page. 15

![Page Image](https://bcdn.docswell.com/page/2JVV3NW9JQ.jpg)

超ざっくり 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


# Page. 16

![Page Image](https://bcdn.docswell.com/page/5EGL3KD4JL.jpg)

超ざっくり 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
を挿入


# Page. 17

![Page Image](https://bcdn.docswell.com/page/4JQY5N1R7P.jpg)

超ざっくり 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


# Page. 18

![Page Image](https://bcdn.docswell.com/page/K74W9GRQE1.jpg)

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


# Page. 19

![Page Image](https://bcdn.docswell.com/page/LJ1YKDQLEG.jpg)

超ざっくり 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


# Page. 20

![Page Image](https://bcdn.docswell.com/page/GJWGDYMQ72.jpg)

超ざっくり 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


# Page. 21

![Page Image](https://bcdn.docswell.com/page/4EZLGXQ373.jpg)

よくある最適化
定数畳み込み
x ← 60 * 60 * 24
定数伝播
x ← 3

z←x
コピー伝播
x ← y
z←x
x ← 86400
x ← 3

z←3
x ← y

z←y


# Page. 22

![Page Image](https://bcdn.docswell.com/page/Y76WY46Z7V.jpg)

よくある最適化
定数畳み込み
x ← 60 * 60 * 24
定数伝播
x ← 3

z←x
コピー伝播
x ← y
z←x
x ← 86400
x ← 3

z←3
x ← y

z←y


# Page. 23

![Page Image](https://bcdn.docswell.com/page/G75MGQ6974.jpg)

よくある最適化
定数畳み込み
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


# Page. 24

![Page Image](https://bcdn.docswell.com/page/9J29YPM5ER.jpg)

よくある最適化
定数畳み込み
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


# Page. 25

![Page Image](https://bcdn.docswell.com/page/DEY4G5X6JM.jpg)

よくある最適化
定数畳み込み
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
！
い
し
れ
う