[llvm-dev] Multi-Threading Compilers

[Doerfert, Johannes via llvm-dev]

On 3/25/20 10:35 AM, Nicolai Hähnle wrote:
 > 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?

Much better than my random though and reasonable to me. Let's verify the
assumptions about use list usage first though. (We probably also need to
allow iterating the emtpy use lists of constants in case your assertion
comment was target to prevent this.)


 >> 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.

You should ask for feedback on this in an explicit thread.

Cheers,
   Johannes