[LLVMdev] GSoC 2009: Auto-vectorization

[Stefanus Du Toit]

On 1-Apr-09, at 1:25 AM, Nick Lewycky wrote:
> My concern being that writing both loop dependence analysis and loop
> autovectorization would be difficult in the time span alloted for  
> GSoC,
> and you may want to consider just doing SLP.

Once you have decent loop dependence analysis, performing  
autovectorization becomes fairly mechanical *if* you start off by  
restricting the kinds of instructions you allow to be vectorized. For  
example, if you start off with loops containing:

  - only instructions whose operands have the same size in bytes, and  
thus will work well with the same "vectorization width" or "lane count"
  - loop counts that are well-known and divisible by the lane count
  - no other control flow
  - only well-aligned loads and stores
  - only instructions that have good vector support in llvm today

Then, given decent dependence analysis, you should be able to write a  
vectorizer that vectorizes loops meeting these conditions pretty  
trivially. Once you've done that, you can start relaxing these  
assumptions, e.g. by adding a scalar loop to "finish up" loop counts  
that don't match the vectorization width to get rid of the loop count  
constraint, performing dynamic alignment analysis, etc.

There may be other issues in LLVM that make this more complicated of  
which I'm not aware, but with a reasonable initial set of constraints,  
the "vectorization" part of a loop autovectorizer should be feasible  
to do in a short timeframe.

--
Stefanus Du Toit <stefanus.dutoit at rapidmind.com>
   RapidMind Inc.
   phone: +1 519 885 5455 x116 -- fax: +1 519 885 1463