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/
