[llvm-dev] Multi-Threading Compilers

[Nicolai Hähnle via llvm-dev]

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.