Incremental compilation overview

incremental.md

Zig Compiler: Incremental Compilation

A few ground rules:

• Values in the InternPool are immutable. The meaning of a given Index never changes.
• The only kind of "exception" to this is that the namespace of types may change. The namespace index is constant, but the contents of that namespace can change while the type lives at the same Index.
• Incremental compilation works at the level of single units of semantic analysis (AnalUnit). During semantic analysis, every AnalUnit registers "dependencies" on various things ("dependees"). On each incremental update, these dependencies are used to figure out what to re-analyze.
• An incremental update may analyze more AnalUnits than are necessary, but it will never analyze the same unit twice; so, the amount of work is bounded by the work of a non-incremental update. (Technically it's bounded at "last_update_work + new_update_work", since we might analyze old declarations which are now unused/unreferenced, but that's rare.)

The early parts of the compiler pipeline are not particularly incremental. At the start of an update, parsing and AstGen are run over every changed file, as a whole. We then build up a mapping from old ZIR instruction indices, to new ZIR instruction indices. We don't try to map every single instruction, but instead only the following tags:

• declaration
• struct_decl
• union_decl
• enum_decl
• opaque_decl
• reify

I won't cover the logic for this here, but it can be found in Zcu.PerThread.mapOldZirToNew.

Let's now change topics, and cover the kinds of "dependee". There are two classes of dependee. For some dependees, we know whether or not they are outdated as soon as AstGen completes, before we begin semantic analysis. For other dependees, we discover whether they are outdated during semantic analysis. For want of a better term, I'll term these "simple" and "complex" dependees respectively. The kinds of dependee are as follows.

• src_hash dependees (simple) are invalidated when the 128-bit source hash associated with a single ZIR instruction changes. They are also invalidated when we fail to map the ZIR instruction in question to the new ZIR, which we refer to as the instruction being "lost".
• namespace dependees (simple) are invalidated when the set of names exposed from a namespace (given by the ZIR struct_decl/etc instruction of the namespace) changes. These dependencies exist exclusively due to @typeInfo, which is the only way to determine the full set of names in a namespace.
• namespace_name dependees (simple) are invalidated when a specific name is added to or removed from a namespace (again, given by the ZIR type declaration instruction). These are triggered by namespace lookups, such as Foo.bar or @hasDecl.
• nav_val dependees (complex) are invalidated whenever the resolved value of a Nav changes. Precisely, they are invalidated when the InternPool.Index of the value changes, or when the address space, or linksection, or alignment of the Nav changes.
• func_ies dependees (complex) are invalidated whenever the inferred error set of a function (given by the function's InternPool.Index) changes. These dependencies are triggered by IES resolution; for instance, switch on an inferred error set value.
• type dependees (complex) are invalidated whenever the "structure" of a container type (given by the type's InternPool.Index) changes. Here, "structure" essentially refers to the type's fields: everything other than its namespace. Notably, these dependencies cannot be registered on opaques, because opaque types do not have fields or anything like them!

In actuality, func_ies and type dependees are combined under the umbrella interned. This is purely to make the code a little simpler, because it's not possible to have a func_ies and type dependency on the same InternPool.Index, so we don't need to separate them!

Now, let us look more at the anatomy of an incremental update. As previously discussed, after AstGen, we correlate ZIR instructions in changed files. This information is sufficient for us to invalidate any "simple" dependencies as needed. So, this immediately tells us that some AnalUnits are outdated -- for instance, if the source code of a container-level const changes, we know the Cau corresponding to that declaration is outdated and hence requires re-analysis.

We don't yet know which "complex" dependencies are outdated, if any. However, we can determine that some are definitely not outdated. For instance, consider this code:

const a = 123;
const b = a;
const c = 456;
const d = c;

If the only simple dependee which was invalidated is the hash of the declaration a, then we know for a fact that nav_val dependees of c and d will not be invalidated. Intuitively, this is because there is no way for any change in a to affect c or d. It can, however, affect b. How can this information guide our implementation?

Here's what we do. Whenever we invalidate a "simple" dependency (which, remember, always happens before semantic analysis begins), we think about the "worst-case scenario": which "complex" dependees may become outdated as a result of the AnalUnits which will be re-analyzed. For instance, if the Cau of a container-level const is to be re-analyzed, it's possible the corresponding nav_val will turn out to be outdated. The full set of these mappings is as follows:

• If a Cau owned by a named source declaration (const/var/fn) is outdated, then the nav_val of the corresponding Nav may turn out to be outdated.
• If a Cau owned by a type (struct/union/enum, but not opaque, since they don't have fields so have no Cau in the first place!) is outdated, then the corresponding type dependee may be outdated.
• If a runtime function (AnalUnit.func) is outdated, then that function's IES may be outdated.

When a simple dependee is invalidated, we mark all AnalUnits which depend on it as outdated. Then, we look at the mappings given above to see if this AnalUnit might cause a complex dependee to become outdated. If so, we consider that dependee "potentially outdated" (which I commonly shorten to PO). So, all AnalUnits which depend on that dependee are marked as PO. In turn, we check whether those AnalUnits might invalidate any complex dependee, recursing until we have marked everything which might be transitively outdated.

After doing this for all simple dependees, we have defined a partition of all AnalUnits into three sets:

• Those which are definitely up-to-date (requiring no re-analysis).
• Those which are definitely outdated (must be re-analyzed).
• Those which are PO (may or may not end up requiring re-analysis, depending on whether complex dependees are invalidated).

During semantic analysis, we will refine this partition, moving items in the PO class into one of the other two classes as we learn about which complex dependees are outdated vs up-to-date. For every AnalUnit, we also store the number of dependees the unit depends on which are PO. (For up-to-date AnalUnits, this number is clearly always zero, and isn't actually stored.) This allows us to efficiently move things between these sets. For instance, if a PO dependee turns out to be up-to-date, we can iterate the AnalUnits that depend on it, and decrement their PO dep count. If that count falls to zero for an AnalUnit which is PO, then we have determined that the unit is actually up-to-date; the dependees which could have made it outdated all turned out to be up-to-date. So, we can move this unit from the PO set into the up-to-date set.

So, after any AnalUnit is analyzed, we look at the mapping discussed before. If this unit is the decider for a dependee, then we either mark it as up-to-date, or we mark it as definitely-outdated. In the former case, we decrement the PO dep count for each AnalUnit which depends on this dependee; if any unit's PO dep count falls to 0, we deem it up-to-date. In the latter case, we still decrement the PO dep count for each such AnalUnit, but any unit which was PO is now known to be outdated. Either way, the PO set will typically decrease in size (it certainly never grows).

So far, it's perhaps not been clear why we track the "PO dep count" for definitely-outdated AnalUnits; I've only described its usage for PO units. To understand this, we need to discuss the re-analysis mechanism.

When we analyze any AnalUnit, it may trigger analysis of other units; either by looking at the resolved value of a Nav corresponding to a runtime declaration (and so requiring analysis of the corresponding Cau), or by resolving the IES of a runtime function. Whenever this happens, we have to be pessimistic. Naturally, if the unit we're analyzing is up-to-date, we don't need to do any work; and conversely, when it is definitely outdated, we do need to re-analyze it. However, if it is potentially outdated, we also need to re-analyze it. The caller (Sema of the other AnalUnit) needs this thing to be up-to-date here and now; it's not enough for it to be up-to-date at some point in the future.

This means that ideally, before we analyze an AnalUnit, we want to know whether the AnalUnits it will reference are up-to-date or not. Unfortunately, it isn't possible for us to know this ahead of time; we by definition don't know for sure what something will reference before semantic analysis. However, during an incremental update, we have a very good heuristic for this: most declarations will reference a very similar, if not identical, set of AnalUnits to what they did on the last update. This is modelled by the unit's existing dependencies. For instance, if an outdated unit has a dependency on a PO dependee, we know it's quite likely that it will reference that dependee again. If we analyzed the unit now, it would have no choice but to treat that dependee as outdated, triggering analysis which may not actually be necessary. So, a better choice would be to first try and make progress towards figuring out whether that other dependee is PO -- chances are we can figure that out by analyzing some different outdated units first! So, this is the use of the PO dep count for outdated units: when we are choosing an outdated unit to analyze, we ideally select one with a PO dep count of 0, since we expect it will have to trigger little to no further analysis, avoiding over-analysis.

Let's now talk in more detail about exactly how we select which outdated AnalUnit to analyze next.

When the job queue is empty, we don't immediately finish compilation when performing an incremental update. Instead, we call Zcu.findOutdatedToAnalyze. This function consults the outdated set and chooses an AnalUnit from it which is a good candidate to re-analyze now; as discussed above, it will ideally pick one which is outdated and depends on zero PO dependees. (For efficiency, we store a separate list of these ideal candidate AnalUnits, called outdated_ready.)

If no such candidate exists, then we need to fall back to a heuristic. This case can happen primarily due to recursive types:

const A = struct { b: ?*B };
const B = struct { a: ?*A, x: if (x == 1) u8 else u16 };
const x = 2;

If the Cau of T is re-analyzed and results in a different value, then the corresponding nav_val dependee is outdated. So, the type B must be PO, which in turn makes the declaration B PO (we'll discuss the relationship between types and other units later). That makes the type A PO, which makes the declaration A PO. So, we have 4 PO units in a loop: even if everything is actually up-to-date, the dependency mechanism might not know that, so it unfortunately has to analyze one of these things.

The heuristic we currently use here is to select the AnalUnit which we expect to "answer the most questions", so to speak. More specifically, we pick the unit which is triggering a PO dependency in the highest number of other units. In the above situation, each of the 4 units is only triggering a PO dependency on one other; but if there were, say, a second reference to A, then the Cau of that declaration would be selected. The idea here is that by re-analyzing this, we're likely to resolve the status of a lot of other units. I'm not sure if this is a good heuristic or not; this is subject to change.

Okay -- enough about that. It's time to talk about types!

Types are a bit tricky. To ensure correctness, if a type is outdated (i.e. its fields are outdated, so field types or something), then we want to re-analyze all uses of the type. One way we could do this would be to mark a dependency whenever we perform literally any type query -- name, field count, "field is comptime", default value, anything. This would be rather inconvenient to implement in Sema, and would probably lead to a lot of dependencies. It would also require semantic analysis to be aware of what backends need to know about types, which we've been trying to get away from. So, we use an alternative strategy: if a type is outdated, it will be recreated at an entirely new InternPool.Index. The old Index remains valid, in that indexToKey and other queries still work -- this is because there may be lingering references to the old type. However, lookups will return the new type. (We achieve this by performing an atomic store into the hashmap metadata: since the key is the same, we just replace the old index with the new one.) This means that, for instance, a Nav of this type will now have a distinct value (at a new InternPool.Index), since the type has changed; so all transitive uses of the type get re-analyzed "for free", so to speak. The disadvantage is that we lose some incrementality, but the compiler is generally fast enough that this doesn't really matter! For instance, recreating Sema -- one of the most complex types in the compiler -- results in only around 3 seconds of analysis+codegen work (on a compiler built with Tracy; probably closer to ~1s on a non-Tracy-enabled compiler build). So, it's okay to occasionally recreate types and do a bit more work than may be strictly necessary to simplify the system.

Types are considered outdated whenever their Cau is outdated. This Cau is what performs type resolution for this type. For enums, this happens at the moment the type declaration is analyzed, whereas for structs and unions, this happens in stages. Type resolution registers dependencies just like any other semantic analysis. So, when the Cau is outdated, some aspect of type resolution may be different, hence we recreate the type as described above. When ensureCauAnalyzed is called on an outdated Cau owned by a type, semaCau calls through to ensureTypeUpToDate which ultimately triggers recreateStructType (or recreateUnionType/recreateEnumType). This function fetches the ZIR index and captures from the type's old InternPool.Index, and recreates the type at a new index. Importantly, if the ZIR instruction has been lost, or the number of captures in the type has changed, we return error.AnalysisFail, because there is no direct equivalent to the old struct type. This causes any analysis which references the old type to record a transitive analysis error: these AnalUnits will never be referenced again, because the struct type they refer to is "dead". Otherwise, we recreate the type at the same ZIR index with the same list of captures, and reparent the old namespace to it.

Since we have no guarantee that the dependency mechanism will re-analyze a type before its use sites (it should do, but it could fall back to the heuristic and analyze something else!), there are other paths through the call graph which can lead to a type getting recreated:

• Sema.zirStructDecl, Sema.zirUnionDecl, and Sema.zirEnumDecl call ensureTypeUpToDate when the lookup finds an existing type, so the type will get recreated if necessary. This is equivalent to calling ensureCauAnalyzed on the type's Cau, but it's a slightly faster path since we don't have to lookup the type in the InternPool again afterwards (the new index is returned by ensureTypeUpToDate).
• Sema.zirThis will call ensureTypeUpToDate on the namespace's owner type (again, equivalent to an ensureCauAnalyzed call). This is important to make sure that all "up-to-date" references to the type refer to the up-to-date type. This one will make a little more sense when we discuss namespaces later.

These call sites are also precisely the places where we store an interned dependency on a type: its declaration site, and @This(). Essentially, if we fetch a type from the InternPool which might become outdated, we store an interned dependency so we can do this ensureTypeUpToDate call and get the updated type if necessary.

Now, let's look at namespaces. A namespace essentially has an owner type, populated when the namespace is created, and a list of declarations, populated by Zcu.PerThread.scanNamespace. On an incremental update, types -- even up-to-date ones, i.e. whose fields definitely haven't changed -- may need to re-scan their namespace, to pick up on new/removed/changed declarations. For this, we use ensureNamespaceUpToDate. This function compares the generation field on the namespace to zcu.generation -- if they're equal, that means the namespace has already been re-scanned this update, so there is no work to do. This isn't strictly necessary, but it's an important optimization -- without it we perform a whole lot of unnecessary re-scans! If they're not equal, it fetches the list of declarations from the type's ZIR, and runs scanNamespace again, then updates generation.

Namespaces are not necessarily up-to-date if a type is up-to-date; ensureTypeUpToDate is only making sure that the InternPool.Index is correct. Instead, namespace updates happen in two main situations.

Firstly, when zirStructDecl (etc) is analyzed and finds an existing type, after calling ensureTypeUpToDate, it will call ensureNamespaceUpToDate. This is important because if the type is still referenced, even if no lookups have changed, we need to make sure its namespace is up-to-date to make sure we've picked up on new tests, comptime declarations, etc. We can guarantee that this will always happen because if the namespace of a type is different, its source must be different (this is one example of where usingnamespace would be a nightmare for incremental compilation!), so the declaration containing the type (be it a function body or some other declaration) will have an outdated source hash so will get re-analyzed, which will ultimately re-analyze the struct_decl (etc) instruction.

However, this is not sufficient for correctness: there's no guarantee that zirStructDecl is analyzed before other references to the namespace happen. So, we also call ensureNamespaceUpToDate whenever we "use" the namespace. This means that whenever we look up decls, either for @typeInfo or for a standard namespace lookup, we make sure the namespace is correct first. Note that this doesn't necessarily make the owner_type up to date (this field changes because namespaces are reused when a type is recreated to avoid throwing out simple analysis work), so the functions that consult this field -- essentially just zirThis -- need to get the current owner type, and call ensureTypeUpToDate to make sure owner_type is populated with the correct type.

TODO: file root structs

TODO: kinds of source hash dependency

TODO: astgen failures