CommonSubexp is an optimization pass for the SSA IntermediateLanguage, invoked from SSASimplify.

Description

It eliminates instances of common subexpressions.

Implementation

Details and Notes

In addition to getting the usual sorts of things like

  • (w + 0wx1) + (w + 0wx1)

    rewritten to

    let val w' = w + 0wx1 in w' + w' end

it also gets things like

  • val a = Array_uninit n
val b = Array_length a

    rewritten to

    val a = Array_uninit n
val b = n

Arith transfers are handled specially. The result of an Arith transfer can be used in common Arith transfers that it dominates:

  • val l = (n + m) + (n + m)

val k = (l + n) + ((l + m) handle Overflow => ((l + m)
                                               handle Overflow => l + n))

    is rewritten so that (n + m) is computed exactly once, as are (l + n) and (l + m).