コンパイラがしていること

この章でわかること:

• Rustのコードが機械語になるまでの変換の段階(rustcとLLVMの役割分担)
• コンパイラ最適化の正体。「小さな書き換えの積み重ね」が大きな差を生む仕組み
• インライン化がすべての最適化の起点になる理由(実測付き)
• 1章で「1億回のループが一瞬で終わった」ことの仕組み
• opt-level、LTO、codegen-unitsなどビルド設定の使い方

コンパイラの中で起きていること

cargo buildの内部では、コードは何段階もの中間表現を経て機械語になります。 次の図はその流れを示します。

途中に現れるHIR、MIR、LLVM IRは中間表現(intermediate representation、IR)と呼ばれる、コンパイラ内部専用のプログラム表現です。 段階ごとに表現を単純化しながら、それぞれの表現に適した処理を行います。

• rustcは、構文解析、型検査、借用検査といったRust固有の検査を行い、 MIR(mid-level IR)という単純化された表現に変換します。 MIRの段階でも一部の最適化が行われ、ジェネリクスを具体的な型ごとの 実体に展開する処理(単相化、7章で扱います)もここです
• LLVMは、多数のコンパイラが共有する最適化・コード生成基盤です (C/C++のClangやSwiftも同じLLVMを使っています)。 機械語レベルの速度に影響する最適化の大半は、LLVMが行います

1章のadd関数は、次のLLVM IRになります。

define i32 @add(i32 %a, i32 %b) {
  %_0 = add i32 %b, %a
  ret i32 %_0
}

型が付いていて、レジスタが無限にある仮想的なアセンブリに 相当する言語です。LLVMの数百の最適化パスは、 このIRをひたすら書き換えていきます。

最適化は単純な変形の積み重ね

コンパイラの最適化は、1つ1つを見れば単純な書き換えの集まりです。 代表例を挙げます。

• 定数畳み込み(constant folding): 60 * 60 * 24をコンパイル時に86400に計算します
• デッドコード除去(dead code elimination): 結果がどこにも使われない計算を削除します
• 共通部分式除去(common subexpression elimination): 同じ計算が2回現れたら、1回にして結果を使い回します
• ループ不変式移動(loop-invariant code motion): ループの中で毎回同じ結果になる計算を、ループの外に出します
• ループのアンローリング(loop unrolling): ループ本体を複数回分展開し、分岐の回数を減らして ILP(3章)やSIMD化(4章)の余地を作ります

どれも単純な書き換えです。しかしこれらのパスが 数百回適用され、ある変形が次の変形の機会を作る連鎖が起きると、 コードは原形をとどめないほど変わります。

インライン化: 他の最適化の起点

その連鎖の起点になるのがインライン化(inlining)、 関数呼び出しを関数本体の中身で置き換える変形です。

コンパイラにとって関数呼び出しは中身の見えない 境界で、呼び出しをまたいだ最適化はできません。インライン化で 境界を取り払うと、呼び出し元と中身がひとつながりのコードになり、 上に挙げたすべてのパスが働けるようになります。 これが、インライン化を起点と呼ぶ理由です。

効果を実測します。「2つの数を足すだけの関数」を1億回呼ぶループを、 インライン化を禁止した場合と、コンパイラの自動判断に任せた場合で 比べます。

use std::time::Instant;

// インライン化を禁止した小さな関数
#[inline(never)]
fn add_never(a: u64, b: u64) -> u64 {
    a.wrapping_add(b)
}

// 通常の小さな関数(インライン化するかはコンパイラが判断する)
fn add_auto(a: u64, b: u64) -> u64 {
    a.wrapping_add(b)
}

fn main() {
    let n = 100_000_000u64;

    let start = Instant::now();
    let mut sum = 0u64;
    for i in 0..n {
        sum = add_never(sum, i);
    }
    println!("inline(never): {:>9.3?} (sum={sum})", start.elapsed());

    let start = Instant::now();
    let mut sum = 0u64;
    for i in 0..n {
        sum = add_auto(sum, i);
    }
    println!("自動判断     : {:>9.3?} (sum={sum})", start.elapsed());
}

筆者の実測(Playground)では、#[inline(never)]版が約155ミリ秒、 自動判断版は約30ナノ秒で、500万倍の差です。 念のため補足すると、関数呼び出し1回のコスト自体は数ナノ秒です。 この大きな差は、次に説明するとおり最適化の連鎖が切れたことによるもので、 呼び出しの費用そのものによるものではありません。

30ナノ秒という値は、1章の「releaseビルドでループが消えた」実験と 同じ現象によるものです。 インライン化で関数の中身がループに露出した結果、 LLVMはループ全体を見通せるようになり、 閉形式(closed form)の式に置き換えたのです。

1章のループが消えた仕組み

置き換え後のコードを実際に確認します。 0からn-1までを足すループのreleaseビルドのアセンブリです(x86-64)。

pub fn sum_to(n: u64) -> u64 {
    let mut sum: u64 = 0;
    let mut i: u64 = 0;
    while i < n {
        sum = sum.wrapping_add(i);
        i += 1;
    }
    sum
}

sum_to:
	test	rdi, rdi
	je	.LBB0_1
	lea	rax, [rdi - 1]
	lea	rcx, [rdi - 2]
	mul	rcx
	shld	rdx, rax, 63
	lea	rax, [rdi + rdx]
	dec	rax
	ret
.LBB0_1:
	xor	eax, eax
	ret

ループはなく、mul(乗算)とshld(シフト)で 等差数列の和の公式 n(n−1)/2 を計算しています。 1億回のループと書いたものが、10個ほどの命令になりました。 LLVMのループ解析には、ループが計算する値を数式として認識する 仕組みがあり、認識できた場合はこのようにループ自体を削除します。

一方、#[inline(never)]版では呼び出しが境界のまま残るので、 「1億回呼んで足す」を文字どおり実行するしかありません。 155ミリ秒との差は、最適化どうしの連鎖が切れたことによる差です。

なお、#[inline]系の指定はコンパイラへの強いヒントであり、 仕様上の保証ではありません(現行のrustcでは通常尊重されます)。

実務での指針は次のとおりです。

• 同一クレート内とジェネリック関数は、コンパイラが自動で適切に インライン化します。基本的に任せて問題ありません
• 別クレートに公開する小さな関数には#[inline]を付けると、 呼び出し側クレートでもインライン化候補になります(後述のLTOでも解決可能です)
• #[inline(always)]の乱用はコードサイズを増やし、 命令キャッシュを圧迫して逆効果になりえます。適用の根拠は計測で得ます

ビルド設定で変わること

コンパイラにどこまで最適化させるかは、Cargoの設定で制御します。 主要な項目を挙げます。

• opt-levelは最適化の強さです。0(なし、debugビルドの既定)から 3(最大、releaseビルドの既定)まであり、sとzはサイズ優先です
• codegen-unitsは、クレートを何分割して並列コンパイルするかの設定です。 releaseの既定は16です。1にするとコンパイルは遅くなりますが、 最適化がクレート全体を見通せるようになります
• lto(link-time optimization)は、リンク時にクレートの境界を越えて 最適化(特にインライン化)を行う設定です。"thin"が 効果とビルド時間のバランスのよい選択です
• panicを"abort"にするとパニック時の巻き戻し処理が消え、 コードがわずかに小さく・速くなります(パニックを捕捉できなくなります)

速度を最優先するときは、典型的には次のように設定します。

[profile.release]
lto = "thin"
codegen-units = 1

これに4章のtarget-cpu=nativeを組み合わせるのが、 「手元で動かす計算プログラム」の定番です。いずれもビルド時間が増える 代わりに得られる効果なので、効果は計測(8章)で確かめます。

もう1段先の手法としてPGO(profile-guided optimization)があります。 一度実行して集めた「どの分岐がよく通るか」の統計をコンパイラに 与え、配置や判断を実測に合わせる方式ですが、 手間に見合う場面は限られるため、本書では紹介にとどめます。

コンパイラと分業する

最後に、この章の内容を「コードの書き方」に接続します。

LLVMの最適化を妨げるのは、中身の見えない境界です。 #[inline(never)]は人工的な例ですが、実務では FFI(他言語関数)呼び出しや、7章で扱う 動的ディスパッチが同じ性質を持ちます。

逆に、Rustの型システムによって最適化が適用されやすくなる面もあります。 複数の参照が同じメモリを指すことをエイリアス(alias)と呼びます。 Rustでは可変参照&mut Tは同時に1つしか存在できないため、 コンパイラは「この&mut参照が指すメモリは、生存中に他の経路から 読み書きされない」という情報をLLVMに伝えられます。 エイリアスが存在しないメモリに対しては、LLVMは読み書きの 並べ替えやベクトル化を正当性を損なわずに行えます。C/C++では人間が注意して 保証するしかなかった前提の一部を、Rustは型システムで機械的に 保証しているのです。

ただし、コンパイラが最適化できるのはあくまで「書かれたコードの範囲内」です。 アルゴリズムとデータ構造の選択は人間の役割、 その実装を機械語レベルで最適化するのはコンパイラの役割、 という分業が基本であり、コンパイラがO(n²)のアルゴリズムを O(n log n)にするような発想の転換を行うことはありません。

まとめ

• rustcはRust固有の検査とMIRへの変換・単相化を行い、機械語レベルの 最適化の大半はLLVMがLLVM IR上で行います
• 最適化は単純な書き換えパスの連鎖です。インライン化が境界を取り除き、 他のすべてのパスに機会を与えます。実測では500万倍の差になりました
• 1章のループが消えたのは、LLVMがループを数式として認識し、 閉形式の式に置き換えたためです
• 速度優先ならlto = "thin"、codegen-units = 1、 必要に応じてtarget-cpu=nativeを設定します。効果は計測で確認します

次章では、この最適化能力を前提に、Rustが掲げる 「ゼロコスト抽象化」がどこまで本当かを検証します。 イテレータ、境界チェック、dyn Traitについて、抽象化のコストを アセンブリと実測の両面から確かめます。