README.md
1# Partial evaluation of initialization code in Go
2
3For several reasons related to code size and memory consumption (see below), it
4is best to try to evaluate as much initialization code at compile time as
5possible and only run unknown expressions (e.g. external calls) at runtime. This
6is in practice a partial evaluator of the `runtime.initAll` function, which
7calls each package initializer.
8
9It works by directly interpreting LLVM IR:
10
11 * Almost all operations work directly on constants, and are implemented using
12 the llvm.Const* set of functions that are evaluated directly.
13 * External function calls and some other operations (inline assembly, volatile
14 load, volatile store) are seen as having limited side effects. Limited in
15 the sense that it is known at compile time which globals it affects, which
16 then are marked 'dirty' (meaning, further operations on it must be done at
17 runtime). These operations are emitted directly in the `runtime.initAll`
18 function. Return values are also considered 'dirty'.
19 * Such 'dirty' objects and local values must be executed at runtime instead of
20 at compile time. This dirtyness propagates further through the IR, for
21 example storing a dirty local value to a global also makes the global dirty,
22 meaning that the global may not be read or written at compile time as it's
23 contents at that point during interpretation is unknown.
24 * There are some heuristics in place to avoid doing too much with dirty
25 values. For example, a branch based on a dirty local marks the whole
26 function itself as having side effect (as if it is an external function).
27 However, all globals it touches are still taken into account and when a call
28 is inserted in `runtime.initAll`, all globals it references are also marked
29 dirty.
30 * Heap allocation (`runtime.alloc`) is emulated by creating new objects. The
31 value in the allocation is the initializer of the global, the zero value is
32 the zero initializer.
33 * Stack allocation (`alloca`) is often emulated using a fake alloca object,
34 until the address of the alloca is taken in which case it is also created as
35 a real `alloca` in `runtime.initAll` and marked dirty. This may be necessary
36 when calling an external function with the given alloca as paramter.
37
38## Why is this necessary?
39
40A partial evaluator is hard to get right, so why go through all the trouble of
41writing one?
42
43The main reason is that the previous attempt wasn't complete and wasn't sound.
44It simply tried to evaluate Go SSA directly, which was good but more difficult
45than necessary. An IR based interpreter needs to understand fewer instructions
46as the LLVM IR simply has less (complex) instructions than Go SSA. Also, LLVM
47provides some useful tools like easily getting all uses of a function or global,
48which Go SSA does not provide.
49
50But why is it necessary at all? The answer is that globals with initializers are
51much easier to optimize by LLVM than initialization code. Also, there are a few
52other benefits:
53
54 * Dead globals are trivial to optimize away.
55 * Constant globals are easier to detect. Remember that Go does not have global
56 constants in the same sense as that C has them. Constants are useful because
57 they can be propagated and provide some opportunities for other
58 optimizations (like dead code elimination when branching on the contents of
59 a global).
60 * Constants are much more efficent on microcontrollers, as they can be
61 allocated in flash instead of RAM.
62
63For more details, see [this section of the
64documentation](https://tinygo.org/compiler-internals/differences-from-go/).
65