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