doc/guide/src/CommonSubexp.adoc

   1 CommonSubexp
   2 ============
   3
   4 <:CommonSubexp:> is an optimization pass for the <:SSA:>
   5 <:IntermediateLanguage:>, invoked from <:SSASimplify:>.
   6
   7 == Description ==
   8
   9 It eliminates instances of common subexpressions.
  10
  11 == Implementation ==
  12
  13 * <!ViewGitFile(mlton,master,mlton/ssa/common-subexp.fun)>
  14
  15 == Details and Notes ==
  16
  17 In addition to getting the usual sorts of things like
  18
  19 * {empty}
  20 +
  21 ----
  22 (w + 0wx1) + (w + 0wx1)
  23 ----
  24 +
  25 rewritten to
  26 +
  27 ----
  28 let val w' = w + 0wx1 in w' + w' end
  29 ----
  30
  31 it also gets things like
  32
  33 * {empty}
  34 +
  35 ----
  36 val a = Array_uninit n
  37 val b = Array_length a
  38 ----
  39 +
  40 rewritten to
  41 +
  42 ----
  43 val a = Array_uninit n
  44 val b = n
  45 ----
  46
  47 `Arith` transfers are handled specially.  The _result_ of an `Arith`
  48 transfer can be used in _common_ `Arith` transfers that it dominates:
  49
  50 * {empty}
  51 +
  52 ----
  53 val l = (n + m) + (n + m)
  54
  55 val k = (l + n) + ((l + m) handle Overflow => ((l + m)
  56                                                handle Overflow => l + n))
  57 ----
  58 +
  59 is rewritten so that `(n + m)` is computed exactly once, as are
  60 `(l + n)` and `(l + m)`.