Here's a much more complete description of how I do SSA, beyond just how I do Phis.
This describes how I do SSA form, which avoids the need to have any coupling between CFG data structures and SSA data structures.
Let's first define a syntax for SSA and some terminology. Here's an example SSA node:
A = Add(B, C)
In reality, this will be a single object in your in-memory representation, and the names are really addresses of those objects. So, this node has an "implicit variable" called A; it's the variable that is implicitly assigned to when you execute the node. If you then do:
X = Sub(A, 1)
Then "A" is just a pointer to the Add node, and we're using the implicit variable "A".
Here's an example function:
int foo(int a, int b)
{
int x;
if (a)
x = b + 1
else
x = b * 2
return x + 42;
}
Here's an SSA program with a Phi in Pizlo form:
root:
A = GetArgument(0)
B = GetArgument(1)
Branch(A, then, else)
then:
X1 = Add(B, 1)
Upsilon(X1, ^X)
Jump(return)
else:
X2 = Mul(B, 2)
Upsilon(X2, ^X)
Jump(return)
return:
X = Phi()
R = Add(X, 42)
Return(R)
In Pizlo form:
-
Every SSA node has an implicit variable, as mentioned above.
-
Every Phi node has a shadow variable in addition to the implicit variable.
Let's say that given a Phi like "X = Phi()", the implicit variable is called "X", and the shadow variable is called "^X".
Therefore, the semantics of an upsilon like "Upsilon(X1, ^X)" is just "set ^X = X1". And the semantics of a Phi like "X = Phi()" is just "set X = ^X".
In other words, you can think of Upsilon as being a side effect (a store to a shadow variable). And you can think of Phi as being a side effect (a load from a shadow variable). You can model them that way in your effect analysis to block reordering Upsilons and Phis.
But also, the shadow variables of Phis in Pizlo form are "Static Single Use" (SSU) variables. This falls out naturally from the fact that the only syntax for loading a shadow variable is the Phi itself. So you can think of Pizlo form as "SSA-SSU form".
The main benefit of this form is that basic blocks - and all CFG data structures - have zero knowledge about SSA. There are no basic block arguments. There's no requirement that Phis appear at the tops of blocks. In fact, this is a valid program in Pizlo form (albeit suboptimal):
M = Stuff(...)
Upsilon(M, ^N)
N = Phi()
MoreStuff(N)
Here, there's a Phi in them middle of a basic block, and there's an Upsilon just before it. That's fine. This is important, because it means that you can do CFG transforms that blow away control flow edges without worrying about fixing your Phis.
In any Pizlo-form compiler, you'll want to have a Phi simplification pass, which you can implement either by running Cytron or by running any other SSA converter. The simplest is just to just fixpoint the rule that if you have a Phi that has Upsilons that only use the Phi or exactly one other value, then replace the Phi with that other value.
First introduced by @pizlonator in the comments of this post: https://news.ycombinator.com/item?id=43009952