[LLVMdev] Loop vectorizer

[Nadav Rotem]

Hi Preston! 

> 
> I'd start by making a plan (a design!) with goals and stuff.
> Publish it so we can see what you mean by "vectorization".

I will send a separate email later, but here is a quick overview.  I see the vectorizer having four main components:

1. Preparation passes: If-conversion, loop transformations, etc. 
 
2. Cost model - This unit decides on the best vectorization factor (could be 1). 

3. Legality check - This unit checks if it is *legal* (from a correctness point of view) to vectorize the program. This is target independent. Also, this unit needs to describe which transformation are needed to make this loop vectorizeable. For example: if-conversion is required if the control flow is not uniform for all iterations of the loop.  

4. Vectorization - This is where the actual widening of the instructions happen. Every time we improve #3 by detecting more vectorizeable loops, we need to add the mechanism for actually generating code for it. For example, we can detect reduction variables, but we also need to be able to generate code for them. 

> I.e., do you mean for real vector machines, a la Cray, or for
> the packed media instructions that are currently so popular?

I am mostly interested in generating code for the popular SIMD cpus (X86, ARM, PPC, etc).

> What's your idea for finding vectorizable loops?

I started with a very very basic check because I needed to start somewhere.  We will need to design a mode advanced check. 

> Do you have a plan for xforms to increase the amount of vectorization?

Yes. We will need to implement a predication phase and to design the interaction with other loop transformations.  Also, this will have to work well with the cost model. We also need to think of a good way to detect early on if the transformations are likely to be effective, because we currently don't have a good way of undoing compiler transformations. 

I think that a simple if-converter will be a good place to start. What do you think ?  

> I've written a dependence analyzer that ought to be suitable
> (if it isn't, we should fix it).

I know :)   Yes, this is really good. Any serious loop transformation and multi-dimentional array vectorization will need this. I am glad that you are working on this and I do want to use it.

In the near future, I plan to work on the code generation cost-model aspects.  

The vectorization legality check that I wrote is very simple and very conservative. It will be great if you could contribute in that area. 

Thanks,
Nadav

> 
> Thanks,
> Preston