Re: wip-cse

[Andy Wingo]

On Mon 16 Apr 2012 14:36, address@hidden (Ludovic Courtès) writes:

> Initially, I was expecting things like:
>
>   (f (* a b) (* a b))
>   =>
>   (let ((x (* a b)))
>     (f x x))
>
> but AIUI the CSE pass here eliminates duplicate references when they are
> superfluous, but not when they are needed as above, right?

This pass does a few related things:

 * Replacement of an expression with a reference to a lexical
   identifier.

 * Inferring the boolean value of an expression, given previous
   expressions that were true.

 * Eliminating an expression where it can cause no effect.

It does not name new values, however.  If we switched to CPS as our IR,
then we would have a lot more names, and CSE could be more effective.

>> I'm attaching a log of the things that it folds in a normal Guile
>> build.
>
> I’m not sure what the messages mean.  Could you explain?

Sure.  In these I just replaced some of the calls to "log" with "pk".
The "inferring" lines indicate boolean-valued expressions that were
folded.  The "elided" lines indicate useless expressions in effect
context.  The "propagate-value" lines... hm, there aren't any.  They
would correspond to replacing expressions with lexical-refs.  That's a
bug probably, caused by the switch to vhashes, I would imagine.  I'll
take a look.

>> I'm pretty happy with it, except for the speed.
>
> What impact does it have on compilation time in module/?

Dunno.  It almost doubles the fresh recompilation of of peval, though
(1.3s to 2.3s).
>
>> seeing that lookup in vhashes is fairly slow.  Dunno.  If we can speed
>> up vhashes somehow then we win in CSE, peval, and other passes, so
>> probably it's best to focus there.
>
> I think we’ll need C-level profiling to see what’s going on.  Do you
> have such info already?  Otherwise I can look into it.

I don't have any such info yet.

> Also, a bit of CSE could help:  ;-)

Hmm :)  If I had to guess, it would be:

> scheme@(ice-9 vlist)> ,optimize   (%vhash-assoc key vhash eq? hashq)
> $3 = (begin
>   (define khash
>     (let ((size (vector-ref
>                   (let ((s vhash))
>                     (if (eq? (struct-vtable s) <vlist>)
>                       (struct-ref s 0)
>                       ((@@ (srfi srfi-9) throw)
>                        'wrong-type-arg
>                        'vlist-base
>                        "Wrong type argument: ~S"
>                        (list s)
>                        (list s))))
>                   3)))
>       (and (> size 0) (hashq key size))))

^ Here we see a call to hashq.  Guile doesn't recognize that it's a pure
function (depending on &mutable-data, causing &type-error), so it
assumes that it could mutate a toplevel variable, causing future checks
not to fold.  (Because a future access to <vlist> does not commute with
a call to `hashq'.)

Also "vhash" is a toplevel ref.  If it were lexically bound, I think
things would be a little bit different.  Dunno!

Regards,

Andy
-- 
http://wingolog.org/