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

[Hal Finkel]

----- Original Message -----
> From: "Arch Robison" <arch.robison at intel.com>
> To: "Jonathan Humphreys" <j-humphreys at ti.com>, "Hal Finkel" <hfinkel at anl.gov>, "Renato Golin"
> <renato.golin at linaro.org>, "Alexander Musman (alexander.musman at gmail.com)" <alexander.musman at gmail.com>
> Cc: "LLVM Dev" <llvmdev at cs.uiuc.edu>
> Sent: Thursday, August 28, 2014 12:32:25 PM
> Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"
> 
> 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.

What was the outcome of this?

Thanks again,
Hal

> 
> - 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
> 
> 

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory