Inside Zig's Incremental Compilation

As a member of the Zig core team, one of the most impactful projects I’ve been involved with is the implementation of incremental compilation into the Zig compiler. This feature allows the compiler to detect which individual functions and declarations have changed since a project was last built, recompile only that code, and directly patch the resulting bytes into the output binary, making the rebuild extremely fast.The Zig project has been working towards this feature for a long time, and over the last few release cycles, it has finally gone from a proof-of-concept quality feature to one which is viable for real-world projects and which most of the Zig core team makes daily use of.Today, using Zig’s incremental compilation, you can make changes to real, complex applications in a matter of milliseconds.But don’t just take my word for it! Here’s a simple video (no audio) demonstrating me using Zig to quickly make and test some changes to Fizzy, a pixel editor application. The initial build takes around 5 seconds, and then every time I make a change, a rebuild completes in 50–70ms.For this demo, I had to upgrade Fizzy to Zig’s master branch. This is because while Zig 0.16.0 does have support for incremental compilation, it is missing some important linker features which have since been implemented. This means that if you prefer to stick to tagged releases of Zig, you likely won’t be able to try this out until 0.17.0 drops; sorry! Fast incremental rebuilds for some random changes to FizzyIf you’re already convinced and just want to know how to use this, great! Head on down to the last section of this post to find out. But perhaps you’re understandably skeptical that this is applicable to most projects, or, like me, you just enjoy learning how stuff like this works. For all of you folks, let’s dig into the details!Processing Source FilesThe Zig compiler’s pipeline can be split up into a few different parts, which we’ll look at in order. The first part works at the granularity of entire source files, and basically consists of running the following process in a loop:Read in a source file from diskParse that file into an ASTConvert that AST into a format named “ZIR” using a pass named “AstGen”If you’re curious, ZIR (Zig Intermediate Representation) is an untyped SSA-form IR—but don’t worry if you have no idea what that means, because it won’t really matter here. All we care about is that we’re converting an entire source file into a different format.While AstGen runs, it learns about all Zig imports (@import("foo.zig")) in the source file, so we can repeat this entire process on all of the imported files. So by running this process in a loop, we will ultimately discover every Zig source file in the compilation, and will convert them all to ZIR. File processing pipeline in the Zig compilerThis part of the pipeline actually has several useful properties:The processing run on each file is a pure function of that file’s contents, involving no shared or external stateParse and AstGen are both quite fast on their own: on my laptop, running them both over the entire src/ directory of the Zig compiler (with no parallelism at all) takes around 920msThanks to Zig’s usage of data-oriented design patterns, ZIR can be trivially written to and read from disk with one writev/readv system call—there is no “serialization” step.These properties have two nice consequences.Firstly, assuming one “task” per source file, this entire process is embarrassingly parallel. That means we can trivially run it on a thread pool by queuing up a task every time we discover a new source file from an import—the only shared state (which we’ll just protect with a mutex) is a hash set keeping track of which file paths we have already seen.Secondly, and arguably even more importantly, these properties make it very straightforward to implement incremental compilation for this part of the pipeline. All we need to do is cache each source file’s generated ZIR on disk, and only rebuild it when we detect that the file changed.Both of these optimizations have been enabled by default in Zig for years—they are battle-tested and make this part of the pipeline near-instantaneous in most cases. If you’re using Zig, you can see how fast this is using the progress output on stderr—when it says “AST Lowering”, this part of the pipeline is running. I’d guess that a lot of Zig users only even notice that happening the very first time they run the compiler (because on its first run the compiler needs to do this work for the entire Zig standard library and compiler_rt).Okay, so, we made this part fast! That’s great, but the bad news is that this was the easy part—lots of compilers can already do this kind of caching. From here, things will get trickier.Semantic AnalysisThe next part of the pipeline is arguably the most important: semantic analysis. This includes both type checking and comptime evaluation.The job of semantic analysis is essentially to “interpret” the ZIR we produced earlier, emitting compile errors (such as type errors) along the way; and, for runtime functions, building another intermediate representation (Analyzed Intermediate Representation, or AIR for short) which can be sent on to later parts of the pipeline.Before we move forward, a quick terminology clarification. A “container-level declaration” is the Zig equivalent of what other languages call a “top-level declaration”. That term is inaccurate in Zig, because container-level declarations do not have to be at the top level syntactically, but the concept is the same. If I say “container-level declaration”, I basically mean “a function, global constant, or global variable”.Semantic analysis is the most difficult part of the compiler to handle incrementally. Perhaps unsurprisingly then, this is where language design starts to matter a lot: while I am pretty confident that most modern languages could support incremental compilation similar to how we do, certain design decisions can make that much more difficult. Zig has had its design tweaked over the years (sometimes controversially) specifically so that it is easier to support fast incremental compilation.The name of the game here is to split up your compilation into a bunch of pieces which you can mostly analyze independently of one another, and, crucially, where the dependencies that do exist between those pieces can be easily modeled in a dependency graph.In the Zig compiler, we call these pieces “analysis units”, or I might sometimes just say “unit” for short. I’m going to ever so slightly simplify things here and tell you that the Zig compiler has four different kinds of analysis unit:The layout (size, alignment, etc) of a struct or union type.The type of a container-level declaration.The value of a container-level const declaration.The body of a runtime function.During semantic analysis of a particular unit, we populate a set of other units which this unit depends on. Let’s look at a basic example:var global_0: u32 = 123; const global_1: u32 = 456; pub fn foo(cond: bool) u32 { if (cond) { return global_0; } else { return global_1; } } Here’s what happens when we analyze the body of the function foo:Because the argument cond is not comptime-known, we semantically analyze both branches of the ifTake a pointer to global_0, in preparation to load from itAdd dependency: type of global_0Load global_0 at runtime, because it is var so does not have a comptime-known valueTake a pointer to global_1, in preparation to load from itAdd dependency: type of global_1Load global_1 at compile time, because it has a comptime-known valueAdd dependency: value of global_1So we end up with this function body depending on the types of global_0 and global_1, and the value of global_1 (since that’s comptime-known). This tells the compiler that if the type of global_0 or global_1 changes, or the comptime-known value of global_1 changes, the function should be re-analyzed.Dependencies on the body of a runtime function are impossible (at least in the simplified view I’m presenting here). This means that function body analysis units can only have “outgoing” edges in the dependency graph (i.e. they may depend on other units, but other units do not depend on them).Dependencies on the value of a const declaration only arise due to Zig’s ability to use those at comptime. If not for that language feature, dependencies on the value of a declaration would be impossible, just as it is impossible to depend on the body of a runtime function.Dependencies on a type’s layout arise, in short, from having values of that type, or from needing to know something about the type’s layout. I’m not going to discuss this any further here, because it’s a bit complicated and quite specific to Zig’s type system, but it’s not fundamentally different.Okay, so, we’ve told the compiler about when re-analysis of one thing needs to also trigger re-analysis of another thing. However, there’s one more puzzle piece here—source code dependencies. By itself, this dependency graph is useless: what do we actually do when the user asks for a recompile (what we call an “incremental update”)? We don’t know the first thing to re-analyze!To solve this problem, we track dependencies of analysis units, not only on other units, but also on pieces of source code. In the cases we’ve looked at so far, these are all really simple: in the snippet above, the unit “type of global_0” depends on the source code of global_0, the units “type of global_1” and “value of global_1” both depend on the source code of global_1, and the unit “body of foo” depends on the source code of foo. Whenever any byte of source code in the given region is modified, the dependent analysis unit will be marked as “outdated” and re-analyzed.Note that in reality, things can get more complicated than each unit depending on one piece of source code. For example, an inline function call in Zig performs semantic inlining, which means that it essentially