Re: Common subexpression elemination (CSE)

The relation to strictness is that you have much tighter control over when things are evaluated (typically) for something strict, so it is less likely to leak. Take the expression 'e + e' at some base type. It's harmless to CSE this to 'let x = e in x+x' because + is strict in x. Whereas '(e,e)' can't be CSE:ed to 'let x = e in (x,x)' without risking a space leak. It's not exactly strictness, it's more about knowing when a value is going to be consumed. Also, things that are "small" can be CSE:ed, since the evaulated form doesn't take more space than the unevaluated. -- Lennart On Nov 28, 2006, at 09:50 , Bertram Felgenhauer wrote:

Dinko Tenev wrote:

...

On 11/27/06, Lennart Augustsson wrote:

...

GHC doesn't normally do CSE. CSE can cause space leaks, so you can't do it willy-nilly. I'm sure there are some strict contexts where it could be done safely, but I don't think ghc uses that information (yet).

-- Lennart

My apologies in advance for asking possibly stupid questions, but I don't understand this.

How exactly can CSE cause space leaks, and what does this have to do with strictness?

Combining two expressions means that they're represented by the same memory location. In particular when you start evaluating the first, the second reference to the value will keep all of it alive even if parts of it could otherwise be freed. This is especially problematic for infinite lists.

http://hackage.haskell.org/trac/ghc/ticket/947

demonstrates this problem, caused by the little CSE that ghc does. (Note: This is not of the form "let x = term in ... term ...", but it will be once it's desugared and the simplifier has floated out the constant expressions from the "primes0" and "primes" functions)

I'm not sure how it relates to strictness. I'd be more worried about about the size of the data that's being kept alive. Numbers are more likely to be ok than lists.

Bertram _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users