Re: wip-cse

[ludo@gnu.org (Ludovic Courtès)]

Hi Andy,

Andy Wingo <wingo@pobox.com> skribis:

> I just finished work on the "wip-cse" branch and would like to merge it
> in sometime.  It does a form of common subexpression elimination.  It's
> a post-pass, designed to run after peval.

The examples in cse.test suggest that it does a good job.  :-)

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?

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

> I'm pretty happy with it, except for the speed.

What impact does it have on compilation time in module/?

> I'm reasonably confident as to its complexity, but once again we are
> 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.

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

--8<---------------cut here---------------start------------->8---
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))))
  (let loop ((base (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)))))
             (khash khash)
             (offset
               (and khash
                    (vector-ref
                      (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))))
                        5)
                      khash)))
             (max-offset
               (let ((s vhash))
                 (if (eq? (struct-vtable s) <vlist>)
                   (struct-ref s 1)
                   ((@@ (srfi srfi-9) throw)
                    'wrong-type-arg
                    'vlist-offset
                    "Wrong type argument: ~S"
                    (list s)
                    (list s))))))
--8<---------------cut here---------------end--------------->8---

Here (vlist-base vhash) occurs three times; this could be reduced
manually to one.  Then there’s (vlist-offset vhash), which repeats the
same struct type checking.

In the body itself I don’t see anything obvious.

Thanks,
Ludo’.