peval update

[Andy Wingo]

Hi!

I was hacking on peval recently, and wanted to give an update.

Firstly, it now works on all of Guile's code -- all of its constructs.
It's pretty careful to not reorder effects, though there could be bugs
of course.  Also it can be used for some simple (sub-0CFA) analysis to
prove that, for example, a prompt tag is unreferenced and so a prompt
can be removed.  This is important for the `while' case, that if no
`break' or `continue' clause is found, no prompt is residualized.

Also, peval is now strictly O(N), because it has "effort counters", as
in Waddell and Dybvig's paper.  Each call site in the source program is
allocated some amount of "effort", and if that effort is all used up,
peval aborts back to the inlining attempt and residualizes the call.  N
call sites * constant effort = O(N).

Peval also has size counters, to control code growth, but they are not
currently used.  Instead there are some heuristics.  We should fix this.

Another thing to fix is that peval doesn't always spend its effort
wisely.  It can visit operands more than once, which is
counter-productive.  It should memoize residual code emitted, as Waddell
and Dybvig do.  If it did this residualization at time of use instead of
time of definition, that would turn the algorithm into being
demand-driven, allowing more accurate code size computations.  It would
also allow context-specific processing of operands to calls, like in
test context or effect context.

Demand-driven processing would also make `letrec' optimization more
effective.  Currently `letrec'-bound bindings are not mutually inlined.
You can see the result of this in psyntax-pp.scm: things that are
inlined in the body are not inlined in the letrec-bound helpers.

That's really all the TODOs that I have, though I'm not sure when to get
to them.  Thanks a lot to Ludovic for producing such a lucid bit of
code!

Andy
-- 
http://wingolog.org/