概要
llvmをrustで使うべくllvm-sysのcrateのDocを見ていたら見かけたのでいい機会なのでコードを読んでみる． （”Wilfred's BF compiler”と書いてあり，BFってなんやねんと思ったら，brainf*ckだった．．．） https://crates.io/crates/llvm-sys
bfcの概要
bfc.wilfred.me.uk 以下上記サイトの引用
- an industrial-grade Brainfuck compiler (産業レベルで耐えれても，産業では使うと誰も．．．と言いたいけど世界は広いので断言はやめておく．)
- a fast compiler for a silly language
- utterly over-engineered
An elaborate IR with position-preserving optimisations.
Extensive testing, even testing idempotence and observational equivalence of optimisations.
Coloured code diagnostics with position highlighting.
Gratuitous website.
軽い気持ちで読むつもりだったが，言語を作る人にはいい勉強になりそうだ．
一旦動かしてみる
cargo.tomlのバージョンを確認
brew install llvm@14 // .zshrcに書き込む export PATH="/opt/homebrew/opt/llvm@14/bin:$PATH" export LDFLAGS="-L/opt/homebrew/opt/llvm@14/lib" export CPPFLAGS="-I/opt/homebrew/opt/llvm@14/include"
実行
target/release/bfc sample_programs/hello_world.bf ./hello_world Hello World!
最適化
--opt=0 # no optimisations --opt=1 # peephole only --opt=2 # peephole and speculative execution // のぞき穴の最適化と投機的実行
Peephole Optimisations
src/peephole.rs
- combine_increments: 連続するインクリメントを単一の命令に統合。
- –> ast arrayをcoalesceして，Incrementを統合
- zeroing_loops: 特定のループをセルをゼロに設定する命令に置き換え。
- remove_dead_loops: 実行されないループを削除。
- remove_redundant_sets: 不要なセット操作を削除。[bf特有]
- annotate_known_zero: 実行開始時にセルがゼロであることを注記。[bf特有]
test
bfcのテストがいい感じっぽいのでちょっと読んでみる． これ以降のコードのスニペットは，GNU General Public License v2.0に準拠する．
quickcheckを使っているっぽい．
Verifying Improvement
最適化を行ったあとに中間表現の命令数が多くなってはいけない．それはそう．
より抜粋．
#[test]
fn quickcheck_optimize_should_decrease_size() {
fn optimize_should_decrease_size(instrs: Vec<AstNode>) -> bool {
// The result of optimize() should never increase the number of
// instructions.
let result = optimize(instrs.clone(), &None).0;
count_instrs(&result) <= count_instrs(&instrs)
}
quickcheck(optimize_should_decrease_size as fn(Vec<AstNode>) -> bool);
}
Verifying Idempotence
冪等性があるよう． 最適化済みなものを最適化しても変化がない． f(f(program)) == f(program)
#[test]
fn annotate_known_zero_idempotent() {
fn is_idempotent(instrs: Vec<AstNode>) -> bool {
let annotated = annotate_known_zero(instrs);
let annotated_again = annotate_known_zero(annotated.clone());
if annotated == annotated_again {
true
} else {
println!("intermediate: {:?}", annotated);
println!("final: {:?}", annotated_again);
false
}
}
quickcheck(is_idempotent as fn(Vec<AstNode>) -> bool);
}
Verifying Behavioural Equivalence
最適化しても実行結果は変わらない．ただし，一部最適化において悪さする場合がある．例えば，無効な処理を削除する最適化がある．実行時のセル（bfでのセルはチューリングマシンでのテープの役割を果たす．）を確認する場合があるが，無効な処理がセルに書き込みをしていた場合，テストにパスしなくなるので注意．eval(f(program)) === eval(program)．（テストを発掘するのは苦労した．#[test]で検索かけて159Hit．ほぼ最後の方に見たファイルの一番下にあった．他にもあったかもしれないが．．．コメントに，semanticsとかbehave周りの直接的な言葉がないのも辛かった．結局ほぼすべてのテストを眺めた，）
fn test_overall_optimize_is_sound() {
fn optimize_ignore_warnings(instrs: Vec<AstNode>) -> Vec<AstNode> {
optimize(instrs, &None).0
}
fn optimizations_sound_together(
instrs: Vec<AstNode>,
read_value: Option<i8>,
) -> TestResult {
// Since sort_by_offset and remove_read_clobber can change
// cell values at termination, the overall optimize can change
// cells values at termination.
transform_is_sound(instrs, optimize_ignore_warnings, false, read_value)
}
quickcheck(optimizations_sound_together as fn(Vec<AstNode>, Option<i8>) -> TestResult);
}
check_cells = falseなので，bfcのweb docsで述べられているように，cellは無視している． github.com
fn transform_is_sound<F>(
instrs: Vec<AstNode>,
transform: F,
check_cells: bool,
dummy_read_value: Option<i8>,
) -> TestResult
まとめ
疲れた，どうでもいいが，soundってなんやねんと思ったら，soundnessが健全性的な意味があることをしった． 正当性とか検証とかの文脈でよく使われるんだろう，
