Re: Adding SIMD loop vectorizing capabilities to MLton

Thanks for the detailed reply...

>
> Aliasing of arrays in SSA, SSA2, and RSSA is essentially as in SML;
> there is no static information that conveys aliasing information
> (other than arrays of different types must not alias).  There isn't an
> alias analysis per-se.  The ConstantPropagation pass uses a "Birth"
> abstraction to perform a basic analysis on which arrays could
> correspond to the same allocation; given the whole-program, one should
> be able to put together a fairly simple data-flow analysis that
> assigns to each variable of array-type the set of (static) array
> allocations from which it could have arisen; an empty intersection of
> such sets would indicate must-not alias.

To make a first cut, I'm only trying to transform sml vector types which
are pure. Later on, I'll try to include arrays as you describe.

>
> You'd also need to introduce primitives to operate on vector
> registers.  And carry such instructions through to the codegen.
>
> You'll also want to have a good idea of how you want to move back and
> forth from vector registers and operations to/from arrays.  One aspect
> to be aware of is that MLton's runtime doesn't support interior
> pointers --- pointers to the interior of an object; every pointer is a
> pointer to the beginning of the object.

Excellent, I thought so... that simplifies matters a lot. I have
introduced pseudo instructions of the form simdX_op(dest, dest_index,
src1, src1_index, src2, src2_index, vector_arity), so they operate
without middle-pointers. Also, for the first cut, codegen will generate
unaligned loads and stores to xmm* registers when implementing each of
these pseudo-ops. Performance may be sub-optimal, but I prefer to deal
with the interaction between alignment requirements and garbage
collection later in development. I may seek more advise on this later.

>
>> - Analyze loops to find (a) accesses to vectors/arrays (b) a hopefully
>> unique induction variable (c) no dependencies carried by the inner-most
>> loop, and (d) a constant step to the induction variable that densely
>> traverses the vectors/arrays. If all the conditions are meet, we would
>> have identified a loop that is vectorizable. It appears that the best
>> place to do this analysis is in SSA2Simplify, right after zone
>> splitting.
>
> That sounds like the high-points.  (a) corresponds to finding uses of
> the Array_sub/update and Vector_sub primitives.  It probably also
> makes sense to examine the body of the loop to be sure that it is only
> "simple" operations; non-tail calls of other functions are unlikely to
> be vectorizable.

Yes, I'm being very careful about side-effects. Something that caught me
by surprise was that SML integer arithmetic raises exceptions on integer
overflow. I'll work on transforming operations on Word vectors before
attempting to safely generalize to integers.

Thanks!
-Anand


------------------------------------------------------------------------------
For Developers, A Lot Can Happen In A Second.
Boundary is the first to Know...and Tell You.
Monitor Your Applications in Ultra-Fine Resolution. Try it FREE!
http://p.sf.net/sfu/Boundary-d2dvs2