HN 日本語サマリー

← 一覧へ戻る
プログラミング

私ではなく、コンパイラの問題だ

It's not me, it's the compiler (parsa.wtf)

74 pointsby SVI12 コメント

要約

この記事は、開発者が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


コメント: HN Reddit