8.4 Optimization Phases

Optimization can be performed on the tree. This is called high-level optimization. Even with today's programming standards -- no transfer into the middle of loops, etc. -- principle 1 makes these high-livel optimizations unsafe. We will see why when we look at a formal definition of a loop. More aggressive, as well as correct, optimizations are made on a graphical intermediate representation of a program.

The phase which represents the pertinent, possible flow of control is often called control flow analysis. If this representation is graphical, then a flow graph depicts all possible execution paths. Control flow analysis simplifies the data flow analysis. Data flow analysis is the proces of collecting information about the modification, preservation , and use of program "quantities"-- usually variables and expressions.

Once control flow analysis and data flow analysis have been done, the next phase, the improvement phase, improves the program code so that it runs faster or uses less space. This phase is sometimes termed optimization. Thus, the term optimization is used for this final code improvement, as well as for the entire process which includes control flow analysis and data flow analysis.

Optimization algorithms attempt to remove useless code, eliminate redundant expressions, move invariant computations out of loops, etc.

The next section describes control flow analysis. We begin by creating the control flow graph.