17
$\begingroup$

This question is tangentially related to: Why is type reinterpretation considered highly problematic in many programming languages?

Regardless how 'problematic' type reinterpretation is, why do some languages such as C allow doing so through some avenues (memcpy, union) but not others such as pointer casts? A search reveals that the answer lies in 'optimization' but it remains unclear to me how to leaving the behavior constructs such as int x; float y = *(float *)&x; undefined permits optimizations that would not be possible if the behavior were defined the same way as if one used a union or memcpy().

$\endgroup$

3 Answers 3

27
$\begingroup$

The main thing the optimizer wants to know here is whether writes through one pointer might affect reads through other pointers or names.

When it knows for sure that two pointers are unrelated in this way (they do not ever alias) it can reorder those unrelated reads and writes for purposes like common subexpression elimination, loop-invariant code motion, or caching intermediate results in registers.

On the other hand, when pointers might alias, the optimizer becomes much more restricted in what it can do. It might be forced to re-load the same values every iteration of a loop, or re-compute the same values several times. If you've ever heard the folklore that Fortran is still faster than C, this sort of missed optimization is why people say that.

Keep in mind that the most important cases here involve pointers that are used across multiple functions. When analyzing uses of pointers that come from parameters or global variables, the compiler has much less information about data and control flow, for multiple reasons:

  • The function may called in many different places at many different times. Combining all this information would be complex, slow, and also (due to Rice's theorem) necessarily incomplete or imprecise in many cases.
  • Even with a solution to the above problem, the full set of call sites is often unknown or even unknowable- consider a library being optimized before the application that uses it.

So how does strict aliasing come into play here? It lets the compiler assume a lot of non-aliasing facts about these kinds of pointers. For example, because the program is never allowed to pass a function void f(int *x, float *y) { ... } aliasing x and y pointers, the optimizer doesn't have to do any (complicated, slow, imprecise) alias analysis of callers before processing its body. Consider this simple prefix scan:

void scan(int *length, float *array) {
    float sum = 0.0f;
    for (int i = 0; i < *length; i++) {
        sum += array[i];
        array[i] = sum;
    }
}

Clang 17 on x86-64 with -O1 generates this assembly, which loads *length once before the loop, saves in it eax, and then each iteration simply reuses eax. It can only do this because the program is not allowed to pass in a length that aliases with array- if that were allowed, writing to array[i] might change *length and thus the number of loop iterations:

scan(int*, float*):
        mov     eax, dword ptr [rdi]          # save `*length` in eax
        test    eax, eax
        jle     .LBB0_3
        xorps   xmm0, xmm0
        xor     ecx, ecx
.LBB0_2:
        addss   xmm0, dword ptr [rsi + 4*rcx]
        movss   dword ptr [rsi + 4*rcx], xmm0 # write to `array[i]`
        inc     rcx
        cmp     rax, rcx                      # reuse eax
        jne     .LBB0_2
.LBB0_3:
        ret

If we change array and sum to int, Clang no longer performs this optimization, and *length is re-loaded every iteration:

scan(int*, int*):
        cmp     dword ptr [rdi], 0
        jle     .LBB1_3
        xor     eax, eax
        xor     ecx, ecx
.LBB1_2:
        add     ecx, dword ptr [rsi + 4*rax]
        mov     dword ptr [rsi + 4*rax], ecx # write to `array[i]`
        inc     rax
        movsxd  rdx, dword ptr [rdi]         # reload `*length` into rdx
        cmp     rax, rdx
        jl      .LBB1_2
.LBB1_3:
        ret

Language designers can certainly make different choices here, but the approach taken by strict aliasing has some nice properties:

  • The rule is relatively simple to explain to programmers: "don't access an object through incompatible pointer types." Carving out more exceptions makes it more difficult to tell if a program is following the rules.
  • The rule is completely independent of compiler implementation details. Changes to make the optimizer smarter don't affect the definition of the language, nor do programmers have to know anything about how the optimizer works just to write correct programs.
  • As discussed in the question you linked, the rule is fairly close to something programmers want to follow anyway. In the rare cases they need to break it, there are options that stick out as "weird" to the reader of the code.

A couple of approaches taken by other languages:

  • Fortran defines its (non-)aliasing rules not in terms of types but in terms of parameters, so it can also optimize (its equivalent of) the int prefix sum example above.
  • Rust distinguishes "shared" pointers, which can alias but must point to an immutable object, from "unique" pointers, which can point to a mutable object but must not alias. This lets it propagate more detailed non-aliasing information through the program, and enforce it at compile time.
$\endgroup$
8
  • $\begingroup$ It's kind of strange that the optimization is dependent on the pointers being to different types. Isn't this what the restrict qualifier handles more generally? $\endgroup$
    – Barmar
    Oct 4, 2023 at 20:34
  • 4
    $\begingroup$ Yes- restrict was added to cover the cases that the strict aliasing rules don't. But restrict requires the programmer to do a lot more work, and be a lot more vigilant, so compiler writers are unlikely to give up on strict aliasing anytime soon. $\endgroup$
    – rpjohnst
    Oct 4, 2023 at 20:35
  • $\begingroup$ @Barmar: restrict isn't strictly more general, it's usable in different subset of possible (non)-aliasing cases. e.g. if int *a and int *b never point to the same thing as each other, but could be pointing to the same object as int *c, you can't use restrict unless they're separated by scope, e.g. make restrict copies of the pointers for the purpose of a loop. But if some of those pointers had different types, the different one would be known not to alias across types, even if it might alias with other pointers of the same type. e.g. foo(int *a, int *b, float *x, float *y). $\endgroup$ Oct 7, 2023 at 18:50
  • $\begingroup$ (With -fno-strict-aliasing, it would be legal if some of those float and int pointers were pointing into the same union, and the compiler couldn't re-order writes and reads on the assumption that the storage was disjoint.) $\endgroup$ Oct 7, 2023 at 18:51
  • 1
    $\begingroup$ @PeterCordes: A compiler could usefully allow most forms of type punning and still make such an assumption, while processing the code for foo, if nothing within the text of that function hinted at any means via which an int* and a float* might come to identify the same storage. It seems dubious, however, that a compiler given float *x could usefully assume an expression like *(unsigned*)x += 0x00800000; will only be invoked if x actually holds the address of an object that's never accessed as a float, despite the type of x being float*. $\endgroup$
    – supercat
    Oct 9, 2023 at 18:23
7
$\begingroup$

Aliasing

As mentioned by @rpjohnst's answer, the definite absence of aliasing is the optimization enabler. That is, a number of optimizations are only sound -- ie, do not alter the semantics -- if the pointers they operate on can be proven NOT to alias.

How the alias analysis which allows deducing this absence of aliasing is conducted has no impact on the optimizations being enabled, only on which pointers can be proven not to alias.

Alias Analysis

Proving the absence of aliasing, however, is hard. It's related to the Escape Analysis problem faced by the compilers of GC languages, and can in fact be arbitrarily hard.

Since the optimizations enabled by proving the absence of aliasing are so important, it therefore makes sense to "simplify" alias analysis by introducing rules in the language:

  • Fortran requires function parameters not to alias.
  • C and C++ have the strict aliasing rule.
  • C (since C99) has the restrict keyword, and many C++ compilers have the __restrict extension.
  • Rust has &T vs &mut T.

Why not Strict Aliasing?

Strict Aliasing is one of the early set of rules decided on to simplify alias analysis, and implemented in C and C++. It unfortunately suffers from a number of issues which later sets of rules have attempted to improve on.

Strict Aliasing, while conceptually simple and intuitive, is plagued by exceptions and accidental collisions:

  • Accidental Collisions: as demonstrated in @rpjohnst's answer a function taking two parameters -- a length int* and an array T* -- will not be as well optimized when it turns out that T = int, because suddenly Strict Aliasing cannot exclude the possibility of aliasing. This is made even worse by the fact that int32_t is just a typedef of int on most platforms, so that even types that are not spelled the same may "accidentally" be the same and foil Strict Aliasing.
  • Exceptions: exceptions are carved into the rule for char* and unsigned char*, allowing those to aliasing everything. It's a useful exception... but also a very unfortunate one seeing as char* is a widely used pointer type whenever one uses strings or raw memory.

C99 introduced the restrict qualifier for much more fine-grained annotations, which do not fall apart by accident.

$\endgroup$
0
6
$\begingroup$

The issue is discussed explicitly in the C99 Rationale at https://www.open-std.org/jtc1/sc22/wg14/www/C99RationaleV5.10.pdf starting on page 59, line 33, and continuing through the top of line 61. The basic idea is that given a function like [from the Rationale]:

int a;
void f( double * b )
{
  a = 1;
  *b = 2.0;
  g(a);
}

it's likely that a compiler's customers wouldn't mind if the compiler were to replace the call g(a) with a call to g(1). There are some contrived scenarios where that substitution would be (as noted in the Rationale) "incorrect", but the view of the Committee was that if a compiler's customers wouldn't demand that a compiler accommodate such possibilities, the Committee shouldn't either. Note that because compilers would always be allowed to access such constructs "in a documented manner characteristic of the environment", any compilers whose customers would care about such constructs remained free to process them in the "correct" manner. Such code may not be portable, but as observed on page 13, in discussing conformance, "A strictly conforming program is another term for a maximally portable program. The goal is to give the programmer a fighting chance to make powerful C programs that are also highly portable, without seeming to demean perfectly useful C programs that happen not to be portable, thus the adverb strictly."

Note that the example shows a relatively non-controversial and safe kind of optimization: saying that if storage is accessed as type T and later read again as type T, and if no intervening actions have any visible relationship to anything having to do with type T, a compiler may replace the load implied by the second operation with code that re-uses the previous value read or written. This optimization is simple but effective and relatively safe, and will be compatible even with most code for which clang and gcc would require -fno-strict-aliasing, provided only that a compiler makes a good faith effort to notice when intervening actions have a visible relationship to the type involved.

Note that because a function like:

unsigned get_float_bits(float *fp)
{
  return *(unsigned*)fp;
}

would be non-portable, the Standard makes no attempt to exercise jurisdiction over how compilers treat it. It was obvious to just about everyone when the Standard was written that anyone wanting to sell compilers to anyone who would find such constructs useful should process such constructs "in a documented manner characteristic of the environment" with or without a mandate, and thus there was no need for the Standard to recognize such constructs.

Note that the authors of the Standard get unfairly maligned for the Standard's failure to forbid nonsensical compiler behavior, as though they intended to invite such nonsense. The Standard was a compromise between people who wanted to recognize non-portable constructs as legitimate, and those who wanted to forbid anything that wasn't portable; the solution was to have the Standard waive jurisdiction over such constructs. If waiver of jurisdiction is recognized as implying nothing about how implementations process constructs that are intended to perform tasks in non-portable fashion, the Standard's categorization of constructs that are useful but non-portable as Undefined Behavior is entirely appropriate.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .