Knowing if an IR instruction will be executed by an OpenMP region

HI all,

is there a way to understand if an LLVM IR instruction will be executed by an OpenMP constructs?
If we have an OpenMP region the instructions within it will be placed in an “ompmicrotask” function,
however what if I call a function inside the OpenMP pragma? Is there a way to find out the instructions inside that function will be executed in parallel?

Thanks
Best,
Simone

is there a way to understand if an LLVM IR instruction will be executed by an OpenMP constructs?

The simple answer is "No", you can't in general tell at compile time whether code will be executed in parallel. (It could be in a separate compilation unit, or even a dynamic library which is only dlopened at runtime).

Even without those practical examples, even knowing whether a given IR instruction will ever be executed is clearly the same as the halting problem...

-- Jim

James Cownie <james.h.cownie@intel.com>
SSG/DPD/TCAR (Technical Computing, Analyzers and Runtimes)
Tel: +44 117 9071438

is there a way to understand if an LLVM IR instruction will be

    >> executed by an OpenMP constructs?

    > The simple answer is "No", you can't in general tell at
    > compile time whether code will be executed in parallel. (It
    > could be in a separate compilation unit, or even a dynamic
    > 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.

    > Even without those practical examples, even knowing whether a
    > given IR instruction will ever be executed is clearly the
    > same as the halting problem...

This is true but let's focus on the cases when we know it is not
intractable... :slight_smile:

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.

is there a way to understand if an LLVM IR instruction will be

    >> executed by an OpenMP constructs?

    > The simple answer is "No", you can't in general tell at
    > compile time whether code will be executed in parallel. (It
    > could be in a separate compilation unit, or even a dynamic
    > 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.

    > Even without those practical examples, even knowing whether a
    > given IR instruction will ever be executed is clearly the
    > same as the halting problem...

This is true but let's focus on the cases when we know it is not
intractable... :slight_smile:

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.

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)
do you think it could help?

Thanks.
Best,
Simone

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

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?

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@gmail.com
+1 (801) 696-8373

Thanks, that makes sense.