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

この章でわかること:

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

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

cargo buildの裏で、コードは何段階もの姿を経て機械語になります。次の図がその流れです。

flowchart LR
    src["ソースコード"] --> hir["HIR"]
    subgraph rustc ["rustc (Rust固有の処理)"]
        hir --> mir["MIR"] --> mopt["MIR最適化・単相化"]
    end
    subgraph llvm ["LLVM (最適化とコード生成)"]
        ir["LLVM IR"] --> opt["最適化パス群"] --> mc["機械語"]
    end
    mopt --> ir
    mc --> bin["リンク → 実行ファイル"]

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

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

LLVM IRは実物を見るのが早いです。1章のadd関数はこうなります。

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はループ全体を見通せるようになり、閉じた式に置き換えたのです。

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——抽象化のコストをアセンブリと実測の両面から確かめます。