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.