HP 3000 Manuals HP 3000 Manuals
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]