Document: N1090

Date: 29-Nov-04

`The C aliasing model is mainly defined by 6.5 paragraph 7 (and paragraph
6). In essence, it limits the address locations that can be pointed to
by a pointer -- that is, with a couple of exceptions, a pointer can only
be deferenced to access objects with the same type. (Sign and type qualifiers
are ignored in this consideration.) A couple of exceptions to this rule
is provided to make the language more usable. However, as pointed out by
DR 236, these provisions make the model ineffective in providing optimization
information.`

`union U {`
` int a;`
` float b;`
`} u;`

`The memory occupied by u can be accessed using an lvalue of type
union U, int or float. Putting it in another way, a U pointer and an int
pointer can point to the same address; likewise for a U pointer and a float
pointer. Both of these are fine as the optimizer knows about this aliasing
possibility through the union's definition. However, due to transitivity,
an int pointer and a float pointer can now point to the same (or overlapping)
memory locations. DR 236 suggests this is not the intention of the aliasing
model.`

`int *p = &u.a`
`float *q = &u.b;`
`...`
`*p=1;`
`++*p;`
`*q=2.0f; // Can the optimizer assume q and p point to different
locations ?`
`++*q;`

`The code separated by "..." can be in different parts of the program.
They can be in different CUs.`

`The intent of the aliasing model is to provide sufficient information
to the optimizer so that it can make assertions about a pointer's value
by just looking locally at the location where the pointer is used (basing
on the pointer's type) without going through extensive analysis. However,
the code samples in DR 236 show that 6.5p7 does not provide sufficient
restrictions for the optimizer to make such assertions.`

`6.5p7 describes the aliasing restriction by using lvalues. If P
is a pointer, the lvalue of the object pointed to by P is *P. 6.5p7 specifies
the group of objects accessible by *P. This approach attacks the problem
at the location where the pointer is being used. However, as alluded to
in the above discussion, the problem may lie at the location where the
pointer gets its value -- the pointers point to overlapping address locations.
Talking about P itself directly may offer some hints of what is causing
the problem. So let us try to rewrite the rules in 6.5p7 in terms of pointers.
(Ignore the implication of effective type for the time being.)`

`Let P, Q and R be pointer objects.`

`a/ The basic restriction we want to impose is that a pointer P can
only point to objects with types compatible to *P, ignoring sign and type
qualifiers. This covers bullets 1,2 and 3 in 6.5p7.`

`b/ A character pointer can point to any address locations. This
covers bullet 6.`

`c/ Now add aggregates and union types. If *P is an aggregate or
union type, and *Q a member type, then P and Q can point to overlapping
memory locations. This covers bullet 5.`

`A side effect of point c is that if *R is another member
type different from *Q, R and Q can point to overlapping memory locations.
This happens when a union type is involved. This is the crust of the problem.
DR 236 suggests that this is not the original intend of the aliasing model.
We need to find a way to restrict this transitive side effect.`

`Note: A pointer can gets an address but never used in any accesses.
Such pointer need not be restricted by the above rules. 6.5p7 talks about
lvalues, which avoids this issue altogether.`

`The dilemma we face in trying to resolve this DR is whether point
a
or c above should take precedence. If point a takes precedence,
then the code sample in the previous section becomes invalid (regardless
of whether the pieces separated by the "..." are in the same CU or not).
If point c takes precedence, then the information provided by point
a
(which is the major information relied on by the optimizer) becomes useless.
This is an all or nothing choice.`

`A type alias set is a set of types. The type alias set of
a pointer P to a non-aggregate non-union type contains the type of *P,
together with all the sign and type qualifier variations. The type
alias set of a pointer P to an aggregate or union type contains the type
of *P, together with all the type qualifier variations, and all member
types, taken recursively for subaggregate or contained union, with all
type qualifier and sign variations (if applicable). The type alias set
of a pointer to char is the set of all types.`

`Two type alias set are distinct if neither is a subset of
the other.`

`Consider adding the following to 6.5.5.2 Function Calls, after paragraph
10:`

[10a] At the beginning of a function, for any two pointers that are accessible at this point, if they have distinct type alias set, and if each is involved in an accessbased on(see below) the pointer's value at this point, and if one access modifies the object pointed to by the pointer and the other access reads the object pointed to by the other pointer, then the two pointers shall point to non-overlapping objects.The termbased onas used here takes on the same meaning as in the "formal definition of restrict" pointers.

`Example 1`

`The following code is valid:`

`union U {`
` int a;`
` float b;`
`};`

`void foo(union U *v) {`
` int *p = &v->a; // v is used`
` float *q = &v->b;`
` ...`
` *p=1;`
` ++*p;`
` *q=2.0f;`
` ++*q;`
`}`

`void main() {`
` union U u = {0};`
` foo(&u);`
`}`

`Note: Is there a need for this to be valid ? That is, would it be
ok to require access to a union member to always go through the lvalue
of the union at some level (which was the point brought up in Santa Cruz)
? Optimizers may have problems here because the pieces separated by the
"..." may be widely separated.`

`Example 2`

`The following is not valid:`

`union U {`
` int a;`
` float b;`
`};`

`void foo(int *p, float *q) { // p & q have distinct type alias
set but point to the same address`
` *p=1;`
` ++*p;`
` *q=2.0f;`
` ++*q;`
`}`

`void main() {`
` union U u = {0};`
` foo(&u.a, &u.b);`
`}`

`Example 3`

`The following is valid because union U *v is used, and its type
alias set includes q's:`

`union U {`
` int a;`
` float b;`
`};`

`void foo(union U *v, float *q) { // q's type alias set is a subset
of v's.`
` int *p = &v->a;`
` ...`
` *p=1;`
` ++*p;`
` *q=2.0f;`
` ++*q;`
`}`

`void main() {`
` union U u = {0};`
` foo(&u, &u.b);`
`}`

`Note: Same comment as in example 1. Is there a need for this to
be valid ?`

`Consider adding the following to 6.5.5.2 Function Calls, after paragraph
10:`

[10a] For any two pointers that are used within the body of a function, if their type alias sets are distinct the two shall point to non-overlapping objects.