[LLVMdev] GSoC 2009: Auto-vectorization

[Andreas Bolka]

Hi Nick,

Nick Lewycky wrote:
> There's no loop dependence analysis in LLVM yet. How are you planning
> to implement it? Can you point to a paper, or write up a plain English
> description?

Currently I'm planning to implement dependence analyis as described in
e.g. Allen, R. and Kennedy, K. (1987). Automatic translation of FORTRAN
programs to vector form. ACM Trans. Program. Lang. Syst. 9, 4.

As mentioned in other replies, I'd only want to support non-nested loops
and array index expressions that are linear functions of the induction
variable, so that the GCD test can be used to determine statement
interdependence.

For the simple loop I showed in my original example, which uses three
distinct arrays, dependence checking may even be sufficient via LLVM's
MemoryDependence interface. But I'll have to investigate this in more
detail.

> In any event, the paper I was thinking of [..] is:
> http://www.cag.lcs.mit.edu/slp/SLP-PLDI-2000.pdf
>
> 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.

Thanks for the suggestion! I considered SLP/"vectorization by unrolling"
as well, but my personal interests currently lean more towards
"classical" vectorization, given the usefulness of loop dependence
analysis for other transformations. The general interest expressed on
this list seems to confirm this.

-- 
Andreas