<p>What design restrictions inform a language having / having a useful whole-program optimizing compiler?</p>
<p>I'm aware that Standard ML has a whole-program optimizing compiler implementation in <a href="http://www.mlton.org/" rel="noreferrer">MLton</a>. 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.</p>
<p>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?</p>

<compilers><optimization><standard-ml>
What design choices inform whether a whole-program optimizing compiler is possible?
CC BY-SA 4.0
2024-11-05T18:43:53.657Z
Unclear whether your premise is accurate; whole-program optimization is supported [in LLVM under the name "link-time optimization"](https://llvm.org/docs/LinkTimeOptimization.html), and thus common across many popular programming languages, some of which (e.g. C) don't have module systems at all.
Sam Estep
CC BY-SA 4.0
2024-11-05T19:13:15.057Z
Oh, that's interesting!
apropos
CC BY-SA 4.0
2024-11-05T19:33:44.270Z
I'd take the opposite tack from Sam -- for me it is unclear whether your premise is correct because I would (perhaps naively) think that the design of ML's module system -- in particular, functors -- would make it *harder* to build a whole-program analyzer, not *easier*. Can you say a little more about this thing that you heard? Who did you hear it from and what claim were they making?
Eric Lippert
CC BY-SA 4.0
2024-11-05T19:50:42.660Z
The obvious limitation is that for a whole program optimizer, the whole program must be available to the optimizer. So, if your optimizer runs before the whole program is available, you can't do whole program optimization. This means that, for example, an ahead-of-time compiler cannot perform whole program optimization in a language with dynamic code loading.
Jörg W Mittag
CC BY-SA 4.0
2024-11-05T21:26:33.527Z
@EricLippert It was communicated to me verbally and I've since forgotten the details, unfortunately. It was something about the module system making it explicit about what requires what, and something about how modules are instantiated, and something about imports of the kind `id : T -> T` (for example) being able to be optimized out.
apropos
CC BY-SA 4.0
2024-11-06T01:01:34.037Z
The design choice that definitions have to precede uses (modulo various kinds of recursive definitions of course) has a lot of impact on how you build a compiler, and on the developer experience. But I don't know that it has much to do with whole-program analysis. Jörg's point is I think the more germane one: the compilation model in which a compiler produces standalone executables rather than libraries of types and functions is a precondition for this kind of analysis.
Eric Lippert
CC BY-SA 4.0
2024-11-06T04:02:17.857Z
@JörgWMittag (but of course you don't have to build an 'ahead-of time compiler'; that's an implementation issue, not something affected by the language at all)
Moonchild
CC BY-SA 4.0
2024-11-06T11:55:20.333Z
LLVM can do link-time optimisation, although in some languages this might be after some information (e.g. about preconditions, postconditions and invariants) has been discarded in an earlier stage. For a practical example, Rust has strict rules about pointer aliasing, which `rustc` uses to perform certain optimisations that I doubt LLVM would be able to do (since it doesn't know about Rust's rules).
kaya3
<p>Designing a <em>language</em> 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.</p>
<p>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.</p>
<p>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).</p>
<p>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 &quot;compiler&quot; is really just a compiler front-end, and the other thing is basically an entire compiler back end + linker.</p>
<p>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.</p>
<p>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).</p>
<p>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.</p>
<h3>Summary</h3>
<p>It's not really about the design of the language itself. It's almost all about the design of the module system.</p>
<p>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.</p>

CC BY-SA 4.0
2024-11-30T03:18:05.680Z
2024-11-30T03:18:05.680Z
Jerry Coffin
<p>Whole program optimization is an umbrella term for various types and techniques of optimizations that may generate effects beyond &quot;local&quot; optimizations -- that is, optimizations that the compiler applies to delimited contexts, such as file level, translation level or module/namespace level.</p>
<p>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 <a href="https://llvm.org/docs/LinkTimeOptimization.html" rel="nofollow noreferrer">LLVM Link Time Optimization: Design and Implementation</a>, and I also suggest reading about incremental compilation and the associated metadata in this other context.</p>
<h4>Metadata for dropping</h4>
<p>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.<sup>1</sup></p>
<p>To be able to optimize the whole program by <em>dropping</em> all unnecessary code, the distributed compiled library needs to be annotated with enough metadata to make this possible.</p>
<p>For example, the library defines the functions <code>a()</code>, <code>b()</code>, and <code>c()</code>, and the program code only explicitly calls <code>a()</code>. But if <code>a()</code> internally calls <code>b()</code>, there is enough metadata to the compiler to drop only <code>c()</code>.</p>
<h4>Metadata or source code for inline</h4>
<p>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.</p>
<p>Here, it's possible to see some impacts on language specifications or expectations. For example, placing a breakpoint on one leaf function will <em>not</em> pause at <em>all</em> invocations of this function, as some (most? all?) call sites may be replaced by the optimizing compiler.</p>
<p>That said, in whole program optimization you may <em>want</em> this duplication and mutation to occur outside the defining locus of the function, <em>after</em> the library is compiled and deployed.</p>
<p>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.</p>
<p>This &quot;duplicated for optimization&quot; 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.</p>
<h4>Source code only, all way down</h4>
<p>This may sound extreme, but there is a sense that de C++ Standard <em>Template</em> 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.</p>
<p>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 <em>re</em>compile the already compiled sources, without needing to <em>de</em>compile some more complicated metadata or binary format.</p>
<p>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.</p>
<p><strong>TL:DR;</strong> Metadata and source code in binaries, or no binaries at all</p>
<hr />
<p><sup><sup>1 </sup>I tried to find, with no luck, one page describing <em>incremental</em> compilation, possibly about Rust, Swift, Zig or Go, that showed numbers about how many <em>little</em> symbols are necessary for a &quot;Hello world&quot;. I vaguely remembered this page because the intervelaing nature of incremental compilation and inter modular optimizations.</sup></p>

CC BY-SA 4.0
2024-11-06T14:54:28.460Z
2024-11-06T15:04:15.557Z
2024-11-06T15:04:15.557Z
André L F S Bacci
<p>It's easier to design a language for whole-program compilation, it's the modular compilation that is more tricky.</p>
<p>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.</p>
<p>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.</p>
<p>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 <a href="https://github.com/IntelLabs/flrc" rel="nofollow noreferrer">The Functional Language Research Compiler</a> (whole program).</p>
<p>I don't know any features that would require the compilers to do one or the other.</p>
<p>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.</p>
<p>Dart SDK is a whole-program compiler, and its solution to this is to ship pre-analyzed and desugared &quot;platform&quot; files for the standard libraries. So you don't parse, type check etc. the standard library code every time.</p>
<p>However code generation is always done for the whole program. That's why I sometimes call it &quot;whole-program code generation&quot; rather than &quot;compilation&quot;.</p>
<p>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.</p>

CC BY-SA 4.0
2024-11-06T19:50:14.597Z
2024-11-07T18:54:23.480Z
2024-11-07T18:54:23.480Z
osa1
CC BY-SA 4.0
2024-11-10T16:56:45.397Z
I would note that while it's easier to design for whole-program compilation, it can be relatively hard to implement a compiler which can actually compile a program as a whole, as that program's code (and dependencies) grow.
Matthieu M.
# What design choices inform whether a whole-program optimizing compiler is possible?
Posted by: username_0 on 2024-11-05
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](http://www.mlton.org/). 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?
**Tags:** compilers optimization standard-ml
> **Comments:**
> **username_1**: Unclear whether your premise is accurate; whole-program optimization is supported [in LLVM under the name "link-time optimization"](https://llvm.org/docs/LinkTimeOptimization.html), and thus common across many popular programming languages, some of which (e.g. C) don't have module systems at all.  
> **username_0**: Oh, that's interesting!  
> **username_2**: I'd take the opposite tack from Sam -- for me it is unclear whether your premise is correct because I would (perhaps naively) think that the design of ML's module system -- in particular, functors -- would make it *harder* to build a whole-program analyzer, not *easier*. Can you say a little more about this thing that you heard? Who did you hear it from and what claim were they making?  
> **username_3**: The obvious limitation is that for a whole program optimizer, the whole program must be available to the optimizer. So, if your optimizer runs before the whole program is available, you can't do whole program optimization. This means that, for example, an ahead-of-time compiler cannot perform whole program optimization in a language with dynamic code loading.  
> **username_0**: @EricLippert It was communicated to me verbally and I've since forgotten the details, unfortunately. It was something about the module system making it explicit about what requires what, and something about how modules are instantiated, and something about imports of the kind `id : T -> T` (for example) being able to be optimized out.  
> **username_2**: The design choice that definitions have to precede uses (modulo various kinds of recursive definitions of course) has a lot of impact on how you build a compiler, and on the developer experience. But I don't know that it has much to do with whole-program analysis. Jörg's point is I think the more germane one: the compilation model in which a compiler produces standalone executables rather than libraries of types and functions is a precondition for this kind of analysis.  
> **username_4**: @JörgWMittag (but of course you don't have to build an 'ahead-of time compiler'; that's an implementation issue, not something affected by the language at all)  
> **username_5**: LLVM can do link-time optimisation, although in some languages this might be after some information (e.g. about preconditions, postconditions and invariants) has been discarded in an earlier stage. For a practical example, Rust has strict rules about pointer aliasing, which `rustc` uses to perform certain optimisations that I doubt LLVM would be able to do (since it doesn't know about Rust's rules).  
---
## 3 answers
### Answer by username_8 on 2024-11-06. Score: 8 | Accepted answer
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](https://github.com/IntelLabs/flrc) (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.
> **Comments:**
> **username_9** (2024-11-10): I would note that while it's easier to design for whole-program compilation, it can be relatively hard to implement a compiler which can actually compile a program as a whole, as that program's code (and dependencies) grow.  
---
### Answer by username_6 on 2024-11-30. Score: 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 by username_7 on 2024-11-06. Score: 0
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](https://llvm.org/docs/LinkTimeOptimization.html), 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.1

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 *re*compile the already compiled sources, without needing to *de*compile 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.
---
