CPS common subexpression elimination landed

CPS common subexpression elimination landed

[Andy Wingo]

Hi,

Just a brief note to say that I've landed common subexpression
elimination on the new CPS intermediate language on the master branch.
It completely replaces the old pass over Tree-IL that I wrote about
here:

  http://wingolog.org/archives/2012/05/14/doing-it-wrong-cse-in-guile

The differences are these:

  1. The new pass operates on CPS instead of Tree-IL, so it sees more
     eliminatable expressions.

  2. The new pass uses a fixed-point data-flow analysis, avoiding bad
     complexity characteristics of the old implementation.

  3. The new pass rewrites the tree to make the scope chain exactly
     reflect the dominator tree, so that all dominating expressions are
     eligible for CSE.  See the notes from Stephen Weeks here:

       http://mlton.org/pipermail/mlton/2003-January/023054.html

     I didn't find the tree rewrite to be particulatly onerous; it's
     lines 490-498 in cse.scm.

  4. Bailout is no longer modelled as an effect; instead a new pass runs
     that prunes control-flow joins after bailouts, because a primcall
     to `throw' will never rejoin control flow.

  5. We still propagate truthy expressions, as the old pass does, so you
     can reduce (if a (if a 10 20) 30) to (if a 10 30).

As a simple benchmark, consider changing
module/language/cps/compile-bytecode.scm to default #:cse? to #f, and
thereby bootstrap a Guile without CSE.  Call that compiler A.  A normal
(with CSE) build would be compiler B.  Now the test case would be
compiling boot-9.scm with both compilers, with the option #:cse? #t.

In this case compiler B is about 4% faster than compiler A.  However, if
we set #:cse? #f for compiler A, compiler A is faster -- so CSE doesn't
really pay for itself yet at bootstrap time (though the new pass is
still faster than the old pass).

4% is not very much, although this was just one test.  However I think
CSE is an important building block for future work, and it does speed up
code, so I think we keep it on by default, as it was before.
Compile-time overhead appears to be about 7 or 8% of compilation time.

Regards,

Andy
-- 
http://wingolog.org/

Re: CPS common subexpression elimination landed

[Andy Wingo]

On Mon 07 Apr 2014 09:44, Andy Wingo <wingo@pobox.com> writes:

> The differences are these:

One more difference.  The old pass did a form of interprocedural CSE,
which was pretty neat.  The new pass does not do that.  Mostly the
reason it does not do so is to reduce complexity.  The other reason is
that the new pass runs after contification, so it sees bigger functions
than the old pass did, which had no way to understand contification.

Still, it's a limitation.  Oh well.

Andy
-- 
http://wingolog.org/