本家Rustコンパイラのソースを読もうとしてみる（7）

# 前回までのあらすじ

[Rustの本家コンパイラ](https://github.com/rust-lang/rust)を[Guide to Rustc Development](https://rustc-dev-guide.rust-lang.org/about-this-guide.html)に沿って読んでいく。ようやく今回で最後です。長かった～。

[目次（初回）](https://qiita.com/0yoyoyo/items/eba97a019d0e60324263)


# MIR to Binaries

最後の章。MIRから最終的なバイナリを出力するところまでが説明されている。

### MIR optimizations

MIRに対しては様々な最適化が行われおり、`run_optimization_passes()`でどのようなパスが実施されるか確認することができる。`MirPass`を実装したトレイトオブジェクトの配列を定義して実行するという流れになっているようだ。

```rust:rustc_mir/src/transform/mod.rs
fn run_optimization_passes<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
    let mir_opt_level = tcx.sess.opts.debugging_opts.mir_opt_level;
...
    // The main optimizations that we do on MIR.
    let optimizations: &[&dyn MirPass<'tcx>] = &[
        &lower_intrinsics::LowerIntrinsics,
        &remove_unneeded_drops::RemoveUnneededDrops,
        &match_branches::MatchBranchSimplification,
        // inst combine is after MatchBranchSimplification to clean up Ne(_1, false)
        &multiple_return_terminators::MultipleReturnTerminators,
        &instcombine::InstCombine,
        &const_prop::ConstProp,
        &simplify_branches::SimplifyBranches::new("after-const-prop"),
        &early_otherwise_branch::EarlyOtherwiseBranch,
        &simplify_comparison_integral::SimplifyComparisonIntegral,
        &simplify_try::SimplifyArmIdentity,
        &simplify_try::SimplifyBranchSame,
        &dest_prop::DestinationPropagation,
        &simplify_branches::SimplifyBranches::new("final"),
        &remove_noop_landing_pads::RemoveNoopLandingPads,
        &simplify::SimplifyCfg::new("final"),
        &nrvo::RenameReturnPlace,
        &simplify::SimplifyLocals,
        &multiple_return_terminators::MultipleReturnTerminators,
    ];
...
    // Main optimization passes
    #[rustfmt::skip]
    run_passes(
        tcx,
        body,
        MirPhase::Optimization,
        &[
            if mir_opt_level > 0 { optimizations } else { no_optimizations },
            pre_codegen_cleanup,
        ],
    );
}
```

試しにどれかひとつパスの中身をのぞいてみよう。ここでは簡単そうな`MatchBranchSimplification`を見てみることにする。このパスは処理のソースコードも100行程度、かつコメントもかなり丁寧に記載されていて大変読みやすかった。

まず、どのような最適化なのか確認しよう。このMIRのサンプルもソースコード内のコメントから転記したものだが、まず、このように2つの基本ブロックに分岐して真理値を代入するMIRがあるとする。

```rust
bb0: {
    switchInt(move _3) -> [42_isize: bb1, otherwise: bb2];
}
bb1: {
    _2 = const true;
    goto -> bb3;
}
bb2: {
    _2 = const false;
    goto -> bb3;
}
```

これを1つの基本ブロックにまとめる。

```rust
bb0: {
   _2 = Eq(move _3, const 42_isize);
   goto -> bb3;
}
```

これが`MatchBranchSimplification`のパスでやっていることだ。Rustのコードで表現するならば、

```rust
if a == 1 {
    b = true;
} else {
    b = false;
}
```
を

```rust
b = a == 1;
```

に変換するような感じだろうか。

実装は`MatchBranchSimplification`に対する`run_pass()`を見ていく。上でも述べた通り、とても読みやすく作られているので解説はあまり必要ないのだが、一応軽めに残しておく。

```rust:rustc_mir/src/transform/match_branches.rs
impl<'tcx> MirPass<'tcx> for MatchBranchSimplification {
    fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
...
        let def_id = body.source.def_id();
        let (bbs, local_decls) = body.basic_blocks_and_local_decls_mut();
        'outer: for bb_idx in bbs.indices() {
...
            let (discr, val, switch_ty, first, second) = match bbs[bb_idx].terminator().kind {
                TerminatorKind::SwitchInt {
                    discr: ref discr @ (Operand::Copy(_) | Operand::Move(_)),
                    switch_ty,
                    ref targets,
                    ..
                } if targets.iter().len() == 1 => {
                    let (value, target) = targets.iter().next().unwrap();
                    if target == targets.otherwise() {
                        continue;
                    }
                    (discr, value, switch_ty, target, targets.otherwise())
                }
                // Only optimize switch int statements
                _ => continue,
            };
...
            for (f, s) in first_stmts.iter().zip(scnd_stmts.iter()) {
                match (&f.kind, &s.kind) {
                    // If two statements are exactly the same, we can optimize.
                    (f_s, s_s) if f_s == s_s => {}

                    // If two statements are const bool assignments to the same place, we can optimize.
                    (
                        StatementKind::Assign(box (lhs_f, Rvalue::Use(Operand::Constant(f_c)))),
                        StatementKind::Assign(box (lhs_s, Rvalue::Use(Operand::Constant(s_c)))),
                    ) if lhs_f == lhs_s
                        && f_c.literal.ty.is_bool()
                        && s_c.literal.ty.is_bool()
                        && f_c.literal.try_eval_bool(tcx, param_env).is_some()
                        && s_c.literal.try_eval_bool(tcx, param_env).is_some() => {}

                    // Otherwise we cannot optimize. Try another block.
                    _ => continue 'outer,
                }
            }
...
            let new_stmts = first.statements.iter().zip(second.statements.iter()).map(|(f, s)| {
...
            });

            from.statements
                .push(Statement { source_info, kind: StatementKind::StorageLive(discr_local) });
            from.statements.push(Statement {
                source_info,
                kind: StatementKind::Assign(box (Place::from(discr_local), Rvalue::Use(discr))),
            });
            from.statements.extend(new_stmts);
            from.statements
                .push(Statement { source_info, kind: StatementKind::StorageDead(discr_local) });
            from.terminator_mut().kind = first.terminator().kind.clone();
        }
    }
}
```

まずは、最適化（簡略化）できるのかを確認する。それは例えば、2方向への分岐（`SwitchInt`）になっているか、分岐の先では結果が真理値になっているか、といった内容だ。確認ができたら入力の内容をもとに同等の新しい文（`new_stmts`）を作成する。最後に、もともとの文（`from.statements`）の最後に新しい文を追加し、分岐がなくなるので基本ブロックの行き先（`from.terminator_mut().kind`）を上書きして完了となる。

### Monomorphization

ジェネリクスで表現されたソースはコード生成時に単一化（Monomorphization）される。そのため単一化の処理は`codegen_crate()`で呼ばれる`collect_and_partition_mono_items()`から開始される。コメントにもあるように、ここではアイテムの収集（Collection）とコード生成ユニットの分割（Partitioning）がセットで行われるので、両方の触りを見ていこう。

```rust:rustc_codegen_ssa/src/base.rs
pub fn codegen_crate<B: ExtraBackendMethods>(
    backend: B,
    tcx: TyCtxt<'tcx>,
    metadata: EncodedMetadata,
    need_metadata_module: bool,
) -> OngoingCodegen<B> {
...
    // Run the monomorphization collector and partition the collected items into
    // codegen units.
    let codegen_units = tcx.collect_and_partition_mono_items(LOCAL_CRATE).1;
...
}
```

`collect_and_partition_mono_items()`の中身を見てみると、`collect_crate_mono_items()`という関数と`partition()`という関数が呼ばれており、それぞれCollectionとPartitioningと思われる。まずはCollectionから見ていこう。

```rust:rustc_mir/src/monomorphize/partitioning/mod.rs
fn collect_and_partition_mono_items<'tcx>(
    tcx: TyCtxt<'tcx>,
    cnum: CrateNum,
) -> (&'tcx DefIdSet, &'tcx [CodegenUnit<'tcx>]) {
...
    let (items, inlining_map) = collector::collect_crate_mono_items(tcx, collection_mode);
...
    let (codegen_units, _) = tcx.sess.time("partition_and_assert_distinct_symbols", || {
        sync::join(
            || {
                &*tcx.arena.alloc_from_iter(partition(
                    tcx,
                    &mut items.iter().cloned(),
                    tcx.sess.codegen_units(),
                    &inlining_map,
                ))
            },
            || assert_symbols_are_distinct(tcx, items.iter()),
        )
    });
...
}
```


##### Collection

ここではアイテムの収集を行う。アイテムというのは典型的には関数をイメージするのが分かりやすいのではないかと思う。ガイドでもポイントされているが、`collector`モジュールの概要については[そのドキュメント](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/monomorphize/collector/index.html)が詳しい。

大きく2つのステップでアイテムを集めていく。

1. ジェネリックでないアイテムを集める。これを**root**と呼ぶ。
2. rootから呼ばれるジェネリックなアイテムを集める。これを**neighbor**と呼ぶ。neighborはジェネリックでないアイテムから呼ばれるので、必然的に具体的な型が分かる。

`collect_roots()`でrootを、`collect_items_rec()`でneighborを収集しているようだ。

```rust:rustc_mir/src/monomorphize/collector.rs
pub fn collect_crate_mono_items(
    tcx: TyCtxt<'_>,
    mode: MonoItemCollectionMode,
) -> (FxHashSet<MonoItem<'_>>, InliningMap<'_>) {
    let _prof_timer = tcx.prof.generic_activity("monomorphization_collector");

    let roots =
        tcx.sess.time("monomorphization_collector_root_collections", || collect_roots(tcx, mode));

    debug!("building mono item graph, beginning at roots");

    let mut visited = MTLock::new(FxHashSet::default());
    let mut inlining_map = MTLock::new(InliningMap::new());

    {
        let visited: MTRef<'_, _> = &mut visited;
        let inlining_map: MTRef<'_, _> = &mut inlining_map;

        tcx.sess.time("monomorphization_collector_graph_walk", || {
            par_iter(roots).for_each(|root| {
                let mut recursion_depths = DefIdMap::default();
                collect_items_rec(
                    tcx,
                    dummy_spanned(root),
                    visited,
                    &mut recursion_depths,
                    inlining_map,
                );
            });
        });
    }

    (visited.into_inner(), inlining_map.into_inner())
}
```

まずは名前もそのままな`collect_roots()`を見てみよう。rootの収集はHIRをもとに行われる。`RootCollector`という型のデータを定義し、その型に`ItemLikeVisitor`を実装してHIRを探索していくという、そろそろ見慣れてきたVisitorを使ったパターンの1つになっている。`ItemLikeVisitor`のコードは転記しないが、渡した`roots`のベクタにアイテムを集めていく処理がその実装から見て取れる。

```rust:rustc_mir/src/monomorphize/collector.rs
// Find all non-generic items by walking the HIR. These items serve as roots to
// start monomorphizing from.
fn collect_roots(tcx: TyCtxt<'_>, mode: MonoItemCollectionMode) -> Vec<MonoItem<'_>> {
    debug!("collecting roots");
    let mut roots = Vec::new();

    {
        let entry_fn = tcx.entry_fn(LOCAL_CRATE);

        debug!("collect_roots: entry_fn = {:?}", entry_fn);

        let mut visitor = RootCollector { tcx, mode, entry_fn, output: &mut roots };

        tcx.hir().krate().visit_all_item_likes(&mut visitor);

        visitor.push_extra_entry_roots();
    }

    // We can only codegen items that are instantiable - items all of
    // whose predicates hold. Luckily, items that aren't instantiable
    // can't actually be used, so we can just skip codegenning them.
    roots
        .into_iter()
        .filter_map(|root| root.node.is_instantiable(tcx).then_some(root.node))
        .collect()
}
```

続いてneighborを収集する`collect_items_rec()`を見てみる。recはおそらくrecursiveのことで、rootを起点にneighborを探し、見つかったneighborを起点にしてさらにその先のneighborを探す、という感じで再帰的に進んでいく。アイテムが関数だった場合、探索する処理は`collect_neighbours()`へと続いていく。（余談だが、このあたりのコードはneighborとneighbourが思い切り混在していて驚いた。）

```rust:rustc_mir/src/monomorphize/collector.rs
// Collect all monomorphized items reachable from `starting_point`
fn collect_items_rec<'tcx>(
    tcx: TyCtxt<'tcx>,
    starting_point: Spanned<MonoItem<'tcx>>,
    visited: MTRef<'_, MTLock<FxHashSet<MonoItem<'tcx>>>>,
    recursion_depths: &mut DefIdMap<usize>,
    inlining_map: MTRef<'_, MTLock<InliningMap<'tcx>>>,
) {
    if !visited.lock_mut().insert(starting_point.node) {
        // We've been here already, no need to search again.
        return;
    }
    debug!("BEGIN collect_items_rec({})", starting_point.node);

    let mut neighbors = Vec::new();
    let recursion_depth_reset;

    match starting_point.node {
...
        MonoItem::Fn(instance) => {
            // Sanity check whether this ended up being collected accidentally
            debug_assert!(should_codegen_locally(tcx, &instance));

            // Keep track of the monomorphization recursion depth
            recursion_depth_reset =
                Some(check_recursion_limit(tcx, instance, starting_point.span, recursion_depths));
            check_type_length_limit(tcx, instance);

            rustc_data_structures::stack::ensure_sufficient_stack(|| {
                collect_neighbours(tcx, instance, &mut neighbors);
            });
        }
...
    }

    record_accesses(tcx, starting_point.node, neighbors.iter().map(|i| &i.node), inlining_map);

    for neighbour in neighbors {
        collect_items_rec(tcx, neighbour, visited, recursion_depths, inlining_map);
    }
...
}
```

`collect_neighbours()`はこのようになっている。rootの収集にはHIRを使うがneighborの収集はMIRで行われる。しかしやり方としては同じようにVisitorパターンで、`MirNeighborCollector`に対して`MirVisitor`を実装して探索、収集していく。

```rust:rustc_mir/src/monomorphize/collector.rs
/// Scans the MIR in order to find function calls, closures, and drop-glue.
fn collect_neighbours<'tcx>(
    tcx: TyCtxt<'tcx>,
    instance: Instance<'tcx>,
    output: &mut Vec<Spanned<MonoItem<'tcx>>>,
) {
    debug!("collect_neighbours: {:?}", instance.def_id());
    let body = tcx.instance_mir(instance.def);

    MirNeighborCollector { tcx, body: &body, output, instance }.visit_body(&body);
}
```

##### Partitioning

さて、話を`collect_and_partition_mono_items()`まで戻し、今度は`partition()`を見ていこう。こちらも[モジュールレベルのドキュメント](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/monomorphize/partitioning/index.html)に多くの説明がある。

上で少し触れたが、収集したアイテムはコード生成ユニット（Codegen Unit: **CGU**）という単位に分割される。この分割は差分コンパイルを効率化するため重要な処理となる。このあたりはRust Blogの[Incremental Compilationの記事](https://blog.rust-lang.org/2016/09/08/incremental.html)も参考になるかもしれない。

差分コンパイルの性能向上のためにはCGUを細かくしていきたいが、コード生成はCGUごとに行うため、細かくしすぎると最適化が十分にできず、生成されたバイナリの性能が悪くなるというジレンマを抱えている。経験に基づき、このような分割を行っているようだ。

- まずはソースレベルのモジュールで分割する。その上でさらに2つに分割する。
  - ジェネリックでないアイテム。これを**stable**なコードと呼ぶ。
  - 単一化されたアイテム。これを**volatile**なコードと呼ぶ。

主な分割処理は`place_root_mono_items()`で行われている。

```rust:rustc_mir/src/monomorphize/partitioning/mod.rs
pub fn partition<'tcx>(
    tcx: TyCtxt<'tcx>,
    mono_items: &mut dyn Iterator<Item = MonoItem<'tcx>>,
    max_cgu_count: usize,
    inlining_map: &InliningMap<'tcx>,
) -> Vec<CodegenUnit<'tcx>> {
    let _prof_timer = tcx.prof.generic_activity("cgu_partitioning");

    let mut partitioner = get_partitioner(tcx);
    let cx = &PartitioningCx { tcx, target_cgu_count: max_cgu_count, inlining_map };
    // In the first step, we place all regular monomorphizations into their
    // respective 'home' codegen unit. Regular monomorphizations are all
    // functions and statics defined in the local crate.
    let mut initial_partitioning = {
        let _prof_timer = tcx.prof.generic_activity("cgu_partitioning_place_roots");
        partitioner.place_root_mono_items(cx, mono_items)
    };
...
}
```

`place_root_mono_items()`ではアイテムごとに`codegen_unit_name`を定義し、その名前をもとにアイテムを振り分けている。名前を生成している`compute_codegen_unit_name()`には`is_volatile`という変数が与えられていることに注目しよう。`is_volatile`は`is_generic_fn()`でジェネリックな関数かどうかを確認しているようなので、上で述べた2つの分割がなされていることが分かる。

```rust:rustc_mir/src/monomorphize/partitioning/default.rs
impl<'tcx> Partitioner<'tcx> for DefaultPartitioning {
    fn place_root_mono_items(
        &mut self,
        cx: &PartitioningCx<'_, 'tcx>,
        mono_items: &mut dyn Iterator<Item = MonoItem<'tcx>>,
    ) -> PreInliningPartitioning<'tcx> {
        let mut roots = FxHashSet::default();
        let mut codegen_units = FxHashMap::default();
...
        for mono_item in mono_items {
...
            let characteristic_def_id = characteristic_def_id_of_mono_item(cx.tcx, mono_item);
            let is_volatile = is_incremental_build && mono_item.is_generic_fn();

            let codegen_unit_name = match characteristic_def_id {
                Some(def_id) => compute_codegen_unit_name(
                    cx.tcx,
                    cgu_name_builder,
                    def_id,
                    is_volatile,
                    cgu_name_cache,
                ),
                None => fallback_cgu_name(cgu_name_builder),
            };

            let codegen_unit = codegen_units
                .entry(codegen_unit_name)
                .or_insert_with(|| CodegenUnit::new(codegen_unit_name));
...
            codegen_unit.items_mut().insert(mono_item, (linkage, visibility));
            roots.insert(mono_item);
        }
...
        PreInliningPartitioning {
            codegen_units: codegen_units
                .into_iter()
                .map(|(_, codegen_unit)| codegen_unit)
                .collect(),
            roots,
            internalization_candidates,
        }
    }
...
}
```

root/neighborの関係とstable/volatileの関係は似ている気もするが、ロジックとしては特に共通化されているわけではないようだ。

### Lowering MIR

生成したCGUをLLVM IRに変換していく。上でも出てきた`codegen_crate()`の続きを見てみよう。`compile_codegen_unit()`という、CGUごとにforで回しているメソッドが中心的な処理に続いている。

ちなみに、Rustのバックエンドは主にLLVMが使用されるが、最近本格的に[Cranelift](https://github.com/bytecodealliance/wasmtime/tree/main/cranelift)が使えるようになってきているようだ。そのため`backend`はジェネリクスとなっているが、ここではLLVMを前提として見ていく。

```rust:rustc_codegen_ssa/src/base.rs
pub fn codegen_crate<B: ExtraBackendMethods>(
    backend: B,
    tcx: TyCtxt<'tcx>,
    metadata: EncodedMetadata,
    need_metadata_module: bool,
) -> OngoingCodegen<B> {
...
    for (i, cgu) in codegen_units.iter().enumerate() {
...
        match cgu_reuse {
            CguReuse::No => {
                let (module, cost) =
                    if let Some(cgu) = pre_compiled_cgus.as_mut().unwrap().remove(&i) {
                        cgu
                    } else {
                        let start_time = Instant::now();
                        let module = backend.compile_codegen_unit(tcx, cgu.name());
                        let mut time = total_codegen_time.lock();
                        *time += start_time.elapsed();
                        module
                    };
                submit_codegened_module_to_llvm(
                    &backend,
                    &ongoing_codegen.coordinator_send,
                    module,
                    cost,
                );
                false
            }
...
        };
    }
...
}
```

`compile_codegen_unit()`では同関数内で定義された`module_codegen()`を実行しており、ここでCGUのさらに中のアイテムについてforで回している。`predefine()`と`define()`の2つループがあるが、ざっくり言うと`predefine()`はアイテムの枠組み（関数で言えばシグネチャ）のみを生成し、その後`define()`で中身を埋めていくような流れになっているようだ。

```rust:rustc_codegen_llvm/src/base.rs
pub fn compile_codegen_unit(
    tcx: TyCtxt<'tcx>,
    cgu_name: Symbol,
) -> (ModuleCodegen<ModuleLlvm>, u64) {
...
    let dep_node = tcx.codegen_unit(cgu_name).codegen_dep_node(tcx);
    let (module, _) =
        tcx.dep_graph.with_task(dep_node, tcx, cgu_name, module_codegen, dep_graph::hash_result);
...
    fn module_codegen(tcx: TyCtxt<'_>, cgu_name: Symbol) -> ModuleCodegen<ModuleLlvm> {
        let cgu = tcx.codegen_unit(cgu_name);
...
        // Instantiate monomorphizations without filling out definitions yet...
        let llvm_module = ModuleLlvm::new(tcx, &cgu_name.as_str());
        {
            let cx = CodegenCx::new(tcx, cgu, &llvm_module);
            let mono_items = cx.codegen_unit.items_in_deterministic_order(cx.tcx);
            for &(mono_item, (linkage, visibility)) in &mono_items {
                mono_item.predefine::<Builder<'_, '_, '_>>(&cx, linkage, visibility);
            }

            // ... and now that we have everything pre-defined, fill out those definitions.
            for &(mono_item, _) in &mono_items {
                mono_item.define::<Builder<'_, '_, '_>>(&cx);
            }
...
        ModuleCodegen {
            name: cgu_name.to_string(),
            module_llvm: llvm_module,
            kind: ModuleKind::Regular,
        }
    }

    (module, cost)
}
```

`define()`は、アイテムが関数であれば`codegen_instance()`へと続き、

```rust:rustc_codegen_ssa/src/mono_item.rs
impl<'a, 'tcx: 'a> MonoItemExt<'a, 'tcx> for MonoItem<'tcx> {
    fn define<Bx: BuilderMethods<'a, 'tcx>>(&self, cx: &'a Bx::CodegenCx) {
...
        match *self {
...
            MonoItem::Fn(instance) => {
                base::codegen_instance::<Bx>(&cx, instance);
            }
        }
...
    }
...
}
```

そのまま`codegen_mir()`へと流れていく。

```rust:rustc_codegen_ssa/src/base.rs
pub fn codegen_instance<'a, 'tcx: 'a, Bx: BuilderMethods<'a, 'tcx>>(
    cx: &'a Bx::CodegenCx,
    instance: Instance<'tcx>,
) {
...
    mir::codegen_mir::<Bx>(cx, instance);
}
```

[以前見た](https://qiita.com/0yoyoyo/items/752073b3b1c7e76bebb2)ように、MIRにおいて関数の内部は複数の基本ブロックで構成されている。LLVM IRも同じように基本ブロックで構成されており、ガイドによるとMIRの基本ブロックがそのままLLVMの基本ブロックにマッピングされるとのこと。流れとしては先ほどのアイテムの場合と似ていて、まずは`build_sibling_block()`（の先で呼ばれる`new_block()`）で基本ブロックの枠組みを生成し、その後`codegen_block()`から続く処理で中身を埋めていくようだ。

```rust:rustc_codegen_ssa/src/mir/mod.rs
pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
    cx: &'a Bx::CodegenCx,
    instance: Instance<'tcx>,
) {
...
    let mir = cx.tcx().instance_mir(instance.def);
...
    let block_bxs: IndexVec<mir::BasicBlock, Bx::BasicBlock> = mir
        .basic_blocks()
        .indices()
        .map(|bb| {
            if bb == mir::START_BLOCK && !reentrant_start_block {
                bx.llbb()
            } else {
                bx.build_sibling_block(&format!("{:?}", bb)).llbb()
            }
        })
        .collect();
...
    let mut fx = FunctionCx {
        instance,
        mir,
        llfn,
        fn_abi,
        cx,
        personality_slot: None,
        blocks: block_bxs,
        unreachable_block: None,
        cleanup_kinds,
        landing_pads,
        funclets,
        locals: IndexVec::new(),
        debug_context,
        per_local_var_debug_info: None,
        caller_location: None,
    };
...
    let rpo = traversal::reverse_postorder(&mir);
...
    // Codegen the body of each block using reverse postorder
    for (bb, _) in rpo {
        visited.insert(bb.index());
        fx.codegen_block(bb);
    }
...
}
```

ここで、`new_block()`も`codegen_block()`も、少し追っていくとLLVMのAPIにつながっていることが分かる。LLVMについては全く詳しくないのだが、RustコンパイラはLLVM IRを直接テキストで出力するのではなく、APIを使って出力しているということなのだろう。（それが普通なのか判断はできないが、大きいプロジェクトであればそのほうが安全な気はする。）

APIの実際の動作はさすがに調べられていないが、試しに一例として`codegen_block()`からLLVM APIに行き着くまでを見てみよう。`codegen_block()`は基本ブロックの構成通り、大きくstatementの処理とterminatorの処理に分けられる。

```rust:rustc_codegen_ssa/src/mir/block.rs
impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
    pub fn codegen_block(&mut self, bb: mir::BasicBlock) {
        let mut bx = self.build_block(bb);
        let mir = self.mir;
        let data = &mir[bb];

        debug!("codegen_block({:?}={:?})", bb, data);

        for statement in &data.statements {
            bx = self.codegen_statement(bx, statement);
        }

        self.codegen_terminator(bx, bb, data.terminator());
    }
...
}
```

terminatorの処理として`codegen_terminator()`を見てみる。種別が`Goto`の場合は`funclet_br()`へと続いている。brは分岐（branch）のbrだろうか。

```rust:rustc_codegen_ssa/src/mir/block.rs
impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
...
    fn codegen_terminator(
        &mut self,
        mut bx: Bx,
        bb: mir::BasicBlock,
        terminator: &'tcx mir::Terminator<'tcx>,
    ) {
...
        match terminator.kind {
...
            mir::TerminatorKind::Goto { target } => {
                if bb == target {
...
                    bx.sideeffect(true);
                } else {
                    helper.maybe_sideeffect(self.mir, &mut bx, &[target]);
                }
                helper.funclet_br(self, &mut bx, target);
            }
...
        }
    }
...
}
```

少し分岐しているが、ここでは`BuilderMethods`の`br()`を呼んでいる方を追っていこう。

```rust:rustc_codegen_ssa/src/mir/block.rs
impl<'a, 'tcx> TerminatorCodegenHelper<'tcx> {
...
    fn funclet_br<Bx: BuilderMethods<'a, 'tcx>>(
        &self,
        fx: &mut FunctionCx<'a, 'tcx, Bx>,
        bx: &mut Bx,
        target: mir::BasicBlock,
    ) {
        let (lltarget, is_cleanupret) = self.lltarget(fx, target);
        if is_cleanupret {
            // micro-optimization: generate a `ret` rather than a jump
            // to a trampoline.
            bx.cleanup_ret(self.funclet(fx).unwrap(), Some(lltarget));
        } else {
            bx.br(lltarget);
        }
    }
...
}
```

`br()`は`LLVMBuildBr()`という関数のラッパーになっていることが分かる。

```rust:rustc_codegen_llvm/src/builder.rs
impl BuilderMethods<'a, 'tcx> for Builder<'a, 'll, 'tcx> {
...
    fn br(&mut self, dest: &'ll BasicBlock) {
        unsafe {
            llvm::LLVMBuildBr(self.llbuilder, dest);
        }
    }
...
}
```

このような`LLVMxxx()`という関数は他にもかなりたくさんあり、主に以下のファイルでインポートしているようだ。

```rust:rustc_codegen_llvm/src/llvm/ffi.rs
extern "C" {
...
    pub fn LLVMBuildBr(B: &Builder<'a>, Dest: &'a BasicBlock) -> &'a Value;
...
}
```

これらの関数の本体は当然LLVMに存在している。LLVMはビルド後であればrust/src/llvm-project/llvmにダウンロードされている。また、場合によってはrust/compiler/rustc_llvm/llvm-wrapperに定義されたRust用のラッパーを介して呼び出しているものもあるようだ。

最後がLLVMのAPIなので少しイメージが湧きづらいところもあるが、これでLLVM IRが生成されたはずだ。機械語の生成はLLVMが行うため、Rustコンパイラの仕事としてはほぼ完了といってもいいのではないだろうか。


### その他

他にもガイドには**Miri**（MIR Interpreter）や**PGO**（profile-guided optimization）の説明なども記載されている。また、ガイドには直接的な記載はないようだが、LLVMが生成した機械語を実行可能なバイナリとして構築するために、リンカを呼び出す処理も最後にあるはずだ。リンカの入り口だけ見てみよう。

コンパイラの入り口である`run_compiler()`まで戻る。上記のコード生成を行っている`ongoing_codegen()`の直後にリンカの処理が実行されている。

```rust:rustc_driver/src/lib.rs
// Parse args and run the compiler. This is the primary entry point for rustc.
// The FileLoader provides a way to load files from sources other than the file system.
fn run_compiler(
    at_args: &[String],
    callbacks: &mut (dyn Callbacks + Send),
    file_loader: Option<Box<dyn FileLoader + Send + Sync>>,
    emitter: Option<Box<dyn Write + Send>>,
    make_codegen_backend: Option<
        Box<dyn FnOnce(&config::Options) -> Box<dyn CodegenBackend> + Send>,
    >,
) -> interface::Result<()> {
...
    interface::run_compiler(config, |compiler| {
...
        let linker = compiler.enter(|queries| {
...
            queries.ongoing_codegen()?;
...
            let linker = queries.linker()?;
            Ok(Some(linker))
        })?;

        if let Some(linker) = linker {
            let _timer = sess.timer("link");
            linker.link()?
        }
...
        Ok(())
    })
}
```

この`link()`を追っていくと、`rustc_codegen_ssa::back::link::link_binary`に行き着くようだ。このあたりを読んでいけばリンカの処理も分かりそうだ。

```rust:rustc_codegen_ssa/src/back/link.rs
/// Performs the linkage portion of the compilation phase. This will generate all
/// of the requested outputs for this compilation session.
pub fn link_binary<'a, B: ArchiveBuilder<'a>>(
    sess: &'a Session,
    codegen_results: &CodegenResults,
    outputs: &OutputFilenames,
    crate_name: &str,
    target_cpu: &str,
) {
...
}
```


# おわりに

いろいろ飛ばしまくりですが、なんとか最後まで読んでいくことができました。ずるずると時間かかりすぎですが、これで一応読了となります。さすがRustの本家コンパイラなだけあって、いろいろなテクニックが詰まっていて勉強になりました。と同時に、理論的なところは全然ついていけず、もっと教科書読んだりして勉強しなければとも思いました。これからも理論的な部分を補強しつつ、少しずつコンパイラの理解を深めていきたいです。

最後に、まとまりなく長く続いてしまった記事を読んで頂き、ありがとうございました！