[MLton-devel] datatype variant tag optimization

[Matthew Fluet]

> Both gcc and the native backend sometimes use the fact that the
> variant tags are consecutive integers in order to build a jump table.
> But, there is no reason why we couldn't arrange the type indices to be
> consecutive.  It would still save us the extra memory reference.

You'll need to be careful with assigning type indices.  You don't want to
end up with a type index for each variant in the program.  For example,
every 'a list where 'a ends up being represented by pointer should be able
to share the same type index.  (It's only variants of the same datatype
with the same pointer mask that need different type indices.)

Here's a pathological example:
datatype x = X1 of int array
           | X2 of int array
           | ...
           | X100 of int array
           | XX of int ref * int ref
datatype y = Y1 of int array
           | Y2 of int array
           | ...
           | Y100 of int array
           | YY of int ref * int ref * int ref
datatype z = Z1 of int array
           | Z2 of int array
           | ...
           | Z100 of int array
           | ZZ of int ref * int ref * int ref * int ref

We'll need to induce at least 100 different type indices for each
{X,Y,Z}N of int array, because they all have the same pointer mask.
Furthermore, we'd really like to share those 100 type indices between x,
y, and z.  But, we'll not be able to make XX, YY, and ZZ all consecutive
to the 100 consecutive type indices, because each of them needs a unique
type index (they have different pointer masks).

Actually, that's probably not so bad for the codegens; the native
codegen's jump-table heuristic just requires that the branches be "dense
enough" and the above would so long at the "extra" index was just a couple
of indices away from the end of the consecutive ones.

Anyways, trying to maximize consecutiveness and sharing sounds like a
packing problem that might be NP-{hard/complete}.  But, with 2^19 indices
to go around, any decent heuristic should be fine.




-------------------------------------------------------
This sf.net email is sponsored by: To learn the basics of securing 
your web site with SSL, click here to get a FREE TRIAL of a Thawte 
Server Certificate: http://www.gothawte.com/rd524.html
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel