What is the rationale behind the strict aliasing rule?

Question

I am currently wondering about the rationale behind the strict aliasing rule. I understand that certain aliasing is not allowed in C and that the intention is to allow optimizations, but I am surprised that this was the preferred solution over tracing type casts when the standard was defined.

So, apparently the following example violates the strict aliasing rule:

uint64_t swap(uint64_t val)
{
    uint64_t copy = val;
    uint32_t *ptr = (uint32_t*)© // strict aliasing violation
    uint32_t tmp = ptr[0];
    ptr[0] = ptr[1];
    ptr[1] = tmp;
    return copy;
}

I might be wrong, but as far as I can see a compiler should perfectly and trivially be able to trace down the type casts and avoid optimizations on types which are casted explicitly (just like it avoids such optimizations on same-type pointers) on anything called with the affected values.

So, which problems with the strict aliasing rule did I miss that a compiler can't solve easily to automatically detect possible optimizations)?

Griffie

Have you looked at the canonical Q&A on strict aliassing and what it means. The why is basically “because it allows more powerful optimizations”; that’s the usual reason. Same with signed integer overflow. – Jenelljenelle

@JonathanLeffler Yes I guess so, I was not thinking of a compiler without the optimization but rather a compiler which detects when such an optimization isn't possible. – Griffie

Do you have any experience on non-x86 systems? Those with strict alignment restrictions on different data types, such as double or long must be on an 8-byte boundary lest your process be killed via something like SIGBUS? That's not technically a strict aliasing issue, but it touches on a lot of the same underlying issues. – Worcestershire

@AndrewHenle Yes I am aware of that, and you are right - it's definitely worth to mention. However, I am currently only interested in the strict aliasing rule. – Griffie

uint64_t is almost by definition suitably aligned for uint32_t @AndrewHenle, so not an issue here for sure. – Unbar

Consider separate compilation. – Chantay

The marked line is not a strict aliasing violation. The violation is on the following line. – Secrecy

Answer 1

Since, in this example, all the code is visible to a compiler, a compiler can, hypothetically, determine what is requested and generate the desired assembly code. However, demonstration of one situation in which a strict aliasing rule is not theoretically needed does nothing to prove there are not other situations where it is needed.

Consider if the code instead contains:

foo(&val, ptr)

where the declaration of foo is void foo(uint64_t *a, uint32_t *b);. Then, inside foo, which may be in another translation unit, the compiler would have no way of knowing that a and b point to (parts of) the same object.

Then there are two choices: One, the language may permit aliasing, in which case the compiler, while translating foo, cannot make optimizations relying on the fact that *a and *b are different. For example, whenever something is written to *b, the compiler must generate assembly code to reload *a, since it may have changed. Optimizations such as keeping a copy of *a in registers while working with it would not be allowed.

The second choice, two, is to prohibit aliasing (specifically, not to define the behavior if a program does it). In this case, the compiler can make optimizations relying on the fact that *a and *b are different.

The C committee chose option two because it offers better performance while not unduly restricting programmers.

Solnit

Thanks, that kind of makes sense. LTO might be able to solve this issue though, isn't it? – Griffie

@Julius: In a simple case like this, we can see that foo(&val, ptr) is given two pointers to the same object. However, consider that pointers might be computed in various ways. I expect that the general problem of determining at translation time (including linking) whether two pointers might point to the same object is not computable. (Likely similar to the halting problem: If we could compute it, we could write a routine that passes the same address if and only if the code to check for that reported the code did not pass the same address.) – Solnit

I understand. Thinking about that... I guess computations could even be done during runtime and that's probably not even possible to predict. I'd still prefer a less restricting rule though :-) Thanks! – Griffie

@Griffie the non-aliasing thing is what makes Fortran so fast compared to C, they say... more info at beza1e1.tuxen.de/articles/faster_than_C.html – Unbar

@AnttiHaapala it's interesting to know that it can have a big impact. In the end I surely want those optimizations to happen, I just wish the compiler was smarter and there were more obvious and less restricting rules. – Griffie

@Julius: If compiler writers took the footnote to N1570 6.5p7 seriously, things would be simple. The stated purpose of the rule is to say when things may alias, but the situations where the rules cause the most trouble for programmers are those where things don't alias in code as written but compilers rewrite code so that they do. If compilers could simply recognize that an access via freshly-derived lvalue or pointer is an access to the object from which it is derived, that would eliminate 99% of the problems associated with the "strict aliasing rule". – Tersanctus

You forgot a third choice: write rules which are intended merely to prohibit aliasing, but express such intention in a footnote rather than a normative rule, so as to allow obtuse compiler writers to interpret them as outlawing constructs which don't involve aliasing as written. – Tersanctus

@Griffie "the compiler was smarter" so that it could detect and handle gracefully the more obvious cases? How obvious? You want to go and write the specification of the cases you would want to see supported? – Chantay

@curiousguy: If the rule had been written to say that it only applied in cases where there was no visible relationship between an lvalue used for access and anything of an appropriate type, but explicitly stated that an ability to recognize such relationships in situations where they might be useful was a Quality of Implementation issue, could anyone say with a straight face that clang's and gcc's actual behavior was consistent with any bona fide effort to behave in quality fashion? – Tersanctus

Answer 2

It allows the compiler to optimize out variable reloads without requiring that you restrict-qualify your pointers.

Example:

int f(long *L, short *S)
{
    *L=42;
    *S=43;
    return *L;
}

int g(long *restrict L, short *restrict S)
{
    *L=42;
    *S=43;
    return *L;
}

Compiled with strict aliasing disabled (gcc -O3 -fno-strict-aliasing) on x86_64 :

f:
        movl    $43, %eax
        movq    $42, (%rdi)
        movw    %ax, (%rsi)
        movq    (%rdi), %rax ; <<*L reloaded here cuz *S =43 might have changed it
        ret
g:
        movl    $43, %eax
        movq    $42, (%rdi)
        movw    %ax, (%rsi)
        movl    $42, %eax     ; <<42 constant-propagated from *L=42 because *S=43 cannot have changed it  (because of `restrict`)
        ret

Compiled with gcc -O3 (implies -fstrict-alising) on x86_64:

f:
        movl    $43, %eax
        movq    $42, (%rdi)
        movw    %ax, (%rsi)
        movl    $42, %eax   ; <<same as w/ restrict
        ret
g:
        movl    $43, %eax
        movq    $42, (%rdi)
        movw    %ax, (%rsi)
        movl    $42, %eax
        ret

https://gcc.godbolt.org/z/rQDNGt

This can help quite a bit when you're working with large arrays which might otherwise lead to a lot of unnecessary reloads.

Volga

The restrict qualifier can be even more effective than type-based aliasing if one either has no need to compare a restrict-qualified pointer for equality with anything else, or is using a compiler that doesn't treat such comparisons nonsensically. – Tersanctus

@Tersanctus It'd be nice if restrict could express everything type based aliasing can so type based aliasing then wouldn't be needed, but I'm afraid it can't so type based aliasing probably isn't going away then (not that I much care about what the committee comes up with next at this point :D). Consider an extension to my example where you take a pointer to two structs head and head_and_body where you might want to allow aliasing between the heads but not between a head and the body: gcc.godbolt.org/z/WfaEcx16T. I don't think this is expressible with restrict. – Volga

@Tersanctus I don't much like type based aliasing. It seems un-C-ish to have to circumvent it with memcpy instead of casts. But I hide the memcpy in a convenience macro, so then it doesn't look so bad (i.e., doesn't look like I'm calling a function just to make do an, e.g., integer cast). – Volga

The Standard deliberately allows compilers designed for some specialized tasks to process code in ways that would make them unsuitable for many others. It also allows implementations to, as a form of "conforming language extension", behave meaningfully in a wider range of circumstances than mandated by the Standard. An optimizer which is designed to be suitable for a particular task won't require programmers to jump through absurd hoops in order to prevent nonsensical "optimization", even if the Standard would allow it to do so. Compiler writers who insist that programmers jump through... – Tersanctus

...needless hoop should be recognized as being more interested in toying with programmers than in producing a quality product. – Tersanctus

Answer 3

Programming languages are specified to support what the members of standardisation committee believe is reasonable, common sense practice. The use of different pointers of very significantly different types aliasing the same object was believe to be unreasonable and something that compilers should not have to go out of the way to make possible.

Such code:

float f(int *pi, float *pf) {
  *pi = 1;
  return *pf;
}

when used with both pi and pf holding the same address, where *pf is meant to reinterpret the bits of the recently written *pi, is considered unreasonable thus the honorable committee members (and before them the designers of the C language) did not believe it was appropriate to require compiler to avoid common sense program transformation in a slightly more complicated example:

float f(int *pi, double *pf) {
  (*pi)++;
  (*pf) *= 2.;
  (*pi)++;
}

Here allowing the corner case where both pointers point to the same object would make any simplification where the increments are fused invalid; assuming such aliasing does not occur allows the code to be compiled as:

float f(int *pi, double *pf) {
  (*pf) *= 2.;
  (*pi) += 2;
}

Chantay

The bolded text was not really correct for C89, to my understanding. The primary motivator for C89 rules was to support the behaviour of existing implementations. – Secrecy

@Secrecy Even then the existing implementations only reflect the intuition of the designers of these compilers WRT what is "reasonable, common sense practice". – Chantay

According to the published rationale document, the authors of the C Standard weren't trying to specify everything an implementation must do to be suitable for any particular purpose, but instead expected the marketplace to drive compiler writers to produce quality implementations that supported various "popular extensions" without regard for whether the Standard required them or not. – Tersanctus

@curiousguy: The existing implementations didn't just reflect the intuition of their designers, but also their customers. Further, there is no fixed concept of "reasonable, common sense practice" that applies uniformly to all implementations. Some constructs that may represent "common sense practice" in low-level OS code may be inappropriate in high-end number-crunching code. The authors of the Standard expected that compiler writers would know more than the Standard writers about what constructs and practices would be typical of their target platforms and intended application fields. – Tersanctus

Answer 4

The footnote to N1570 p6.5p7 clearly states the purpose of the rule: to say when things may alias. As to why the rule is written so as to forbid constructs like yours which don't involve aliasing as written (since all accesses using the uint32_t* are performed in contexts where it is visibly freshly derived from the uint64_t, that's most likely because the authors of the Standard recognized that anyone making a bona fide effort to produce a quality implementation suitable for low-level programming would support constructs like yours (as a "popular extension") whether or not the Standard mandated it. This same principle appears more explicitly with regard to constructs like:

unsigned mulMod65536(unsigned short x, unsigned short y)
{ return (x*y) & 65535u; }

According to the Rationale, commonplace implementations will process operations on short unsigned values in a fashion equivalent to unsigned arithmetic even if the result is between INT_MAX+1u and UINT_MAX, except when certain conditions apply. There's no need to have a special rule to make the compiler treat expressions involving short unsigned types as unsigned when the results are coerced to unsigned because--according to the authors of the Standard--commonplace implementations do that even without such a rule.

The Standard was never intended to fully specify everything that should be expected of a quality implementation that claims to be suitable for any particular purpose. Indeed, it doesn't even require that implementations be suitable for any useful purpose whatsoever (the Rationale even acknowledges the possibility of a "conforming" implementation that is of such poor quality that cannot meaningfully process anything other than a single contrived and useless program).

Tersanctus

One issue I have with this POV is that "visibly freshly derived" is not formally defined (AFAIK), and formal specification are extremely useful to reason both about program code and compiler code. – Chantay

@curiousguy: The authors probably made the footnote non-normative to avoid having to write a precise definition of aliasing, and because the handling of some borderline cases (e.g. what a compiler should assume about pointers retrieved from volatile objects or produced via integer casts) should be treated as a Quality of Implementation issue. While the authors could have required that implementations handle certain obvious cases while leaving others as a QOI issue, I don't think they considered the notion that implementers would use the Standard as an excuse to ignore the obvious cases. – Tersanctus

@curiousguy: The authors of the Standard published a rationale document describing their intentions. They openly recognize the possibility of a "conforming" implementation that is contrived to be of such poor quality as to be useless. The fact that they don't require implementations process code in a way consistent with the Spirit of C described in the rationale in no way implies that quality implementations shouldn't be expected to do so anyhow. – Tersanctus

@curiousguy: If programmers adopted the attitude "don't do anything weird with memory without making it obvious that something weird is going on" and compiler writers adopted the attitude "make a bonafide effort to notice evidence that something weird may be going on", those principles would probably resolve most issues more easily and effectively than a more detailed standard. The situations where people squawk most loudly about -fstrict-aliasing behavior are those where the authors of gcc and clang act with wanton disregard for evidence of cross-type access patterns. – Tersanctus