This article brought to you by LWN subscribers

Subscribers to LWN.net made this article — and everything that surrounds it — possible. If you appreciate our content, please buy a subscription and make the next set of articles possible.

The traditional structure of a compiler forms a pipeline — parsing, type-checking, optimization, and code-generation, usually in that order. But modern programming languages have requirements that are ill-suited to such a design. Increasingly, compilers are moving toward other designs in order to support incremental compilation and low-latency responses for uses like integration into IDEs. Rust has, for the last eight years, been pursuing a particularly unusual design; in that time compile times have substantially improved, but there's still more work to be done.

In a traditional compiler, normally each step of the pipeline needs to complete before the next is started. For example, optimization must complete before the compiler can begin emitting machine code. There are ways to improve this — working on translation units in parallel, caching some kinds of analysis, etc. — but, at a certain point, the architectures of the compilers themselves make it difficult to make the code support incremental compilation.

Language design can influence how much of a problem this is in practice. For example, while the GCC developers did look into making the compiler incremental, the fact that C defines each file as a stand-alone translation unit makes it easier to add incrementalism at the level of the build system. Many modern languages don't observe the same separation between files, however. In Rust, an entire crate is a single translation unit; cargo, Rust's build system, handles only recompiling changed crates, but adding incrementalism within a crate requires special support from the compiler.

So, in response to wishes for faster compile times, Rust has been exploring an alternative to the traditional structure of a compiler by switching to a query-based model: instead of having a fixed pipeline, the compiler has a set of queries for different properties of the program. Each query can either retrieve the answer from a persistent compilation database, or, if the answer has not yet been cached, calculate it from scratch by making other queries and combining their results. For example, the compiler uses the type_of() query to infer the types of local bindings. The query takes the ID of a local definition, and then calls other queries to determine whether it is an impl Trait type, what the abstract syntax tree of the definition is, what the types of the variables it refers to are, and so on.

Suppose that the programmer changes the type of a constant in their crate. When they run the compiler, it will evaluate a top-level query to produce an output binary. That query will in turn query for the final versions of each function in the crate (after type-checking and optimization). Most of those will not have changed, so the answers are provided from the on-disk compilation database. The queries for functions that depend on the changed constant, however, will get re-run — and will, themselves, call other queries until the whole process ends up at the query corresponding to the parsed representation of the single changed definition. Only the minimum amount of analysis and compilation needed to accommodate that change is performed.

This approach is reminiscent of a build system — and that's deliberate. Build systems, while not always perfect, usually do a good job of tracking the dependencies between components and correctly caching partial results. A compiler that has the architecture of a build system can take advantage of the research that has been done on build systems to do the same.

Rust's approach

The Rust project began the process of rewriting its compiler to support incremental compilation in 2016. While that redesign is not yet fully complete, large portions of the compiler now use a query-based approach. LWN recently covered Sparrow Li's talk that discussed what remains to be done.

The Rust compiler organizes queries using a structure called TyCtxt. When the compiler starts up, the various modules all register functions called "providers" that implement each query. Then, depending on how the compiler was invoked, it parses the code (because the parser has not yet been integrated into the query system) and runs a set of top-level queries to compile an artifact, format the code, produce warnings, or whatever else was requested.

Providers need to be pure functions, since the compiler may not always need to run them, so the programmer can't depend on any side effects. This also has the effect of forcing those parts of the compiler that have been converted to the query system to avoid global state. The results of queries could in theory be any type, but in practice the compiler requires that they be values that can be cheaply copied, in order to simplify the ownership of cached values. Not every query is saved to disk, but most queries return types that can be serialized and hashed, so that they can be.

There are some important differences in structure between Rust's queries and static build systems like Make, not just in the form that their results take. In Rust's implementation, the relationship between queries is implicit. Queries are always invoked via a TyCtxt; that structure can track the dependencies between queries by seeing which queries are invoked while another is executing. Also, unlike some build systems, the compiler tracks the order in which dependencies are invoked. This is important because the results of one query can change which other queries get executed — therefore, the order impacts the calculation of which queries need to be rerun when doing incremental compilation. For example, this query depends on different things depending on the result of subquery1():

    fn example_query<'tcx>(tcx: TyCtxt<'tcx>) -> SomeType {
        if tcx.subquery1() {
            tcx.subquery2()
        } else {
            tcx.subquery3()
        }
    }

During the initial run of the compiler, when there are no saved results, the program collects the graph of which queries refer to each other. When the compiler is rerun, it checks that graph to see which queries need to be rerun because of changed inputs. As an additional optimization, if the inputs to a query have changed, but the result of the query has not, the compiler can detect that and cut off the process of recalculating queries early.

The process of figuring out whether an intermediate result has changed is complicated by the fact that any information about the incremental build needs to be shared between runs of the compiler by saving it to disk. The compiler uses a lot of internal ID numbers to organize different components that differ from run to run, and serializing every intermediate result in the compiler would be expensive. So actually saving the results of cached queries is more complex.

In order to work around the problem of changing internal IDs, structures that are saved to disk are given "stable" forms of each ID. For example, function and type definitions are identified by path (e.g. std::collections::HashMap) instead of by internal ID. In order to avoid the overhead of deserializing intermediate results to detect changes, the compiler calculates and stores hashes for each item. Hashes are much more compact, and don't require complex deserialization, so this is a substantial performance improvement. The downside is that computing so many hashes actually causes significant overhead. The compiler's internal documentation calls it "the main reason why incremental compilation can be slower than non-incremental compilation."

These performance improvements introduce their own complications, of course. For example, if a result is never loaded from disk, the compiler won't necessarily be able to include it in the incremental-compilation database for the next run of the program. So, after generating results, the compiler does another pass through the query graph to fetch and update the results that it skipped earlier, in order to make sure that the size of the cache doesn't unnecessarily shrink. This increases the compiler's overall runtime — but what users usually care about is the time it takes to produce warnings and errors, not how long it takes the compiler to do cleanup before exiting. There are various other optimizations and tweaks applied to the largest queries to make the overall system more performant. The Rust Compiler Development Guide's section on the query system has more details.

Overall, the query-based approach introduces a lot of complexity compared to a simple pipeline-based approach. But any large, performance-sensitive codebase accumulates complexity over time — and having a single, well-understood system for incremental compilation may well win out over gradually introducing ad-hoc improvements to a pipeline-based system. In any case, Rust's incremental compilation has been stable enough to become the default for development builds. Release builds still avoid incremental compilation by default, however, out of an abundance of caution. Whether the query-based compiler design will ultimately be adopted by other languages remains to be seen.