[Openmp-dev] Knowing if an IR instruction will be executed by an OpenMP region

[Simone Atzeni]

Hi Jim,

I have been working on a low-overhead data race detector for OpenMP programs (SC’14 LLLVM Workshop Paper <http://dl.acm.org/citation.cfm?id=2688369>, SC’14 Poster <http://sc14.supercomputing.org/sites/all/themes/sc14/files/archive/src_poster/src_poster_pages/spost128.html>).
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.
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
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).

Does it make sense?

Simone

Simone Atzeni
simone.at at gmail.com
+1 (801) 696-8373

> On Feb 11, 2015, at 10:21, Cownie, James H <james.h.cownie at intel.com> wrote:
> 
> Can you lift the level a little? <>
>  
> Why do you care whether an instruction is executed in a parallel region or not?
>  
> What higher-level problem are you trying to solve?
>  
> -- Jim
> 
> James Cownie <james.h.cownie at intel.com <mailto:james.h.cownie at intel.com>>
> SSG/DPD/TCAR (Technical Computing, Analyzers and Runtimes)
> Tel: +44 117 9071438
>  
> From: openmp-dev-bounces at cs.uiuc.edu [mailto:openmp-dev-bounces at cs.uiuc.edu] On Behalf Of Simone Atzeni
> Sent: Wednesday, February 11, 2015 5:15 PM
> To: Ronan KERYELL
> Cc: openmp-dev at dcs-maillist2.engr.illinois.edu
> Subject: Re: [Openmp-dev] Knowing if an IR instruction will be executed by an OpenMP region
>  
> Hi Ronan,
>  
> thanks for you answer.
> I think I will try to implement your first suggestion, some inter procedural control flow analysis.
> I would like to do it statically and not involving any dynamic analysis.
>  
> 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
> in parallel, if not I recursively check if its parent function is called inside an OpenMP construct and so on.
> In order to do this I was taking a look to llvm::CallGraph (http://llvm.org/docs/doxygen/html/classllvm_1_1CallGraph.html#details <http://llvm.org/docs/doxygen/html/classllvm_1_1CallGraph.html#details>) 
> do you think it could help?
>  
> Thanks.
> Best,
> Simone
>  
> Simone Atzeni
> simone.at at gmail.com <mailto:simone.at at gmail.com>
> +1 (801) 696-8373
>  
> On Feb 11, 2015, at 10:05, Ronan KERYELL <ronan-list at keryell.fr <mailto:ronan-list at keryell.fr>> wrote:
>  
> On Tue, 10 Feb 2015 11:19:39 +0000, "Cownie, James H" <james.h.cownie at intel.com <mailto:james.h.cownie at intel.com>> said:
> 
> 
> is there a way to understand if an LLVM IR instruction will be
> executed by an OpenMP constructs?
> 
>    James> The simple answer is "No", you can't in general tell at
>    James> compile time whether code will be executed in parallel. (It
>    James> could be in a separate compilation unit, or even a dynamic
>    James> library which is only dlopened at runtime).
> 
> Yes, this is why the OpenMP API provides functions like
> int omp_in_parallel(void);
> to test it.
> 
>    James> Even without those practical examples, even knowing whether a
>    James> given IR instruction will ever be executed is clearly the
>    James> same as the halting problem...
> 
> This is true but let's focus on the cases when we know it is not
> intractable... :-)
> 
> You can apply some interprocedural control flow analysis in the compiler
> and in some cases be sure it is executed or not in parallel. Doing this
> in the LTO phase is a way to go.
> 
> Another more pragmatic way is to rewrite some code bloc B by cloning it
> in the following way:
> 
> if omp_in_parallel() {
>  // We know that here B is executed in a parallel context
>  B
> }
> else {
>  // We know that here B is not executed in a parallel context
>  B
> }
> and then go on with some optimizations on both paths.
> 
> So this is a dynamic+static approach which may worth it if B is big enough.
> 
> You may also use some partial evaluation late in the compilation phases
> to figure out that in some case omp_in_parallel() returns always true or
> false and then remove the dead code.
> -- 
>  Ronan KERYELL
> _______________________________________________
> Openmp-dev mailing list
> Openmp-dev at dcs-maillist2.engr.illinois.edu <mailto:Openmp-dev at dcs-maillist2.engr.illinois.edu>
> http://lists.cs.uiuc.edu/mailman/listinfo/openmp-dev <http://lists.cs.uiuc.edu/mailman/listinfo/openmp-dev>
>  
> ---------------------------------------------------------------------
> Intel Corporation (UK) Limited
> Registered No. 1134945 (England)
> Registered Office: Pipers Way, Swindon SN3 1RJ
> VAT No: 860 2173 47
> 
> This e-mail and any attachments may contain confidential material for
> the sole use of the intended recipient(s). Any review or distribution
> by others is strictly prohibited. If you are not the intended
> recipient, please contact the sender and delete all copies.
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/openmp-dev/attachments/20150211/c851b56e/attachment.html>