[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

thoughts on peval

From: Andy Wingo
Subject: thoughts on peval
Date: Wed, 21 Sep 2011 09:31:03 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux)


I was playing around with peval early this morning -- yay jetlag -- and
had some notes I'd like to share.

Firstly, I added a let-values inliner to peval.  It was fairly pleasant
to write.  It can do things like:

(let ((x 0))
      (lambda () (if (zero? x) (values 1 2) (values 3 4)))
    (lambda (a b)
      (+ a b))))
=> 3

By that I mean to say that it inlines to 3, at compile time.  Good
times!  Goes to show that peval is fairly flexible.

My goal is to have peval do well when compiling psyntax to produce
psyntax-pp.scm.  However it does not currently work -- the peval
aborts.  Looking into this issue, it seems that peval does not work for
any of our .scm files (!!!).  The reason for this is that the code that
looks to inline applications bails for a number of common procedure
types, including module-ref forms.  Module-refs are mostly produced by
macro expansion, such as the call to define-module* that starts most of
our .scm files.

I tried making peval leave module-ref calls alone, and it does let peval
proceed, but then things explode: since there is practically no
constraint on inlining, the code size and compilation time explodes.
Any call to a procedure whose definition is known is eligible for
inlining if any argument to the procedure is constant, including lambda
arguments, regardless of the size of the procedure being inlined.  It is
so bad that optimize.scm can't even compile itself, if you add a simple
clause for <module-ref> in the <application> block.

This concerns me a great deal.  We will need to work hard to
retain/regain O(N) compile times.  Before peval, compile times (with a
bootstrapped compiler) were roughly linear in program size.  If we
diverge too much now, we won't be able to compile large programs.

A short-term solution would be to add heuristics.  A more proper
solution would involve effort and size counters, as in the Waddell and
Dybvig paper.  It sounds doable.

Peval probably also needs to thread around some idea of the "context" --
whether an expression is in effect, value, test, or tail position.  This
can help enable additional optimizations.  It would help if peval were
demand-driven, as in that paper, so you would know in which context to
evaluate the operands; but, step by step.

Also, I think that peval is probably inlining too much, at least by
default.  By the time that code hits peval, all definitions in a file
are in one big <sequence>.  Peval assumes those definitions are static,
but that has not historically been the case.  At least by default, we
should only inline statically-bound definitions.

Finally I think that we should be more pragmatic regarding lexical
set!.  One set! should not abort optimization of an entire form.

I suppose the blockers for the next release would be the excessive
inlining thing.  We should also fix toplevel inlining.  Ludo, what do
you think?



reply via email to

[Prev in Thread] Current Thread [Next in Thread]