Add flow-sensitive optimizations

[bbannier]

Broadly speaking optimizations implemented in Spicy are currently not flow-sensitive. Instead they follow a pattern of collecting information about variables, functions and types, and then checking the code for uses. Based on the collected information we then make AST edits. This process is repeated until there are no new changes.

This approach works well enough when e.g., working with constant values and to detect whether certain functions or types are used, but gives at best mediocre results for e.g., dead code elimination.

This ticket tracks work to make optimizations flow sensitive. Like existing optimizations all new functionality will be implemented so it works on fully resolved HILTI code just before we emit C++ code.

The work decomposes into the following aspects:

• Build a component which can compute a control flow graph (CFG) for a global HILTI AST. The control flow graph should tie individual HILTI AST nodes to CFG nodes.

• Implement pointer alias analysis.

  In order to track reads or writes to e.g., members of units which are emitted as references we need to implement an alias analysis pass. Ideally we can use type-based alias analysis for this which will e.g., allow us to distinguish reference arguments to generated parse functions.

• Implement dead code elimination (unreachable code, dead stores) for function bodies.

  Here we will compute CFGs for individual function bodies and optimize them separately. To detect dead code we will use data flow analysis. The approach here would be to compute a CFG, identify dead code and make AST edits in a single pass.

  Since most functions in HILTI can at least in principle throw we probably need to treat all writes to non-local variables as live. Optimization of e.g., writes to members will already be modelled through the alias analysis.

• Migrate optimizations implemented in ConstantFoldingVisitor to control-flow based approach.

  Currently ConstantFoldingVisitor implements optimizations for simplifying logic around constants. If we migrate this optimization to a control-flow based approach we can make us of it for locals with known values as well.

• Implement optimizer pass removing unused function arguments.

  For e.g., our generated parser functions not all function arguments might be always used. Above function-based dead code elimination will surface such dead parameters and can be tweaked to store that information (e.g., global list of unused function parameters). We can rewrite function declarations and their implementations, and callers. Analyzing function bodies with callers again might surface more dead code which can be removed.

Possible follow-up work:

• Migrate optimization removing unused functions and methods.

• Use a more fine-grained approach to decide what code can be removed from the public interface.