Global Optimisation

Optimizations across basic blocks are called global. Optimization cannot not produce optimal code-two problems:

1. opt. subsumes problems known to be undecidable, for example, reachability, which can be reduced to halting problem.
2. even if solvable, opt. may be ridiculously expensive-many algorithms are O(e^n) and, in practice, heuristics are used.

Two issues:

safety

does the opt. code always produce the same results as the original program? Opts which compromise this are: associative reordering of operands; code motion (out of loops); loop unrolling.

profitability

is it worth the effort? Opt. can return 20-25%performance improvement, but an improved algorithm may take the program from O(n^2) to O(n) or from O(n) to O(log n) - optimization is not a substitute for good algorithms, it is the icing on the cake.

Optimized code may introduce errors and it is hard to debug An idealized optimizing compiler structure:

          dependent      independent
------------------------------------
source |  language   |   machine
CG     |  machine    |   language
IR     |             |   language and machine

Language design interacts with GO-some features help:

• named constants rather than variables which are never modified-trivial identified
• operator assigns-something and becomes (+= makes it easier to identify redundant code
• case-better code than if chains in the right circumstances, ie. indexed jump table versus test sequence (eg. byte code interpreter).
• loop index protection-no assignment

• by name parameters-historical now
• functions with side-effects-inhibits code-elimination and motion
• alias creation-identification of redundant code is harder
• exceptions-jumps to handlers which have side-effects and then resume

GO examines flows between basic blocks-construct data flow graph. However, most gains come from analysing loops in scientific programs (FORTRAN) and many optimizing compilers only consider loops. In particular loops are a good source of common subexpressions, especially in array index computations. Two classes:

• loop invariants can be moved to loop entry and evaluated once, for example:

  while (j>i) { a[j] = 10/i; j = j+2; }

  but if i=0 and 10/i is moved to top will give rise to a division by zero exception.

• index variable based expressions: index variable values are i-0, i-0+1, ... while expression values are i-0*b, i-0*b+b, ... differing by b. The multiplication can be eliminated in favour of addition (strength reduction).

  DO 10 I=1,N
  A(I) = B*I
  END DO

Other optimisations are:

• in-line expansion (procedure integration, partial evaluation)
• simplified leaf calls (static allocation of AR's, ie. automatic allocation replaced by static allocation).
• interprocedural data-flow analysis