On Thu, Aug 17, 2017 at 4:49 PM, Hal Finkel <hfinkel at anl.gov> wrote:> > On 08/17/2017 04:49 PM, Daniel Berlin via llvm-dev wrote: > > >> >> For two given access sequences we can determine if the accessed >> objects are allowed to overlap by the rules of the input >> language. > > > Sadly, this is where this becomes "unlikely to want to use to replace > TBAA", at least for me. It may still be a thing we want anyway. > > > The rules proposed by Ivan for handling C/C++ seem pretty generic. >Uh? " [X...] is allowed to overlap with [S1..., X..., S2...] and the most generic access sequence is [X...]. [X1..., X2...] is allowed to overlap with [S1..., X1...] with the most generic access sequence to be [X1...]. [X1..., U, U::m1, X2...] is allowed to overlap with [S1..., X1..., U, U::m2, S2...] for a union U of an unknown effective type, provided m1 != m2 and the most generic access sequence is [X1..., U]. If neither of the given sequences contains the leading access type of the other, then they are allowed to overlap if the leading access type of one sequence is a direct or indirect field of the final access type of the other sequence and then the most generic access sequence consists of a single element, which is that final access type. For the purpose of determining whether one type is a direct or indirect member of another type unions are considered to have no members as accesses to members of unions are only allowed to overlap if they have the base union object explicitly specified." This sounds super specific to me. It talks about unions, and how they behave in C/C++, etc. It has initial sequence rules, etc. These would make no sense for "Rust", "Go", or "Haskell" at all. We generally explain our current TBAA rules by saying that they're generic> but motivated by C/C++ rules. >We do say that but that's not really what our implementation does in any way.> I could say the same thing about this proposed system with its proposed > rules. >It is, IMHO, nowhere near as generic.> >> This scheme is really an encoding of C/C++ TBAA info so it can be read by > LLVM and requires that *LLVM* have some set of rules that it enforces about > that scheme. > But that scheme is still very language specific in how it is used. > GCC still has something in between this and LLVM, where the language rules > are a bit encoded (but not as much as you have). > > We (and gcc) have deliberately avoided such schemes, in favor of > transforming the info into abstract set trees that then tag loads and > stores. > > The encoding of "struct path" tbaa, is just a way of trading space vs time > in that encoding. We trade walking time for the space of transitive > closure, etc. > > > If the provided statistic of 15% holds up, maybe which way we go in this > trade-off space doesn't matter much? >Sure, that part i'm indifferent about.> > > > None of the TBAA in LLVM really has any *real* relation to the original > type system rules, and that is deliberate. I've argued for years that > calling it "TBAA" just badly confuses people, and i believe here is a good > example :) > > So i don't think what you've written can be used to replace TBAA. > > > So *if* we just take the proposed rules for C/C++ as the rules for the > scheme in general, I'm not sure this is true. >Okay, let me try to rephrase a little more precisely: It is almost certainly true that we *could* make *any* particular lowering work, at different costs to the front ends and middle ends. IE i totally agree that the power of all of these systems (with small extensions) are equal. and also, for the record, i certainly think the rules/scheme described here would almost certainly produce better optimization results than what is currently implemented. *But* I don't see how you use this as a general scheme without ending up forcing the other frontends to lower things to look as if it was a C/C++ based type system. This is definitely *not* true today. They only have to lower things to look like a tree of sets. Having been down this path before, it's definitely easier to lower things to look like trees of sets than like groups of C/C++ structs/bitfields/etc that follow certain rules. This is one of the reasons I'm honestly having a lot of trouble seeing how this is is definitively better than what IBM's proposal was, which seemed both more generic and incremental, and handled most concerns. The only practical difference i see is that this just changes the scheme from one where the language rules are mostly in the front ends to one where the language rules are also partially in llvm. To me that isn't necessarily better, just different (heck, i'm even more used to that system because it's a push closer to gcc :P) So overall I don't see one as particularly better than the other. You seem to. So i'd really like to understand your perspective on this in terms of the pro/con that you are seeing. I mean, i'm really not even opposed (though others may be) in principle to saying "hey, let's just have a set of language specific tbaa passes with semi-common metadata". I'd just like to understand why we would change tradeoffs, etc. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170817/478f35fa/attachment-0001.html>
On 08/17/2017 07:20 PM, Daniel Berlin wrote:> > > On Thu, Aug 17, 2017 at 4:49 PM, Hal Finkel <hfinkel at anl.gov > <mailto:hfinkel at anl.gov>> wrote: > > > On 08/17/2017 04:49 PM, Daniel Berlin via llvm-dev wrote: >> >> >> >> For two given access sequences we can determine if the accessed >> objects are allowed to overlap by the rules of the input >> language. >> >> >> Sadly, this is where this becomes "unlikely to want to use to >> replace TBAA", at least for me. It may still be a thing we want >> anyway. > > The rules proposed by Ivan for handling C/C++ seem pretty generic. > > > Uh? > > " > > [X...] is allowed to overlap with [S1..., X..., S2...] > and the most generic access sequence is [X...]. > > [X1..., X2...] is allowed to overlap with [S1..., X1...] > with the most generic access sequence to be [X1...]. > > [X1..., U, U::m1, X2...] is allowed to overlap with > [S1..., X1..., U, U::m2, S2...] > for a union U of an unknown effective type, provided m1 != m2 > and the most generic access sequence is [X1..., U]. > > If neither of the given sequences contains the leading access > type of the other, then they are allowed to overlap if the > leading access type of one sequence is a direct or indirect field > of the final access type of the other sequence and then the most > generic access sequence consists of a single element, which is > that final access type. > > For the purpose of determining whether one type is a direct or > indirect member of another type unions are considered to have no > members as accesses to members of unions are only allowed to > overlap if they have the base union object explicitly specified." > > > This sounds super specific to me. It talks about unions, and how they > behave in C/C++, etc.I realize that it sounds super specific, but I'm not sure that it is. I was thinking about it in the following way: Imagine that we took the enhancement we previously discussed, but instead of implementing it directly, we just directly encoded for every access the path from the access type to the root. I think it would look very much like this proposal. You'd need some way of designating when you passed through a disjunctive node (where here we're calling "union", but the concept seems generic). I need to think more about the direct/indirect access rules and what's being represented. I believe we end up recovering some of this information now because of the way that we track offsets. This might be better.> It has initial sequence rules, etc.How so?> These would make no sense for "Rust", "Go", or "Haskell" at all. > > > We generally explain our current TBAA rules by saying that they're > generic but motivated by C/C++ rules. > > > We do say that but that's not really what our implementation does in > any way.Really? I thought it was motivated by C/C++ rules. When you say that it's "not really what our implementation does", is this because it drops a lot of potential information in the translation to our generic form?> I could say the same thing about this proposed system with its > proposed rules. > > It is, IMHO, nowhere near as generic. > > >> >> This scheme is really an encoding of C/C++ TBAA info so it can be >> read by LLVM and requires that *LLVM* have some set of rules that >> it enforces about that scheme. >> But that scheme is still very language specific in how it is used. >> GCC still has something in between this and LLVM, where the >> language rules are a bit encoded (but not as much as you have). >> >> We (and gcc) have deliberately avoided such schemes, in favor of >> transforming the info into abstract set trees that then tag loads >> and stores. >> >> The encoding of "struct path" tbaa, is just a way of trading >> space vs time in that encoding. We trade walking time for the >> space of transitive closure, etc. > > If the provided statistic of 15% holds up, maybe which way we go > in this trade-off space doesn't matter much? > > > Sure, that part i'm indifferent about. > > > >> >> None of the TBAA in LLVM really has any *real* relation to the >> original type system rules, and that is deliberate. I've argued >> for years that calling it "TBAA" just badly confuses people, and >> i believe here is a good example :) >> >> So i don't think what you've written can be used to replace TBAA. > > So *if* we just take the proposed rules for C/C++ as the rules for > the scheme in general, I'm not sure this is true. > > > Okay, let me try to rephrase a little more precisely: > It is almost certainly true that we *could* make *any* particular > lowering work, at different costs to the front ends and middle ends. > IE i totally agree that the power of all of these systems (with small > extensions) are equal. and also, for the record, i certainly think > the rules/scheme described here would almost certainly produce better > optimization results than what is currently implemented. > > *But* > I don't see how you use this as a general scheme without ending up > forcing the other frontends to lower things to look as if it was a > C/C++ based type system. > This is definitely *not* true today. > > They only have to lower things to look like a tree of sets. Having > been down this path before, it's definitely easier to lower things to > look like trees of sets than like groups of C/C++ > structs/bitfields/etc that follow certain rules.Our current TBAA has trees of structure types, essentially (lists of fields and offsets in each node). I don't understand how the mapping is easier or harder depending on whether we encode tree-node references vs. the path from the leaf to the root.> > This is one of the reasons I'm honestly having a lot of trouble seeing > how this is is definitively better than what IBM's proposal was, which > seemed both more generic and incremental, and handled most concerns.The claim, as I understand it, is that this is more expressive. I'm trying to understand that.> > The only practical difference i see is that this just changes the > scheme from one where the language rules are mostly in the front ends > to one where the language rules are also partially in llvm. To me > that isn't necessarily better, just different (heck, i'm even more > used to that system because it's a push closer to gcc :P)Philosophically, this doesn't bother me too much provided that we can define the required semantics in terms of IR-level constructs (without direct appeal to some outside language standard). This seems to be true in this case. We have a lot of IR-level features that come about this way (where they have well defined, but seemingly arbitrary, semantics because of the source-level language semantics that motivated their creation).> > So overall I don't see one as particularly better than the other. > You seem to. > So i'd really like to understand your perspective on this in terms of > the pro/con that you are seeing.I'm not sold yet (and may never be). I'm interested in exploring the alternative. Maybe we'll come up with some kind of hybrid design in the end, or maybe we'll go back to the previous proposal. When you say, "i certainly think the rules/scheme described here would almost certainly produce better optimization results than what is currently implemented." is this also true relative to our previous proposed enhancements? In particular, I'd like to understand where this scheme is more expressive than our current one (and the current one plus proposed enhancement for unions/arrays).> > I mean, i'm really not even opposed (though others may be) in > principle to saying "hey, let's just have a set of language specific > tbaa passes with semi-common metadata".I'd rather not go there ;)> I'd just like to understand why we would change tradeoffs, etc.Me too. Thanks again, Hal -- Hal Finkel Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170817/38ac2396/attachment.html>
<just want to focus on these parts for a second. *All* of these representations are really access path representations, just encoded slightly different ways, and, as a result, with various parts of the rules in slightly different places> Imagine that we took the enhancement we previously discussed, but instead> of implementing it directly, we just directly encoded for every access the > path from the access type to the root. I think it would look very much like > this proposal.Something like it, yes. Note that this representation also has special vtable and union groups, for example, and assumes very c-like rules in several places around the sequencing of access types. Also note that in the language of access paths, C allows overlapping that does not exist in, for example, Java (This is true in both the points-to and type-based domains). Ada has discriminated unions (and you could not use the "union" in this proposal to represent them) etc.> > We generally explain our current TBAA rules by saying that they're generic >> but motivated by C/C++ rules. >> > > We do say that but that's not really what our implementation does in any > way. > > > Really? I thought it was motivated by C/C++ rules. When you say that it's > "not really what our implementation does", is this because it drops a lot > of potential information in the translation to our generic form? >What we do is completely and totally unrelated to types as they exist in the original language. It is a completely and totally generic implementation with no rules related to the original language. The original language, for example, has dynamic typing rules, object lifetime rules, etc. We have none of these. The types do not, in fact,even always have the same relationship we give them. We have a tree and some nodes, and we happen to name them after types. Like this proposal, they also represent computed access paths, in a much simpler language. The nodes represent alias set members (either one or many) The edges represent either "access at offset" (where the default is 0 if unweighted). We have a simple rule that that processes the access paths related to ancestry. You can view it as either a grammar parsing or a graph reachability problem depending on what works for you (in fact, it's really a Dyck-CFL reachability problem on bidirected trees) The reachability rule is usually given as: If node Target is reachable from node Source, offset another through either it's children or the upwards edges (or was it downwards, i always screw up which direction we go in), they may-alias You could also implement it as a real grammar parsing problem (IE you quite literally could generate strings from tag + offset, and parse them against the grammar, and see if the terminal nodes contain your target). They are equivalent. This representation would be the same in that regard. Our current lowering for clang happens to kind of look like c/c++ structures converted to a tree. However, this is actually just inefficient, space wise, and done because it's simple to lower it this way. Because the accesses are completely unrelated to the original types, and require *no* language rules to interpret, you could also just partition the things that alias by the language rules in the frontend, and then output a tree that represents the possible unique paths. IE figure out all the answers, then re-encode it as precisely as possible. This trades time for space. This representation is *super* generic. That is, the language being used here is super simple, and the reachability rule is super simple. I could have the frontend generate these trees based on anything i like. I could, in fact, encode steensgaard points-to results as this tree without any trouble. The access path language described in this proposal is more complex and complete, and directly closer to access paths you find in C/C++. It has bitfields, vtables, and unions. The reachability rules are more complex. Is it possible to express other languages in that set of access path rules? Sure. For example, you can, as above, generate the set of answers, and then re-encode it into access paths. Right now, the work it takes *in the front end* is minimal, and has a fairly efficient space encoding. if i want to say two things alias, i just gotta be able to reach one from the other. If i want to say two things do not alias, i just gotta be able to not reach one from the other only using certain types of edges In our current language, all that takes in a frontend is "find longest no-aliasing part of tree. Go to parent, add new child". In the proposed language, the lowering is more complex. Is it doable? Sure, of course, not gonna claim otherwise. But the more "features" of the access path you add and expect the middle end to handle, instead of the front-end expanding them, and the more those feature's reachability rules are related to a specific language the more language-specific it gets. That's the *only* tradeoff we are making here, representationally. How much does the frontend have to understand about how the middle end walks these things, in order to generate whatever it wants as precisely as possible We can make whichever we want express everything we want in N^3 time :) The real question is "do we try to add on to what we have in ways that work for multiple languages, and are expressed neutrally in a simple reachability language" or "do we add language-specific kinds of nodes to the grammar, and have reachability rules that are fairly language specific". IE do you add, say, discriminated_union nodes to our current representation for ada, or "vtable_access" nodes to our current representation for C++ vtable accesses Or do you instead generate a metadata that has a unidirectional edge reachability (IE up only), or whatever it takes to do vtables generically. Both are completely and totally viable paths, and it's all about which way you want to go. But they *definitely* have a difference in terms of language-specificness. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170817/323dd762/attachment.html>