If we see the instructions sequence
(1) (1) MOV R0,a
(2) (2) MOV a,R0
we can delete instructions (2) because whenever (2) is executed. (1) will ensure that the value of a is already in register R0.If (2) had a label we could not be sure that (1) was always executed immediately before (2) and so we could not remove (2).
UNREACHABLE CODE
Another opportunity for peephole optimizations is the removal of unreachable instructions. An unlabeled instruction immediately following an unconditional jump may be removed. This operation can be repeated to eliminate a sequence of instructions. For example, for debugging purposes, a large program may have within it certain segments that are executed only if a variable debug is 1.In C, the source code might look like:
#define debug 0
....
If ( debug ) {
Print debugging information
}
In the intermediate representations the if-statement may be translated as:
If debug =1 goto L2
Goto L2
L1: print debugging information
L2: ����������(a)
One obvious peephole optimization is to eliminate jumps over jumps .Thus no matter what the value of debug, (a) can be replaced by:
If debug ?1 goto L2
Print debugging information
L2: �����������(b)
As the argument of the statement of (b) evaluates to a constant true it can be replaced by
If debug ?0 goto L2
Print debugging information
L2: �����������(c)
As the argument of the first statement of (c) evaluates to a constant true, it can be replaced by goto L2. Then all the statement that print debugging aids are manifestly unreachable and can be eliminated one at a time.
FLOW-OF-CONTROL OPTIMIZATIONS
The unnecessary jumps can be eliminated in either the intermediate code or the target code by the following types of peephole optimizations. We can replace the jump sequence
goto L2
�.
L1 : gotoL2
by the sequence
goto L2
�.
L1 : goto L2
If there are now no jumps to L1, then it may be possible to eliminate the statement L1:goto L2 provided it is preceded by an unconditional jump .Similarly, the sequence
if a < b goto L1
�.
L1 : goto L2
can be replaced by
if a < b goto L2
�.
L1 : goto L2
Finally, suppose there is only one jump to L1 and L1 is preceded by an unconditional goto. Then the sequence
goto L1
��..
L1:if a<b goto L2
L3: �������������..(1)
may be replaced by
if a<b goto L2
goto L3
��.
L3: �������������.(2)
While the number of instructions in (1) and (2) is the same, we sometimes skip the unconditional jump in (2), but never in (1).Thus (2) is superior to (1) in execution time
ALGEBRAIC SIMPLIFICATION
There is no end to the amount of algebraic simplification that can be attempted through peephole optimization. Only a few algebraic identities occur frequently enough that it is worth considering implementing them .For example, statements such as
x := x+0
Or
x := x * 1
are often produced by straightforward intermediate code-generation algorithms, and they can be eliminated easily through peephole optimization.
ELIMINATION OF COMMON SUBEXPRESSIONS
Common sub expressions need not be computed over and over again. Instead they can be computed once and kept in store from where its referenced when encountered again � of course providing the variable values in the expression still remain constant.
ELIMINATION OF DEAD CODE
Its possible that a large amount of dead(useless) code may exist in the program. This might be especially caused when introducing variables and procedures as part of construction or error-correction of a program � once declared and defined, one forgets to remove them in case they serve no purpose. Eliminating these will definitely optimize the code
REDUCTION IN STRENGTH
Reduction in strength replaces expensive operations by equivalent cheaper ones on the target machine. Certain machine instructions are considerably cheaper than others and can often be used as special cases of more expensive operators. For example, x� is invariably cheaper to implement as x*x than as a call to an exponentiation routine. Fixed-point multiplication or division by a power of two is cheaper to implement as a shift. Floating-point division by a constant can be implemented as multiplication by a constant, which may be cheaper.
USE OF MACHINE IDIOMS
The target machine may have hardware instructions to implement certain specific operations efficiently. Detecting situations that permit the use of these instructions can reduce execution time significantly. For example, some machines have auto-increment and auto-decrement addressing modes. These add or subtract one from an operand before or after using its value. The use of these modes greatly improves the quality of code when pushing or popping a stack, as in parameter passing. These modes can also be used in code for statements like i : =i+1.
Getting Better Performance
Dramatic improvements in the running time of a program-such as cutting the running time form a few hours to a few seconds-are usually obtained by improving the program at all levels, from the source level to the target level, as suggested by fig. At each level, the available options fall between the two extremes of finding a better algorithm and of implementing a given algorithm so that fewer operations are performed.
Algorithmic transformations occasionally produce spectacular improvements in running time. For example, Bentley relates that the running time of a program for sorting N elements dropped from 2.02N^2 microseconds to 12Nlog2N microseconds then a carefully coded "insertion sort" was replaced by "quicksort".
THE PRINCIPAL SOURCES OF OPTIMIZATION
Here we introduce some of the most useful code-improving transformations. Techniques for implementing these transformations are presented in subsequent sections. A transformation of a program is called local if it can be performed by looking only at the statements in a bas9ic block; otherwise, it is called global. Many transformations can be performed at both the local and global levels. Local transformations are usually performed first.
Function-Preserving Transformations
There are a number of ways in which a compiler can improve a program without changing the function it computes. Common subexpression elimination, copy propagation, dead-code elimination, and constant folding are common examples of such function-preserving transformations. The other transformations come up primarily when global optimizations are performed.
Frequently, a program will include several calculations of the same value, such as an offset in an array. Some of these duplicate calculations cannot be avoided by the programmer because they lie below the level of detail accessible within the source language. For example, block B5 shown in fig recalculates 4*i and 4*j.
