cps & contification

Stephen Weeks MLton@sourcelight.com
Wed, 24 Jan 2001 12:43:34 -0800 (PST)


> Since there is no way of nesting all of the functions in x_49, nothing
> from that group is contified -- including x_35 and x_40.

This all or nothing business is annoying.  The better analysis results in less
being contified.  :-(

> Intuitively, this seems like a safe analysis, but it violates the
> current definition of safety:

The definition of safety was motivated by the transformation.  It was the
minimal constraints (except for the mutual recursion) I could think of so that I
could do the transformation.  If you don't require A(g) in {f, A(f), Unknown},
then I don't see how to make sure the resulting program is lexically scoped --
how do you ensure that a call to a local function is in the scope of its
definition.  Once you start contifying callers and callees in different
functions, it gets confusing.

> But, logic seems to say
> that sometimes all of these issues do come together. 

Yes, especially since if we change the analysis to a less precise one, we may be
able to contify more because the IL restrictions.  Perhaps we should consider
including the IL mutual recursion constraint in the analysis and definition of
safety.  It may not be the right thing to do for a paper, but it is right
optimization wise.

We should also try to figure out the relaxation of the safety that is just
sufficient to meet the lexical scoping constraints of the IL.

Longer term, we should think about the CPS IL.  What does lexical scoping buy
us?  As far as I can tell, the lexical scoping of local functions gives us an
order in which to process the basic blocks so that we can visit function
definitions before uses.  The lexical scoping of variables gives us partial
dominator information in that it assures us that the definition of a variable
dominates all of its uses.  Does it buy us anything else?  

Maybe the right way to go is to represent a toplevel function as a set of basic
blocks (local functions) with a main, and to infer the dominator information
when necessary.


Anyways, I've included the latest contify in the mainline code, with the default 
strategy as New.  I'm running tests now to make sure everything works out.