zayac/eq — pull request #5 by zayac (2012-10-18 14:31:22+00:00)
Title: SSA and Phi node implementation

### Description
We build a control flow graph and perform a conversion to static single
assignment for according to the following algorithm:

1. Create a new block with `head` statement allocated (the beginning of
`controlflow_pass_block` function).
2. If previous blocks were body of the `if` statement, we need to link them
with the existing block.
3. Verify all identifiers inside the current statement according to the scheme
(`ssa_verify_vars` function):
1. For all identifiers except those in the left part of the assignment
statement
1. Try to find a record inside a variable hash set (`struct basic_block:var_hash`) and substitute identifier name for the string `id_new` inside the record (`ssa_redefine_vars` function) if found.
2. If variable record is not found inside the hash create a new initial entry (`ssa_declare_new_var` function).
2. For identifiers in the left part of the assignment statement:
1. Generate a new variable name (`ssa_reassign_var`), replace an old one,
and substitute an `id_new` field inside the relevant hash set record.
4. In case the current statement is `IF` statement
1. Create a new block for a "true" block.
2. Copy the variable hash in the newly created block (`ssa_copy_var_hash`
function).
3. Recursively perform block construction for "true" block body. (go to step
2).
4. Merge variable hashes of inner and outer blocks.
5. If "false" block exists
1. Create a new block for a "false" block.
2. Copy the variable hash in the newly created block (`ssa_copy_var_hash` function).
3. Recursively perform block construction for "false" block body. (go to step 2).
4. Merge variable hashes of inner and outer blocks. We separately consider two cases here for every variable:
* Variable was changed inside both, "true" and "false" blocks.
* Variable was changed inside just one block.
5. Repeat algorithm for the next statement.

### Example
Consider the following example:
```latex
\begin{eqcode}{\mu}{\ }{\ }{\type{Z}}
x \gets 1 \lend
x \gets x - 3 \lend
y \gets 0 \lend
\qif {x < 3}
y \gets x \cdot 2 \lend
w \gets y \lend
\qif {x + y < 5}
y \gets w + x \lend
\qendif
\qelse
y \gets x - 3 \lend
\qendif
w \gets x - y \lend
z \gets x + y \lend
\return {z} \lend
\end{eqcode}
```

#### CFG representation
To output flow graph you need to build the compiler with `-DCFG_OUTPUT` flag.
The [DOT language](http://www.graphviz.org/doc/info/lang.html) is used for graph description
In order to get a visual representation of the graph run these commands:
```
$ eq any_source_file.tex | sed -n '/^digraph * /p' > any_dot_file.dot
$ ccomps -x any_dot_file.dot | dot | gvpack -array3 | neato -Tpng -n2 -o any_output_file.png
```

For current example CFG looks like this:
`digraph mu { 0; 1; 0->1; 2; 1->2; 3; 2->3; 1->3; 4; 0->4; 5; 3->5; 4->5; }`

Notice that a "dummy" block #3 with just one `DUMMY_NODE` is created during
typechecking stage for correct flow representation.

SSA convertion result for this example:
```python
def __main():
_mu_x = 1
_mu_x0 = (_mu_x - 3)
_mu_y = 0
if (_mu_x0 < 3):
_mu_y0 = (_mu_x0 * 2)
_mu_w = _mu_y0
if ((_mu_x0 + _mu_y0) < 5):
_mu_y1 = (_mu_w + _mu_x0)

else:
_mu_y2 = (_mu_x0 - 3)

_mu_w = (_mu_x0 - < _mu_y0 _mu_y1 _mu_y2 >)
_mu_z = (_mu_x0 + _mu_y2)
return(_mu_z)
```

### Future work
It seems that the current implementation is quite dirty, and it needs fixes or
refactoring in the future. The major cases should work correctly.
For instance, the following example causes a memory leak:
```latex
\begin{eqcode}{e}{d}{\type{Z}}{\type{Z}}
d \gets 1 \lend
\qif {4 > 0}
a \gets 2 \lend
\qelse
d \gets 2 \lend
\qendif
\return {d} \lend
\end{eqcode}
```