[MLton] Interference Graphs
Matthew Fluet
fluet at tti-c.org
Tue Feb 13 22:54:12 PST 2007
>> 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.
More information about the MLton
mailing list