[LLVMdev] LLVM loop vectorizer

[Michael Zolotukhin]

Hi Alex,

Example from the link you provided looks like this:
for (i=0; i<M; i++ ){ 
    z[i]=0;
    for (ckey=row_ptr[i]; ckey<row_ptr[i+1]; ckey++) {
      z[i] += data[ckey]*x[colind[ckey]];
    }              
  }
Is it the loop you are trying to vectorize? I don’t see any ‘if’ inside the innermost loop.

But anyway, here vectorizer might have following troubles:
1) iteration count of the innermost loop is unknown.
2) Gather accesses ( a[b[i]] ). With AVX512 set of instructions it’s possible to generate efficient code for such case, but a) I think it’s not supported yet, b) if this ISA isn’t available, then vectorized code would need to ‘manually’ gather scalar values to vector, which might be slow (and thus, vectorizer might decide to leave the code scalar).

And here is a list of papers vectorizer is based on:
// The reduction-variable vectorization is based on the paper:
//  D. Nuzman and R. Henderson. Multi-platform Auto-vectorization.
//
// Variable uniformity checks are inspired by:
//  Karrenberg, R. and Hack, S. Whole Function Vectorization.
//
// The interleaved access vectorization is based on the paper:
//  Dorit Nuzman, Ira Rosen and Ayal Zaks.  Auto-Vectorization of Interleaved
//  Data for SIMD
//
// Other ideas/concepts are from:
//  A. Zaks and D. Nuzman. Autovectorization in GCC-two years later.
//
//  S. Maleki, Y. Gao, M. Garzaran, T. Wong and D. Padua.  An Evaluation of
//  Vectorizing Compilers.
And probably, some of the parts are written from scratch with no reference to a paper.

The presentations you found are a good starting point, but while they’re still good from getting basics of the vectorizer, they are a bit outdated now in a sense that a lot of new features has been added since then (and bugs fixed:) ). Also, I’d recommend trying a newer LLVM version - I don’t think it’ll handle the example above, but it would be much more convenient to investigate why the loop isn’t vectorized and fix vectorizer if we figure out how.

Best regards,
Michael

> On Jul 8, 2015, at 10:01 AM, RCU <alex.e.susu at gmail.com> wrote:
> 
>  Hello.
>    I am trying to vectorize a CSR SpMV (sparse matrix vector multiplication) procedure but the LLVM loop vectorizer is not able to handle such code.
>    I am using cland and llvm version 3.4 (on Ubuntu 12.10). I use the -fvectorize option with clang and -loop-vectorize with opt-3.4 .
>    The CSR SpMV function is inspired from http://stackoverflow.com/questions/13636464/slow-sparse-matrix-vector-product-csr-using-open-mp (I can provide the exact code samples used).
> 
>    Basically the problem is the loop vectorizer does NOT work with if inside loop (be it 2 nested loops or a modification of SpMV I did with just 1 loop - I can provide the exact code) changing the value of the accumulator z. I can sort of understand why LLVM isn't able to vectorize the code.
>    However, at http://llvm.org/docs/Vectorizers.html#if-conversion it is written:
>            <<The Loop Vectorizer is able to "flatten" the IF statement in the code and generate a single stream of instructions.
>              The Loop Vectorizer supports any control flow in the innermost loop.
>              The innermost loop may contain complex nesting of IFs, ELSEs and even GOTOs.>>
>     Could you please tell me what are these lines exactly trying to say.
> 
>    Could you please tell me what algorithm is the LLVM loop vectorizer using (maybe the algorithm is described in a paper) - I currently found only 2 presentations on this topic: http://llvm.org/devmtg/2013-11/slides/Rotem-Vectorization.pdf and https://archive.fosdem.org/2014/schedule/event/llvmautovec/attachments/audio/321/export/events/attachments/llvmautovec/audio/321/AutoVectorizationLLVM.pdf .
> 
>  Thank you very much,
>      Alex
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150708/2188ff84/attachment.html>