Proposal: Aliasing barriers and sequencing rules

The "effective type" rules in the C standard are designed to allow compilers to reorder certain operations on disjoint objects in such a way as to maximize performance.  Unfortunately, the language used to describe them is rather cryptic and ambiguous, and fails to make clear what compilers are and are not allowed to do.  Further, even when understood, they only enable compilers to make a fraction of the useful optimizations they could make in most programs without adversely affecting the semantics, and yet may sometimes require programmers to awkwardly jump through hoops to prevent compilers from make unwanted "optimizations" that would break their code.

I would propose that rather than speaking of the effective types of objects sitting in memory, it would be far more useful to express rules in terms of sequencing behavior.  Since performing multiple unsequenced accesses to an object will invoke Undefined Behavior unless none of the accesses modify the object in question, defining the cases in which accesses are sequenced will effectively define the cases where aliasing is permissible or impermissible, but will do so in a way would convey much more effectively than the current Standard what optimizations a compiler may or may not do.

The basic essence of the rules would be that even in cases where the Standard would describe an execution order for an abstract machine which stores objects in memory, the abstract machine would in general be allowed to read objects from memory in advance of when their values were used, and delay writing them to memory after their values were set, provided that if an object or portion thereof is read by operation R and there exists an operation W such that:

1. Operation W was a write to that portion of the object.
2. All write operations to that portion of the object, other than W, are either sequenced before W or after R.

Then operation R will yield the value written by W.


BASIC SEQUENCING GUARANTEES

To start with, in the absence of any specifications to the contrary, writes and reads made to the same object using identical type/member paths shall be sequenced relative to each other in the order they occur.  Further, if an expression reads some objects and writes some objects, any operation which is sequenced before any of the reads shall be sequenced before all of the writes, and any operation which is sequenced after any of the writes will be sequenced after all of the reads(*).  The operations performed in the true or false bodies of an "if()" or "if/else" statement are sequenced after any reads syntactically required to resolve the condition, even if the effects of both branches of the conditional test would be identical.  Likewise for operations in other conditional or looping structures except that Basic Guarantees do not cause operations after a loop which have no data dependencies on anything within the loop to be sequenced after it.

(*)Note that this means that an expression like *q=*p ^ 1; will have defined behavior if both pointers are of the same type and identify the same object, or if they identify disjoint objects, but will invoke Undefined Behavior if they alias in any other fashion, since the read and write would be unsequenced in that case.  Note also that the sequencing rules apply even when the value obtained by one of the reads can't change the result.  For example, give "x=y*z;", a compiler may not move the write to x before any operation preceding the read of z, even if "y" is known to be zero.
If a variable of pointer type has a "restrict" qualifier applied to it, then accesses made using that
pointer or other pointer based upon it (per C99 terminology) will, collectively, be unsequenced
relative to anything else in the universe except at the moment the pointer is created and the moment it is destroyed, unless the pointer is also qualified "volatile", in which case such accesses shall also be sequenced relative to other "volatile" accesses but not to ordinary accesses; all pointers with the same base shall honor the same sequencing relations relative to each other as they would absent the qualifier.  Once the pointer is destroyed, all operations on the object identified thereby using the pointer will forevermore be unsequenced with regard to anything else in the universe unless the pointer was volatile, in which case such operations will be forevermore unsequenced with regard to non-volatile variables.

All accesses to lvalues of volatile type are fully sequenced relative to other lvalue accesses of volatile types, but the minimal sequencing guarantees say nothing about sequencing relative to non-volatile accesses.
 
Functions like malloc(), calloc(), strdup(), etc. would be sequenced before any operations which
dereference the pointer acquired thereby; functions like "realloc()" and "free()" would be
sequenced after any operations which dereference the pointers released thereby.

ADDITIONAL IMPLICIT GUARANTEES

Certain directives would allow programs to specify that additional sequencing guarantees beyond those above should be applied by default when using objects of various types; further, the lack of any directives related to aliasing would imply certain default behaviors including saying that all character-type accesses to things that could be of allocated duration have both happens-before and happens-after relationships with accesses to all other types, and all writes to things that could be of allocated duration have happens-before and happens-after relationships with all other writes of all types, and happens-after (though not happens-before) relationships with reads of all types.
 
EXPLICIT GUARANTEES

Execution of a __FULL_ALIASING_BARRIER() directive will cause all operations which precede the directive to be sequenced before all operations which follow it.  Over-use of this directive may adversely affect performance, but it may be required for some kinds of systems programming (e.g. prior to and following code that alters memory mappings, to ensure that any pending writes get deferred past the mapping change, and no reads get moved before it).

DEFINITIONS:

The "outer lvalue" refers to object returned by the last pointer indirection, if any, applied in the evaluation of an lvalue, or else the type of the object before any subscripting or member-access operators, if no pointer indirections were performed.

The "type/member path" to be the type of an outer lvalue, along with whatever subscripting or member-access operators are applied to it.  A member/access path is compatible with another if the outer-lvalue type of one is the type of a step along the access path for the other, and if the access paths beyond that point are equivalent.  Note that compatibility is not an equivalence relation, because a type may have multiple access paths to the same member; the trailing portions of those
access paths would be compatible with the base type, but would not be compatible with each
other.
 
Given

   struct foo { int x, y; };
   union bar { int ints[8]; int fourpair[4][2]; int biquad[2][4]; struct foo foos[4]; }   union bar *moo;
   foo *zoo;

The outer lvalue type for "moo[4].foos[2].y" would be "union bar", since that's the result of the indirection applied by [4].  Note that the access to foos[2] is not an indirection, since foo is a pointer rather than an array.  The type/access path for that expression would be "(union bar).foos[2].y".  Note also that while "moo[4].fourpair[2][1]" and "moo[4].biquad[1][1]" would identify the same integer (which would likely be the same integer as "moo[4].foos[2].y"), they would have different access paths to it.

The outer lvalue type for "zoo->y" would be "struct foo", and the access path would be "(struct foo).y".  Note that because the type of "moos[4].foos[2]" is "struct foo", the type/access path of "zoo->y" would be compatible with that of the earlier expression.