[MLton-devel] The Essence of Compiling with Continuations Retrospective

[Stephen Weeks]

Hi Matthias.  I ran across "The Essence of Compiling with
Continuations" (TECC) retrospective on the web the other day, and
wanted to send you my thoughts on it.

First, I wanted to correct a couple of incorrect statements about
MLton. 

	More recent compilers, such as ... MLton, ...: only functions
	with known continuations are converted to CPS

In MLton (since August 1998), all functions are completely converted
to make continuations explicit.  There is no selectivity.

	This limited use of CPS is called "contification" or "local
	CPS conversion".

Contification and local CPS conversion are two different things.
Contification is an optimization in which nontail calls are converted
to tail calls and returns are turned into jumps, whenever an analysis
can determine that the continuation of the nontail call is "known".
On the other hand, local CPS conversion is a transformation on a
direct-style IL that makes continuations explicit enough so that
optimizations that require them (like contification) can be
performed.  So, local CPS conversion can enable contification to be
expressed (and indeed Reppy gives a particular contification analysis
in his paper).  But there is no need for local CPS conversion in MLton
since our IL makes all continuations explicit.

Next, I wanted to mention the impact that TECC has had on me and MLton
and give a brief history of MLton's main IL used for optimization.

MLton has always used a simply-typed first-order intermediate language
in which a program is a collection of mutually recursive functions.
Over the years, the language used to represent the function bodies has
gone through two major shifts.  MLton originally used an ANF based
representation, and this decision was in large part based on TECC,
which had convinced me that CPS had nothing to offer other than
useless administrative redexes and redundant continuation arguments.

The earliest snapshot of MLton with this ANF IL is from March of 1998.
After playing around with optimizations on this IL for a few months,
we decided that there were some problems with the IL.  These stemmed
from the lack of explicit labels for code blocks in the IL.  This lack
prevented us from conveniently expressing loops, flattening tuples
across join points, and from doing optimizations like contification,
which required an explicit continuation to jump to.  So, in August of
1998 we began to transition to a new IL in which basic blocks were
explicit.  We called this our CPS IL, although in reality it was an
ANF/CPS hybrid, and was probably closer to ANF than to what most
people called CPS.  For example, while in TECC ANF you would write for
a nontail call

	(let ((x (V V1 ... Vn))) M)

in our CPS IL we would write

	(let ((l (\x.M))) (l (V V1 .... Vn)))

The point being that we extended ANF with the ability to define basic
blocks (continuations) and to explicitly write the continuation at a
nontail call.  So, our CPS IL kept the benefits of ANF over CPS that I
had learned from TECC, namely no useless administrative redexes or
redundant continuation arguments.  But, our CPS IL had one thing that
I think that ANF misses -- namely the explicit naming of basic blocks
and a clear connection between these blocks and traditional basic
blocks of assembly code.

Once we had explicit continuations, we were able to add a simple
contification optimization (not using dominators), which we did in
September 1998.  We also continued with the transition from our pure
ANF IL to our CPS IL, which was completed by January of 1999, and went
out with the original public release of MLton in March 1999.

When we began work on contification using dominators in November of
2000, the CPS IL was pretty much the same.  As we were working on
implementing this optimization, as well as a couple of others
including common-subexpression elimination, we found a weakness of our
CPS IL that interfered with the optimizations, sometimes making the
transformations more complex and sometimes causing us to miss cases
that we knew we should be able to optimize.  What we found was that
our transformations had to go to quite a bit of effort to produce
output that met the lexical scoping requirements of CPS, which
requires variable uses and continuation uses to occur within the scope
of their definition.

Because contification using dominators moves quite a bit of code
around based on a whole-program analysis, it had to be very careful to
ensure that the uses of continuations occurred within the scope of
their definition.  In some cases it might even have to skip an
optimization because it was unable to produce properly scoped
code. Other intraprocedural optimizations that performed a lot of code
rewriting or motion had to be very careful to ensure that variable
uses were correctly scoped.  For example, with common-subexpression
elimination, there was a mismatch between the dominator computation
used by the optimization and the lexical scoping requirements of the
language.  For example, we might have that x = y * z dominates w = y *
z, and like to replace the latter with w = x.  However, we could not
do so unless w = y * z was in the scope x.

In short, we found that the explicit scoping requirements of CPS were
too constraining.  So, in August of 2001 we began to transition to a
new IL that did not have any scoping requirements on continuations,
instead making them all mutually recursive (after all they are just
assembly labels for basic blocks).  We also eliminated the explicit
scoping requirement on variables, instead going to the implicit
requirement that a definition of a variable dominate all of its uses.
Of course, this is just the usual SSA condition, and so we called this
our SSA IL.  It is in fact very close to SSA, with the major
difference being that we used gotos that pass arguments instead of
phi-functions.

>From the perspective of typed ILs, I view the scoping requirements of
CPS as pushing some of the work of the IL typechecker into each pass,
by requiring each transformation to produce the scoping information
necessary to make it easy for the type checker that variable
definitions dominate uses.  On the other hand, with SSA, the
transformations don't have to do any extra work, while the type
checker has to do more, in that it has to do a dominator computation.
So, with CPS, we complicate many transformations to make the type
checker simple, while with SSA, we complicate one type checker to make
many passes simpler.

We completed the transition to SSA in December 2001, and have been
using SSA as our main IL for optimization since then.  We are quite
happy with it.  The only major weakness in our SSA IL that we know of,
and are currently working on, is orthogonal to the whole ANF/CPS/SSA
discussion.  We are currently working on making data representations
more explicit in order to do optimizations with array address
computations, flattening of ref cells, and the like.

So, to sum up, I see TECC as the first couple of steps on the path
from traditional CPS to SSA, which I view as a superior IL for
performing optimizations.

CPS -->
	1. eliminate administrative redexes
	2. eliminate redundant continuation arguments -- treat
		the continuation as a global
	3. name local blocks
	4. eliminate scoping rules on block labels and variables and
		replace with dominator condition on variables
--> SSA

Oh well, that was a bit longer than I planned when I started :-).  I
hope you found it informative and interesting.  Feel free to ask any
questions you may have, or to forward it on to your coauthors (or
others) that you think might be interested.


-------------------------------------------------------
This SF.net email is sponsored by:
The Definitive IT and Networking Event. Be There!
NetWorld+Interop Las Vegas 2003 -- Register today!
http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel