Compiler optimization

Compiler optimization transforms a program representation to improve a chosen resource objective while preserving the behavior required by its programming language semantics. Objectives include execution time, code size and memory traffic. A transformation need not find a globally best program, and improving one objective can worsen another.

For example, constant folding replaces 2+3 by 5, while common subexpression elimination may compute a repeated expression once. Reusing a load across a store is valid only if the store cannot change the loaded location; alias analysis helps establish that condition. Similarly, replacing floating-point (a+b)+c by a+(b+c) can change rounding, so an optimizer needs an applicable permission or proof. Data-flow analysis supplies facts used by transformations, and undefined behavior affects which executions the language requires an implementation to preserve.

Data-flow analysis propagates facts about values or variable uses through a control-flow graph. Each program operation transforms incoming facts, and a join combines information from possible predecessor paths. A compiler can use the result to justify compiler optimization or issue warnings. Clang's introduction develops this method using sets of possible values and iteration to a fixed point.^[ref]

For example, live-variable analysis asks which current values might be read later before being overwritten. For a basic block $b$, with uses before any local definition in ${\mathrm{USE}}_b$ and definitions in ${\mathrm{DEF}}_b$, the backward equations areA use requires the incoming value; an intervening definition removes that requirement. Iterating from empty sets terminates for a finite graph and finite variable set because these equations only add facts. The result guides register allocation.

Live-variable analysis computes which program variables may be read in the future before their current values are overwritten. It is a backward data-flow analysis: future uses make information flow toward earlier instructions. For a basic block $B$, let $\mathrm{USE}(B)$ contain values read before being defined in that block and let $\mathrm{DEF}(B)$ contain its definitions. ThenA value is needed on entry if the block itself first reads it, or if a successor needs it and the block does not replace it.^[ref]

For a block x = y + 1; return x;, y is live on entry but the old x is not. Iterating the equations over a finite control-flow graph yields a conservative answer useful for register allocation. Syntactically possible paths may include paths that execution can never take, so computed liveness need not prove that a use actually occurs.