contifier bug

Matthew Fluet Matthew Fluet <fluet@CS.Cornell.EDU>
Sun, 25 Feb 2001 13:41:21 -0500 (EST)


> > The transformation code had a small bug in handling uncontifiable sccs;
> > it's fixed now.  Here are the results for kit (using G0 mlton, so the
> > times are a little high):
> 
> That fixed the bug when running with contifyStrategy Dom.  It did not fix the
> bug when running with contifyStrategy CallCont.  I turned off the call to the
> shrinker in contify.fun and turned on type checking for the following run, which
> shows the transformation produces a function out of scope.
...
> mlton: action_0 has no handlers property

I've reconstructed the error and I think I understand what's going on. 
Here is the problematic section, [n] indicates the number of occurences of
the call that appear in the function. 

fun get_4 () = ... [1]L_60065 (continue_1 ()) ...
fun continue_1 () = ... [1]scan_0 () ...
fun scan_0 () = ... [2]scan_0 () ... [3]action_2 () ...
fun action_2 () = ... [1]action_2 () ... [2]identifier_1 () ... [24]continue_1 ()
fun identifier_1 () = ...

So, we have 
               ACall       ACont    ACC1        ACC2     ADom
continue_1     L_60065     L_60065  L_60065     L_60065  L_60065
scan_0         continue_1  L_60065  continue_1  L_60065  scan_0
action_2       Unknown     L_60065  L_60065     L_60065  continue_1
identifier_1   Unknown     L_60065  L_60065     L_60065  action_2

ACC1 combines ACall and ACont, deferring to ACall when the two analyses
differ.  ACC2 defers to ACont.

ACC1 is what is currently being used.  Note, it is not a safe analysis
according to the paper definition of safe, because (scan_0, action_2) in
Tail, but ACC1(action_2) = L_60065 notin {scan_0, ACC1(scan_0), Unknown}. 
I had thought about proving that ACC1 is a safe analysis, but clearly this
is a nice counter example.  On the other hand, it is safe by the A*
definition, because ACC1(action_2) in A*(scan_0) U {Unknown} = {scan_0,
continue_1, L_60065, Unknown}. 

ACC2 is safe under both definitions.

The error is arising with ACC1 because the set of functions to be
contified at L_60065 is continue_1, action_2, and identifier_1.  Looking
at the call graph of these functions, there are only the edges:
(action_2, action_2), (action_2, identifier_1), (action_2, continue_1),
so the sccs, topologically sorted, are:
[[action_2],[continue_1],[identifier_1]]
There is no problem with outside callers, so we decide to prefix L_60065
with [action_2, continue_1, identfier_1], and when we actually do the
transformation, we add declarations for these functions in reverse order
after the declaration for L_60065, with scan_0 contified in continue_1.
There's the scoping problem: continue_1 (with scan_0 calling action_2) is
declared before action_2.

Arguably, we could switch to ACC2.  On the other hand, because ACC2 is
safe by the A* definition, I'd really rather fix the transformation to
work with it.  And the solution is not particularly difficult.  The basic
problem was that no edge (continue_1, action_2) was included in the
constructed mini call-graph, corresponding to the (scan_0, action_2) call.
Yet, we really have this information available.  Because we process the
nodes according to a dfs of the analysis forest, by the time we process
L_60065, we've already determined everything that should be contified in
continue_1, action_2, and identifier_1.  Therefore, we just build the mini
call-graph by recursively including edges in prefixed functions.


I'll run through the regression and benchmarks this evening and send out
the fix tomorrow morning.