[PATCH] Make alias_sets_conflict_p less conservative

[PATCH] Make alias_sets_conflict_p less conservative

[Richard Guenther]

This makes alias_sets_conflict_p less conservative.  rev 34373 (Kenner)
added a check that makes a structure containing a member with alias
set zero alias everything.  Which IMHO is non-obvious and pessimizes
for example the testcase in PR27799.  Richard, can you explain this
change?

I'll bootstrap and test this, but posted for enlightening comments early.
(I can imagine latent bugs that make this necessary, but not a
fundamental alias rule?)

Thanks,
Richard.

2008-03-04  Richard Guenther  <rguenther@suse.de>

	PR middle-end/27799
	* alias.c (alias_sets_conflict_p): A alias set zero member
	in a structure does not mean the structure aliases with
	everything.

	* gcc.dg/alias-2.c: Adjust.
	* gcc.dg/alias-12.c: New testcase.

Index: alias.c
===================================================================
*** alias.c	(revision 132816)
--- alias.c	(working copy)
*************** alias_sets_conflict_p (alias_set_type se
*** 325,341 ****
    /* See if the first alias set is a subset of the second.  */
    ase = get_alias_set_entry (set1);
    if (ase != 0
!       && (ase->has_zero_child
! 	  || splay_tree_lookup (ase->children,
! 				(splay_tree_key) set2)))
      return 1;
  
    /* Now do the same, but with the alias sets reversed.  */
    ase = get_alias_set_entry (set2);
    if (ase != 0
!       && (ase->has_zero_child
! 	  || splay_tree_lookup (ase->children,
! 				(splay_tree_key) set1)))
      return 1;
  
    /* The two alias sets are distinct and neither one is the
--- 325,339 ----
    /* See if the first alias set is a subset of the second.  */
    ase = get_alias_set_entry (set1);
    if (ase != 0
!       && splay_tree_lookup (ase->children,
! 			    (splay_tree_key) set2))
      return 1;
  
    /* Now do the same, but with the alias sets reversed.  */
    ase = get_alias_set_entry (set2);
    if (ase != 0
!       && splay_tree_lookup (ase->children,
! 			    (splay_tree_key) set1))
      return 1;
  
    /* The two alias sets are distinct and neither one is the
Index: testsuite/gcc.dg/alias-2.c
===================================================================
*** testsuite/gcc.dg/alias-2.c	(revision 132816)
--- testsuite/gcc.dg/alias-2.c	(working copy)
*************** struct foo {
*** 11,16 ****
  int
  sub1 (long long int foobar)
  {
!   struct foo *tmp = (struct foo *) &foobar; // { dg-warning "type-punned pointer might" "" }
    return tmp->i;
  }
--- 11,16 ----
  int
  sub1 (long long int foobar)
  {
!   struct foo *tmp = (struct foo *) &foobar; // { dg-warning "type-punned pointer will" "" }
    return tmp->i;
  }
Index: testsuite/gcc.dg/alias-12.c
===================================================================
*** testsuite/gcc.dg/alias-12.c	(revision 0)
--- testsuite/gcc.dg/alias-12.c	(revision 0)
***************
*** 0 ****
--- 1,27 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-optimized" } */
+ 
+ extern void abort (void);
+ 
+ struct X {double m; int x;};
+ struct Y {int y; short d;};
+ struct YY {int y; short d; char c;};
+ 
+ int foo(struct X *x,  struct Y *y)
+ {
+   x->x =  0;
+   y->y =  1;
+   if (x->x != 0)
+     abort ();
+ }
+ 
+ int foo_no(struct X *x,  struct YY *y)
+ {
+   x->x =  0;
+   y->y =  1;
+   if (x->x != 0)
+     abort ();
+ }
+ 
+ /* { dg-final { scan-tree-dump-not "abort" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Kenner]

> This makes alias_sets_conflict_p less conservative.  rev 34373 (Kenner)
> added a check that makes a structure containing a member with alias
> set zero alias everything.  Which IMHO is non-obvious and pessimizes
> for example the testcase in PR27799.  Richard, can you explain this
> change?

I'm not certain, but I think it goes like this: if a structure has
a member with alias set X (nonzero), we normally mark the alias sets
in such a way that the alias set of the structure as a whole conflicts
with alias set X.  But if X is zero, the subsetting mechanism doesn't
allow doing that.  So we have to do it explicitly, like in this code.

In other words, this is exactly analogous to the non-zero alias set
of a field case.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Daniel Berlin]

On Tue, Mar 4, 2008 at 6:55 PM, Richard Kenner
<kenner@vlsi1.ultra.nyu.edu> wrote:
> > This makes alias_sets_conflict_p less conservative.  rev 34373 (Kenner)
>  > added a check that makes a structure containing a member with alias
>  > set zero alias everything.  Which IMHO is non-obvious and pessimizes
>  > for example the testcase in PR27799.  Richard, can you explain this
>  > change?
>
>  I'm not certain, but I think it goes like this: if a structure has
>  a member with alias set X (nonzero), we normally mark the alias sets
>  in such a way that the alias set of the structure as a whole conflicts
>  with alias set X.  But if X is zero, the subsetting mechanism doesn't
>  allow doing that.  So we have to do it explicitly, like in this code.
>
>  In other words, this is exactly analogous to the non-zero alias set
>  of a field case.
>

Sadly, you are right about how the subsetting mechanism works, but he
is right in what the result we want should be.

This is because the the type based rules (at least for C) say "access
through pointer char can validly alias anything" but not "access
through pointer to anything can validly alias char".

Because alias_sets_conflicts_p checks both ways, it ends up claiming
the second statement is true as well.

In reality, you need a directional aliasing test here, not
alias_sets_conflict_p (IE you want something that says "can a pointer
of this point to this type over there)

--Dan

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Kenner]

> This is because the the type based rules (at least for C) say "access
> through pointer char can validly alias anything" but not "access
> through pointer to anything can validly alias char".

I note there is no char * in sight there.  Are we, by some chance, assigning
char to alias set zero? That seems wrong.  Rather char * should be
marked as type-pointed-to-can-alias-all.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Guenther]

On Tue, 4 Mar 2008, Richard Kenner wrote:

> > This is because the the type based rules (at least for C) say "access
> > through pointer char can validly alias anything" but not "access
> > through pointer to anything can validly alias char".
> 
> I note there is no char * in sight there.  Are we, by some chance, assigning
> char to alias set zero? That seems wrong.  Rather char * should be
> marked as type-pointed-to-can-alias-all.

Yes, char is assigned alias set zero.  And this is correct.

  char a[4];
  int *p;

an access through *p conflicts with a.  (note there is no char * involved
here)

Richard.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Paolo Bonzini]

> Yes, char is assigned alias set zero.  And this is correct.
> 
>   char a[4];
>   int *p;
> 
> an access through *p conflicts with a.  (note there is no char * involved
> here)

Would it be considered a good cleanup to assign it a different alias 
set, and make C char* a TYPE_REF_CAN_ALIAS_ALL variant?  Other languages 
may not have this behavior.

Paolo

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Eric Botcazou]

> Would it be considered a good cleanup to assign it a different alias
> set, and make C char* a TYPE_REF_CAN_ALIAS_ALL variant?  Other languages
> may not have this behavior.

This is done only the C family of languages.  In Ada we do something similar 
for our own "universal aliasing" type.

-- 
Eric Botcazou

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Paolo Bonzini]

Eric Botcazou wrote:
>> Would it be considered a good cleanup to assign it a different alias
>> set, and make C char* a TYPE_REF_CAN_ALIAS_ALL variant?  Other languages
>> may not have this behavior.
> 
> This is done only the C family of languages.  In Ada we do something similar 
> for our own "universal aliasing" type.

Yes, I was asking if it was meaningful to do it for C too -- especially 
for LTO it could make sense.

Paolo

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Eric Botcazou]

> Yes, I was asking if it was meaningful to do it for C too -- especially
> for LTO it could make sense.

You probably misunderstood my message.  Giving char alias set 0 is C-family 
specific, in Ada we give alias set 0 to something else.  This is orthogonal 
to the TYPE_REF_CAN_ALIAS_ALL flag on pointers.

-- 
Eric Botcazou

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Kenner]

> Yes, I was asking if it was meaningful to do it for C too -- especially 
> for LTO it could make sense.

If you work globally, you can do far better and can do essentially the same
as we do for Ada.  What you do is to detect all cases of other pointers
(e.g., int *) that get assigned from char * and use a TYPE_CAN_ALIAS_ALL
variant of that pointer for those int * variables.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Kenner]

> Yes, char is assigned alias set zero.  And this is correct.
> 
>   char a[4];
>   int *p;
> 
> an access through *p conflicts with a. 

By what rule?  I was under the impression that this was a special rule
applying to "char *".

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Guenther]

On Wed, 5 Mar 2008, Richard Kenner wrote:

> > Yes, char is assigned alias set zero.  And this is correct.
> > 
> >   char a[4];
> >   int *p;
> > 
> > an access through *p conflicts with a. 
> 
> By what rule?  I was under the impression that this was a special rule
> applying to "char *".

6.5/7

  An object shall have its stored value accessed only by an lvalue
  expression that has one of the following types:

  ...

  - a character type

you are right if for

  char c[4];

c has a declared type of char.  Which would make

  char c[4];
  int *p = c;
  *p = 0;

undefined.  But the above is commonly used enough to make any
declared character array handled the same as allocated storage is.

Richard.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Kenner]

> you are right if for
> 
>   char c[4];
> 
> c has a declared type of char.  Which would make
> 
>   char c[4];
>   int *p = c;
>   *p = 0;
> 
> undefined.  But the above is commonly used enough to make any
> declared character array handled the same as allocated storage is.

So you feel that we need to support it?

But we're actually creating an object of char * here in that second
statement.  Perhaps we can use that knowlege somehow.

But pessimizing "char" with no pointers in sight just to support this
seems very bad.  There must be some approach that works.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Guenther]

On Wed, 5 Mar 2008, Richard Kenner wrote:

> > you are right if for
> > 
> >   char c[4];
> > 
> > c has a declared type of char.  Which would make
> > 
> >   char c[4];
> >   int *p = c;
> >   *p = 0;
> > 
> > undefined.  But the above is commonly used enough to make any
> > declared character array handled the same as allocated storage is.
> 
> So you feel that we need to support it?
> 
> But we're actually creating an object of char * here in that second
> statement.  Perhaps we can use that knowlege somehow.
> 
> But pessimizing "char" with no pointers in sight just to support this
> seems very bad.  There must be some approach that works.

Well, my C-fu is from interpreting the words in the standard and looking
at existing use.

So you agree that your change introducing this handling of alias set zero
was not with the fact in mind that C assigns alias set zero to 'char'?

Note that apart from the bug in RTL dse which is uncovered by the patch
everything still seems to work fine.  The fact that we assign alias set
zero to char should not matter, and I still do not understand the
reasoning behind

struct alias_set_entry GTY(())
{
...
  /* Nonzero if would have a child of zero: this effectively makes this
     alias set the same as alias set zero.  */
  int has_zero_child;

and the purpose and reasoning of

alias_sets_conflict_p (alias_set_type set1, alias_set_type set2)
{
...
  /* See if the first alias set is a subset of the second.  */
  ase = get_alias_set_entry (set1);
  if (ase != 0
      && (ase->has_zero_child
        ^^^^^^^^^^^^^^^^^^^^^^
          || splay_tree_lookup (ase->children,
                                (splay_tree_key) set2)))
    return 1;

Can you explain again why a alias-set zero child of set1 or set2
makes any alias set conflict with such set?  This effectively makes
a set with an alias-set zero child equivalent to alias-set zero itself,
which doesn't make sense.

In which case would the above (alias-set zero member) happen for Ada
(which does not assign alias set zero to char, but to "something else")?

Thanks,
Richard.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Kenner]

> So you agree that your change introducing this handling of alias set zero
> was not with the fact in mind that C assigns alias set zero to 'char'?

I don't understand precisely what you're asking here, but let me try to
answer.  My change was made because it's *required* by the rules we're using
to determine alias sets and subsetting rules.  It's been quite a while,
but I do *not* think it was motivated by any bug, just a realization that
the current code was wrong.

I'm certain that the change was not *motivated* by the fact that C's 'char'
is alias set zero.  I'm not even sure if that was the case back when the
change was made.  I doubt I was thinking about that issue then.

> Can you explain again why a alias-set zero child of set1 or set2
> makes any alias set conflict with such set?  

For the same reason that the alias set of a parent conflicts with the
alias set of a child if it's nonzero.

> This effectively makes a set with an alias-set zero child equivalent
> to alias-set zero itself, which doesn't make sense.

It's not equivalent, but close.

I really feel that the problem here is the assignment of alias set zero
to C's 'char'.  It's *totally* unnecessary.  char * should certainly
be TYPE_REF_CAN_ALIAS_ALL and perhaps char[] should be alias set zero,
but not 'char'.  The assumption here is that having *objects* (as opposed
to indirect references) of alias set zero is relatively rare.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Guenther]

On Wed, 5 Mar 2008, Richard Kenner wrote:

> > So you agree that your change introducing this handling of alias set zero
> > was not with the fact in mind that C assigns alias set zero to 'char'?
> 
> I don't understand precisely what you're asking here, but let me try to
> answer.  My change was made because it's *required* by the rules we're using
> to determine alias sets and subsetting rules.  It's been quite a while,
> but I do *not* think it was motivated by any bug, just a realization that
> the current code was wrong.
> 
> I'm certain that the change was not *motivated* by the fact that C's 'char'
> is alias set zero.  I'm not even sure if that was the case back when the
> change was made.  I doubt I was thinking about that issue then.
> 
> > Can you explain again why a alias-set zero child of set1 or set2
> > makes any alias set conflict with such set?  
> 
> For the same reason that the alias set of a parent conflicts with the
> alias set of a child if it's nonzero.

I don't see that.  in alias_sets_conflict_p (set1, set2) we ask if
set1 conflicts with set2.  In this context it is only relevant if
either of set1 or set2 is alias set zero (which implicitly contains
all alias sets in its child set) or whether set1 is contained in set2
or set2 is contained in set1.

It is not relevant if set2 contains alias set zero.

Oh - ok.  I can follow your logic.  If set2 contains alias set zero it
contains all alias sets, but then

> > This effectively makes a set with an alias-set zero child equivalent
> > to alias-set zero itself, which doesn't make sense.
> 
> It's not equivalent, but close.

It _is_ equivalent to alias set zero, as every member in either set
is a member of the other set.

Now, lets assume we don't want a alias set zero member to leak all its
children.  Then my patch does exactly that.  (whether giving alias
set zero to char makes sense - apart from making *(char *) alias set
zero this way automatically - is another question, but this way
things fall out nicely at least)

The question remains, in which practical cases we _do_ want the
behavior that an alias set zero member makes the set itself effectively
alias set zero.  If you look where subsets are added, it happens
from record_component_aliases (I can't think of a C structure
where we want this behavior), and from get_alias_set in the case of
computing DECL_POINTER_ALIAS_SET which is computed from the pointed
to type again (it wouldn't work for char here).

So even if it somewhat breaks the symmetry of alias set zero I believe
my patch is the right thing to do, otherwise there is no need to for
example add any further children once the parent has_zero_child
(which we should rename to is_alias_set_zero).

Richard.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Kenner]

> > > This effectively makes a set with an alias-set zero child equivalent
> > > to alias-set zero itself, which doesn't make sense.
> > 
> > It's not equivalent, but close.
> 
> It _is_ equivalent to alias set zero, as every member in either set
> is a member of the other set.

This is a distinction without a difference.  Just because something
conflicts with all other alias sets doesn't mean that it *is* alias
set zero, just that it *acts* like it.

> Now, lets assume we don't want a alias set zero member to leak all its
> children.  

But why do you assume that?  It's wrong.  It's no more correct than
saying that it shouldn't "leak" a child of some other particular alias set.

> The question remains, in which practical cases we _do_ want the
> behavior that an alias set zero member makes the set itself effectively
> alias set zero. 

In any case where a member is alias set zero for a reason.

> (I can't think of a C structure where we want this behavior)

I can't either, but the fix is to not make 'char' alias set zero!

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Guenther]

On Wed, 5 Mar 2008, Richard Kenner wrote:

> > > > This effectively makes a set with an alias-set zero child equivalent
> > > > to alias-set zero itself, which doesn't make sense.
> > > 
> > > It's not equivalent, but close.
> > 
> > It _is_ equivalent to alias set zero, as every member in either set
> > is a member of the other set.
> 
> This is a distinction without a difference.  Just because something
> conflicts with all other alias sets doesn't mean that it *is* alias
> set zero, just that it *acts* like it.
> 
> > Now, lets assume we don't want a alias set zero member to leak all its
> > children.  
> 
> But why do you assume that?  It's wrong.  It's no more correct than
> saying that it shouldn't "leak" a child of some other particular alias set.
> 
> > The question remains, in which practical cases we _do_ want the
> > behavior that an alias set zero member makes the set itself effectively
> > alias set zero. 
> 
> In any case where a member is alias set zero for a reason.
> 
> > (I can't think of a C structure where we want this behavior)
> 
> I can't either, but the fix is to not make 'char' alias set zero!

Well, that's true.  But this fix will be way more involved than my
patch which works as well (fix for PR35472 is in testing).

So I'm still inclined to go with my patch with adding a big'n'fat
comment.

Richard.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Kenner]

> So I'm still inclined to go with my patch with adding a big'n'fat
> comment.

I think your patch is wrong: it says that two alias set don't conflict
when, in fact, they do.

Bugs caused by this are notoriously hard to find because they come and go
so I'd be very much against introducing this into GCC even if the only
bug is a latent one.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Guenther]

On Wed, 5 Mar 2008, Richard Kenner wrote:

> > So I'm still inclined to go with my patch with adding a big'n'fat
> > comment.
> 
> I think your patch is wrong: it says that two alias set don't conflict
> when, in fact, they do.
> 
> Bugs caused by this are notoriously hard to find because they come and go
> so I'd be very much against introducing this into GCC even if the only
> bug is a latent one.

Meh.  It is not going to work out to make char not alias set zero.
Look:

alias_set_type
c_common_get_alias_set (tree t)
{
...
  /* The C standard guarantees that any object may be accessed via an
     lvalue that has character type.  */
  if (t == char_type_node
      || t == signed_char_type_node
      || t == unsigned_char_type_node)
    return 0;

an 'lvalue' isn't a pointer, so I don't see how you can possibly preserve
(with reasonable amount of hackery) Cs special handling of character
lvalues.

But - Joseph, do you have any idea if it in theory could be made to
work with char not being alias set zero?  The FE would need to mark
every lvalue of type char with a special flag.

Thanks,
Richard.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Michael Matz]

Hi,

On Wed, 5 Mar 2008, Richard Guenther wrote:

> But - Joseph, do you have any idea if it in theory could be made to work 
> with char not being alias set zero?  The FE would need to mark every 
> lvalue of type char with a special flag.

If that should be possible, it's no different to making 'char' have alias 
set zero.  Given:

struct S {char c; int i;};
struct T {double d;};

f () {
  struct S s;
  s.c = 0;
}

Here the lvalue s.c would then have the "special flag" (i suppose the 
semantic you had in mind for that flag would be "alias everything"), so it 
would conflict with everything which of course it can't.  It won't 
conflict with T.d for instance, so we're back to square one.


Ciao,
Michael.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Guenther]

On Wed, 5 Mar 2008, Michael Matz wrote:

> Hi,
> 
> On Wed, 5 Mar 2008, Richard Guenther wrote:
> 
> > But - Joseph, do you have any idea if it in theory could be made to work 
> > with char not being alias set zero?  The FE would need to mark every 
> > lvalue of type char with a special flag.
> 
> If that should be possible, it's no different to making 'char' have alias 
> set zero.  Given:
> 
> struct S {char c; int i;};
> struct T {double d;};
> 
> f () {
>   struct S s;
>   s.c = 0;
> }
> 
> Here the lvalue s.c would then have the "special flag" (i suppose the 
> semantic you had in mind for that flag would be "alias everything"), so it 
> would conflict with everything which of course it can't.  It won't 
> conflict with T.d for instance, so we're back to square one.

Hm.  As I said I know of enough code that uses an array of chars as
"memory", even if embedded in a struct.  So,

struct S { int size; char mem[1]; } s;
struct T { double d; } *p;

double f ()
{
  p->d = 1.0;
  s.mem[0] = 0;
  return p->d;
}

here indeed the store to s.mem[0] should conflict with the store and
load from p->d.

But in the case we are trying to fix, the current alias behavior would
make

  s.size = 0;

conflict with the store and load from p->d, which is incorrect.  That
said, somehow we end up asking for the alias set of 's' here instead
of that for 's.size' - or we make that one of 's.size' a different
one from its type.  Which would move the problem we run into in
PR27799 to get_alias_set and away from alias_sets_conflict_p.

Richard.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Kenner]

> But in the case we are trying to fix, the current alias behavior would
> make
> 
>   s.size = 0;
> 
> conflict with the store and load from p->d, which is incorrect.

I don't think so.  In that case, we look at the alias set of s.size, not of s.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Guenther]

On Wed, 5 Mar 2008, Richard Kenner wrote:

> > But in the case we are trying to fix, the current alias behavior would
> > make
> > 
> >   s.size = 0;
> > 
> > conflict with the store and load from p->d, which is incorrect.
> 
> I don't think so.  In that case, we look at the alias set of s.size, not of s.

Ok, so the problem (of PR27799) is that our tree aliasing machinery
creates SMTs (structure-memory-tags) that represent all structures
with a given type.  TBAA relations here are computed by asking wheter
for example a pointer can access struct X which is done by asking for
alias_sets_conflict_p (get_alias_set (*ptr), get_alias_set (struct-type))
which in this case returns true (as struc-type has a char member).
[this all happens in may_alias_p]

Later during operand scanning we (could) ask again, but only the
same question -- does the access p->x alias a SMT?  And the answer
would be the same.  [access_can_touch_variable]

So we are lost here, as we obviously cannot ask the question this way
with the current scheme. (?)

To recap:

struct A { int i; char c; };
struct B { float f; };

the question we ask is, can you access any struct A through a pointer
to struct B?  And, can ((struct B *)p)->f touch any struct A?

For this sort of questions (with char having alias set zero and the
subsetting work as is), we can only answer yes.  With my patch
we can start to say no here.

Richard.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Kenner]

> Ok, so the problem (of PR27799) is that our tree aliasing machinery
> creates SMTs (structure-memory-tags) that represent all structures
> with a given type.  TBAA relations here are computed by asking wheter
> for example a pointer can access struct X which is done by asking for
> alias_sets_conflict_p (get_alias_set (*ptr), get_alias_set (struct-type))
> which in this case returns true (as struc-type has a char member).
> [this all happens in may_alias_p]

That seems *very* wrong and very inefficient.

The definition of the alias set for a field x.y as used by the RTL
passes has always been:

if alias_set (x) == 0 (not this case), then alias set zero
else if y is addressable, then alias_set (y)
else alias_set (x)

If the tree level does anything else, it is *seriously* inefficient since
the entire aliasing subsetting mechanism was designed around alias sets of
fields being computed in the above way.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Guenther]

On Wed, 5 Mar 2008, Richard Kenner wrote:

> > Ok, so the problem (of PR27799) is that our tree aliasing machinery
> > creates SMTs (structure-memory-tags) that represent all structures
> > with a given type.  TBAA relations here are computed by asking wheter
> > for example a pointer can access struct X which is done by asking for
> > alias_sets_conflict_p (get_alias_set (*ptr), get_alias_set (struct-type))
> > which in this case returns true (as struc-type has a char member).
> > [this all happens in may_alias_p]
> 
> That seems *very* wrong and very inefficient.

It's not wrong and not inefficient.  tree aliasing just models
alias-sets as SMTs, thus tries to re-create the subsetting (SMTs
have a set of other SMTs it aliases) by this querying.  Obviously
it doesn't work out in this case ;)

So it basically asks -- is struct A in the alias set of struct B.
Maybe it shouldn't use alias_sets_conflict_p for this kind of query
but should use alias_set_subset_of (), but that would need a similar
fix for set2->has_zero_subset:

/* Return true if the first alias set is a subset of the second.  */

bool
alias_set_subset_of (alias_set_type set1, alias_set_type set2)
{
  alias_set_entry ase;

  /* Everything is a subset of the "aliases everything" set.  */
  if (set2 == 0)
    return true;

  /* Otherwise, check if set1 is a subset of set2.  */
  ase = get_alias_set_entry (set2);
  if (ase != 0
      && (splay_tree_lookup (ase->children,
                             (splay_tree_key) set1)))
    return true;
  return false;
}

so it wouldn't help either.

> The definition of the alias set for a field x.y as used by the RTL
> passes has always been:
> 
> if alias_set (x) == 0 (not this case), then alias set zero
> else if y is addressable, then alias_set (y)
> else alias_set (x)
> 
> If the tree level does anything else, it is *seriously* inefficient since
> the entire aliasing subsetting mechanism was designed around alias sets of
> fields being computed in the above way.

but alias_set (x) _is_ zero in this case.  Because x has a char
member.

Richard.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Kenner]

> So it basically asks -- is struct A in the alias set of struct B.

But that's *totally wrong* if the two access are, for example, a.x and
b.y and (as is usually the case in C) x and y are addressable.  In
that case, the alias sets of A and B are *completely irrelevant* and
*all* you care about are the alias sets of x and y.  Any code that does
something else is broken.

> > The definition of the alias set for a field x.y as used by the RTL
> > passes has always been:
> > 
> > if alias_set (x) == 0 (not this case), then alias set zero
> > else if y is addressable, then alias_set (y)
> > else alias_set (x)
> > 
> > If the tree level does anything else, it is *seriously* inefficient since
> > the entire aliasing subsetting mechanism was designed around alias sets of
> > fields being computed in the above way.
> 
> but alias_set (x) _is_ zero in this case.  Because x has a char
> member.

NO!  We DO NOT set the set to zero, but rather handle it as conflicting
with all other alias sets.  The difference between those is *precisely*
this algorithm.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Guenther]

On Wed, 5 Mar 2008, Richard Kenner wrote:

> > So it basically asks -- is struct A in the alias set of struct B.
> 
> But that's *totally wrong* if the two access are, for example, a.x and
> b.y and (as is usually the case in C) x and y are addressable.  In
> that case, the alias sets of A and B are *completely irrelevant* and
> *all* you care about are the alias sets of x and y.  Any code that does
> something else is broken.
> 
> > > The definition of the alias set for a field x.y as used by the RTL
> > > passes has always been:
> > > 
> > > if alias_set (x) == 0 (not this case), then alias set zero
> > > else if y is addressable, then alias_set (y)
> > > else alias_set (x)
> > > 
> > > If the tree level does anything else, it is *seriously* inefficient since
> > > the entire aliasing subsetting mechanism was designed around alias sets of
> > > fields being computed in the above way.
> > 
> > but alias_set (x) _is_ zero in this case.  Because x has a char
> > member.
> 
> NO!  We DO NOT set the set to zero, but rather handle it as conflicting
> with all other alias sets.  The difference between those is *precisely*
> this algorithm.

Err, right.  But tree aliasing is computing a representation for TBAA,
using alias set conflict queries but _not_ looking at individual accesses.

So, is alias_set_subset_of () wrong as currently implemented?  Does
it lack the ase->has_zero_child test in your opinion?  Otherwise I'll
try using that for these queries.

Richard.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Guenther]

On Wed, 5 Mar 2008, Richard Guenther wrote:

> On Wed, 5 Mar 2008, Richard Kenner wrote:
> 
> > > So it basically asks -- is struct A in the alias set of struct B.
> > 
> > But that's *totally wrong* if the two access are, for example, a.x and
> > b.y and (as is usually the case in C) x and y are addressable.  In
> > that case, the alias sets of A and B are *completely irrelevant* and
> > *all* you care about are the alias sets of x and y.  Any code that does
> > something else is broken.
> > 
> > > > The definition of the alias set for a field x.y as used by the RTL
> > > > passes has always been:
> > > > 
> > > > if alias_set (x) == 0 (not this case), then alias set zero
> > > > else if y is addressable, then alias_set (y)
> > > > else alias_set (x)
> > > > 
> > > > If the tree level does anything else, it is *seriously* inefficient since
> > > > the entire aliasing subsetting mechanism was designed around alias sets of
> > > > fields being computed in the above way.
> > > 
> > > but alias_set (x) _is_ zero in this case.  Because x has a char
> > > member.
> > 
> > NO!  We DO NOT set the set to zero, but rather handle it as conflicting
> > with all other alias sets.  The difference between those is *precisely*
> > this algorithm.
> 
> Err, right.  But tree aliasing is computing a representation for TBAA,
> using alias set conflict queries but _not_ looking at individual accesses.
> 
> So, is alias_set_subset_of () wrong as currently implemented?  Does
> it lack the ase->has_zero_child test in your opinion?  Otherwise I'll
> try using that for these queries.

Which means like the following (untested) patch, also fixes PR27799.

Richard.

Index: tree-ssa-alias.c
===================================================================
*** tree-ssa-alias.c	(revision 132898)
--- tree-ssa-alias.c	(working copy)
*************** may_alias_p (tree ptr, alias_set_type me
*** 2869,2875 ****
        alias_stats.tbaa_queries++;
  
        /* If the alias sets don't conflict then MEM cannot alias VAR.  */
!       if (!alias_sets_conflict_p (mem_alias_set, var_alias_set))
  	{
  	  alias_stats.alias_noalias++;
  	  alias_stats.tbaa_resolved++;
--- 2869,2875 ----
        alias_stats.tbaa_queries++;
  
        /* If the alias sets don't conflict then MEM cannot alias VAR.  */
!       if (!alias_set_subset_of (mem_alias_set, var_alias_set))
  	{
  	  alias_stats.alias_noalias++;
  	  alias_stats.tbaa_resolved++;
Index: tree-ssa-structalias.c
===================================================================
*** tree-ssa-structalias.c	(revision 132898)
--- tree-ssa-structalias.c	(working copy)
*************** set_uids_in_ptset (tree ptr, bitmap into
*** 4780,4786 ****
  		  var_alias_set = get_alias_set (sft);
  		  if (no_tbaa_pruning
  		      || (!is_derefed && !vi->directly_dereferenced)
! 		      || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
  		    {
  		      bitmap_set_bit (into, DECL_UID (sft));
  		      
--- 4780,4786 ----
  		  var_alias_set = get_alias_set (sft);
  		  if (no_tbaa_pruning
  		      || (!is_derefed && !vi->directly_dereferenced)
! 		      || alias_set_subset_of (ptr_alias_set, var_alias_set))
  		    {
  		      bitmap_set_bit (into, DECL_UID (sft));
  		      
*************** set_uids_in_ptset (tree ptr, bitmap into
*** 4808,4814 ****
  		  var_alias_set = get_alias_set (vi->decl);
  		  if (no_tbaa_pruning
  		      || (!is_derefed && !vi->directly_dereferenced)
! 		      || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
  		    bitmap_set_bit (into, DECL_UID (vi->decl));
  		}
  	    }
--- 4808,4814 ----
  		  var_alias_set = get_alias_set (vi->decl);
  		  if (no_tbaa_pruning
  		      || (!is_derefed && !vi->directly_dereferenced)
! 		      || alias_set_subset_of (ptr_alias_set, var_alias_set))
  		    bitmap_set_bit (into, DECL_UID (vi->decl));
  		}
  	    }

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Daniel Berlin]

On Wed, Mar 5, 2008 at 11:21 AM, Richard Guenther <rguenther@suse.de> wrote:
>
>  Which means like the following (untested) patch, also fixes PR27799.
>
>  Richard.
>

This looks right to me because we always know which one is the pointer
and which one is the pointed-to var.
So it's fine assuming it passes bootstrap and regtest

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Guenther]

On Wed, 5 Mar 2008, Daniel Berlin wrote:

> On Wed, Mar 5, 2008 at 11:21 AM, Richard Guenther <rguenther@suse.de> wrote:
> >
> >  Which means like the following (untested) patch, also fixes PR27799.
> >
> >  Richard.
> >
> 
> This looks right to me because we always know which one is the pointer
> and which one is the pointed-to var.
> So it's fine assuming it passes bootstrap and regtest

It doesn't work.

Richard.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Daniel Berlin]

On Wed, Mar 5, 2008 at 11:55 AM, Richard Guenther <rguenther@suse.de> wrote:
>
> On Wed, 5 Mar 2008, Daniel Berlin wrote:
>
>  > On Wed, Mar 5, 2008 at 11:21 AM, Richard Guenther <rguenther@suse.de> wrote:
>  > >
>  > >  Which means like the following (untested) patch, also fixes PR27799.
>  > >
>  > >  Richard.
>  > >
>  >
>  > This looks right to me because we always know which one is the pointer
>  > and which one is the pointed-to var.
>  > So it's fine assuming it passes bootstrap and regtest
>
>  It doesn't work.
>

You reversed the arguments.

alias_set_subset_of tells you if the first is a subset of the second.

So you want to know if the var is a subset (actually subset or equal
to) of the ptr.
The way the arguments are in your patch, you are asking if ptr is a
subset of var.
>

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Kenner]

> Err, right.  But tree aliasing is computing a representation for TBAA,
> using alias set conflict queries but _not_ looking at individual accesses.

That seems quite wrong to me.

> So, is alias_set_subset_of () wrong as currently implemented?  Does
> it lack the ase->has_zero_child test in your opinion?  Otherwise I'll
> try using that for these queries.

I don't know enough to answer those questions.

What I *do* know is that if you have x.y, with y addressable, any code
that looks at the alias set of X *for any reason* is broken.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Guenther]

On Wed, 5 Mar 2008, Richard Kenner wrote:

> > Err, right.  But tree aliasing is computing a representation for TBAA,
> > using alias set conflict queries but _not_ looking at individual accesses.
> 
> That seems quite wrong to me.
> 
> > So, is alias_set_subset_of () wrong as currently implemented?  Does
> > it lack the ase->has_zero_child test in your opinion?  Otherwise I'll
> > try using that for these queries.
> 
> I don't know enough to answer those questions.

That is sad, because you knew enough to fix exactly the same code
in alias_sets_conflict_p.

> What I *do* know is that if you have x.y, with y addressable, any code
> that looks at the alias set of X *for any reason* is broken.

Well, you obviously do not have enough knowledge of the alias 
representation used in tree-ssa and I won't try to start to explain.
If you want, take the testcase in PR27799, build with
-O2 -fdump-tree-salias-vops-details and look at the 052t.salias dump.

Richard.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Kenner]

> That is sad, because you knew enough to fix exactly the same code
> in alias_sets_conflict_p.

Yes, but you're now asking about a different set of functions used in
different ways and ...

> Well, you obviously do not have enough knowledge of the alias 
> representation used in tree-ssa

... this is quite correct.

But if it can't handle very simple cases correctly, I'd say it has some
serious problems.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Daniel Berlin]

On Wed, Mar 5, 2008 at 11:30 AM, Richard Kenner
<kenner@vlsi1.ultra.nyu.edu> wrote:
> > That is sad, because you knew enough to fix exactly the same code
>  > in alias_sets_conflict_p.
>
>  Yes, but you're now asking about a different set of functions used in
>  different ways and ...
>
>
>  > Well, you obviously do not have enough knowledge of the alias
>  > representation used in tree-ssa
>
>  ... this is quite correct.
>
>  But if it can't handle very simple cases correctly, I'd say it has some
>  serious problems.

I await your design for a completely accurate def-use chain
representation for memory accesses that does not take infinite amounts
of memory at compile time.
Until then, i have to laugh at your claim of "serious problems".
We knew what we were doing when we made it, and we knew it would have
some issues that would take further disambiguation to solve.
This just happens to be one of those cases.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Michael Matz]

Hi,

On Wed, 5 Mar 2008, Richard Kenner wrote:

> > > > This effectively makes a set with an alias-set zero child equivalent
> > > > to alias-set zero itself, which doesn't make sense.
> > > 
> > > It's not equivalent, but close.
> > 
> > It _is_ equivalent to alias set zero, as every member in either set
> > is a member of the other set.
> 
> This is a distinction without a difference.  Just because something
> conflicts with all other alias sets doesn't mean that it *is* alias
> set zero, just that it *acts* like it.

Well, if it acts like set zero, then it's equivalent to set zero, so we 
can simply use set zero in places where we formerly used set X (now found 
to be equivalent to zero).  If it's not distinguishable from set zero 
(except by it's number) there's no reason for it to exist.

> > The question remains, in which practical cases we _do_ want the
> > behavior that an alias set zero member makes the set itself effectively
> > alias set zero. 
> 
> In any case where a member is alias set zero for a reason.

I think this would still fail (or be suboptimal, imprecise, whatever), if 
char wouldn't have set zero, but e.g. char* would have.  Namely in this 
situation:

struct S { char *p; int i;};
struct T { double d; };

Now S.p would have alias set zero, and again accesses to the whole S would 
again conflict with everything (because it contains a member of set zero).  
This is clearly wrong.  An access to *S.p can alias everything, but not an 
access to S (or even to S.p, which itself can only conflict with 
accesses through any other char**).

Is it possible that our subsetting of alias sets based on structure 
members is non-sensical?  After all, in the end real accesses conflict 
with each other, so they are the ones with alias sets.  And for accesses 
we have the final type, for which we can determine conflict sets, I don't 
see why we would have to make all member sets subsets of the alias set of 
structure types to implement that.

Alternatively I think we are confused about what the alias set numbers on 
types actually mean. In particular I think we are confusing accesses to 
objects of type T and accesses through pointer to type T and glob them 
together.

Maybe the alias set of struct S needs to conflict with the alias sets of 
all _pointers_ to member types (not to alias sets of member types itself).  
Hmm.


Ciao,
Michael.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Kenner]

> Well, if it acts like set zero, then it's equivalent to set zero, so we 
> can simply use set zero in places where we formerly used set X (now found 
> to be equivalent to zero).  If it's not distinguishable from set zero 
> (except by it's number) there's no reason for it to exist.

Sure there is.  For one thing, if we set the alias set to zero, then
an access to a field inside the struct of nonzero alias set would be
treated as zero.  Moreover, is it really the case that the *only* thing we
do with alias sets is check for conflicts and, if so, will that always
be the case?  Why lose information?

> struct S { char *p; int i;};
> struct T { double d; };
> 
> Now S.p would have alias set zero, 

No, it wouldn't.  char * isn't alias set zero.  It's marked as
TYPE_REF_CAN_ALIAS_ALL, which means that *S.p is alias set zero, not
S.p itself.

> Is it possible that our subsetting of alias sets based on structure 
> members is non-sensical?

No, not at all.  It's *quite* important, actually.

> Alternatively I think we are confused about what the alias set numbers on 
> types actually mean. In particular I think we are confusing accesses to 
> objects of type T and accesses through pointer to type T and glob them 
> together.

There has been a discussion a long time ago about differentiating precisely
those two types of objects.  But the difference is very small except in
the case where you don't take the address of an object.  But that latter
case, except for globals, is one we can and do detect.  So I think this would
add lots of complexity and buy little.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Guenther]

On Tue, 4 Mar 2008, Richard Kenner wrote:

> > This makes alias_sets_conflict_p less conservative.  rev 34373 (Kenner)
> > added a check that makes a structure containing a member with alias
> > set zero alias everything.  Which IMHO is non-obvious and pessimizes
> > for example the testcase in PR27799.  Richard, can you explain this
> > change?
> 
> I'm not certain, but I think it goes like this: if a structure has
> a member with alias set X (nonzero), we normally mark the alias sets
> in such a way that the alias set of the structure as a whole conflicts
> with alias set X.  But if X is zero, the subsetting mechanism doesn't
> allow doing that.  So we have to do it explicitly, like in this code.

Well, this is not what happens.  The subsetting code doesn't allow
for _sub_setting alias set zero, not for putting alias set zero in
a subset.

So, if we have

struct S { int i; char c; };
struct B { double x; };

then we at the moment say that the alias sets of S and B conflict
just because S has a subset that includes alias set zero.

This is bogus.  Alias set zero only comes into play if either
argument of alias_sets_conflict_p is zero, which is handled by
the alias_sets_must_conflict_p code already.

It actually doesn't matter if we insert alias set zero into subsets
at all here, as alias set zero is special.

> In other words, this is exactly analogous to the non-zero alias set
> of a field case.

?  It is not.

The patch bootstrapped fine with a single failure,

FAIL: gcc.c-torture/execute/20071219-1.c execution

where it looks we get things right on the tree level but break it
on the RTL level.  (It's test3 () that is broken, from a quick
look we DSE *p = a; which of course is wrong as p points to b)

Richard.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Kenner]

> So, if we have
> 
> struct S { int i; char c; };
> struct B { double x; };
> 
> then we at the moment say that the alias sets of S and B conflict
> just because S has a subset that includes alias set zero.

As I asked in a different message, why does char have alias set zero?
*That's* what seems bogus to me.  Not having to do that is exactly why
TYPE_REF_CAN_ALIAS_ALL exists in the first place!  There's nothing special
about "char", but only about "char *".

> This is bogus.  Alias set zero only comes into play if either
> argument of alias_sets_conflict_p is zero, which is handled by
> the alias_sets_must_conflict_p code already.

I disagree.  Unless field C is nonaddressable (not the case in C),
some accesses to struct S will be accessing that field.  Those will be
accessing something in alias set zero.  That must conflict with any other
reference and that's what the code does.

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Mark Mitchell]

Richard Kenner wrote:

> As I asked in a different message, why does char have alias set zero?
> *That's* what seems bogus to me.  Not having to do that is exactly why
> TYPE_REF_CAN_ALIAS_ALL exists in the first place!  There's nothing special
> about "char", but only about "char *".

Although this debate seems to have died down, I found it in plowing 
through back email.  I agree that Richard G.'s original proposed patch 
to alias_set_conflicts_p (which appears to have gone into limbo anyhow) 
  seems wrong, and that alias set zero shouldn't be special with respect 
to the handling of children of structures.

However, I do think that people may well write code like this:

   __attribute__((aligned)) char buffer[1024];
   int *p = (int *) buffer[0];
   double *d = (double *) buffer[8];
   *p = 3;
   *d = 7.0;

This is "poor man's placement-new".  (Placement new is the bit in C++ 
that allows this:

   __attribute__((aligned)) char buffer[1024];
   int *p = new (buffer) int;
   int *d = new (buffer + 8) double;

If we want to make the C code above work, we'd need character arrays (at 
least) to have alias set zero.  However, my recollection was that in C++ 
we're now requiring the placement-new construct and that Richard G. and 
Ian did quite a bit of work (CHANGE_DYNAMIC_TYPE_EXPR) to (a) make 
placement-new work, and (b) not unduly pessimize other uses of casts. 
If that's correct, then I'd expect the C usage above is already broken, 
for the same reasons that placement-new used to be broken -- and that, 
therefore, we don't really need "char" itself to be in alias set zero, 
so long as "char *" is somehow specially marked.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH] Make alias_sets_conflict_p less conservative

[Richard Guenther]

On Wed, 5 Mar 2008, Richard Guenther wrote:

> The patch bootstrapped fine with a single failure,
> 
> FAIL: gcc.c-torture/execute/20071219-1.c execution
> 
> where it looks we get things right on the tree level but break it
> on the RTL level.  (It's test3 () that is broken, from a quick
> look we DSE *p = a; which of course is wrong as p points to b)

We break it at tree level already, a tree-level DSE bug is exposed
by this change (PR35472).  We go from (before the patch)

  # VUSE <p_16>
  p.3_1 = p;
  # p_20 = VDEF <p_16>
  # a_21 = VDEF <a_17>
  # b_22 = VDEF <b_18>
  # SMT.29_23 = VDEF <SMT.29_19>
  *p.3_1 = a;
  # VUSE <p_20>
  p.3_2 = p;
  # p_24 = VDEF <p_20>
  # a_25 = VDEF <a_21>
  # b_26 = VDEF <b_22>
  # SMT.29_27 = VDEF <SMT.29_23>
  *p.3_2 = b;

(note how the store to *p wrongly affects p itself, and thus we store
to two different pointer SSA_NAMEs)

to (after the patch)

  # VUSE <p_16>
  p.3_1 = p;
  # a_20 = VDEF <a_17>
  # b_21 = VDEF <b_18>
  # SMT.29_22 = VDEF <SMT.29_19>
  *p.3_1 = a; 
  # a_23 = VDEF <a_20>
  # b_24 = VDEF <b_21>
  # SMT.29_25 = VDEF <SMT.29_22>
  *p.3_1 = b; 

where DSE now wrongly decides to delete the *p.3_1 = a; store.

Richard.