Buildsimplementation

Incremental Compilation

Recompile what the change actually affected, not what it touched. The modern form is not file timestamps but a memoized graph of queries, where a change invalidates exactly the results that depended on it.

The question

How does a compiler avoid redoing work when only a little changed?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

In the classic model the program is a set of units plus a record of the last build. In the modern model the compiler *is* a memoized graph: every question — "what is the type of this item?", "what does this name resolve to?", "what MIR does this function have?" — is a query node whose result is cached and whose dependencies on other queries are recorded as they execute. The program in that model is not a data structure at all; it is a set of answered questions, and a change invalidates exactly the answers that read the changed input.

What this phase may assume or do

Skipping work is behavior-preserving only if the cached result is a function of inputs that provably did not change. That requires every dependency to be *recorded*, not assumed: an analysis that reads an input without registering the read produces a cached answer that survives a change it depended on. This is the precondition the whole mechanism rests on, and it is why unrecorded dependencies — ambient environment, a file read outside the tracked filesystem layer, a global counter — turn incremental compilation from an optimization into a source of stale, wrong output.

Key points

  • Incremental compilation means recompiling what a change affected, which is usually much less than what it touched.
  • Early cut-off — comparing recomputed outputs against cached ones and stopping when they match — is what turns most edits into small rebuilds.
  • Query-based compilers restructure the compiler as a memoized, demand-driven graph, so invalidation is precise and unused analyses never run.
  • Every dependency must be recorded. An unrecorded read produces a cached answer that survives a change it depended on, and the result is a stale build.
  • The costs are real: purity constraints, a serializable cache format, higher memory use, and a slower first build.

The classic model and where it stops

The oldest form is per-unit: record what each unit depended on, compare timestamps or hashes, recompile the units whose inputs changed. This is what make plus a compiler-generated dependency file does, and for C-family builds it remains the mainstream answer. It is coarse — the granularity is a whole unit — and it degrades badly when the unit is large or when a widely-included header changes.

The next refinement is early cut-off: after recompiling a unit, compare its *outputs* — particularly its interface artifact — against the previous build's, and stop propagating if they match. That is the mechanism [[interface-files]] provides, and it converts most body-only edits from a cascade into a single recompile.

Query-based compilation: the compiler as a memo table

implementationrustc's query system and its on-disk incremental cache are internal and change between releases; the cache lives in target/incremental and is invalidated wholesale by a compiler upgrade or a flag change. Roslyn, the Swift driver and Kotlin's incremental compiler each solve the same problem with a different granularity and different persistence rules, and none of them guarantees the same rebuild set for the same edit.

The modern approach inverts the structure. Instead of a pipeline of passes that walk the whole program, the compiler is a set of *queries*, each a pure function from inputs to a result, and each recording which other queries it called while running. Ask for the final artifact and the queries pull each other into existence on demand; the parts of the program nobody asked about are never analysed at all.

rustc works this way, with a query system whose design is shared with the salsa framework; Roslyn does something similar for C# and VB, which is what lets it serve an IDE and a batch compile from the same code. The property that makes it worth the complexity is *demand-driven* evaluation plus precise invalidation: an edit marks the changed source file's query as dirty, and the system walks the recorded dependency edges to find exactly which cached results can no longer be trusted.

Early cut-off matters even more here. If re-running a query produces a value equal to the cached one — reformatting whitespace, renaming a local — the propagation stops at that node, and nothing downstream is recomputed even though the input genuinely changed. Whole regions of the graph survive edits that looked significant.

A query system, in the small
1query type_of(item) {
2  let ast   = parse(file_of(item));      // dependency recorded
3  let sig   = signature_of(ast, item);  // dependency recorded
4  return check(sig);
5}
6 
7// edit widget.rs
8mark_dirty(source("widget.rs"))
9 
10// on the next demand for type_of(x):
11//   re-run parse(widget.rs)   -> new AST
12//   re-run signature_of(...)  -> SAME value as cached
13//   early cut-off: type_of(x) is not re-run, and neither is anything above it

The third comment is the whole trick. Invalidation walks *down* to the changed input, then verification walks back *up* and stops the moment a recomputed value equals its cached predecessor.

What it costs, honestly

This is not free architecture. Every query must be a pure function of its recorded inputs, which forbids the ambient mutable state that compilers have traditionally been full of. Results must be hashable and, if the cache is to survive a process restart, serializable — which means a stable on-disk format for a large fraction of the compiler's internal data structures. The cache itself takes real disk space and real time to load and save.

And the failure mode is nasty: if a dependency is not recorded, the compiler returns a stale answer, and the symptom is a build that produces different output from a clean build of the same source. Every query-based compiler ships a way to disable incrementality precisely because "does it reproduce from clean?" is the first question asked about a strange bug.

  • Purity is a hard constraint, not a style preference. One unrecorded read makes the cache lie.
  • Serialization is a second, large project: an on-disk cache needs a versioned format for internal types.
  • Memory and disk grow with the graph; incremental builds routinely use more RAM than clean ones.
  • The first build is slower than a non-incremental first build, because everything is being recorded and written out.
  • Debugging requires being able to turn it off, and the ability to reproduce from clean is the standard triage step.

How it works

The steps, in the order the compiler takes them.

  • Each query executes inside a tracking context that records every other query it invokes and every input it reads.
  • Results are stored in a memo table keyed by the query and its arguments, alongside the recorded dependency list and a hash of the result.
  • An edit marks the corresponding input node dirty; dirtiness is propagated lazily rather than eagerly.
  • When a query is demanded, the system first verifies its dependencies recursively; a dependency whose recomputed result hash matches the cached one is treated as unchanged.
  • If every dependency verifies, the cached result is returned without re-executing the query — this is where the saving comes from.
  • At the end of the session the memo table and dependency graph are serialized so the next process can start from them.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • An incremental build succeeds and a clean build of the same source fails, or vice versa; the difference is a dependency the compiler did not record.
  • A rename or a whitespace edit triggers a full rebuild because the change perturbed a hash that everything depends on — often a span or a symbol index rather than anything semantic.
  • The incremental cache grows to tens of gigabytes and the machine runs out of disk during a build, with an error from the filesystem rather than the compiler.
  • Diagnostics disappear on the second build because the query that produced them was cached and its warnings were not part of the cached value.
  • A compiler upgrade silently invalidates the entire cache, and a team reports that "the build got slow" on the day of the upgrade with no other change.

When it helps

  • Interactive development, where the edit-compile loop dominates the working day and the change per iteration is tiny.
  • IDE and language-server workloads, which are the extreme case: the same analyses are demanded thousands of times against a document that changes by one character.
  • Large monorepos where the ratio of codebase size to change size is enormous and a proportional rebuild is the only viable model.

When it hurts

  • Clean CI builds, which never reuse a cache and pay only the overheads — recording, hashing and serialization — for no benefit. Many CI configurations disable it for exactly this reason.
  • Codebases where a single widely-depended-on definition changes constantly, so the invalidation set is nearly everything and the bookkeeping is pure cost.

What it costs

Every one of these is paid by something.

  • Precise invalidation buys rebuilds proportional to the change, and pays in compiler architecture: purity, recorded dependencies, hashable results, and a serialization format for internal types.
  • An on-disk cache buys reuse across process restarts and pays in disk space, load and save time, and a first build that is slower than a non-incremental one.
  • Finer granularity buys smaller rebuild sets and pays with a larger dependency graph — more nodes, more edges, more memory, and more time spent verifying rather than compiling.
  • Reusing analysis results buys speed and costs reproducibility as a default assumption; a build that cannot be trusted to match a clean build is a build whose failures are twice as hard to diagnose.

What else you could do

What a different compiler or language does instead, and when that is better.

  • Timestamp-based per-unit rebuilding, as in classic make. Vastly simpler, coarse, and subject to both missed and spurious rebuilds — see [[build-system-interface]].
  • Content-hash-based per-unit rebuilding with a shared artifact cache, as in Bazel and Buck. Coarser than queries but distributable and reproducible, which query caches generally are not.
  • Compile-everything-every-time, which is what a whole-program build does; correct by construction, and only viable when the program is small or the build is rare.
  • A separate fast path for the interactive case: some toolchains keep a batch compiler and an incremental language server as different programs, accepting duplicated semantics to avoid rebuilding the compiler around queries.

See it for yourself

The flag, dump or tool that shows you this directly.

  • cargo build -Z timings on nightly, and target/incremental on disk — its size is the cache, and deleting it forces the non-incremental path.
  • CARGO_INCREMENTAL=0 cargo build versus the default, on the same edit, is a direct measurement of what incrementality bought.
  • rustc -Z self-profile records query counts and durations, and summarize renders which queries actually ran after an edit.
  • ghc -ddump-hi-diffs shows exactly which parts of an interface changed between builds, which is what decides downstream invalidation.
  • gcc -MMD and clang -MMD emit the dependency files that a make-based incremental build relies on; reading one shows what the build thinks a unit depends on.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Incremental compilation means only changed files are recompiled." It means only *affected* results are recomputed, which is both less — thanks to early cut-off — and more, since dependents can be affected without changing.
  • "It is just caching." Caching without recorded dependencies is how you get stale output. The dependency tracking is the hard and load-bearing part.
  • "Incremental builds are always faster." The first one is slower, CI builds are slower, and an edit that invalidates a root definition is slower than the equivalent non-incremental build because of the bookkeeping.
  • "If it compiles incrementally, a clean build gives the same result." That is the goal, not a guarantee. It is exactly what a missed dependency edge breaks.

Misconceptions

The claim, and what is actually true.

Incremental compilation is a build-system feature.
It exists at two levels. The build system decides which compiler invocations to run; the compiler decides how much work to skip inside one invocation. Query systems are the second, and a build system cannot provide them.
Query-based compilers are just compilers with a cache bolted on.
The cache dictates the architecture. Passes become queries, mutable global state becomes illegal, and every internal type acquires a hashing and serialization obligation.
Turning off incremental compilation is a bug workaround.
It is the standard triage step, and it is deliberately supported. A discrepancy between incremental and clean output localizes the bug immediately.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

After you change one line, most of the work the compiler did last time is still valid. Incremental compilation keeps the previous results and redoes only the parts that could have been affected. The old way was to compare file timestamps and recompile whole files; the new way is to remember the answer to every small question the compiler asked and to re-ask only the ones whose inputs changed.

practical

Three things to know in practice. Incremental caches are per-machine and per-compiler-version, so they help local development and generally do not help CI — many teams disable them there. If an incremental build behaves oddly, reproduce from clean before doing anything else, because that single comparison distinguishes a code bug from a cache bug. And if a trivial edit keeps triggering large rebuilds, look at what your public surface exports: an interface change propagates, an implementation change usually does not.

advanced

The design lesson generalizes past compilers. A demand-driven memoized graph with recorded dependencies and early cut-off is the same architecture as a modern build system, a spreadsheet recalculation engine and a reactive UI framework, and they hit the same three problems: how to record dependencies without burdening every call site, how to compare results cheaply enough that verification beats recomputation, and how to persist the graph without freezing your internal data structures into a format you must then support forever. rustc and Roslyn answer them differently — rustc interns aggressively and hashes structurally, Roslyn leans on immutable snapshots of the whole solution — and both answers are visible in the resulting user experience.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationrustc's incremental cache format, its query granularity and what it chooses to persist are internal and change between releases; a compiler upgrade discards the cache entirely. Roslyn, the Swift driver, Kotlin's incremental compiler and GHC's recompilation checker are four different designs with four different granularities, and none of their behavior transfers to the others.
typicalMainstream incremental compilers apply early cut-off by comparing a hash of a recomputed result against the cached one. Whether a specific edit stops at cut-off depends on what the hash covers: in several implementations spans are part of it, so inserting a blank line changes hashes that a semantic view would consider unchanged.
simplifiedThe query example in this lesson shows three queries; a real system has hundreds, with cycles detected at runtime, arena-allocated results, interned keys and a separate on-disk representation. The shape — record dependencies, verify recursively, cut off on equal results — is faithful, the scale is not.

If you were asked this in an interview

  • What is early cut-off, and why does it matter more than dependency tracking for real edits?
  • What breaks if a compiler analysis reads an input without recording it as a dependency?
  • Why do many teams disable incremental compilation in CI?

Connections

DSAdagtopological-sorthash-table
Performancemeasure-before-optimizingperformance-regression-detection
Domains that do not exist yet
  • DevOps / Production Engineering — Build caches, cache keys and remote execution
    The compiler-internal cache and the build system's artifact cache solve the same problem at different granularities and have opposite operational properties — one is machine-local and version-fragile, the other is shareable and content-addressed. Operating the second, and deciding when a shared cache is trustworthy, belongs there.