Loop-local variable in Cytron's SSA algorithm

I am trying to write a compiler that converts a simple imperative language to SSA form, but I am having trouble with loops. As an example, I have some code that looks like:

fun count() {
    i = 0;
    while(i < 10) {
        x = i + 1
        i = x;
    }
    return i;
}

I then convert it to a control flow graph that looks like this:

0 ->
    predecessors                = []
    successors                  = [1,2]
    dominators                  = [0]
    strict dominators           = []
    dominatees                  = [0,1,2]
    dominance frontier          = []
    inverse dominance frontier  = []
    immediate dominator         = none
    immediate dominatees        = [1,2]
    instructions                =
        r := 0
        i := 0
        if i >= 10 goto 2 else goto 1

1 ->
    predecessors                = [0,1]
    successors                  = [1,2]
    dominators                  = [0,1]
    strict dominators           = [0]
    dominatees                  = [1]
    dominance frontier          = [1,2]
    inverse dominance frontier  = [1]
    immediate dominator         = 0
    immediate dominatees        = []
    instructions                =
        x := i + 1
        i := x
        if i 
    predecessors                = [0,1]
    successors                  = []
    dominators                  = [0,2]
    strict dominators           = [0]
    dominatees                  = [2]
    dominance frontier          = []
    inverse dominance frontier  = [1]
    immediate dominator         = 0
    immediate dominatees        = []
    instructions                =
        r := i
        ret

The issue I'm running into is that when I use the algorithm for placing phi nodes described in section 5.1 of Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, I get something like this:

```
0 ->
predecessors = []
successors = [1,2]
...
instructions =

Congratulations for implementing Cytron's algorithm! You are one of a select few who have attempted it.

Most compilers these days tend to use a much simplified algorithm which inserts and then removes redundant phi nodes. We will go through that later. Be aware that although it produces minimal SSA form on reducible flow graphs, it sometimes doesn't on irreducible flow graphs. But all in good time.

I'm going to go through a couple of related points, some of which you've probably already noticed, but I'm going to mention anyway to make this answer a bit more self-contained.

First off, the definition of $\mathit{HasAlready}$ in the paper is doesn't make a lot of sense. It is defined as follows:


$\mathit{HasAlready}(*)$ is an array of flags, one for each node, where $\mathit{HasAlready}(X)$ indicates whether a $\phi$-function for $V$ has already been inserted at $X$.

Already, we see a problem: Where's $V$ in this query? But then, in figure 11, we see this code:


$\texttt{if}\,\mathit{HasAlready}(X)

• If there is a Phi assignment whose arguments are the returned value

of the assignment and one other value, remove it and rename the assigned variable to that other value.

An example of the first rule is in block 2, with r_3. That is unused, so we remove it.

An example of the second rule is in block 1, with r_1. Here, r_1 can be replaced with r_0 everywhere. In general, you might find something like this:

v_1 := Phi(v_1, v_2, v_2, v_1, v_2)

In that case, remove the Phi and replace v_1 with v_2 everywhere.

It should be clear why these two simplifications are valid transformations. What's interesting is that if you apply these two rules until none apply any more, you get minimal SSA form if the flow graph is reducible.

In your case, you get this:

0 ->
    r_0 := 0
    i_0 := 0
    x_0 := 0
    if i_0 >= 10 goto 2 else goto 1

1 ->
    i_1 := Phi(i_0, i_2)
    x_2 := i_1 + 1
    i_2 := x_2
    if i_2 
    i_3 := Phi(i_0, i_2)
    r := i_3
    ret

Now you can see that all of the Phi nodes for x have been eliminated, as we would hope. Also, x_0 and r_0 are dead definitions, but they can be removed later.

Just as a last comment, the very notion of a "basic block" isn't necessarily that important in modern compilers any more, after you have resolved scopes and before you generate assembly language.

The "sea of nodes" representation is a case in point. Many modern IRs tend to think in terms of sequencing constraints instead of linear blocks of code. That way, you don't have to deal with basic blocks specially as in this example.

If you think of each instruction as its own "basic block", then Cytron's algorithm should work perfectly!

StackExchange Computer Science Q#124405, answer score: 4