Compiler Design · topic
The data-flow framework, reaching definitions, available expressions for global common-subexpression elimination, liveness solved backward by iteration, and constant propagation on its lattice.
Global optimisations need facts that hold at a program point on every execution, or on some execution: "this definition of x may reach here", "y may be used later", "a + b has already been computed on every path to here", "z is always 3 here".
If a variable holds the same known constant on every path to a use, the compiler can replace the use by the constant. That enables constant folding (computing 4 * 2 at compile time), which can make more variables constant, and can make branch conditions known so that whole paths become dead.
A variable is live at a program point if its current value may still be read later. A register holding a dead variable can be reused; an assignment to a variable that is dead immediately afterwards is useless and can be deleted.
An expression is a common subexpression if it was computed earlier and its operands have not changed since. Reusing the earlier value is common subexpression elimination; across blocks it relies on the available expressions analysis.
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
