[llvm-dev] Multi-Threading Compilers

[Florian Hahn via llvm-dev]

> On Mar 25, 2020, at 15:35, Nicolai Hähnle via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> On Wed, Mar 25, 2020 at 8:52 AM Doerfert, Johannes <jdoerfert at anl.gov <mailto: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?

I think one important observation is that most passes currently probably do not really care too much about use lists of various constants, beyond the bookkeeping required to maintain them.

We might be able to break the dependencies on GlobalValue without too much work directly as an IR transformation. I’ve not thought this completely through, but we might get away with a module pass that duplicate globals per function and replace all uses in a function with the copy per function before running a set of function passes. Then merge the duplicates again before running passes that inspect global uses. It is probably not an optimal solution, but it might shorten the path towards getting into a state where we can run function passes in parallel. It would also require making ConstantInt & co function-local, but both things could be implemented in parallel.

I think this thread explores the problem in quite a few directions very well. It might be worth summarizing the problems & possible solutions somewhere, e.g. the docs, to preserve them.

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