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 aConApp
. -
Transparent
: it is the only variant in its datatype and its argument type does not contain any uses ofarray
orvector
. -
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 array
where all uses of t
are replaced by u array
.