Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

コンパイラの概要

この章では、プログラムをコンパイルする全体的なプロセス、つまりすべてがどのように組み合わさっているかについて説明します。

Rust コンパイラは 2 つの点で特別です。ほかのコンパイラが行わないことを コードに対して行う点（例: borrow checking）と、通常とは異なる実装上の選択が 多い点（例: queries）です。 この章ではこれらについて順に説明し、ガイドの残りの部分では、 個々の構成要素をより詳しく見ていきます。

コンパイラがコードに対して行うこと

まず、コンパイラがコードに対して行うことを見ていきましょう。 現時点では、必要な場合を除き、コンパイラがこれらのステップをどのように実装しているかには触れません。

呼び出し

コンパイルは、ユーザーが Rust ソースプログラムをテキストで記述し、それに対して rustc コンパイラを呼び出すところから始まります。 コンパイラが実行する必要のある作業は、コマンドラインオプションによって定義されます。 たとえば、nightly features（-Z flags）を有効にしたり、check のみのビルドを実行したり、実行可能な機械語コードではなく LLVM Intermediate Representation（LLVM-IR）を出力したりすることができます。 rustc 実行ファイルの呼び出しは、cargo の使用を通じて間接的に行われる場合があります。

コマンドライン引数の解析は [rustc_driver] で行われます。 このクレートは、ユーザーが要求したコンパイル設定を定義し、それを [rustc_interface::Config] としてコンパイルプロセスの残りの部分に渡します。

字句解析と構文解析

生の Rust ソーステキストは、[rustc_lexer] にある低レベルの lexer によって解析されます。 この段階で、ソーステキストは tokens と呼ばれる 原子的なソースコード単位のストリームに変換されます。 lexer は Unicode 文字エンコーディングをサポートしています。

トークンストリームは、コンパイルプロセスの次の段階に備えるために、 [rustc_parse] にあるより高レベルの lexer を通過します。 この段階では、[Lexer] struct が一連の検証を実行し、 文字列をインターン化されたシンボルに変換するために使用されます（interning については後述します）。 [String interning] は、個別の文字列値ごとに不変のコピーを 1 つだけ保存する方法です。

lexer は小さなインターフェイスを持ち、rustc の診断 インフラストラクチャには直接依存しません。 代わりに、診断をプレーンなデータとして提供し、それらは [rustc_parse::lexer] で実際の診断として出力されます。 lexer は、IDE と手続き型マクロ （“proc-macros” と呼ばれることもあります）の両方に対して、完全な忠実度の情報を保持します。

parser は、[lexer からのトークンストリームを抽象構文木 （AST）に変換します][parser]。 構文解析には、再帰下降（トップダウン）アプローチを使用します。 parser のクレートエントリポイントは、 [rustc_parse::parser::Parser] にある [Parser::parse_crate_mod][parse_crate_mod] および [Parser::parse_mod][parse_mod] メソッドです。 外部モジュール解析の エントリポイントは [rustc_expand::module::parse_external_mod][parse_external_mod] です。 また、macro-parser のエントリポイントは [Parser::parse_nonterminal][parse_nonterminal] です。

構文解析は、[bump]、 [check]、[eat]、[expect]、[look_ahead] を含む一連の [parser] ユーティリティメソッドを使用して実行されます。

構文解析は意味的な構成要素ごとに整理されています。 個別の parse_* メソッドは [rustc_parse][rustc_parse_parser_dir] ディレクトリ内にあります。 ソースファイル名は構成要素名に従います。 たとえば、parser には次のファイルがあります。

この命名方式は、多くのコンパイラ段階で使用されています。 構文解析、lowering、型 検査、[Typed High-level Intermediate Representation（THIR）][thir] の lowering、および [Mid-level Intermediate Representation（MIR）][mir] の構築ソースの各所で、同じ名前のファイルまたはディレクトリが見つかります。

マクロ展開、AST 検証、名前解決、および early linting も、 字句解析と構文解析の段階で行われます。

[rustc_ast::ast]::{[Crate], [Expr], [Pat], …} AST ノードは parser から返され、エラー処理には標準の [Diag] API が使用されます。 一般に Rust のコンパイラは、Rust の文法のスーパーセットを解析することで エラーからの回復を試みると同時に、エラー型も出力します。

AST lowering

次に、AST は [High-Level Intermediate Representation （HIR）][hir] に変換されます。これは、AST よりもコンパイラにとって扱いやすい表現です。 このプロセスは「lowering」と呼ばれ、ループや async fn のようなものに対して、多くの desugaring（短縮または省略された構文構成要素の展開と 形式化）を伴います。

その後、HIR を使用して、[type inference]（式の型を自動的に 検出するプロセス）、[trait solving]（trait への各参照に impl を対応付けるプロセス）、および [type checking] を行います。 型検査とは、ユーザーが記述した内容を表す HIR 内の型（[hir::Ty]）を、 コンパイラが使用する内部表現（[Ty<'tcx>]）へ変換するプロセスです。 型検査と呼ばれるのは、その情報が、プログラム内で使用される型の 型安全性、正しさ、および一貫性を検証するために使用されるためです。

MIR lowering

HIR はさらに MIR に lowering されます （[borrow checking] に使用されます）。これは、THIR（パターンと網羅性検査に使用される、さらに desugar された HIR）を構築し、それを MIR に変換することで行われます。

MIR は汎用的であり、それによって後続のコード生成とコンパイル速度が向上するため、 [MIR に対して多くの最適化を行います][mir-opt]。 一部の最適化は、LLVM-IR レベルよりも MIR レベルで行う方が簡単です。 たとえば LLVM は、 [simplify_try] MIR-opt が探すパターンを最適化できないようです。

Rust コードはコード生成中に monomorphized もされます。これは、 型パラメーターを具体的な型に置き換えたジェネリックコードのコピーをすべて作成することを意味します。 これを行うには、どの具体的な型に対してコードを生成するかのリストを収集する必要があります。 これは monomorphization collection と呼ばれ、MIR レベルで行われます。

コード生成

次に、単に コード生成 または codegen と呼ばれるものを開始します。 [コード生成段階][codegen] は、ソースの高レベル表現が 実行可能バイナリに変換される段階です。 rustc はコード生成に LLVM を使用するため、 最初のステップは MIR を LLVM-IR に変換することです。 ここで MIR が実際に monomorphize されます。 LLVM-IR は LLVM に渡され、LLVM はそれに対してさらに多くの 最適化を行い、追加の低レベル型とアノテーションが付加された、基本的にはアセンブリコードである機械語コード （例: ELF オブジェクトまたは WASM）を出力します。 その後、異なるライブラリやバイナリがリンクされ、最終的なバイナリが生成されます。 [trait solving]: traits/resolution.md [type checking]: hir-typeck/summary.md [type inference]: type-inference.md [bump]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_parse/parser/struct.Parser.html#method.bump [check]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_parse/parser/struct.Parser.html#method.check [Crate]: https://doc.rust-lang.org/beta/nightly-rustc/rustc_ast/ast/struct.Crate.html [diag]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_errors/struct.Diag.html [eat]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_parse/parser/struct.Parser.html#method.eat [expect]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_parse/parser/struct.Parser.html#method.expect [Expr]: https://doc.rust-lang.org/beta/nightly-rustc/rustc_ast/ast/struct.Expr.html [hir::Ty]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_hir/hir/struct.Ty.html [look_ahead]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_parse/parser/struct.Parser.html#method.look_ahead [Parser]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_parse/parser/struct.Parser.html [Pat]: https://doc.rust-lang.org/beta/nightly-rustc/rustc_ast/ast/struct.Pat.html [rustc_ast::ast]: https://doc.rust-lang.org/beta/nightly-rustc/rustc_ast/index.html [rustc_driver]: rustc-driver/intro.md [rustc_interface::Config]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_interface/interface/struct.Config.html [rustc_lexer]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_lexer/index.html [rustc_parse::lexer]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_parse/lexer/index.html [rustc_parse::parser::Parser]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_parse/parser/struct.Parser.html [rustc_parse]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_parse/index.html [simplify_try]: https://github.com/rust-lang/rust/pull/66282 [Lexer]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_parse/lexer/struct.Lexer.html [Ty<'tcx>]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/struct.Ty.html [borrow checking]: borrow-check.md [codegen]: backend/codegen.md [hir]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_hir/index.html [lex]: the-parser.md [mir-opt]: mir/optimizations.md [mir]: mir/index.md [parse_crate_mod]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_parse/parser/struct.Parser.html#method.parse_crate_mod [parse_external_mod]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_expand/module/fn.parse_external_mod.html [parse_mod]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_parse/parser/struct.Parser.html#method.parse_mod [parse_nonterminal]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_parse/parser/struct.Parser.html#method.parse_nonterminal [parser]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_parse/index.html [rustc_parse_parser_dir]: https://github.com/rust-lang/rust/tree/HEAD/compiler/rustc_parse/src/parser [String interning]: https://en.wikipedia.org/wiki/String_interning [thir]: ./thir.md

どのように行うのか

コンパイラがあなたのコードに対して何を行うのかを大まかに把握したところで、 次は、それらすべてを_どのように_行うのかを大まかに見ていきましょう。 コンパイラが満たし、最適化する必要のある制約や相反する目標は数多くあります。 たとえば、

  • コンパイル速度: プログラムのコンパイルはどれくらい速いか？ コンパイル時の解析をより多く、またはより良く行うと、多くの場合コンパイルは遅くなります。
    • また、インクリメンタルコンパイルをサポートしたいので、その点も考慮する必要があります。 ユーザーがプログラムを変更した場合に、どの作業をやり直す必要があり、 どの作業を再利用できるかを、どのように追跡できるでしょうか？
      • また、インクリメンタルキャッシュにあまり多くのものを保存することはできません。 ディスクから読み込むのに長い時間がかかり、ユーザーのシステム上で多くの 容量を占める可能性があるためです…
  • コンパイラのメモリ使用量: プログラムをコンパイルしている間、必要以上のメモリを使用したくありません。
  • プログラムの速度: コンパイルされたプログラムはどれくらい速いか？ コンパイル時の解析をより多く、またはより良く行うと、多くの場合コンパイラはより優れた最適化を行えます。
  • プログラムのサイズ: コンパイルされたバイナリはどれくらい大きいか？ 前の項目と似ています。
  • コンパイラのコンパイル速度: コンパイラをコンパイルするのにどれくらい時間がかかるか？ これはコントリビューターやコンパイラの保守に影響します。
  • 実装の複雑さ: コンパイラの構築は、人やグループが取り組める中でも最も難しい ことの 1 つであり、Rust はそれほど単純な言語ではありません。では、どのようにして コンパイラのコードベースを管理しやすくするのでしょうか？
  • コンパイラの正しさ: コンパイラが生成するバイナリは、入力プログラムが行うと 記述していることを実行するべきであり、絶えず起きている膨大な変更にもかかわらず、 そうし続けるべきです。
  • 統合: cargo、clippy、Miri など、さまざまな方法でコンパイラを使用する必要がある 他のツールが多数あり、それらをサポートしなければなりません。
  • コンパイラの安定性: コンパイラは stable チャンネルでクラッシュしたり、不格好に失敗したりするべきではありません。
  • Rust の安定性: コンパイラは、常に行われている実装への多くの変更にもかかわらず、 以前はコンパイルできていたプログラムを壊さないことで、Rust の安定性保証を尊重しなければなりません。
  • 他のツールの制限: rustc はバックエンドで LLVM を使用しており、LLVM には 活用できる強みがある一方で、回避策が必要な側面もあります。

したがって、このガイドの残りを読み進める際には、これらの点を念頭に置いてください。 これらは、私たちが下す判断にしばしば影響します。

中間表現

ほとんどのコンパイラと同様に、rustc は計算を容易にするためにいくつかの中間表現（IR）を使用します。 一般に、ソースコードを直接扱うのは非常に不便で、エラーが発生しやすいものです。 ソースコードは人間にとって扱いやすく、同時に曖昧さがないように設計されていますが、 たとえば型チェックのようなことを行うにはあまり便利ではありません。

代わりに、rustc を含むほとんどのコンパイラは、解析しやすい何らかの IR を ソースコードから構築します。 rustc にはいくつかの IR があり、それぞれ異なる目的に最適化されています:

  • トークンストリーム: レキサーはソースコードから直接トークンのストリームを生成します。 このトークンのストリームは、生のテキストよりもパーサーが扱いやすいものです。
  • 抽象構文木（AST）: 抽象構文木は、レキサーによって生成されたトークンのストリームから構築されます。 これは、ユーザーが書いたものをほぼそのまま表します。 これは、構文上の健全性チェック （例: ユーザーが型を書いた場所で型が期待されているかのチェック）を行うのに役立ちます。
  • 高水準 IR（HIR）: これは、一種の脱糖された AST です。 構文的にはユーザーが書いたものにまだ近いですが、省略されたライフタイムなどの暗黙的なものもいくつか含みます。 この IR は型チェックに適しています。
  • 型付き HIR（THIR）以前は High-level Abstract IR（HAIR）: これは HIR と MIR の中間表現です。 HIR に似ていますが、完全に型付けされており、 さらに少し脱糖されています（例: メソッド呼び出しや暗黙の参照外しが 完全に明示されます）。 その結果、HIR からよりも THIR から MIR に下げる方が容易です。
  • 中水準 IR（MIR）: この IR は基本的に制御フローグラフ（CFG）です。 CFG は、プログラムの基本ブロックと、それらの間で制御フローがどのように移動できるかを示す図の一種です。 同様に、MIR にも多数の基本ブロックがあり、 その中に単純な型付き文（例: 代入、単純な計算、 など）と、他の基本ブロックへの制御フローエッジ（例: 呼び出し、値の ドロップ）があります。 MIR は借用チェックや、 未初期化の値のチェックなど、その他の重要なデータフローベースのチェックに使用されます。 また、一連の最適化や定数評価（Miri 経由）にも使用されます。 MIR はまだジェネリックであるため、単相化後よりも ここで多くの解析を効率的に行うことができます。
  • LLVM-IR: これは LLVM コンパイラへのすべての入力の標準形式です。 LLVM-IR は、多数のアノテーションを備えた、一種の型付きアセンブリ言語です。 これは LLVM を使用するすべてのコンパイラで使われる標準形式です（例: clang C コンパイラも LLVM-IR を出力します）。 LLVM-IR は、他の コンパイラが出力しやすく、また LLVM がその上で多数の最適化を実行するのに十分な表現力を持つように設計されています。

もう 1 つ注意すべき点は、コンパイラ内の多くの値が インターン化 されることです。 これは、値を arena と呼ばれる特殊なアロケータに割り当てる、 性能とメモリの最適化です。 そして、arena に割り当てられた値への参照を受け渡します。 これにより、 同一の値（例: プログラム内の型）が一度だけ割り当てられるようにし、 ポインタを比較することで低コストに比較できるようになります。 中間表現の多くはインターン化されます。

クエリ

最初の大きな実装上の選択は、Rust がコンパイラで クエリ システムを使用していることです。 Rust コンパイラは、コードに対して順番に実行される一連のパスとして構成されて_いません_。 Rust コンパイラがこれを行うのは、 インクリメンタルコンパイルを可能にするためです。つまり、ユーザーが プログラムに変更を加えて再コンパイルした場合、新しいバイナリを出力するために できるだけ冗長な作業を少なくしたいのです。

rustc では、上記の主要なステップはすべて、互いに呼び出し合う多数のクエリとして構成されています。 たとえば、あるものの型を問い合わせるクエリや、 関数の最適化済み MIR を問い合わせるクエリがあります。 これらのクエリは互いに呼び出すことができ、すべてクエリシステムを通じて追跡されます。 クエリの結果はディスクにキャッシュされるため、コンパイラは前回のコンパイルからどのクエリ結果が 変わったかを判断し、それらだけをやり直すことができます。 これがインクリメンタルコンパイルの仕組みです。

原則として、クエリ化されたステップについては、上記の各処理を各アイテムごとに個別に行います。 たとえば、ある関数の HIR を取り、その HIR に対する LLVM-IR を クエリで問い合わせます。 これが最適化済み MIR の生成を駆動し、それが借用チェッカーを駆動し、それが MIR の生成を駆動する、という具合です。

…ただし、これは非常に過度に単純化した説明です。 実際には、一部のクエリは ディスクにキャッシュされず、またコンパイラの一部は、たとえコードがデッドコードであっても、 正当性のためにすべてのコードに対して実行される必要があります（例: 借用チェッカー）。たとえば、 現在、mir_borrowck クエリはクレートのすべての関数に対して最初に実行されます。 その後、コード生成バックエンドが collect_and_partition_mono_items クエリを呼び出します。このクエリはまず、到達可能なすべての関数について optimized_mir を再帰的に要求し、それが今度はその関数について mir_borrowck を実行してから コード生成ユニットを作成します。 この種の分割は、到達不能な関数であってもそのエラーが出力されることを保証するために、 維持される必要があります。

さらに、コンパイラはもともとクエリシステムを使用するように構築されたわけではありません。クエリ システムはコンパイラに後付けされたため、まだクエリ化されていない部分があります。 また、LLVM は私たちのコードではないため、これもクエリ化されていません。 最終的には前のセクションに列挙したすべてのステップをクエリ化する計画ですが、

2022年11月時点では、`HIR` から

LLVM-IR までのステップだけがクエリ化されています。 つまり、字句解析、構文解析、名前解決、マクロ 展開は、プログラム全体に対して一度に行われます。

ここでもう 1 つ触れておくべきことは、非常に重要な「型付けコンテキスト」である TyCtxt です。これは、すべての中心にある巨大な構造体です。 （この名前はほとんど歴史的なものだという点に注意してください。 これは、型理論における Γ や Δ の意味での「型付けコンテキスト」では_ありません_。 この名前が残っているのは、それがソースコード内の構造体の名前だからです。）すべての クエリは TyCtxt 型のメソッドとして定義され、メモリ内のクエリ キャッシュもそこに格納されます。 コード内には通常、型付けコンテキストへのハンドルである tcx という変数があります。 また、'tcx という 名前のライフタイムも目にするでしょう。これは、何かが TyCtxt のライフタイムに結び付いていることを意味します（通常、それはそこに格納またはインターン化されています）。

コンパイラ内のクエリの詳細については、クエリの章を参照してください。

ty::Ty

型は Rust において非常に重要であり、多くのコンパイラ解析の中核を成しています。 （コンパイラ内で）型（ユーザーの プログラム内の型）を表す主要な型は rustc_middle::ty::Ty です。 これは非常に重要なので、ty::Ty については丸ごと 1 章を 割いていますが、ここではひとまず、それが存在し、rustc が型を表現する方法であることだけを述べておきます！

また、rustc_middle::ty モジュールが、前述の TyCtxt 構造体を定義していることにも注意してください。

並列性

コンパイラの性能は、私たちが改善したいと考えている（そして常に取り組んでいる）問題です。 その一側面が、rustc 自体の並列化です。 現在、rustc のうちデフォルトで並列化されているのは、ただ1つの部分だけです: コード生成。

しかし、コンパイラのそれ以外の部分は、まだ並列化されていません。 これには多くの取り組みが費やされてきましたが、一般に難しい問題です。 現在のアプローチは、RefCell を Mutex に変えることです。つまり、スレッドセーフな内部可変性へ 切り替えます。 しかし、ロック競合、並行実行下でのクエリシステムの不変条件の維持、 そしてコードベースの複雑さについて、継続的な課題があります。 現在の作業は、bootstrap.toml で並列コンパイルを有効にすることで試せます。 まだ初期段階ですが、 すでに有望なパフォーマンス改善がいくつか見られています。

ブートストラップ

rustc 自体は Rust で書かれています。 では、コンパイラをどのようにコンパイルするのでしょうか？ より古いコンパイラを使って、より新しいコンパイラをコンパイルします。 これは ブートストラップ と呼ばれます。

ブートストラップには興味深い含意がたくさんあります。 たとえば、Rust の主要なユーザーの1つが Rust コンパイラであることを意味するため、私たちは 常に自分たちのソフトウェアをテストしています（「自分のドッグフードを食べる」）。

ブートストラップの詳細については、ガイドのブートストラップのセクションを参照してください。

参考資料