It is in general expensive to do pointer analysis in a program. A pointer can point to different address locations at different time; and two pointers can be used to access overlapping objects. This limits the amount of code motion an optimizer can safely do, and in turn limits optimization opportunities. On the other hand, if we restrict pointer usage, the language may not express the programming logic as fluently as it should. The C aliasing model attempts to strike a balance between expressiveness of the language and ease of optimization. Note that good optimization in the end also benefits the program.
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.) The exceptions to this rule are 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 suggested this was 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 optimizers) becomes
useless. This is an all or nothing choice.
If the analysis in the previous section is correct, the problem cannot be fixed by rules on lvalues alone. This is because the issue is not caused by the relationship between an object and its lvalue, but between the object (its type) and the piece of memory it occupies. In cases where only one type of object can occupy a particular piece of memory, specifying the aliasing rules via lvalues creates no ambiguity. But when different object types can occupy the same memory location, the one-to-one correspondence between lvalues and memory locations is gone. If P and Q are pointers, by just telling the optimizer that *P and *Q are different lvalue types provides little information.
If we accept that the three examples in N1090 (repeated below) are invalid, then the following variation of the suggestion in N1090 might be considered.
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. If two pointers have distinct type alias set, they shall point to non-overlapping address locations. Note that this effectively fixed the type of allocated storage to the one that is used in the first access. A union type would be needed if the allocated storage is used as a buffer for different object types.
Below repeats the three code examples in N1090.
Example 1
The following code is invalid because p and q have distinct type alias set but point to the same address.
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);
}
Example 2
The following is invalid for the same reason as above. p and q cannot point to the same address location.
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 invalid. It would be valid if p is removed and the code is rewritten as in example 4 below.
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);
}
Example 4
The following is valid. q's type alias set is a subset of v's. They
can
point to overlapping address location.
union U {
int a;
float b;
};
void foo(union U *v, float *q) { // q's type alias set is a subset
of v's.
v->a =1;
v->a +=1;
*q=2.0f;
++*q;
}
void main() {
union U u = {0};
foo(&u, &u.b);
}