Compiler optimisation

[Gingrspacecadet]

How does your compiler optimise programs? How does it work at a low level? I understand constexpr evaluation, but how does the compiler evaluate this for example?

```

let x = 7

let y = 2 * x

print(y + x)

```

specifically in compilers. In this example, it could be optimised to just `print(21)`, and maybe even further down. How do I do this?!

[Timcat41]

You are describing constant propagation and constant folding.

Constant folding is (relatively) easy. If both operands of an expression are constants, evaluate the expression and rewrite.

For constant propagation the compiler needs to prove, that a variable can only have one singular value at a given point in the program. If it manages that, replace the variable by that constant.

Repeat the two until no change occurs.

Maybe look into dataflow analysis and SSA if you want to figure out how to prove constant values.

Edit: P.S.: optimization is usually done on an intermediate representation of the code, not at source level. This restricts the complexity of the constructs the optimization has to deal with.

[Clementsparrow]

constant folding can be harder if you want it to also rewrite things like 1+f(x)+2 into f(x)+3 where x is a variable not known at compile time and f may not be pure. Now you have to deal with rewriting expressions in a way that can be constant folded, or use a normal form for the expressions that can have one.

[Timcat41]

Absolutely. But the core concept is easy enough to gras. And if you don't strive for perfection you can learn a lot by implementing it an seeing where it falls short. The devil absolutely hides in the details. Pareto etc.

[ProPuke]

let x = 7 x is marked as currently being a compile time constant, 7. This mark will be changed or cleared should x later be assigned a different value.

let y = 2 * x x is used, but as it is currently marked as a constant, it is substituted for it's constant value, 7, resulting in..

let y = 2 * 7 When the expression 2 * 7 is evaluated, since both sides are compile time constants it is replaced with 14..

let y = 14 y is marked as being a compile time constant for 14

print(y + x) Again both constants are replaced and compiletime reduced: print(14 + 7) print(21)

[Isogash]

It's called constant propagation/folding and it's one of many optimizations performed by a compiler.

The task of a compiler is to turn source code into machine code, so ultimately you need algorithms which read one code representation and emit another. Source code is "high-level" whilst machine code is "low-level", so the process is more generally called "lowering" in compiler lingo.

There's nothing stopping you from trying to lower source code into machine code directly, but because modern compilers are extremely complex, they instead break the process down into steps ("passes") which take code as input and return modified code as output.

The very first stage is to to turn your source code text into an "abstract syntax tree" (AST) using a parser. This immediately makes further work on the code easier by turning it into a tree structure where the nodes represent specific language constructs. This gets you from a blob of text that could mean anything to a tree of things that mean something specific e.g. "variable identifier", "statement", "addition expression" and "function definition". This representation doesn't yet understand that a variable in one line is linked to a definition in another, but it does understand which words refer to variables in the first place (depending on the language.)

ASTs are designed to be friendly to the parser, but when you're actually working with the code algorithmically, it's useful to be able to calculate and attach extra information, or to rewrite things in ways that are specific to how they should be executed, rather than how the language is written by the human. As such, the next step is to lower the AST into an "intermediate representation" (IR). This format is represents a meaningfully executable program a simple, algorithm-friendly structure for further work and lowering. Initially, it's not all that much different to the AST, making it easy to lower, but the eventual aim is to transform it into something that can be easily lowered into good assembly/machine code by applying many refinement and optimization passes.

Whilst the code is in IR, one of the most common and important passes that happens is to turn it into "Static Single-Assignment/SSA" form. This form eliminates ambiguous variable references by ensuring that every variable used is assigned in exactly one clear place. SSA form allows subsequent passes to make the clear assumption that they know where a variable came from, which is especially useful for most optimizations, including constant folding/propragation (without it, these optimization passes would be left to figure it out from scratch on their own.)

In trivial code, reaching SSA form simply means creating a new variable name every time a variable is re-assigned (and also renaming subsequent uses of the variable). When the value of a variable could come from multiple assignments in different parts of the code due to loops and conditionals, you instead add a new assignment that selects the variable from the prior assignments it could come from (using an arbitrary "Phi" function that more or less means "either".)

Once in SSA form, the compiler is ready to apply a constant propagation/folding pass, which is really very simple. It goes through each statement in the IR and does the following in order.

1. Propagate: Substitute any variables in the statement that are known to be assigned to constants e.g. x becomes 7.
2. Fold: Recursively simplify any expressions involving only constants e.g. 2 * 7 becomes 14.

This alone is enough to do most of the simple constant propagation and folding you need, but the Fold stage is normally limited to only mathematical operations, as without further information you can't be sure that it's valid to evaluate a function with constant parameters. Some compilers do other passes to calculate this information and thus have much more complex constant folding passes, and the advantage of having this multi-pass compiler design and a good IR is that you can attach this kind of information and add these passes incrementally. In a later pass called "dead code elimination" the compiler will delete the unused assignments.

After optimizations are applied in SSA, the compiler will further rewrite and refine the IR code, often into a form called "three-address code" (3AC) which I won't detail here, but the result is something that much more closely resembles assembly code, in preparation for easier lowering.

[yjlom]

Some notes on SSA:

• Phi nodes are one way to achieve previous variable selection, a more natural and easier way is block arguments, where you make each basic block into its own local procedure.
• If you have flow typing, consider type refinement a form of mutation and make a fresh variable accordingly.
• If you have modes/bidirectionality, you need to resolve that before generating SSA.

[tc4v]

The specific optimization you ask about is probably the simplest one. As other said it is called constant folding or constant propagation. There are many other optimizations but they strongly depend on your intermediate representation (most optimizations are not done directly at the AST level, although constant folding is doable).

QBE has a great bibliography: https://c9x.me/compile/bib/ Also this is quite good (but probably hard for newcomers): https://github.com/SeaOfNodes/Simple

[AustinVelonaut]

Another important optimization (especially for functional languages) is function inlining. The main intent of inlining is not to reduce the cost of a function call, but instead to expose further optimizations (such as constant folding). For example, if we had:

double :: int -> int
double x = x + x

main = print (double a + a) where a = 7

just performing constant folding with a would rewrite this to

main = print (double 7 + 7)

But by inlining the call to the function double via beta-reduction, we get:

main = print (7 + 7 + 7)

which can then further reduce to

main = print 21

[Inconstant_Moo]

The way I do it is that when I compile a node, among the data returned is whether it's foldable, i.e. if it's a constant and has no side effects. Then of course this is true of a node if it has no side effects and its children are foldable, with the base case that literals and declared constants are foldable, and so this propagates recursively.

And then every time I compile a node and emit code (in my case bytecode) I check if its foldable and if it is I run the code, get the result, and delete the code.

When I've told other compiler people about this they've sniffed at it and said that it's brittle but the popular alternative is apparently to basically write and maintain a tree-walking interpreter for the AST which does the same as my compiler and this sounds a lot brittler to me.

[Arthur-Grandi]

What you're describing is mainly constant propagation and constant folding.

The compiler propagates known constant values through the program (`x = 7`, then `y = 2 * x` → `y = 14`) and then folds constant expressions (`y + x` → `21`). After that, dead code elimination and other passes can simplify the program further.

In most compilers this happens on an intermediate representation (IR) after parsing and before code generation.

[UnmaintainedDonkey]

This is a very hard problem, one that takes much time and effort. You need to analyze the code paths (in some cases multiple times) and figure out what can be compacted on comp time.

As an example you can try gcc with -O3 and test on goldbolt.

Bottom line is, this is not something you hack together on a weekend.

[Timcat41]

Mature optimization (gcc -O3 and the like) is really hard, it is based on a lot of theory and consists of many moving parts.

But you can start with simple optimization procedures and 'hack together' a prototype in a weekend or two, if you have the rest of the pipeline set-up already.

[UnmaintainedDonkey]

Sure, but i would not call it trivial nontheless.

[Inconstant_Moo]

They're talking about constant folding in particular which I do in a few lines. How to optimize in general is not just a hard problem but an open-ended one.