[llvm-dev] Multi-Threading Compilers

Wed Mar 25 12:14:57 PDT 2020

On 3/25/20 12:25 PM, Florian Hahn via llvm-dev wrote:
>
>
>> On Mar 25, 2020, at 15:35, Nicolai Hähnle via llvm-dev 
>> <llvm-dev at lists.llvm.org <mailto: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
>
I don't have access to the wiki for writing but I'm taking notes on what 
should  be added as I read the thread. :) Probably the holy grail
for multi threading a compiler is to make the pass manager async. I 
tried for months on the GCC side to figure that out by reading
the code e.t.c., its almost impossible it seems without IR level state 
detection.

Frankly I gave up on that but if people are curious its a issue of IPO 
between passes and pass reordering issues,

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/20200325/723ddfd7/attachment.html>