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

> Sorry for coming to the discussion so late.  I have a couple of
questions/comments:
Actually, you're note is timely, because I'm planning to send out a
patch (as soon as I update LangRef and rerun tests) that supports safelen but
*not* lexical dependences.  I don't need the safelen for Julia, but having
done the work and seeing that OpenMP needs it, feel that I should finish the
work to contribute it.

Yes, safelen and lexical forward dependences are separable.  I was initially
under the impression that to implement OpenMP 4.0 simd loops correctly, support
for both safelen and lexical forward dependences were necessary.  Indeed, the
Intel compiler supports forward lexical dependences in OpenMP 4.0 simd loops. 
(Sophisticated vectorizers have to support them anyway for auto-vectorization.) 
But upon closer reading, and discussion with the experts here, it became
apparent that the OpenMP 4.0 spec talks about execution of SIMD instructions,
but does not say much about how source code is mapped onto those instructions,
so support for lexical dependences is not necessary for 4.0.

Likewise, I'm dropping my experiment with supporting lexical forward
dependences in Julia, though I'm mulling an alternative language-level
solution.
> Assuming that lexical ordering is irrelevant to this discussion, it would
be nice if we could build upon the llvm.mem.parallel_loop_access metadata rather
than inventing more metadata.
Right.
> I was thinking that you could add an additional parameter that specifies
the minimum dependence distance.  It would be optional and if absent, would be
infinite (which preserves existing semantics).
The parameter is best put on the loop instead of each access.  That way it can
have different values for different loop levels.  I.e., each loop is marked with
its relevant component of the minimum distance vector.

With respect to a more general mechanism, and perhaps more complete distance
information, that seems worthwhile if there's real benefit to be obtained. 
I'll leave that to others, though I'd be curious to see proposed
designs.  I haven't explored the limits of LLVM's metadata format.  For
instance, what's the best way to store a distance matrix as metadata?

- I agree with Hal's request that we don't use the name
'safelen'

I'm fine with the "minimum_dependence_distance" if everyone else
is.

- Arch

-----Original Message-----
From: Humphreys, Jonathan [mailto:j-humphreys at ti.com] 
Sent: Wednesday, August 27, 2014 5:37 PM
To: Robison, Arch; Hal Finkel; Renato Golin; Alexander Musman (alexander.musman
at gmail.com)
Cc: LLVM Dev
Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

Sorry for coming to the discussion so late.  I have a couple of
questions/comments:
 - I'm no openMP expert but I don't understand the relevance of
lexically forward or backward dependence with respect to the safelen() metadata.
I would be surprised if the openMP spec based safelen() upon lexical ordering
for the reasons that you are running up against.
 - I agree with Hal's request that we don't use the name
'safelen'.  I can think of many other 'safety' requirements for
SIMD (such as alignment), and the proposed metadata is specifically addressing
memory dependence.
 - what are the semantics for outer loop dependences in nested loops?  I believe
that openMP restricts the usage of this clause to nested loops that are
perfectly nested and collapsible.  We will be introducing this metadata in LLVM
without such restrictions.
 - Assuming that lexical ordering is irrelevant to this discussion, it would be
nice if we could build upon the llvm.mem.parallel_loop_access metadata rather
than inventing more metadata.  I was thinking that you could add an additional
parameter that specifies the minimum dependence distance.  It would be optional
and if absent, would be infinite (which preserves existing semantics).
 - And having said that, I'm also wondering (but haven't thought any of
it through) if instead of inventing metadata to address particular language
features, we should instead invent a more general mechanism for expressing
memory independence through metadata.  Then the expression of a language feature
could be decomposed into basic dependence metadata.  There are many advantages
to this.  It would be more precise (operation based vs loop based).  Being
basic/lowlevel, passes that invalidate it (or enhance it) can do that at a
fundamental level and not need to be aware of a specific language feature that
might be implied in the name of the metadata.  And being more precise, it would
be more robust because any pass that introduces memory operations would not have
the metadata and so wouldn't inherit assertions that might not be true for
it.

Jon

Well, having not understood the connection between lexical dependence and the
openMP simd construct yesterday, I inquired in the openMP community.  If I
understand the answer I got (from someone at Intel), the openMP simd construct
is really asserting that no lexically backward dependences exist.  This is not
at all obvious to me from reading the spec.

That answer seems to be in conflict with what you are saying below.

Thanks
Jon

-----Original Message-----
From: Robison, Arch [mailto:arch.robison at intel.com] 
Sent: Thursday, August 28, 2014 10:47 AM
To: Humphreys, Jonathan; Hal Finkel; Renato Golin; Alexander Musman
(alexander.musman at gmail.com)
Cc: LLVM Dev
Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"
> Sorry for coming to the discussion so late.  I have a couple of
questions/comments:
Actually, you're note is timely, because I'm planning to send out a
patch (as soon as I update LangRef and rerun tests) that supports safelen but
*not* lexical dependences.  I don't need the safelen for Julia, but having
done the work and seeing that OpenMP needs it, feel that I should finish the
work to contribute it.

Yes, safelen and lexical forward dependences are separable.  I was initially
under the impression that to implement OpenMP 4.0 simd loops correctly, support
for both safelen and lexical forward dependences were necessary.  Indeed, the
Intel compiler supports forward lexical dependences in OpenMP 4.0 simd loops. 
(Sophisticated vectorizers have to support them anyway for auto-vectorization.) 
But upon closer reading, and discussion with the experts here, it became
apparent that the OpenMP 4.0 spec talks about execution of SIMD instructions,
but does not say much about how source code is mapped onto those instructions,
so support for lexical dependences is not necessary for 4.0.

Likewise, I'm dropping my experiment with supporting lexical forward
dependences in Julia, though I'm mulling an alternative language-level
solution.
> Assuming that lexical ordering is irrelevant to this discussion, it would
be nice if we could build upon the llvm.mem.parallel_loop_access metadata rather
than inventing more metadata.
Right.
> I was thinking that you could add an additional parameter that specifies
the minimum dependence distance.  It would be optional and if absent, would be
infinite (which preserves existing semantics).
The parameter is best put on the loop instead of each access.  That way it can
have different values for different loop levels.  I.e., each loop is marked with
its relevant component of the minimum distance vector.

With respect to a more general mechanism, and perhaps more complete distance
information, that seems worthwhile if there's real benefit to be obtained. 
I'll leave that to others, though I'd be curious to see proposed
designs.  I haven't explored the limits of LLVM's metadata format.  For
instance, what's the best way to store a distance matrix as metadata?

- I agree with Hal's request that we don't use the name
'safelen'

I'm fine with the "minimum_dependence_distance" if everyone else
is.

- Arch

-----Original Message-----
From: Humphreys, Jonathan [mailto:j-humphreys at ti.com] 
Sent: Wednesday, August 27, 2014 5:37 PM
To: Robison, Arch; Hal Finkel; Renato Golin; Alexander Musman (alexander.musman
at gmail.com)
Cc: LLVM Dev
Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

Sorry for coming to the discussion so late.  I have a couple of
questions/comments:
 - I'm no openMP expert but I don't understand the relevance of
lexically forward or backward dependence with respect to the safelen() metadata.
I would be surprised if the openMP spec based safelen() upon lexical ordering
for the reasons that you are running up against.
 - I agree with Hal's request that we don't use the name
'safelen'.  I can think of many other 'safety' requirements for
SIMD (such as alignment), and the proposed metadata is specifically addressing
memory dependence.
 - what are the semantics for outer loop dependences in nested loops?  I believe
that openMP restricts the usage of this clause to nested loops that are
perfectly nested and collapsible.  We will be introducing this metadata in LLVM
without such restrictions.
 - Assuming that lexical ordering is irrelevant to this discussion, it would be
nice if we could build upon the llvm.mem.parallel_loop_access metadata rather
than inventing more metadata.  I was thinking that you could add an additional
parameter that specifies the minimum dependence distance.  It would be optional
and if absent, would be infinite (which preserves existing semantics).
 - And having said that, I'm also wondering (but haven't thought any of
it through) if instead of inventing metadata to address particular language
features, we should instead invent a more general mechanism for expressing
memory independence through metadata.  Then the expression of a language feature
could be decomposed into basic dependence metadata.  There are many advantages
to this.  It would be more precise (operation based vs loop based).  Being
basic/lowlevel, passes that invalidate it (or enhance it) can do that at a
fundamental level and not need to be aware of a specific language feature that
might be implied in the name of the metadata.  And being more precise, it would
be more robust because any pass that introduces memory operations would not have
the metadata and so wouldn't inherit assertions that might not be true for
it.

Jon

It's a problem in the OpenMP specification.  The authors (including some
from Intel) intended that the OpenMP simd construct assert no lexically backward
dependences exist, but as you say, it's not obvious from the spec.  One of
our OpenMP community members is going to bring up the ambiguity with the OpenMP
committee.

- Arch

-----Original Message-----
From: Humphreys, Jonathan [mailto:j-humphreys at ti.com] 
Sent: Thursday, August 28, 2014 11:53 AM
To: Robison, Arch; Hal Finkel; Renato Golin; Alexander Musman (alexander.musman
at gmail.com)
Cc: LLVM Dev
Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

Well, having not understood the connection between lexical dependence and the
openMP simd construct yesterday, I inquired in the openMP community.  If I
understand the answer I got (from someone at Intel), the openMP simd construct
is really asserting that no lexically backward dependences exist.  This is not
at all obvious to me from reading the spec.

That answer seems to be in conflict with what you are saying below.

Thanks
Jon

-----Original Message-----
From: Robison, Arch [mailto:arch.robison at intel.com] 
Sent: Thursday, August 28, 2014 10:47 AM
To: Humphreys, Jonathan; Hal Finkel; Renato Golin; Alexander Musman
(alexander.musman at gmail.com)
Cc: LLVM Dev
Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"
> Sorry for coming to the discussion so late.  I have a couple of
questions/comments:
Actually, you're note is timely, because I'm planning to send out a
patch (as soon as I update LangRef and rerun tests) that supports safelen but
*not* lexical dependences.  I don't need the safelen for Julia, but having
done the work and seeing that OpenMP needs it, feel that I should finish the
work to contribute it.

Yes, safelen and lexical forward dependences are separable.  I was initially
under the impression that to implement OpenMP 4.0 simd loops correctly, support
for both safelen and lexical forward dependences were necessary.  Indeed, the
Intel compiler supports forward lexical dependences in OpenMP 4.0 simd loops. 
(Sophisticated vectorizers have to support them anyway for auto-vectorization.) 
But upon closer reading, and discussion with the experts here, it became
apparent that the OpenMP 4.0 spec talks about execution of SIMD instructions,
but does not say much about how source code is mapped onto those instructions,
so support for lexical dependences is not necessary for 4.0.

Likewise, I'm dropping my experiment with supporting lexical forward
dependences in Julia, though I'm mulling an alternative language-level
solution.
> Assuming that lexical ordering is irrelevant to this discussion, it would
be nice if we could build upon the llvm.mem.parallel_loop_access metadata rather
than inventing more metadata.
Right.
> I was thinking that you could add an additional parameter that specifies
the minimum dependence distance.  It would be optional and if absent, would be
infinite (which preserves existing semantics).
The parameter is best put on the loop instead of each access.  That way it can
have different values for different loop levels.  I.e., each loop is marked with
its relevant component of the minimum distance vector.

With respect to a more general mechanism, and perhaps more complete distance
information, that seems worthwhile if there's real benefit to be obtained. 
I'll leave that to others, though I'd be curious to see proposed
designs.  I haven't explored the limits of LLVM's metadata format.  For
instance, what's the best way to store a distance matrix as metadata?

- I agree with Hal's request that we don't use the name
'safelen'

I'm fine with the "minimum_dependence_distance" if everyone else
is.

- Arch

-----Original Message-----
From: Humphreys, Jonathan [mailto:j-humphreys at ti.com] 
Sent: Wednesday, August 27, 2014 5:37 PM
To: Robison, Arch; Hal Finkel; Renato Golin; Alexander Musman (alexander.musman
at gmail.com)
Cc: LLVM Dev
Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

Sorry for coming to the discussion so late.  I have a couple of
questions/comments:
 - I'm no openMP expert but I don't understand the relevance of
lexically forward or backward dependence with respect to the safelen() metadata.
I would be surprised if the openMP spec based safelen() upon lexical ordering
for the reasons that you are running up against.
 - I agree with Hal's request that we don't use the name
'safelen'.  I can think of many other 'safety' requirements for
SIMD (such as alignment), and the proposed metadata is specifically addressing
memory dependence.
 - what are the semantics for outer loop dependences in nested loops?  I believe
that openMP restricts the usage of this clause to nested loops that are
perfectly nested and collapsible.  We will be introducing this metadata in LLVM
without such restrictions.
 - Assuming that lexical ordering is irrelevant to this discussion, it would be
nice if we could build upon the llvm.mem.parallel_loop_access metadata rather
than inventing more metadata.  I was thinking that you could add an additional
parameter that specifies the minimum dependence distance.  It would be optional
and if absent, would be infinite (which preserves existing semantics).
 - And having said that, I'm also wondering (but haven't thought any of
it through) if instead of inventing metadata to address particular language
features, we should instead invent a more general mechanism for expressing
memory independence through metadata.  Then the expression of a language feature
could be decomposed into basic dependence metadata.  There are many advantages
to this.  It would be more precise (operation based vs loop based).  Being
basic/lowlevel, passes that invalidate it (or enhance it) can do that at a
fundamental level and not need to be aware of a specific language feature that
might be implied in the name of the metadata.  And being more precise, it would
be more robust because any pass that introduces memory operations would not have
the metadata and so wouldn't inherit assertions that might not be true for
it.

Jon