Re: Incorrect bitfield aliasing with Tree SSA
> > I continue to strongly feel that the field type shouldn't be used > > for ANYTHING! > > Then you will continue to get worse code generation than you could, in > addition to bugs like we have now. Explain to me why in the following case: struct s1 {int a;}; struct s2 {short a;}; there should be any difference. Why should one reference something having to do with "int" and the other "short"? How does knowing the "type" of the field here help anything? Perhaps you are forgetting about MEM_EXPR (which I understand *very well* since I was the implementor of it)!
Re: Incorrect bitfield aliasing with Tree SSA
> > struct foo {int a: 32; int b: 32; }; > > struct bar {int c: 32; int d: 32; }; > > > > you have the fields A and C conflicting, which is wrong. > > With the current scheme you have fields a and b conflict > and c and d conflicting > > Both of which are wrong But nothing is changing that! This is true whether or not the fields are addressable and for all proposals given so far. The only way to change this would be to make a new unique alias set for each nonaddressable field in a record and mark each as a subset of the record. This would be optimal, but is expensive for large records (e.g., ones with thousands of fields) and there's no good place to store such an alias set. However, you don't really NEED to deconflict such fields using alias sets since there are already mechanisms at both the tree and RTL level to know that such accesses can't conflict (being different FIELD_DECLs).
Re: Incorrect bitfield aliasing with Tree SSA
On 6/18/07, Richard Kenner <[EMAIL PROTECTED]> wrote: > > you have the fields A and C conflicting, which is wrong. > > Well, that is where structure-field aliasing comes in. The two cannot > even alias for addressable fields: At tree level I'll take your word for it, but what about RTL level? Is that nonconflicting status passed to RTL? What *is* the problem with just using the parent alias set? At the RTL level, nothing. If you ever wanted to make the RTL level do *better* than it does now, you'd run into the same problem the tree level does. I continue to strongly feel that the field type shouldn't be used for ANYTHING! Then you will continue to get worse code generation than you could, in addition to bugs like we have now. HTH, Dan
Re: Incorrect bitfield aliasing with Tree SSA
On 6/18/07, Richard Kenner <[EMAIL PROTECTED]> wrote: > Type of the expression passed to get_alias_set. And without the > component_uses_parent_alias_set loop. So you mean the type of the *field*? That can't work. That type can't be used for *anything*! Otherwise, if you have struct foo {int a: 32; int b: 32; }; struct bar {int c: 32; int d: 32; }; you have the fields A and C conflicting, which is wrong. With the current scheme you have fields a and b conflict and c and d conflicting Both of which are wrong HTH, Dan
Re: Incorrect bitfield aliasing with Tree SSA
On 6/18/07, Richard Kenner <[EMAIL PROTECTED]> wrote: > They are the alias set mechanism, which you don't seem to understand. > They always have been. I certainly understand the alias set mechanism. It sounded like you were talking about something else since if the only thing we're using is alias sets, I'm mystified as to what the issue is. > I'd rather not explain all of alias.c to you in an email message, to > be honest As I said, I completely understand alias.c. You clearly do not It sounded like you were trying to do something OUTSIDE of that. So let's start again: why is it suddenly necessary that their be a hierarchy of alias sets when no fields are addressable? If I have struct foo {int a: 1; int b: 1;}; why do we need more than one alias set? Who is it that requires any subsetting at all? Certainly nothing in alias.c does. I'm not going through this again, i'm just going to fix the problem. I've wasted enough time on this.
Re: Incorrect bitfield aliasing with Tree SSA
> > you have the fields A and C conflicting, which is wrong. > > Well, that is where structure-field aliasing comes in. The two cannot > even alias for addressable fields: At tree level I'll take your word for it, but what about RTL level? Is that nonconflicting status passed to RTL? What *is* the problem with just using the parent alias set? I continue to strongly feel that the field type shouldn't be used for ANYTHING!
Re: Incorrect bitfield aliasing with Tree SSA
Richard Kenner writes: > Otherwise, if you have > > struct foo {int a: 32; int b: 32; }; > struct bar {int c: 32; int d: 32; }; > > you have the fields A and C conflicting, which is wrong. Well, that is where structure-field aliasing comes in. The two cannot even alias for addressable fields: struct s { int a; int b; }; struct t { int a; int b; }; struct s *a; struct t *b; main () { a->a = 1; b->a = 2; return a->a; } movqa(%rip), %rax movl$1, (%rax) movqb(%rip), %rax movl$2, (%rax) movl$1, %eax ret Adam
Re: Incorrect bitfield aliasing with Tree SSA
> They are the alias set mechanism, which you don't seem to understand. > They always have been. I certainly understand the alias set mechanism. It sounded like you were talking about something else since if the only thing we're using is alias sets, I'm mystified as to what the issue is. > I'd rather not explain all of alias.c to you in an email message, to > be honest As I said, I completely understand alias.c. It sounded like you were trying to do something OUTSIDE of that. So let's start again: why is it suddenly necessary that their be a hierarchy of alias sets when no fields are addressable? If I have struct foo {int a: 1; int b: 1;}; why do we need more than one alias set? Who is it that requires any subsetting at all? Certainly nothing in alias.c does.
Re: Incorrect bitfield aliasing with Tree SSA
On 6/18/07, Richard Kenner <[EMAIL PROTECTED]> wrote: > It gives you the alias set of the parent, which, for the reason that > OTHER THINGS USE THE ALIAS SET SPLAY TREES, gives the wrong answer. Can you give a few sentence explanation of what "alias set splay trees" are and why they aren't using the alias set mechanism? They are the alias set mechanism, which you don't seem to understand. They always have been. How do you believe we determine whether two alias sets conflict, or are related at all? > > I'm not sure what a "TBAA forest" is, but keep in mind that, at least in > > Ada, we have many different types (meaning different tree nodes) that have > > the same alias set and we really do mean that they are to conflict. > > That's nice. But are they handled properly? Yes > There are other questions we ask about alias sets other than "do these > two alias sets conflict" (which is asking whether they are subsets of > each other, or equal). We have good reasons to ask these questions. Can you give examples of those questions? I'd rather not explain all of alias.c to you in an email message, to be honest
Re: Incorrect bitfield aliasing with Tree SSA
> Type of the expression passed to get_alias_set. And without the > component_uses_parent_alias_set loop. So you mean the type of the *field*? That can't work. That type can't be used for *anything*! Otherwise, if you have struct foo {int a: 32; int b: 32; }; struct bar {int c: 32; int d: 32; }; you have the fields A and C conflicting, which is wrong. The "T" has to be the *record type*, so that when you share alias sets, it's the same for every type in the same record, not every occurence of some random type in different records.
Re: Incorrect bitfield aliasing with Tree SSA
Richard Kenner writes: > > I am glad to see we are converging toward implementation issues now! > > > > I am storing it in a new field under the alias_set_entry: > > > > get_alias_set_entry (TYPE_ALIAS_SET (t))->nonaddr_alias_set. > > Where T is which type? Type of the expression passed to get_alias_set. And without the component_uses_parent_alias_set loop. Adam
Re: Incorrect bitfield aliasing with Tree SSA
> It gives you the alias set of the parent, which, for the reason that > OTHER THINGS USE THE ALIAS SET SPLAY TREES, gives the wrong answer. Can you give a few sentence explanation of what "alias set splay trees" are and why they aren't using the alias set mechanism? > > I'm not sure what a "TBAA forest" is, but keep in mind that, at least in > > Ada, we have many different types (meaning different tree nodes) that have > > the same alias set and we really do mean that they are to conflict. > > That's nice. But are they handled properly? > There are other questions we ask about alias sets other than "do these > two alias sets conflict" (which is asking whether they are subsets of > each other, or equal). We have good reasons to ask these questions. Can you give examples of those questions?
Re: Incorrect bitfield aliasing with Tree SSA
> I am glad to see we are converging toward implementation issues now! > > I am storing it in a new field under the alias_set_entry: > > get_alias_set_entry (TYPE_ALIAS_SET (t))->nonaddr_alias_set. Where T is which type?
Re: Incorrect bitfield aliasing with Tree SSA
On 6/18/07, Richard Kenner <[EMAIL PROTECTED]> wrote: > How does this get a different result for trees than RTL? > > As i've explained, we rely on the proper of the TBAA forest that given > > struct foo (set 1) > / \ > int :31 (set 2) short :31 (set 3) > > sets for int :31 and short :31 are strict subsets of that of struct foo. Where I'm lost here is why you need do anything whatsoever! If you ask for the alias set of something, get_alias_set *already* does the right thing. It does not do the above, so it does not do the correct thing. It gives you the alias set of the parent, which, for the reason that OTHER THINGS USE THE ALIAS SET SPLAY TREES, gives the wrong answer. This is not, and has never been about get_alias set. There are other queries to the splay trees that is generated from get_alias_set than alias_sets_conflict_p All you have to do is look at the splay tree lookups in alias.c, and you will see alias_subset_of Or is the issue that you're calling get_alias_set on a FIELD_DECL I'm not sure what a "TBAA forest" is, but keep in mind that, at least in Ada, we have many different types (meaning different tree nodes) that have the same alias set and we really do mean that they are to conflict. That's nice. This is why it's a concern to me if we're not uniformly using the same functions at the tree and RTL level to compute alias sets. Sigh, I give up. We are computing the alias sets only using get_alias_set There are other questions we ask about alias sets other than "do these two alias sets conflict" (which is asking whether they are subsets of each other, or equal). We have good reasons to ask these questions. By creating TBAA info that makes fields not subsets of their parents you don't break alias_sets_conflict_p (which is all RTL ever uses), but you break *all the other questions we ask about relationships between alias sets*, which is what the tree level uses.
Re: Incorrect bitfield aliasing with Tree SSA
Richard Kenner writes: > But there's also an implementation issue: where do you propose to *store* > this fake alias set? There is no such field as DECL_ALIAS_SET. I am glad to see we are converging toward implementation issues now! I am storing it in a new field under the alias_set_entry: get_alias_set_entry (TYPE_ALIAS_SET (t))->nonaddr_alias_set. Adam
Re: Incorrect bitfield aliasing with Tree SSA
> How does this get a different result for trees than RTL? > > As i've explained, we rely on the proper of the TBAA forest that given > > struct foo (set 1) > / \ > int :31 (set 2) short :31 (set 3) > > sets for int :31 and short :31 are strict subsets of that of struct foo. Where I'm lost here is why you need do anything whatsoever! If you ask for the alias set of something, get_alias_set *already* does the right thing. Or is the issue that you're calling get_alias_set on a FIELD_DECL? I'm not sure what a "TBAA forest" is, but keep in mind that, at least in Ada, we have many different types (meaning different tree nodes) that have the same alias set and we really do mean that they are to conflict. This is why it's a concern to me if we're not uniformly using the same functions at the tree and RTL level to compute alias sets. But there's also an implementation issue: where do you propose to *store* this fake alias set? There is no such field as DECL_ALIAS_SET.
Re: Incorrect bitfield aliasing with Tree SSA
On 6/18/07, Richard Kenner <[EMAIL PROTECTED]> wrote: > > But throws away the entire DECL_NONADDRESSABLE_P mechanism! > > No, an int* will still not conflict with int:31 > a short * will still not conflict with short:31 Using what mechanism? That's what DECL_NONADDRESSABLE_P does! Please read what the *second* proposal was again 1. The alias set is a subset of the parent set and more importantly 2. The alias set is different than that of the underlying type and the parent set. Thus, the alias sets will not conflict with the underlying type, but will conflict with the parent set which is exactly what you want. How does this get a different result for trees than RTL? As i've explained, we rely on the proper of the TBAA forest that given struct foo (set 1) / \ int :31 (set 2) short :31 (set 3) sets for int :31 and short :31 are strict subsets of that of struct foo. This is how it is documented and except for this one little wart introduced by DECL_NONADDRESSABLE_P, how it is. For the sake of a complete example, we also have int (set 4) and short (set 5), which are both roots of this forest, and thus, do not conflict with set 3 or 2. The forest we have now says: struct foo, int :31, short :31 (set 1) (and int = set 4 and short = set 5). Note again that in neither forest does set 1 conflict with 4 or 5, but in the first forest, the subset relationship between int:31 and struct foo is properly represented as subset but different. As I said to Eric, you can also change the strict subset to subset_or_equals, but that is really not quite in accord with reality. They *really are different alias sets than their parent*. Note also that it is more precise in the first case. If you were ever to ask "can int:31 touch short:31", the first forest would correctly say no, what we have now would say "yes". > Tell me what TYPE_NONALIASED_COMPONENT does, and i'll tell you what > will happen right now :) Very similar. If I have typedef xyz[100] foo; and mark that type with that flag, it means that int * will not conflict with it, just foo *. Then these should simply have different non-conflicting aliasing sets :)
Re: Incorrect bitfield aliasing with Tree SSA
> > But throws away the entire DECL_NONADDRESSABLE_P mechanism! > > No, an int* will still not conflict with int:31 > a short * will still not conflict with short:31 Using what mechanism? That's what DECL_NONADDRESSABLE_P does! > Tell me what TYPE_NONALIASED_COMPONENT does, and i'll tell you what > will happen right now :) Very similar. If I have typedef xyz[100] foo; and mark that type with that flag, it means that int * will not conflict with it, just foo *.
Re: Incorrect bitfield aliasing with Tree SSA
On 6/18/07, Richard Kenner <[EMAIL PROTECTED]> wrote: > His first patch, which simply makes #1 true, would cause missed optimization. It doesn't "cause missed optimizations": it completely removes all the functionality of DECL_NONADDRESSABLE_P! Hence the reason for the second suggestion.
Re: Incorrect bitfield aliasing with Tree SSA
On 6/18/07, Richard Kenner <[EMAIL PROTECTED]> wrote: > Again, the tree level relies on the documented (in the comments of > alias.c) fact that given a structure, the fields contained in a > structure will have alias sets that are strict subsets of the parent. That is ONLY true for fields that don't have DECL_NONADDRESSABLE_P and that's been the case foreever. The documentation might be confusing, but the code has never been. > The bug reports are about cases where we have a struct foo * (where > struct foo contains int a:31), and foo pointer->a is claimed to not > alias with foo.a. How can you take a pointer to the bitfield? > I would much rather maintain the strict subset invariant than the > component_uses_parent_alias_set stuff, since this is the documented > invariant, and makes sense. But throws away the entire DECL_NONADDRESSABLE_P mechanism! No, an int* will still not conflict with int:31 a short * will still not conflict with short:31 Also, how do we handle TYPE_NONALIASED_COMPONENT? It's exactly the same issue? Tell me what TYPE_NONALIASED_COMPONENT does, and i'll tell you what will happen right now :)
Re: Incorrect bitfield aliasing with Tree SSA
> His first patch, which simply makes #1 true, would cause missed optimization. It doesn't "cause missed optimizations": it completely removes all the functionality of DECL_NONADDRESSABLE_P!
Re: Incorrect bitfield aliasing with Tree SSA
> Again, the tree level relies on the documented (in the comments of > alias.c) fact that given a structure, the fields contained in a > structure will have alias sets that are strict subsets of the parent. That is ONLY true for fields that don't have DECL_NONADDRESSABLE_P and that's been the case foreever. The documentation might be confusing, but the code has never been. > The bug reports are about cases where we have a struct foo * (where > struct foo contains int a:31), and foo pointer->a is claimed to not > alias with foo.a. How can you take a pointer to the bitfield? > I would much rather maintain the strict subset invariant than the > component_uses_parent_alias_set stuff, since this is the documented > invariant, and makes sense. But throws away the entire DECL_NONADDRESSABLE_P mechanism! Also, how do we handle TYPE_NONALIASED_COMPONENT? It's exactly the same issue?
Re: Incorrect bitfield aliasing with Tree SSA
On 6/18/07, Richard Kenner <[EMAIL PROTECTED]> wrote: > Uh, except as we've discovered, the RTL uses alias set 0, so whatever > alias set you choose for these doesn't matter anyway to the RTL level. Only in some cases. That was a kludge put in to fix some obscure bug and left there. I hope we can remove it at some point, and think we can. > No i mean the idea of making it a different alias set than the parent, > but a subset of the parent. Because it *is* the parent in most places, so it should be in all. Again, the tree level relies on the documented (in the comments of alias.c) fact that given a structure, the fields contained in a structure will have alias sets that are strict subsets of the parent. The bug reports are about cases where we have a struct foo * (where struct foo contains int a:31), and foo pointer->a is claimed to not alias with foo.a. This is because we use the subset relationship to prune the set of aliases that a pointer to the structure could touch (this is the only case we get wrong, as the bug reports will show). We do not test subset or equal, only strict subset. Since parent-alias set is not a strict subset of parent-alias set, we determine they cannot alias. I would much rather maintain the strict subset invariant than the component_uses_parent_alias_set stuff, since this is the documented invariant, and makes sense. Adam's suggestion to use a new alias set that is 1. A subset of the parent structure's alias set. *AND* 2. Not the same as the "type" (IE int in the case of int:31) of the field Will not cause missed optimization. It will maintain the strict subset relationship. It requires no component_uses_parent_alias_set function. His first patch, which simply makes #1 true, would cause missed optimization.
Re: Incorrect bitfield aliasing with Tree SSA
> Uh, except as we've discovered, the RTL uses alias set 0, so whatever > alias set you choose for these doesn't matter anyway to the RTL level. Only in some cases. That was a kludge put in to fix some obscure bug and left there. I hope we can remove it at some point, and think we can. > No i mean the idea of making it a different alias set than the parent, > but a subset of the parent. Because it *is* the parent in most places, so it should be in all.
Re: Incorrect bitfield aliasing with Tree SSA
On 6/18/07, Daniel Berlin <[EMAIL PROTECTED]> wrote: On 6/18/07, Eric Botcazou <[EMAIL PROTECTED]> wrote: > > If it was designed properly in the first place, there simply would *be > > no problem at the tree level*, because nothing would have broken. > > That's certainly a point of view. The other is that the RTL implementation > predates the Tree one, works fine in GCC 3.x, including for the C compiler. > One would have thought that the Tree implementation would be aware of it > instead of overlooking it, given that alias.c is shared among them. Uh, except as we've discovered, the RTL uses alias set 0, so whatever alias set you choose for these doesn't matter anyway to the RTL level. > > > So far you guys have resisted what seem like perfectly reasonable > > solutions by Adam > > You mean the patch that would have disabled the whole thing at the RTL level? > I'm sure that we can devise something better. No i mean the idea of making it a different alias set than the parent, but a subset of the parent. also, unique from the alias set of the other type (IE int:31 has a different alias set than int).
Re: Incorrect bitfield aliasing with Tree SSA
On 6/18/07, Eric Botcazou <[EMAIL PROTECTED]> wrote: > If it was designed properly in the first place, there simply would *be > no problem at the tree level*, because nothing would have broken. That's certainly a point of view. The other is that the RTL implementation predates the Tree one, works fine in GCC 3.x, including for the C compiler. One would have thought that the Tree implementation would be aware of it instead of overlooking it, given that alias.c is shared among them. Uh, except as we've discovered, the RTL uses alias set 0, so whatever alias set you choose for these doesn't matter anyway to the RTL level. > So far you guys have resisted what seem like perfectly reasonable > solutions by Adam You mean the patch that would have disabled the whole thing at the RTL level? I'm sure that we can devise something better. No i mean the idea of making it a different alias set than the parent, but a subset of the parent. -- Eric Botcazou
Re: Incorrect bitfield aliasing with Tree SSA
> If it was designed properly in the first place, there simply would *be > no problem at the tree level*, because nothing would have broken. It's possible to have bugs anytime and that's all we have here: somebody is using the wrong alias set someplace. We fix that and all is OK. > So far you guys have resisted what seem like perfectly reasonable > solutions by Adam Because they turn off the feature rather than use it. I still don't understand what the difficulty is here and why you persist in thinking that type alias set of the type of a non-addressable field has any use at all: it doesn't and should be COMPLETELY ignored. All the code has been written to do that. Somebody is trying to directly compute an alias set instead of using get_alias_set and when you find that, you'll find the bug.
Re: Incorrect bitfield aliasing with Tree SSA
> That is not the example case we have given where this breaks. > The case where it breaks is exactly the case i have shown you. > > We have a pointer to a structure, and because you have not recorded > the type's alias relationships properly, we claim derferences that are > offsetted from the structure can not access the field. > This is a direct consequence of trying to use the parent's alias set > for that of the child type, instead of creating a new alias set. Let me try to explain it this way: if you have a structure where all fields are nonaddressable, EVERY reference should have the same alias set, that of the structure. So they all conflict, as they should, and no other reference will conflict, which is also correct. It sounds like there's a bug here in that somebody is using the wrong alias set somewhere. All the RTL dumps posted in this thread (and the related one in gcc-patches) look correct, so it's right at the RTL level. That means that only place it's wrong would be at tree level, but get_alias_set also does the right thing.
Re: Incorrect bitfield aliasing with Tree SSA
> If it was designed properly in the first place, there simply would *be > no problem at the tree level*, because nothing would have broken. That's certainly a point of view. The other is that the RTL implementation predates the Tree one, works fine in GCC 3.x, including for the C compiler. One would have thought that the Tree implementation would be aware of it instead of overlooking it, given that alias.c is shared among them. > So far you guys have resisted what seem like perfectly reasonable > solutions by Adam You mean the patch that would have disabled the whole thing at the RTL level? I'm sure that we can devise something better. -- Eric Botcazou
Re: Incorrect bitfield aliasing with Tree SSA
On 6/18/07, Eric Botcazou <[EMAIL PROTECTED]> wrote: > I'm completely unsurprised this is broken at the tree level given how > it is implemented Nice tautology. :-) You have resisted implementing anything at the tree level to fix the problem and now you're complaining there is a problem... Pardon? If it was designed properly in the first place, there simply would *be no problem at the tree level*, because nothing would have broken. Everyone in the bug reports in question has told you this, not just me. Let's try and devise something plausible at the tree level. If we eventually fail, we could indeed consider disabling the optimization at the RTL level. So far you guys have resisted what seem like perfectly reasonable solutions by Adam
Re: Incorrect bitfield aliasing with Tree SSA
> I'm completely unsurprised this is broken at the tree level given how > it is implemented Nice tautology. :-) You have resisted implementing anything at the tree level to fix the problem and now you're complaining there is a problem... Let's try and devise something plausible at the tree level. If we eventually fail, we could indeed consider disabling the optimization at the RTL level. -- Eric Botcazou
Re: Incorrect bitfield aliasing with Tree SSA
> I am trying now to prototype a new approach along the lines of > returning true in component_uses_parent_alias_set for SFT's with > DECL_NONADDRESSABLE_P. Yes, the key problem is indeed SFTs, which is why we disable structure aliasing in the Ada compiler. -- Eric Botcazou
Re: Incorrect bitfield aliasing with Tree SSA
> > type T1 is record > >J : Integer; > > end record; > > > > X1 : T1; > > > > => then X1.J "address" cannot be taken in legal Ada, so no integer > > pointer can ever point to it. > > However, can a pointer to X1, stored into, affect J? Of course. > If so, field J's alias set must be marked as a subset of X1's alias > set, or we will get the info wrong. "field J" doesn't *have* an alias set (only references do) and any reference to field J will have the alias set of T1 (see get_alias_set). So they conflict. If you insist on asking "what is the alias set of field J", you get it by DECL_NONADDRESSABLE_P (decl_of_j) ? TYPE_ALIAS_SET (DECL_CONTEXT (decl_of_j)) : TYPE_ALIAS_SET (TREE_TYPE (decl_of_j))
Re: Incorrect bitfield aliasing with Tree SSA
On 6/17/07, Richard Kenner <[EMAIL PROTECTED]> wrote: > > > > So if I have > > > > struct foo {int x; float y; } bar; > > > > > > But if you add > > > > > > struct foo *foop = &bar. > > > > > > foop->x = 5. > > > > > > It can, even though we *claim* X is nonaddressable. > > > > Which can what exactly? > > It can be addressed, as i've shown above. foop is a pointer to &bar.x > in the above case. No, it's a pointer to bar. It contains the same *value* as a pointer to bar.x is "nonaddresable" in the sense that any pointer that refers to memory contained in it can't be of the type of the field (int) and hence can't be of its alias set, but must be of the type of bar (struct foo) and hence of *that* alias set. > The reality is that a pointer to it's parent can legally access it, so > their alias sets should conflict. Which alias sets? How can a pointer to int conflict with a pointer to bar if X is nonaddressable? That is not the example case we have given where this breaks. The case where it breaks is exactly the case i have shown you. We have a pointer to a structure, and because you have not recorded the type's alias relationships properly, we claim derferences that are offsetted from the structure can not access the field. This is a direct consequence of trying to use the parent's alias set for that of the child type, instead of creating a new alias set.
Re: Incorrect bitfield aliasing with Tree SSA
> > > > So if I have > > > > struct foo {int x; float y; } bar; > > > > > > But if you add > > > > > > struct foo *foop = &bar. > > > > > > foop->x = 5. > > > > > > It can, even though we *claim* X is nonaddressable. > > > > Which can what exactly? > > It can be addressed, as i've shown above. foop is a pointer to &bar.x > in the above case. No, it's a pointer to bar. It contains the same *value* as a pointer to bar.x would, but is of the wrong type. bar.x is "nonaddresable" in the sense that any pointer that refers to memory contained in it can't be of the type of the field (int) and hence can't be of its alias set, but must be of the type of bar (struct foo) and hence of *that* alias set. > The reality is that a pointer to it's parent can legally access it, so > their alias sets should conflict. Which alias sets? How can a pointer to int conflict with a pointer to bar if X is nonaddressable? > You guys seem to be trying to get some sort of optimization through > hacking around with the alias set system, and then guessing at how all > the clients will actually use the information. Not at all. This is completely consistent. No hacking or lying to the type system involved!
Re: Incorrect bitfield aliasing with Tree SSA
On Sun, 2007-06-17 at 17:02 -0400, Daniel Berlin wrote: > On 6/17/07, Laurent GUERBY <[EMAIL PROTECTED]> wrote: > > In Ada if you have a struct type, components of the struct > > that do not have the explicit keyword "aliased" cannot > > have their adress taken. Example: > > > > type T1 is record > >J : Integer; > > end record; > > > > X1 : T1; > > > > => then X1.J "address" cannot be taken in legal Ada, so no integer > > pointer can ever point to it. > > However, can a pointer to X1, stored into, affect J? In the particular case above there cannot be a pointer to X1 in the program. But if you have: X1 : aliased T1; Then yes a pointer P1 to X1 can exist, and then P1.all.J is legal. There are some record types which are automatically aliased, for example object oriented stuff ("tagged" types in Ada) but most simple records are non aliased in Ada "normal" code that's why it could pessimize code to assume all components are aliased. If aliased variable/aliased type Y1 has a T1 component then of course you can modify J through a pointer to the container. > If so, field J's alias set must be marked as a subset of X1's alias > set, or we will get the info wrong. We currently do *not* mark field > J's alias set as a subset of X1's, because J is DECL_NONADDRESSABLE_P. > > (This is in fact, the problem we are hitting here in C. We do *not* > record the alias as a subset, which in effect, claims a pointer to > the structure can never touch the field, which is wrong. > The correct place for such optimization is to do it per-memory > reference, not to screw up the type based info) I can't comment here :). Laurent
Re: Incorrect bitfield aliasing with Tree SSA
On 6/17/07, Laurent GUERBY <[EMAIL PROTECTED]> wrote: On Sun, 2007-06-17 at 15:31 -0400, Daniel Berlin wrote: > On 6/17/07, Eric Botcazou <[EMAIL PROTECTED]> wrote: > > > > So if I have > > > > struct foo {int x; float y; } bar; > > > > int *pi; > > > > float *pf; > > > > > > > > and mark X as "nonaddressable", I know that an assigment to *pi can't > > > > affect bar.x. > > > > > > But if you add > > > > > > struct foo *foop = &bar. > > > > > > foop->x = 5. > > > > > > It can, even though we *claim* X is nonaddressable. > > > > Which can what exactly? > > It can be addressed, as i've shown above. foop is a pointer to &bar.x > in the above case. > > You guys seem to be trying to get some sort of optimization through > hacking around with the alias set system, and then guessing at how all > the clients will actually use the information. > > The reality is that a pointer to it's parent can legally access it, so > their alias sets should conflict. In Ada if you have a struct type, components of the struct that do not have the explicit keyword "aliased" cannot have their adress taken. Example: type T1 is record J : Integer; end record; X1 : T1; => then X1.J "address" cannot be taken in legal Ada, so no integer pointer can ever point to it. However, can a pointer to X1, stored into, affect J? If so, field J's alias set must be marked as a subset of X1's alias set, or we will get the info wrong. We currently do *not* mark field J's alias set as a subset of X1's, because J is DECL_NONADDRESSABLE_P. (This is in fact, the problem we are hitting here in C. We do *not* record the alias as a subset, which in effect, claims a pointer to the structure can never touch the field, which is wrong. The correct place for such optimization is to do it per-memory reference, not to screw up the type based info)
Re: Incorrect bitfield aliasing with Tree SSA
On Sun, 2007-06-17 at 15:31 -0400, Daniel Berlin wrote: > On 6/17/07, Eric Botcazou <[EMAIL PROTECTED]> wrote: > > > > So if I have > > > > struct foo {int x; float y; } bar; > > > > int *pi; > > > > float *pf; > > > > > > > > and mark X as "nonaddressable", I know that an assigment to *pi can't > > > > affect bar.x. > > > > > > But if you add > > > > > > struct foo *foop = &bar. > > > > > > foop->x = 5. > > > > > > It can, even though we *claim* X is nonaddressable. > > > > Which can what exactly? > > It can be addressed, as i've shown above. foop is a pointer to &bar.x > in the above case. > > You guys seem to be trying to get some sort of optimization through > hacking around with the alias set system, and then guessing at how all > the clients will actually use the information. > > The reality is that a pointer to it's parent can legally access it, so > their alias sets should conflict. In Ada if you have a struct type, components of the struct that do not have the explicit keyword "aliased" cannot have their adress taken. Example: type T1 is record J : Integer; end record; X1 : T1; => then X1.J "address" cannot be taken in legal Ada, so no integer pointer can ever point to it. type T2 is record J : aliased Integer; end record; X2 : T2; => then X2.J "address" can be taken and integer pointers can point to it. I don't think other language have such fine grained control of adressability attached to the type. I'm not understanding much of the discussion, just pointing this language difference out in hope it helps. Laurent
Re: Incorrect bitfield aliasing with Tree SSA
On 6/17/07, Eric Botcazou <[EMAIL PROTECTED]> wrote: > > So if I have > > struct foo {int x; float y; } bar; > > int *pi; > > float *pf; > > > > and mark X as "nonaddressable", I know that an assigment to *pi can't > > affect bar.x. > > But if you add > > struct foo *foop = &bar. > > foop->x = 5. > > It can, even though we *claim* X is nonaddressable. Which can what exactly? It can be addressed, as i've shown above. foop is a pointer to &bar.x in the above case. You guys seem to be trying to get some sort of optimization through hacking around with the alias set system, and then guessing at how all the clients will actually use the information. The reality is that a pointer to it's parent can legally access it, so their alias sets should conflict. You seem to only want it to not conflict "in certain cases", and hacking around with alias sets is the wrong way to do this. The right way to do this is to take the special cases into account when you actually see them. I'm completely unsurprised this is broken at the tree level given how it is implemented --Dan
Re: Incorrect bitfield aliasing with Tree SSA
Eric Botcazou writes: > For the Ada testcase: > > ;; s->i = 0 > (insn 7 6 0 p.adb:5 (set (mem/s/j:SI (reg/v/f:DI 59 [ s ]) [4 .i+0 > S4 A32]) > (const_int 0 [0x0])) -1 (nil)) > > ;; *p = 1 > (insn 8 7 0 p.adb:6 (set (mem:SI (reg/v/f:DI 60 [ p ]) [2 S4 A32]) > (const_int 1 [0x1])) -1 (nil)) > > ;; return s->i > (insn 9 8 10 p.adb:6 (set (reg:SI 62) > (mem/s/j:SI (reg/v/f:DI 59 [ s ]) [4 .i+0 S4 A32])) -1 > (nil)) > > i.e. s->i is accessed with the alias set of 'S'. Thanks, that helped. I think you're right. Obviously we don't have this issue with bitfields in C. I am trying now to prototype a new approach along the lines of returning true in component_uses_parent_alias_set for SFT's with DECL_NONADDRESSABLE_P. Adam
Re: Incorrect bitfield aliasing with Tree SSA
> > struct foo {int x; float y; } bar; > > int *pi; > > float *pf; > > > > and mark X as "nonaddressable", I know that an assigment to *pi can't > > affect bar.x. > > But if you add > > struct foo *foop = &bar. > > foop->x = 5. > > It can, even though we *claim* X is nonaddressable. I don't follow. It's still the case that *pi = 10; cannot change bar.x. Making a pointer to the entire structure doesn't change that. > If you told me this is what you meant by "nonaddressable", i'd > probably call you crazy. > > It is most certainly addressable, because you can form the address of it. I'd certainly have no problem replacing that name with a better one. The Ada terminology is "aliased", but that seemed too obscure. The name doesn't refer to the machine-level concept of "address", but to the C operator "&", which is normally called "address of". DECL_NONADDRESSABLE_P means you can't apply the C operator "&" to that field.
Re: Incorrect bitfield aliasing with Tree SSA
> > So if I have > > struct foo {int x; float y; } bar; > > int *pi; > > float *pf; > > > > and mark X as "nonaddressable", I know that an assigment to *pi can't > > affect bar.x. > > But if you add > > struct foo *foop = &bar. > > foop->x = 5. > > It can, even though we *claim* X is nonaddressable. Which can what exactly? -- Eric Botcazou
Re: Incorrect bitfield aliasing with Tree SSA
> Because it wouldn't be pruning it if the alias sets conflicted! Well, just look at the first RTL dump for: struct S { int i; }; int f (struct S *s, int *p) { s->i = 0; *p = 1; return s->i; } and package P is type S is record i : Integer; end record; type SP is access all S; type IP is access all Integer; function f (s : SP; p : IP) return Integer; end P; package body P is function f (s : SP; p : IP) return Integer is begin s.i := 0; p.all := 1; return s.i; end; end P; compiled at -O2 -gnatp -fno-tree-dominator-opts -fno-tree-store-ccp. For the C testcase: ;; s->i = 0 (insn 7 6 0 t.c:5 (set (mem/s:SI (reg/v/f:DI 59 [ s ]) [3 .i+0 S4 A32]) (const_int 0 [0x0])) -1 (nil)) ;; *p = 1 (insn 8 7 0 t.c:6 (set (mem:SI (reg/v/f:DI 60 [ p ]) [3 S4 A32]) (const_int 1 [0x1])) -1 (nil)) ;; return s->i (insn 9 8 10 t.c:6 (set (reg:SI 62) (mem/s:SI (reg/v/f:DI 59 [ s ]) [3 .i+0 S4 A32])) -1 (nil)) i.e. everything is accessed with the alias set of 'int'. For the Ada testcase: ;; s->i = 0 (insn 7 6 0 p.adb:5 (set (mem/s/j:SI (reg/v/f:DI 59 [ s ]) [4 .i+0 S4 A32]) (const_int 0 [0x0])) -1 (nil)) ;; *p = 1 (insn 8 7 0 p.adb:6 (set (mem:SI (reg/v/f:DI 60 [ p ]) [2 S4 A32]) (const_int 1 [0x1])) -1 (nil)) ;; return s->i (insn 9 8 10 p.adb:6 (set (reg:SI 62) (mem/s/j:SI (reg/v/f:DI 59 [ s ]) [4 .i+0 S4 A32])) -1 (nil)) i.e. s->i is accessed with the alias set of 'S'. Now put 'aliased' on the field type S is record i : aliased Integer; end record; and you get: ;; s->i = 0 (insn 7 6 0 p.adb:5 (set (mem/s:SI (reg/v/f:DI 59 [ s ]) [2 .i+0 S4 A32]) (const_int 0 [0x0])) -1 (nil)) ;; *p = 1 (insn 8 7 0 p.adb:6 (set (mem:SI (reg/v/f:DI 60 [ p ]) [2 S4 A32]) (const_int 1 [0x1])) -1 (nil)) ;; return s->i (insn 9 8 10 p.adb:6 (set (reg:SI 62) (mem/s:SI (reg/v/f:DI 59 [ s ]) [2 .i+0 S4 A32])) -1 (nil)) like in C. The discrepancy purely stems from DECL_NONADDRESSABLE_P. > > I didn't invent it either, but everything is more or less documented. > > No, not really. Yes, it is, that's how I've understood how this stuff works. -- Eric Botcazou
Re: Incorrect bitfield aliasing with Tree SSA
On 6/16/07, Richard Kenner <[EMAIL PROTECTED]> wrote: > You guys have come up with a very weird idea of what > non-addressability means. These fields are all addressable, they > are just not directly addressable. Terminology is always tricky here. "addressable" in this context means that no pointer can point directly to the field. Which is, well, at least in aliasing and pointer tracking, a meaningless thing. So if I have struct foo {int x; float y; } bar; int *pi; float *pf; and mark X as "nonaddressable", I know that an assigment to *pi can't affect bar.x. But if you add struct foo *foop = &bar. foop->x = 5. It can, even though we *claim* X is nonaddressable. If you told me this is what you meant by "nonaddressable", i'd probably call you crazy. It is most certainly addressable, because you can form the address of it.
Re: Incorrect bitfield aliasing with Tree SSA
On 6/16/07, Eric Botcazou <[EMAIL PROTECTED]> wrote: > If that was really true, we would get this right. Well, this is true, I really don't understand why you keep denying that. Because it wouldn't be pruning it if the alias sets conflicted! Just grep the RTL expanders for MEM_KEEP_ALIAS_SET_P for example: `MEM_KEEP_ALIAS_SET_P (X)' In `mem' expressions, 1 if we should keep the alias set for this mem unchanged when we access a component. Set to 1, for example, when we are already in a non-addressable component of an aggregate. Stored in the `jump' field and printed as `/j'. > You guys have come up with a very weird idea of what non-addressability > means. I didn't invent it either, but everything is more or less documented. No, not really. > These fields are all addressable, they are just not directly addressable. Right, that's just what is written in tree.h: /* Used in a FIELD_DECL to indicate that we cannot form the address of this component. */ #define DECL_NONADDRESSABLE_P(NODE) \ (FIELD_DECL_CHECK (NODE)->decl_common.decl_flag_3) Uh, no. You *can* form the address, that's the whole problem. You just can't form it directly. The above comment gives absolutely no clue as to why this was added, what it really means, etc -- Eric Botcazou
Re: Incorrect bitfield aliasing with Tree SSA
> You guys have come up with a very weird idea of what > non-addressability means. These fields are all addressable, they > are just not directly addressable. Terminology is always tricky here. "addressable" in this context means that no pointer can point directly to the field. So if I have struct foo {int x; float y; } bar; int *pi; float *pf; and mark X as "nonaddressable", I know that an assigment to *pi can't affect bar.x. But if Y isn't similarly marked, an assignment to *pf MIGHT affect bar.y unless I could somehow prove by value tracking that it can't.
Re: Incorrect bitfield aliasing with Tree SSA
> If that was really true, we would get this right. Well, this is true, I really don't understand why you keep denying that. Just grep the RTL expanders for MEM_KEEP_ALIAS_SET_P for example: `MEM_KEEP_ALIAS_SET_P (X)' In `mem' expressions, 1 if we should keep the alias set for this mem unchanged when we access a component. Set to 1, for example, when we are already in a non-addressable component of an aggregate. Stored in the `jump' field and printed as `/j'. > You guys have come up with a very weird idea of what non-addressability > means. I didn't invent it either, but everything is more or less documented. > These fields are all addressable, they are just not directly addressable. Right, that's just what is written in tree.h: /* Used in a FIELD_DECL to indicate that we cannot form the address of this component. */ #define DECL_NONADDRESSABLE_P(NODE) \ (FIELD_DECL_CHECK (NODE)->decl_common.decl_flag_3) -- Eric Botcazou
Re: Incorrect bitfield aliasing with Tree SSA
On 6/16/07, Eric Botcazou <[EMAIL PROTECTED]> wrote: > HMm, i'd just record it for all of them, since the [fields] are accessible > through a pointer to the structure. They are indeed accessible this way... > Just because you can't directly take the address of a bitfield doesn't > mean you can't access one through a pointer, which is the entire > purpose of knowing alias sets (knowing what a pointer dereference > could affect). ...but DECL_NONADDRESSABLE_P precisely means that the alias set used for accessing these fields at the RTL level is that of the containing structure: If that was really true, we would get this right. Adam has simply run with C into another form of the same discrepancy we have run into when we tried to enable struct aliasing with Ada, see PR 25737. You guys have come up with a very weird idea of what non-addressability means. These fields are all addressable, they are just not directly addressable.
Re: Incorrect bitfield aliasing with Tree SSA
> HMm, i'd just record it for all of them, since the [fields] are accessible > through a pointer to the structure. They are indeed accessible this way... > Just because you can't directly take the address of a bitfield doesn't > mean you can't access one through a pointer, which is the entire > purpose of knowing alias sets (knowing what a pointer dereference > could affect). ...but DECL_NONADDRESSABLE_P precisely means that the alias set used for accessing these fields at the RTL level is that of the containing structure: /* Return true if all nested component references handled by get_inner_reference in T are such that we should use the alias set provided by the object at the heart of T. This is true for non-addressable components (which don't have their own alias set), as well as components of objects in alias set zero. This later point is a special case wherein we wish to override the alias set used by the component, but we don't have per-FIELD_DECL assignable alias sets. */ bool component_uses_parent_alias_set (tree t) { while (1) { /* If we're at the end, it vacuously uses its own alias set. */ if (!handled_component_p (t)) return false; switch (TREE_CODE (t)) { case COMPONENT_REF: if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1))) return true; break; so the code in record_component_aliases is consistent with that. Adam has simply run with C into another form of the same discrepancy we have run into when we tried to enable struct aliasing with Ada, see PR 25737. -- Eric Botcazou
Re: Incorrect bitfield aliasing with Tree SSA
On 6/15/07, Adam Nemet <[EMAIL PROTECTED]> wrote: Daniel Berlin writes: > On 6/15/07, Adam Nemet <[EMAIL PROTECTED]> wrote: > > get_alias_set and internally record_component_aliases makes > > assumptions about the IR that are only valid in RTL. > > What is this assumption, exactly? That non-addressable fields are always accessed through alias set 0. For example: X: (set (mem A) ...) Y: (set (zero_extract (mem B) 2 2) ...) Let's say that A and B both point to the same type and have the same alias set 1. The bitfield store in Y would normally have the alias set of the field, let's say 2. Normally 2 would have to be recorded as an alias subset of 1. This is not done in RTL and the comment before record_component_aliases mentions this: /* Record that component types of TYPE, if any, are part of that type for aliasing purposes. For record types, we only record component types for fields that are marked addressable. HMm, i'd just record it for all of them, since the are accessible through a pointer to the structure. Just because you can't directly take the address of a bitfield doesn't mean you can't access one through a pointer, which is the entire purpose of knowing alias sets (knowing what a pointer dereference could affect). This should solve the problem without having to do anything IR specific.
Re: Incorrect bitfield aliasing with Tree SSA
Daniel Berlin writes: > On 6/15/07, Adam Nemet <[EMAIL PROTECTED]> wrote: > > get_alias_set and internally record_component_aliases makes > > assumptions about the IR that are only valid in RTL. > > What is this assumption, exactly? That non-addressable fields are always accessed through alias set 0. For example: X: (set (mem A) ...) Y: (set (zero_extract (mem B) 2 2) ...) Let's say that A and B both point to the same type and have the same alias set 1. The bitfield store in Y would normally have the alias set of the field, let's say 2. Normally 2 would have to be recorded as an alias subset of 1. This is not done in RTL and the comment before record_component_aliases mentions this: /* Record that component types of TYPE, if any, are part of that type for aliasing purposes. For record types, we only record component types for fields that are marked addressable. If I am not mistaken this is because the functions expanding RTL ensure that the alias set of the mem operand in Y has alias set 0. Or to quote expmed.c: /* We may be accessing data outside the field, which means we can alias adjacent data. */ if (MEM_P (op0)) { op0 = shallow_copy_rtx (op0); set_mem_alias_set (op0, 0); set_mem_expr (op0, 0); } Adam
Re: Incorrect bitfield aliasing with Tree SSA
On 6/15/07, Adam Nemet <[EMAIL PROTECTED]> wrote: get_alias_set and internally record_component_aliases makes assumptions about the IR that are only valid in RTL. What is this assumption, exactly?