Optimizations

“Optimizing programs is basically like pruning branches.”

(These are random notes, with no real organization)

Graydon Hoare did a presentation on this (this one: http://venge.net/graydon/talks/CompilerTalk-2019.pdf)

But the paper that covered the 7 major optimisations was by Frances Allen “A Catalogue of Optimizing Transformations” found here: https://www.clear.rice.edu/comp512/Lectures/Papers/1971-allen-catalog.pdf

Some bits:

1. Constant folding makes other optimisation easier to see
2. Dead code elimination
3. Inlining - constants as arguments allows ahead of time (compile time)
4. If statements might be dead.
5. Register allocation
6. …more

Nicolas’ blog post Scalar replacement and branch burning — c loop and what happens when they go together. There is a blog post but i don’t remember where.

One major branch of optimizations: ICs (inline caches) TODO: Go read this paper and write a summary for the papers page.

Some notes

Inline caches are really extremely simple. You see tons of branches, the goal of inline caches is encoding the path that you use. Removing the number of branches. Also records type information specific to one situation. We used to have two data structures for this, now we have one.

Another aspect of inline caches where you have the result only relies on the input value. It can be costly to do too many inline caches. Restarting is costly.