llvm dev - Mar 2020 - Multi-Threading Compilers

> On Mar 20, 2020, at 12:34 PM, Nicholas Krause <xerofoify at
gmail.com> wrote:
> 
>> 
>> The problem isn’t constants or functions themselves, it is that they
are instances of llvm::Value.  Everything that walks a use/def list would have
to run code that checks for this, and every call to inst->setOperand() would
have to do locking or conditional locking.  This would be a significant
across-the-board slowdown for the compiler even when globals and constants are
not involved.
>> 
>> -Chris
> 
> Hi Chris,
> 
> Thanks for the comments. Sure that may be true but I would prefer to get
real data to see how shared data actually looks. We can
> argue over it at a theoretical level. However with any real mutli-threading
of a code base, real data is required. I've not sure about
> setOperand() or other llvm:Value issues but real data is more my concern.
Sure it may turn out that is the case but I would prefer
> to have data as guessing with multi-threaded code in terms of
locking/scaling is always bad or even assuming issues.
I also love and endorse the collection of real data here!

-Chris

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200321/5fde2831/attachment.html>

On 3/21/20 11:29 AM, Chris Lattner wrote:
 >
 >
 >> On Mar 20, 2020, at 12:34 PM, Nicholas Krause <xerofoify at
gmail.com>
wrote:
 >>
 >>>
 >>> The problem isn’t constants or functions themselves, it is that
they
 >>> are instances of llvm::Value.  Everything that walks a use/def
list
 >>> would have to run code that checks for this, and every call to
 >>> inst->setOperand() would have to do locking or conditional
locking.
 >>> This would be a significant across-the-board slowdown for the
 >>> compiler even when globals and constants are not involved.
 >>>
 >>> -Chris
 >>
 >> Hi Chris,
 >>
 >> Thanks for the comments. Sure that may be true but I would prefer to 
get real data to see how shared data actually looks. We can
 >> argue over it at a theoretical level. However with any real 
mutli-threading of a code base, real data is required. I've not sure about
 >> setOperand() or other llvm:Value issues but real data is more my 
concern. Sure it may turn out that is the case but I would prefer
 >> to have data as guessing with multi-threaded code in terms of 
locking/scaling is always bad or even assuming issues.
 >
 > I also love and endorse the collection of real data here!

Right, actual data would be great.


I think the solution space for the value/use-list issue might be larger
than what was mentioned so far.


Some random thoughts:

If no pass ever walks the use list of a constant, except globals which
we could handle differently, we could get rid of their use-list or
overwrite their use-list interface functions to make them no-ops. We
could also do this kind of specialization in the Use class (I think).

When creating a constant we could provide the function in which the
constant is used. We have a ConstantExpr wrapper per function to make
the constants local (similar to what I understand the MLIR design is).
We would not get pointer comparison between constants used in different
functions but I suspect the places we need this we can specialize
accordingly.

We wouldn't need to lock every setOperand call but only the ones that
set a constant operand.



 > -Chris
 >
 >

On Wed, Mar 25, 2020 at 8:52 AM Doerfert, Johannes <jdoerfert at anl.gov>
wrote:
> I think the solution space for the value/use-list issue might be larger
> than what was mentioned so far.
>
>
> Some random thoughts:
>
> If no pass ever walks the use list of a constant, except globals which
> we could handle differently, we could get rid of their use-list or
> overwrite their use-list interface functions to make them no-ops. We
> could also do this kind of specialization in the Use class (I think).
Okay, let's actually think through how practical that is. The class
hierarchy is:

Value
- Argument
- BasicBlock
- InlineAsm (huh, why is that not a constant?)
- MetadataAsValue (+ children)
- User
-- Instruction (+ children)
-- Constant
--- ConstantData (undef, token none, literals)
--- ConstantAggregate (non-literal aggregates)
--- BlockAddress
--- ConstantExpr
--- GlobalValue (+ children)
-- Operator (utility / facade, i.e. not real)
-- DerivedUser (extension point used by MemorySSA)

It seems to me that the only points of this hierarchy that are
guaranteed to be function-local are Argument and Instruction.
Everything else could end up having uses from multiple functions
and/or initializers of globals. DerivedUser seems particularly special
-- but it's only used by MemorySSA, and that appears to be
function-local?

Of the values that can have global references to them, I believe that
most could just be immortal and without use lists. I'd say this
applies to:
- InlineAsm
- MetadataAsValue
- Constant other than GlobalValue

This leaves as values with global references that _cannot_ be immortal:
- GlobalValue (+ children)
- BasicBlock

And values that will have use lists, and only local references are:
- Argument
- Instruction

So the following does seem like a feasible minimal step forward:

1. Build a mechanism to break the use dependencies for GlobalValue and
BasicBlock, i.e. allow immortal BlockAddress and ConstantGlobalValue
values while _also_ allowing us to delete GlobalValues and
BasicBlocks.

For this mechanism, we can let ourselves be inspired by
mlir::SymbolRefAttr, which uses strings for the linkage.

Alternatively (and perhaps preferably), we could use a weak_ptr-like
mechanism. This can be very efficient, since each GlobalValue and
BasicBlock only ever needs to have a single instance of
ConstantGlobalValue and BlockAddress referring to it, respectively, so
a simple back-link is sufficient.

2. Change setOperand to only update use lists of Argument and
Instruction. All other use lists will always be empty -- no special
handling in the use list accessors is required, but we should place
assertions there to assert that use lists are not accidentally used on
other value types.

How does that sound for that start?

> When creating a constant we could provide the function in which the
> constant is used. We have a ConstantExpr wrapper per function to make
> the constants local (similar to what I understand the MLIR design is).
> We would not get pointer comparison between constants used in different
> functions but I suspect the places we need this we can specialize
> accordingly.
>
> We wouldn't need to lock every setOperand call but only the ones that
> set a constant operand.
MLIR distinguishes between "attributes" and "operations". So
you'd
define a constant by placing an operation (aka instruction) in each
function that has the actual constant as an attribute.
mlir::Attributes don't have use lists at all, so they're like
llvm::Metadata in that sense.

There is a certain elegance to having explicit instructions to import
constants into the llvm::Function context, but also ugliness, as IR
will then be full of "constant" instructions, unlike today. Plus,
changing all existing LLVM IR to have those is an enormous amount of
churn. I'm not totally opposed to doing this, but I'd lean towards
smaller, incremental steps.

Regardless, there are some related cleanups that seem like they would
be useful. For example, getting rid of llvm::ConstantExpr seems like a
very good idea to me, though somewhat orthogonal to the problem of
multi-threading. While we're at it, we could get rid of
llvm::ConstantAggregate and move llvm::Constant to no longer be an
llvm::User. This may impact how global value initializers work.

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

> On Mar 25, 2020, at 12:52 AM, Doerfert, Johannes <jdoerfert at
anl.gov> wrote:
> 
> 
> Some random thoughts:
> 
> If no pass ever walks the use list of a constant, except globals which
> we could handle differently, we could get rid of their use-list or
> overwrite their use-list interface functions to make them no-ops. 
This would be really problematic because it breaks orthogonality in the
compiler.  Today, you can walk the use-list of any operand to an instruction. 
This would be broken by this change, which would make it much easier to write
buggy/incorrect compiler code and passes.

-Chris

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200325/3d08c954/attachment-0001.html>