How to represent merging of variables / Phi functions

Created by: eliotmoss

This is an update of a proposal from a year ago.

The current Mu definition of SSA-form has labels, branches to labels, and Phi functions just after labels.

I propose an alternative, which we might call "goto with values". It is similar to continuation passing style except that all the continuations are statically defined (one for each label). This alternative would work as follows:

• Each label would have zero or more (SSA-variable : type) pairs. These SSA-variables are local to the block that starts at the label.
• Each branch label (both labels in a conditional branch, the single labels in an unconditional branch, etc.) would list locally visible values being "sent" to the branch target.

Example: x = 3; y = 25; goto l(x, y); ... l: (x2:int<32>,y2:int<8>)

This form makes it clear that the association ("assignment") of values to phi-variables has to happen as part of the control transfer. Phi-functions are simply one way of representing that, but they're not not a way that seems immediately helpful for code generation.

I further observe that the current definition apparently allows any value to be passed in to a Phi, but I think it should be restricted to global/constant SSA variables or SSA variables defined in the sending block. The new form perhaps makes that clear, not least because with it you can explicitly disallow referring to local SSA variables defined in other blocks.

Putting these another way, non-global SSA-variables have a scope only from where they are defined to the end of their block. Some may be defined at the label that start the block and others may be defined later, but all live values must be mentioned at branches and explicitly passed on.

Compared with traditional SSA form this may appear verbose. However it has at least a couple of advantages:

• A code generator or optimizer need not perform a live variable analysis to know what is live at a given point in the code.
• Longer live ranges are broken up into smaller ones, which may allow better register allocation, and which is very suited to a coalescing register allocator.
• This form appears simpler to deal with in a formal specification of Mu.