Level One Optimization [ HP Pascal/iX Programmer's Guide ] MPE/iX 5.0 Documentation
HP Pascal/iX Programmer's Guide
Level One Optimization
Level one optimization transforms small sections of code quickly, using
little compile-time storage. Compile your program with level one
optimization when you want to improve run-time performance with little
increase in compile time.
The functions of the five level one optimizer transformations are:
* Branch optimization
* Dead code elimination
* Faster register allocation (including copy elimination)
* Instruction scheduling
* Peephole optimization
Branch Optimization
The branch optimization transformation makes branch instruction sequences
more efficient wherever possible.
Table 12-1 gives examples of equivalent unoptimized and optimized
branch instruction sequences.
Table 12-1. Unoptimized and Optimized Branch Instruction Sequences
---------------------------------------------------------------------------------------------
| | |
| Unoptimized Sequence | Optimized Sequence |
| | |
---------------------------------------------------------------------------------------------
| | |
| Branch target is the default, as in: | Branch is deleted: |
| | |
| IF b THEN GOTO 100; | 100 : writeln('Hi'); |
| 100 : writeln('Hi'); | |
| | |
---------------------------------------------------------------------------------------------
| | |
| Branch target is an unconditional branch, | Target of unconditional branch is target of |
| as in: | conditional branch: |
| | |
| IF b1 THEN | IF b1 THEN p(5); |
| IF 2<5 THEN p(5); | |
| | |
---------------------------------------------------------------------------------------------
| | |
| Target of an unconditional branch at the | Conditional branch at the bottom of the |
| bottom of a loop is a conditional branch at | loop: |
| the top of a loop, as in: | |
| | IF b THEN BEGIN |
| 100 : IF b THEN BEGIN | 100 : |
| . | BEGIN |
| . | . |
| . | . |
| GOTO 100; | . |
| END; | IF b THEN GOTO 100; |
| | END; |
| | END; |
| | |
---------------------------------------------------------------------------------------------
Table 12-1. Unoptimized and Optimized Branch Instruction Sequences (cont.)
---------------------------------------------------------------------------------------------
| | |
| Unoptimized Sequence | Optimized Sequence |
| | |
---------------------------------------------------------------------------------------------
| | |
| Target of unconditional branch is a routine | Unconditional branch is an exit sequence, |
| exit, as in: | if possible. (This cannot be shown at the |
| | source code level.) |
| PROCEDURE p; | |
| BEGIN | |
| . | |
| . | |
| . | |
| GOTO 99; | |
| . | |
| . | |
| . | |
| 99: END; | |
| | |
---------------------------------------------------------------------------------------------
| | |
| Branch over a single instruction, as in: | Conditional nullification of the |
| | instruction preceding the skipped |
| IF b THEN GOTO 1; | instruction: |
| i := 0; {single instruction} | |
| 1: j := j+1; | IF NOT b THEN i:=0; |
| | 1: j := j+1; |
| Which has the machine code: | |
| | Which has the machine code: |
| LDB "b",r1 | |
| BB,>=,N r1,31,false_if | LDB "b",r1 |
| B,N label_1 | EXTRS,< r1,31,1,r0 |
| | STW r0,"i" |
| false_if STW r0,"i" | LDW "j",r31 |
| | ADDIO 1,r31,r19 |
| label_1 LDW "j",r31 | STW r19,"j" |
| ADDIO 1,r31,r19 | |
| STW r19,"j" | |
| | |
---------------------------------------------------------------------------------------------
| | |
| Conditional branch over an unconditional | The condition in the conditional branch is |
| branch, as in: | inverted, and the unconditional branch is |
| | deleted: |
| IF b THEN GOTO 100; | |
| GOTO 110; | IF NOT b THEN GOTO 110; |
| 100: writeln('Hi'); | writeln('Hi'); |
| 110: writeln('Bye'); | 110: writeln('Bye'); |
| | |
---------------------------------------------------------------------------------------------
Dead Code Elimination
The dead code elimination transformation eliminates code that will never
be executed. For example:
a := 2;
goto 1;
writeln('debug_patch_01',a);
1:
becomes:
a := 2;
Do not depend on dead code because the compiler can eliminate dead code
even without optimization. The current compiler performs the following
transformation without optimization:
The code:
IF 2>3 THEN a ELSE b;
WHILE 2>3 DO c;
FOR i := 7 TO 0 DO d;
CASE 1 OF
1: e;
2: f;
END;
REPEAT g UNTIL 3>2;
becomes:
b;
e;
g;
Faster Register Allocation
The faster 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 faster register allocation transformation analyzes register use
faster than the coloring register allocation transformation (at level
two) does.
Instruction Scheduling
The instruction scheduling transformation:
* Reorders the instructions in a basic block to minimize waiting.
(A basic block is an instruction sequence that can be entered only
at the first instruction and exited only from the last
instruction.)
* Follows a branch instruction with a useful instruction that can be
executed as the branch occurs, where possible.
* Schedules floating-point instructions.
Example
The code:
in which ADDI must wait an extra machine cycle for r1 to be loaded with
its new value, becomes:
which does not immediately use r1 and, therefore, does not have to wait.
Peephole Optimization
The peephole optimization transformation makes one pass through the
program, shortening instruction sequences in small windows of code by:
* Changing the addressing modes of instructions, so that they use
shorter sequences.
* Substituting smaller, equivalent instruction sequences.
Example
The code:
LDI 32,r3
AND r1,r3,r2
COMIB,= 0,r2,L1 {COMpare Immediate; Branch if equal}
becomes:
BB,>= r1,26,L1 {Branch on Bit 26}
Real Expression Folding
The real expression folding transformation simplifies real expressions as
follows:
Real Expressions of the Form: Become:
-----------------------------------------------
r1 * 1 r1
1 * r1
r1 + 0
0 + r1
r1 - 0
r1 / 1
r1 * 0 0
0 * r1
0 - r1 -r1
NOTE Folding real expressions violates the IEEE Real Standard, which
disallows operations for certain real values (for example, infinity
and NAN). The real expression folding transformation assumes that
r1 does not have any of these values. The above expressions are
not folded if optimization is turned off.
MPE/iX 5.0 Documentation