インクリメンタルコンパイル

インクリメンタルコンパイルの仕組みは、本質的にはクエリシステム全体に対する驚くほど単純な拡張です。まず、実際のものを少し単純化した変種、すなわち「基本アルゴリズム」について説明し、その後で考えられる改善点をいくつか説明します。

基本アルゴリズム

基本アルゴリズムは赤緑アルゴリズム¹と呼ばれます。大まかな考え方は、コンパイラを実行するたびに、実行したすべてのクエリの結果と クエリDAGを保存するというものです。 クエリDAGは、どのクエリがどの他のクエリを実行したかを索引付けするDAGです。たとえば、Q1を計算するためにQ2を計算する必要があった場合、クエリQ1から別のクエリQ2へのエッジが存在します（クエリは自分自身に依存できないため、これは一般的なグラフではなくDAGになります）。

NOTE: クエリとは単にクエリの定義のことだと考えるかもしれません。関数のように呼び出すことができ、キャッシュされた結果を返すか、実際にコードを実行するものです。

クエリをそのように考える場合、以下の文章ではクエリに色があると言われることを知っておくとよいでしょう。ただし、ここでのクエリという語は、特定の入力に対するクエリのある呼び出しも指していることに注意してください。後で読むように、クエリはその引数に基づいてフィンガープリント化されます。ある引数を渡したときにはクエリの結果が変わって赤に色付けされる一方で、別の引数では同じままであり、そのため緑になることがあります。

要するに、ここでのクエリという語は、単にクエリの定義を意味するためだけに使われているのではなく、与えられた引数を持つそのクエリの特定のインスタンスも指しています。

次回コンパイラを実行するときには、クエリを再実行しないようにするために、これらのクエリ結果を再利用できる場合があります。これは、すべてのクエリに色を割り当てることで行います。

クエリが赤に色付けされている場合、それはこのコンパイル中の結果が前回のコンパイルから変化したことを意味します。
クエリが緑に色付けされている場合、それはその結果が前回のコンパイルと同じであることを意味します。

ここには2つの重要な洞察があります。

第一に、クエリQへのすべての入力が緑に色付けされている場合、クエリQは前回と同じ値を必ず返すため、再実行する必要はありません（そうでなければコンパイラは決定的ではありません）。
第二に、クエリへの入力の一部が変化したとしても、そのクエリが前回のコンパイルとなお同じ結果を生成する場合があります。特に、クエリは入力の一部しか使用しないことがあります。
- したがって、クエリを実行した後は、それが前回と同じ結果を生成したかどうかを常に確認します。もしそうであれば、 そのクエリを緑としてマークできるため、依存するクエリの再実行を回避できます。

try-mark-greenアルゴリズム

インクリメンタルコンパイルの中核には、“try-mark-green“と呼ばれるアルゴリズムがあります。これは、与えられたクエリQ（まだ実行されていてはなりません）の色を判定する役割を持ちます。Qに赤の入力がある場合、 Qの色を判定するには、その出力を比較できるようにQを再実行する必要があるかもしれません。しかし、Qのすべての入力が緑であれば、Qを再実行したりその値をまったく調べたりせずに、Qは緑でなければならないと結論できます。コンパイラでは、これにより不要なときにディスクから結果をデシリアライズすることを回避でき、実際には結果のシリアライズも時にはスキップできるようになります（下記の改良のセクションを参照）。

Try-mark-greenは次のように動作します。

まず、クエリQが前回のコンパイル中に実行されたかどうかを確認します。
- 実行されていない場合は、通常どおりクエリを再実行し、その色を赤に割り当てるだけです。
実行されていた場合は、Qの「依存クエリ」をロードします。
保存された結果がある場合は、クエリDAGからreads(Q)ベクターをロードします。“reads“は、Qが実行中に実行したクエリの集合です。
- reads(Q)内の各クエリRについて、try-mark-greenを使用して Rの色を再帰的に要求します。
  - 注: reads(Q)内の各ノードを、元のコンパイルで出現したのと同じ順序で訪問することが重要です。詳しくは下記のクエリDAGに関するセクションを参照してください。
  - reads(Q)内のノードのいずれかが最終的に赤に色付けされた場合、 Qはdirtyです。
    - Qを再実行し、その結果のハッシュを前回のコンパイルでの結果のハッシュと比較します。
    - ハッシュが変化していなければ、Qを緑としてマークして戻ることができます。
  - そうでない場合、reads(Q)内のノードはすべて****緑でなければなりません。その場合、Qを緑に色付けして戻ることができます。

クエリDAG

クエリDAGのコードは compiler/rustc_middle/src/dep_graphに格納されています。DAGの構築は、クエリ実行をインストルメントすることで行われます。

重要な点の1つは、クエリDAGが順序も追跡するということです。つまり、各クエリQについて、Qが読み取るクエリを追跡するだけでなく、それらが読み取られた順序も追跡します。これにより、try-mark-greenはそれらのクエリを同じ順序でたどり直すことができます。これは重要です。なぜなら、あるサブクエリが赤として返ってくると、Qが以前と同じ経路を進み続けるかどうかをもはや確信できないからです。つまり、次のようなクエリを想像してください。

fn main_query(tcx) {
    if tcx.subquery1() {
        tcx.subquery2()
    } else {
        tcx.subquery3()
    }
}

ここで、最初のコンパイルではmain_queryがまずsubquery1を実行し、これがtrueを返すと想像してください。その場合、main_queryが次に実行するクエリはsubquery2であり、subquery3はまったく実行されません。

しかし、次のコンパイルでは、入力が変化してsubquery1がfalseを返すようになったと想像してください。この場合、subquery2は決して実行されません。ところが、try-mark-greenがreads(main_query)を順不同で訪問した場合、subquery1より先にsubquery2を訪問し、その結果それを実行してしまう可能性があります。これは、コンパイラ内でICEやその他の問題につながることがあります。

基本アルゴリズムの改善

基本アルゴリズムの説明では、コンパイルの終了時に、実行されたすべてのクエリの結果を保存すると述べました。実際には、これはかなり無駄になり得ます。それらの結果の多くは再計算が非常に安価であり、それらをシリアライズおよびデシリアライズしても特に得にはなりません。実際には、実行したすべてのサブクエリのハッシュを保存します。そして、選択された場合には、結果も併せて保存します。

これが、インクリメンタルアルゴリズムが、ノードの値を必要としないことが多いノードの色の計算と、ノードの結果の計算を分離している理由です。結果の計算は、次のような単純なアルゴリズムによって行われます。

Qの保存済み結果が利用可能かどうかを確認します。利用可能であれば、Qの色を計算します。 Qが緑であれば、保存済み結果をデシリアライズして返します。
そうでない場合は、Qを実行します。
- その後、結果のハッシュを比較し、変化していなければQを緑として色付けできます。

リソース

初期設計ドキュメントはこちらにあり、メモ化の詳細を掘り下げ、このシステムについてのより高水準な概要と動機を提供しています。

脚注

私は長い間、これをSalsaアルゴリズムに改名したいと思っていましたが、定着することはありませんでした。-@nikomatsakis ↩

Keyboard shortcuts