HP 3000 Manuals

Level Two Optimization [ HP Pascal/iX Programmer's Guide ] MPE/iX 5.0 Documentation


HP Pascal/iX Programmer's Guide

Level Two Optimization 

Level two optimization transforms each routine as a unit, causing the
compiler to use more compile-time storage and take longer than level one
optimization or no optimization would.  Compile your program with level
two optimization when you want maximum run-time performance and
compilation speed is not important.

The functions of the seven level two optimizer transformations are:

   *   Coloring register allocation.

   *   Induction variable elaboration and strength reduction.

   *   Common subexpression elimination.

   *   Constant folding.

   *   Loop invariant code motion.

   *   Store-copy optimization.

   *   Unused definition elimination.

Coloring Register Allocation 

The coloring register allocation transformation:

   *   Inserts entry and exit code.

   *   Generates code for operations (such as multiplication and
       division).

   *   Eliminates unnecessary copy instructions.

   *   Allocates actual registers to the dummy registers in instructions.

The coloring register allocation transformation analyzes register use
more slowly than the faster register allocation transformation (at level
one), because it must handle the more extensive register usage caused by
level two optimizations.

Example 

The code:

     LDI    2,r104
     COPY   r104,r103
     LDO    5(r103),r106
     COPY   r106,r105
     LDO    10(r105),r107

becomes:

     LDI    2,r25
     LDO    5(r25),r26
     LDO    10(r26),r31

Induction Variable Elaboration and Strength Reduction 

The induction variables and strength reduction transformation:

   *   Replaces loop counters with induction variables where appropriate
       (in the following example, the loop counter i is replaced by an
       offset into the array r).

   *   Substitutes addition for multiplication where possible.

Example 

The code:

     FOR i := 1 TO 10000 DO BEGIN
        r[i] := i * k;
     END;

becomes:

     t1 := k;
     FOR i := 1 TO 10000 DO BEGIN
        r[i] := t1;
        t1 := t1 + k;
     END;

Common Subexpression Elimination 

The common subexpression elimination transformation identifies
expressions that appear more than once and have the same result, computes
the result, and substitutes it for each occurrence of the expression.

Example 

The code:

     a := x + y + z;
     b := x + y + w;

becomes:

     t1 := x + y;
     a := t1 + z;
     b := t1 + w;

Constant Folding 

The constant folding transformation replaces constant expressions with
their values within basic blocks.

Example 

The code:

     a := 1;
     b := 2;
     c := a + b;

becomes:

     a := 1;
     b := 2;
     c := 3;

Loop-Invariant Code Motion 

The loop-invariant code motion transformation moves loop-invariant code
out of the loop (loop-invariant code is code whose effect is independent
of the value of the loop counter).

Example 

The code:

     FOR i := 1 TO 100 DO BEGIN
        a[i] := (4 * x) + i;
     END;

becomes:

     t1 := 4 * x;
     FOR i := 1 TO 100 BEGIN
        a[i] := t1 + i;
     END;

Because optimization affects the machine code, but not the source code,
error messages associated with loop-invariant source code inside the loop
appear outside the loop after optimization.

Example 

Unoptimized program:

     i := 1;
     REPEAT
        a[i] := i;
        b[i] := b[i] + x/y;
     UNTIL i = 10;

Optimized program:

     i := 1;
     t := x/y;
     REPEAT
        a[i] := i;
        b[i] := b[i] + t;
     UNTIL i = 10;

If y is zero, the unoptimized program causes an error within the loop, at
the assignment of b[1].  The optimized program causes an error before the
loop is entered, before b[1] is assigned a value.  This error occurs
before the program enters the loop.

Store-Copy Optimization 

The store-copy optimization transformation substitutes registers for
memory locations where possible, by replacing store instructions with
copy instructions and deleting load instructions.

Example 

Source code:

     t1 :=  x + y;
     a  := t1 + z;
     b  := t1 + w;

Unoptimized code:

     LDW "x",r104
     LDW "y",r105
     ADD r104,r105,r106
     STW r106,"t1"
     LDW "t1",r106
     LDW "z",r107
     ADD r106,r107,r108
     STW r108,"a"
     LDW "t1",r106
     LDW "w",r109
     ADD r106,r107,r110
     STW r110,"b"

Optimized code:

     LDW "x",r104
     LDW "y",r105
     ADD r104,r105,r106

     LDW "z",r107
     ADD r106,r107,r108
     STW r108,"a"

     LDW "w",r109
     ADD r106,r107,r110
     STW r110,"b"

Unused Definition Elimination 

The unused definition elimination transformation removes unused memory
location and register definitions (which are often the by-products of
other optimizations).

Example 

The function:

     FUNCTION f (x : integer) : integer;
     VAR
        a,b,c : integer;
     BEGIN
        a := 1;
        b := 2;
        c := 0;
        c := x * b;
        f := c;
     END;

becomes:

     FUNCTION f (x : integer) : integer;
     VAR
        a,b,c : integer;
     BEGIN
        b := 2;
        c := x * b;
        f := c;
     END;

All the level two optimizations combined produce:

     FUNCTION f (x : integer) : integer;
     VAR
        a,b,c : integer;[REV BEG]
     BEGIN
        f := x * 2;
     END;[REV END]



MPE/iX 5.0 Documentation