Single Static Assingment Optimization   mikroBasic PRO for FT90x Specifics >

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 mikroBasic PRO for FT90x, 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

sub procedure SSA_Test(dim y as integer, dim k as integer)
  if (y+k) then
    asm 
      nop
    end asm
  end if
end sub

main:
  SSA_Test(5,5)
end.

With SSA enabled, sub procedure SSA_Test this example is consisted of 4 asm instructions :

0x0090  0x44200010  ADD.L	R2, R0, R1
0x0094  0x5BE14002  CMP.S	R2, #0 ($0)
0x0098  0x00280028  JMPC	R30, Z, #1 ($1), L__SSA_Test2
;Example.mbas, 6 ::     nop
0x009C  0x44004000  NOP	

Without SSA enabled, sub procedure SSA_Test this example is consisted of 6 asm instructions :

0x0090  0xAA1F8008  LDI.S   R1, SP, #8 ($8)
0x0094  0x4410C00C  BEXTS.L R1, R1, #0 ($0)
0x0098  0xAA0F8004  LDI.S   R0, SP, #4 ($4)
0x009C  0x4400400C  BEXTS.L R0, R0, #0 ($0)
0x00A0  0x44000010  ADD.L   R0, R0, R1
0x00A4  0x5BE04002  CMP.S   R0, #0 ($0)
0x00A8  0x0028002C  JMPC    R30, Z, #1 ($1), L__SSA_Test2
;Example.mbas, 6 ::     nop
0x00AC  0x44004000  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 as function2 parameters, then parameter order should remain the same :

  sub procedure f2(dim a as integer, dim b as integer)
  
  end sub
  
  sub procedure f1(dim x as integer, dim y as 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)
  end sub
  

• 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.

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 :

sub procedure SSA_Test()
dim y as char

  if (y) then    ' Variable y might not have been initialized
    asm 
      nop
    end asm
  end if
  	
end sub

main:
  SSA_Test()
end.

Related topics: Code Optimization, FT90x Specifics, mikroBasic PRO for FT90x specifics, Memory type specifiers