[LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

[Johannes Doerfert]

Hello Arch,

I very much like the idea of such an annotation, especially since I was
looking for the same thing in the recent past. My use case is different
from yours, thus it might provide a second reason to support this.

I recently submitted a patch to the list [1] which would allow Polly to
extract the dependency distance for each analyzable loop. While the
distance is often not constant but parametric we would also need to
version the vectorized loop based on the actual runtime values. However,
the versioning doesn't need to be done by the vectorizer but could also
be part of Polly (depending on whether or not the vectorizer will have
that capability). I admit that we would need a good heuristic in order
to turn this feature on as a default optimization, but I will work on
that in the near future too.

Best regards,
  Johannes


[1] http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140804/230137.html

On 08/12, Robison, Arch wrote:
> Julia and OpenMP 4.0 have features where the user can bless a loop as 
> having no memory dependences that prevent vectorization, thus enabling
> vectorization of loops not amenable to compile-time or run-time 
> dependence analysis.  LLVM currently has no metadata to express such,
> as explained further below.
> 
> I'd like to propose new metadata that enables front-ends to tell the 
> vectorizer that "memory dependences are not a problem for vectorization
> widths up to n".  I'd appreciate any comments before I spend time 
> prototyping it.
> 
> BACKGROUND
> ----------
> 
> OpenMP 4.0 allows the programmer to write something such as:
> 
>     void foo( float* a, int n, int k ) {
>     #pragma omp simd safelen(8)
>         for( int i=0; i<n; ++i ) {
>             a[i] = 2*a[i+k];
>     }
> 
> The pragma tells the compiler that the loop is safe to vectorize with 
> a width of 8 or less.  (I.e. it's up to the programmer to ensure that 
> either k<=-8 or k>=0.)  If safelen is missing, the safe width is 
> unbounded.  The example is a trivial one for exposition.  Real examples 
> may involve complex subscripting patters or scatter/gather patterns 
> well beyond what is practical to check with a run-time check.
> 
> Julia has an @simd annotation with a similar purpose, but without a 
> safelen parameter.  It's documented as not allowing any dependences, 
> but that's because of the LLVM shortcoming addressed by this proposal. 
> 
> WHY CURRENT METADATA DOES NOT SUFFICE
> -------------------------------------
> 
> There are currently two pieces of metadata that come close, but miss the 
> desired semantics.
> 
> * llvm.loop.vectorize.width - hints at what vectorization width to use
>   *if* the loop is safe to vectorize.  It does not specify that the 
>   loop is safe to vectorize.
> 
> * llvm.mem.parallel_loop_access - indicates that accesses do not
>   have a loop-carried dependence between them.  That's too broad a 
>   brush, as it precludes loops that do have dependences (e.g. "forward 
>   lexical dependences") that are nonetheless vectorizable.
> 
> PROPOSAL
> --------
> 
> Add new metadata "llvm.loop.vectorize.safelen" that has a parameter n 
> of type i32.  The metadata tells the vectorizer that the loop is safe 
> to vectorize with any vectorization width less or equal to n.  The loop 
> vectorizer is free to choose any vectorization width within that 
> constraint.
> 
> - Arch D. Robison
>   Intel Corporation
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-- 

Johannes Doerfert
Researcher / PhD Student

Compiler Design Lab (Prof. Hack)
Saarland University, Computer Science
Building E1.3, Room 4.26

Tel. +49 (0)681 302-57521 : doerfert at cs.uni-saarland.de
Fax. +49 (0)681 302-3065  : http://www.cdl.uni-saarland.de/people/doerfert
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 213 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140812/6d2a8548/attachment.sig>