Follow

Yesterday I described one optimization pass which may be applied to the Haskell Core intermediate language. This run by a driver, and today I want to discuss all (most) the other passes which that same driver might run.

These are:

* Common Subexpression Elimination
* Unrolling recursion involving case expressions
* Float `let`s inwards to reduce allocation
* Float `let`s out of callbacks
* Turn function arguments into variables
* Determine whether to eta-expand.
* Simplify recursion
* etc

1/9

Common Subexpression Elimination traverses all the `let`s in the program/module whilst building & applying a rewrite mapping of them. It doesn't apply CSE to a finer level, but later passes might nuke that point. Or maybe rely on equivalent optimizations in the next intermediate language.

Liberate Case inlines simple-enough recursions where there's a `case` between it & the recursive call, because that often reveals further optimizations.

2/8?

Floating variables towards of the leaves control flow tree reduces the conditions on which their (lazy) values are allocated, even pushing them down into function arguments. But not lambda functions. The variables being floated into a branch are kept in a list and floated down until duplication, relying on the float out to remove degenerate cases. Taking special care around primitive functions & bindings.

Float up mostly removes `let`s from callbacks which do not change per-call.

3/8?

Another means of moving loop invariants out of loops is to examine the function's arguments & building a inner function which doesn't duplicate the unchanging args. By traversing the expression maintaining a list of interesting IDs sourced from the lambda's calls, info which may require a merging step.

There's a pass which counts up how many args each local function is passed, so it knows to optimize those functions to receive that many arguments by consolidating lambda ops together.

4/6?

If a tailcall-recursive function has only a single non-recursive branch (which is very common), it can be helpful to extract that into it's own function to make future optimizations more obvious. There's an optimization for that!

There's a pass to annotate the code with which variables are required in each branch in a postoder traversal, for the sake of tomorrow's topic. And another analysis pass to determine the strictness of each function parameter.

5/5 Fin, for now. Tomorrow: exp optimizer!

Sign in to participate in the conversation
FLOSS.social

For people who care about, support, or build Free, Libre, and Open Source Software (FLOSS).