doc/guide/src/SimplifyTypes.adoc

   1 SimplifyTypes
   2 =============
   3
   4 <:SimplifyTypes:> is an optimization pass for the <:SSA:>
   5 <:IntermediateLanguage:>, invoked from <:SSASimplify:>.
   6
   7 == Description ==
   8
   9 This pass computes a "cardinality" of each datatype, which is an
  10 abstraction of the number of values of the datatype.
  11
  12 * `Zero` means the datatype has no values (except for bottom).
  13 * `One` means the datatype has one value (except for bottom).
  14 * `Many` means the datatype has many values.
  15
  16 This pass removes all datatypes whose cardinality is `Zero` or `One`
  17 and removes:
  18
  19 * components of tuples
  20 * function args
  21 * constructor args
  22
  23 which are such datatypes.
  24
  25 This pass marks constructors as one of:
  26
  27 * `Useless`: it never appears in a `ConApp`.
  28 * `Transparent`: it is the only variant in its datatype and its argument type does not contain any uses of `array` or `vector`.
  29 * `Useful`: otherwise
  30
  31 This pass also removes `Useless` and `Transparent` constructors.
  32
  33 == Implementation ==
  34
  35 * <!ViewGitFile(mlton,master,mlton/ssa/simplify-types.fun)>
  36
  37 == Details and Notes ==
  38
  39 This pass must happen before polymorphic equality is implemented because
  40
  41 * it will make polymorphic equality faster because some types are simpler
  42 * it removes uses of polymorphic equality that must return true
  43
  44 We must keep track of `Transparent` constructors whose argument type
  45 uses `array` because of datatypes like the following:
  46 [source,sml]
  47 ----
  48 datatype t = T of t array
  49 ----
  50
  51 Such a datatype has `Cardinality.Many`, but we cannot eliminate the
  52 datatype and replace the lhs by the rhs, i.e. we must keep the
  53 circularity around.
  54
  55 Must do similar things for `vectors`.
  56
  57 Also, to eliminate as many `Transparent` constructors as possible, for
  58 something like the following,
  59 [source,sml]
  60 ----
  61 datatype t = T of u array
  62      and u = U of t vector
  63 ----
  64 we (arbitrarily) expand one of the datatypes first.  The result will
  65 be something like
  66 [source,sml]
  67 ----
  68 datatype u = U of u array array
  69 ----
  70 where all uses of `t` are replaced by `u array`.