llvm dev - Aug 2014 - [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

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

On 12 August 2014 18:24, Robison, Arch <arch.robison at intel.com>
wrote:
> 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.
Hi Arch,

That was the intention, yes, and I believe that was the exact
semantics we thought about. This metadata should be applied and kept
in the same way as other loop metadata.

Arnold or Nadav should know better, though, since they are up-to-date
with the current developments.

cheers,
--renato

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>

On 12 August 2014 18:49, Johannes Doerfert <doerfert at
cs.uni-saarland.de> wrote:
> 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.
Since this is a metadata node, we can actually add it with whatever we
want, from an integer constant to whatever we want. But of course,
complexity is an issue. I believe a constant is a good starting point.

Remember that this annotation is saying that "the loop *as it is* is
safe in a N vector", but things can change between the annotation
(generally source code pragmas, but could be a Polly thing) and actual
vectorization. This is a game that the user must be ready to play to
use these advanced features and Polly has to be extremely conservative
(since the user is *not* directly recommending safety boundaries), but
can also allow some extra room (similar to -ffast-math, we could do
-ffast-polly if needed),

> 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.
The original idea for vectorization annotations was to help multiple
passes to communicate.

Initially, it was used between two passes of the vectorizer (so it
wouldn't vectorize the same loop again) but later was used as a
vehicle to source code pragmas. Though, the idea of Polly sharing the
annotation space was in it from the beginning, and I think we'll come
up with a lot more metadata than just wide/safe. Arnold had some
slides about it.

cheers,
--renato

> On Aug 12, 2014, at 10:24 AM, Robison, Arch <arch.robison at
intel.com> 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.
> 
In general, I think this is a useful addition. We just have to get the semantics
nailed down.

Is this annotation - if present -  meant as a restriction to accesses marked
with “llvm.mem.parallel_loop_access”?  - That there is no loop carried
dependence at a |distance| < k but there might be one at >= k between
marked accesses.

Thanks,
Arnold

On 12 August 2014 22:44, Arnold Schwaighofer <aschwaighofer at apple.com>
wrote:
> Is this annotation - if present -  meant as a restriction to accesses
marked with “llvm.mem.parallel_loop_access”?  - That there is no loop carried
dependence at a |distance| < k but there might be one at >= k between
marked accesses.
Hum, indeed, Polly and the vectorizer should be careful when
adding/changing annotations on loops that the user has already
annotated, or we run the risk of trying to be smarter than the user
and getting it wrong.

If I remember correctly, the safelen semantics was just a hint to the
validation that, despite its lack of knowledge, the loop was valid at
length N, so that we could skip directly to the cost model. But it
wasn't intended to force any particular width.

cheers,
--renato

>
> 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.
>
How does this relate to the recent additions by Hal on invariants using 
llvm.assume? [0]

Can we translate llvm.mem.vectorize.safelen into an invariant on k 
similarly as to what you're proposing that the programmer should ensure?

Cheers,
  Roel

[0] http://comments.gmane.org/gmane.comp.compilers.llvm.devel/74941

----- Original Message -----
> From: "Roel Jordans" <r.jordans at tue.nl>
> To: llvmdev at cs.uiuc.edu
> Sent: Wednesday, August 13, 2014 5:57:15 AM
> Subject: Re: [LLVMdev] Proposal for
""llvm.mem.vectorize.safelen"
> 
> >
> > 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.
> >
> 
> How does this relate to the recent additions by Hal on invariants
> using
> llvm.assume? [0]
I don't think this related because the assumptions don't provide any
direct way of asserting things about memory aliasing. That might be an
interesting thing to do, but we've not really thought about it yet.

Regarding the proposal, I'm in favor. I don't like using the name
'savelen' however. I can forgive OpenMP for choosing such a short name
because people need to type it, but I'd prefer that the metadata have a
more-descriptive name. minimum_dependency_distance is perhaps better.

 -Hal
> 
> Can we translate llvm.mem.vectorize.safelen into an invariant on k
> similarly as to what you're proposing that the programmer should
> ensure?
> 
> Cheers,
>   Roel
> 
> [0] http://comments.gmane.org/gmane.comp.compilers.llvm.devel/74941
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory