On Tue, May 26, 2009 at 6:49 PM, Conal Elliott <[email protected]> wrote: > Hi Tom, > > I've been working on another code-generating graphics compiler, generating > GPU code. As always, I run into the problem of efficient common > subexpression elimination. In Pan, Vertigo & Pajama, I used lazy > memoization, using stable pointers and weak references, to avoid the > worst-case-exponential behavior you mention below. I'm now using a > bottom-up CSE method that's slower and more complicated than I'm going for. > > What's your latest wisdom about CSE in DSELs?
I wasn't able to find a solution that offered both performance and elegance, so I changed the fundamental operation of the DSL (in this case, atom). When atom was still a hardware description language, the compiler would combine several user defined expressions together resulting in very wide and deep expression trees, resulting in the same problem you are observing. But when I switch the target of atom from HDL to C, the compiler no longer needed to perform the same expression expansion. And since the user defined expressions are generally shallow -- at least in the case of my applications -- atom is able to get away with exhaustive equality comparison (deriving Eq). Sorry I can't be of more help. -Tom _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
