Re: Adding SIMD loop vectorizing capabilities to MLton

> My name is Anand.

Hi, Anand.

> I am a masters student at Carnegie Mellon doing
> research on optimizing compilers. Presently, I would like to add to MLton
> the ability to vectorize loops and target the SSE3/SSE4 instruction sets.
> As far as I can tell, this has not already been done.

I don't believe that anyone has attempted loop vectorization with
SSE3/4 instructions.

> A few obvious bounds that I have already established:
> - The pass had better be somewhere below SSA/SSASimplify. By the point,
> IntroduceLoops has turned tail recursive functions into loops (increasing
> the applicability of loop vectorization). Additionally, monomorphization
> has happened and gives us a better chance of finding instances of
> functions such as map/app that can be vectorized.
> - It is also probably a good idea to work below SSA2/SSA2Simplify. If I
> understand it correctly, DeepFlatten gives arrays and vectors of integers
> a dense representation without pointer indirection. That probably also
> increases the number of opportunities for vectorization.

I certainly agree that working in SSA or SSA2 would be appropriate.
As you note, by the SSA IL, the program has been monomorphized.
Towards the end of the SSA optimizations, enough inlining and
simplifications will have happened to expose loops.

I'm not sure that you will gain much by working at SSA2.  The
DeepFlatten pass will make (some) '(int * int) array's into arrays of
pairs of integers, rather than arrays of pointers to pairs of
integers; but, it seems unlikely that the same operation would be
applied to each integer in the pair at each step, so it isn't clear
that you would find opportunities to vectorize operations on such
arrays.

Nonetheless, there wouldn't be any major disadvantage to working in SSA2.

> - I am still fuzzy on what RSSA does, and what modifications will have to
> be made here. Any enlightenment would be appreciated.
>
> Things I could use more information on:
> - What is the purpose of RSSA?

RSSA makes representation decisions explicit.  For instance, it
chooses the order of fields within a tuple.  It decides how to
distinguish variants of a datatype.

> - I am used to an LLVM-style SSA representation, with phi-nodes
> indicating where multiple definitions meet in a control-dependent manner.
> MLton appears to have a different but equivalent representation where
> blocks have arguments. When control is transferred into a block,
> control-flow dependent values are passed as arguments to the block. Is
> this correct?

Yes.

> Do the arguments of a block include all variables that are
> live into the block? Or do the arguments only include those variables
> that do not originate from dominating definitions?

The latter.  Essentially, the set of variables that get phi-nodes at
the beginning of a block become arguments to the block.

> - There is documentation on something called zone splitting that happens
> in SSA2Simplify. It appears to include the identification of
> zone-headers, blocks which dominate a connected component. Then, a
> zone-header which has a back-edge should also be the header of a natural
> loop. Could you tell me more about how information about zone-headers is
> stored and retrieved? I could use this information to easily analyze
> induction variables and loop-carried dependencies.

The Zone pass was introduced to cut down on the number of variables in
large SSA functions.  I think the connected components that it would
find are likely to be too large for your purposes.

You could use the 'DirectedGraph.loopForestSteensgaard' function to
identify loop headers (in reducible and irreducible CFGs).

> - In each of SSA, SSA2 and RSSA, when and how can arrays alias? Is there
> an alias analysis pass to determine this?

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.

> Work that I need to do:
> - Expand the "Machine" representation to include a concept of vector
> registers (such as those used in SIMD instruction sets). Also,
> investigate alignment restrictions.

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.

> - 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.

------------------------------------------------------------------------------
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