• Български
  • English

Building SolidOpt Static Single-Assignment Code Model On Top of The Existing Three Address Code

SolidOpt (www.solidopt.org) provides toolchain helpful for various code transformations like compilation, decompilation and optimization. The project has various of intermediary source code representations such as .NET IL, control flow graphs, call graphs, three address code, abstract syntax tree and etc.

We would like to implement a new source code representation following the rules of the Static Single-Assignment Form. SSA should be an extension of the existing TAC representation, embedding few more restrictions and features. It should have two distinctive aspects in comparison to the three address code.

"The first is that all assignments in SSA are to variables with distinct names.

p = a + b 
q = p - c
p = q * d
p = e - p
q = p + q
p1 = a + b
q1 = p1 - c
p2 = q1 * d
p3 = e - p2
q2 = p3 + q1

The same variable may be defined in two different control flow paths in a program. For example, the source program:

if (flag) x = -1; else x = 1;

y = x * a;

has two control flow paths in which the variable x gets defined. If we use different names for x in the true and the false part of the conditional statement, then which name should we use in the assignment y = x * a; Here is the second distinctive aspect of SSA comes into play. SSA uses a notational convention called the phi-function to combine the two definitions of x:

if (flag) x1 = -1; else x2 = 1;
x3 = phi(x1, x2)

..."(for further information see the Dragon Book)

Knowledge Prerequisite: C#, Basic knowledge of compiler code representations

Expected results: The final project should be able to transform TAC into SSA. An excellent achievement would be implementing the opposite transformation (SSA into TAC). SSA's phi functions should be supported.

Mentor: Vassil Vassilev