<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Hi Jim,<div class=""><br class=""></div><div class="">I have been working on a low-overhead data race detector for OpenMP programs (<a href="http://dl.acm.org/citation.cfm?id=2688369" class="">SC’14 LLLVM Workshop Paper</a>, <a href="http://sc14.supercomputing.org/sites/all/themes/sc14/files/archive/src_poster/src_poster_pages/spost128.html" class="">SC’14 Poster</a>).</div><div class="">I would like to find exactly all the instructions that are not executed in parallel so that I can exclude them form the data race dynamic analysis to reduce the overhead.</div><div class="">I implemented a pass and a plugin in LLVM that select those lines but it is not very precise because I don’t look in deep of the functions call (for example I an instruction is not within</div><div class="">an OpenMP microtask I assume it’s not executed in parallel, but this is wrong since that function could be called inside an OpenMP constructs).</div><div class=""><br class=""></div><div class="">Does it make sense?</div><div class=""><br class=""></div><div class="">Simone</div><div class=""><br class=""><div apple-content-edited="true" class="">
<div class="">Simone Atzeni</div><div class=""><a href="mailto:simone.at@gmail.com" class="">simone.at@gmail.com</a></div><div class="">+1 (801) 696-8373</div>
</div>
<br class=""><div><blockquote type="cite" class=""><div class="">On Feb 11, 2015, at 10:21, Cownie, James H <<a href="mailto:james.h.cownie@intel.com" class="">james.h.cownie@intel.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="WordSection1" style="page: WordSection1; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><a name="_MailEndCompose" class=""><span lang="EN-GB" style="font-size: 10pt; font-family: Verdana, sans-serif; color: rgb(31, 73, 125);" class="">Can you lift the level a little?<o:p class=""></o:p></span></a></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span lang="EN-GB" style="font-size: 10pt; font-family: Verdana, sans-serif; color: rgb(31, 73, 125);" class=""> </span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span lang="EN-GB" style="font-size: 10pt; font-family: Verdana, sans-serif; color: rgb(31, 73, 125);" class="">Why do you care whether an instruction is executed in a parallel region or not?<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span lang="EN-GB" style="font-size: 10pt; font-family: Verdana, sans-serif; color: rgb(31, 73, 125);" class=""> </span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span lang="EN-GB" style="font-size: 10pt; font-family: Verdana, sans-serif; color: rgb(31, 73, 125);" class="">What higher-level problem are you trying to solve?<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span lang="EN-GB" style="font-size: 10pt; font-family: Verdana, sans-serif; color: rgb(31, 73, 125);" class=""> </span></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span lang="EN-GB" style="font-size: 10pt; font-family: Verdana, sans-serif; color: rgb(31, 73, 125);" class="">-- Jim<br class=""><br class="">James Cownie <<a href="mailto:james.h.cownie@intel.com" style="color: purple; text-decoration: underline;" class="">james.h.cownie@intel.com</a>><br class="">SSG/DPD/TCAR (Technical Computing, Analyzers and Runtimes)<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span lang="EN-GB" style="font-size: 10pt; font-family: Verdana, sans-serif; color: rgb(31, 73, 125);" class="">Tel: +44 117 9071438</span><span lang="EN-GB" style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""></o:p></span></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span lang="EN-GB" style="font-size: 10pt; font-family: Verdana, sans-serif; color: rgb(31, 73, 125);" class=""> </span></div><div class=""><div style="border-style: solid none none; border-top-color: rgb(225, 225, 225); border-top-width: 1pt; padding: 3pt 0cm 0cm;" class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><b class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class="">From:</span></b><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span class="Apple-converted-space"> </span><a href="mailto:openmp-dev-bounces@cs.uiuc.edu" class="">openmp-dev-bounces@cs.uiuc.edu</a> [<a href="mailto:openmp-dev-bounces@cs.uiuc.edu" class="">mailto:openmp-dev-bounces@cs.uiuc.edu</a>]<span class="Apple-converted-space"> </span><b class="">On Behalf Of<span class="Apple-converted-space"> </span></b>Simone Atzeni<br class=""><b class="">Sent:</b><span class="Apple-converted-space"> </span>Wednesday, February 11, 2015 5:15 PM<br class=""><b class="">To:</b><span class="Apple-converted-space"> </span>Ronan KERYELL<br class=""><b class="">Cc:</b><span class="Apple-converted-space"> </span><a href="mailto:openmp-dev@dcs-maillist2.engr.illinois.edu" class="">openmp-dev@dcs-maillist2.engr.illinois.edu</a><br class=""><b class="">Subject:</b><span class="Apple-converted-space"> </span>Re: [Openmp-dev] Knowing if an IR instruction will be executed by an OpenMP region<o:p class=""></o:p></span></div></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Hi Ronan,<o:p class=""></o:p></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">thanks for you answer.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">I think I will try to implement your first suggestion, some inter procedural control flow analysis.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">I would like to do it statically and not involving any dynamic analysis.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">My basic idea is that given an instruction we can check if it belongs or not to an OpenMP microtask, if yes it will be executed<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">in parallel, if not I recursively check if its parent function is called inside an OpenMP construct and so on.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">In order to do this I was taking a look to llvm::CallGraph (<a href="http://llvm.org/docs/doxygen/html/classllvm_1_1CallGraph.html#details" style="color: purple; text-decoration: underline;" class="">http://llvm.org/docs/doxygen/html/classllvm_1_1CallGraph.html#details</a>) <o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">do you think it could help?<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Thanks.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Best,<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Simone<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Simone Atzeni<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><a href="mailto:simone.at@gmail.com" style="color: purple; text-decoration: underline;" class="">simone.at@gmail.com</a><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">+1 (801) 696-8373<o:p class=""></o:p></div></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><div class=""><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">On Feb 11, 2015, at 10:05, Ronan KERYELL <<a href="mailto:ronan-list@keryell.fr" style="color: purple; text-decoration: underline;" class="">ronan-list@keryell.fr</a>> wrote:<o:p class=""></o:p></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><div class=""><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">On Tue, 10 Feb 2015 11:19:39 +0000, "Cownie, James H" <<a href="mailto:james.h.cownie@intel.com" style="color: purple; text-decoration: underline;" class="">james.h.cownie@intel.com</a>> said:<o:p class=""></o:p></div></blockquote></blockquote></blockquote></blockquote></blockquote><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><br class=""><br class=""><o:p class=""></o:p></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">is there a way to understand if an LLVM IR instruction will be<br class="">executed by an OpenMP constructs?<o:p class=""></o:p></div></blockquote></blockquote><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><br class=""> James> The simple answer is "No", you can't in general tell at<br class=""> James> compile time whether code will be executed in parallel. (It<br class=""> James> could be in a separate compilation unit, or even a dynamic<br class=""> James> library which is only dlopened at runtime).<br class=""><br class="">Yes, this is why the OpenMP API provides functions like<br class="">int omp_in_parallel(void);<br class="">to test it.<br class=""><br class=""> James> Even without those practical examples, even knowing whether a<br class=""> James> given IR instruction will ever be executed is clearly the<br class=""> James> same as the halting problem...<br class=""><br class="">This is true but let's focus on the cases when we know it is not<br class="">intractable... :-)<br class=""><br class="">You can apply some interprocedural control flow analysis in the compiler<br class="">and in some cases be sure it is executed or not in parallel. Doing this<br class="">in the LTO phase is a way to go.<br class=""><br class="">Another more pragmatic way is to rewrite some code bloc B by cloning it<br class="">in the following way:<br class=""><br class="">if omp_in_parallel() {<br class=""> // We know that here B is executed in a parallel context<br class=""> B<br class="">}<br class="">else {<br class=""> // We know that here B is not executed in a parallel context<br class=""> B<br class="">}<br class="">and then go on with some optimizations on both paths.<br class=""><br class="">So this is a dynamic+static approach which may worth it if B is big enough.<br class=""><br class="">You may also use some partial evaluation late in the compilation phases<br class="">to figure out that in some case omp_in_parallel() returns always true or<br class="">false and then remove the dead code.<br class="">--<span class="Apple-converted-space"> </span><br class=""> Ronan KERYELL<br class="">_______________________________________________<br class="">Openmp-dev mailing list<br class=""><a href="mailto:Openmp-dev@dcs-maillist2.engr.illinois.edu" style="color: purple; text-decoration: underline;" class="">Openmp-dev@dcs-maillist2.engr.illinois.edu</a><br class=""><a href="http://lists.cs.uiuc.edu/mailman/listinfo/openmp-dev" style="color: purple; text-decoration: underline;" class="">http://lists.cs.uiuc.edu/mailman/listinfo/openmp-dev</a><o:p class=""></o:p></div></div></blockquote></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div></div></div><p style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">---------------------------------------------------------------------<br class="">Intel Corporation (UK) Limited<br class="">Registered No. 1134945 (England)<br class="">Registered Office: Pipers Way, Swindon SN3 1RJ<br class="">VAT No: 860 2173 47</p><p style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">This e-mail and any attachments may contain confidential material for<br class="">the sole use of the intended recipient(s). Any review or distribution<br class="">by others is strictly prohibited. If you are not the intended<br class="">recipient, please contact the sender and delete all copies.</p></div></blockquote></div><br class=""></div></body></html>