On Oct 10, 2013, at 8:53 PM, Daniel Berlin <dberlin at dberlin.org> wrote:> > > > On Thu, Oct 10, 2013 at 10:34 AM, Chris Lattner <clattner at apple.com> wrote: > On Oct 7, 2013, at 11:49 PM, Daniel Berlin <dberlin at dberlin.org> wrote: >> >> Hence it’s more meaningful to reason about TBAA in terms of its semantics rather than hypothesizing about how and why someone would produce it. >> >> That would be great, but it's not what the langref says, nor does it match up with the name of the thing you are creating, nor does it necessarily have optimal semantics, nor would it be great for future producers or the ability to do other analyses in those producers. > > Hey Daniel, > > Can you be more specific about your concerns here? It's true that we describe the TBAA nodes in terms of expression C-like type constraints, but the intention of the design has always been for it to be more general. > > Specifically, partitioning the heap for use-cases like what Phil is doing with Javascript was factored into the original design. We have even talked about adding type tags to represent C++ vtables (for example) since language loads and stores can't touch them (not even through char*). > > The datastructures and algorithms we have are powerful enough to express these sorts of things, and so long as a frontend abided by the rules, there shouldn't be a problem. > > > My concerns are simply that whether designed this way or not, it ends up fairly inconsistent. > > For example, what would the plan be when a frontend does something like clang does now for C/C++ (generate type based TBAA), and also wants to do something like Filip is suggesting (which is also doable on C/C++ with simple frontend analysis)? > > Generate a split tree of some sort, one side of which represents TBAA info, and the other side which represents partitioned abstract heaps?[1] > It seems like that would be awfully confusing. > > However, it would now be necessary in order to use the new tbaa.read/tbaa.write metadata,, since they will only reference tbaa tags. But they only make a lot of sense on tbaa tags that point to partitioned heaps like filip's, so if you did want to actually to make use of them, you now have to put both the type info and the heap info in the same tree. > > You also run into issues with the existing metadata on loads/stores in this situation. It's again, entirely possible for a load to conflict with both a tbaa type, and a partitioned heap. In Filip's scheme, there is no way to represent this. > > Because of this, the only thing I essentially asked Filip to do was not place it in the same exact tree as we are currently putting type info into. > > Then your heap.read/heap.write metadata works with the heap tree (and you annotate loads/stores with your heap attributes), and your tbaa attributes work on the tbaa tree. You can tag a load/store with both a heap tag and a tbaa tag, and disambiguate based on both of them. > > Now, if the consensus is this is still a good idea, great. My suggestion would then be to update langref, rename the attributes, etc, to make this all more clear. > > --Dan > [1] The other option of trying to generate some fake set of heaps that accurately represent the conflicts in both is, well, difficult :) > _______________________________________________JSC is able to make better use of the original TBAA design by encoding the access path within the type itself. Roughly: JSCType->Class->Field/Index This is what we're doing with C++ struct-path TBAA now, but simpler because only one access path is legal. JSC does need a hierarchical representation which makes TBAA a perfect fit. The only decision point to make now is whether to allow current TBAA to apply to calls. That seems entirely consistent with LLVM's approach to memory disambiguation. I do think this discussion is interesting and useful with respect to adding different styles of alias analysis in the future, but we are way beyond the scope of the RFC. -Andy -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131010/4c82e7a9/attachment.html>
On Thu, Oct 10, 2013 at 9:56 PM, Andrew Trick <atrick at apple.com> wrote:> > On Oct 10, 2013, at 8:53 PM, Daniel Berlin <dberlin at dberlin.org> wrote: > > > > > On Thu, Oct 10, 2013 at 10:34 AM, Chris Lattner <clattner at apple.com>wrote: > >> On Oct 7, 2013, at 11:49 PM, Daniel Berlin <dberlin at dberlin.org> wrote: >> >> >>> Hence it’s more meaningful to reason about TBAA in terms of its >>> semantics rather than hypothesizing about how and why someone would produce >>> it. >>> >> >> That would be great, but it's not what the langref says, nor does it >> match up with the name of the thing you are creating, nor does it >> necessarily have optimal semantics, nor would it be great for future >> producers or the ability to do other analyses in those producers. >> >> >> Hey Daniel, >> >> Can you be more specific about your concerns here? It's true that we >> describe the TBAA nodes in terms of expression C-like type constraints, but >> the intention of the design has always been for it to be more general. >> > >> Specifically, partitioning the heap for use-cases like what Phil is doing >> with Javascript was factored into the original design. We have even talked >> about adding type tags to represent C++ vtables (for example) since >> language loads and stores can't touch them (not even through char*). >> >> The datastructures and algorithms we have are powerful enough to express >> these sorts of things, and so long as a frontend abided by the rules, there >> shouldn't be a problem. >> > > > My concerns are simply that whether designed this way or not, it ends up > fairly inconsistent. > > For example, what would the plan be when a frontend does something like > clang does now for C/C++ (generate type based TBAA), and also wants to do > something like Filip is suggesting (which is also doable on C/C++ with > simple frontend analysis)? > > Generate a split tree of some sort, one side of which represents TBAA > info, and the other side which represents partitioned abstract heaps?[1] > It seems like that would be awfully confusing. > > However, it would now be necessary in order to use the new > tbaa.read/tbaa.write metadata,, since they will only reference tbaa tags. > But they only make a lot of sense on tbaa tags that point to partitioned > heaps like filip's, so if you did want to actually to make use of them, you > now have to put both the type info and the heap info in the same tree. > > You also run into issues with the existing metadata on loads/stores in > this situation. It's again, entirely possible for a load to conflict with > both a tbaa type, and a partitioned heap. In Filip's scheme, there is no > way to represent this. > > Because of this, the only thing I essentially asked Filip to do was not > place it in the same exact tree as we are currently putting type info into. > > Then your heap.read/heap.write metadata works with the heap tree (and you > annotate loads/stores with your heap attributes), and your tbaa attributes > work on the tbaa tree. You can tag a load/store with both a heap tag and a > tbaa tag, and disambiguate based on both of them. > > Now, if the consensus is this is still a good idea, great. My suggestion > would then be to update langref, rename the attributes, etc, to make this > all more clear. > > --Dan > [1] The other option of trying to generate some fake set of heaps that > accurately represent the conflicts in both is, well, difficult :) > _______________________________________________ > > > JSC is able to make better use of the original TBAA design by encoding the > access path within the type itself. Roughly: > > JSCType->Class->Field/Index > > This is what we're doing with C++ struct-path TBAA now, but simpler > because only one access path is legal. > > JSC does need a hierarchical representation which makes TBAA a perfect fit. > > The only decision point to make now is whether to allow current TBAA to > apply to calls. That seems entirely consistent with LLVM's approach to > memory disambiguation. > > I do think this discussion is interesting and useful with respect to > adding different styles of alias analysis in the future, but we are way > beyond the scope of the RFC. >I again, respectfully disagree. What I am suggesting is not a massive change. He already has to add attributes to various instructions. Renaming those adds no additional work. The only additional work is adding a new tag for loads/stores. Work was just recently completed to do the same, and it was, AFAIK, not a huge undertaking.> > -Andy > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131011/15ea7227/attachment.html>
BTW, in any case, can we at least agree that updating the langref and comments all over the codebase that specify the tbaa tree is tied strictly to type hierarchy rules should be in scope to be updated to talk about an abstract heap hiearchy (with traditional type based as an example) instead? On Fri, Oct 11, 2013 at 12:17 AM, Daniel Berlin <dberlin at dberlin.org> wrote:> > > > On Thu, Oct 10, 2013 at 9:56 PM, Andrew Trick <atrick at apple.com> wrote: > >> >> On Oct 10, 2013, at 8:53 PM, Daniel Berlin <dberlin at dberlin.org> wrote: >> >> >> >> >> On Thu, Oct 10, 2013 at 10:34 AM, Chris Lattner <clattner at apple.com>wrote: >> >>> On Oct 7, 2013, at 11:49 PM, Daniel Berlin <dberlin at dberlin.org> wrote: >>> >>> >>>> Hence it’s more meaningful to reason about TBAA in terms of its >>>> semantics rather than hypothesizing about how and why someone would produce >>>> it. >>>> >>> >>> That would be great, but it's not what the langref says, nor does it >>> match up with the name of the thing you are creating, nor does it >>> necessarily have optimal semantics, nor would it be great for future >>> producers or the ability to do other analyses in those producers. >>> >>> >>> Hey Daniel, >>> >>> Can you be more specific about your concerns here? It's true that we >>> describe the TBAA nodes in terms of expression C-like type constraints, but >>> the intention of the design has always been for it to be more general. >>> >> >>> Specifically, partitioning the heap for use-cases like what Phil is >>> doing with Javascript was factored into the original design. We have even >>> talked about adding type tags to represent C++ vtables (for example) since >>> language loads and stores can't touch them (not even through char*). >>> >>> The datastructures and algorithms we have are powerful enough to express >>> these sorts of things, and so long as a frontend abided by the rules, there >>> shouldn't be a problem. >>> >> >> >> My concerns are simply that whether designed this way or not, it ends up >> fairly inconsistent. >> >> For example, what would the plan be when a frontend does something like >> clang does now for C/C++ (generate type based TBAA), and also wants to do >> something like Filip is suggesting (which is also doable on C/C++ with >> simple frontend analysis)? >> >> Generate a split tree of some sort, one side of which represents TBAA >> info, and the other side which represents partitioned abstract heaps?[1] >> It seems like that would be awfully confusing. >> >> However, it would now be necessary in order to use the new >> tbaa.read/tbaa.write metadata,, since they will only reference tbaa tags. >> But they only make a lot of sense on tbaa tags that point to partitioned >> heaps like filip's, so if you did want to actually to make use of them, you >> now have to put both the type info and the heap info in the same tree. >> >> You also run into issues with the existing metadata on loads/stores in >> this situation. It's again, entirely possible for a load to conflict with >> both a tbaa type, and a partitioned heap. In Filip's scheme, there is no >> way to represent this. >> >> Because of this, the only thing I essentially asked Filip to do was not >> place it in the same exact tree as we are currently putting type info into. >> >> Then your heap.read/heap.write metadata works with the heap tree (and you >> annotate loads/stores with your heap attributes), and your tbaa attributes >> work on the tbaa tree. You can tag a load/store with both a heap tag and a >> tbaa tag, and disambiguate based on both of them. >> >> Now, if the consensus is this is still a good idea, great. My suggestion >> would then be to update langref, rename the attributes, etc, to make this >> all more clear. >> >> --Dan >> [1] The other option of trying to generate some fake set of heaps that >> accurately represent the conflicts in both is, well, difficult :) >> _______________________________________________ >> >> >> JSC is able to make better use of the original TBAA design by encoding >> the access path within the type itself. Roughly: >> >> JSCType->Class->Field/Index >> >> This is what we're doing with C++ struct-path TBAA now, but simpler >> because only one access path is legal. >> >> JSC does need a hierarchical representation which makes TBAA a perfect >> fit. >> >> The only decision point to make now is whether to allow current TBAA to >> apply to calls. That seems entirely consistent with LLVM's approach to >> memory disambiguation. >> >> I do think this discussion is interesting and useful with respect to >> adding different styles of alias analysis in the future, but we are way >> beyond the scope of the RFC. >> > > I again, respectfully disagree. What I am suggesting is not a massive > change. He already has to add attributes to various instructions. Renaming > those adds no additional work. > The only additional work is adding a new tag for loads/stores. Work was > just recently completed to do the same, and it was, AFAIK, not a huge > undertaking. > > >> >> -Andy >> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131011/579bdf1b/attachment.html>