[MLton] Interference Graphs

[Matthew Fluet]

>> The only difference from a 'traditional' SSA is that we use 'goto with 
>> arguments' rather than 'phi-nodes'.
> 
> Interesting.  Is this for doing continuations, or does it confer some 
> other advantage?  I'd be interested to hear the retrospective on that 
> design choice.

It wasn't motivated by an implementation strategy for continuations; 
that is handled very differently in MLton.

The SSA IL was designed in August 2001 as a replacement for the CPS IL:
   http://mlton.org/pipermail/mlton/2001-August/019689.html

As an aside, from at least the time that I joined the MLton project
(June 2000), "CPS" was a bit of a misnomer for that IL.  Indeed, one of
the things you couldn't do with continuations was to "pass" them as
first-class values.  In our ICFP01 paper, we named it "FOL" (First Order
Language).  I recommend that paper for a bunch of references on the
correspondence between CPS, SSA, and A-normal form.  Especially, take a
look at Appel's "SSA is Functional Programming", which, although I 
wasn't particularly familiar with it at the time, was probably an 
inspiration in the IL design.

The continuations in the CPS IL essentially served as intraprocedural
control-flow: targets of conditionals were continuations, targets of
(unconditional) gotos were continuations.  They also served as the way
of getting back "into" a procedure: a non-tail function call returned to
a continuation, a raised exception was handled by a continuation.  (I'm
guessing that the name "CPS" got used because like true continuations in
true CPS, these "continuations" served as a unifying control-flow
construct.)

Not surprisingly, the CPS IL looked a lot like a little functional
language.  A CPS IL program consisted of a set of mutually recursive
first-order functions (with a distinguished main); each function had
formal arguments and had an expression body, which consisted of
lexically scoped value bindings and continuation bindings (whose bodies
were themselves expressions), terminated by a control transfer (a
conditional or goto to a declared continuation, a non-tail call that
would return to a local continuation,  or a return or tail call).  Since
the continuations looked like little (first-order) functions, they
themselves had formal arguments arguments that were lexically bound it
their body.  (The continuation itself was also bound in the body; this
was critical for expressing function local loops.)  Transferring control
to a continuation meant passing actuals for their formals.

At the time of the ICFP01 paper, we were running into limitations with 
the lexical scoping of continuations.  Indeed, in the ICFP01 paper, to 
streamline the presentation, FOL allowed one to bind a collection of 
mutually recursive continuations.  This wasn't allowed in the
implementation of the CPS IL.  Often, the ability to nest one 
continuation in the body of another was enough to "fake" mutually 
recursion, but there were program transformations that we wished to make 
that wouldn't be expressible without the mutual recursion (the 
optimization described in the ICFP01 paper includes some such missed 
opportunities).

In designing a new IL, we knew we wanted to ditch the lexical scoping of
continuations.  We also wanted to leverage the fact that our compilation
strategy turned a higher-order ML program into a first-order program 
allowing us to utilize "traditional" optimizations.  Both of those 
suggested something like SSA.  On the other hand, we already had a lot 
of familiarity with the existing IL that allowed us to gensym new 
variables when needed and simply pass them as arguments to continuations 
when we needed to get them to the right place.  Also, Stephen may have 
been more intimately familiar with the related work mentioned above. 
Looking at Appel's paper now, I see that it outlines something very 
similar to what we have; at the same time, I don't think Appel went 
quite far enough -- I would argue not only that "SSA is Functional 
Programming", but also that "SSA is better *represented* as Functional 
Programming".  I try to argue this more below.

The SSA IL has undergone some minor revisions since Aug 2001, but it is
pretty much equivalent to the one Stephen describes in the email.

I think I can safely say that we have been very pleased with the IL.
Some points are mentioned in that e-mail:
  * it directly expresses the control-flow graph
  * many optimizations (or sub-passes of optimizations) can be expressed
by a simple loop over the blocks of a function
    + for those that can't be expressed by an unordered loop over the 
blocks of a function, often a Depth First Search suffices, which is 
still very efficient in the IL.
    + for those that need to traverse the function according to the 
dominator tree, its fairly easy to get.

In our experience, it isn't worth maintaining the dominator tree for 
every intermediate SSA IL program; we compute for those few functions 
that need it.

Another points that I like:

  * a program in the IL is a functional data structure.  This means that
optimization passes are simply program to program transformations.  Some
have argued for a mutable IL because it saves space.  However, it also
makes the IL invariants considerably more complicated to maintain (see
the Dias&Ramsey paper in the Workshop on ML for more evidence).  We have
almost never uncounted a space problem with SSA IL optimizations.  (I 
believe that there is an outstanding issue with the deepFlatten pass for 
some large programs (MLKit and MLton with exception history and 
debugging on), though even there, I think it is due to the supporting 
analysis and not to the cost of having two copies of an SSA function 
live at the same time.)

But, really the biggest advantage of MLton's SSA IL over more
"traditional" notions of SSA is that it dispenses with two brittle
notions: phi-functions and versioned variables.

Phi-functions, in my mind, are just plain misleading.  If you look at a 
traditional SSA program, the physical presentation seemingly denies the 
essential dominance property.  By which I mean, staring at an SSA 
control-flow-graph figure in a compiler text book or paper, it just 
jumps out at me that there are many "uses" of variables (they happen to 
be in phi-nodes) that aren't dominated by their definitions.  These 
un-dominated "uses" of variables are o.k., because they are in phi-nodes.

Similarly, phi-nodes in a block have other "weird" properties: they have 
to appear at the beginning of a block; they have simultaneous assignment 
semantics.  This can be confusing in self-loops where the same variable 
is a phi-node argument and a phi-node result.

Finally, the (static & dynamic) semantics of phi-nodes demands a 
canonical ordering of the predecessors of a block and the (dynamic) 
semantics seems to require the program to remember where it came from, 
in order to "execute" the phi-nodes correctly.

Obviously, none of this is fundamentally incorrect.  Rather, I find that 
it is conceptually difficult for students to grasp.  It is also 
difficult to implement in an intuitive manner in a compiler IL.  I 
worked with the SUIF compiler infrastructure during one compilers 
course; they seemed to go to some lengths to allow phi-nodes to be 
represented by ordinary statements.  Yet, there are so many special 
properties of phi-nodes that it hardly seemed worth it.

None of these issues arise in MLton's SSA IL.  Look at the graphical 
output of an SSA IL program (the '-keep dot' option) and all uses of 
variables are really dominated by their definitions; some uses happen to 
be as arguments in an intraprocedural transfer to another block (e.g., a 
goto with arguments), but nonetheless, these uses are dominated by their 
definition.

Writing an intraprocedural transfer to another block as a goto with 
arguments leverages the intuition of argument passing; namely, that 
substituting actuals for formals happens simultaneously and at the 
beginning -- exactly those "weird" properties of phi-nodes.

And, finally, this representation requires no canonical ordering of a 
block's predecessor.

Now, MLton's SSA IL is a little lacking in the "A" department -- the 
formals of a block,  which constitute the definitions of those 
variables, aren't technically the targets of an "assignment."  On the 
other hand, while a variable can be "assigned" the result of a phi-node 
in traditional SSA, all the other special properties of phi-nodes makes 
it difficult treat this as a normal "assignment".

The other aspect of SSA that I think MLton's version improves upon is 
versioned variables.  In many/most presentations of SSA, there is an 
assumption that an imperative (C-like) program was converted into SSA 
form; in establishing the SSA condition, the conversion introduces 
versions of variables.  Sometimes this is completely explicit, like 
requiring that a phi-node only assign to and select among versions of 
the same variable.  This property holds immediately upon converting into 
SSA form, but it seems rather hard to maintain.

MLton, coming from a functional programming perspective, makes no 
attempt to relate any SSA IL variable to another.  The only relationship 
is the one expressed by the flow of actuals to formals in the 
control-flow graph.  In particular, gensyming variables (which are 
completely fresh and have no predetermined relationship to existing 
variables) is done extensively in SSA optimizations.  Similarly, 
alpha-renaming of variable has no effect on MLton's SSA optimizations.

Where I have found this difference between MLton's SSA and "traditional" 
SSA to be particularly relevant is in Partial Redundancy Elimination 
(PRE).  The original SSAPRE work (Kennedy, R., Chan, S., Liu, S.M., Lo, 
R., Peng, T., and Chow, F.; TOPLAS 99) only identifies redundancy 
between expressions that syntactically equivalent (ignoring versions of 
variables).  Such equivalent expressions might appear in the initial 
conversion from the source program into SSA form, but it seems hard to 
believe that they would be preserved by any other non-trivial 
optimization.  And, in MLton's SSA IL, we've many times alpha-converted 
the source program by the time we are in the SSA IL, so almost no 
expressions are syntactically equivalent.

So, the "traditional" SSA form allowed a rather brittle optimization to 
work well enough in practice.  The brittleness is in the fact that the 
optimization is not robust against alpha-renaming of the SSA program. 
In a sense, the optimization attacked a syntactic property of the 
program, rather than a semantic.

In dispensing with versioned variables (instead, having unrelated 
variables), MLton's SSA IL makes it much harder to get any benefit out 
of syntactic properties and biases optimizations towards semantic 
properties.  On the other hand, it doesn't immediately suggest any way 
of finding semantically redundant expressions.  Indeed, this is a pretty 
hard problem.  I poked at it for a little while without getting 
anything.  There were two separate attempts by graduate students to do 
PRE for MLton as final projects for courses, neither of which yielded 
great benefits (and, perhaps more importantly, neither of which yielded 
code to be incorporated into MLton).  Thomas VanDrunen's PhD 
dissertation (and related publications) seems to have yielded the most 
robust SSA PRE optimization, by relating the redundant expression 
problem to value numbering (which is itself much more a semantic 
property).  It's on my todo to try to incorporate VanDrunen's work into 
a PRE optimization for MLton; it could also be a good project for a 
graduate student looking for a final project in a compilers course 
(third time's a charm, right?) ;-)

Anyways, that's my retrospective on MLton's SSA IL.