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

Sun Sep 28 13:40:52 PDT 2014

More precisely, for a simd loop, if the safelen(VL) clause is specified,  there should have no loop-carried lexical backward data dependency within the specified safe vector length VL.

We will make this clear in the OpenMP 4.1 spec.

Xinmin Tian (Intel)

-----Original Message-----
From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of Hal Finkel
Sent: Sunday, September 28, 2014 12:59 AM
To: Robison, Arch
Cc: Jonathan Humphreys; LLVM Dev
Subject: Re: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

----- Original Message -----

> From: "Arch Robison" <arch.robison at intel.com<mailto:arch.robison at intel.com>>

> To: "Jonathan Humphreys" <j-humphreys at ti.com<mailto:j-humphreys at ti.com>>, "Hal Finkel" <hfinkel at anl.gov<mailto:hfinkel at anl.gov>>, "Renato Golin"

> <renato.golin at linaro.org<mailto:renato.golin at linaro.org>>, "Alexander Musman

> (alexander.musman at gmail.com<mailto:alexander.musman at gmail.com>)" <alexander.musman at gmail.com<mailto:alexander.musman at gmail.com>>

> Cc: "LLVM Dev" <llvmdev at cs.uiuc.edu<mailto: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<mailto: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<mailto: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<mailto: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

_______________________________________________

LLVM Developers mailing list

LLVMdev at cs.uiuc.edu<mailto:LLVMdev at cs.uiuc.edu>         http://llvm.cs.uiuc.edu

http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140928/0f0833ee/attachment.html>