peval update

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/

Re: peval update

[Ludovic Courtès]

Hi Andy!

(As you can see I’m lagging behind and notice guile-commits before
guile-devel.  :-))

Andy Wingo <wingo@pobox.com> skribis:

> Firstly, it now works on all of Guile's code -- all of its constructs.

Cool!

> 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).

Excellent!  I noticed that, as a side-effect (I suppose), it fixes
infinite recursion while trying to inline a function application with
static arguments but whose result does not depend solely on these
arguments (the example in commit
21524430e9d821014d6c0efbe4df74c12179c072).

It also removes the main reason for not having peval inline module-local
top-level bindings (the previous approach was way too aggressive.)  Have
you thought about it?

> 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.

Hmm, interesting.

> Demand-driven processing would also make `letrec' optimization more
> effective.  Currently `letrec'-bound bindings are not mutually inlined.

When there are no static arguments, right?

> 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.

OK.

Thanks for turning a nice hack into a practical optimizer!

Ludo’.

Re: peval update

[Andy Wingo]

Hi Ludo :)

On Sat 01 Oct 2011 16:45, ludo@gnu.org (Ludovic Courtès) writes:

> (As you can see I’m lagging behind and notice guile-commits before
> guile-devel.  :-))

As you can see I'm lagging behind 2012 and am answering mails from 2011
:)

> It also removes the main reason for not having peval inline module-local
> top-level bindings (the previous approach was way too aggressive.)  Have
> you thought about it?

Yes.  Of course we would need some guarantees about binding mutability:
if N toplevel definitions are compiled together in one module, and M of
those bindings are never set!, then those M definitions should be fair
game for inlining.

We would also need some more visibility regarding modules.  For example,
in the following code:

  (define x 10)
  (foo!)
  (define y x)

We don't know that the toplevel-ref of `x' in the definition of `y'
refers to the `x' defined above, because `(foo!)' could have changed the
current module.  The syntax expander knows these things, but not all of
that knowledge is residualized in the tree-il.

Perhaps we need to add fields to toplevel-{ref,define,set!} for the
module that was current at expansion time.  Perhaps this could lead to
coalescing toplevel-{ref,define,set!} and module-{ref,set!} into one
triumvarate of toplevel binding tree-il forms.

Andy
-- 
http://wingolog.org/