Fri Sep 18 08:45:58 CEST 2009

Sparse Conditional Constant Propagation

These 3 are very related:

- constant folding  (1 + 2 -> 3)
- constant propagation (A = 3; B = 4; A + B -> 3 + 4 -> 7)
- function inlining (f x y = x + y;   f a b -> a + b)

Abstract interpretation can do constant prop+fold and function inline
all at the same time, as long as all operations / functions have a
staged behaviour.  In a functional (SSA) setting, this isn't such a

Mutation however complicates matter.  The wikipedia page about
constant folding[1] talks about reaching definition[2] analysis, which
in SSA is of course trivial.

So, sparse conditional constant propagation[3] uses abstract
evaluation of SSA form: ``The crux of the algorithm comes in how it
handles the interpretation of branch instructions.''  Basicly,
conditional branches depending on known data can be picked at compile

[1] http://en.wikipedia.org/wiki/Constant_folding
[2] http://en.wikipedia.org/wiki/Reaching_definition
[3] http://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation