[MLton] Vector.fromList[] performance

[Matthew Fluet]

>> 'Vector.fromList' is implemented in SML, so the compiler doesn't
>> treat it specially.  Trying to identify exactly this code would be
>> pretty tough.
>
> For anyone who wants to see what MLton sees, I've attached the SSA
> control-flow graph for the original "vectors" function, which uses
> Vector.fromList.   The relevant blocks in the SSA do the following:
>
>  1. cons up list (L_178)
>  2. loop to compute the length of list (L_179, L_180)
>  3. allocate an array (L_184)
>  4. loop through the list, filling in the array (L_186, L_187)
>  5. convert the array to vector (L_188)
>
> So, it's pretty much out of the question to turn things into a direct
> vector construction by that point.

I really don't think that it is completely out of the question to recover 
a direct construction at this point.  The essential thing is to identify 
that the loops L_179,L_180 and L_186,L_187 are called on directly 
constructed lists, and then unroll the loops the length of the list. 
After that, constant folding in the shrinker should turn it into a single 
basic block that allocates the array, directly fills the elements, and 
then casts to a vector.

> On the other hand, adding a
> Vector_fromList primitive, implementing Vector.fromList in the basis
> via the primitive, and treating the primitive specially in the
> optimizer shouldn't be too hard.  With a primitive, the optimizer
> would simply have to notice that the argument to fromList is a
> directly constructed list.

Which optimizer?  Once you determine that something is a directly 
constructed list in SSA, I don't see that it is much harder to determine 
whether the list is used in Vector_fromList or if the list is used in a 
loop.