コンパイラを凌駕する

Matt Keeter // ブログ プロジェクト リサーチ ブログ リンクコンパイラを凌駕する現代では、アセンブリを書くのは愚かな試みだと誰もが知っています。コンパイラは何世紀にもわたるエンジニアリングの成果であり、プロセッサのことをあなたよりもよく知っています。それにもかかわらず、噂を聞くことがあります。古代の書物に書かれ、静かな酒場で囁かれ、過ぎ去った寺院の壁に書きつけられ、謎めいたテキストで示唆されている噂は、特定の絵を描いています。コンパイラはインタプリタのコード生成が苦手であり、アセンブリでインタプリタを書くことでコンパイラを上回ることが可能です。私は最近、256個のオペコードを持つスタックベースのアーキテクチャであるUxn CPUの高速インタプリタを書きました。インタプリタは、RAMからバイトを読み取り、適切な命令を選択する単純なループです。 impl Uxn { /// 指定されたアドレスから開始し、終了するまでVMを実行します #[inline] pub fn run<D: Device>(&mut self, dev: &mut D, mut pc: u16) { loop { let op = self.ram[usize::from(pc)]; pc = pc.wrapping_add(1); let Some(next) = self.op(op, dev, pc) else { break; }; pc = next; } } /// 単一のオペレーションを実行します #[inline] fn op<D: Device>(&mut self, op: u8, dev: &mut D, pc: u16) -> Option<u16> { match op { 0x00 => op::brk(self, dev, pc), 0x01 => op::inc::<0b000>(self, dev, pc), 0x02 => op::pop::<0b000>(self, dev, pc), 0x03 => op::nip::<0b000>(self, dev, pc), 0x04 => op::swp::<0b000>(self, dev, pc), 0x05 => op::rot::<0b000>(self, dev, pc), 0x06 => op::dup::<0b000>(self, dev, pc), 0x07 => op::ovr::<0b000>(self, dev, pc), 0x08 => op::equ::<0b000>(self, dev, pc), 0x09 => op::neq::<0b000>(self, dev, pc), 0x0a => op::gth::<0b000>(self, dev, pc), 0x0b => op::lth::<0b000>(self, dev, pc), 0x0c => op::jmp::<0b000>(self, dev, pc), 0x0d => op::jcn::<0b000>(self, dev, pc), 0x0e => op::jsr::<0b000>(self, dev, pc), // ...など } } } すべてのオペコードの実装はモノモルファイズされ、Uxn::run(..)の本体にインライン化され、コンパイラはキーとなる値をレジスタに保持するのに十分賢いです。これにより比較的高速になり、参照実装よりも10〜20％の速度向上が見られます。コンパイラが何をしているのか、そして私たちがそれより良くできるのかをアセンブリで見てみましょう。コンテキストとして、Uxn CPUには4つの異なるメモリがあります。データスタック、これは[u8; 256]とu8インデックスです。リターンスタック、これは同じ形式です。RAM、これは[u8; 65535]です。デバイスメモリ、これは今回は無視します（D: Device引数とともに）。評価中、プログラムカウンタpcも追跡します。これはRAMをインデックス付けするために使用されるu16です。各サイクルで、RAMからバイトをロードし、適切なオペコードを呼び出します。一部のオペコードはRAMの読み書きもできるため、自己変更コードも可能です。アセンブリを調べることで、どの値がどこに格納されているかを逆エンジニアリングできます。データスタックの最上位の値を取得してインクリメントするINC操作を考えてみましょう。 ; INC 0x100002d4c: ldrb w8, [x25] ; 現在のデータスタックインデックスを読み取る 0x100002d50: ldrb w9, [x24, x8] ; データスタックからバイトを読み取る 0x100002d54: add w9, w9, #1 ; そのバイトをインクリメントする 0x100002d58: strb w9, [x24, x8] ; そのバイトをスタックに書き戻す 0x100002d5c: b 0x100002d1c ; ディスパッチループに戻る このアセンブリから、以下のことがわかります。x25はデータスタックインデックスの値ではなく、そのアドレスです！x24はデータスタック配列のアドレスです。w9は一時レジスタとして使用されます。 同様に、INCr（リターンスタックの最上位の値をインクリメントする）は、x22とx23がリターンスタックのデータとインデックスのアドレスであることを教えてくれます。JMPは、プログラムカウンタがw27に格納されていることを示しています。 ; JMP 0x100002eac: ldrb w8, [x25] ; 現在のデータスタックインデックスを読み取る 0x100002eb0: ldrsb w9, [x24, x8] ; データスタックから符号付きジャンプオフセットを読み取る 0x100002eb4: sub w8, w8, #1 ; データスタックインデックスをデクリメントする 0x100002eb8: strb w8, [x25] ; データスタックインデックスを書き戻す 0x100002ebc: add w27, w27, w9 ; プログラムカウンタにジャンプを適用する 0x100002ec0: b 0x100002d1c ; ディスパッチループに戻る 最後に、ディスパッチループ自体も調べる価値があります。 0x100002d1c: and x10, x27, #0xffff ; pcをu16にマスクする 0x100002d20: ldr x8, [x20, #256] ; RAMベースを*mut Uxnからロードする 0x100002d24: ldrb w10, [x8, x10] ; RAMからオペコードバイトをロードする 0x100002d28: add w27, w27, #1 ; pcをインクリメントする 0x100002d2c: adr x11, #-96 ; ジャンプのベースをロードする 0x100002d30: ldrh w12, [x27, x10, lsl #1] ; オペコードごとのジャンプ量をロードする 0x100002d34: add x11, x11, x12, lsl #2 ; ジャンプ場所を計算する 0x100002d38: br x11 ; オペコード実装にジャンプする コンパイラは256個のオフセット（それぞれ2バイトの値、lsl #1で示される）のジャンプテーブルを生成しました。このテーブルからオペコード固有の値を取得してジャンプターゲットを計算し、オペコードの実装にジャンプする間接ブランチを実行します。デバッガでこれを実行し、実際のジャンプテーブルをダンプできます。 (lldb) disas -p -c3 raven-cli`raven_uxn::Uxn::run::had9dba0d7d1b5105: -> 0x100002d30 <+236>: ldrh w12, [x27, x10, lsl #1] 0x100002d34 <+240>: add x11, x11, x12, lsl #2 0x100002d38 <+244>: br x11 (lldb) reg read x27 x27 = 0x0000000100170b10 (lldb) memory read -s2 -fu -c256 0x0000000100170b10 0x100170b10: 2923 0x100170b12: 31 0x100170b14: 36 0x100170b16: 40 0x100170b18: 44 0x100170b1a: 52 0x100170b1c: 28 0x100170b1e: 64 0x100170b20: 70 0x100170b22: 78 0x100170b24: 86 0x100170b26: 94 0x100170b28: 119 0x100170b2a: 102 0x100170b2c: 110 0x100170b2e: 125 ; など...（確かに、これはオペコードごとの命令リストを生成した方法です） アセンブリを見たところ、非効率的である可能性のある点が2つあります。一部の重要な値（スタックインデックス、RAMのベースアドレス）はレジスタではなくメモリに保持されています。例えば、INCは現在のデータスタックインデックスを取得するために追加のロード操作があります。ディスパッチループは、オペコード固有の実装への単一の間接ブランチを取ります。これは、そのブランチがほとんど予測不可能になることを意味します！コードのプロファイリングによると、最もホットな命令はすべてディスパッチループにあります。ldrhは総実行時間の1/3以上を占めます。（プロファイラが時間を正しい特定の命令に帰属させているか確信はありませんが、ディスパッチがコストがかかるという感覚は確かにあります）。LuaJITは最高の高速インタプリタであり、アセンブリで書かれています。Mike Pallは、レジスタに状態を保持することと間接スレッディングを速度の2つの要因として特に挙げており、これらはアセンブリでしか確実に達成できません。コンパイラに非常に特定のパターンを生成させるのは難しいため、独自のアセンブリを書き始めましょう。私のホームマシンはM1 Macbookなので、すべてのアセンブリはAArch64形式になります。実装は汎用レジスタを使用します。w*とx*が同じレジスタの32ビットと64ビットビューを参照することに注意してください。 レジスタ割り当て私たちの最初の最適化は、すべての重要なデータをレジスタに格納し、余分なロードとストアを避けることです。私の実装は、数個のスクラッチレジスタとともに、9個のレジスタ（x0-x8）を使用します。 ; x0 - スタックポインタ (&mut [u8; 256]) ; x1 - スタックインデックス (u8) ; x2 - リターンスタックポインタ (&mut [u8; 256]) ; x3 - リターンスタックインデックス (u8) ; x4 - RAMポインタ (&mut [u8; 65536]) ; x5 - プログラムカウンタ (u16)、RAM内の次の値のオフセット ; x6 - VMポインタ (&mut Uxn) ; x7 - デバイスハンドルポインタ (&DeviceHandle) ; x8 - ジャンプテーブルポインタ ; x9-15 - スクラッチレジスタ AArch64呼び出し規約は8個の入力引数しか与えないため、これらの値をすべてレジスタに入れて関数を直接呼び出すことはできません。C ABI形式のエントリポイント（後述）が必要になります。 間接スレッディング私たちの2番目の最適化は、ディスパッチループを排除するためにスレッドコードを使用することです。各オペコードの実装は、次のオペコードの実装へのジャンプで終わります。オペコードはVM RAMに単一バイトとして格納され、ベースアドレスはx4です。関数ポインタの個別のジャンプテーブルを構築し、そのアドレスをレジスタx8に渡します。Rust側では、そのテーブルは次のようになります。 extern "C" { fn BRK(); fn INC(); fn POP(); fn NIP(); fn SWP(); // ...