A simple tool for common subexpression elimination



As part of some of my various Julia side projects, I’ve put together a very simple tool to perform common subexpression elimination (CSE). The idea of CSE is that if you have an expression like:

y = f(x)
z = g(f(x))
a = 2 * g(f(x))

which calls f(x) 3 times and g(f(x)) twice, then you can get the same result by identifying and combining identical function evaluations, like so:

f_x = f(x)
g_f_x = g(f_x)
g_f_x_2 = 2 * g_f_x
a = g_f_x_2

which calls each function exactly once.

This optimization only makes sense if the functions are pure, that is if they have no side effects and don’t mutate their arguments. That makes it hard to apply CSE automatically inside Julia.

However, there are often situations where you know that all of your functions are pure, so it’s nice to be able to opt into this optimization. I’ve written CommonSubexpressions.jl to do just that. Just wrap your code in the @cse macro and it might magically become faster. Or it might explode horribly, because this is a brand new package and probably still has bugs. Use with caution.

If this ends up being useful or interesting, then I’ll go ahead and register it. Meanwhile, I’d appreciate any feedback.



It might be useful to provide also output to highlight where the sub-expressions were. Then, instead of optimization, you could just spruce up your code.


That’s a good idea. I’ve opened an issue to remind myself: https://github.com/rdeits/CommonSubexpressions.jl/issues/1