Single Static Assingment Optimization

Single Static Assignment Optimization

Introduction

In compiler design, static single assignment form (often abbreviated as SSA form or SSA) is an intermediate representation (IR) in which every variable is assigned exactly once.

An SSA-based compiler modifies the program representation so that every time a variable is assigned in the original program, a new version of the variable is created.
A new version of the variable is distinguished (renamed) by subscripting the variable name with its version number or an index, so that every definition of each variable in a program becomes unique.
At a joining point of the control flow graph where two or more different definitions of a variable meet, a hypothetical function called a phi-function is inserted so that these multiple definitions are merged.

In mikroPascal PRO for AVR, SSA's main goal is in allocating local variables into the RX space (instead onto the frame).
To do that, SSA has to make an alias and data flow analysis of the Control Flow Graph.

Besides these savings, there are a number of compiler optimization algorithms enhanced by the use of SSA, like :

Constant Propagation
Dead Code Elimination
Global Value Numbering
Register Allocation

Changes that SSA brings is also in the way in which routine parameters are passed. When the SSA is enabled, parameters are passed through a part of the RX space which is reserved exclusively for this purpose (W10-W13 for dsPIC).
Allocating local variables and parameters in RX space has its true meaning for those architectures with hardware frame.

Enabling SSA optimization in compiler is done by checking box from the Output Settings Menu.

Lets consider a trivial case :

program Example;

procedure SSA_Test(y : integer; k : integer);

begin
  if (y+k) then
    asm
      nop;
    end
end;

begin
  SSA_Test(5,5);
end.

Without SSA enabled, this example consists of 7 more instructions, as it can be seen below :

          // Without SSA Enabled
_main:
0x0078   0xE5BF   LDI     R27, 95
0x007A   0xBFBD   OUT     SPL, R27
0x007C   0xE0B4   LDI     R27, 4
0x007E   0xBFBE   OUT     SPH, R27
;SSA.mpas,36 ::        begin
;SSA.mpas,37 ::        SSA_Test(5,5);
0x0080   0xE0B0   LDI     R27, 0
0x0082   0x93BF   PUSH    R27
0x0084   0xE0B5   LDI     R27, 5
0x0086   0x93BF   PUSH    R27
0x0088   0xE0B0   LDI     R27, 0
0x008A   0x93BF   PUSH    R27
0x008C   0xE0B5   LDI     R27, 5
0x008E   0x93BF   PUSH    R27
0x0090   0xDFE1   RCALL   _SSA_Test+0
0x0092   0xB7AD   IN      R26, SPL
0x0094   0xB7BE   IN      R27, SPH
0x0096   0x9614   ADIW    R26, 4
0x0098   0xBFAD   OUT     SPL, R26
0x009A   0xBFBE   OUT     SPH, R27
;SSA.mpas,38 ::        end.
L_end_main:
0x009C   0xCFFF   RJMP    L_end_main
; end of _main
_SSA_Test:
0x0054   0x93CF   PUSH    R28
0x0056   0x93DF   PUSH    R29
0x0058   0xB7CD   IN      R28, SPL
0x005A   0xB7DE   IN      R29, SPH
0x005C   0x9625   ADIW    R28, 5
;SSA.mpas,29 ::        begin
;SSA.mpas,30 ::        if (y+k) then
0x005E   0x8128   LDD     R18, Y+0
0x0060   0x8139   LDD     R19, Y+1
0x0062   0x810A   LDD     R16, Y+2
0x0064   0x811B   LDD     R17, Y+3
0x0066   0x0F02   ADD     R16, R18
0x0068   0x1F13   ADC     R17, R19
0x006A   0x2FB0   MOV     R27, R16
0x006C   0x2BB1   OR      R27, R17
0x006E   0xF009   BREQ    L__SSA_Test2
L__SSA_Test6:
;SSA.mpas,32 ::        nop;
0x0070   0x0000   NOP
;SSA.mpas,33 ::        end
L__SSA_Test2:
;SSA.mpas,34 ::        end;
L_end_SSA_Test:
0x0072   0x91DF   POP     R29
0x0074   0x91CF   POP     R28
0x0076   0x9508   RET
; end of _SSA_Test

          // With SSA Enabled
_main:
0x0064   0xE5BF   LDI     R27, 95
0x0066   0xBFBD   OUT     SPL, R27
0x0068   0xE0B4   LDI     R27, 4
0x006A   0xBFBE   OUT     SPH, R27
;SSA.mpas,36 ::        begin
;SSA.mpas,37 ::        SSA_Test(5,5);
0x006C   0x922F   PUSH    R2
0x006E   0x923F   PUSH    R3
0x0070   0x924F   PUSH    R4
0x0072   0x925F   PUSH    R5
0x0074   0xE0B5   LDI     R27, 5
0x0076   0x2E4B   MOV     R4, R27
0x0078   0xE0B0   LDI     R27, 0
0x007A   0x2E5B   MOV     R5, R27
0x007C   0xE0B5   LDI     R27, 5
0x007E   0x2E2B   MOV     R2, R27
0x0080   0xE0B0   LDI     R27, 0
0x0082   0x2E3B   MOV     R3, R27
0x0084   0xDFE7   RCALL   _SSA_Test+0
;SSA.mpas,38 ::        end.
L_end_main:
0x0086   0x905F   POP     R5
0x0088   0x904F   POP     R4
0x008A   0x903F   POP     R3
0x008C   0x902F   POP     R2
0x008E   0xCFFB   RJMP    L_end_main
; end of _main
_SSA_Test:
;SSA.mpas,29 ::        begin
;SSA.mpas,30 ::        if (y+k) then
0x0054   0x0182   MOVW    R16, R4
0x0056   0x0D02   ADD     R16, R2
0x0058   0x1D13   ADC     R17, R3
0x005A   0x2FB0   MOV     R27, R16
0x005C   0x2BB1   OR      R27, R17
0x005E   0xF009   BREQ    L__SSA_Test2
L__SSA_Test6:
;SSA.mpas,32 ::        nop;
0x0060   0x0000   NOP
;SSA.mpas,33 ::        end
L__SSA_Test2:
;SSA.mpas,34 ::        end;
L_end_SSA_Test:
0x0062   0x9508   RET
; end of _SSA_Test

Proper Coding Recommendations

To get the maximum out of the SSA, user should regard the following rules during the coding process :

Routines should not contain too many parameters (not more than 4 words).
Don't change the value of the parameter in the function body (it is better to use a new local variable).

If the function1 parameters are passed as function2 parameters, then parameter order should remain the same :

procedure f2(a: integer; b: integer;) { }

procedure f1(x: integer; y: integer;) {
  // routine call
  f2(x,y);  // x->a and y->b (1 to 1 and 2 to 2) is far more efficient than :
  f2(y,x);  // y->a and x->b (1 to 2 and 2 to 1)
}

Large amount of nested loops and complex structures as its members should be avoided.
When writing a code in assembly, keep in mind that there are registers reserved exclusively for routine parameters.
Using goto and label statements in nested loops should be avoided.
Obtaining address of the local variable with the global pointer and using it to alter the variable's address should be avoided.

Notes :

mcl files compiled with or without SSA enabled are fully compatible and can be used and mixed without any restrictions, except function pointers.
All function prototypes and function pointers have to be built using the same optimizer because of different calling conventions in different optimizers. In SSA, function parameters are passed via working registers, and without SSA they end up on the function frame.
This means that you cannot have a function implementation which is optimized using SSA optimizer, and to call this function via function pointer in another module which is optimized using NON-SSA.
When using pointers to functions, compiler must know exactly how to pass function parameters and how to execute function call.

Asm code and SSA optimization

If converting code from an earlier version of the compiler, which consists of mixed asm code with the Pascal code, keep in mind that the generated code can substantially differ when SSA optimization option is enabled or disabled.
This is due to the fact that SSA optimization uses certain working registers to store routine parameters (W10-W13), rather than storing them onto the function frame.

Because of this, user must be very careful when writing asm code as existing values in the working registers used by SSA optimization can be overwritten.
To avoid this, it is recommended that user includes desired asm code in a separate routine.

Debugging Notes

SSA also influences the code debugging in such a way that the local variables will be available in the Watch Window only in those parts of the procedure where they have useful value (eg. on entering the procedure, variable isn't available until its definition).
Variables can be allocated in one part of the procedure in register W4, and in another part of the procedure in register W2, if the optimizer estimates that it is better that way. That means that the local variable has no static address.

Warning Messages Enhancement

Besides the smaller code, SSA also deals with the intensive code analysis, which in turn has the consequence in enhancing the warning messages.
For example, compiler will warn the user that the uninitialized variable is used :

void main() {
  int y;

  if (y)        // Variable y might not have been initialized
    PORTD = 0;
}

Want more examples and libraries?
Find them on