Re: alias question

Re: alias question

[xorbe]

> But not every type aliases character type!

What?  You can access any type with a char type,
this is a specific exception.

Here's a concrete example.  I think the point that is being
overlooked is that all *writes* are done with char only.
That's the twist that makes this follow the letter of the
law.  It doesn't matter that short and int overlap below,
because they are "both" written simultaneously with a char.

#include <stdio.h>
char b[4] = {0,0,0,0};
const short *w((short*)b);
const int   *d((  int*)b);
void print() {printf("%02x%02x%02x%02x %04x%04x %08x\n",
                     b[3],b[2],b[1],b[0],w[1],w[0],d[0]);}
int main() {
  print();
  for (int i(0); i<4; ++i) { b[i] = i+1; print(); }
}

ie,
b[3] = value;
The compiler looks at w[1], and says, oh there was a byte write.
The compiler looks at d[0], and says, oh there was a byte write.
The compiler doesn't even notice that w[1] and d[0] overlap,
which is what alias optimization is about.  But it does notice
that b[3] and w[1] overlap, and that b[3] and d[0] overlap.

Jason

Re: alias question

[Segher Boessenkool]

>> But not every type aliases character type!
>
> What?  You can access any type with a char type,
> this is a specific exception.

Yes.  And you cannot access a char as any type.  The exception is
not symmetric in that way.

> Here's a concrete example.

> const short *w((short*)b);

That's not C code.  I have no idea about the rules in C++..

> char b[4] = {0,0,0,0};

If it was C, then the objects b[...] have declared type "char", so
you are only allowed to access it as a character type; anything
else results in  undefined behaviour.


Segher

Re: alias question

[xorbe]

> That's not C code.  I have no idea about
> the rules in C++..

Apology, I'll try to stick to C code.

> > What?  You can access any type with a char type,
> > this is a specific exception.
> 
> Yes.  And you cannot access a char as any type. 
> The exception is not symmetric in that way.

I looked this up.  That's just legalese wording to stop the
following "logic" of attempting to alias through char:

uint32_t *d;
char     *c =     (char*)d;  /* okay */
uint16_t *s = (uint16_t*)c;  /* bzzt spec says no! */

Clearly the above code will fail when written by *s and read
by *d, or vice-versa.  Not because we created an alias to
char, but because we sneakily created an alias between two
different non-char types through the char pointer.

If there is only char + one type in question, then the reality is
that it make no difference which order the aliases are created.
There are two pointers that alias each other.  One can't say that
the char aliases the type, or that the type aliases the char,
it's equivalent at that point.

My example is different that any other example that I could dig
up on the web.  I've concluded that the reason my example code is
valid and works is because there are only char writes.  Any other
type of read to the same region will always see the char writes,
even if those other reads happen to overlap.

Counter-example code that breaks always welcome!

Thanks,
Jason

Re: alias question

[Patrick Horgan]

On 02/18/2011 09:35 AM, xorbe wrote:
> #include<stdio.h>
> char b[4] = {0,0,0,0};
> const short*w((short*)b);
> const int*d((  int*)b);
> void print() {printf("%02x%02x%02x%02x %04x%04x %08x\n",
>                       b[3],b[2],b[1],b[0],w[1],w[0],d[0]);}
> int main() {
>    print();
>    for (int i(0); i<4; ++i) { b[i] = i+1; print(); }
> }
You're right.  This might make it clearer, it's a version that's valid C 
and looks like it has an optimization opportunity (which would give you 
output you _didn't_ want;) but actually doesn't because of the special 
case char& or char* can alias anything rule.

#include <stdio.h>

char b[4] = {0,0,0,0};
const short *w;
const int   *d;

int main()
{
     size_t i;
     w = ((short*)b);
     d = ((  int*)b);
     /* the next line makes explicit endianess assumptions */
     printf("%02x%02x%02x%02x %04x%04x 
%08x\n",b[3],b[2],b[1],b[0],w[1],w[0],d[0]);
     for (i=0; i<4; ++i) {
         b[i] = (char)(i+1);
         printf("%02x%02x%02x%02x %04x%04x 
%08x\n",b[3],b[2],b[1],b[0],w[1],w[0],d[0]);
     }
     return 0;
}

A compiler might want to optimize the references to w and d since 
they're unchanged inside the loop, and just remember their values from 
outside the list.  Unfortunately, since access through a char reference 
or pointer can alias anything, the compiler is unable to make this 
assumption and cannot do any optimizations.  In general, doing any 
accesses of things through a char* or char& in a method or function can 
make a lot of optimizations impossible.

Patrick

p.s. Please read my aliasing whitepaper and make any suggestions for 
improvement that occur to you.  http://dbp-consulting.com/StrictAliasing.pdf

Re: alias question

[Patrick Horgan]

On 02/18/2011 09:35 AM, xorbe wrote:
>> >  But not every type aliases character type!
> What?  You can access any type with a char type,
> this is a specific exception.
>
> Here's a concrete example.  I think the point that is being
> overlooked is that all*writes*  are done with char only.
> That's the twist that makes this follow the letter of the
> law.  It doesn't matter that short and int overlap below,
> because they are "both" written simultaneously with a char.
>
> #include<stdio.h>
> char b[4] = {0,0,0,0};
> const short*w((short*)b);
> const int*d((  int*)b);
> void print() {printf("%02x%02x%02x%02x %04x%04x %08x\n",
>                       b[3],b[2],b[1],b[0],w[1],w[0],d[0]);}
> int main() {
>    print();
>    for (int i(0); i<4; ++i) { b[i] = i+1; print(); }
> }
>
> ie,
> b[3] = value;
> The compiler looks at w[1], and says, oh there was a byte write.
> The compiler looks at d[0], and says, oh there was a byte write.
> The compiler doesn't even notice that w[1] and d[0] overlap,
> which is what alias optimization is about.  But it does notice
> that b[3] and w[1] overlap, and that b[3] and d[0] overlap.
Actually the compiler doesn't have to notice any of the above.  The real 
issue is whether the compiler can assume there are no aliases and take 
the opportunity to make optimizations under that assumption.  Under the 
rules, the compiler is free to assume that w and d do not alias, but 
must assume that b can alias everything.   It's the rule.  Accesses 
through char* or char& can alias anything and if they can, the compiler 
must make the assumption that they have and scotch any otherwise 
available optimizations.

Patrick
> Jason
>
>
>
>
>

Re: alias question

[Segher Boessenkool]

>>> No: character types are special.  See Section 6.5 re arrays of
>>> character type and effective types.
>>
>> 6.5/6, first line: The effective typeof an object for an access to its
>> stored value is the declared type of the object, if any.
>>
>> No exception for character types here; there is in some other
>> aspects (like for accesses to allocated storage), but not for this.
>
> "If a value is copied into an object having no declared type using

_no declared type_

> memcpy or memmove, or is copied as an array of character type, then
> the effective type of the modified object for that access and for
> subsequent accesses that do not modify the value is the effective type
> of the object from which the value is copied, if it has one...
>
> 7  An object shall have its stored value accessed only by an
> lvalue expression that has one of the following types: 73)
>
> — a type compatible with the effective type of the object,
>
> — a qualified version of a type compatible with the effective type of
> the object,
>
> — a type that is the signed or unsigned type corresponding to the
> effective type of the object, — a type that is the signed or unsigned
> type corresponding to a qualified version of the effective type of the
> object,
>
> — an aggregate or union type that includes one of the aforementioned
> types among its members (including, recursively, a member of a
> subaggregate or contained union), or
>
> — a character type.
>
> 73) The intent of this list is to specify those circumstances in which
> an object may or may not be aliased."
>
> In other words, a character type aliases all other types.

But not every type aliases character type!

> Without
> this, it's not possible to write malloc() in C.

You cannot have the "memory pool" be a declared array, yes.  You can get it
from mmap() or brk() or whatever just fine, the pointers those return are not
pointing to declared objects, so all those special rules apply, and you get
the effective type to be the type of what you store in the malloc()ed area.


Segher

Re: alias question

[Andrew Haley]

On 02/18/2011 02:13 PM, Segher Boessenkool wrote:
>>>>>> If I have a char array, and it's always written by the char array,
>>>>>> can
>>>>>> it
>>>>>> be always reliably read by any combination of short/int/long
>>>>>> pointers?
>>>>>>
>>>>>> As I understand, the compiler will see byte writes for all types, so
>>>>>> readind shoulg be fine without violating any strict alias rules.
>>>>>> Just
>>>>>> can't write the array by any other type than char[] access.  Right?
>>>>>
>>>>> No.  You can access anything only as its declared type or character
>>>>> type;
>>>>> an array of char thus can be accessed as char only.
>>>>
>>>> Not quite: if you write an int to an array of char, you can read it
>>>> back again.  What matters is the effective type.
>>>
>>> Of course, but the effective type is equal to the declared type (if
>>> there
>>> is any) of the object,
>>> so that write as int is undefined behaviour already!
>>
>> No: character types are special.  See Section 6.5 re arrays of
>> character type and effective types.
>
> 6.5/6, first line: The effective typeof an object for an access to its
> stored value is the declared type of the object, if any.
>
> No exception for character types here; there is in some other
> aspects (like for accesses to allocated storage), but not for this.

"If a value is copied into an object having no declared type using
memcpy or memmove, or is copied as an array of character type, then
the effective type of the modified object for that access and for
subsequent accesses that do not modify the value is the effective type
of the object from which the value is copied, if it has one...

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

— a type compatible with the effective type of the object,

— a qualified version of a type compatible with the effective type of
the object,

— a type that is the signed or unsigned type corresponding to the
effective type of the object, — a type that is the signed or unsigned
type corresponding to a qualified version of the effective type of the
object,

— an aggregate or union type that includes one of the aforementioned
types among its members (including, recursively, a member of a
subaggregate or contained union), or

— a character type.

73) The intent of this list is to specify those circumstances in which
an object may or may not be aliased."

In other words, a character type aliases all other types.  Without
this, it's not possible to write malloc() in C.

Andrew.

Re: alias question

[Segher Boessenkool]

>>>>> If I have a char array, and it's always written by the char array,
>>>>> can
>>>>> it
>>>>> be always reliably read by any combination of short/int/long
>>>>> pointers?
>>>>>
>>>>> As I understand, the compiler will see byte writes for all types, so
>>>>> readind shoulg be fine without violating any strict alias rules.
>>>>> Just
>>>>> can't write the array by any other type than char[] access.  Right?
>>>>
>>>> No.  You can access anything only as its declared type or character
>>>> type;
>>>> an array of char thus can be accessed as char only.
>>>
>>> Not quite: if you write an int to an array of char, you can read it
>>> back again.  What matters is the effective type.
>>
>> Of course, but the effective type is equal to the declared type (if
>> there
>> is any) of the object,
>> so that write as int is undefined behaviour already!
>
> No: character types are special.  See Section 6.5 re arrays of
> character type and effective types.

6.5/6, first line: The effective typeof an object for an access to its
stored value is the declared type of the object, if any.

No exception for character types here; there is in some other aspects (like
for accesses to allocated storage), butnot for this.


Segher

Re: alias question

[Andrew Haley]

On 02/18/2011 10:40 AM, Segher Boessenkool wrote:
>>>> If I have a char array, and it's always written by the char array, can
>>>> it
>>>> be always reliably read by any combination of short/int/long pointers?
>>>>
>>>> As I understand, the compiler will see byte writes for all types, so
>>>> readind shoulg be fine without violating any strict alias rules.  Just
>>>> can't write the array by any other type than char[] access.  Right?
>>>
>>> No.  You can access anything only as its declared type or character
>>> type;
>>> an array of char thus can be accessed as char only.
>>
>> Not quite: if you write an int to an array of char, you can read it
>> back again.  What matters is the effective type.
>
> Of course, but the effective type is equal to the declared type (if there
> is any) of the object,
> so that write as int is undefined behaviour already!

No: character types are special.  See Section 6.5 re arrays of
character type and effective types.

Andrew.

Re: alias question

[Segher Boessenkool]

>>> If I have a char array, and it's always written by the char array, can
>>> it
>>> be always reliably read by any combination of short/int/long pointers?
>>>
>>> As I understand, the compiler will see byte writes for all types, so
>>> readind shoulg be fine without violating any strict alias rules.  Just
>>> can't write the array by any other type than char[] access.  Right?
>>
>> No.  You can access anything only as its declared type or character
>> type;
>> an array of char thus can be accessed as char only.
>
> Not quite: if you write an int to an array of char, you can read it
> back again.  What matters is the effective type.

Of course, but the effective type is equal to the declared type (if there
is any) of the object,
so that write as int is undefined behaviour already!


Segher

Re: alias question

[Andrew Haley]

On 02/18/2011 10:02 AM, xorbe wrote:
>
>>> If I have a char array, and it's always written by the char array,
>>> can it be always reliably read by any combination of
>>> short/int/long pointers?
>>>
>>> As I understand, the compiler will see byte writes for all types,
>>> so readind shoulg be fine without violating any strict alias
>>> rules.  Just can't write the array by any other type than char[]
>>> access.  Right?
>>
>> No.  You can access anything only as its declared type
>> or character type;
>> an array of char thus can be accessed as char only.
>
> However, what I said is walking the fine line of following
> that rule.  I have several overlapping read-only types, BUT
> they are only written as char.  Hence, they'll always resolve
> to the correct value.  I haven't been able to construct any
> code which fails to work yet.  If a char write precedes a
> type's access to the same location, then it will be seen.
> As far as I can tell, that basic rule is followed here!

I think not, but you haven't described what you're doing with
sufficient precision for us to be able to tell for sure.

Andrew.

Re: alias question

[xorbe]

> > If I have a char array, and it's
> always written by the char array, can it
> > be always reliably read by any combination of
> short/int/long pointers?
> >
> > As I understand, the compiler will see byte writes for
> all types, so
> > readind shoulg be fine without violating any strict
> alias rules.  Just
> > can't write the array by any other type than char[]
> access.  Right?  -Jason
> 
> No.  You can access anything only as its declared type
> or character type;
> an array of char thus can be accessed as char only.
> 
> Segher

However, what I said is walking the fine line of following
that rule.  I have several overlapping read-only types, BUT
they are only written as char.  Hence, they'll always resolve
to the correct value.  I haven't been able to construct any
code which fails to work yet.  If a char write precedes a
type's access to the same location, then it will be seen.
As far as I can tell, that basic rule is followed here!
Jason

Re: alias question

[Andrew Haley]

On 02/18/2011 02:29 AM, Segher Boessenkool wrote:
>> If I have a char array, and it's always written by the char array, can it
>> be always reliably read by any combination of short/int/long pointers?
>>
>> As I understand, the compiler will see byte writes for all types, so
>> readind shoulg be fine without violating any strict alias rules.  Just
>> can't write the array by any other type than char[] access.  Right?
>
> No.  You can access anything only as its declared type or character type;
> an array of char thus can be accessed as char only.

Not quite: if you write an int to an array of char, you can read it
back again.  What matters is the effective type.

Andrew.

Re: alias question

[Segher Boessenkool]

> If I have a char array, and it's always written by the char array, can it
> be always reliably read by any combination of short/int/long pointers?
>
> As I understand, the compiler will see byte writes for all types, so
> readind shoulg be fine without violating any strict alias rules.  Just
> can't write the array by any other type than char[] access.  Right?

No.  You can access anything only as its declared type or character type;
an array of char thus can be accessed as char only.


Segher

alias question

[xorbe]

If I have a char array, and it's always written by the char array, can it be always reliably read by any combination of short/int/long pointers?

As I understand, the compiler will see byte writes for all types, so readind shoulg be fine without violating any strict alias rules.  Just can't write the array by any other type than char[] access.  Right?

char buf[8];
... alter buf[] ...
((short*)buf)[x];
((int*)buf)[y];
((long*)buf)[z];
... alter buf[] ...
((short*)buf)[x];
((int*)buf)[y];
((long*)buf)[z];

Thanks,
Jason Mancini