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

> I recommend that you send patches for an implementation 
> (including the Loop::GetAnnotatedVectorSafelen function 
>  and associated updates to the vectorizer) for review. 
I expect to send the patches for review later this week.
> Make sure to remember LangRef updates!
Thanks for the reminder.
> Also, looking at the original proposal again, I see no reason 
> to restrict this to an i32: we might as well allow it to be an 
> i64 obviously we don't have billion-lane vectors, but the 
> metadata can also be useful for other kinds of analysis).
I doubt there is much advantage between knowing the minimum loop-carried
dependence difference is 1u<<31 or 1u<<63.  Unless there is a clear
need for the higher values less than infinity, It would seem simpler
for now to adopt the same conventions as llvm.loop.vectorize.width
so that some processing infrastructure can be shared easily.
> I don't like using the name 'safelen' 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.
I'm open to naming suggestions, though I'm wondering if sticking with 
what is now a term of art in OpenMP might be the least of all evils,
because the semantics turn out to be a little more subtle than
just a minimum dependence distance.  My current wording of the semantics 
for safelen of k are: 

  /// The loop can be assumed to have no loop-carried
  /// lexically backward dependencies with distance less than k.

- Arch D. Robison
  Intel Corporation

Now that I'm looking at editing LangRef, I have a question.  The current
llvm.loop.vectorize metadata are hints, and have this constraint:

   The``llvm.loop.vectorize`` and ``llvm.loop.interleave`` metadata are only
   optimization hints and the optimizer will only interleave and vectorize loops
   if it believes it is safe to do so.

But safelen is different.  It's an assertion about safety, so prefixing it
with
llvm.loop.vectorize seems inappropriate.  Does is sound reasonable to drop
the "vectorize" portion.  Maybe spell it something like this?

	llvm.loop.carried_dependence_distance.min

- Arch

> On Aug 20, 2014, at 8:08 AM, Robison, Arch <arch.robison at
intel.com> wrote:
> 
>> I recommend that you send patches for an implementation 
>> (including the Loop::GetAnnotatedVectorSafelen function 
>> and associated updates to the vectorizer) for review. 
> 
> I expect to send the patches for review later this week.
> 
>> Make sure to remember LangRef updates!
> 
> Thanks for the reminder.
> 
>> Also, looking at the original proposal again, I see no reason 
>> to restrict this to an i32: we might as well allow it to be an 
>> i64 obviously we don't have billion-lane vectors, but the 
>> metadata can also be useful for other kinds of analysis).
> 
> I doubt there is much advantage between knowing the minimum loop-carried
> dependence difference is 1u<<31 or 1u<<63.  Unless there is a
clear
> need for the higher values less than infinity, It would seem simpler
> for now to adopt the same conventions as llvm.loop.vectorize.width
> so that some processing infrastructure can be shared easily.
> 
>> I don't like using the name 'safelen' 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.
> 
> I'm open to naming suggestions, though I'm wondering if sticking
with
> what is now a term of art in OpenMP might be the least of all evils,
> because the semantics turn out to be a little more subtle than
> just a minimum dependence distance.  My current wording of the semantics 
> for safelen of k are: 
> 
>  /// The loop can be assumed to have no loop-carried
>  /// lexically backward dependencies with distance less than k.
This means you would allow lexically forward dependencies which complicates
things (this would need more infrastructure in clang). You need to carry over
“source order” from the front-end. Because the dependency is loop carried llvm
would be allowed to move loads and stores within the loop:

Lexical forward dependency:

#pragma vectorize safelen(4)
for (i = …) {
   a[i] = b[i] + z[i];
   c[i]  = a[i-1] + 1;
}

LLVM might tranform this loop to:

for (i = …) {
   c[i]  = a[i-1] + 1;
   a[i] = b[i] + z[i];
}

if we now vectorize this (without knowledge of the orignal source order) we get
the wrong answer:

for (i = …) {
   c[i]  = a[i-1:i+2] + 1;
   a[i:i+3] = b[i] + z[i];
}

Alternatively, the metadata loop.vectorize.safelen would have to prevent any
such reordering of accesses i.e. any pass that reorders memory accesses would
have to be aware of it which is fragile.
> 
> - 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

On 20 August 2014 16:17, Robison, Arch <arch.robison at intel.com>
wrote:
> But safelen is different.  It's an assertion about safety, so prefixing
it with
> llvm.loop.vectorize seems inappropriate.  Does is sound reasonable to drop
> the "vectorize" portion.  Maybe spell it something like this?
This was true to all *current* vectorizer pragmas, but certainly not
safelen. I think we can change that description instead of changing
the namespace.

cheers,
--renato

Thanks for alerting me to this issue.  This is going to take more
effort than I thought :-(.  Given that a major motivation behind
the OpenMP #pragma omp simd is to allow lexical forward dependences,
we should find a way to do this right.

I agree that we want to avoid making passes that reorder accesses fragile.
The extra work in Clang (or Julia :-) seems unavoidable, unless those
producers always emit LLVM instructions in lexical order.  If the latter
is the case, perhaps we could have a helper routine that, given the IR early
and in lexical order, finishes the annotation work?  

It seems that we need metadata on each memory access, distinct from 
llvm.mem.parallel_loop_access.  Say something like llvm.mem.vector_loop_access
that includes relative lexical position as a third operand?  Second operand
could point back to the metadata with the minimum loop-carried distance,
which in turn could point back to the loop id.  

- Arch

On 08/20, Arnold Schwaighofer wrote:
> 
> > On Aug 20, 2014, at 8:08 AM, Robison, Arch <arch.robison at
intel.com> wrote:
> > 
> >> I recommend that you send patches for an implementation 
> >> (including the Loop::GetAnnotatedVectorSafelen function 
> >> and associated updates to the vectorizer) for review. 
> > 
> > I expect to send the patches for review later this week.
> > 
> >> Make sure to remember LangRef updates!
> > 
> > Thanks for the reminder.
> > 
> >> Also, looking at the original proposal again, I see no reason 
> >> to restrict this to an i32: we might as well allow it to be an 
> >> i64 obviously we don't have billion-lane vectors, but the 
> >> metadata can also be useful for other kinds of analysis).
> > 
> > I doubt there is much advantage between knowing the minimum
loop-carried
> > dependence difference is 1u<<31 or 1u<<63.  Unless there
is a clear
> > need for the higher values less than infinity, It would seem simpler
> > for now to adopt the same conventions as llvm.loop.vectorize.width
> > so that some processing infrastructure can be shared easily.
> > 
> >> I don't like using the name 'safelen' 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.
> > 
> > I'm open to naming suggestions, though I'm wondering if
sticking with
> > what is now a term of art in OpenMP might be the least of all evils,
> > because the semantics turn out to be a little more subtle than
> > just a minimum dependence distance.  My current wording of the
semantics
> > for safelen of k are: 
> > 
> >  /// The loop can be assumed to have no loop-carried
> >  /// lexically backward dependencies with distance less than k.
> 
> This means you would allow lexically forward dependencies which complicates
things (this would need more infrastructure in clang). You need to carry over
“source order” from the front-end. Because the dependency is loop carried llvm
would be allowed to move loads and stores within the loop:
This should not be that hard (see below).
> Lexical forward dependency:
> 
> #pragma vectorize safelen(4)
> for (i = …) {
>    a[i] = b[i] + z[i];
>    c[i]  = a[i-1] + 1;
> }
> 
> LLVM might tranform this loop to:
> 
> for (i = …) {
>    c[i]  = a[i-1] + 1;
>    a[i] = b[i] + z[i];
> }
> 
> if we now vectorize this (without knowledge of the orignal source order) we
get the wrong answer:
> 
> for (i = …) {
>    c[i]  = a[i-1:i+2] + 1;
>    a[i:i+3] = b[i] + z[i];
> }
> 
> Alternatively, the metadata loop.vectorize.safelen would have to prevent
any such reordering of accesses i.e. any pass that reorders memory accesses
would have to be aware of it which is fragile.
Could we number the memory accesses for such loops (e.g., in clang)?
Adding metadata to each memory access which points to the safelen
annotation and contains an increasing constant would be similarly
fragile as other constructions we use at the moment. However, it would
allow us to determine iff the current order is still the original one or
not. (At least if I did not miss anything).

Best regards,
  Johannes

-- 

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/20140820/12b3dcf1/attachment.sig>

----- Original Message -----
> From: "Arch Robison" <arch.robison at intel.com>
> To: "Hal Finkel" <hfinkel at anl.gov>, "Roel
Jordans" <r.jordans at tue.nl>
> Cc: llvmdev at cs.uiuc.edu
> Sent: Wednesday, August 20, 2014 10:08:15 AM
> Subject: RE: [LLVMdev] Proposal for
""llvm.mem.vectorize.safelen"
> 
> > I recommend that you send patches for an implementation
> > (including the Loop::GetAnnotatedVectorSafelen function
> >  and associated updates to the vectorizer) for review.
> 
> I expect to send the patches for review later this week.
> 
> > Make sure to remember LangRef updates!
> 
> Thanks for the reminder.
> 
> > Also, looking at the original proposal again, I see no reason
> > to restrict this to an i32: we might as well allow it to be an
> > i64 obviously we don't have billion-lane vectors, but the
> > metadata can also be useful for other kinds of analysis).
> 
> I doubt there is much advantage between knowing the minimum
> loop-carried
> dependence difference is 1u<<31 or 1u<<63.  Unless there is a
clear
> need for the higher values less than infinity, It would seem simpler
> for now to adopt the same conventions as llvm.loop.vectorize.width
> so that some processing infrastructure can be shared easily.
Okay; fair enough.
> 
> > I don't like using the name 'safelen' 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.
> 
> I'm open to naming suggestions, though I'm wondering if sticking
with
> what is now a term of art in OpenMP might be the least of all evils,
> because the semantics turn out to be a little more subtle than
> just a minimum dependence distance.  My current wording of the
> semantics
> for safelen of k are:
> 
>   /// The loop can be assumed to have no loop-carried
>   /// lexically backward dependencies with distance less than k.
Alright. Perhaps you're right that it is better to stick with safelen as a
term of art. I'm okay with that.

 -Hal
> 
> - Arch D. Robison
>   Intel Corporation
> 
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory