HP 3000 Manuals

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