In the example with the shown dependency graphs, it says that we change the first line from const lucky_number = 42; to const lucky_number = 43; in the text, but this is not reflected in the graph (it stays with the value 42), only the invalidation.
Why?
About the linking part: Shouldn’t relocatable executable code be helpful here for parallelisation?
No particular reason, I just didn’t think to change it to be honest. It probably would be more accurate if it were changed to 43 there, sorry if that was confusing to you!
I assume you’re talking about position-independent code (PIC & PIEs)? Not to be pedantic, it’s just that the term “relocatable” has a specific meaning in ELF—it basically means “object file”—which isn’t really relevant here!
Assuming that is what you mean: it doesn’t actually help that much, because PIC almost always works by replacing absolute addresses with offsets from the “current” address to the “target” address. Those offsets still change if if you rearrange your binary’s address space, so we still need to update relocations in the linker! For instance, on x86_64, non-PIC code might have an R_X86_64_64 relocation which is an absolute 64-bit address, while in PIC code that might be replaced with R_X86_64_GOTPCREL which is a 32-bit offset to a GOT entry containing an absolute address via a runtime relocation. In fact, that’s actually a bit more work for us to handle!
Ultimately, the work of gluing references to the right addresses needs to happen at some point—either during “static linking” (what most people just call “linking”) or “dynamic linking” (aka “dynamic loading”). In theory the dynamic linker could handle everything, but on ELF at least, it’s standard for dynamic linkers to basically refuse to do anything which the static linker could have done, so most of the work pretty much has to fall on us.
Oh no, what a sneaky move, publishing this when I am at a conference 
Guess I can carve out some time out of tonight’s sleep, exited about the post!
Fantastic post! One question: what determines identity of analysis unit? If I replace my code with something else entirely, there’s no reuse. If I just add a single new function, there’s going to be a lot of reuse. But there’s a continuum of possibilities between two extremes?
What is the heuristic for “this new thing sorta looks like this old thing, so we want to attempt re-use” vs “this is brand-new and must be analyzed from scratch”
And another question: if in my otherwise runtime function I have some comptime computations, like, e.g, xs[0..2+2], would each maximal comptime expression be its own unit?
Great read, thank you for taking the time to write it! I’m very excited about the part at the end about hot reloading long running applications, specifically for games.
I remember discussing incremental compilation for a language I was involved with, with a colleague once. Over the course of half an hour we both realized how difficult it would be.
Thanks, glad you liked it!
(Replying to this question first because it’s simpler!)
comptime evaluation all happens within the analysis unit of the caller. This is kinda necessary because of the fact that comptime-mutable state can be shared across different comptime expressions (e.g. by passing around pointers to comptime vars). So if you have a really complicated comptime function call, and you change just one part of it, the whole thing will get re-analyzed. In some languages this might not be granular enough, but I think it works okay in Zig, because IMO the language has introduced juuuust enough friction to stop people going too crazy with comptime, whereas I’ve heard from Rust users that fully re-evaluating Rust macros whenever they might change would be hideously expensive in some cases. (Also, the speed of comptime evaluation is also something we want to improve quite significantly in general, so that’ll help improve this.)
Ah yes—this is something I ended up skimming over a bit because it felt a bit too “in the weeds” (and the Semantic Analysis section was already quite long!). In short, this is based on how we correlate instructions between the old and new ZIR for a file. If we think an old ZIR declaration maps to a new ZIR declaration, then analysis units which come from that declaration are assumed to now be based on the new declaration.
So, how do we actually do that mapping? The things we need to map are basically container type declarations (struct { ... } / union { ... } / enum { ... } / opaque { ... }), and the declarations in their namespaces. Our implementation is based on some pretty straightforward heuristics:
-
The really easy part: when we have decided that two container type declarations (
struct { ... }or whatever) map to each other, we consider the namespaces of both of those types, and correlate declarations within those namespaces by name. For instance, ifstruct { const foo = 123; }is known to map tostruct { fn foo() void {} }, we will map thatconst foodeclaration to thefn foodeclaration, because they are named declarations with the same name.Named tests and named decltests are also mapped like that, although they have their own “namespaces” for the mapping process.
Unnamed tests are correlated based on order—we map
old_unnamed_tests[0..n]tonew_unnamed_tests[0..n], wheren = @min(old_unnamed_tests.len, new_unnamed_tests.len). We do the same forcomptimedeclarations. -
When we have decided that declaration
old_zir.Amaps tonew_zir.A, we traverse the bodies of those, and build a list of all the container type declarations in each one. This traversal recurses into everything except other namespaces—e.g. if you have this:const A = struct { x: enum {}, const other = union {}; };…then traversing
Awill build a list including thestruct_declZIR instruction and theenum_declZIR instruction, but not theunion_declZIR instruction, because we don’t recurse into thestruct/enumtypes’ namespaces for now (even though we do recurse into their fields).Anyway, once we have these lists
old_container_typesandnew_container_types, we just mapold_container_types[0..n]tonew_container_types[0..n]forn = @min(old_container_types.len, new_container_types.len), just like how we dealt with unnamed tests andcomptimedecls within a namespace.(There’s actually one more caveat here, which is that we can’t map e.g. a
struct_declto aunion_decljust because it would confuse later parts of the pipeline, so we just refuse to do mappings like that.)This is definitely the messy part of the heuristic, and one that could easily be improved if we want. You can probably immediately think of ways to do that—our approach almost completely ignores the structure of the code! That said, we get surprisingly far with this heuristic alone, because even if the mapping goes wrong, the Zig compiler is actually decently fast even at semantic analysis (even though it often doesn’t feel it in clean builds because of just how much standard library code you pull in).
…okay, that was surprisingly long to explain, but I promise it’s not too complicated! The code that does this mapping is here if you want to look at it—I think it’s faiiiirly possible to understand without heavy knowledge of compiler internals and I’m happy to clarify how any of it works.
If you build a debug compiler (-D, you can use zig changelist old.zig new.zigto see the ZIR instruction mappings, and to make any sense of those you can usezig ast-check -t` to see the actual ZIR. So:
//! old.zig
bar: struct {},
const A = struct { inner: enum {} };
//! new.zig
foo: struct {},
const A = struct {
inner: Inner,
const Inner = enum {};
};
$ zig ast-check -t old.zig
# Source bytes: 65B
# Tokens: 20 (124B)
# AST Nodes: 7 (219B)
# Total ZIR bytes: 365B
# Instructions: 8 (72B)
# String Table Bytes: 13
# Extra Data Items: 54 (216B)
%0 = extended(struct_decl(hash(8ca19e388b512c5034dc397073dc7762) parent, auto, {}, {
%3 = declaration(const 'A' line(2) column(0) hash(2689df32c85f50f51d8b39f16fe44772) value={
%4 = extended(struct_decl(hash(66b55941322d2ef94880aa8b4125eb0f) parent, auto, {}, {}, {
inner: {
%5 = extended(enum_decl(hash(af1349b9f5f9a1a6a0404dea36dcc949) anon, {}, {}, {}) node_offset:3:27 to :3:34
%6 = break_inline(%4, %5)
},
}) node_offset:3:11 to :3:36
%7 = break_inline(%3, %4)
}) node_offset:3:1 to :3:36
}, {
bar: {
%1 = extended(struct_decl(hash(00000000000000000000000000000000) anon, auto, {}, {}, {}) node_offset:2:6 to :2:15
%2 = break_inline(%0, %1)
},
}) node_offset:1:1 to :1:1
$ zig ast-check -t new.zig
# Source bytes: 95B
# Tokens: 26 (154B)
# AST Nodes: 9 (245B)
# Total ZIR bytes: 454B
# Instructions: 11 (99B)
# String Table Bytes: 19
# Extra Data Items: 68 (272B)
%0 = extended(struct_decl(hash(15ab49c484c832a791bab453a273f5ab) parent, auto, {}, {
%3 = declaration(const 'A' line(2) column(0) hash(ae6fc0247993c7ab2cf8e07e0ede0be4) value={
%4 = extended(struct_decl(hash(738e1ffa7b7418908ed6ff317da3e9e2) parent, auto, {}, {
%7 = declaration(const 'Inner' line(4) column(4) hash(7cd6d18c949481924a148c8f19006610) value={
%8 = extended(enum_decl(hash(af1349b9f5f9a1a6a0404dea36dcc949) parent, {}, {}, {}) node_offset:5:19 to :5:26
%9 = break_inline(%7, %8)
}) node_offset:5:5 to :5:26
}, {
inner: {
%5 = decl_val("Inner") token_offset:4:12 to :4:17
%6 = break_inline(%4, %5)
},
}) node_offset:3:11 to :3:17
%10 = break_inline(%3, %4)
}) node_offset:3:1 to :3:6
}, {
foo: {
%1 = extended(struct_decl(hash(00000000000000000000000000000000) anon, auto, {}, {}, {}) node_offset:2:6 to :2:15
%2 = break_inline(%0, %1)
},
}) node_offset:1:1 to :1:1
$ zig changelist old.zig new.zig
Instruction mappings:
%4 => %4
%1 => %1
%0 => %0
%3 => %3
Oh, this one’s nice and simple because the numbers are the same! Going through these mappings:
%0, in both cases, refers to the implicitstruct { ... }around the whole file. This mapping always exists, because it’s how we begin the process!%1refers to thestruct {}in the top-level field. Notice how even though we renamed the field, this mapping still happened, because fields are not declarations so they just go through the dumb in-order traversal.%3refers to the declaration namedA, which was mapped because they’re both named A. If the declaration had changed names, this mapping (and consequently also the mapping for%4) wouldn’t be there.%4refers to thestruct { ... }inside ofA, which makes sense, because in both cases it’s the first thing we see doing an in-order traversal of the body ofA.- Notice how the
enum{}is not mapped—that’s because it was previously in a field of the struct (meaning it would have been a part of the in-order traversal ofA), but was moved into a declaration, which is mapped separately.
(By the way, it seems like zig changelist accidentally works in release compilers… oops! But you still need a debug compiler for zig ast-check -t :P)
I’ve enjoyed the article, thank you. One question - is there any (even abstract) ETA for the ARM backend? I know you are all using Linux but I think there are also lots of people using macos, and we can’t wait to try it out too 
I’m afraid I’m not going to give a concrete ETA, because it’d probably be super wrong (I’m bad at this kind of time estimate!), and I also don’t want to put pressure on the rest of the team. That said, I can tell you that it’s something I’ve been actively discussing with Jacob, and which I want to make progress on ASAP. I think we want to get debug information implemented for x86_64 incremental first, because that will further improve our workflows (and so it’ll be easier for us to work on the aarch64 backend!), but once that’s sorted out, I hope to focus in on the aarch64 backend and collaborate with Jacob on getting it usable as fast as possible. We also need to work on a new incremental Mach-O linker for macOS support—it’ll probably be me doing that, and I plan to work on it imminently (possibly even within this release cycle, though it won’t be very useful until the aarch64 backend works!). Hopefully, some level of incremental compilation will be available on aarch64-macos, not in the current release cycle, but in the one following it (i.e. 0.18.0).
Aha, this makes sense, but still leaves a big mystery: how comptime figures in the picture? If we have something like
fn FooType(T: type, comptime n: u32) type {
// some code here
return struct {
// more code there
};
}
Do we have one analysis unit here for the struct? Or do we have a separate analysis unit for each value of T reachable?
Banger posts, thanks for all the insights.
Just want to give praise as well. Absolute fantastic post, I learned a lot and found many things which I should learn more about (as in, they passed way over my head).
Are there any good books or other articles where one could get started with Linkers (I’ve heard that the linker concepts are quite straightforward but the details are where hell resides).
Would this allow Zig to support incremental compilation of C and C++ eventually?
I had been wanting to ask the same question, and make a decision to replace my MacBook M1 with a Framework 13 Pro. However the latter has become so much more expensive since last time I investigated, that I’ll probably reconsider using my Lenovo T480 and wait for 0.18.0 instead.
Zig isn’t a C or C++ compiler (it just calls into an external dependency), so most likely not to the extent that it does Zig. Part of the effectiveness of the techniques in the post takes advantage of carefully designed language constructs that don’t exist or even possible for C/C++.
Every separate instance of the struct (for every distinct T) has a separate analysis unit (assuming that the struct actually captures T, of course!). The compiler knows that the struct { ... } definition captures T, so when analyzing that expression (struct { ... }), it finds/creates a type keyed on <that source location, value of T>; and each distinct type has a distinct analysis unit for type resolution.
What’s working is incremental compilation of a Zig project with C/C++ deps.
I haven’t tried but presumably modifiying a C header that goes to Zig tranlate C, should leverage incremental compilation. Probably not so useful though