Sat Feb 6 08:11:49 CET 2010

Explicit memoization

It seems that performing explicit memoization (introducing local
variables) is one of the tricks that can make a code generation step
simpler by taking common subexpression elimination work out of the
hands of the compiler.

I'm thinking particularly of automatic differentiation: it's a problem
that ``uses'' sequential processing (deep dependency graphs due to
memoization) to reduce the amount of operations compared to symbolic

So, what is common subexpression elimination (CSE)?  It converts tree
structures into directed acyclic graph structures.

The big idea is that common subexpressions are often the result of
macro expansion: macros can copy code.  The rule then becomes: don't
copy code, always memoize.