<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=utf-8">
<meta name="Generator" content="Microsoft Word 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* 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:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
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";}
p.MsoAcetate, li.MsoAcetate, div.MsoAcetate
{mso-style-priority:99;
mso-style-link:"Balloon Text Char";
margin:0in;
margin-bottom:.0001pt;
font-size:8.0pt;
font-family:"Tahoma","sans-serif";}
span.PlainTextChar
{mso-style-name:"Plain Text Char";
mso-style-priority:99;
mso-style-link:"Plain Text";
font-family:"Calibri","sans-serif";}
span.BalloonTextChar
{mso-style-name:"Balloon Text Char";
mso-style-priority:99;
mso-style-link:"Balloon Text";
font-family:"Tahoma","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="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoPlainText">Pekka, thanks for updating this.<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">A small edit - the sentence ending with:<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">"with L1 and L2 being the set of loops associated with that metadata, respectively, then there is no loop carried dependence between m1 and m2 for loops L1 or L2."<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">Should read:<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">"with L1 and L2 being the set of loops associated with that metadata, respectively, then there is no loop carried dependence between m1 and m2 for loops
<i><span style="color:red">in both L1 and L2</span></i>."<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">-----Original Message-----<br>
From: Pekka Jääskeläinen [mailto:pekka.jaaskelainen@tut.fi] <br>
Sent: Friday, May 23, 2014 6:45 AM<br>
To: Humphreys, Jonathan; Hal Finkel; Tobias Grosser<br>
Cc: llvmdev@cs.uiuc.edu<br>
Subject: Re: [LLVMdev] parallel loop metadata question</p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">OK,<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">I updated the text to LangRef in r209507 after some editing.<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">On 05/11/2014 12:36 PM, Pekka Jääskeläinen wrote:<o:p></o:p></p>
<p class="MsoPlainText">> Hi,<o:p></o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">> This looks good to me except that the first sentence could already
<o:p></o:p></p>
<p class="MsoPlainText">> include "that refer to the same loop" or similar.<o:p></o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">> I could imagine that e.g. loop invariant code motion, if applied to a
<o:p></o:p></p>
<p class="MsoPlainText">> parallel loop could hoist code out of inner loops to outer (parallel)
<o:p></o:p></p>
<p class="MsoPlainText">> loops. Then the outer loop contains parallel_loop_access instructions
<o:p></o:p></p>
<p class="MsoPlainText">> referring to the inner loop, making the outer loop non-trivially
<o:p></o:p></p>
<p class="MsoPlainText">> parallel.<o:p></o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">> But these are probably rare cases as, at least in pocl, basic
<o:p></o:p></p>
<p class="MsoPlainText">> optimizations have already been executed before the work-group
<o:p></o:p></p>
<p class="MsoPlainText">> function generation where the parallel work-item loops are created.<o:p></o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">> On 05/10/2014 12:08 AM, Humphreys, Jonathan wrote:<o:p></o:p></p>
<p class="MsoPlainText">>> I propose that we change the first paragraph of<o:p></o:p></p>
<p class="MsoPlainText">>> <a href="http://llvm.org/docs/LangRef.html#llvm-mem-parallel-loop-access-metadata">
<span style="color:windowtext;text-decoration:none">http://llvm.org/docs/LangRef.html#llvm-mem-parallel-loop-access-metadata</span></a>:<o:p></o:p></p>
<p class="MsoPlainText">>><o:p> </o:p></p>
<p class="MsoPlainText">>> ---<o:p></o:p></p>
<p class="MsoPlainText">>> For a loop to be parallel, in addition to using the llvm.loop
<o:p></o:p></p>
<p class="MsoPlainText">>> metadata to mark the loop latch branch instruction, also all of the
<o:p></o:p></p>
<p class="MsoPlainText">>> memory accessing instructions in the loop body need to be marked with
<o:p></o:p></p>
<p class="MsoPlainText">>> the llvm.mem.parallel_loop_access metadata. If there is at least one
<o:p></o:p></p>
<p class="MsoPlainText">>> memory accessing instruction not marked with the metadata, the loop
<o:p></o:p></p>
<p class="MsoPlainText">>> must be considered a sequential loop. This causes parallel loops to
<o:p></o:p></p>
<p class="MsoPlainText">>> be converted to sequential loops due to optimization passes that are
<o:p></o:p></p>
<p class="MsoPlainText">>> unaware of the parallel semantics and that insert new memory instructions to the loop body.<o:p></o:p></p>
<p class="MsoPlainText">>> ---<o:p></o:p></p>
<p class="MsoPlainText">>><o:p> </o:p></p>
<p class="MsoPlainText">>> To be:<o:p></o:p></p>
<p class="MsoPlainText">>><o:p> </o:p></p>
<p class="MsoPlainText">>> ---<o:p></o:p></p>
<p class="MsoPlainText">>> The llvm.mem.parallel_loop_access metadata attaches to instructions
<o:p></o:p></p>
<p class="MsoPlainText">>> and denotes that no loop carried memory dependence exist between it
<o:p></o:p></p>
<p class="MsoPlainText">>> and other such denoted instructions. The <o:p></o:p></p>
<p class="MsoPlainText">>> llvm.mem.parallel_loop_access metadata refers to a loop identifier,
<o:p></o:p></p>
<p class="MsoPlainText">>> or metadata containing a list of loop identifiers for nested loops -
<o:p></o:p></p>
<p class="MsoPlainText">>> these are the loops to which the metadata applies. Precisely, given
<o:p></o:p></p>
<p class="MsoPlainText">>> two instructions m1 and m2 that both have <o:p></o:p></p>
<p class="MsoPlainText">>> llvm.mem.parallel_loop_access metadata, with L1 and L2 being the set
<o:p></o:p></p>
<p class="MsoPlainText">>> of loops associated with that metadata, respectively, then there is no loop carried dependence between m1 and m2 for loops in both L1 and L2.<o:p></o:p></p>
<p class="MsoPlainText">>><o:p> </o:p></p>
<p class="MsoPlainText">>> Trivially, if all memory accessing instructions in a loop have
<o:p></o:p></p>
<p class="MsoPlainText">>> llvm.mem.parallel_loop_access metadata that refers to that loop, then
<o:p></o:p></p>
<p class="MsoPlainText">>> the loop has no loop carried memory dependence and is considered to
<o:p></o:p></p>
<p class="MsoPlainText">>> be a parallel loop. Note that if not all memory access instructions
<o:p></o:p></p>
<p class="MsoPlainText">>> have this metadata referring to this loop, then the loop is not
<o:p></o:p></p>
<p class="MsoPlainText">>> trivially parallel - additional memory dependence analysis is
<o:p></o:p></p>
<p class="MsoPlainText">>> required to make that determination. As a fail safe mechanism, this
<o:p></o:p></p>
<p class="MsoPlainText">>> causes loops that were originally parallel to be considered
<o:p></o:p></p>
<p class="MsoPlainText">>> sequential if optimization passes that are unaware of the parallel
<o:p></o:p></p>
<p class="MsoPlainText">>> semantics insert new memory instructions into the loop body.<o:p></o:p></p>
<p class="MsoPlainText">>> ---<o:p></o:p></p>
<p class="MsoPlainText">>><o:p> </o:p></p>
<p class="MsoPlainText">>> Please let me know your feedback.<o:p></o:p></p>
<p class="MsoPlainText">>><o:p> </o:p></p>
<p class="MsoPlainText">>> As far as taking advantage of the more precise semantics, I've
<o:p></o:p></p>
<p class="MsoPlainText">>> dropped the priority of this work because I'm not seeing cases where
<o:p></o:p></p>
<p class="MsoPlainText">>> we insert memory instruction. I'm wondering if others have any
<o:p></o:p></p>
<p class="MsoPlainText">>> anecdotal evidence of how often we 'loose' the fact that a loop is
<o:p></o:p></p>
<p class="MsoPlainText">>> parallel because of inserting memory instructions during optimizations.<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">>><o:p> </o:p></p>
<p class="MsoPlainText">>> -----Original Message-----<o:p></o:p></p>
<p class="MsoPlainText">>> From: Hal Finkel [<a href="mailto:hfinkel@anl.gov"><span style="color:windowtext;text-decoration:none">mailto:hfinkel@anl.gov</span></a>]<o:p></o:p></p>
<p class="MsoPlainText">>> Sent: Monday, May 05, 2014 5:14 PM<o:p></o:p></p>
<p class="MsoPlainText">>> To: Humphreys, Jonathan<o:p></o:p></p>
<p class="MsoPlainText">>> Cc: Pekka Jääskeläinen; <a href="mailto:llvmdev@cs.uiuc.edu">
<span style="color:windowtext;text-decoration:none">llvmdev@cs.uiuc.edu</span></a>; Tobias Grosser<o:p></o:p></p>
<p class="MsoPlainText">>> Subject: Re: [LLVMdev] parallel loop metadata question<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: "Jonathan Humphreys" <<a href="mailto:j-humphreys@ti.com"><span style="color:windowtext;text-decoration:none">j-humphreys@ti.com</span></a>><o:p></o:p></p>
<p class="MsoPlainText">>>> To: "Hal Finkel" <<a href="mailto:hfinkel@anl.gov"><span style="color:windowtext;text-decoration:none">hfinkel@anl.gov</span></a>>, "Tobias Grosser"<o:p></o:p></p>
<p class="MsoPlainText">>>> <<a href="mailto:tobias@grosser.es"><span style="color:windowtext;text-decoration:none">tobias@grosser.es</span></a>><o:p></o:p></p>
<p class="MsoPlainText">>>> Cc: "Pekka Jääskeläinen" <<a href="mailto:pekka.jaaskelainen@tut.fi"><span style="color:windowtext;text-decoration:none">pekka.jaaskelainen@tut.fi</span></a>>,
<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><o:p></o:p></p>
<p class="MsoPlainText">>>> Sent: Monday, May 5, 2014 5:09:42 PM<o:p></o:p></p>
<p class="MsoPlainText">>>> Subject: RE: [LLVMdev] parallel loop metadata question<o:p></o:p></p>
<p class="MsoPlainText">>>><o:p> </o:p></p>
<p class="MsoPlainText">>>> Will do. I will write something up.<o:p></o:p></p>
<p class="MsoPlainText">>>><o:p> </o:p></p>
<p class="MsoPlainText">>>> Hal, your concern below isn't so much with the proposed semantics
<o:p></o:p></p>
<p class="MsoPlainText">>>> but rather with the use - that optimizations must respect the loop
<o:p></o:p></p>
<p class="MsoPlainText">>>> for which the metadata applies, correct?<o:p></o:p></p>
<p class="MsoPlainText">>><o:p> </o:p></p>
<p class="MsoPlainText">>> Yes, sounds right. Nevertheless, I would recommend putting such a
<o:p></o:p></p>
<p class="MsoPlainText">>> cautionary note into the documentation itself just to make explicit
<o:p></o:p></p>
<p class="MsoPlainText">>> an issue which might otherwise be overlooked.<o:p></o:p></p>
<p class="MsoPlainText">>><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">>>> 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: Hal Finkel [<a href="mailto:hfinkel@anl.gov"><span style="color:windowtext;text-decoration:none">mailto:hfinkel@anl.gov</span></a>]<o:p></o:p></p>
<p class="MsoPlainText">>>> Sent: Monday, May 05, 2014 4:00 AM<o:p></o:p></p>
<p class="MsoPlainText">>>> To: Tobias Grosser<o:p></o:p></p>
<p class="MsoPlainText">>>> Cc: Pekka Jääskeläinen; Humphreys, Jonathan; <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">>>> Subject: Re: [LLVMdev] parallel loop metadata question<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: "Tobias Grosser" <<a href="mailto:tobias@grosser.es"><span style="color:windowtext;text-decoration:none">tobias@grosser.es</span></a>><o:p></o:p></p>
<p class="MsoPlainText">>>>> To: "Pekka Jääskeläinen" <<a href="mailto:pekka.jaaskelainen@tut.fi"><span style="color:windowtext;text-decoration:none">pekka.jaaskelainen@tut.fi</span></a>>, "Jonathan
<o:p></o:p></p>
<p class="MsoPlainText">>>>> Humphreys" <<a href="mailto:j-humphreys@ti.com"><span style="color:windowtext;text-decoration:none">j-humphreys@ti.com</span></a>>,
<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: Monday, May 5, 2014 3:36:07 AM<o:p></o:p></p>
<p class="MsoPlainText">>>>> Subject: Re: [LLVMdev] parallel loop metadata question<o:p></o:p></p>
<p class="MsoPlainText">>>>><o:p> </o:p></p>
<p class="MsoPlainText">>>>> On 05/05/2014 10:14, Pekka Jääskeläinen wrote:<o:p></o:p></p>
<p class="MsoPlainText">>>>>> On 05/02/2014 07:22 PM, Humphreys, Jonathan wrote:<o:p></o:p></p>
<p class="MsoPlainText">>>>>>> Thanks for the link. I understand your concern of caution with
<o:p></o:p></p>
<p class="MsoPlainText">>>>>>> metadata.<o:p></o:p></p>
<p class="MsoPlainText">>>>>>> I cannot, though, imagine how the dependence relation<o:p></o:p></p>
<p class="MsoPlainText">>>>>>> (independence)<o:p></o:p></p>
<p class="MsoPlainText">>>>>>> of two<o:p></o:p></p>
<p class="MsoPlainText">>>>>>> memory references can be affected by a third memory reference.<o:p></o:p></p>
<p class="MsoPlainText">>>>>>> If<o:p></o:p></p>
<p class="MsoPlainText">>>>>>> two references are independent across loop iterations, then they
<o:p></o:p></p>
<p class="MsoPlainText">>>>>>> are independent, and any other load or store cannot change that.<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">>>>>> Yes, it makes sense. I'm mostly concerned about accesses to stack,
<o:p></o:p></p>
<p class="MsoPlainText">>>>>> but even those at this point should remain independent. Otherwise
<o:p></o:p></p>
<p class="MsoPlainText">>>>>> even the current semantics might produce broken code with parallel
<o:p></o:p></p>
<p class="MsoPlainText">>>>>> stack accesses.<o:p></o:p></p>
<p class="MsoPlainText">>>>>><o:p> </o:p></p>
<p class="MsoPlainText">>>>>> However, as this is such a major semantics change to the original
<o:p></o:p></p>
<p class="MsoPlainText">>>>>> one, I'd like to hear more opinions on it. I suggest you create a<o:p></o:p></p>
<p class="MsoPlainText">>>>>> (documentation)<o:p></o:p></p>
<p class="MsoPlainText">>>>>> patch where the new semantics is articulated and request comments
<o:p></o:p></p>
<p class="MsoPlainText">>>>>> for it at the LLVM-commits list.<o:p></o:p></p>
<p class="MsoPlainText">>>>><o:p> </o:p></p>
<p class="MsoPlainText">>>>> I agree with both. I think the extension is very reasonable and I
<o:p></o:p></p>
<p class="MsoPlainText">>>>> also do not see a reason why this interpretation should cause
<o:p></o:p></p>
<p class="MsoPlainText">>>>> troubles.<o:p></o:p></p>
<p class="MsoPlainText">>>>> However, to get it right it would be good to get this throughly
<o:p></o:p></p>
<p class="MsoPlainText">>>>> reviewed.<o:p></o:p></p>
<p class="MsoPlainText">>>><o:p> </o:p></p>
<p class="MsoPlainText">>>> I agree, I think this sounds reasonable. You'll certainly need to be
<o:p></o:p></p>
<p class="MsoPlainText">>>> careful, however, that the associated instruction has not been
<o:p></o:p></p>
<p class="MsoPlainText">>>> hoisted/sunk out of the associated loops. Even if the load is one
<o:p></o:p></p>
<p class="MsoPlainText">>>> that can be speculated, that does not mean that there was not a
<o:p></o:p></p>
<p class="MsoPlainText">>>> control dependence on the independence information itself.<o:p></o:p></p>
<p class="MsoPlainText">>>><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">>>>> Tobias<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>
<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">>><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">><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">Pekka<o:p></o:p></p>
</div>
</body>
</html>