[llvm-dev] RFC: An Extension Mechanism for Parallel Compilers Based on LLVM

[Doerfert, Johannes Rudolf via llvm-dev]

Hi Jeff,

On 10/18, Jeffrey Sandoval via llvm-dev wrote:
> Has there been any thought about adopting a model that represents
> regions as outlined functions (similar to how OpenMP is represented
> today), but abstracts the "fork" call into a general LLVM intrinsic?
> I believe a lot or all of the same optimizations could be performed
> with this representation, though the analysis and transformations
> would necessarily be inter-procedural (and probably require writing
> new passes, rather than leveraging existing passes).  But, the main
> advantage is that it would be less invasive to the standard LLVM IR
> and infrastructure.
>
> Is there a middle ground, with first-class support for nested
> functions or lambdas?  This would allow outlining a region into a
> nested function or lambda.  Optimizations on this form would still
> require inter-procedural analysis and transformation, but it could be
> limited to a smaller scope (i.e., not an entire module, but perhaps a
> single function plus a set of nested functions or associated lambdas).

I have been looking into a way to enable "existing sequential
optimizations" with minimal overhead and a "soundness guarantee". There
have been multiple versions along the way but I think we have a solution
now that makes a lot of sense. I'll explain in the following what I
talked about at the LLVM-Dev'18 Meeting [0,1] and the LCPC'18 workshop
[2]. For some context on what we did before, and how we want to enable
parallel optimizations, see our EuroLLVM'18 Talk [3,4] and our IWOMP'18
paper [5].

When we want to "enable existing optimizations" we should keep in mind
that these are just optimizing sequential aspects of a program. They do
not know, nor do they need to know, about parallelism. They are not
applied today due to the "two levels of indirection" which we introduced
to guarantee a sound compilation in the presence of parallel semantics.

Let's say we want to keep the indirections for now but enable existing
optimizations in their presence. While intra-procedural optimizations
won't be applicable, we can enable inter-procedural optimizations. The
"only problem" is the runtime library call which hides the connection
between the call site (as well as the arguments) and the outlined
parallel function (and its parameters). To overcome this indirection we
introduced a "transitive call site" that exposes this connection
seamlessly through an interface which is a subset of the existing
CallSite abstraction. The transitive call site models the fact that the
runtime library will eventually call the outlined function and pass some
of its arguments along. In contrast to regular call sites, transitive
ones are partially defined. Thus, arguments of the actual call
instruction might not map to parameters of the transitively called
function. Similarly, not all parameters of the transitively called
function have corresponding arguments in the actual call instruction.

Note that transitive call sites have _nothing_ to do with parallelism.
They model a call that is performed by a "broker function" which is
called directly. As a consequence, transitive call sites can be reused
for other indirections that involve "function pointers", e.g., qsort in
C, or std::functions that are passed and called in C++.

I will push patches to phabricator in the next two weeks so everybody
can take a look and provide feedback. I'm happy to answer questions or
start a discussion before that already.

Cheers,
  Johannes


[0] https://llvm.org/devmtg/2018-10/talk-abstracts.html#talk20
[1] https://llvm.org/devmtg/2018-10/slides/Doerfert-Johannes-Optimizing-Indirections-Slides-LLVM-2018.pdf
[2] http://compilers.cs.uni-saarland.de/people/doerfert/par_opt_lcpc18.pdf
[3] http://llvm.org/devmtg/2018-04/slides/Finkel-Representing%20Parallelism%20Within%20LLVM.pdf
[4] https://www.youtube.com/watch?v=u2Soj49R-i4
[5] http://compilers.cs.uni-saarland.de/people/doerfert/par_opt18.pdf


-- 

Johannes Doerfert
Researcher

Argonne National Laboratory
Lemont, IL 60439, USA

jdoerfert at anl.gov
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 228 bytes
Desc: Digital signature
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20181025/de7c19b0/attachment-0001.sig>