Document: N1090
Date: 29-Nov-04

An Analysis of the Issue Raised by DR 236

Introduction

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.) 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.
 

The issue raised by DR 236

The "exception" referred to in the above is basically bullet 7 of 6.5p7. This bullet allows a union to be referenced via both the lvalue of the union type and lvalues of the member types. For example:

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.
 

Intention of the alising model

As a first step in resolving this DR, let us reexamine the intention of the C aliasing model, and the balance it attempts to strike between helping the programmer and the optimizer. We need to identify those cases that are supposed to be allowed and those that are not. For the purpose of this discussion, we will introduce rules as though they are added to the Standard. These rules are not meant to be the ultimate resolution of this DR nor meant to be suggested text to the Standard. (Further discussion is needed to come up with those text.) It is meant to help understanding the issue.

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.
 

Where should we draw the line

We don't want an all or nothing choice. We want to draw the line somewhere in the middle. A possible compromise is to draw it at a function boundary. That is, on entry into a function, point a holds for all pointers accessible at that point. Within the body of a function, the transitive side effect of point c is allowed. Let us write a rule to say this.

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 access based 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 term based on as used here takes on the same meaning as in the "formal definition of restrict" pointers.
Accessible means the pointer is either visible, or the pointer's value can be accessed through (multiple levels of ) indirections via a visible pointer.

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 ?
 

Alternate Rule

The essential issue is the access to members of unions. Optimizers may have problems in the first and third examples, as the code in setting and using the pointer may be too far apart. The rule suggested above give more freedom to the program and less information to the optimizer. An alternate rule could be written as follows:

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.

Concluding Remarks

The effect of allocated storage has been ignored in this discussion. It is taken for granted that 6.5.5.2p10a will automatically apply. This should be verified.