> 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>
Doerfert, Johannes via llvm-dev
2020-Mar-25 07:52 UTC
[llvm-dev] Multi-Threading Compilers
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>
Possibly Parallel Threads
- Multi-Threading Compilers
- [cfe-dev] Create a BlockAddress array from LLVM Pass
- Create a BlockAddress array from LLVM Pass
- [LLVMdev] Crash on invalid during LLVMContext destruction MDNode::dropAllReferences
- [LLVMdev] How to extract the starting address of each basic block with llvm?