llvm dev - Mar 2020 - Reach Out about Module Infrastructure Multi-Threading

On 3/17/20 6:16 PM, Johannes Doerfert wrote:
> Hey,
>
> Apologies for the wait, everything right now is going crazy..
Compiler Folks are very busy people as there aren't as much of us 
unfortunately so no need to
apologize. I've yet to heard from someone on the GCC side and will wait 
until after GCC 11
is released due to this. Also not to mention the health issues of 
Coronavirus-19.
>
> I think we should early in move this conversation on the llvm Dev list 
> but generally speaking we can see three options here:
> 1) parallelize single passes or a subset of passes that are known to 
> not interfer, e.g. the attributor,
> 2) parallelize analysis pass execution before a transformation that 
> needs them,
> 3) investigate what needs to be done for a parallel execution of many 
> passes, e.g. How can we avoid races on shared structure such as the 
> constant pool.
I was researching this on and off for the last few months in terms of 
figuring out how to make the pass manager itself async. Its not easy and 
I'm not even
sure if that's possible. Not sure about GIMPLE as I would have to ask 
the middle end maintainer on the GCC side but LLVM IR does not seem to 
have shared
state detection or the core classes and same for the back ends. So yes 
this would interest me.

The first place to start with is which data structures are shared for 
sure. The biggest ones seem to be basic blocks and function definitions 
in terms of shared state, as
those would be shared by passes running on each function.  We should 
start looking at implementing here locks or ref counting here first if 
your OK with that.
It also allows me  to understand a little more concrete the linkage 
between the core classes as would be required for multi threading LLVM. 
In addition,
it allows us to look into partitioning issues with threads at the same 
thing in terms of how to do it.

If others want to chip it as I've CCed the list, that's fine as well and
this should be up for discussion with the whole community.

I've given up on the idea of a async pass manager as it seems to require 
IR level detection of changed state between passes but maybe I'm wrong,

Nick
>
> What sounds interesting to you?
>
> Cheers,
>   Johannes
>
>
>
> On Tue, Mar 17, 2020, 08:09 Nicholas Krause <xerofoify at gmail.com 
> <mailto:xerofoify at gmail.com>> wrote:
>
>     Johanne,
>
>     I'm assuming you've been busy as so have I am so I'm
pinging this
>     email.
>
>     Nick
>
>     On 3/6/20 7:57 PM, Nicholas Krause wrote:
>     > Greetings Johannes,
>     >
>     > I'm pinging you as you wanted to discuss the ModulePass and
related
>     > infrastructure in terms of
>     > making it either multi-threading or preparing for that. You
>     stated to
>     > wait to this week so now
>     > seems a good time.
>     >
>     >
>     > Regards,
>     > Nick
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200318/b5f5b5a9/attachment.html>

(this thread seems to have been split from the original thread in gmail at
least - which might make it hard to keep track of the context)

Ah, it was a different thread:
http://lists.llvm.org/pipermail/llvm-dev/2020-March/139606.html - might be
best to pick up from that thread instead of starting a new one.

On Tue, Mar 17, 2020 at 9:07 PM Nicholas Krause via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
>
> On 3/17/20 6:16 PM, Johannes Doerfert wrote:
>
> Hey,
>
> Apologies for the wait, everything right now is going crazy..
>
> Compiler Folks are very busy people as there aren't as much of us
> unfortunately so no need to
> apologize. I've yet to heard from someone on the GCC side and will wait
> until after GCC 11
> is released due to this. Also not to mention the health issues of
> Coronavirus-19.
>
>
> I think we should early in move this conversation on the llvm Dev list but
> generally speaking we can see three options here:
> 1) parallelize single passes or a subset of passes that are known to not
> interfer, e.g. the attributor,
> 2) parallelize analysis pass execution before a transformation that needs
> them,
>
> 3) investigate what needs to be done for a parallel execution of many
> passes, e.g. How can we avoid races on shared structure such as the
> constant pool.
>
> I was researching this on and off for the last few months in terms of
> figuring out how to make the pass manager itself async. Its not easy and
> I'm not even
> sure if that's possible. Not sure about GIMPLE as I would have to ask
the
> middle end maintainer on the GCC side but LLVM IR does not seem to have
> shared
> state detection or the core classes and same for the back ends. So yes
> this would interest me.
>
> The first place to start with is which data structures are shared for
> sure. The biggest ones seem to be basic blocks and function definitions in
> terms of shared state, as
> those would be shared by passes running on each function.  We should start
> looking at implementing here locks or ref counting here first if your OK
> with that.
> It also allows me  to understand a little more concrete the linkage
> between the core classes as would be required for multi threading LLVM. In
> addition,
> it allows us to look into partitioning issues with threads at the same
> thing in terms of how to do it.
>
As was discussed on the previous thread - generally the assumption is that
one wouldn't try to run two function optimizations on the same function at
the same time, but, for instance - run function optimizations on unrelated
functions at the same time (or CGSCC passes on distinct CGSCCs). But this
is difficult in LLVM IR because use lists are shared - so if two functions
use the same global variable or call the same 3rd function, optimizing out
a function call from each of those functions becomes a write to shared
state when trying to update the use list of that 3rd function. MLIR
apparently has a different design in this regard that is intended to be
more amenable to these situations.

>
> If others want to chip it as I've CCed the list, that's fine as
well and
> this should be up for discussion with the whole community.
>
> I've given up on the idea of a async pass manager as it seems to
require
> IR level detection of changed state between passes but maybe I'm wrong,
>
> Nick
>
>
> What sounds interesting to you?
>
> Cheers,
>   Johannes
>
>
>
> On Tue, Mar 17, 2020, 08:09 Nicholas Krause <xerofoify at gmail.com>
wrote:
>
>> Johanne,
>>
>> I'm assuming you've been busy as so have I am so I'm
pinging this email.
>>
>> Nick
>>
>> On 3/6/20 7:57 PM, Nicholas Krause wrote:
>> > Greetings Johannes,
>> >
>> > I'm pinging you as you wanted to discuss the ModulePass and
related
>> > infrastructure in terms of
>> > making it either multi-threading or preparing for that. You stated
to
>> > wait to this week so now
>> > seems a good time.
>> >
>> >
>> > Regards,
>> > Nick
>>
>>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200317/019ed1f8/attachment.html>

Hi Nick,

On Wed, Mar 18, 2020 at 5:07 AM Nicholas Krause via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> I was researching this on and off for the last few months in terms of
figuring out how to make the pass manager itself async. Its not easy and I'm
not even
> sure if that's possible. Not sure about GIMPLE as I would have to ask
the middle end maintainer on the GCC side but LLVM IR does not seem to have
shared
> state detection or the core classes and same for the back ends. So yes this
would interest me.
>
> The first place to start with is which data structures are shared for sure.
The biggest ones seem to be basic blocks and function definitions in terms of
shared state, as
> those would be shared by passes running on each function.  We should start
looking at implementing here locks or ref counting here first if your OK with
that.
> It also allows me  to understand a little more concrete the linkage between
the core classes as would be required for multi threading LLVM. In addition,
> it allows us to look into partitioning issues with threads at the same
thing in terms of how to do it.
I think it's great that you're looking into this!

As David already mentioned, the gnarliest immediate issue is that
constant values (which includes global variables and functions) track
uses via a linked list. So in the current design, being able to do
concurrent transformations within the same LLVMContext would require
taking a lock whenever a use of a constant is added or removed. That's
obviously too much overhead.

So one of the first steps you'd have to do would be to change that.
That may seem a bit daunting initially, but it's feasible and seems
like a good idea to evolve LLVM IR in the direction of what MLIR does
here.

Cheers,
Nicolai


>
> If others want to chip it as I've CCed the list, that's fine as
well and this should be up for discussion with the whole community.
>
> I've given up on the idea of a async pass manager as it seems to
require IR level detection of changed state between passes but maybe I'm
wrong,
>
> Nick
>
>
> What sounds interesting to you?
>
> Cheers,
>   Johannes
>
>
>
> On Tue, Mar 17, 2020, 08:09 Nicholas Krause <xerofoify at gmail.com>
wrote:
>>
>> Johanne,
>>
>> I'm assuming you've been busy as so have I am so I'm
pinging this email.
>>
>> Nick
>>
>> On 3/6/20 7:57 PM, Nicholas Krause wrote:
>> > Greetings Johannes,
>> >
>> > I'm pinging you as you wanted to discuss the ModulePass and
related
>> > infrastructure in terms of
>> > making it either multi-threading or preparing for that. You stated
to
>> > wait to this week so now
>> > seems a good time.
>> >
>> >
>> > Regards,
>> > Nick
>>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


-- 
Lerne, wie die Welt wirklich ist,
aber vergiss niemals, wie sie sein sollte.