GCC and strict aliasing between arrays of a same type

Question

Context

“Strict aliasing”, named after the GCC optimization, is an assumption by the compiler that a value in memory will not be accessed through an lvalue of a type (the “declared type”) very different from the type the value was written with (the “effective type”). This assumption allows code transformations that would be incorrect if the possibility had to be taken into account that writing to a pointer to float could modify a global variable of type int.

Both GCC and Clang, extracting the most meaning out of a standard description full of dark corners, and having a bias for performance of generated code in practice, assume that a pointer to the int first member of a struct thing does not alias a pointer to the int first member of a struct object:

struct thing { int a; };
struct object { int a; };

int e(struct thing *p, struct object *q) {
  p->a = 1;
  q->a = 2;
  return p->a;
}

Both GCC and Clang infer that the function always return 1, that is, that p and q cannot be aliases for the same memory location:

e:
        movl    $1, (%rdi)
        movl    $1, %eax
        movl    $2, (%rsi)
        ret

As long as one agrees with the reasoning for this optimization, it should be no surprise that p->t[3] and q->t[2] are also assumed to be disjoint lvalues in the following snippet (or rather, that the caller causes UB if they alias):

struct arr { int t[10]; };

int h(struct arr *p, struct arr *q) {
  p->t[3] = 1;
  q->t[2] = 2;
  return p->t[3];
}

GCC optimizes the above function h:

h:
        movl    $1, 12(%rdi)
        movl    $1, %eax
        movl    $2, 8(%rsi)
        ret

So far so good, as long as one sees p->a or p->t[3] as somehow accessing a whole struct thing (resp. struct arr), it is possible to argue that making the locations alias would break the rules laid out in 6.5:6-7. An argument that this is GCC's approach is this message, part of a long thread that also discussed the role of unions in strict aliasing rules.

Question

I have doubts, however, about the following example, in which there is no struct:

int g(int (*p)[10], int (*q)[10]) {
  (*p)[3] = 1;
  (*q)[4] = 2;
  return (*p)[3];
}

GCC versions 4.4.7 through the current version 7 snapshot on Matt Godbolt's useful website optimize function g as if (*p)[3] and (*q)[4] could not alias (or rather, as if the program had invoked UB if they did):

g:
        movl    $1, 12(%rdi)
        movl    $1, %eax
        movl    $2, 16(%rsi)
        ret

Is there any reading of the standard that justifies this very strict approach to strict aliasing? If GCC's optimization here can be justified, would the arguments apply as well to the optimization of functions f and k, which are not optimized by GCC?

int f(int (*p)[10], int (*q)[9]) {
  (*p)[3] = 1;
  (*q)[3] = 2;
  return (*p)[3];
}

int k(int (*p)[10], int (*q)[9]) {
  (*p)[3] = 1;
  (*q)[2] = 2;
  return (*p)[3];
}

I'm willing to take this up with the GCC devs, but I should first decide without I am reporting a correctness bug for function g or a missed optimization for f and k.

Answer 1

In:

int g(int (*p)[10], int (*q)[10]) {
  (*p)[3] = 1;
  (*q)[4] = 2;
  return (*p)[3];
}

*p and *q are lvalues of array type; If they may overlap, access to them is governed by section 6.5 paragraph 7 (the so called "strict aliasing rule"). However, since their type is the same, that does not present a problem for this code. The standard is however remarkably vague regarding a number of relevant concerns that would be required to give a comprehensive answer to this question, such as:

• Do (*p) and (*q) actually necessitate "access" (as the term is used in 6.5p7) to the arrays to which they point? If they do not, it's tempting to take the view that the expressions (*p)[3] and (*q)[4] essentially degrade to pointer arithmetic and dereference of two int *s which can clearly alias. (This isn't an entirely unreasonable standpoint; 6.5.2.1 Array Subscripting says that One of the expressions shall have type ‘‘pointer to complete object type’’, the other expression shall have integer type, and the result has type ‘‘type’’ - so the array lvalue has necessarily degraded to a pointer as per usual conversion rules; the only question is whether the array was accessed before the conversion occurred).

• However, to defend the view that (*p)[3] is purely equivalent to *((int *)p + 3), we'd have to show that (*p)[3] doesn't require evaluation of (*p), or that if it does, the access does not have undefined behaviour (or defined but unwanted behaviour). I don't believe there is any justification in the precise wording of the standard to allow that (*p) is not evaluated; this implies that the expression (*p) must not have undefined behaviour if the behaviour of (*p)[3] is defined. So, the question really boils down to whether *p and *q have defined behaviour if they refer to partially overlapping arrays of the same type, and indeed whether it is possible that they can simultaneously do so.

For the definition of the * operator, the standard says:

if it points to an object, the result is an lvalue designating the object

• does this mean that the pointer must point to the start of the object? (It seems likely that this is what is meant). Does the object have to have been established somehow before it can be accessed (and does establishing an object disestablish any overlapping object)? If both are the case, *p and *q cannot overlap - since establishing either object would invalidate the other - and so (*p)[3] and (*q)[4] cannot alias.

The problem is that there is no suitable guidance on these questions. In my view, a conservative approach should be taken: do not assume that this kind of aliasing is legal.

In particular, the "effective type" wording in 6.5 suggests a means by which an object of a particular type can be established. It seems like a good bet that this is intended to be definitive; that is, that you cannot establish an object other than by setting its effective type (including by means of it having a declared type), and that access by other types is restricted; further, establishing an object un-establishes any existing overlapping object (to be clear, this is extrapolation, not the actual wording). Thus if (*p)[3] and (*q)[4] could alias, then either p or q does not point to an object, and therefore one of either *p or *q has undefined behaviour.

Answer 2

IMHO, the standard does not allow arrays of definite size to overlap at the same time(*). Draft n1570 says in 6.2.7 Compatible type and composite type (emphasis mine):

§2 All declarations that refer to the same object or function shall have compatible type; otherwise, the behavior is undefined.

§3 A composite type can be constructed from two types that are compatible; it is a type that is compatible with both of the two types and satisfies the following conditions:

• If both types are array types, the following rules are applied:
  • If one type is an array of known constant size, the composite type is an array of that size.
    ...

As an object shall have its stored value accessed only by an lvalue expression that has a compatible type (simplified reading of 6.5 Expressions §7), you cannot alias arrays of different sizes, nor can you have arrays of the same size that overlap. So, in function g, p and q should either point to the same array or to non-overlapping arrays, which allows the optimization.

For functions f and k, my understanding is that the optimization would be allowed per the standard but has not been implemented by the developers. We must remember that as soon as one of the parameters is a simple pointer, it is allowed to point to any element of the other array and no optimization can occur. So I think that the absence of optimization is just an example of the famous rule for UB: anything can happen, including the expected result.