What design choices inform whether a whole-program optimizing compiler is possible?

Question

What design restrictions inform a language having / having a useful whole-program optimizing compiler?

I'm aware that Standard ML has a whole-program optimizing compiler implementation in MLton. I have heard that this is an impressive feat of engineering, and I have heard that the ability to do this has something to do with the design of its module system.

But what is it exactly? What about the module system lends itself to this being a reasonable attempt to make? Are there other features of Standard ML - and other languages with whole-program optimizing compilers, though I'm not aware of any - that affect whether this is a reasonable approach to take?

Answer 1

It's easier to design a language for whole-program compilation, it's the modular compilation that is more tricky.

A whole program compiler will always have more information than a modular one, which will look at one compilation unit (e.g. a module) at a time.

To be able to compile one module in isolation, a modular compiler needs to know various things about the dependencies, like the types of functions called, and memory layouts or size of the types. These information need to be generated before the compilation, and different languages have different file formats to store these information: GHC generates .hi files of modules, OCaml has its own header file format .mli, C and C++ use header files and include information about the dependencies textually in the compilation unit using the C preprocessor.

In practice though, I think most languages can be compiled as whole program or modularly. For SML, we have SML/NJ (modular) and MLton (whole program). For Haskell, we have GHC (modular) and The Functional Language Research Compiler (whole program).

I don't know any features that would require the compilers to do one or the other.

On the more practical side of things: pure whole-program compilation is not feasible as it takes a long time to compile even the simplest programs. A practical language will have thousands of lines of standard library, and applications can have hundreds of dependencies. You can't parse, type check, desugar, analyze ... all of the code all of the time.

Dart SDK is a whole-program compiler, and its solution to this is to ship pre-analyzed and desugared "platform" files for the standard libraries. So you don't parse, type check etc. the standard library code every time.

However code generation is always done for the whole program. That's why I sometimes call it "whole-program code generation" rather than "compilation".

Since one of the comments mention dynamic code loading: it's mostly an orthogonal concept. Most languages need to call libc and other system libraries via C ABI. In the worst case you can load parts of the program as opaque code compiled to C ABI. There are other ways too. Dart SDK is a whole-program compiler, but it supports dynamic loading (where parts of the program is loaded on demand). There's also some experimental code in the VM that can load not just modules of the program, but code generated in a separate compilation step.

Answer 2

Designing a language to allow whole program optimization is pretty easy. In fact, there's no real difference from just designing a language, at least as a rule.

If you just want whole program optimization, you basically dump everything into a single source file then compile and optimize it all together. The internals of the compiler are non-trivial, but as far as overall design goes, it's pretty basic and straightforward.

Likewise, if you just want modularity, you compile pieces of code, store the object files, and link them in as needed. Again, mostly pretty simple and straightforward--to the point that it's been pretty much the default way things have been done since the 1960's or so (longer than that in some cases).

You only run into difficulty when/if you try to combine the two. Compiled modules normally don't have source code for the compiler to work with while optimizing. One way to do this is put some representation of the compiler's IR into each compiled module. In this case, your "compiler" is really just a compiler front-end, and the other thing is basically an entire compiler back end + linker.

Another possibility is to compile to some sort of byte-code, then when/if you want to optimize, you basically reverse engineer IR from the byte code, do your optimization on the IR, then generate your final code. Not exactly the cleanest way to do things, but works reasonably well.

Likewise, if you want to badly enough, you can undoubtedly compile to machine code, reverse engineer IR from the machine code, and proceed from there. I'm not sure whether they're still being developed, but I've seen a couple of projects that reverse engineered machine code to LLVM IR. If memory serves, one dealt with ARM machine code, and a couple of others with x86 machine code (if memory serves, the x86 ones were mcsema and revgen; can't recall the name of the ARM one, but some searching will probably turn it up).

Of course, if you're planning on a module system that supports whole-program optimization, the obvious choice is to include something in your module that's easy to optimize.

Summary

It's not really about the design of the language itself. It's almost all about the design of the module system.

The main question involved is what you include in a module--specifically including something that's fairly easy to optimize, rather than just machine code that you'll probably need to reverse engineer to IR before you can do much with it.

Answer 3

Whole program optimization is an umbrella term for various types and techniques of optimizations that may generate effects beyond "local" optimizations -- that is, optimizations that the compiler applies to delimited contexts, such as file level, translation level or module/namespace level.

Below I will try to show some of these types of design choices that the compiler (and not the language) may exhibit in implementing whole-program or link time optimizations, and how these design choices may or may not impact the language specification or expectations. The examples below are wonderfully detailed in the already mentioned LLVM Link Time Optimization: Design and Implementation, and I also suggest reading about incremental compilation and the associated metadata in this other context.

Metadata for dropping

Say, the standard library defines a lot of types and functions, but one particular program may only need a fraction, less than 1% of all this code base.¹

To be able to optimize the whole program by dropping all unnecessary code, the distributed compiled library needs to be annotated with enough metadata to make this possible.

For example, the library defines the functions a(), b(), and c(), and the program code only explicitly calls a(). But if a() internally calls b(), there is enough metadata to the compiler to drop only c().

Metadata or source code for inline

You note that the compiler and code base uses a lot of leaf, simple and small functions, a sweet spot for inlining. So a module or library may have these public functions compiled and published, but there is the possibly of inlined functions to be duplicated all over the place, as copied and optimized away in various vestigial forms.

Here, it's possible to see some impacts on language specifications or expectations. For example, placing a breakpoint on one leaf function will not pause at all invocations of this function, as some (most? all?) call sites may be replaced by the optimizing compiler.

That said, in whole program optimization you may want this duplication and mutation to occur outside the defining locus of the function, after the library is compiled and deployed.

For this to occur, the compiled library also needs to exhibit some duplication itself, so that the compiler then can further replace outside calling sites with more duplicated and mutated copies of original function.

This "duplicated for optimization" form needs to exist in some pre-compiled or even in embed source form, in a sufficiently high level to permit the compiler to understand and further optimize it away.

Source code only, all way down

This may sound extreme, but there is a sense that de C++ Standard Template Library does: There are no binaries, only source code. I think this also applies to the MLton of the question, because afaik ML language libraries are defined entirely in terms of pure source code, sprinkled with few compiler intrinsics as necessary.

In a language and standard library designed this way, having any binary library always embed with their source counterparts, would facilitate whole program optimizations as the compiler may then choose to try recompile the already compiled sources, without needing to decompile some more complicated metadata or binary format.

In this last example, the difference between modular compilation and whole-program optimization may end blurred, but in a sense, whole-program optimization is a form of whole-program recompilation, in a latter time.

TL:DR; Metadata and source code in binaries, or no binaries at all

---

^{1 I tried to find, with no luck, one page describing incremental compilation, possibly about Rust, Swift, Zig or Go, that showed numbers about how many little symbols are necessary for a "Hello world". I vaguely remembered this page because the intervelaing nature of incremental compilation and inter modular optimizations.}