コンパイラ基盤を支える言語たち

Transcript

1. コンパイラ基盤を支える言語たち 2026/04/17 コンパイラのコンパの部分 #02 Arata 1
2. 導入：コンパイラの中で使われているDSL（ドメイン特化言語） コンパイラには DSLで宣言的に記述できると嬉しい 処理がある 命令セット（ISA）の定義 e.g. このCPUは RAX という64bitのレジスタを持つ 命令選択 e.g. 加算は ADD r32, r32 （CPU命令）で実装できる 最適化ルール e.g. x + 0 は x に最適化できる 2
3. 導入：どのように嬉しいか 宣言的に記述できる 再利用できる 静的に検査できる 3
4. 好きなDSL3選 4
5. 1. Go SSA rewrite rules 2015年ごろ開発開始 命令選択や最適化ルールの記述に使われる このルールに基づいてGoのコードが生成される Goのシンプルさとうまくマッチしている コードの例（ LEA a, [c]; ADD a, d => LEA a, [c+d] ） (ADD(Q|L)const [c] (LEA(Q|L) [d] {s} x)) && is32Bit(int64(c)+int64(d)) => (LEA(Q|L) [c+d] {s} x) 5
6. 2. Cranelift ISLE 2021年ごろ開発開始 命令選択や最適化ルールの記述に使われる このルールに基づいてRustのコードが生成される ルールの検証に気持ちがある 型検査が実装されている ルール同士の重複があるとエラーになる 書き換え前後で意味が変わらないかSMTソルバーで検査できる コードの例（ ADD x, y => LEA a, [x+y] ） (rule iadd_base_case_32_or_64_lea -5 (lower (has_type (ty_32_or_64 ty) (iadd _ x y))) (x64_lea ty (to_amode_add (mem_flags_trusted) x y (zero_offset)))) 6
7. 3. LLVM TableGen 2002年ごろ開発開始 命令セットの定義や命令選択の記述など、幅広く使われる （基本的に）C++のコードが生成される 制御構文があり一番言語っぽい バックエンド次第でなんでもできる SQLクエリ生成、JSON生成など コードの例（ ADD x, -1 => DEC x ） def : Pat<(add GR32:$src, -1), (!cast<Instruction>(DEC32r#suffix) GR32:$src)>; 7
8. 紹介しきれなかったDSL 命令セットの定義 / 命令選択 GCC Machine Description OpenJDK HotSpot ADL 最適化ルール / 書き換えルール Cranelift Peepmatic MLIR PDLL 命令セットの定義 Ghidra SLEIGH QEMU DecodeTree 8
9. 紹介しきれなかったDSL（続き） VM V8 Torque GraalVM Truffle DSL GraalVM Bytecode DSL Erlang/OTP BEAM LuaJIT DynASM 9
10. 好きなDSLがあればぜひ教えてください！ 10
11. 参考文献 LLVM TableGen https://llvm.org/docs/TableGen/ProgRef.html https://github.com/llvm/llvm-project/blob/main/llvm/lib/Target/X86/X86.td https://github.com/llvm/llvm- project/commit/a6240f6b1a34f9238cbe8bc8c9b6376257236b0a https://github.com/mshockwave/SQLGen Cranelift ISLE https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/isle/docs/lang uage-reference.md https://cfallin.org/blog/2023/01/20/cranelift-isle/ 11
12. 参考文献 Cranelift Peepmatic https://github.com/bytecodealliance/wasmtime/tree/dba74024aa412f28487137 5db292c1bf9079d769/cranelift/peepmatic MLIR PDLL https://mlir.llvm.org/docs/PDLL/ https://www.jeremykun.com/2024/08/04/mlir-pdll/ GCC Machine Description https://github.com/gcc-mirror/gcc/blob/master/gcc/config/ia64/ia64.md https://gcc.gnu.org/onlinedocs/gccint/Machine-Desc.html https://www.cse.iitb.ac.in/grc/intdocs/gcc-writing-md.html 12
13. 参考文献 Ghidra SLEIGH 　 - https://ghidra.re/ghidra_docs/languages/html/sleigh.html https://github.com/NationalSecurityAgency/ghidra/blob/master/Ghidra/Processor s/x86/data/languages/ia.sinc Golans SSA rewrite rules https://github.com/golang/go/blob/e870de9936a7efa42ac1915ff4ffb16017dbc 819/src/cmd/compile/internal/ssa/_gen/AMD64.rules https://www.quasilyte.dev/blog/post/go_ssa_rules/ OpenJDK HotSpot ADL https://github.com/openjdk/jdk/blob/master/src/hotspot/cpu/x86/x86.ad https://hsmemo.github.io/articles/noVxQtU9lk.html https://www.dcs.gla.ac.uk/~jsinger/pdfs/sicsa_openjdk/OpenJDKArchitecture.pd 13