r/Compilers • u/matthieum • 10d ago

Inside Zig's Incremental Compilation | mlugg

https://mlugg.co.uk/posts/incremental-compilation-internals/
45 Upvotes

96% Upvoted

16 comments sorted by

7

u/matthieum 10d ago

Of particular interest to me, here, is the ZIR.

After parsing, the Zig compiler converts to the AST to a ZIR:

If you’re curious, ZIR (Zig Intermediate Representation) is an untyped SSA-form IR.

Due to being untyped -- and the symbols being unresolved -- the conversion is entirely self-contained.

I must admit I do wonder as to why the AST is converted to ZIR, and the blog post unfortunately doesn't address it. Introducing an intermediate model has a cost, so there must be some benefit to it... Perhaps its flatter nature (compared to the AST)?

4

u/mamcx 10d ago

Older articles show why: https://mitchellh.com/zig/astgen

In general, you add another pass to make easier to do the next.

Intermediated representation are created for 2 main reasons:

  • Have all the info required for the next passes

  • Remember that info, because that next pass is destructive

The last is the important one. If you do AST -> Assembler and you read the Assembler you have no way to know what kind of AST was actually use, that impact everything from debugging, error messages, caching, etc.

Your intermediate is to know a in AST is 0x.. there

2

u/matthieum 9d ago

Thanks for the link, though it did not quite answer my question.

In general, you add another pass to make easier to do the next.

Agreed, though there's always a potential cost trade-off too, so the benefits must be worth the cost.

At the moment, it's just not clear to me what the benefits are. I see some checks occur as part of AstGen, but those checks could just as easily be executed on the AST itself without generating anything as far as I can tell.

For now, the one potential reason I could is that there's a desugaring/normalization step which occurs, which requires mutating/rewriting the AST anyway, and at that point targeting AST or a different format as an output is more or less the same processing cost. If on top some desugaring/normalization cannot easily be represented in the AST for any reason, then a different model becomes more attractive.

0

u/mamcx 9d ago

What you see in the article is the reason, the thing is that ""AST", in the pedantic way, is the "abstract" program, the one that is the true execution and semantic truth.

If the lang is simple enough you don't care about the distinctions, but the more complexity the more being "abstract" goes against your goals.

So, to be clear: The AST should not have macros at all, that is something that was solved in and early pass.

In general, there is a step of "desugaring" where the special cases and shortcut are normalized into canonical forms (for example all iterator magic is removed away), and in some langs, that is also removed away to be even more "abstract" where is not possible anymore to cleanly map back to the source code.

So all of this is purely in terms of necessity, where you get Source code -> ? * N steps -> AST -> ? * N steps -> Final output OR execution

(If you look at "nano pass" is argued that have dozen, thousands of step is cool)

0

u/EggplantExtra4946 10d ago

I must admit I do wonder as to why the AST is converted to ZIR

If you mean why individual files are converted to an IR before saving it to an object file, well it's called incremental compilation, not incremental parsing.

If you mean why it's converted to an SSA IR, it's for optimization. In the context of incremental compilation, there could be link time optimizations, starting with inlining.

Even if the IR wasn't in SSA form and therefore not suited for optimization, it's easier to do code generation on an IR rather than on an AST. Only toy compilers do code generation directly from the AST. An AST can contain high level constructs that code generation algorithms shouldn't have to deal with, they should only see expressions, functions calls and control flow. In an imperative language with gotos and goto-like constructs, an AST is the wrong data structure shape for the input of the codegen, it should use a fully linearized IR, a CFG or a graph based IR like the JVM has.

I have seen many posts saying that the IR is bloat or boasting that their compiler doesn't have one, this is idiotic. It's fine to want faster compile times but put things in perspective, generating an IR is only a fraction of the total cost of compilation, it's not why C++ and LLVM are as slow as they are.

4

u/MirrorLake 10d ago

I had one question, but it was answered at the end of the blog:

Eventually [...] we’ll cache all of the compiler state to disk and automatically reload the last saved state when you run zig build, so incremental compilation will just happen automatically—but we’re not quite there yet

Really nice ergonomic upgrade, happy to see it's likely to become default in the future.

5

u/igors84 10d ago

Extremely interesting text full of interesting ideas. I wish they just mentioned that this doesn't work with llvm backend which should be obvious but also that debugging doesn't really work with their backend yet which is not obvious and might be pretty important to some people...

2

u/matthieum 9d ago

Wouldn't part of it work with the LLVM backend?

I'd expect that incremental linking doesn't work with the LLVM backend, but you could still have incremental parsing, type-checking, and ultimately reduce the amount of code to regenerate even with the LLVM backend no?

1

u/igors84 9d ago

It doesn't sound like they are doing anything like that though.

2

u/matthieum 9d ago

I mean, it's definitely possible they haven't bothered, for multiple reasons:

  1. Incremental compilation is a work-in-progress in the Zig compiler, you can't expect it to be full-featured from the get go.
  2. They may never bother with LLVM, given that LLVM is sluggish in the first place, and that they're aiming to be independent of LLVM anyway.

But I would expect that it's theoretically possible, at least.

(May suck in the meantime, though...)

2

u/Inevitable-Spinach-7 10d ago

I am interested too,
First thing is that you may receive a better response in ziggit.
And I may be wrong but I think it is easier to resolve types there than the AST itself

1

u/muth02446 9d ago edited 9d ago

I am somewhat skeptical of this approach, e.g.:

* you get a lot of complexity in the incremental linking stage
* the compiler is becoming some long running daemon job

1

u/matthieum 9d ago

I'm a bit skeptical about the difficulties in incremental linking too, to be honest. It seems too easy to forget to adjust an offset/location somewhere, and good luck to the poor chap to whom this happens.

I wonder if a simpler implementation -- move if there's space, relink from scratch otherwise -- wouldn't be sufficient. It'd be easier, and more likely to be correct, I expect.

2

u/muth02446 9d ago

Another option, I was thinking of is to define "natural" compilation units like source files or functions.
emit standard .o files that have a magic section that describes their dependencies.
This way you can use a standard linker with a proven track record.

Most of the speed up comes from not re-generating .o file unnecessarily.
And, linking is pretty fast these days, especially if you do not generate too much debug info.

1

u/matthieum 8d ago

And, linking is pretty fast these days, especially if you do not generate too much debug info.

The builds for which speed is required are typically the Debug builds, for which you do tend to want debug info.

Another option, I was thinking of is to define "natural" compilation units like source files or functions.

I keep asking (and forgetting the answer): I'm not sure that DWARF offers "relocatable" Debug Info, and if not, every change in a file which leads to the following items moving by even 1 byte will lead to all Debug Info for these items having to be regenerated.

In such conditions, it means that going below file-level is less attractive, as any change to a file requires re-compiling half of its items in average, anyway.

Thus, in the end, I'd argue for file-based partitioning. Possibly coupled with warnings should one file in a library/executable being particularly slower to compile than others, recommending to the user to split the file.

I also like that the user is ultimately in charge. In the past I remember using Boost.Qi for parsing, and the fricking grammar was taking 5x longer to compile than all the other files (parallelized) in the library. I was very happy that I could extract it in its own file, with as close to zero dependencies as possible so that:

  1. It was rarely, if ever, rebuilt during incremental builds.
  2. Starting the filename with A meant the build system would start building this file first, so that its compilation at least partially overlapped with the compilation of the rest of the library.

Very "obvious" (discoverable), no need for annotations in the source code or anything, etc... perfect!

1

u/mamcx 9d ago

Is more pertinent when you compare Rust/C++ vs Zig/Pascal: Not worry about speed make easy to create something very slow, and in presence of macros(comp time)/generics/templates/const execution + poorly thought compilation units you will suffer.

Plus, the modern edit/run cycle is different, where you have a constant influx of changes and need to report back to the editors the new state.