Incremental compilation

[aturon]

Point of contact

@nikomatsakis @michaelwoerister

Overview

The goal of the project is to allow the compiler to reuse results from previous compilations. The overall approach is that we dynamically track what data it has accessed to form a dependency graph. You can find more details on the current approach in RFC 1298 -- however, we are also contemplating an architecture shift that has yet to be written up in RFC form. The best notes, perhaps, can be found in the etherpad from the Paris 2017 design sprint.

The newer approach

The critical change in the new design is to be more reluctant to invalidate. Instead of eagerly invalidating everything that might have changed, we invalidate things when we see that a direct input as changed, and this invalidation propagates through the graph. This can result in more re-use, because we may have a node whose inputs have changed but which, when executed, still recomputes the same value (this could happen if, for example, it does not depend on the particular part of the input which changed, but only on other parts).

This algorithm integrates with the "on-demand" processing mechanism that we are phasing in. To describe the algorithm, we will use a series of three colors on the dependency graph: grey, red, and green. Grey is the initial color, and indicates that the node was loaded from a previous session and may or may have a valid value associated with it. Execution happens by a series of queries, which request values (e.g., "compute the TypeckTables for def-id D"). If we have a saved value for a query, but the node for that value is still colored grey, then we must first validate the value. This is done by checking the color of our predecessors in the dependency graph (i.e., the values which were read when computing the saved value). If they are grey, then we first demand the value. This will process the value recursively and ultimately leave it one of two colors:

• Red, meaning that the value has changed in this compilation session.
• Green, meaning that the previous value is still valid.

In both cases, we can now obtain the correct value for this particular session (which may or may not have been recomputed). If all inputs to our task come back as Green, then our saved value is still valid and we can re-use it (and color ourselves Green). If at any point we find that any of our inputs come back as red, then we can know that we have to recompute the value we are looking for (e.g., "compute the TypeckTables for def-id D"). We do this by running its "on-demand" task. Once the task completes, we take the new value and compare it against our saved value: it is possible, after all, that the inputs have changed but in a way that doesn't affect this particular result. If the result is the same as the saved value, we can color ourselves Green (even though we had red inputs), but otherwise we have to color ourselves as red -- which will cause those that used us as an input to be recomputed.

Scenarios

The following issues represent "scenarios that we want to work". In some cases, these issues will contain notes on the things that block them from "working" to our satisfaction yet.

• modifying private method in another crate's impl should not require users of public methods to recompile

Status

We are currently in the "beta period" for the current code. In particular, we are now able -- within a single crate -- to skip the translation into LLVM IR and the optimization phases by re-using object code. There are currently several major goals for moving past this point. Each is listed below, along with issues that track major milestones in that direction:

• Prep work for red-green algorithm: The first task here is primarily transitioning into on-demand compilation:
  • Tracking issue for "Red/Green" Dependency Tracking rust#42293 -- general tracking issue
  • [incremental] remove unwanted DepTrackingMap methods rust#40614: better encapsulate DepTrackingMap
  • migrate all "incremental tasks" to "on-demand queries" rust#40746: Convert with_task() and in_task() calls into queries
  • stricter task isolation for incremental compilation tasks rust#40304: isolate tasks more reliably using type system
  • dynamically check dep-graph write patterns rust#40305: prevent dangerous read-write patterns on dep-tracking-maps
  • refactor used_mut_nodes result rust#42384: remove the used_mut_nodes set
  • refactor lint handling to be more "eager" rust#42511: refactor lints
  • capture diagnostic output in queries rust#42513: integrate diagnostics and query system
• Improving our cross-crate dependency tracking:
  • revise metadata hashing to hash the contents of the metadata, not its input dependencies rust#38114: hash metadata content not inputs
  • [incremental] don't use NodeId in the HIR, but something local to an item rust#40303: adopt local node-ids
• Improving memory usage:
  • change internalize_symbols to work per-CGU rust#41707: change how internalize symbols work to facilitate pipelining
  • trans/LLVM: Don't keep all LLVM modules in memory at the same time rust#39280: pipeline translation and LLVM optimization to reduce memory usage
    • has mentoring instructions
• Other bugfixes:
  • codegen-units ruins debug symbols rust#39160: debug info and codegen units do not place nice
  • fix perf measurements for incremental test cases rust#42535: fix perf measurement infrastructure for incremental

[vitiral]

You should probably strikethrough rust-lang/rust#40304 as you've closed it in favor of rust-lang/rust#40746

edit: rust-lang/rust#42535 is also done, so ✔️

[e-oz]

We are currently in the "beta period"

Please restore ability to use incremental compilation in beta branch of Rust.

[steveklabnik]

@e-oz beta is like a release candidate for the final release; as such, beta follows the same rules as stable.

[ErichDonGubler]

Looks like all unchecked items should be checked now?

[michaelwoerister]

Thanks, @ErichDonGubler. I checked all the boxes.

[ErichDonGubler]

@michaelwoerister: Is there anything left that's actionable in this issue, if everything is checked now? What's left to do?

[michaelwoerister]

I'll leave it to @aturon to decide what to do with this issue now that 2017 is over.