MLton MLTONWIKIVERSION

CommonSubexp

Home Index

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)`.

Last edited on 2007-08-23 03:59:21 by MatthewFluet.