Criteria for Code-Improving Transformations
Simply stated, the best program transformations are those that yield the most benefit for the least effort. The transformations provided by an optimizing compiler should have several properties.
First, a transformation must preserve the meaning of programs. That is, an "optimization" must not change the output produced by a program for a given input, or cause an error, such as a division by zero, that was not present in the original version of the source program. The influence of this criterion pervades this chapter; at all times we take the "safe" approach of missing an opportunity to apply a transformation rather than risk changing what the program does.
Second, a transformation must, on the average, speed up programs by a measurable amount. Sometimes we are interested in reducing the space taken by the compiled code, although the size of code has less importance than it once had. Of course, not every transformation succeeds in improving every program, and occasionally an "optimization" may slow down a program slightly, as long as on the average it improves things.
Third, a transformation must be worth the effort. It does not make sense for a compiler writer to expend the intellectual effort to implement a code improving transformation and to have the compiler expend the additional time compiling source programs if this effort is not repaid when the target programs are executed. Certain local or "peephole" transformations of the kind are simple enough and beneficial enough to be included in any compiler.
Some transformations can only be applied after detailed, often time-consuming, analysis of the source program, so there is little point in applying them to programs that will be run only a few times. For example, a fast, nonoptimizing, compiler is likely to be more helpful during debugging or for "student jobs� that will be run successfully a few times and thrown away. Only when the program in question takes up a significant fraction of the machine's cycles does improved code quality justify the time spent running an optimizing compiler on the program.
Before we get into optimization as such we need to familiarize ourselves with a few things
ALGEBRAIC TRANSFORMATION
Countless algebraic transformations can be used to change the set of expressions computed by a basic block into an algebraically equivalent set. The useful ones are those that simplify expressions or replace expensive operations by cheaper ones. For example, statements
such as
x := x +0
Or
x := x*1
can be eliminated from a basic block without changing the set of expressions it computes. The exponentiation operator in the statements
x := y ** 2
usually requires a function call to implement. Using an algebraic transformation, this statement can be replaced by cheaper, but equivalent statement
x := y*y
FLOW GRAPHS
We can add the flow-of �control information to the set of basic blocks making up a program by constructing a directed graph called a flow graph. The nodes of the flow graph are the basic blocks. One node is distinguished as initial; it is the block whose leader is the first statement. There is a directed edge from block B1 to block B2can be immediately follow B1in some execution sequence; that is, if
1. there is a conditional or unconditional jump from the last statement of B2, or
2. B2 immediately follow B1in the order of the program, and B1 does not end in the unconditional jump
B1 is a predecessor of B2, and B2is a successor of B1.
Example 4:The flow graph of the program of fig. 7 is shown in fig. 9, B1 is the initial node.
figflowchart
REPRESENTATION OF BASIC BLOCKS
Basic Blocks are represented by variety of data structures. For example, after partitioning the three address statements by Algorithm 1, each basic block can be represented by a record consisting of a count of number of quadruples in the block, followed by a pointer to the leader of the block, and by the list of predecessors and successors of the block. For example the block B2 running from the statement (3) through (12) in the intermediate code of figure 2 were moved elsewhere in the quadruples array or were shrunk, the (3) in if i<=20 goto(3) would have to be changed.
LOOPS
Loop is a collection of nodes in a flow graph such that
1. All nodes in the collection are strongly connected; from any node in the loop to any other, there is path of length one or more, wholly within the loop, and
2. The collection of nodes has a unique entry, a node in the loop such that is, a node in the loop such that the only way to reach a node of the loop from a node outside the loop is to first go through the entry.
A loop that contains no other loops is called an inner loop.
PEEPHOLE OPTIMIZATION
A statement-by-statement code-generations strategy often produce target code that contains redundant instructions and suboptimal constructs .The quality of such target code can be improved by applying �optimizing� transformations to the target program.
A simple but effective technique for improving the target code is peephole optimization, a method for trying to improving the performance of the target program by examining a short sequence of target instructions (called the peephole) and replacing these instructions by a shorter or faster sequence, whenever possible.
The peephole is a small, moving window on the target program. The code in the peephole need not contiguous, although some implementations do require this. We shall give the following examples of program transformations that are characteristic of peephole optimizations:
� Redundant-instructions elimination
� Flow-of-control optimizations
� Algebraic simplifications
� Use of machine idioms
