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 mikroC 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 simple case :

void main() {
  int y,k;
  y = PORTA;
  k = PORTB;

  if(y+k)
    asm nop;

  Delay_10ms();
}

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

          // Without SSA Enabled
_main:
0x0062   0xE5BF   LDI        R27, 95
0x0064   0xBFBD   OUT        SPL, R27
0x0066   0xE0B4   LDI        R27, 4
0x0068   0xBFBE   OUT        SPH, R27
0x006A   0xB7CD   IN         R28, SPL
0x006C   0xB7DE   IN         R29, SPH
0x006E   0x9724   SBIW       R28, 4
0x0070   0xBFCD   OUT        SPL, R28
0x0072   0xBFDE   OUT        SPH, R29
0x0074   0x9621   ADIW       R28, 1
;SSA.c,26 ::              void main() {
;SSA.c,28 ::              y = PORTA;
0x0076   0xB30B   IN         R16, PORTA+0
0x0078   0x8308   STD        Y+0, R16
0x007A   0xE0B0   LDI        R27, 0
0x007C   0x83B9   STD        Y+1, R27
;SSA.c,29 ::              k = PORTB;
0x007E   0xB308   IN         R16, PORTB+0
0x0080   0x830A   STD        Y+2, R16
0x0082   0xE0B0   LDI        R27, 0
0x0084   0x83BB   STD        Y+3, R27
;SSA.c,31 ::              if(y+k)
0x0086   0x8128   LDD        R18, Y+0
0x0088   0x8139   LDD        R19, Y+1
0x008A   0x810A   LDD        R16, Y+2
0x008C   0x811B   LDD        R17, Y+3
0x008E   0x0F02   ADD        R16, R18
0x0090   0x1F13   ADC        R17, R19
0x0092   0x2FB0   MOV        R27, R16
0x0094   0x2BB1   OR         R27, R17
0x0096   0xF009   BREQ       L_main0
L__main2:
;SSA.c,32 ::     asm nop;
0x0098   0x0000   NOP
L_main0:
;SSA.c,34 ::     Delay_10ms();
0x009A   0xDFDC   RCALL      _Delay_10ms+0
;SSA.c,36 ::   }
L_end_main:
0x009C   0xCFFF   RJMP       L_end_main
; end of _main

          // With SSA Enabled
_main:
0x0062    0xE5BF   LDI        R27, 95
0x0064	 0xBFBD   OUT        SPL, R27
0x0066	 0xE0B4   LDI        R27, 4
0x0068	 0xBFBE   OUT        SPH, R27
;SSA.c,26 :: 		void main() {
;SSA.c,28 :: 		y = PORTA;
; y start address is: 18 (R18)
0x006A	 0xB32B   IN         R18, PORTA+0
0x006C	 0xE030   LDI        R19, 0
;SSA.c,29 :: 		k =  PORTB;
; k start address is: 20 (R20)
0x006E	 0xB348   IN         R20, PORTB+0
0x0070	 0xE050   LDI        R21, 0
;SSA.c,31 :: 		if(y+k)
0x0072	 0x018A   MOVW       R16, R20
0x0074	 0x0F02   ADD        R16, R18
0x0076	 0x1F13   ADC        R17, R19
; k end address is: 20 (R20)
; y end address is: 18 (R18)
0x0078	 0x2FB0   MOV        R27, R16
0x007A	 0x2BB1   OR         R27, R17
0x007C	 0xF009   BREQ       L_main0
L__main2:
;SSA.c,32 :: 	asm nop;
0x007E	 0x0000   NOP
L_main0:
;SSA.c,34 :: 	Delay_10ms();
0x0080	 0xDFE9   RCALL      _Delay_10ms+0
;SSA.c,36 :: 	}
L_end_main:
0x0082	 0xCFFF   RJMP       L_end_main
; end of _main

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 :

f2(int a, int b) { }

f1(int x, int y) {
  // 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 C 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