A catalog of ways to generate SSA

Pizlo form is not basic block with arguments, because basic blocks don't have arguments in Pizlo form.

I don't think basic block with arguments is CPS because CPS, in practice, involves return closures.

It's not, because the Phi's in Pizlo form introduce a Static Single Use variable, which makes them easy to analyze.

Allocas have no requirement that there's a static single use. They are quite hard to analyze.

Sure.

Let's first define a syntax for SSA and some terminology. Here's an example SSA node:

    A = Add(B, C)

    X = Sub(A, 1)

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;
    }

    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)

- 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)

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.

I presume their question is about "simple" techniqyes. With goto, the most famous one needs to compute dominance frontiers.

Doesn't every language with break-to-label (i.e. break out of multiple nested loops) effectively have goto, from an implementation standpoint?