[Top][All Lists]

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

CPS common subexpression elimination landed

From: Andy Wingo
Subject: CPS common subexpression elimination landed
Date: Mon, 07 Apr 2014 09:44:53 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux)


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

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:

     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.



reply via email to

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