tiger-ssa

[Download tiger-ssa.str]

The Stratego Tiger compiler is an experimental program transformation system. The high-level source language is Appel's Tiger language. I am developing a static single assignment form (SSA) conversion pass for Tiger programs. SSA is a sparse intermediate representation used in many modern optimising compilers.

Here is a simple example Tiger program fragment:

( x := 0;
 if x then while x < 10 do (y := x; x := x+1)
      else y := 0;
 z := x + y
)

Here is the SSA transformed version of the above Tiger program:

(a_0 := 0;
 (if a_0
  then while (b_0 := phi(y, e_0);
              c_0 := phi(a_0, f_0);
              c_0 < 10) do
         (e_0 := c_0;
          f_0 := c_0 + 1)
  else h_0 := 0;
  i_0 := phi(c_0, a_0);
  j_0 := phi(b_0, h_0));
 k_0 := i_0 + j_0)

You can download the Stratego source code for my tiger-ssa transformation pass. I run it in conjunction with the following commands:

parse-tiger < $inputfile | 
Tiger-Desugar | 
./tiger-ssa | 
Tiger-Ensugar | 
pp-tiger

tiger-ssa is based on the syntax-directed SSA transformation algorithm by Brandis and Mössenböck. SSA phi-functions are represented as ordinary function calls. In if statements, the first parameter of a phi-function corresponds to the variable from the then-branch, and the second parameter corresponds to the variable from the else-branch. In while statements, The first parameter corresponds to the loop-entry variable and the second parameter corresponds to the loop-carried variable.

There are a number of outstanding issues with this SSA transformation pass. It is no more than a proof-of-concept implementation at present, since it has the following deficiencies:

• No support for for loops or break statements.
• No support for multiple function declarations in a single source file.
• No let declarations for new variables introduced by the SSA renaming phase.
• There are currently no SSA optimisation algorithms for the Tiger/Statego compiler.
• Developed on Stratego 0.9 - old version of dynamic rules.

There was an earlier attempt at producing a Stratego/Tiger SSA pass. As far as I know it was never completed. The archived source code is still available.