Data-flow Analysis and Global Optimization

DATA-FLOW ANALYSIS provides tools to get increased information about the program such that

• we can extend optimization across multiple basic blocks and such that
• we use new optimizations applicable to groups of basic blocks forming loops.

Global data-flow analysis can provide the following types of information

liveness

of variables

available expressions:

if we have two identical expressions in separate blocks, we need to know if the variables they use hold the same value

reaching definitions:

for any TAC statement x:= y op z, we need to know where the operands y and z were defined.

copy statements:

in order to extend copy propagation to more than a single basic block, one needs to know which copy statements remain unchanged across blocks

GLOBAL OPTIMIZATION uses transformations applicable to groups of basic blocks, usually groups of blocks forming loops.

Global analysis and global optimization are studied in the next sections.