Compiler Optimizations

WIP

lib.rs:

CubeCL Optimizer

A library that parses CubeCL IR into a control flow graph, transforms it to static single-assignment form and runs various optimizations on it. The order of operations is as follows:

1. Parse root scope recursively into a control flow graph
2. Run optimizations that must be done before SSA transformation
3. Analyze variable liveness
4. Transform the graph to pruned SSA form
5. Run post-SSA optimizations and analyses in a loop until no more improvements are found
6. Speed

The output is represented as a petgraph graph of BasicBlocks terminated by ControlFlow. This can then be compiled into actual executable code by walking the graph and generating all phi nodes, instructions and branches.

Representing PhiInstruction in non-SSA languages

Phi instructions can be simulated by generating a mutable variable for each phi, then assigning value to it in each relevant block.