8.1 Comparison of Algorithms

8.2 What to Optimize

8.3 Issues in Optimization

8.4 Optimization Phases

8.5 Control Flow Analysis

8.6 Loops

8.7 Summary

Exercises

8.3 Issues in Optimization

The most important optimization principle is correctness. The meaning of a program can't be changed:

    Principle 1. If you can't do it safely, don't do it.

The task is to find frequently occurring code sequences, perform improvements to them, and forget the rest.

    Principle 2. Don't expect the programmer to optimize high-level language features.

Sometimes the questions are asked: Why optimize? Can't programmers just be taught to write good code? The answer is (rarely) yes . For large programs which execute for many hours or days, programmers do rewrite them to make them as efficient as possible. The more common answer, however, is no. Programmers should be able to use the features of a language to implement an algorithm without worrying about its efficiency. They should be optimizing for readability and maintainability. Example 1 shows a common case

 EXAMPLE 1 Two-dimensional arrays
 	LOOP
 	  A[I,J] := . . .
 	  . . .
 	  . . .
 	   := A[I,J]
 	  . . .
 	ENDLOOP
    The translated code for Example 1 quite likely has "things" which can be optimized. The programmer could conceivably do it -- By using one-dimensional arrays, etc. Realistically, then, the programmer might as well not be using a high-level language.

An optimizing compiler is expected to optimize the high-level features.

Optimizations optimize most frequently for time. This is represented, syntactically (that is, it can be seen by looking at the code), by minimization of the number of operations and minimization of the number of memory accesses. Operations can be computed faster if their operands are in registers. Constants can be computed at compile-time.

Optimizations optimize next most frequently for space . Minimizing memory accesses may produce a smaller amount of code as well as code that executes faster since most machine code requires more bytes to reference memory.

There are also space-time tradeoffs. For example, replacing two instances of the same code by a subroutine may save code space, but takes more time because of the overhead of jumping to the subroutine, passing arguments and returning from the subroutine.

An optimization should speed up a program by a measurable amount. Also, we don't optimize in heavy debugging environments (student environments are heavy debugging environments). It takes too much compiler time for environments where a program is compiled many times (until it is correct) and run once or twice.

On the other hand, as we shall see, certain so-called peephole optimizations are so easy that they should be done by all compilers.