Adding SIMD loop vectorizing capabilities to MLton

Hi,

My name is 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. Before getting in
over my head, I would like your advise so that I can do this in a manner
consistent with the existing code base. I would also appreciate a quick
sanity check of my current assumptions.

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 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?
- 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? 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?
- 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.
- In each of SSA, SSA2 and RSSA, when and how can arrays alias? Is there
an alias analysis pass to determine this?

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

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