MLton

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

Description

This pass computes a "cardinality" of each datatype, which is an abstraction of the number of values of the datatype.

  • Zero means the datatype has no values (except for bottom).

  • One means the datatype has one value (except for bottom).

  • Many means the datatype has many values.

This pass removes all datatypes whose cardinality is Zero or One and removes:

  • components of tuples

  • function args

  • constructor args

which are such datatypes.

This pass marks constructors as one of:

  • Useless: it never appears in a ConApp.

  • Transparent: it is the only variant in its datatype and its argument type does not contain any uses of array or vector.

  • Useful: otherwise

This pass also removes Useless and Transparent constructors.

Implementation

Details and Notes

This pass must happen before polymorphic equality is implemented because

  • it will make polymorphic equality faster because some types are simpler

  • it removes uses of polymorphic equality that must return true

We must keep track of Transparent constructors whose argument type uses array because of datatypes like the following:

datatype t = T of t array

Such a datatype has Cardinality.Many, but we cannot eliminate the datatype and replace the lhs by the rhs, i.e. we must keep the circularity around.

Must do similar things for vectors.

Also, to eliminate as many Transparent constructors as possible, for something like the following,

datatype t = T of u array
     and u = U of t vector

we (arbitrarily) expand one of the datatypes first. The result will be something like

datatype u = U of u array vector

where all uses of t are replaced by u array.