Globalization of arrays and refs of "small" types in ConstantPropagation

[MatthewFluet]

Space-safety prohibits ConstantPropagation from globalizing all arrays and refs that are allocated at most once by a program. In particular, because globals are live for the duration of the program, globalizing an int list ref (for example) would not be safe-for-space: an arbitrarily large list may be written to the reference and never garbage collected (whereas, when the int list ref is not globalized, it will be garbage collected when it is no longer live). On the other hand, globalizing an int ref is safe-for-space.

However, MLton currently uses a very conservative estimation for space safety. Only "small" types may be globalized, where smallness is defined as:

     fun isSmall t =
         case dest t of
            Array _ => false
          | Datatype _ => false
          | Ref t => isSmall t
          | Tuple ts => Vector.forall (ts, isSmall)
          | Vector _ => false
          | _ => true

Note that no Datatype is small; this is conservative (since a recursive datatype could represent unbounded data), but prevents globalizing bool ref. Also, no Array is small; this is correct (because an int array ref should not be globalized), but the globalization of a val a: t array = Array_alloc[t] (l) is currently conditioned on the smallness of t array, not the smallness of t. It would be correct to globalize an array if t were small; note that to globalize val a: t array = Array_alloc[t] (l), l (the length) must be globalized and must, therefore, be a constant and the array is of constant size. (This is Stephen Weeks's relaxed notion of safe-for-space, where the constant factor blowup can be chosen per program.) In practice, it may be better to limit globalization of arrays to ones with "small" length in addition to small element type.

RefFlatten uses a more precise notion of small/large types (although RefFlatten was meant to be safe-for-space, the initial definition of small/large types was incorrect; see b1a0a80).

[MatthewFluet]

There are (at least) two orthogonal improvements that could be investigated:

• Allow globalization of "small constant" arrays:

  • Allow globalization of arrays with "small type" contents; this simply requires changing the Type.isSmall resultType to Type.isSmall (Vector.first targs) in fun bear z = ... in fun primApp.
  • Restrict globalization of arrays with "small type" contents to ones with "small" length; this requires changing the fn _ => length to check if length is a "small constant size".

• Relax notion of "small type":

  • Pre-process the datatypes and allow any datatype with all nullary constructors to be considered small. (Simple iteration of datatypes.) This would allow bool (and other "enumeration" datatypes) to be considered small.
  • Pre-process the datatypes as with RefFlatten, allowing any datatype with all constructors with small types to be considered small. (Fixed-point iteration of datatypes.) This would allow some value carrying datatypes to be considered small, for example, some closure datatypes where the environment constructors only capture small data.
  • Post-process the datatypes after the main constant propagation analysis, taking into account components of constructors that are known to be constant. For example, a datatype like datatype t = T of int array would not be considered small by either of the previous approaches, but if it was determined that the int array were itself constant (and globalized) then the datatype would be transformed to datatype t = T of unit, which would be considered small.