[LLVMdev] LLVM Parallel IR

[Kevin Streit]

Hi William,

A similar discussion has recently been started on this list by a grad
student of MIT (The student was Lefteris Ioannidis and the discussion
titled "LLVM parallel annotations"). So you might also participate in
that discussion.

I am working on automatic parallelization in LLVM and have frequently
come to the point during my research that I wished I had started with
discussing and implementing a parallel extension of LLVM IR.
Unfortunately I did not, or at least not in a way it should be
implemented. So I am happy to hear that someone plans to work on this.

As you might be aware of there is already a representation for
parallel loops in LLVM IR. This representation is basically based on
metadata being added to both the loop (llvm.loop <id>) and
all memory accesses within that loop (llvm.mem.parallel_loop_access
<id>) which are safe. The loop with id <id> can then be executed in
parallel (i.e., every iteration thereof) provided all potential memory
accesses it contains carry a corresponding mark with the same id.
Optimizations which are not aware of the parallelism thus potentially
break it, but the result would be sequential execution, which is at
least sound.

You will find details and discussions about those annotations in the
archives of this list and in the sources (e.g., LoopInfo)

Although I understand why such a minimally invasive approach to
parallelism in the IR is desired for most use cases, I think that
parallelism is invasive by nature and would have to influence most
optimizations. During my PhD work I always wished for a completely
parallel IR with all analyses and transformations being aware of
parallelism at least those that have to be. Such an IR would be usable
as the target for parallel source languages like Cilk(+), OpenMP, or
simply for automatic parallelization.

For that however, it would have to be able to express parallelism not
only for loops. Instead, one should also be able to "fork" arbitrary
code regions for parallel execution. Think, a cilk spawn.

I think it should be possible to come up with a minimal, clearly
defined set of parallelism constructs in the IR. The goal should be to
be able to map the most important forms of parallelism to these
constructs. Completely parallel loops (DOALL loops) are just one form.
A first guide might be OpenMP constructs, including parallel sections
and tasks.

I'd be interested in hearing more details about your ideas in that direction.

Cheers,

---

Kevin Streit
Neugäßchen 2
66111 Saarbrücken

Tel. +49 (0)151 23003245
streit at mailbox.org · http://www.kevinstreit.de

> On March 9, 2015 at 4:58 PM William Moses <wmoses at csail.mit.edu> wrote:
> 
> 
> I'm part of a research group at MIT looking to create an extension of LLVM
> that inherently allows one to nicely code a parallel loop.
> 
> Most parallel frameworks tend to take the body of a parallel loop and stick
> it inside of a function for the parallel runtime to call when appropriate.
> However, this makes optimizations significantly more difficult as most
> compiler optimizations tend to be intraprocedural. The goal of this
> parallel IR is to allow LLVM to more easily optimize parallel code -- which
> often gets the short end of the optimization stick.
> 
> Long story short: I was wondering if anyone in the LLVM community has
> already begun a similar project or knows of something that begins to
> accomplish this.
> 
> Additionally, does anyone who has worked with parallelism in LLVM have any
> specific comments or suggestions regarding this project.
> 
> Sincerely,
> William Moses
> MIT Computer Science and Artificial Intelligence Laboratory
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev