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 PIC32, 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.
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.
With SSA enabled, procedure SSA_Test
is consisted of 3 asm instructions :
;Example.mpas, 29 :: if (y+k) then
0x9D000000 0x033A1021 ADDU R2, R25, R26
0x9D000004 0x10400002 BEQ R2, R0, L__SSA_Test2
0x9D000008 0x70000000 NOP
Without SSA enabled, procedure SSA_Test
is consisted of 5 asm instructions :
;Example.mpas, 29 :: if (y+k) then
0x9D000000 0x87A30002 LH R3, 2(SP)
0x9D000004 0x87A20000 LH R2, 0(SP)
0x9D000008 0x00431021 ADDU R2, R2, R3
0x9D00000C 0x10400002 BEQ R2, R0, L__SSA_Test2
0x9D000010 0x70000000 NOP
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 asfunction2
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
andlabel
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.
emcl
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; }
What do you think about this topic ? Send us feedback!