Loop-local variable in Cytron's SSA algorithm

Question

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 < 10 goto 1 else goto 2

2 ->
    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                =
        r := 0
        i := 0
        if i >= 10 goto 2 else goto 1

1 ->
    predecessors                = [0,1]
    successors                  = [1,2]
    ...
    instructions                =
        x := phi(x, x)
        i := phi(i, i)
        x := i + 1
        i := x
        if i < 10 goto 1 else goto 2

2 ->
    predecessors                = [0,1]
    successors                  = []
    ...
    instructions                =
        x := phi(x, x)
        i := phi(i, i)
        r := i
        ret

I understand why a phi is necessary for i in basic block #1 and #2, but I don't understand why phis are necessary for x, and in fact they seem to break the renaming algorithm that follows (specifically, at one point where the renaming algorithm tries to pop off the S("x") stack, that stack is empty, because x was not assigned to in basic block #0). Did I somehow incorrectly implement this algorithm, or is there some subtlety I'm not understanding?

Answer 1

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) < \mathit{IterCount}$

...

$\,\,\,\,\,\,\,\,\mathit{HasAlready}(X) \leftarrow \mathit{IterCount}$

So $\mathit{HasAlready}(X)$ should clearly be an integer, not a flag. Its value represents the highest-numbered variable that has had a $\phi$-function introduced for each basic block.

Secondly, if you are constructing SSA form using basic blocks, then Cytron's algorithm as published doesn't deal with multiple assignments to the same variable within a basic block, because the they don't need $\phi$-functions. The set of assignments to a variable $V$ (denoted $\mathcal{A}(V)$ in the paper) only refers to the last assignment in a basic block.

Now what you've identified is the dual of this: the only "uses" which matter are any that occur before the first assignment in a basic block. That also means that no potential reaching definition of a variable is "used" in a basic block if there are no uses before that first assignment in the block.

Now I've forgotten a lot of the details here, but that might explain the pop issue in the renaming algorithm: there isn't an assignment to x in basic block 1 as far as Cytron's algorithm is concerned.

OK, now that's out of the way, here's what most compilers tend to do: insert $\phi$-functions everywhere for everything (using variable scopes so we don't go completely crazy), and then remove the redundant ones.

In your case, let's suppose that x is declared outside the loop and initialised with 0. We rename every assignment, then insert a $\phi$ at the start of every block (except the start block) with the incoming values from the last assignment in all predecessors:

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_1 := Phi(x_0, x_2)
    r_1 := Phi(r_0, r_1)
    x_2 := i_1 + 1
    i_2 := x_2
    if i_2 < 10 goto 1 else goto 2

2 ->
    i_3 := Phi(i_0, i_2)
    x_3 := Phi(x_0, x_2)
    r_3 := Phi(r_0, r_1)
    r := i_3
    ret

This is already valid SSA form, it is just not minimal SSA form.

Now we iteratively apply two transformations:

1. If there is a Phi assignmment whose value is unused, remove it.
2. 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 < 10 goto 1 else goto 2

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!