[LLVMdev] GSoC 2009: Auto-vectorization

[Chris Lattner]

On Apr 1, 2009, at 2:54 PM, Andreas Bolka wrote:
>> 1. We need an abstract dependence analysis interface (like we have  
>> for
>> AA) and one implementation (probably handling trivial loops like the
>> one above to start with).  Many people have talked about this, but no
>> code has gone in yet.
>
> My original plan was to implement a loop dependence analysis only for
> non-nested loops using the "GCD" method of determining interdependent
> statements. This limits the array subscript expressions to simple  
> linear
> equations of the form x1*i + x0 where i is the induction variable of  
> the
> loop.
>
> I haven't thought yet about generalising this to ease future
> implementation of more complex loop dependency analyses.

Sounds fine, I'm ok with starting simple, so long as the client talks  
through an abstract interface of some sort, and the impl is in a  
different pass.

>> 2. We need some interface that can be implemented by a target machine
>> to describe what the vector capabilities of the machine are.
>
> Initially the vectorization pass would basically only need the SIMD
> register width; later, the supported "packing formats" may come in  
> handy
> (i.e. the information that 128-bit registers that be used as e.g.
> 16 x i8, 8 x i16, and 4 x i32).

Sounds good.  Perhaps a list of supported types would be enough.

>> Once the basics are in place, it can be feature-crept to support new
>> idioms (reductions, alignment analysis, etc).  The first cut doesn't
>> need to provide an immediate speedup, but should have many testcases
>> that demonstrates the loop forms it can handle.
>
> That's exactly my understanding of it. I want to limit this to the  
> most
> basic transformation possible; i.e.:
>
> - non-nested loops, having
> - a statically known constant trip count, which is
> - divisible by the vectorization factor;
> - a single basic block as loop body, with
> - a single arithmetic instruction, using
> - only same-sized vector operands, and
> - ignoring alignment issues.

Sounds great!

>> Depending on how ambitious you are, you could also do a GSoC project
>> just around a) building dependence analysis interface + some
>> *non*-trivial implementations, and b) build some dep analysis clients
>> around it (e.g. loop interchange, etc). This may be a less risky and
>> higher impact project in the short term, if you are interested in it.
>
> I understand the importance and necessity of a general loop dependence
> interface, but I'm not too familiar with the more complex
> approaches (which generally require integer linear programming, if I'm
> not mistaken). So I can't really asses if there's a realistic chance  
> to
> build a generally usable non-trivial implementation in the time
> available.

Ok!

-Chris