[MLton] more edits to flatten.fun

Stephen Weeks MLton@mlton.org
Thu, 22 Jan 2004 15:28:33 -0800

> Currently flatten.fun does not do anything with nested tuples,
> correct?


> Will any of these changes need to be propogated to local flatten?

Not necessarily.  There is no necessary connection between the two.
Most of the SSA optimization passes are standalone, taking valid SSA
and producing valid SSA.  There may be a few assumptions about
simplifier pass ordering in terms of eliminating certain primitives
before others, but that's about the only constraint I can think of.

> There is one problem that still needs to be addressed in flatten and that
> is the case of tupples within other tupples.
> Something like: ((a,b),(d,e,(f,g)),h,i,j)
> I believe the best solution to this, is in the flatten all case, is to
> simply have a function that will recurse through the Var.t vector of a
> tuple as well as the type and if we see another tupple type mark that as
> flat. Ofcourse this will require a change in doitArgs and potentially
> doitCaseCon.

If you want to hardwire the notion of "flatten everything deeply",
then you might be able to succeed with an approach like this.  Even
simpler (at least for fast experimentation), you could simply run the
flatten pass over and over until it has nothing left to flatten.

Also, I'm curious how your experiments with flattening all tuples (but
not deeply) went.  It seems like that should be working before
proceeding onto more complex stuff.

If you want to do deep-flattening experiments, and possibly feed this
back into our development, it might be better to take a step back and
think about both the analysis and the transformation.  As it currently
stands, the analysis cannot express deep flattening because it uses a
two point lattice, which is only capable of encoding a decision about
flattening the outermost tuple.

In order to express deep flattening, you need a lattice that reflects
the complete structure of tuple types and you need to change the
transformation to do more than single round of detupling.

To get a feel for such a lattice, have a look at
constant-propagation.fun and useless.fun, both of which analyze tuples
to their full depth.  I think it would be very nice to have an analog
of these two passes for flattening, where the Value.t type includes a
bool associated with each abstract tuple indicating whether or not it
should be flattened.  The analysis would annotate each variable in the
program with such a value.  Then, one could write a corresponding
transformation that works with *any* annotation, inserting the
appropriate tupling/detupling coercions to convert between tuples with
different annotations.  The transformation would be a generalization
of the current flatten.fun, so that if the annotation corresponded to
it at the outermost tuple in types and always said to keep tuples on
the inner levels, then we would get exactly the transformation we have
now.  It would also be easy to experiment with other analyses,
e.g. one that said "always flatten deeply", or even one that said
"always flatten the outermost two levels".

I realize this isn't super precise, but hopefully this gives you some