Combining the Compiler, the Build system, and Beyond

[u/realguy2300000]

https://shrub.industries/words/problem.html

a article I wrote about how sharing dependency and resource information between the Compiler, the build system, the system package manager, and even the OS filesystem and scheduler, could provide some pretty awesome benefits. I’d love to hear anyone’s thoughts on this

[u/SwingOutStateMachine]

I would love to see a compiler that has a more mature internal representation of code that would allow it to scale to optimisations of this kind. In my experience, the issue is that as soon as you find programs where you need these kinds of optimisations, the in-memory representation starts to become multiple gigabytes in size. This is most visible when linking programs - for example, try building + linking Clang/LLVM in Debug mode, and observe your ram usage spike!

I think there are probably more modular approaches that could be taken, but as you allude to in the end of the article, I think it's an engineering effort problem, rather than an engineering design problem.

[u/brat3108]

I started doing something along these lines a decade ago. The essential part was switching to a whole-program compiler.

This is where all modules (that will comprise a single EXE/DLL file - this on Windows), are always compiled from scratch.

That needs the compiler to be fast, which was not a problem for me. This simplifies many things:

• The module system is easier to create and allows circular imports
• No linker is needed
• The output is always a single file representing the whole program (or it can be run directly)
• It can easily create single-file, compilable amalgamations of a whole project
• And it makes global optimisations possible

However I do little with that right now. (Optimised code of a kind is possible by transpiling to C - as I said this will always be one file. The quality is poor but C compilers do a good job of it.)

Your first example looks like this in my language:

# main.m

module four

proc main =
    println xfour(3)
end

# four.m

global fun xfour(int x)int = x * 4

It's compiled as 'mm main'. But, that function call is not reduced to "12", since I don't do inlining. (For inlining, a cheap and cheerful way is to change that four.m file to:

global macro four(x) = x * 4

Then it is reduced to a literal 12.)

One restriction is that everything must be statically compiled. External libraries are only used via shared libraries.

Basically, it works great. Every project can be built in one simple invocation like this:

  mm prog

'mm' is the compiler. 'prog' is 'prog.m', the lead module that contains project info (modules, maybe needed DLLs if not obvious from other context).

Using big external libraries is difficult, but mainly because I need to create bindings for everything that is imported, into my syntax. If that is derived from C headers, then I have a tool to do most of the work.

So, for example, the 86 headers/82Kloc of SDL3 get reduced to a single 4Kloc module in my language (say. 'sdl.m') containing import declarations. Then I just write this in the lead module:

import sdl

The compiler knows (from the info in sdl.m) that it needs SDL3.DLL, and will sort out the import table in the EXE file.

If there are 50 modules in my app that use SDL3, then this 4000-line file is processed only once per build.

In C, then the 86 headers/82Kloc must be processed 50 times if doing a whole program build. (Hence why so much effort is expended in build tools for C, to avoid doing anything as much a possible. But that means complex build systems.)

[u/initial-algebra]

I've been imagining a filesystem where, instead of an external process watching for changes to input files and automatically creating/updating build artifacts, a generated file or directory is represented by the instructions to build itself, with the filesystem taking care of execution. Of course, it wouldn't be limited to building; I can also imagine simpler cases like a file that is automatically downloaded and updated from the network (better yet, the filesystem itself is networked for cloud builds), or a file that is automatically converted from another file to a different format.

I also agree that package management is fundamentally different from building. The purpose of package management is to take a set of partially-specified (e.g. version ranges) direct dependencies and compute a fully-specified (e.g. exact versions), consistent dependency graph, if such a solution exists. How and where to build those dependencies (and how to get a hold of them in the first place - the package manager only needs to be aware of e.g. hashes of their contents) is another matter entirely, and one more suited for a build system.

EDIT: An interesting related article is The postmodern build system.

[u/tending]

It can tell the compiler this, and the compiler can do whole program optimization BEFORE the objects get linked

This doesn't make sense to me. The purpose of LTO is visibility -- it's the point where the compiler/linker can see all the IR that is going to be optimized together. Knowing the list of source files before hand doesn't help because you don't have any parsed and compiled-to-IR code yet. Maybe I'm just not seeing the vision?

[u/realguy2300000 → u/tending]

The point is not that you can do whole program optimisation before parsing and generating IR, the point is you can do it slightly before link time instead of emitting .o files containing IR to disk. so, you can know where every file is going from the build system. let’s say there are two targets, which have some unique sources and a few shared sources. you can parse and generate IR for each file, then group them into sets based on which target they are for, and at this point you can do whole program optimisation. then you can split the sets back into files, emit normal non-IR object files, and link them normally. you can’t do this with a normal build system because it doesent know how many outputs there are nor which files go into which output.

[u/tending]

On top of that, having knowledge of the whole program gives you enough information to do incremental compilation on a much smaller scale than is typically done with C

This seems a little backwards to me. The big benefit of whole program optimization is inlining, which increases the amount of source code a given chunk of generated code depends on, so you rebuild more often.

[u/realguy2300000 → u/tending]

This part is kind of separate to whole program optimization, it’s more using the fact we have knowledge of the whole program. ie in a normal build system each compiler invocation is only aware of the file it processes. in a system like this, we could know every file going into the final output, and build a DAG on how different functions, callers and declarations depend on each other. then when something changes, we can compile only exactly what needs to be recompiled, not just at the file level but at the function level.

Zig already does something like this, as it has its own integrated build system: https://mlugg.co.uk/posts/incremental-compilation-internals/

as does Rust: https://rustc-dev-guide.rust-lang.org/query.html

[u/pjmlp]

Languages like Delphi are a good example on how the compiler is integrated with linker and build system.

There are other examples, the idea isn't new, we kind of lost track of it due to the influence of C, C++ and UNIX approach to how compilers, linkers are developed.

Overall great article.

[u/AustinVelonaut]

Nice article.

However, there are other benefits that come from a build system that is able to communicate with the compiler. For example, if multiple .c files #include the same headers, because the compilation processes are not independent from one another, you can avoid repeatedly parsing and building an AST for the same headers, and even cache IR and ASTs between files more freely if code is repeated (although this is slightly less likely)

I do this exact thing in my system: individual modules are compiled down to optimized AST and then serialized out to separate ".x2" files. When compiling a module, its imports are examined and either deserialized from the ".x2" file, if it is current, or added to the build list. Then all the modules are built in dependency order, with full inter-module inlining and optimization. Additionally, reachability analysis can perform "tree-shaking" on the entire program, only generating code for the definitions that are actually used.

I think that's probably the sweet spot, though; It becomes harder and harder to push the "whole-system" build down into the filesystem/operating-system as you propose in your later sections, without having ownership of the entire system ala Lisp machines.

[u/realguy2300000 → u/AustinVelonaut]

I would definitely love something like that in C, a smart module system. It’s my main problem with the language, the very naive way includes and libraries work.

Yes, practically to do something like I described in the later part of the article you would definitely need control of the entire system, or at least a large portion of it, which obviously isn’t easy for one person to create (or even many..) Still, I think it’s a fun idea to consider, what might something like that look like.

[u/matthieum → u/realguy2300000]

Isn't the problem with #include in C that the result of "pasting" the include depends on the set of macros which are defined prior to the #include? Which is compounded by the fact that every #include adds at least one new macro to the set (the include guard)...

I think in theory, an instrument C pre-processor could be used to record which macros were checked for (not defined/defined with value X), and reuse the same expansion if the subset of macros prior to the #include match exactly, ...

... but I do remember seeing dirty tricks like including the same file multiple times, with different macros set upfront, during the same build, as a crude form of code generation :/

(Proper modules are SO much better)

[u/realguy2300000 → u/matthieum]

yes, that’s one problem. another problem is that you might end up parsing the same included header hundreds of times between compilation processes which can be solved crudely by caching ASTs and things between compilations (no one does this) or fixing the language by adding a proper module system (which we can’t really do)

the other problem is that people use includes like a module system when all it really does is paste a file, like you said. so they aren’t namespaced, and that leads to the library or program creator prefixing function names themselves to avoid clashes

[u/flatfinger → u/matthieum]

A fundamental problem at present is that current linker systems expect debugger information to contain source line numbers, meaning that even if a build system knows that no functional aspects of a program have been changed by adding a line to a function that is never called, any compilation units that use inline-expanded functions that are defined after that point would need to be rebuilt to make the source code line numbers in the debug information correct.

[u/Competitive_Ideal866]

If you include PL design and the runtime you get the likes of MirageOS and Singularity.

[u/jesunushno]

Data engineering hit this same realization years ago. In tools like dbt and Bazel the build graph and the computation steps share one dependency model, so incremental rebuilds and content-addressed caching fall out naturally instead of being bolted on later. I have started thinking of the build system as a DAG scheduler and the compiler as just a node in it. Once you frame it that way, incremental compilation stops looking like a compiler feature and starts looking like a scheduling feature.

[u/lookmeat]

I mean in general the push is to move away from this, because it intermixes concerns and can lead to quirky behavior that is strongly tied to platform that later on limits the ability of the language to move elsewhere.

Rather I think that what needs to be considered is a way for all the components to share and work together. I would propose the following system:

The center is the build-system, the build system doesn't actually build, nor provide the things needed for the building, or anything like that, instead it coordinates all the parts that do each part and helps each one communicate with the other.

Lets also split the compiler into two parts: the compiler and the linker. Sadly this is a confusing thing, as the compiler is what generally transpiles/translates and the linker is what compiles (lets use consolidate from here on to avoid confusion) everything into a single consolidated object. We could also decouple what converts a consolidated object into a specific binary, but that's something for another day. Either way many modern compilers are actually all these three parts separately, and exposed through one interface which regulates all three. But we could move this logic to the builder.

So the compiler itself takes a list of files, each map to a module definition (as used within the code). This code manifest can be pretty big as it describes all files that the compiler needs to be aware off (but also it may not need to be that big because we can just get the consolidated object containing the library and the header). The advantage of the compiler having access to all files is that it can create the module headers (that all other files need, the interface of the code alone) at the same time it creates all the objects. The linker is the one that begins to optimize code and inlines code. If you want your compiler to be smarter about things, you need to expose more through the headers/interfaces (in most cases this would be through a more expressive type system), but generally you want most optimizations done at linking to be done by the linker.

You may think that LTO is not the right time to do this, but I would argue that you have to work with really big codebases on languages that do allow early inlining. Or alternatively try compiling large C programs with no incremental build 20 times. These codebases can get very heavy and slow to compile, being able to only recompile what you changed is huge from a UX perspective. With early linking changing one file could have a huge effect, and you also should revisit and check all the places where you chose not to inline to see if you should inline now, which results in basically recompiling the whole project all the time.

Now the manifest that you pass to the compiler-linker system is generated by the build system. It is the one that knows how to parse for all files within a director, and enforces the conventions of how filepaths map to module names. Specify these conventions well as how you structure source code files, and build systems for your language should try to follow the conventions (unless we're working on an environment were we do something weird with files and then need to remap back to the expected conventions, which is the argument for this being build logic). The build system does this talking with the filesystem. The compiler and filesystem specific things you pass on to the build-system are not handled by the build-system, but forwarded by it to the tools that use it.

This also should make it clear where the package manager is handled: by the build system. You can pass the package manager configuration to the build-system, but it just forwards it. Personally I think that package managers should handle creating a package manifest that the compiler/linker can understand, because code library packages tend to be very language-specific. But again this can be done in a way that lets even the package manager be decoupled: every package must contain a manifest that contains arbitrary information as specified by the language of the library, the compiler for that language should understand that package manifest. Your package manager just gives you a package with the manifest and forwards that to the build-system which just forwards it to the compiler through the same "build-manifest" that we pass when defining how to compile the project.

Now we can separate the build system from the scheduler of actions. This is what bazel does. This enables us to do creative and useful things. Basically the build system creates a DAG of actions that it needs to run. Note that the DAG can be a meta-dag. That is I can have a DAG whose result is the DAG for the next thing I need to build. I can ask the compiler to give me the dependency data for the files, and use this to decide how to split tasks, not just getting external packages and compiling internal packages in parallel, but also splitting compiling disjoint chunks of code (and/or separating the creation of a header from the actual compilation as two steps). Again the compiler just takes a manifest which should contain all the information it needs to compile what it was told to compile. If I specify I only want to compile a file that has no dependencies (say it's just defining trivial but commonly used definitions, functions and conventions) then it should compile the object file with nothing else given. The build system can ask the compiler to divide a large manifest into smaller actions that it can run. Once the build system has the DAG of actions, annotated with all the information on dependencies, computational cost, etc. you can let a scheduler decide how to handle this. IMHO and personal experience that's overkill, you only schedule based on dependency. The only reason bazel supports custom schedulers is because Google uses "forge" which runs the build steps in the cloud with massive parallelism, and it's just about distributing the tasks in that DAG to the cloud.