Overview of Global Optimization

A globally optimizing compiler will perform the following operations:

1. Order nodes using an ordering algorithm to find dominators.

2. Find basic available and busy information for blocks.

3. Solve boolean equations to get available and busy information for each block.

4. Replace common subexpressions by corresponding compiler variables.

5. Assign registers using graph coloring.

The information provided by data flow analysis provides a special-purpose proof that the optimized program is correct (produces the same answers).