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.
Doerfert, Johannes via llvm-dev
2020-Mar-25 16:10 UTC
[llvm-dev] Multi-Threading Compilers
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
> 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>
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>
> On Mar 25, 2020, at 8:35 AM, Nicolai Hähnle <nhaehnle at gmail.com> wrote: > > > 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.FWIW, the Swift SIL IR does the same thing - it uses “integer_literal” instructions to materialize constants. In addition to the multithreading benefits explored in this thread, this also allows carrying location information more correctly. This is important for source level analysis tools, debugging etc.> 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.Yes, it increases verbosity of the IR this is very true. In practice, it is not a problem though.> 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.I would love to kill off ConstantExpr. It is a huge design wart: for example the fact that we have constantexpr “divide” instructions means that constants “canTrap()” which leads to all sorts of problems. A much better design (ignoring the multithreading concerns) would be to make scalar constants be llvm::Constant’s, keep aggregate constants but only allow them in global variables, and introduce a new ConstantExpr like class which represents a linker-relocatable expressions like “symbol+constant” and “symbol1-symbol2+constant” on Darwin. -Chris -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200325/b598f062/attachment.html>