<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
        {font-family:SimSun;
        panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
        {font-family:"Cambria Math";
        panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
        {font-family:Calibri;
        panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
        {font-family:"\@SimSun";
        panose-1:2 1 6 0 3 1 1 1 1 1;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
        {margin:0in;
        margin-bottom:.0001pt;
        font-size:11.0pt;
        font-family:"Calibri","sans-serif";}
a:link, span.MsoHyperlink
        {mso-style-priority:99;
        color:#0563C1;
        text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
        {mso-style-priority:99;
        color:#954F72;
        text-decoration:underline;}
p.MsoPlainText, li.MsoPlainText, div.MsoPlainText
        {mso-style-priority:99;
        mso-style-link:"Plain Text Char";
        margin:0in;
        margin-bottom:.0001pt;
        font-size:11.0pt;
        font-family:"Calibri","sans-serif";}
span.PlainTextChar
        {mso-style-name:"Plain Text Char";
        mso-style-priority:99;
        mso-style-link:"Plain Text";
        font-family:"Calibri","sans-serif";}
.MsoChpDefault
        {mso-style-type:export-only;
        font-family:"Calibri","sans-serif";}
@page WordSection1
        {size:8.5in 11.0in;
        margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
        {page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoPlainText">More precisely, for a simd loop, if the safelen(VL) clause is specified,  there should have no loop-carried lexical backward data dependency
<b><span style="color:#4472C4">within the specified safe vector length VL</span></b>.
<o:p></o:p></p>
<p class="MsoPlainText"><a name="_MailEndCompose">We will make this clear in the OpenMP 4.1 spec.
<o:p></o:p></a></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">Xinmin Tian (Intel)<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">-----Original Message-----<br>
From: llvmdev-bounces@cs.uiuc.edu [mailto:llvmdev-bounces@cs.uiuc.edu] On Behalf Of Hal Finkel<br>
Sent: Sunday, September 28, 2014 12:59 AM<br>
To: Robison, Arch<br>
Cc: Jonathan Humphreys; LLVM Dev<br>
Subject: Re: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"</p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">----- Original Message -----<o:p></o:p></p>
<p class="MsoPlainText">> From: "Arch Robison" <<a href="mailto:arch.robison@intel.com"><span style="color:windowtext;text-decoration:none">arch.robison@intel.com</span></a>><o:p></o:p></p>
<p class="MsoPlainText">> To: "Jonathan Humphreys" <<a href="mailto:j-humphreys@ti.com"><span style="color:windowtext;text-decoration:none">j-humphreys@ti.com</span></a>>, "Hal Finkel" <<a href="mailto:hfinkel@anl.gov"><span style="color:windowtext;text-decoration:none">hfinkel@anl.gov</span></a>>,
 "Renato Golin"<o:p></o:p></p>
<p class="MsoPlainText">> <<a href="mailto:renato.golin@linaro.org"><span style="color:windowtext;text-decoration:none">renato.golin@linaro.org</span></a>>, "Alexander Musman
<o:p></o:p></p>
<p class="MsoPlainText">> (<a href="mailto:alexander.musman@gmail.com"><span style="color:windowtext;text-decoration:none">alexander.musman@gmail.com</span></a>)" <<a href="mailto:alexander.musman@gmail.com"><span style="color:windowtext;text-decoration:none">alexander.musman@gmail.com</span></a>><o:p></o:p></p>
<p class="MsoPlainText">> Cc: "LLVM Dev" <<a href="mailto:llvmdev@cs.uiuc.edu"><span style="color:windowtext;text-decoration:none">llvmdev@cs.uiuc.edu</span></a>><o:p></o:p></p>
<p class="MsoPlainText">> Sent: Thursday, August 28, 2014 12:32:25 PM<o:p></o:p></p>
<p class="MsoPlainText">> Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> It's a problem in the OpenMP specification.  The authors (including
<o:p></o:p></p>
<p class="MsoPlainText">> some from Intel) intended that the OpenMP simd construct assert no
<o:p></o:p></p>
<p class="MsoPlainText">> lexically backward dependences exist, but as you say, it's not obvious
<o:p></o:p></p>
<p class="MsoPlainText">> from the spec.  One of our OpenMP community members is going to bring
<o:p></o:p></p>
<p class="MsoPlainText">> up the ambiguity with the OpenMP committee.<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">What was the outcome of this?<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">Thanks again,<o:p></o:p></p>
<p class="MsoPlainText">Hal<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> - Arch<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> -----Original Message-----<o:p></o:p></p>
<p class="MsoPlainText">> From: Humphreys, Jonathan [<a href="mailto:j-humphreys@ti.com"><span style="color:windowtext;text-decoration:none">mailto:j-humphreys@ti.com</span></a>]<o:p></o:p></p>
<p class="MsoPlainText">> Sent: Thursday, August 28, 2014 11:53 AM<o:p></o:p></p>
<p class="MsoPlainText">> To: Robison, Arch; Hal Finkel; Renato Golin; Alexander Musman<o:p></o:p></p>
<p class="MsoPlainText">> (<a href="mailto:alexander.musman@gmail.com"><span style="color:windowtext;text-decoration:none">alexander.musman@gmail.com</span></a>)<o:p></o:p></p>
<p class="MsoPlainText">> Cc: LLVM Dev<o:p></o:p></p>
<p class="MsoPlainText">> Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> Well, having not understood the connection between lexical dependence
<o:p></o:p></p>
<p class="MsoPlainText">> and the openMP simd construct yesterday, I inquired in the openMP
<o:p></o:p></p>
<p class="MsoPlainText">> community.  If I understand the answer I got (from someone at Intel),
<o:p></o:p></p>
<p class="MsoPlainText">> the openMP simd construct is really asserting that no lexically
<o:p></o:p></p>
<p class="MsoPlainText">> backward dependences exist.  This is not at all obvious to me from
<o:p></o:p></p>
<p class="MsoPlainText">> reading the spec.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> That answer seems to be in conflict with what you are saying below.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> Thanks<o:p></o:p></p>
<p class="MsoPlainText">> Jon<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> -----Original Message-----<o:p></o:p></p>
<p class="MsoPlainText">> From: Robison, Arch [<a href="mailto:arch.robison@intel.com"><span style="color:windowtext;text-decoration:none">mailto:arch.robison@intel.com</span></a>]<o:p></o:p></p>
<p class="MsoPlainText">> Sent: Thursday, August 28, 2014 10:47 AM<o:p></o:p></p>
<p class="MsoPlainText">> To: Humphreys, Jonathan; Hal Finkel; Renato Golin; Alexander Musman<o:p></o:p></p>
<p class="MsoPlainText">> (<a href="mailto:alexander.musman@gmail.com"><span style="color:windowtext;text-decoration:none">alexander.musman@gmail.com</span></a>)<o:p></o:p></p>
<p class="MsoPlainText">> Cc: LLVM Dev<o:p></o:p></p>
<p class="MsoPlainText">> Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> > Sorry for coming to the discussion so late.  I have a couple of<o:p></o:p></p>
<p class="MsoPlainText">> > questions/comments:<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> Actually, you're note is timely, because I'm planning to send out a
<o:p></o:p></p>
<p class="MsoPlainText">> patch (as soon as I update LangRef and rerun tests) that supports
<o:p></o:p></p>
<p class="MsoPlainText">> safelen but *not* lexical dependences.  I don't need the safelen for
<o:p></o:p></p>
<p class="MsoPlainText">> Julia, but having done the work and seeing that OpenMP needs it, feel
<o:p></o:p></p>
<p class="MsoPlainText">> that I should finish the work to contribute it.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> Yes, safelen and lexical forward dependences are separable.  I was
<o:p></o:p></p>
<p class="MsoPlainText">> initially under the impression that to implement OpenMP 4.0 simd loops
<o:p></o:p></p>
<p class="MsoPlainText">> correctly, support for both safelen and lexical forward dependences
<o:p></o:p></p>
<p class="MsoPlainText">> were necessary.  Indeed, the Intel compiler supports forward lexical
<o:p></o:p></p>
<p class="MsoPlainText">> dependences in OpenMP 4.0 simd loops.<o:p></o:p></p>
<p class="MsoPlainText">>  (Sophisticated vectorizers have to support them anyway for<o:p></o:p></p>
<p class="MsoPlainText">> auto-vectorization.)  But upon closer reading, and discussion with the
<o:p></o:p></p>
<p class="MsoPlainText">> experts here, it became apparent that the OpenMP 4.0 spec talks about
<o:p></o:p></p>
<p class="MsoPlainText">> execution of SIMD instructions, but does not say much about how source
<o:p></o:p></p>
<p class="MsoPlainText">> code is mapped onto those instructions, so support for lexical
<o:p></o:p></p>
<p class="MsoPlainText">> dependences is not necessary for 4.0.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> Likewise, I'm dropping my experiment with supporting lexical forward
<o:p></o:p></p>
<p class="MsoPlainText">> dependences in Julia, though I'm mulling an alternative language-level
<o:p></o:p></p>
<p class="MsoPlainText">> solution.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> > Assuming that lexical ordering is irrelevant to this discussion, it
<o:p></o:p></p>
<p class="MsoPlainText">> > would be nice if we could build upon the <o:p></o:p></p>
<p class="MsoPlainText">> > llvm.mem.parallel_loop_access metadata rather than inventing more
<o:p></o:p></p>
<p class="MsoPlainText">> > metadata.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> Right.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> > I was thinking that you could add an additional parameter that
<o:p></o:p></p>
<p class="MsoPlainText">> > specifies the minimum dependence distance.  It would be optional and
<o:p></o:p></p>
<p class="MsoPlainText">> > if absent, would be infinite (which preserves existing semantics).<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> The parameter is best put on the loop instead of each access.  That
<o:p></o:p></p>
<p class="MsoPlainText">> way it can have different values for different loop levels.  I.e.,
<o:p></o:p></p>
<p class="MsoPlainText">> each loop is marked with its relevant component of the minimum
<o:p></o:p></p>
<p class="MsoPlainText">> distance vector.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> With respect to a more general mechanism, and perhaps more complete
<o:p></o:p></p>
<p class="MsoPlainText">> distance information, that seems worthwhile if there's real benefit to
<o:p></o:p></p>
<p class="MsoPlainText">> be obtained.  I'll leave that to others, though I'd be curious to see
<o:p></o:p></p>
<p class="MsoPlainText">> proposed designs.  I haven't explored the limits of LLVM's metadata
<o:p></o:p></p>
<p class="MsoPlainText">> format.  For instance, what's the best way to store a distance matrix
<o:p></o:p></p>
<p class="MsoPlainText">> as metadata?<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> - I agree with Hal's request that we don't use the name 'safelen'<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> I'm fine with the "minimum_dependence_distance" if everyone else is.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> - Arch<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> -----Original Message-----<o:p></o:p></p>
<p class="MsoPlainText">> From: Humphreys, Jonathan [<a href="mailto:j-humphreys@ti.com"><span style="color:windowtext;text-decoration:none">mailto:j-humphreys@ti.com</span></a>]<o:p></o:p></p>
<p class="MsoPlainText">> Sent: Wednesday, August 27, 2014 5:37 PM<o:p></o:p></p>
<p class="MsoPlainText">> To: Robison, Arch; Hal Finkel; Renato Golin; Alexander Musman<o:p></o:p></p>
<p class="MsoPlainText">> (<a href="mailto:alexander.musman@gmail.com"><span style="color:windowtext;text-decoration:none">alexander.musman@gmail.com</span></a>)<o:p></o:p></p>
<p class="MsoPlainText">> Cc: LLVM Dev<o:p></o:p></p>
<p class="MsoPlainText">> Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> Sorry for coming to the discussion so late.  I have a couple of<o:p></o:p></p>
<p class="MsoPlainText">> questions/comments:<o:p></o:p></p>
<p class="MsoPlainText">>  - I'm no openMP expert but I don't understand the relevance of 
<o:p></o:p></p>
<p class="MsoPlainText">> lexically forward or backward dependence with respect to the<o:p></o:p></p>
<p class="MsoPlainText">>  safelen() metadata.  I would be surprised if the openMP spec based<o:p></o:p></p>
<p class="MsoPlainText">>  safelen() upon lexical ordering for the reasons that you are  running
<o:p></o:p></p>
<p class="MsoPlainText">> up against.<o:p></o:p></p>
<p class="MsoPlainText">>  - I agree with Hal's request that we don't use the name 'safelen'.<o:p></o:p></p>
<p class="MsoPlainText">>   I can think of many other 'safety' requirements for SIMD (such as 
<o:p></o:p></p>
<p class="MsoPlainText">> alignment), and the proposed metadata is specifically addressing 
<o:p></o:p></p>
<p class="MsoPlainText">> memory dependence.<o:p></o:p></p>
<p class="MsoPlainText">>  - what are the semantics for outer loop dependences in nested loops?<o:p></o:p></p>
<p class="MsoPlainText">>   I believe that openMP restricts the usage of this clause to nested 
<o:p></o:p></p>
<p class="MsoPlainText">> loops that are perfectly nested and collapsible.  We will be 
<o:p></o:p></p>
<p class="MsoPlainText">> introducing this metadata in LLVM without such restrictions.<o:p></o:p></p>
<p class="MsoPlainText">>  - Assuming that lexical ordering is irrelevant to this discussion, 
<o:p></o:p></p>
<p class="MsoPlainText">> it would be nice if we could build upon the  <o:p></o:p></p>
<p class="MsoPlainText">> llvm.mem.parallel_loop_access metadata rather than inventing more 
<o:p></o:p></p>
<p class="MsoPlainText">> metadata.  I was thinking that you could add an additional  parameter
<o:p></o:p></p>
<p class="MsoPlainText">> that specifies the minimum dependence distance.  It would  be optional
<o:p></o:p></p>
<p class="MsoPlainText">> and if absent, would be infinite (which preserves  existing
<o:p></o:p></p>
<p class="MsoPlainText">> semantics).<o:p></o:p></p>
<p class="MsoPlainText">>  - And having said that, I'm also wondering (but haven't thought any 
<o:p></o:p></p>
<p class="MsoPlainText">> of it through) if instead of inventing metadata to address  particular
<o:p></o:p></p>
<p class="MsoPlainText">> language features, we should instead invent a more  general mechanism
<o:p></o:p></p>
<p class="MsoPlainText">> for expressing memory independence through  metadata.  Then the
<o:p></o:p></p>
<p class="MsoPlainText">> expression of a language feature could be  decomposed into basic
<o:p></o:p></p>
<p class="MsoPlainText">> dependence metadata.  There are many  advantages to this.  It would be
<o:p></o:p></p>
<p class="MsoPlainText">> more precise (operation based vs  loop based).  Being basic/lowlevel,
<o:p></o:p></p>
<p class="MsoPlainText">> passes that invalidate it (or  enhance it) can do that at a
<o:p></o:p></p>
<p class="MsoPlainText">> fundamental level and not need to be  aware of a specific language
<o:p></o:p></p>
<p class="MsoPlainText">> feature that might be implied in the  name of the metadata.  And being
<o:p></o:p></p>
<p class="MsoPlainText">> more precise, it would be more  robust because any pass that
<o:p></o:p></p>
<p class="MsoPlainText">> introduces memory operations would not  have the metadata and so
<o:p></o:p></p>
<p class="MsoPlainText">> wouldn't inherit assertions that might not  be true for it.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> Jon<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">--<o:p></o:p></p>
<p class="MsoPlainText">Hal Finkel<o:p></o:p></p>
<p class="MsoPlainText">Assistant Computational Scientist<o:p></o:p></p>
<p class="MsoPlainText">Leadership Computing Facility<o:p></o:p></p>
<p class="MsoPlainText">Argonne National Laboratory<o:p></o:p></p>
<p class="MsoPlainText">_______________________________________________<o:p></o:p></p>
<p class="MsoPlainText">LLVM Developers mailing list<o:p></o:p></p>
<p class="MsoPlainText"><a href="mailto:LLVMdev@cs.uiuc.edu"><span style="color:windowtext;text-decoration:none">LLVMdev@cs.uiuc.edu</span></a>         <a href="http://llvm.cs.uiuc.edu"><span style="color:windowtext;text-decoration:none">http://llvm.cs.uiuc.edu</span></a><o:p></o:p></p>
<p class="MsoPlainText"><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev"><span style="color:windowtext;text-decoration:none">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</span></a><o:p></o:p></p>
</div>
</body>
</html>