On Mar 25, 2020, at 4:14 PM, Doerfert, Johannes <jdoerfert at anl.gov> wrote:> >> Today, you can walk the use-list of any operand to an instruction. >> This would be broken by this change, > > First, you would be able to walk the use-list of any operand. So nothing > breaks just yet.If I understand correctly, you are suggesting that you can walk it, but you don’t get all the uses. This is extremely dangerous, it would be better to abort.>> which would make it much easier to write buggy/incorrect compiler code >> and passes. > > I argued (implicitly) above that the uses of a Constant[Int/Float/...] > are really not interesting if no-one ever walks them.There is a difference between “no one ever walks them in practice” and “no one can walk them. :-)> Let's assume you > walk the uses and we "removed" the use list so there are none, what does > that mean. I'd say, nothing much. If you inspect the Value and see it's > a Constant you have to assume it has Aliases that denote the same value > so direct uses are not really interesting anyway. If you inspect further > and see ConstantInt/Float/... you can deal with the missing use list. If > you don't inspect the Value you cannot really make much of an empty use > list, or can you? I doubt we ever call RAUW on a ConstantInt/Float/... > > Feel free to elaborate on your concerns.Have you tested your thesis that no one walks the use-def chains? You could just add an assertion to the compiler (the methods like use_begin() hasOneUse() etc), that aborts on constants, then run the test suite. -Chris
Doerfert, Johannes via llvm-dev
2020-Mar-26 00:14 UTC
[llvm-dev] Multi-Threading Compilers
On 3/25/20 6:47 PM, Chris Lattner wrote: > On Mar 25, 2020, at 4:14 PM, Doerfert, Johannes <jdoerfert at anl.gov> wrote: >> >>> Today, you can walk the use-list of any operand to an instruction. >>> This would be broken by this change, >> >> First, you would be able to walk the use-list of any operand. So nothing >> breaks just yet. > > If I understand correctly, you are suggesting that you can walk it, > but you don’t get all the uses. This is extremely dangerous, it would > be better to abort. Correct, that is what I suggested. >>> which would make it much easier to write buggy/incorrect compiler code >>> and passes. >> >> I argued (implicitly) above that the uses of a Constant[Int/Float/...] >> are really not interesting if no-one ever walks them. > > There is a difference between “no one ever walks them in practice” and > “no one can walk them. :-) Sure. That is why I argued below walking the incomplete list is not a problem. At leas I'm not aware of a problem yet. >> Let's assume you >> walk the uses and we "removed" the use list so there are none, what does >> that mean. I'd say, nothing much. If you inspect the Value and see it's >> a Constant you have to assume it has Aliases that denote the same value >> so direct uses are not really interesting anyway. If you inspect further >> and see ConstantInt/Float/... you can deal with the missing use list. If >> you don't inspect the Value you cannot really make much of an empty use >> list, or can you? I doubt we ever call RAUW on a ConstantInt/Float/... >> >> Feel free to elaborate on your concerns. > > > Have you tested your thesis that no one walks the use-def chains? You > could just add an assertion to the compiler (the methods like > use_begin() hasOneUse() etc), that aborts on constants, then run the > test suite. That is what I suggested a few emails back. However, I never said it is safe because no one walks it but what I suggested is that it will actually not impact much if we don't remember the uses of Constants (except globals). > -Chris >
> On Mar 25, 2020, at 5:14 PM, Doerfert, Johannes <jdoerfert at anl.gov> wrote: > >>> Let's assume you >>> walk the uses and we "removed" the use list so there are none, what does >>> that mean. I'd say, nothing much. If you inspect the Value and see it's >>> a Constant you have to assume it has Aliases that denote the same value >>> so direct uses are not really interesting anyway. If you inspect further >>> and see ConstantInt/Float/... you can deal with the missing use list. If >>> you don't inspect the Value you cannot really make much of an empty use >>> list, or can you? I doubt we ever call RAUW on a ConstantInt/Float/... >>> >>> Feel free to elaborate on your concerns. >> >> >> Have you tested your thesis that no one walks the use-def chains? You >> could just add an assertion to the compiler (the methods like >> use_begin() hasOneUse() etc), that aborts on constants, then run the >> test suite. > > That is what I suggested a few emails back. However, I never said it is > safe because no one walks it but what I suggested is that it will > actually not impact much if we don't remember the uses of Constants > (except globals).Sure, I was just curious what you base that opinion on. Have you done an experiment? -Chris -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200325/45c17b14/attachment-0001.html>
On Wed, Mar 25, 2020 at 5:26 PM Florian Hahn <florian_hahn at apple.com> wrote:> 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.Agreed, though as Chris points out it's something that can and should be tested experimentally fairly easily.> 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.That feels like a really awkward hack :( Now you have to keep track of whether the IR is currently in the state where function pass parallelization is okay or not, which seems rather fragile. It also doesn't solve the problem of Functions themselves -- those are also GlobalValues... On Thu, Mar 26, 2020 at 12:47 AM Chris Lattner <clattner at nondot.org> wrote:> > 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.Okay, it seems like it could be a viable long-term goal to do this. What I'm trying to figure out is how to incrementally evolve LLVM IR, and it feels like this change to enable "constant materialization instructions" is extremely invasive in terms of churn in the code base on a level comparable to opaque pointers -- and it's not strictly necessary for the goal of multi-threading. I'm just trying to be pragmatic here. [snip]> On Mar 25, 2020, at 4:14 PM, Doerfert, Johannes <jdoerfert at anl.gov> wrote: > > > >> Today, you can walk the use-list of any operand to an instruction. > >> This would be broken by this change, > > > > First, you would be able to walk the use-list of any operand. So nothing > > breaks just yet. > > If I understand correctly, you are suggesting that you can walk it, but you don’t get all the uses. This is extremely dangerous, it would be better to abort.Agreed.> >> which would make it much easier to write buggy/incorrect compiler code > >> and passes. > > > > I argued (implicitly) above that the uses of a Constant[Int/Float/...] > > are really not interesting if no-one ever walks them. > > There is a difference between “no one ever walks them in practice” and “no one can walk them. :-)Yes, but you've got to ask yourself: what's the point of walking the use list of a scalar constant? It feels like code that would do that is quite likely broken to begin with and should probably abort already today... which is exactly the experiment that you suggest below, and I agree that doing this experiment would be a useful step in all this :) Cheers, Nicolai -- Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.
> On Mar 26, 2020, at 10:19, Nicolai Hähnle via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > On Wed, Mar 25, 2020 at 5:26 PM Florian Hahn <florian_hahn at apple.com> wrote: >> 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. > > Agreed, though as Chris points out it's something that can and should > be tested experimentally fairly easily. > > >> 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. > > That feels like a really awkward hack :( >> Now you have to keep track of whether the IR is currently in the state > where function pass parallelization is okay or not, which seems rather > fragile. >Agreed, it is not production solution. I think it was not really clear from my previous mail, but I see it mostly as a relatively cheap approach (in terms of work required to get it working) to try to get to a state where we can run experiments with function passes in parallel and get a better idea of the benefit and turn up other issues.> It also doesn't solve the problem of Functions themselves -- those are > also GlobalValues…I am not sure why not. Function passes should only rely on the information at the callsite & from the declaration IIRC. For functions, we coulkd add extra declarations and update the call sites. But I might be missing something. Cheers, Florian
On Thu, Mar 26, 2020 at 11:19 AM Nicolai Hähnle <nhaehnle at gmail.com> wrote:> On Thu, Mar 26, 2020 at 12:47 AM Chris Lattner <clattner at nondot.org> wrote: > > > 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. > > Okay, it seems like it could be a viable long-term goal to do this. > What I'm trying to figure out is how to incrementally evolve LLVM IR, > and it feels like this change to enable "constant materialization > instructions" is extremely invasive in terms of churn in the code base > on a level comparable to opaque pointers -- and it's not strictly > necessary for the goal of multi-threading. I'm just trying to be > pragmatic here.I feel like I should clarify this after thinking a bit more about this. It sounds like "constant materialization instructions" are a useful feature to have for better location information (for diagnostics and debug info). And _introducing_ constant materialization instructions should be quite feasible to do incrementally. For example, if Clang or some other frontend sees a use case for adding those in order to do more work in IR rather than on the AST, then that should be supportable. The thing that I think is "extremely invasive in terms of churn in the code base" is making constant materialization instructions the _only_ representation of constants inside a function. Which means that this path is not very viable if your goal is to enable multi-threaded compilation. However, if your goal is to move towards constant materialization instructions for the other benefits that they can bring, then there is an incremental path available that can quickly bring you gains - something along the lines of: 1. The initial MVP: Introduce constant materialization instructions as a concept. Add a switch to the Builder so that constants are optionally emitted as materialization instructions, start using that switch in at least one frontend, add/convert some initial passes to make use of them, and add a very simple pass that strips them out again for the remainder of the compilation pipeline. 2. Teach an increasing number of passes, analyses, matching infrastructure, etc. about the constant materialization instructions. 3. Eventually, get to the point where the pass that strips them out can be removed. Somewhere around that time, we can make the Builder unconditionally emit them everywhere. 4. Flip the switch that starts aborting when old-style Constants are used instead. 5. Cleanup any remains of old constant support e.g. in the matching infrastructure. This seems viable, but very much a marathon and not a sprint, and I feel that this is going away a bit from the topic of multi-threading :) Cheers, Nicolai -- Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.
> On Thu, Mar 26, 2020 at 12:47 AM Chris Lattner <clattner at nondot.org> wrote: >>> 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. > > Okay, it seems like it could be a viable long-term goal to do this. > What I'm trying to figure out is how to incrementally evolve LLVM IR, > and it feels like this change to enable "constant materialization > instructions" is extremely invasive in terms of churn in the code base > on a level comparable to opaque pointers -- and it's not strictly > necessary for the goal of multi-threading. I'm just trying to be > pragmatic here.What if we modeled constants as implicit arguments to functions rather than introducing a constant materialization instruction? That would solve the problem of making their use lists function local, while avoiding some of the unnecessary complexity introduced by materialization functions (de-duplication, code placement, etc.). --Owen