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

Description

It eliminates instances of common subexpressions.

Implementation

common-subexp.sig common-subexp.fun

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_array n
   val b = Array_length a
  

  rewritten to

   val a = Array_array 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).