私ではなく、コンパイラの問題だ
It's not me, it's the compiler (parsa.wtf)
要約
この記事は、開発者がJavaScriptエンジンのパーサーをリファクタリング中に遭遇したコンパイラバグの体験談です。当初、`bool`値を`u32`にキャストするコードをより簡潔な形式に変更したところ、予期せぬパースエラーが発生しました。明示的なif文を使ったバージョンに戻すと問題が解消したため、開発者はコンパイラの問題だと確信し、その原因をアセンブリコードを調査して突き止めました。
全文翻訳
Parsa's Blog
私じゃない、コンパイラだ!
どんなプログラマーでも、少なくとも一度は「私じゃない、コンパイラだ!」と思ったことがあるはずだ。通常、それは間違いなのだが、今回は私が実際に正しかった時の話である。
土曜の夜、いつものように、私はJavaScriptエンジンのパーサーをリファクタリングしていた。以前、プロジェクトにこのコードを書いていた。
impl LexerConsumer {
#[inline]
pub fn consume(&mut self) {
self.0 += 1;
}
#[inline]
pub fn consume_test(&mut self, store: &LexStore, expected: TokenKind) -> bool {
if self.peek(store) == expected {
self.consume();
true
} else {
false
}
}
}
これはパーサーとしてはかなり一般的なパターンだが、このコードの形は気に入らなかった。各分岐が比較の結果を返していたので、自分で値を返すようにしたらどうだろうか?
作業に取り掛かり、代わりにこのバージョンを書いた。単体で見ると生成されるアセンブリの見た目は良かった。数バイト短くなり、分岐もなかった。
#[inline]
pub fn consume_test(&mut self, store: &LexStore, expected: TokenKind) -> bool {
let x = self.peek(store) == expected;
self.0 += x as u32;
x
}
mov eax,DWORD PTR [rdi]
mov ecx,eax
and ecx,0x3f
movzx ecx,BYTE PTR [rsi+rcx*1]
cmp cl,dl
jne 233263
inc eax
mov DWORD PTR [rdi],eax
cmp cl,dl
sete al
ret
mov ecx,DWORD PTR [rdi]
mov r8d,ecx
and r8d,0x3f
xor eax,eax
cmp BYTE PTR [rsi+r8*1],dl
sete al
add ecx,eax
mov DWORD PTR [rdi],ecx
ret
そこで、簡単なステートメントをパースしてみたところ、bashの履歴のトップにあったforループをパースするコマンドがこれだった。
> joe parse - 'for (var lol; false; false) {}'
Error was found
Diagnostic { kind: E079, flag: Flag(11529215046068469773), byte: 5, current_token: Var }
Parse error
待て!何が起こったんだ?!関数を間違ってしまったのか? x as u32 は記憶しているのと違う意味を持つのか…?もっと明示的に書いてみよう。
#[inline]
pub fn consume_test(&mut self, store: &LexStore, expected: TokenKind) -> bool {
let x = self.peek(store) == expected;
self.0 += if x { 1 } else { 0 };
x
}
すると、なぜかこのバージョンは動作した!
> joe parse - 'for (var lol; false; false) {}'
Parsed 8 nodes in 14ns
Raw nodes:
[0] POS=0 ScriptStart payload=0
[1] POS=9 VariableDeclaration payload=0
[2] POS=14 FalseLit payload=0
[3] POS=21 FalseLit payload=0
[4] POS=28 BlockStatementStart payload=0
[5] POS=29 BlockStatement payload=0
[6] POS=0 ForStatement payload=0
[7] POS=0 Script payload=0
POS=000 [7] Script
POS=000 [6] ForStatement
POS=009 [1] VariableDeclaration @A0
POS=014 [2] FalseLit
POS=021 [3] FalseLit
POS=029 [5] BlockStatement
一瞬、自分の正気を疑ったが、bool as u32 が何を意味するかは十分に自信があった。このキャストは数百回書いたことがある。だから、その瞬間、絶望的で少し混乱したプログラマーなら誰でも言うであろう言葉を口にした。
私じゃない、コンパイラだ!
自分のforステートメントパーサーが実際何をしているのかを調べる必要があった。幸いなことに、社内のカスタムビルドシステムを使えば、どんな関数のアセンブリを見るのもコマンド一つでできる。そして、これはcargo asmのラッパーではない。私のプロジェクトはcargoを使っていない。TypeScriptで独自のビルドシステムを作り、Denoで実行しているからだ。Denoは--dryモードもサポートしているので、裏で何が実行されているかを確認できる。透明性万歳!
> x -b --fn ForOrInOfStatement 1 --dry
MKDIR ./out
RUN rustc src/main.rs --crate-name=joe --crate-type=staticlib
--edition=2024 --out-dir=./out --target=x86_64-unknown-linux-gnu
--cfg joe_no_libc --emit=link,obj -Crelocation-model=static
-Copt-level=3 -Clto -Ccodegen-units=1
-Cdebuginfo=line-tables-only --diagnostic-width=150
-Cpanic=abort -Ztemps-dir=out/tmp -Zhuman-readable-cgu-names
--extern proc=./out/libproc.so
RUN mold -melf_x86_64 -o ./out/joe ./out/joe.o --static
--package-metadata="Joe!" -zrelro -znoexecstack
--discard-locals --build-id --gc-sections --no-undefined
--icf=safe --compress-debug-sections=zlib
RUN bash -c nm out/joe | rustfilt | grep ForOrInOfStatement
| grep -oP '^[0-9a-f]+ t\s+\K.+' | sed -n '1p'
| xargs -I {} objdump -WK -M intel -d --disassembler-color=on
--visualize-jumps=color
--demangle=rust ./out/joe --disassemble={} 2>/dev/null
| grep -v 'Disassembly of section' | grep -v './out/joe:' | less -R
; 見やすさのために改行を追加しました。どういたしまして。
とにかく…アセンブリの検査に戻ろう。しかし、先にRustのバージョンを見た方が良いかもしれない。実際の関数は数百行あるので、ここでは短縮版を示す。
fn ForOrInOfStatement(
store: &mut Storage,
mut lex: LexerConsumer,
mut emit: EmitBuffer,
mut stack: StateStack,
) -> Termination {
debug_assert_eq!(lex.peek(store), TokenKind::For);
lex.consume();
if lex.peek_test(store, TokenKind::Await) {
if !stack.has_flag(Flag::AWAIT) {
return raise_diagnostic(store, lex, emit, stack, DiagnosticKind::E056);
}
if !lex.consume_test(store, TokenKind::LParen) {
return raise_diagnostic(store, lex, emit, stack, DiagnosticKind::E057);
}
wip!();
}
if !lex.consume_test(store, TokenKind::LParen) {
return raise_diagnostic(store, lex, emit, stack, DiagnosticKind::E058);
}
match lex.peek(store) {
TokenKind::Var => { } // var キーワード
_ => {
stack.use_flags(store, FlagDiff::clear(Flag::IN));
stack.push(store, State::ForOrInOfStatement_decide);
LeftHandSideExpression(store, lex, emit, stack)
},
}
}
fn PrimaryExpression(
store: &mut Storage,
mut lex: LexerConsumer,
mut emit: EmitBuffer,
mut stack: StateStack,
) -> Termination {
match lex.peek(store) {
_ => raise_diagnostic(store, lex, emit, stack, DiagnosticKind::E079),
}
}
そして、ついに明らかになった。
> x -b --fn ForOrInOfStatement 1
000000000021e290 <joe::fe::parser_handlers::ForOrInOfStatement>:
21e290: ff c6 inc esi
21e292: 89 f0 mov eax,esi
21e294: 83 e0 3f and eax,0x3f
21e297: 0f b6 04 07 movzx eax,BYTE PTR [rdi+rax*1]
21e29b: 83 f8 04 cmp eax,0x4 # cmp TokenKind::LParen
21e29e: ,----- 75 70 jne 21e310 <joe::fe::parser_handlers::ForOrInOfStatement+0x80>
21e2a0: | 4d 85 c0 test r8,r8
21e2a3: | ,-- 78 14 js 21e2b9 <joe::fe::parser_handlers::ForOrInOfStatement+0x29>
21e2a5: | | 41 0f b6 c0 movzx eax,r8b
21e2a9: | | c6 84 07 10 56 00 00 mov BYTE PTR [rdi+rax*1+0x5610],0x20
21e2b0: | | 20
21e2b1: | | 49 ff c0 inc r8
21e2b4: | | e9 d7 45 00 00 jmp 222890 <joe::fe::parser_handlers::LeftHandSideExpression>
21e2b9: | '-> 48 b8 00 ff ff ff ff movabs rax,0x7fffffffffffff00
21e2c0: | ff ff 7f
21e2c3: | 4c 21 c0 and rax,r8
21e2c6: | 45 0f b6 c8 movzx r9d,r8b
21e2ca: | 42 c6 84 0f 10 56 00 mov BYTE PTR [rdi+r9*1+0x5610],0x0
21e2d1: | 00 00
21e2d3: | 45 89 c9 mov r9d,r9d
21e2d6: | 4d 89 c2 mov r10,r8
21e2d9: | 49 c1 ea 10 shr r10,0x10
21e2dd: | 49 bb 00 00 00 00 ff movabs r11,0xffff00000000
21e2e4: | ff 00 00
21e2e7: | 4d 21 d3 and r11,r10
21e2ea: | 4e 89 9c cf d0 56 00 mov QWORD PTR [rdi+r9*8+0x56d0],r11
21e2f1: | 00
21e2f2: | 41 ff c0 inc r8d
21e2f5: | 45 0f b6 c0 movzx r8d,r8b
21e2f9: | 49 09 c0 or r8,rax
21e2fc: | 41 0f b6 c0 movzx eax,r8b
21e300: | c6 84 07 10 56 00 00 mov BYTE PTR [rdi+rax*1+0x5610],0x20
21e307: | 20
21e308: | 49 ff c0 inc r8
21e30b: | e9 80 45 00 00 jmp 222890 <joe::fe::parser_handlers::LeftHandSideExpression>
21e310: '----> 48 89 ca mov rdx,rcx
21e313: 83 f8 6e cmp eax,0x6e # cmp TokenKind::Await
21e316: ,-- 75 15 jne 21e32d <joe::fe::parser_handlers::ForOrInOfStatement+0x9d>
21e318: | 4c 89 c1 mov rcx,r8
21e31b: | 49 0f ba e0 3d bt r8,0x3d
21e320: ,--|-- 72 19 jb 21e33b <joe::fe::parser_handlers::ForOrInOfStatement+0xab>
21e322: | | 41 b8 37 00 00 00 mov r8d,0x37
21e328: | | e9 b3 ae 00 00 jmp 2291e0 <joe::fe::parser::raise_diagnostic>
21e32d: | '-> 4c 89 c1 mov rcx,r8
21e330: | 41 b8 39 00 00 00 mov r8d,0x39
21e336: | e9 a5 ae 00 00 jmp 2291e0 <joe::fe::parser::raise_diagnostic>
21e33b: '----> 41 b8 38 00 00 00 mov r8d,0x38
21e341: e9 9a ae 00 00 jmp 2291e0 <joe::fe::parser::raise_diagnostic>
ああ!これだけか?!私のmatch文はどこに行ったんだ?!その週の初めに、いくつかレジスタからスタックへのスピルを解消しようとしていた、このForOrInOfStatementが以前はどうなっていたか、すでに知っていた。しかし、アセンブリをよく見ると、consume_test(store, TokenKind::LParen)から来ているであろうTokenKind::LParenとの比較が見える。しかし、まずパーサーのABI、特にSysV ABIについて少し触れておこう。これは現在Rustのデフォルトの動作だ。
pub struct LexerConsumer(u32, u32);
pub struct EmitBuffer(usize);
pub struct StateStack(u64);
fn Foo(
store: &mut Storage,
mut lex: LexerConsumer,
mut emit: EmitBuffer,
mut stack: StateStack,
) -> Termination {...}
だから、アセンブリは今やかなり読みやすい。
; lex.consume() // `for`
21e290: ff c6 inc esi
; レクサーのリングバッファのインデックス計算:
21e292: 89 f0 mov eax,esi
21e294: 83 e0 3f and eax,0x3f
; 現在の位置のトークンをロード
21e297: 0f b6 04 07 movzx eax,BYTE PTR [rdi+rax*1]
; TokenKind::LParen と比較
21e29b: 83 f8 04 cmp eax,0x4
; LParen でなければ 21e310 へジャンプ
21e29e: 75 70 jne 21e310 <joe::fe::parser_handlers::ForOrInOfStatement+0x80>
; ここに来たということは、トークンはLParenで、`consume_test`の中だ。
; しかし… consume_test には `self.0 += x as u32` があったのでは?
; 待て…私の `INC ESI` は誰が食べたんだ?!
まあ、コンパイラが間違っているという確証は得られた。あとは最小限の再現可能な例を作成するだけだった。私は1.94.0-nightlyを使っていたので、nightlyでは修正されているかもしれないと疑ったが、そうではなかった!つまり、原因を見つけようと試みる必要があった。最初の試みは、最適化前のLLVM IRを見ることだった。ビルドフラグに-Cno-prepopulate-passesを追加したところ、未初期化メモリからのロードが見つかった。そして、Rust/MIRの問題かLLVMの問題かを確認するために、-Zmir-opt-level=0も使用したところ、問題は修正された。
私はイシューを開いた。最初は少し不安だった。「こんなに一般的なパターンで、私がただの馬鹿で公衆の面前で恥をかくのではないか?」と思ったのだ。だから、イシューのタイトルは「疑わしい誤コンパイル」となった。もし私が愚かな猫(ニャー)だったら、この言葉で隠れようとした。イシューを開いたときはすでに遅かったので、寝る必要があった。
翌日、目が覚めると、すでにHanna Kruppeさんから修正のためのPRが開かれていたのを見て、最高のターンアラウンドだった。
このイシューはp-criticalとi-miscompileというラベルが付いていた。61,000以上のRustイシューの中で、両方のラベルが付いているのは(これを含めて)わずか7件だ。私にとって、これらはコンパイラが持つ最も危険な種類のバグだ。なぜなら、それらはプログラマーと言語との間の契約を侵害するからだ。書いた安全なコードがすべて安全であるとは限らないことを示している。そして、一般的にp-criticalなイシューはそもそも247件しかない。
この話の最も素晴らしい点は、コミュニティがイシューに非常に速く反応し、わずか18時間で実際の修正がマージされたことだ。これがこの話で最も印象的な部分であり、迅速な対応をしてくれたtmiaskoさんとhanna-kruppeさんに感謝する。
これで、rustcと戦って勝利した時の話を生き証人として語ることができるようになった :D