ISO Aliasing rules question

ISO Aliasing rules question

[law]

Given this testcase:

struct s1 { double d; };
struct s2 { double d; };

double f(struct s1 *a, struct s2 *b)
{
  a->d = 1.0;
  return b->d + 1.0;
}

int main()
{
  struct s1 a;
  a.d = 0.0;
  if (f (&a, (struct s2 *)&a) != 2.0)
    abort ();
  return 0;
}


Does this code produce undefined behavior according to ISO standard,
particularly in regards to aliasing issues.

My recollection of the standard is that struct s1 and struct s2 are 
_NOT_ type compatible (even though they have identical internal structure).

Thus the variables a & b in function f can't refer to the same object
as they are not type compatible.  Thus the compiler should be free to
ignore the assignment a->d = 1.0 when evaluating return b->d + 1.0
(which is precisely what the tree-ssa branch does :-)

Is this correct?  Or is my recollection of the ISO standard incorrect here?

Jeff

Re: ISO Aliasing rules question

[Mark Mitchell]

--On Friday, February 21, 2003 10:16:02 AM -0700 "law@redhat.com" 
<law@redhat.com> wrote:

> Is this correct?  Or is my recollection of the ISO standard incorrect
> here?

This is tricky.  In general, you're right -- the structure of the type
doesn't matter, only the name.

But, then there's the "common initial sequence" stuff -- which doesn't 
apply in your example, but can in other palces.  See 6.5.2.3 in your C99 
standard for details.

Bottom line: the optimization in the code you showed is correct.

-- 
Mark Mitchell                mark@codesourcery.com
CodeSourcery, LLC            http://www.codesourcery.com

Re: ISO Aliasing rules question

[Michael Matz]

Hi,

On Fri, 21 Feb 2003 law@redhat.com wrote:

> struct s1 { double d; };
> struct s2 { double d; };
>
> double f(struct s1 *a, struct s2 *b)
> {
>   a->d = 1.0;
>   return b->d + 1.0;
> }
>
> int main()
> {
>   struct s1 a;
>   a.d = 0.0;
>   if (f (&a, (struct s2 *)&a) != 2.0)
>     abort ();
>   return 0;
> }
>
>
> Does this code produce undefined behavior according to ISO standard,
> particularly in regards to aliasing issues.

I asked myself also repeatedly similar things.  Is 'a->d' a whole object
or not?  If yes, then 'a->d' and 'b->d' alias because they have the same
type.  I not, i.e. they are only part of the objects *a and *b, then they
can not alias, because as you notice 'struct s1' and 'struct s2' are not
compatible types as defined in 6.2.7 #1.

> Thus the variables a & b in function f can't refer to the same object
> as they are not type compatible.

Well, the aliasing rules only constrain how you can _access_ the storage,
not how many and which references you can have to it.  I.e. a and b are
allowed to refer to the same storage, just the access later would be
non-conforming.  But the basic question is, if a->b constitutes an access
to a 'double' object, or to a 'struct s1.double' object.  And about that I
wondered too repeatedly ;-)  6.5.2.3 says the type of an 's->x' expression
is that of member 'x' (with added qualification), so I guess, that a->b
and b->d _do_ alias each other (both types are double).


Ciao,
Michael.

Re: ISO Aliasing rules question

[law]

In message <75590000.1045854544@warlock.codesourcery.com>, Mark Mitchell writes
:
 >
 >
 >--On Friday, February 21, 2003 10:16:02 AM -0700 "law@redhat.com" 
 ><law@redhat.com> wrote:
 >
 >> Is this correct?  Or is my recollection of the ISO standard incorrect
 >> here?
 >
 >This is tricky.  In general, you're right -- the structure of the type
 >doesn't matter, only the name.
 >
 >But, then there's the "common initial sequence" stuff -- which doesn't 
 >apply in your example, but can in other palces.  See 6.5.2.3 in your C99 
 >standard for details.
Understood.  However, those cases are caught by the subset/superset
relationships we build in alias.c.

In the testcase I showed we effectively have the following alias sets

  struct s1     struct s2
     |             |
   double        double


s1 is not a superset of s2 and s2 is not a superset of s2.  Thus according
to our alias code objects of type s1 and type s2 will never conflict, even
though they have members of the same type.


Anyway, I'm just trying to make sure that 

  a. I understand this case correctly.

  b. Our aliasing code does the right thing.

  c. Our testsuite doesn't have tests with undefined behavior :-)
     (that test is execute/20000603-1.c).

 >Bottom line: the optimization in the code you showed is correct.
Meaning that execute/20000603-1.c is a bogus test :-)

jeff

Re: ISO Aliasing rules question

[Michael Matz]

Hi,

On Fri, 21 Feb 2003, Mark Mitchell wrote:

> This is tricky.  In general, you're right -- the structure of the type
> doesn't matter, only the name.

Yes, but he's accessing a member, not the whole struct.  And that access
has type 'double'.  6.5 #7 only speaks about accessing "an object".  Is
somewhere defined, that a->d is not such an object, but merely a part of a
bigger one (and b->d too, so 6.5 #7 would apply to the whole struct, which
indeed can't alias).

Hmm, I can construct a funny example:

struct s1 {int i1, i2; };
struct s2 {int i1, i2; };
int g(struct s1 *a, struct s2* b);
int f()
{
  struct s1 * p = malloc (sizeof (struct s1));
  // P1
  p->i1 = 2;
  // P2
  ((struct s2 *)p)->i2 = 3;
  // P3
  g (p, (struct s2* )p);
}

As per 6.5 #4 (effective type of objects);
At P1 *p does not have an effective type yet.  At P2 the object
'p->i1' does have effective type double.  But what is the effective type
of *p?  If you can answer that, then which type has *p at P3?  I think
under this light it makes only sense to speak about the effective types of
the members.  Hmm, what does that mean for aliasing of a and b int g()?


Ciao,
Michael.

Re: ISO Aliasing rules question

[Mark Mitchell]

>  >Bottom line: the optimization in the code you showed is correct.
> Meaning that execute/20000603-1.c is a bogus test :-)

The key thing there is that b doesn't really point to an s2, so accesses 
through it are invalid.  Although I can't find the part of the standard 
that says that any more!

The C++ standard has this language:

  If  a program attempts to access the stored value of an object through
  an lvalue of other than one of the following  types  the  behavior  is
  undefined25):

  --the dynamic type of the object,

  ...

The problem here is that b doesn't have the dynamic type s2.

I think the C standard has similar language -- somewhere.

-- 
Mark Mitchell                mark@codesourcery.com
CodeSourcery, LLC            http://www.codesourcery.com

Re: ISO Aliasing rules question

[Michael Matz]

Hi,

On Fri, 21 Feb 2003, Mark Mitchell wrote:

> The C++ standard has this language:
>
>   If  a program attempts to access the stored value of an object through
>   an lvalue of other than one of the following  types  the  behavior  is
>   undefined25):
>
>   --the dynamic type of the object,
>
>   ...
>
> The problem here is that b doesn't have the dynamic type s2.
>
> I think the C standard has similar language -- somewhere.

6.5 #6 defines effective type (that's the dynamic type of C++)
6.5 #7 defines the permitted accesses (the aliasing rules.  similar to
       C++, except it doesn't contain the base class case)


Ciao,
Michael.

Re: ISO Aliasing rules question

[Mark Mitchell]

--On Friday, February 21, 2003 08:38:07 PM +0100 Michael Matz 
<matz@suse.de> wrote:

> Yes, but he's accessing a member, not the whole struct.  And that access

I'm pretty sure it's the pointer he's using that's the key.

If he wrote:

  double *dp = (double*) b;

  *dp = 1.0;

that would be fine, but saying b->d = 1.0 isn't.

-- 
Mark Mitchell                mark@codesourcery.com
CodeSourcery, LLC            http://www.codesourcery.com

Re: ISO Aliasing rules question

[Michael Matz]

Hi,

On Fri, 21 Feb 2003, Mark Mitchell wrote:

> --On Friday, February 21, 2003 08:38:07 PM +0100 Michael Matz
> <matz@suse.de> wrote:
>
> > Yes, but he's accessing a member, not the whole struct.  And that access
>
> I'm pretty sure it's the pointer he's using that's the key.
>
> If he wrote:
>
>   double *dp = (double*) b;
>
>   *dp = 1.0;
>
> that would be fine, but saying b->d = 1.0 isn't.

Hmm.  How's that then:

double *dp = &(b->d);
*dp = 1.0;

This definitely is accessing a 'double' object, and aliases ergo with
a->d.  In this regard I fail to see the difference between
"*dp = 1.0" and "b->d = 1.0".  If there _is_ a difference it could only
result from types, and then only if there would be the concept of
subtypes, or tagged types, or however we call them.  I.e. if
type(*dp) != type(b->d) would be true.  I don't think this concept exists
in C.  Hmm.


Ciao,
Michael.

Re: ISO Aliasing rules question

[Mark Mitchell]

--On Friday, February 21, 2003 09:20:32 PM +0100 Michael Matz 
<matz@suse.de> wrote:

> Hi,
>
> On Fri, 21 Feb 2003, Mark Mitchell wrote:
>
>> --On Friday, February 21, 2003 08:38:07 PM +0100 Michael Matz
>> <matz@suse.de> wrote:
>>
>> > Yes, but he's accessing a member, not the whole struct.  And that
>> > access
>>
>> I'm pretty sure it's the pointer he's using that's the key.
>>
>> If he wrote:
>>
>>   double *dp = (double*) b;
>>
>>   *dp = 1.0;
>>
>> that would be fine, but saying b->d = 1.0 isn't.
>
> Hmm.  How's that then:
>
> double *dp = &(b->d);
> *dp = 1.0;
>
> This definitely is accessing a 'double' object, and aliases ergo with
> a->d.  In this regard I fail to see the difference between
> "*dp = 1.0" and "b->d = 1.0".

The point is that "b" doesn't point to what you're claiming it does.

The model goes like this:

(1) When you see ->, check that the object on the left of the -> has
    an effective type compatible with its static type.  If not, blow up.

(2) Having done that, access the data.

You're reversing the two steps, in some sense.

Another way to say this is that "x->y" is really short-hand for "(*x).y". 
The C++ stnadard explicitly says that the -> is just short-hand.

-- 
Mark Mitchell                mark@codesourcery.com
CodeSourcery, LLC            http://www.codesourcery.com

Re: ISO Aliasing rules question

[Joseph S. Myers]

On Fri, 21 Feb 2003, Michael Matz wrote:

> Hi,
> 
> On Fri, 21 Feb 2003 law@redhat.com wrote:
> 
> > struct s1 { double d; };
> > struct s2 { double d; };
> >
> > double f(struct s1 *a, struct s2 *b)
> > {
> >   a->d = 1.0;
> >   return b->d + 1.0;
> > }
> >
> > int main()
> > {
> >   struct s1 a;
> >   a.d = 0.0;
> >   if (f (&a, (struct s2 *)&a) != 2.0)
> >     abort ();
> >   return 0;
> > }
> >
> >
> > Does this code produce undefined behavior according to ISO standard,
> > particularly in regards to aliasing issues.
> 
> I asked myself also repeatedly similar things.  Is 'a->d' a whole object
> or not?  If yes, then 'a->d' and 'b->d' alias because they have the same
> type.  I not, i.e. they are only part of the objects *a and *b, then they
> can not alias, because as you notice 'struct s1' and 'struct s2' are not
> compatible types as defined in 6.2.7 #1.

The basic "what is an object?" question is discussed in Nick Maclaren's
discussion with a title something like that, posted to the WG14 reflector
some time ago, required reading for anyone contemplating such issues; ask
him for a copy if you don't have one.

In this case, a (in main) has declared type (so effective type) struct s1,
so _if_ the structure is the relevant object then access through the type
struct s2 would be undefined.  But if you declared a as double, and then
cast &a to each pointer type, then I think all accesses in f would be
legitimate: an object of effective type double is accessed through
structure types with an element of that type.

DR#236 discusses some problems with the type-based aliasing rules that are
far from resolved.  A proper resolution of such problems requires the
underlying issues with the concept of an object to be resolved first.

-- 
Joseph S. Myers
jsm28@cam.ac.uk

Re: ISO Aliasing rules question

[Geoff Keating]

Michael Matz <matz@suse.de> writes:

> Hi,
> 
> On Fri, 21 Feb 2003, Mark Mitchell wrote:
> 
> > This is tricky.  In general, you're right -- the structure of the type
> > doesn't matter, only the name.
> 
> Yes, but he's accessing a member, not the whole struct.  And that access
> has type 'double'.  6.5 #7 only speaks about accessing "an object".  Is
> somewhere defined, that a->d is not such an object, but merely a part of a
> bigger one (and b->d too, so 6.5 #7 would apply to the whole struct, which
> indeed can't alias).

Yes, both '*a' and 'a->d' are objects.  When you write '(*a).d', you
access *a then you access d, and 'a->d' is the same as '(*a).d'.

> Hmm, I can construct a funny example:
> 
> struct s1 {int i1, i2; };
> struct s2 {int i1, i2; };
> int g(struct s1 *a, struct s2* b);
> int f()
> {
>   struct s1 * p = malloc (sizeof (struct s1));
>   // P1
>   p->i1 = 2;
>   // P2
>   ((struct s2 *)p)->i2 = 3;
>   // P3
>   g (p, (struct s2* )p);
> }
> 
> As per 6.5 #4 (effective type of objects);
> At P1 *p does not have an effective type yet.  At P2 the object
> 'p->i1' does have effective type double.  But what is the effective type
> of *p? 

It's 'struct s1'.  "If a value is stored into an object ... the type
of the lvalue becomes the effective type of the object ... for
subsequent accesses that do not modify the stored value."

> If you can answer that, then which type has *p at P3?

At P3, it has 'struct s2': "for all other accesses, the effective
type... is the type used".  (The sentence I quoted earlier don't apply
because this is an access which does "modify the stored value" of *p.)

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: ISO Aliasing rules question

[law]

In message <Pine.LNX.4.33.0302220019400.4365-100000@kern.srcf.societies.cam.ac.
uk>, "Joseph S. Myers" writes:
 >> I asked myself also repeatedly similar things.  Is 'a->d' a whole object
 >> or not?  If yes, then 'a->d' and 'b->d' alias because they have the same
 >> type.  I not, i.e. they are only part of the objects *a and *b, then they
 >> can not alias, because as you notice 'struct s1' and 'struct s2' are not
 >> compatible types as defined in 6.2.7 #1.
 >
 >The basic "what is an object?" question is discussed in Nick Maclaren's
 >discussion with a title something like that, posted to the WG14 reflector
 >some time ago, required reading for anyone contemplating such issues; ask
 >him for a copy if you don't have one.
Do you have a contact address for Nick?  I wandered

 http://std.dkuug.dk/jtc1/sc22/wg14

But couldn't find a reference to that paper.


 >In this case, a (in main) has declared type (so effective type) struct s1,
 >so _if_ the structure is the relevant object then access through the type
 >struct s2 would be undefined.  But if you declared a as double, and then
 >cast &a to each pointer type, then I think all accesses in f would be
 >legitimate: an object of effective type double is accessed through
 >structure types with an element of that type.
But in "f" we have the following

  a->d = 1.0
  return b->d + 1.0;

According to an earlier message, that is just "shorthand" for:

  (*a).d = 1.0
  return (*b).d + 1.0

Which seems to me to clearly access "a" and "b" first, then their
appropriate field, which it would seem to me to run afoul of the
aliasing rules.

FWIW, the tree-ssa code uses the model above.  First you indirect the
pointer, then you look at the appropriate field.

 >DR#236 discusses some problems with the type-based aliasing rules that are
 >far from resolved.  A proper resolution of such problems requires the
 >underlying issues with the concept of an object to be resolved first.
Yup, but I didn't see how DR236 directly related to this issue.  Or maybe
I just didn't think about it hard enough :-)

jeff

Re: ISO Aliasing rules question

[Joseph S. Myers]

On Mon, 24 Feb 2003 law@redhat.com wrote:

>  >The basic "what is an object?" question is discussed in Nick Maclaren's
>  >discussion with a title something like that, posted to the WG14 reflector
>  >some time ago, required reading for anyone contemplating such issues; ask
>  >him for a copy if you don't have one.
> Do you have a contact address for Nick?  I wandered
> 
>  http://std.dkuug.dk/jtc1/sc22/wg14
> 
> But couldn't find a reference to that paper.

nmm1@cus.cam.ac.uk.  I don't think it made a formal WG14 paper, just a
mail to the reflector.

>  >In this case, a (in main) has declared type (so effective type) struct s1,
>  >so _if_ the structure is the relevant object then access through the type
>  >struct s2 would be undefined.  But if you declared a as double, and then
>  >cast &a to each pointer type, then I think all accesses in f would be
>  >legitimate: an object of effective type double is accessed through
>  >structure types with an element of that type.
> But in "f" we have the following
> 
>   a->d = 1.0
>   return b->d + 1.0;
> 
> According to an earlier message, that is just "shorthand" for:
> 
>   (*a).d = 1.0
>   return (*b).d + 1.0
> 
> Which seems to me to clearly access "a" and "b" first, then their
> appropriate field, which it would seem to me to run afoul of the
> aliasing rules.

If the effective type is double, then the accesses to a and b are OK,
since those structs contain a double.  And if the effective type is double
because the declared type is double (in the variant example I gave), 
accesses and modifications cannot change the effective type to something 
else.

-- 
Joseph S. Myers
jsm28@cam.ac.uk

Re: ISO Aliasing rules question

[Toon Moene]

law@redhat.com wrote:

> Do you have a contact address for Nick?  I wandered
> 
>  http://std.dkuug.dk/jtc1/sc22/wg14
> 
> But couldn't find a reference to that paper.

Google's your friend.

"nick maclaren" gives ("I'm feeling lucky"):

nmm1@cus.cam.ac.uk

[ Watch out - Nick's a Fortran supporter ;-) ]

-- 
Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
GNU Fortran 95: http://gcc-g95.sourceforge.net/ (under construction)

Re: ISO Aliasing rules question

[Fergus Henderson]

On 24-Feb-2003, law@redhat.com <law@redhat.com> wrote:
> But in "f" we have the following
> 
>   a->d = 1.0
>   return b->d + 1.0;
> 
> According to an earlier message, that is just "shorthand" for:
> 
>   (*a).d = 1.0
>   return (*b).d + 1.0

In C++ yes, but not in C.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.

Re: ISO Aliasing rules question

[David Carlton]

On Fri, 21 Feb 2003 10:16:02 -0700, law@redhat.com said:

> struct s1 { double d; };
> struct s2 { double d; };

> double f(struct s1 *a, struct s2 *b)

> int main()
> {
>   struct s1 a;
>   f (&a, (struct s2 *) &a);
> }

(I've chopped the test case.)

I have a few related questions:

1) What if the call to f were changed to

  f (&a, (struct s2 *) &a.d);

or to

    f (&a, (struct s2 *) (double *) &a);

Would that make a difference?

2) What if we have a sequence like this (with the same s1 as above):

void f (struct s1 *s1p);

void g (double *dp)
{
  f ((struct s1 *) dp);
}

void h (void)
{
  struct s1 a;

#ifdef SWITCH
  f (&a);
#else
  g (&p.d);
#endif
}

Does the behavior depend on whether or not SWITCH is defined?


I confess that I don't have a copy of the C standard; I'm just curious
what lies behind the statement in K&R that "If a pointer to a
structure is cast to the type of a pointer to its first member, the
result refers to the first member."

The reason why I ask is that there are places in GDB where we get a
(clumsy) analogue of C++ subclassing by creating a struct whose first
member is another struct (which acts like a superclass).  I think that
everything we do currently in that regard is legit, but I'd like to
augment this by doing a sort of Java-style generic container, where
the container contains a pointer to the first member (the
"superclass") that I'd like to be able to cast back to a pointer to
the entire struct (the "subclass").  I would hope that this is legal
because the K&R quote above suggests that the pointer to the first
member is the same as casting to the superclass, so all I'd be doing
is casting to the superclass and then back to the subclass.  But these
sorts of discussions are making me a bit paranoid about when casts are
ever reliable.

David Carlton
carlton@math.stanford.edu